广义矩阵乘法

普通矩阵乘法：

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

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

证明在 $\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)$ 元。

应有：

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

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

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

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

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