1 Rank of tropical semiring

关键点：乘法不会增加秩；存在一个分解只给出上界，而秩是最小分解维数，所以上界成立。

---

这个推导只用了两件事：矩阵乘法的结合律，以及秩的定义是“最小分解中间维数”。逐句拆开看：

1. 先回顾论文里秩的定义

在热带半环中，矩阵 $M$ 的秩定义为最小的 $r$，使得存在矩阵 $C,R$ 满足

$$M=C\odot R,$$

其中 $C$ 有 $r$ 列，$R$ 有 $r$ 行。也就是说，$M$ 可以“穿过”一个 $r$ 维的中间空间分解掉。

所以：

$$\operatorname{rank}(M)\le r$$

的意思是：只要你能找到一种中间维数为 $r$ 的分解，秩就不会超过 $r$。因为秩是所有可行分解中间维数的最小值。

---

2. 证明 $\operatorname{rank}(A\odot B)\le \operatorname{rank}(A)$

设

$$\operatorname{rank}(A)=r.$$

由秩的定义，存在分解

$$A=C\odot R,$$

其中 $C$ 有 $r$ 列，$R$ 有 $r$ 行。维度上就是：

$$A_{m\times n}=C_{m\times r}\odot R_{r\times n}.$$

现在计算 $A\odot B$。利用矩阵乘法结合律：

$$A\odot B =(C\odot R)\odot B =C\odot (R\odot B).$$

注意 $R\odot B$ 的维度是 $r\times p$，所以

$$A\odot B=C\odot (R\odot B)$$

就是一个中间维数为 $r$ 的分解：左因子 $C$ 有 $r$ 列，右因子 $R\odot B$ 有 $r$ 行。

既然存在一个中间维数为 $r$ 的分解，而秩是最小可能的中间维数，因此

$$\operatorname{rank}(A\odot B)\le r =\operatorname{rank}(A).$$

这就是第一个不等式。

---

3. 证明 $\operatorname{rank}(A\odot B)\le \operatorname{rank}(B)$

设

$$\operatorname{rank}(B)=s.$$

由定义，存在分解

$$B=C'\odot R',$$

其中 $C'$ 有 $s$ 列，$R'$ 有 $s$ 行。维度上：

$$B_{n\times p}=C'_{n\times s}\odot R'_{s\times p}.$$

于是

$$A\odot B =A\odot(C'\odot R') =(A\odot C')\odot R'.$$

这里 $A\odot C'$ 是 $m\times s$ 矩阵，$R'$ 是 $s\times p$ 矩阵，所以这又是一个中间维数为 $s$ 的分解。

因此

$$\operatorname{rank}(A\odot B)\le s =\operatorname{rank}(B).$$

---

4. 合并两个上界

我们已经得到：

$$\operatorname{rank}(A\odot B)\le \operatorname{rank}(A),$$

并且

$$\operatorname{rank}(A\odot B)\le \operatorname{rank}(B).$$

一个数同时小于等于 $a$ 和 $b$，就一定小于等于它们中较小的那个：

$$\operatorname{rank}(A\odot B)\le \min(\operatorname{rank}(A),\operatorname{rank}(B)).$$

这就是公式 (3)。

---

直观理解

矩阵乘法 $A\odot B$ 可以看成：先用 $B$ 映射，再用 $A$ 映射。

• 如果 $A$ 的秩只有 $r$，那么无论输入是什么，经过 $A$ 后最多只能落在 $r$ 维的“方向集合”里，所以 $A\odot B$ 的秩不可能超过 $A$。
• 同理，如果 $B$ 的秩只有 $s$，那么 $B$ 的输出本身最多只有 $s$ 维独立方向，再乘 $A$ 也不会凭空增加独立方向，所以 $A\odot B$ 的秩不可能超过 $B$。

关键点：乘法不会增加秩；存在一个分解只给出上界，而秩是最小分解维数，所以上界成立。