广义矩阵乘法

· · 个人记录

普通矩阵乘法：

C_{i,j} = \sum_{k=1}^{A.m} A_{i,k} \times B_{k,j}

定义两个新运算 \oplus,\otimes，广义矩阵乘法：

C_{i,j} = \bigoplus_{k=1}^{A.m} A_{i,k} \otimes B_{k,j}

想要对广义矩阵乘法做矩阵快速幂，需要满足结合律：

(A \times B) \times C = A \times (B \times C)

证明在 \oplus,\otimes 的意义下矩阵如何满足结合律，以下默认矩阵为方阵。

记 D = A \times B，则 D_{i,j} = \bigoplus_{k=1}^{n} A_{i,k} \otimes B_{k,j}。

记 E = B \times C，则 C_{i,j} = \bigoplus_{k=1}^{n} B_{i,k} \otimes C_{k,j}。

考虑 (A\times B)\times C 与 A\times (B \times C) 的 (i,j) 元。

应有：

\bigoplus_{k=1}^{n} (\bigoplus_{k'=1}^{n} A_{i,k'} \otimes B_{k',k}) \otimes C_{k,j} = \bigoplus_{k=1}^{n} A_{i,k} \otimes (\bigoplus_{k' = 1}^{n} B_{k,k'} \otimes C_{k',j})

如果 \otimes 对 \oplus 有分配律，则有：

\bigoplus_{k=1}^{n} \bigoplus_{k'=1}^{n} A_{i,k'} \otimes B_{k',k} \otimes C_{k,j} = \bigoplus_{k=1}^{n} \bigoplus_{k' = 1}^{n} A_{i,k} \otimes B_{k,k'} \otimes C_{k',j}

如果 \oplus 有交换律，那么左右相等。

所以广义矩阵乘法有交换律得有 \otimes 对 \oplus 有分配律，\oplus 有交换律。

常见广义矩阵乘法 (+,\times),(\max,+),(\min,+),(\min,\max),(\max,\min)。

用处是优化 DP 状态转移方程。