第 2 节 BACKGROUND 逐段精读
这一节是全文的"数学地基"。它要回答一个问题："矩阵乘法 + 秩"这一套线性代数工具，能不能搬到 max-plus 这种奇怪的运算体系里？ 如果能，那第 4 节的并行算法就有依据。
下面按论文顺序，把五个概念逐一吃透。
一、半环（Semiring）：为什么需要它
1. 论文原定义
A semiring is a five-tuple ( D , ⊕ , ⊗ , 0 , 1 ) (D,\oplus ,\otimes ,0,1) ( D , ⊕ , ⊗ , 0 , 1 ) ( D , ⊕ , 0 ) (D,\oplus ,0) ( D , ⊕ , 0 ) ( D , ⊗ , 1 ) (D,\otimes ,1) ( D , ⊗ , 1 ) ⊕ \oplus ⊕ O \mathbb{O} O ⊗ \otimes ⊗
2. 用大白话解释
半环 = 一个集合 + 两种运算 + 一套"像加法和乘法"的公理。
普通实数上有加法和乘法，满足一整套好用的规律。半环就是抽象出这些规律 ，但不要求必须有"减法"（不要求每个元素有逆元）。所以半环比"环"弱，但足够支撑矩阵乘法。
论文列的六条公理，翻译成人话：
公理 含义 ( D , ⊕ , 0 ) (D,\oplus,0) ( D , ⊕ , 0 ) ⊕ \oplus ⊕ 0 0 0 ( D , ⊗ , 1 ) (D,\otimes,1) ( D , ⊗ , 1 ) ⊗ \otimes ⊗ 1 1 1 分配律 x ⊗ ( y ⊕ z ) = ( x ⊗ y ) ⊕ ( x ⊗ z ) x\otimes(y\oplus z)=(x\otimes y)\oplus(x\otimes z) x ⊗ ( y ⊕ z ) = ( x ⊗ y ) ⊕ ( x ⊗ z ) 0 0 0 ⊗ \otimes ⊗ x ⊗ 0 = 0 x\otimes 0=0 x ⊗ 0 = 0
关键点 ：
只要求结合律 ，不要求交换律（⊗ \otimes ⊗
不要求有减法/逆元。这正是热带半环能成立的原因——max 没有逆运算。
有分配律，才能把矩阵乘法展开成"乘加"形式。
3. 为什么需要半环
因为后面要定义矩阵乘法 。矩阵乘法的核心公式是
( A B ) [ i , j ] = ⨁ k ( A [ i , k ] ⊗ B [ k , j ] ) (AB)[i,j]=\bigoplus_k (A[i,k]\otimes B[k,j]) ( A B ) [ i , j ] = k ⨁ ( A [ i , k ] ⊗ B [ k , j ]) 要让这个公式有良好的代数性质（尤其是结合律 ，这是并行算法能拆分矩阵连乘的前提），就必须保证 ⊕ , ⊗ \oplus,\otimes ⊕ , ⊗ 结合律是第 4 节把 A n ⋯ A 1 A_n\cdots A_1 A n ⋯ A 1
二、热带半环（Tropical Semiring）：本文的工作舞台
1. 论文原定义
The semiring ( R ∪ { − ∞ } , max , + , − ∞ , 0 ) (\mathbb{R}\cup \{-\infty \} ,\max , + , - \infty ,0) ( R ∪ { − ∞ } , max , + , − ∞ , 0 ) − ∞ -\infty − ∞ ⊕ \oplus ⊕ + + + ⊗ \otimes ⊗
2. 逐项对照
半环要素 热带半环中的具体含义 域 D D D R ∪ { − ∞ } \mathbb{R}\cup\{-\infty\} R ∪ { − ∞ } − ∞ -\infty − ∞ 加法 ⊕ \oplus ⊕ max \max max 乘法 ⊗ \otimes ⊗ 普通加法 + + + 加法单位元 0 0 0 − ∞ -\infty − ∞ max ( x , − ∞ ) = x \max(x,-\infty)=x max ( x , − ∞ ) = x 乘法单位元 1 1 1 0 0 0 x + 0 = x x+0=x x + 0 = x
3. 验证六条公理
公理 在热带半环中是否成立 为什么 max \max max ✅ max ( max ( a , b ) , c ) = max ( a , max ( b , c ) ) \max(\max(a,b),c)=\max(a,\max(b,c)) max ( max ( a , b ) , c ) = max ( a , max ( b , c )) max \max max − ∞ -\infty − ∞ ✅ max ( a , − ∞ ) = a \max(a,-\infty)=a max ( a , − ∞ ) = a max \max max ✅ max ( a , b ) = max ( b , a ) \max(a,b)=\max(b,a) max ( a , b ) = max ( b , a ) + + + ✅ 普通加法结合律 + + + 0 0 0 ✅ a + 0 = a a+0=a a + 0 = a 分配律 ✅ a + max ( b , c ) = max ( a + b , a + c ) a+\max(b,c)=\max(a+b,a+c) a + max ( b , c ) = max ( a + b , a + c ) − ∞ -\infty − ∞ + + + ✅ a + ( − ∞ ) = − ∞ a+(-\infty)=-\infty a + ( − ∞ ) = − ∞
全部成立。 所以热带半环确实是半环。
4. 最反直觉的地方
在热带半环里：
"加法"是取最大值，没有减法 （你不能"减掉"一个 max）。
"乘法"是普通加法，但它的"零"是 − ∞ -\infty − ∞
普通的 0 在这里是"乘法单位元 1"，即 x ⊗ 0 = x + 0 = x x\otimes 0=x+0=x x ⊗ 0 = x + 0 = x
这就是为什么论文说：
Alternately, one can reverse the sign of every element in the domain and change the additive operation to min.
把 max 换成 min、所有数取负，得到等价的"min-plus"版本，很多文献用这个。本文用 max-plus。
5. 为什么 DP 会落到热带半环里
回看 LTDP 递推：
s i [ j ] = max k ( s i − 1 [ k ] + A i [ j , k ] ) s_i[j]=\max_k(s_{i-1}[k]+A_i[j,k]) s i [ j ] = k max ( s i − 1 [ k ] + A i [ j , k ]) 这正是"max 当加法、+ 当乘法"的矩阵-向量乘法。所以 DP 天然就是热带半环下的线性代数。
三、矩阵乘法：把普通公式里的符号换掉
1. 论文原定义
( A ⊙ B ) [ i , j ] = ⨁ 1 ≤ k ≤ m ( A [ i , k ] ⊗ B [ k , j ] ) = max 1 ≤ k ≤ m ( A [ i , k ] + B [ k , j ] ) . (A\odot B)[i,j] = \bigoplus_{1\leq k\leq m}(A[i,k]\otimes B[k,j]) = \max_{1\leq k\leq m}(A[i,k] + B[k,j]). ( A ⊙ B ) [ i , j ] = ⨁ 1 ≤ k ≤ m ( A [ i , k ] ⊗ B [ k , j ]) = max 1 ≤ k ≤ m ( A [ i , k ] + B [ k , j ]) .
2. 普通矩阵乘法 vs 热带矩阵乘法
普通 ：
( A B ) [ i , j ] = ∑ k A [ i , k ] ⋅ B [ k , j ] (AB)[i,j]=\sum_k A[i,k]\cdot B[k,j] ( A B ) [ i , j ] = k ∑ A [ i , k ] ⋅ B [ k , j ] 热带 ：
( A ⊙ B ) [ i , j ] = max k ( A [ i , k ] + B [ k , j ] ) (A\odot B)[i,j]=\max_k \big(A[i,k]+B[k,j]\big) ( A ⊙ B ) [ i , j ] = k max ( A [ i , k ] + B [ k , j ] ) 逐项替换 ：∑ → max \sum \to \max ∑ → max ⋅ → + \cdot \to + ⋅ → +
3. 手算一个例子
设
A = ( 1 2 3 0 ) , B = ( 0 4 1 2 ) A=\begin{pmatrix}1&2\\3&0\end{pmatrix},\quad
B=\begin{pmatrix}0&4\\1&2\end{pmatrix} A = ( 1 3 2 0 ) , B = ( 0 1 4 2 ) 计算 A ⊙ B A\odot B A ⊙ B
max ( A [ 0 , 0 ] + B [ 0 , 0 ] , A [ 0 , 1 ] + B [ 1 , 0 ] ) = max ( 1 + 0 , 2 + 1 ) = max ( 1 , 3 ) = 3 \max(A[0,0]+B[0,0],\ A[0,1]+B[1,0])=\max(1+0,\ 2+1)=\max(1,3)=3 max ( A [ 0 , 0 ] + B [ 0 , 0 ] , A [ 0 , 1 ] + B [ 1 , 0 ]) = max ( 1 + 0 , 2 + 1 ) = max ( 1 , 3 ) = 3 (0,1) 元素：
max ( 1 + 4 , 2 + 2 ) = max ( 5 , 4 ) = 5 \max(1+4,\ 2+2)=\max(5,4)=5 max ( 1 + 4 , 2 + 2 ) = max ( 5 , 4 ) = 5 (1,0) 元素：
max ( 3 + 0 , 0 + 1 ) = max ( 3 , 1 ) = 3 \max(3+0,\ 0+1)=\max(3,1)=3 max ( 3 + 0 , 0 + 1 ) = max ( 3 , 1 ) = 3 (1,1) 元素：
max ( 3 + 4 , 0 + 2 ) = max ( 7 , 2 ) = 7 \max(3+4,\ 0+2)=\max(7,2)=7 max ( 3 + 4 , 0 + 2 ) = max ( 7 , 2 ) = 7 所以
A ⊙ B = ( 3 5 3 7 ) A\odot B=\begin{pmatrix}3&5\\3&7\end{pmatrix} A ⊙ B = ( 3 3 5 7 ) 对比普通乘法 A B = ( 2 8 0 12 ) AB=\begin{pmatrix}2&8\\0&12\end{pmatrix} A B = ( 2 0 8 12 ) 运算结构 一样。
4. 为什么这个定义对 DP 有用
把 A i A_i A i s ⃗ i − 1 \vec{s}_{i-1} s i − 1
s ⃗ i [ j ] = ( A i ⊙ s ⃗ i − 1 ) [ j ] = max k ( A i [ j , k ] + s ⃗ i − 1 [ k ] ) \vec{s}_i[j]=(A_i\odot \vec{s}_{i-1})[j]=\max_k(A_i[j,k]+\vec{s}_{i-1}[k]) s i [ j ] = ( A i ⊙ s i − 1 ) [ j ] = k max ( A i [ j , k ] + s i − 1 [ k ]) 正是 LTDP 递推。所以DP 的一个阶段 = 一次热带矩阵-向量乘法 。
5. 转置与向量记号的说明
论文说：
The transpose of A n × m A_{n\times m} A n × m A m × n T A_{m\times n}^{\mathrm{T}} A m × n T ∀ i , j : A T [ i , j ] = A [ j , i ] \forall i,j:A^{\mathrm{T}}[i,j] = A[j,i] ∀ i , j : A T [ i , j ] = A [ j , i ]
这是标准转置，没有变化。论文用 v ⃗ \vec{v} v v ⃗ T \vec{v}^{\mathrm{T}} v T
6. 结合律（Lemma 2.1）
LEMMA 2.1. Matrix multiplication is associative in semirings: ( A ⊙ B ) ⊙ C = A ⊙ ( B ⊙ C ) . (A\odot B)\odot C = A\odot (B\odot C). ( A ⊙ B ) ⊙ C = A ⊙ ( B ⊙ C ) .
这是全文最重要的数学事实。 它来自半环的分配律和结合律。
为什么重要 ：
如果矩阵乘法可结合，那么 A n ⊙ A n − 1 ⊙ ⋯ ⊙ A 1 A_n\odot A_{n-1}\odot\cdots\odot A_1 A n ⊙ A n − 1 ⊙ ⋯ ⊙ A 1
第 4 节说"两个处理器可以分别计算 A n ⋯ A n / 2 + 1 A_n\cdots A_{n/2+1} A n ⋯ A n /2 + 1 A n / 2 ⋯ A 1 A_{n/2}\cdots A_1 A n /2 ⋯ A 1
但注意 ：论文紧接着说，虽然理论可结合，但直接做矩阵-矩阵乘法会带来线性开销，不实用。所以后面用"秩收敛"绕开它。结合律是"理论上允许并行"的依据，秩收敛是"实际高效并行"的依据。
四、平行向量（Parallel Vectors）：热带版的"共线"
1. 论文原定义
Two vectors u ⃗ \vec{u} u v ⃗ \vec{v} v u ⃗ ∥ v ⃗ \vec{u}\parallel \vec{v} u ∥ v x x x y y y u ⃗ ⊙ x = v ⃗ ⊙ y \vec{u}\odot x = \vec{v}\odot y u ⊙ x = v ⊙ y
2. 在热带半环里 "u ⃗ ⊙ x \vec{u}\odot x u ⊙ x
标量乘向量：每个元素都"乘"上 x x x
( u ⃗ ⊙ x ) [ i ] = u ⃗ [ i ] + x (\vec{u}\odot x)[i]=\vec{u}[i]+x ( u ⊙ x ) [ i ] = u [ i ] + x 即：给向量每个分量加同一个常数 x x x 。
3. 定义的含义
u ⃗ ∥ v ⃗ \vec{u}\parallel\vec{v} u ∥ v x , y x,y x , y
u ⃗ + x = v ⃗ + y \vec{u}+x=\vec{v}+y u + x = v + y 等价于
u ⃗ − v ⃗ = y − x = 常数 \vec{u}-\vec{v}=y-x=\text{常数} u − v = y − x = 常数 所以热带半环下的"平行" = 两个向量只差一个常数偏移 。
4. 例子
论文说：
[ 1 0 2 ] T [1\ 0\ 2]^{\mathrm{T}} [ 1 0 2 ] T [ 3 2 4 ] T [3\ 2\ 4]^{\mathrm{T}} [ 3 2 4 ] T
验证：
[ 3 , 2 , 4 ] T = [ 1 , 0 , 2 ] T + 2 [3,2,4]^{\mathrm{T}}=[1,0,2]^{\mathrm{T}}+2 [ 3 , 2 , 4 ] T = [ 1 , 0 , 2 ] T + 2 每个分量都加了 2，所以平行。
5. 和普通线性代数"平行"的区别
概念 普通线性代数 热带半环 平行 u ⃗ = c v ⃗ \vec{u}=c\vec{v} u = c v 倍数 ）u ⃗ = v ⃗ + c \vec{u}=\vec{v}+c u = v + c 常数 ）方向 由比例决定 由分量之间的相对差 决定 例子 [ 1 , 2 ] [1,2] [ 1 , 2 ] [ 2 , 4 ] [2,4] [ 2 , 4 ] [ 1 , 0 , 2 ] [1,0,2] [ 1 , 0 , 2 ] [ 3 , 2 , 4 ] [3,2,4] [ 3 , 2 , 4 ]
直觉 ：热带半环里，"方向"不是看比例，而是看各分量之间的差 。把整个向量平移一个常数，方向不变。
6. 为什么这个定义重要
第 4 节的秩收敛告诉我们：从任意初始向量出发，经过足够多阶段，得到的向量会平行于 真实解。
平行向量虽然数值不同，但相对结构相同 。
而 Lemma 3.1 将证明：平行向量产生相同的前驱（predecessor） 。所以"平行"就够了，不需要"相等"。
7. 为什么要求 x , y ≠ − ∞ x,y\neq -\infty x , y = − ∞
论文说：
Note that the previous definition requires the two scalars not to be − ∞ -\infty − ∞ − ∞ -\infty − ∞
因为如果 x = − ∞ x=-\infty x = − ∞ u ⃗ + ( − ∞ ) \vec{u}+(-\infty) u + ( − ∞ ) − ∞ -\infty − ∞ − ∞ -\infty − ∞
五、矩阵秩（Matrix Rank）：本文用"分解维数"定义
1. 论文原定义
The rank of a matrix M m × n M_{m\times n} M m × n rank ( M ) \operatorname{rank}(M) rank ( M ) r r r C m × r C_{m\times r} C m × r R r × n R_{r\times n} R r × n M M M
2. 用大白话解释
秩 = 把矩阵分解成"高瘦矩阵 × 矮胖矩阵"时，中间那个维度最小能取多少。
图示：
M = C ⊙ R
m×n m×r r×n
↑
中间维度 r 尽可能小
如果 r = 1 r=1 r = 1
M = c ⃗ ⊙ r ⃗ T M=\vec{c}\odot\vec{r}^{\mathrm{T}} M = c ⊙ r T 即一列 × 一行 ，所有行都"平行"（只差常数），所有列也"平行"。
3. 和普通秩定义的对比
论文特别警告：
There are alternate ways to define the rank of a matrix in semirings, such as the number of linearly independent rows or columns in a matrix. While such definitions coincide in fields (which have inverses for ⊕ \oplus ⊕ ⊗ \otimes ⊗
普通线性代数（域上） ：
秩 = 线性无关行数 = 线性无关列数 = 最大非零子式阶数 = 像空间维数。
这些定义等价 ，因为有减法/逆元。
半环中 ：
"线性无关"很难定义（没有减法）。
各种定义不再等价 。
论文选用"最小分解维数"这个定义，因为它在半环里最自然、最可操作 ，而且直接支撑后面的秩收敛论证。
4. 为什么这个定义适合并行算法
回顾第 4 节要用的两个性质：
(a) 秩不增 ：rank ( A ⊙ B ) ≤ min ( rank ( A ) , rank ( B ) ) \operatorname{rank}(A\odot B)\le\min(\operatorname{rank}(A),\operatorname{rank}(B)) rank ( A ⊙ B ) ≤ min ( rank ( A ) , rank ( B ))
用"分解维数"定义，证明极简洁（我们上一轮已经推过）：
若 A = C ⊙ R A=C\odot R A = C ⊙ R r r r A ⊙ B = C ⊙ ( R ⊙ B ) A\odot B=C\odot(R\odot B) A ⊙ B = C ⊙ ( R ⊙ B ) r r r r r r
这个论证只用了结合律 ，不需要减法，所以在半环里照样成立。
(b) 秩 1 矩阵把所有向量映到一条线上 ：Lemma 2.2。
LEMMA 2.2. For any vectors u ⃗ \vec{u} u v ⃗ \vec{v} v A A A A ⊙ u ⃗ ∥ A ⊙ v ⃗ A\odot \vec{u}\parallel A\odot \vec{v} A ⊙ u ∥ A ⊙ v
证明（论文原文）：
若 rank ( A ) = 1 \operatorname{rank}(A)=1 rank ( A ) = 1 A = c ⃗ ⊙ r ⃗ T A=\vec{c}\odot\vec{r}^{\mathrm{T}} A = c ⊙ r T
A ⊙ u ⃗ = ( c ⃗ ⊙ r ⃗ T ) ⊙ u ⃗ = c ⃗ ⊙ ( r ⃗ T ⊙ u ⃗ ) = c ⃗ ⊙ x u A\odot\vec{u}=(\vec{c}\odot\vec{r}^{\mathrm{T}})\odot\vec{u}=\vec{c}\odot(\vec{r}^{\mathrm{T}}\odot\vec{u})=\vec{c}\odot x_u A ⊙ u = ( c ⊙ r T ) ⊙ u = c ⊙ ( r T ⊙ u ) = c ⊙ x u A ⊙ v ⃗ = ( c ⃗ ⊙ r ⃗ T ) ⊙ v ⃗ = c ⃗ ⊙ ( r ⃗ T ⊙ v ⃗ ) = c ⃗ ⊙ x v A\odot\vec{v}=(\vec{c}\odot\vec{r}^{\mathrm{T}})\odot\vec{v}=\vec{c}\odot(\vec{r}^{\mathrm{T}}\odot\vec{v})=\vec{c}\odot x_v A ⊙ v = ( c ⊙ r T ) ⊙ v = c ⊙ ( r T ⊙ v ) = c ⊙ x v 其中 x u = r ⃗ T ⊙ u ⃗ x_u=\vec{r}^{\mathrm{T}}\odot\vec{u} x u = r T ⊙ u x v = r ⃗ T ⊙ v ⃗ x_v=\vec{r}^{\mathrm{T}}\odot\vec{v} x v = r T ⊙ v
所以 A ⊙ u ⃗ A\odot\vec{u} A ⊙ u A ⊙ v ⃗ A\odot\vec{v} A ⊙ v c ⃗ \vec{c} c 平行 。
直观 ：秩 1 矩阵只有一个"方向"，不管输入向量是什么，输出都被压到 c ⃗ \vec{c} c
5. 论文的例子
A = [ 123 ] ⊤ ⊙ [ 012 ] A=[123]^\top \odot [012] A = [ 123 ] ⊤ ⊙ [ 012 ] A ⊙ u ⃗ = [ 67 ] ⊺ A\odot \vec{u}=[67]^{\intercal} A ⊙ u = [ 67 ] ⊺ A ⊙ v ⃗ = [ 456 ] ⊺ A\odot \vec{v}=[456]^{\intercal} A ⊙ v = [ 456 ] ⊺
验证一下这个例子（注意这是热带半环）：
设 c ⃗ = [ 1 , 2 , 3 ] T \vec{c}=[1,2,3]^{\mathrm{T}} c = [ 1 , 2 , 3 ] T r ⃗ T = [ 0 , 1 , 2 ] \vec{r}^{\mathrm{T}}=[0,1,2] r T = [ 0 , 1 , 2 ]
A [ i , j ] = c ⃗ [ i ] + r ⃗ [ j ] = [ 1 , 2 , 3 ] T + [ 0 , 1 , 2 ] A[i,j]=\vec{c}[i]+\vec{r}[j]=[1,2,3]^{\mathrm{T}}+[0,1,2] A [ i , j ] = c [ i ] + r [ j ] = [ 1 , 2 , 3 ] T + [ 0 , 1 , 2 ] 得到
A = ( 1 2 3 2 3 4 3 4 5 ) A=\begin{pmatrix}1&2&3\\2&3&4\\3&4&5\end{pmatrix} A = 1 2 3 2 3 4 3 4 5 取 u ⃗ \vec{u} u v ⃗ \vec{v} v r ⃗ T ⊙ u ⃗ = 6 \vec{r}^{\mathrm{T}}\odot\vec{u}=6 r T ⊙ u = 6 r ⃗ T ⊙ v ⃗ = 4 \vec{r}^{\mathrm{T}}\odot\vec{v}=4 r T ⊙ v = 4 u ⃗ , v ⃗ \vec{u},\vec{v} u , v A ⊙ u ⃗ = [ 6 , 7 , 8 ] T A\odot\vec{u}=[6,7,8]^{\mathrm{T}} A ⊙ u = [ 6 , 7 , 8 ] T A ⊙ v ⃗ A\odot\vec{v} A ⊙ v
关键是：两个输出向量每个分量都差 2，所以平行。
Also note that all rows in a rank-1 matrix are parallel to each other.
因为 A A A i i i c ⃗ [ i ] + r ⃗ T \vec{c}[i]+\vec{r}^{\mathrm{T}} c [ i ] + r T c ⃗ [ i ] − c ⃗ [ i ′ ] \vec{c}[i]-\vec{c}[i'] c [ i ] − c [ i ′ ] 秩 1 矩阵 = 所有行共线、所有列共线。
六、这一节的"骨架图"
把五个概念串起来：
半环（Semiring）
│ 提供两种运算 + 公理
│ 核心：结合律 + 分配律
↓
热带半环（Tropical Semiring）
│ ⊕ = max, ⊗ = +
│ 0 = -∞, 1 = 0
↓
热带矩阵乘法（⊙）
│ (A⊙B)[i,j] = max_k(A[i,k]+B[k,j])
│ 满足结合律（Lemma 2.1）
↓
├──→ 平行向量（∥）
│ ū∥v̄ ⟺ ū = v̄ + 常数
│ 用于定义"方向相同、只差偏移"
│
└──→ 矩阵秩（rank）
最小分解维数 r
rank(A⊙B) ≤ min(rank(A), rank(B))
rank 1 矩阵把所有向量映到一条线（Lemma 2.2）
七、每个概念"后面会用在哪里"
概念 后续用途 半环公理（尤其结合律） 第 4.1 节：理论上可把矩阵连乘拆开并行 热带半环 第 3 节：把 LTDP 写成 s ⃗ i = A i ⊙ s ⃗ i − 1 \vec{s}_i=A_i\odot\vec{s}_{i-1} s i = A i ⊙ s i − 1 热带矩阵乘法 第 3 节：LTDP 的递推就是一次热带矩阵-向量乘法 平行向量 ∥ \parallel ∥ 第 4.2 节：秩收敛后，解向量"平行"于真实解即可；Lemma 3.1：平行向量前驱相同 矩阵秩（分解维数） 第 4.2 节：秩不增 → 秩收敛 → 可打破阶段依赖 秩 1 矩阵 Lemma 2.2 第 4.2 节：秩 1 保证从任意初始向量出发，结果都平行于真实解 − ∞ -\infty − ∞ 第 4.5 节：初始向量必须 all-non-zero，避免塌缩
八、最容易踩的坑
"加法"不是加法 。热带半环里 ⊕ = max \oplus=\max ⊕ = max a ⊕ b a\oplus b a ⊕ b
"乘法"是普通加法 。⊗ = + \otimes=+ ⊗ = + a ⊗ b a\otimes b a ⊗ b a + b a+b a + b A [ i , k ] + B [ k , j ] A[i,k]+B[k,j] A [ i , k ] + B [ k , j ]
"零"是 − ∞ -\infty − ∞ 。热带半环的加法单位元是 − ∞ -\infty − ∞ max ( x , − ∞ ) = x \max(x,-\infty)=x max ( x , − ∞ ) = x x + 0 = x x+0=x x + 0 = x − ∞ -\infty − ∞
"平行"不是"成比例" 。是"差一个常数"，不是"差一个倍数"。[ 1 , 0 , 2 ] [1,0,2] [ 1 , 0 , 2 ] [ 2 , 0 , 4 ] [2,0,4] [ 2 , 0 , 4 ] 不平行 （差分别是 1,0,2，不是常数），但 [ 1 , 0 , 2 ] [1,0,2] [ 1 , 0 , 2 ] [ 3 , 2 , 4 ] [3,2,4] [ 3 , 2 , 4 ]
秩的定义不是"线性无关行数" 。论文明确说半环里这些定义不等价，本文用"最小分解维数"。证明秩不增时也只能用这个定义。
结合律成立 ≠ 可以随便做矩阵-矩阵乘法 。第 4.1 节明确说，直接做矩阵-矩阵乘法开销是线性的，不实用。结合律只是"允许"并行，实际算法要靠秩收敛绕开矩阵-矩阵乘法。
九、一句话总结第 2 节
热带半环把 max 当加法、+ 当乘法，构成一个满足结合律和分配律的代数系统；在这个系统里矩阵乘法有良好定义且可结合，平行向量定义为"差一个常数"，矩阵秩定义为"最小分解维数"；这三样工具——结合律、平行、秩不增——共同支撑了第 4 节"从任意初始值出发、靠秩收敛到 1 来打破阶段依赖"的并行算法。
下一步进入 第 3 节 LINEAR-TROPICAL DYNAMIC PROGRAMMING ，把"DP 如何严格写成热带矩阵乘法"以及"前驱乘积（predecessor product）"这两个关键点讲清楚——这是理解 Rank-1 方法"为什么平行向量也能得到正确结果"的最后一环。