此随笔是修复版，请尊重原创。
修复版
markdown见下修复 自 矩阵乘法笔记 - Elegia：https://www.luogu.com.cn/blog/EntropyIncreaser/ju-zhen-sheng-fa-bi-ji
矩阵乘法的基本定理
矩阵乘法结合律
设有矩阵 \(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)，也就是还要有逆元和单位元。
矩阵快速幂解决最短路问题
我们尝试置$ + \rightarrow \otimes, \min \rightarrow \oplus$ 后，可以发现这仍然符合矩阵运算所需要的性质，而这时
\[AB_{i,j} = \bigoplus_{k=1}^n A_{i,k} \otimes B_{k,j} = \min_{k=1}^n (A_{i,k} + B_{k,j}) \]（这个minmin的特别用法是我自己编的，嘻嘻）
我们惊奇地发现，这就等同于一次边 \((i,j)\) 的松弛操作！于是我们对图的邻接矩阵 \(Adj\)，计算 \(n-1\) 次幂，就可以得出两两边的最短路了。其中如果 \((u,v)\) 无边，则置 \(Adj_{u,v} \leftarrow +\infty\)。计算 \(Adj^{n-1}\) 的时间复杂度为 \(O(n^3 \log n)\)，虽然逊色于floyd算法的\(O(n^3)\) ，但是这也是一个非常启发式的方法。
修复 自 矩阵乘法笔记 - Elegia：https://www.luogu.com.cn/blog/EntropyIncreaser/ju-zhen-sheng-fa-bi-ji
修复版 markdown
## 矩阵乘法的基本定理
### 矩阵乘法结合律
设有矩阵 $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://en.wikipedia.org/wiki/Field/_(mathematics))，也就是还要有逆元和单位元。
### 矩阵快速幂解决最短路问题
我们尝试置$ + \rightarrow \otimes, \min \rightarrow \oplus$ 后，可以发现这仍然符合矩阵运算所需要的性质，而这时
$$AB_{i,j} = \bigoplus_{k=1}^n A_{i,k} \otimes B_{k,j} = \min_{k=1}^n (A_{i,k} + B_{k,j})$$
（这个minmin的特别用法是我自己编的，嘻嘻）
我们惊奇地发现，这就等同于一次边 $(i,j)$ 的松弛操作！于是我们对图的邻接矩阵 $Adj$，计算 $n-1$ 次幂，就可以得出两两边的最短路了。其中如果 $(u,v)$ 无边，则置 $Adj_{u,v} \leftarrow +\infty$。计算 $Adj^{n-1}$ 的时间复杂度为 $O(n^3 \log n)$，虽然逊色于floyd算法的$O(n^3)$ ，但是这也是一个非常启发式的方法。