一个 $n\times m$ 的矩阵对应到 C++ 中可以看作一个 n 行 m 列的二维数组。

矩阵运算

矩阵加法和减法

矩阵的加法和减法就是把两个矩阵对应位置的元素相加或相减。举例来说：

$$A=\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right]$$$$B=\left[\begin{array}{cc}5& 6\\ 7& 8\end{array}\right]$$

则有：

$$A+B=\left[\begin{array}{cc}6& 8\\ 10& 12\end{array}\right]$$$$A-B=\left[\begin{array}{cc}-4& -4\\ -4& -4\end{array}\right]$$

矩阵乘法

矩阵乘法稍微复杂一些。设 $A$ 为 $n$ 行 $p$ 列的矩阵，$B$ 为 $p$ 行 $m$ 列的矩阵，则 $AB$ 是一个 $n$ 行 $m$ 列的矩阵，且满足：

$$(AB{)}_{i,j}=\sum _{k=1}^p{A}_{i,k}{B}_{k,j}$$

也就是说，参与矩阵乘法运算的第一个矩阵的列数必须等于第二个矩阵的行数，而结果矩阵的行数和列数分别等于第一个矩阵的行数和第二个矩阵的列数，结果矩阵的第 $(i,j)$ 个元素等于第一个矩阵的第 $i$ 行与第二个矩阵的第 $j$ 列的元素的乘积之和。举例来说：

$$A=\left[\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\end{array}\right]$$$$B=\left[\begin{array}{cc}7& 8\\ 9& 10\end{array}\right]$$

则有：

$$AB=\left[\begin{array}{cc}25& 28\\ 57& 64\\ 89& 100\end{array}\right]$$

矩阵乘法的过程可以用 C++ 代码表示：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        C[i][j] = 0;
        for (int k = 0; k < p; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

矩阵乘法的性质：

1. 结合律：$(AB)C=A(BC)$
2. 分配律：$A(B+C)=AB+AC$

注意：矩阵乘法不满足交换律，即 $AB$ 不一定等于 $BA$。

矩阵乘法与递推

考虑特殊的矩阵乘法形式：

$A$ 为 $1\times n$ 矩阵，$B$ 为 $n\times n$ 矩阵，则 $C=AB$ 也是一个 $1\times n$ 矩阵，而 $A$ 和 $C$ 都可以看作一个一位数组，按照矩阵乘法的定义可知，经过一次与 $B$ 的矩阵乘法，$A$ 数组中的第 $k$ 个元素会以 $B_{k,j}$ 为系数累加到 $C$ 数组的第 $j$ 个元素上。等价于在一个向量的 $k,j$ 两个状态之间发生了递推。

举例来说，我们都知道斐波那契数列中 $F_n=F_{n-1}+F_{n-2}(n\ge 2)$，且 $F_0=0,F_1=1$。那么，我们可以用矩阵乘法来表示斐波那契数列：

$$\left[\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_{n-1}\\ F_{n-2}\end{array}\right]$$

一般来说，如果一类问题可以使用矩阵乘法进行优化，那么它应该具有以下特点：

1. 可以抽象出一个长度为 $n$ 的一维向量，该向量在每个时间单位发生一次变化。
2. 变化的形式是一个线性递推。
3. 递推式在每个时间可能作用于不同的数据上，但本身保持不变。
4. 向量变化时间很长，但向量长度不大。