矩阵乘法

标签：AB BC 矩阵 bigoplus otimes 乘法

矩阵可以看成一个二维数组，\(A_{i,j}\) 表示第 \(i\) 行第 \(j\) 列的元素。

一般来说，定义广义上的加法 \(\oplus\) 和乘法 \(\otimes\)，那么矩阵乘法定义如下：

设 \(A\) 是 \(P\times M\) 的矩阵，\(B\) 是 \(M\times Q\) 的矩阵，\(C=AB\) 是 \(P\times Q\) 的矩阵，那么有，

\[C_{i,j}=\bigoplus_{k=1}^{M}A_{i,k}\otimes B_{k,j} \]

尝试证明矩阵乘法具有分配律，即

\[(AB)C=A(BC) \]

也即对任意 \(i,j\)，有，

\[((AB)C)_{i,j}=(A(BC))_{i,j} \]

容易得到（方便起见，这里设矩阵均为 \(N\times N\) 的）

\[\begin{aligned} ((AB)C)_{i,j} &=\bigoplus_{s=1}^{N}(AB)_{i,s}\otimes C_{s,j}\\ &=\bigoplus_{s=1}^{N}\left(\bigoplus_{t=1}^{N}A_{i,t}\otimes B_{t,s}\right)\otimes C_{s,j} \end{aligned} \]

\[\begin{aligned} (A(BC))_{i,j} &=\bigoplus_{t=1}^{N}A_{i,t}\otimes (BC)_{t,j}\\ &=\bigoplus_{t=1}^{N}A_{i,t}\otimes \left(\bigoplus_{s=1}^{N}B_{t,s}\otimes C_{s,j}\right)\\ \end{aligned} \]

若 \(\otimes\) 对 \(\oplus\) 有分配律，则有

\[((AB)C)_{i,j}=(A(BC))_{i,j}=\bigoplus_{s=1}^{N}\bigoplus_{t=1}^{N}A_{i,s}\otimes B_{s,t}\otimes C_{t,j} \]

对于一般的 \((+,\times)\) 矩阵乘法，后者对前者有分配律，因此一般定义的矩阵乘法具有分配律。

众所周知矩阵乘法可以优化 DP，例如斐波那契数列的递推；同时单点修改的 DP 可以用线段树维护，称之为 DDP（线段树维护的东西需要有结合律，不然没法设计 tag）。

对于更一般的 DP，可能需要广义的矩乘，例如 \((\max,+)\) 等。

标签：AB,BC,矩阵,bigoplus,otimes,乘法
From： https://www.cnblogs.com/weily09/p/18396039/matrix