（广义）矩阵乘法

若无特殊说明，矩阵默认指方阵，矩阵乘法指广义矩阵乘法。

对于数集上的两个二元运算 \(+\) 和 \(\times\)，及一个 \(n\times m\) 的矩阵和 \(m\times p\) 的矩阵，定义矩阵乘法：

\[ (AB)_{i,j}=\sum_{k=1}^{m}{A_{i,k}\times B_{k,j}} \]

一般情况下，矩阵乘法要求：

• \(a+ b=b+ a\)；
• \(a\times (b\times c)=(a\times b)\times c\)；
• \(a\times (b+ c)=a\times c+ b\times c\)；
• \((b+ c)\times a=b\times a+ c\times a\)；

只有满足这些条件，矩阵乘法才具有结合律，才能使用快速幂和线段树。

结合律证明

对于 \(n\times n\) 的方阵 \(A,B,C\)，求证：

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

证明：

根据 乘法对加法的分配律 乘法的结合律 和 加法的交换律：

\[ \begin{align*} \big((AB)C\big)_{i,j}&=\sum_{k_2=1}^{n}{\Big(\sum_{k_1=1}^{n}A_{i,k_1}B_{k_1,k_2}\Big)}C_{k_2,j}\\ &=\sum_{k_2=1}^{n}{\Big(\sum_{k_1=1}^{n}A_{i,k_1}B_{k_1,k_2}C_{k_2,j}\Big)}\\ &=\sum_{k_1=1}^{n}{\Big(\sum_{k_2=1}^{n}A_{i,k_1}B_{k_1,k_2}C_{k_2,j}\Big)}\\ &=\sum_{k_1=1}^{n}{A_{i,k_1}\Big(\sum_{k_2=1}^{n}B_{k_1,k_2}C_{k_2,j}\Big)}\\ &=\big(A(BC)\big)_{i,j} \end{align*} \]