一、什么是矩阵
\(m\) 行 \(n\) 列的数表记作矩阵 \(A_{mn}\)，在 \((i,j)\) 的数记作 \(a_{i,j}\)。
注意：矩阵的行列不能颠倒。
二、矩阵转置
\(A\) 的转置记作 \(A^T\)，操作为 \(a_{i,j}\to a_{j,i}\)。
三、矩阵乘法
-
矩阵数乘：每个元分别乘上该数字。
-
矩阵点乘向量：\(n\times m\) 矩阵与 \(n\) 维向量 \(w\) 点乘，矩阵第 \(i\) 行每个元分别乘以 \(w_i\)。
-
矩阵乘向量：矩阵列数等于向量维数，必须矩阵在前向量在后，如图。
-
矩阵乘矩阵：\(m\times n\) 与 \(n\times p\) 矩阵才能相乘；方法为把后一个矩阵拆分乘若干个列向量，分别与前矩阵相乘，如图。
矩阵乘法有结合律，没有交换律。因为矩阵是对线性变换的描述，例如 \((AB)C\cdot x\) 表示先对向量 \(x\) 做 \(C\) 变换，再做 \(AB\) 组合变换（相当于先 \(B\) 后 \(A\)——没有交换律）；而 \(A(BC)\cdot x\) 的变换顺序也是 \(C\to B\to A\) ——有结合律。
通过矩阵的乘法结合律，我们可以由小到大的计算，降低复杂度。
四、矩阵快速幂
实现类比一般的倍增快速幂。有些动态规划的式子（如斐波那契数列）能写成矩阵乘法的形式，用快速幂计算能大大降低复杂度。