矩阵乘法的基本定理
矩阵乘法结合律
设有矩阵 \(A,B,C\)，分别的大小为 \(n \times m, m \times p, p \times q\) 。求证 \((AB)C=A(BC)\)，进一步为 \((AB)C_{i,j}=A(BC)_{i,j}(AB)C\)
根据矩阵乘法的定义，有
\[AB_{i,j} = \sum\limits_{k=1}^m A_{i,k} \times B_{k,j}
\]
故
\[\begin{eqnarray} (AB)C_{i,j} & = & \sum_{l=1}^p AB_{i,l} \times C_{l,j} \\ & = & \sum_{l=1}^p (\sum_{k=1}^m A_{i,k} \times B_{k,l}) \times C_{l,j} \\ & = & \sum_{l=1}^p \sum_{k=1}^m A_{i,k} \times B_{k,l} \times C_{l,j} \\ & = & \sum_{k=1}^m \sum_{l=1}^p A_{i,k} \times B_{k,l} \times C_{l,j} \\ & = & \sum_{k=1}^m (\sum_{l=1}^p B_{k,l} \times C_{l,j}) \times A_{i,k} \\ & = & \sum_{k=1}^m A_{i,k} \times BC_{k,j} \\ & = & A(BC)_{i,j} \end{eqnarray}
\]
证毕
矩阵快速幂的正确性
设方阵 \(A\)(行数为 \(r\))和自然数 \(n\)，可以将 \(n\) 分解为一个 \(m\) 位的二进制数 \(\overline{b_mb_{m-1}...b_1b_0}\)，则
\[\begin{eqnarray} A^n & = & A^{\sum\limits_{i=0}^m b_i 2^i} \\ & = & \prod_{i=0}^m A^{b_i 2^i} \\ & = & \prod_{b_i = 1} A^{2^i} \end{eqnarray}
\]
从第一步到第二步的变换是不平凡的，它只有基于结合律才成立。因此，我们可以发现通过反复平方法可以以 \(O(r^3 \log n)\) 求出 \(A^n\)。
重定义运算符
矩阵乘法中的运算涉及两种操作，即乘法和加法，我们在对结合律进行证明的过程中可以发现，我们依赖了：两种运算符各自符合交换律、结合律，乘法对加法符合分配率。形式化描述，即有运算 \(\oplus\) 加法与 \(\otimes\) 乘法，只要它们符合以下性质
\[\begin{eqnarray} x \oplus y & = & y \oplus x \\ (x \oplus y) \oplus z & = & x \oplus (y \oplus z) \\ x \otimes y & = & y \otimes x \\ (x \otimes y) \otimes z & = & x \otimes (y \otimes z) \\ x \otimes (y \oplus z) & = & (x \otimes y) \oplus (x \otimes z) \end{eqnarray}
\]
那么将该运算替换掉原本矩阵乘法的加法和乘法，交换律依然成立，快速幂也仍然可以使用。比如说，我们知道带余加法和带余乘法仍然满足该性质，所以我们也可以置 \(\times_p \rightarrow \otimes, +_p \rightarrow \oplus\)
当然，如果还想要让这种重定义的矩阵可逆等，就需要该矩阵的元素所属集合与两种运算构成域(field)，也就是还要有逆元和单位元。
修复 自 矩阵乘法笔记：https://www.luogu.com.cn/blog/EntropyIncreaser/ju-zhen-sheng-fa-bi-ji - Elegia