矩阵基础知识

一、矩阵是什么

矩阵可以简单理解成一个“按行和列排列的数字表”。

例如：

$$A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix}$$

这个矩阵有 $2$ 行、$3$ 列，所以它是一个 $2\times 3$ 的矩阵。

矩阵中的每一个数叫作矩阵的元素。通常用 $A_{ij}$ 表示矩阵 $A$ 中第 $i$ 行第 $j$ 列的元素。

比如：

$$A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix}$$

那么：

$$A_{11}=1,\quad A_{12}=2,\quad A_{23}=6$$

矩阵的大小通常写成：

$$行数\times 列数$$

例如：

$$\begin{bmatrix} 1&2\\ 3&4\\ 5&6 \end{bmatrix}$$

有 $3$ 行、$2$ 列，所以它是一个 $3\times 2$ 的矩阵。

在算法中，矩阵常常用二维数组存储：

int a[105][105];

如果矩阵有 $n$ 行、$m$ 列，就可以用：

for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
        cin >> a[i][j];
    }
}

来读入整个矩阵。

二、几种常见矩阵

最常见的是普通矩阵，也就是任意行列大小的数字表。

例如：

$$\begin{bmatrix} 2&5&7\\ 1&0&3 \end{bmatrix}$$

如果一个矩阵的行数和列数相同，就叫作方阵。

例如：

$$\begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}$$

这是一个 $2\times 2$ 方阵。

再比如：

$$\begin{bmatrix} 1&2&3\\ 4&5&6\\ 7&8&9 \end{bmatrix} $$

这是一个 $3\times 3$ 方阵。

方阵在算法中非常重要，因为只有方阵才能自然地做幂运算，例如矩阵快速幂中的：

$$M^k$$

还有一种很重要的矩阵叫单位矩阵。单位矩阵是一个方阵，它的主对角线都是 $1$，其他位置都是 $0$。

例如 $2\times 2$ 单位矩阵是：

$$I= \begin{bmatrix} 1&0\\ 0&1 \end{bmatrix}$$

$3\times 3$ 单位矩阵是：

$$I= \begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{bmatrix} $$

单位矩阵在矩阵中的作用类似于普通乘法里的 $1$。

对于合适大小的矩阵 $A$，有：

$$AI=A$$ $$IA=A$$

还有一种矩阵叫零矩阵，也就是所有元素都是 $0$ 的矩阵。例如：

$$\begin{bmatrix} 0&0&0\\ 0&0&0 \end{bmatrix}$$

它在矩阵加法中类似于普通加法里的 $0$。

三、矩阵加法、数乘和转置

矩阵加法比较容易理解：两个大小完全相同的矩阵，可以对应位置相加。

例如：

$$A= \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}$$ $$B= \begin{bmatrix} 5&6\\ 7&8 \end{bmatrix}$$

那么：

$$A+B= \begin{bmatrix} 1+5&2+6\\ 3+7&4+8 \end{bmatrix} = \begin{bmatrix} 6&8\\ 10&12 \end{bmatrix} $$

注意，矩阵加法要求两个矩阵的大小一样。一个 $2\times 3$ 的矩阵和一个 $3\times 2$ 的矩阵不能相加。

矩阵数乘就是用一个数去乘矩阵中的每个元素。

例如：

$$3 \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix} = \begin{bmatrix} 3&6\\ 9&12 \end{bmatrix} $$

矩阵转置是把矩阵的行和列互换。

例如：

$$A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix}$$

它的转置是：

$$A^T= \begin{bmatrix} 1&4\\ 2&5\\ 3&6 \end{bmatrix} $$

原来的第 $1$ 行：

$$1,2,3$$

变成了转置后的第 $1$ 列。

原来的第 $2$ 行：

$$4,5,6$$

变成了转置后的第 $2$ 列。

转置在算法题中不一定经常直接出现，但它能帮助我们理解矩阵的“行列关系”。尤其是学习矩阵乘法时，转置能让人更清楚地意识到：矩阵乘法本质上是“行”和“列”的配合。

四、矩阵乘法的定义

矩阵乘法是矩阵基础中最重要的一部分，也是最容易一开始看不懂的部分。

矩阵乘法不是对应位置相乘。

例如：

$$\begin{bmatrix} 1&2\\ 3&4 \end{bmatrix} \begin{bmatrix} 5&6\\ 7&8 \end{bmatrix} $$

不是得到：

$$\begin{bmatrix} 1\times 5&2\times 6\\ 3\times 7&4\times 8 \end{bmatrix} $$

真正的矩阵乘法规则是：

答案矩阵中的第 $i$ 行第 $j$ 列，等于左边矩阵第 $i$ 行和右边矩阵第 $j$ 列对应相乘后再相加。

设：

$$C=A\times B$$

那么：

$$C_{ij}=\sum_k A_{ik}B_{kj}$$

看一个具体例子。

设：

$$A= \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}$$ $$B= \begin{bmatrix} 5&6\\ 7&8 \end{bmatrix}$$

要求：

$$C=A\times B$$

先算 $C_{11}$。

取左边矩阵第 $1$ 行：

$$[1,2]$$

取右边矩阵第 $1$ 列：

$$\begin{bmatrix} 5\\ 7 \end{bmatrix}$$

对应相乘再相加：

$$1\times 5+2\times 7=19$$

所以：

$$C_{11}=19$$

再算 $C_{12}$。

取左边矩阵第 $1$ 行：

$$[1,2]$$

取右边矩阵第 $2$ 列：

$$\begin{bmatrix} 6\\ 8 \end{bmatrix}$$

所以：

$$C_{12}=1\times 6+2\times 8=22$$

继续算：

$$C_{21}=3\times 5+4\times 7=43$$ $$C_{22}=3\times 6+4\times 8=50$$

因此：

$$\begin{bmatrix} 1&2\\ 3&4 \end{bmatrix} \begin{bmatrix} 5&6\\ 7&8 \end{bmatrix} = \begin{bmatrix} 19&22\\ 43&50 \end{bmatrix} $$

矩阵乘法有一个很重要的限制：

如果 $A$ 是 $n\times m$ 的矩阵，$B$ 是 $p\times q$ 的矩阵，那么只有当：

$$m=p$$

时，$A\times B$ 才能计算。

也就是说，左边矩阵的列数必须等于右边矩阵的行数。

最后结果矩阵的大小是：

$$n\times q$$

例如：

$$(2\times 3)\times(3\times 4)=(2\times 4)$$

但是：

$$(2\times 3)\times(2\times 4)$$

不能相乘，因为左边列数是 $3$，右边行数是 $2$，二者不相等。

矩阵乘法代码通常是三重循环：

for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= q; j++) {
        c[i][j] = 0;

        for(int k = 1; k <= m; k++) {
            c[i][j] += a[i][k] * b[k][j];
        }
    }
}

这里的含义是：

• $i$ 枚举答案矩阵的行；
• $j$ 枚举答案矩阵的列；
• $k$ 枚举“左边矩阵的列”和“右边矩阵的行”。

五、矩阵乘法的性质

矩阵乘法和普通数字乘法很像，但也有一些非常重要的区别。

首先，矩阵乘法满足结合律：

$$(AB)C=A(BC)$$

只要矩阵大小合法，这个性质就成立。

这也是矩阵快速幂能够成立的关键原因。

因为快速幂需要不断改变乘法顺序，例如：

$$M^8=(M^4)^2$$

如果没有结合律，这种写法就不一定成立。

其次，矩阵乘法满足分配律：

$$A(B+C)=AB+AC$$ $$(A+B)C=AC+BC$$

这和普通数字乘法比较像。

但是，矩阵乘法一般不满足交换律。

也就是说，通常情况下：

$$AB\ne BA$$

甚至有时候 $AB$ 能算，但 $BA$ 根本不能算。

例如 $A$ 是 $2\times 3$ 矩阵，$B$ 是 $3\times 4$ 矩阵，那么：

$$AB$$

可以计算，结果是 $2\times 4$。

但是：

$$BA$$

需要计算：

$$(3\times 4)\times(2\times 3)$$

因为 $4\ne 2$，所以不能计算。

即使 $AB$ 和 $BA$ 都能计算，结果也不一定相同。

例如：

$$A= \begin{bmatrix} 1&1\\ 0&1 \end{bmatrix}$$ $$B= \begin{bmatrix} 1&0\\ 1&1 \end{bmatrix}$$

则：

$$AB= \begin{bmatrix} 2&1\\ 1&1 \end{bmatrix}$$

而：

$$BA= \begin{bmatrix} 1&1\\ 1&2 \end{bmatrix}$$

它们并不相同。

所以写矩阵时一定要注意顺序。尤其是在矩阵快速幂、线性递推、图转移这些问题中，如果把乘法方向写反，结果通常会错。

六、矩阵和线性递推的关系

矩阵在算法中最常见的作用，就是表示“状态转移”。

例如斐波那契数列：

$$F_n=F_{n-1}+F_{n-2}$$

我们可以把状态写成：

$$\begin{bmatrix} F_n\\ F_{n-1} \end{bmatrix}$$

如果已知：

$$\begin{bmatrix} F_{n-1}\\ F_{n-2} \end{bmatrix}$$

怎样得到：

$$\begin{bmatrix} F_n\\ F_{n-1} \end{bmatrix}$$

呢？

第一行要算出新的 $F_n$。

由于：

$$F_n=F_{n-1}+F_{n-2}$$

所以第一行应该是：

$$[1,1]$$

表示：

$$1\cdot F_{n-1}+1\cdot F_{n-2}$$

第二行要保留 $F_{n-1}$。

也就是：

$$F_{n-1}=1\cdot F_{n-1}+0\cdot F_{n-2}$$

所以第二行是：

$$[1,0]$$

于是有：

$$\begin{bmatrix} F_n\\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix} \begin{bmatrix} F_{n-1}\\ F_{n-2} \end{bmatrix} $$

这个矩阵的意义就是：完成一次斐波那契递推。

如果初始状态是：

$$\begin{bmatrix} F_2\\ F_1 \end{bmatrix}$$

乘一次转移矩阵，得到：

$$\begin{bmatrix} F_3\\ F_2 \end{bmatrix}$$

乘两次，得到：

$$\begin{bmatrix} F_4\\ F_3 \end{bmatrix}$$

乘三次，得到：

$$\begin{bmatrix} F_5\\ F_4 \end{bmatrix}$$

所以矩阵可以理解为“把一个状态变成下一个状态的工具”。

更一般地，如果递推需要前 $k$ 项，比如：

$$f_n=c_1f_{n-1}+c_2f_{n-2}+\cdots+c_kf_{n-k}$$

那么可以把状态设计成：

$$\begin{bmatrix} f_n\\ f_{n-1}\\ f_{n-2}\\ \vdots\\ f_{n-k+1} \end{bmatrix} $$

转移矩阵的第一行负责计算新的 $f_n$，下面几行负责把状态往后平移。

例如：

$$f_n=f_{n-1}+2f_{n-2}+3f_{n-3}$$

可以写成：

$$\begin{bmatrix} f_n\\ f_{n-1}\\ f_{n-2} \end{bmatrix} = \begin{bmatrix} 1&2&3\\ 1&0&0\\ 0&1&0 \end{bmatrix} \begin{bmatrix} f_{n-1}\\ f_{n-2}\\ f_{n-3} \end{bmatrix} $$

这个结构非常常见：第一行写递推公式，下面几行负责移动状态。

七、矩阵在算法中的常见用途

矩阵最直接的用途是表示二维数据。

比如网格图、地图、棋盘、图像灰度表，本质上都可以看成矩阵。

在这类问题中，矩阵通常只是一个数据容器。我们关心的是如何枚举行列、如何处理相邻格子、如何做前缀和或动态规划。

例如二维前缀和中，原数组可以看成一个矩阵：

$$a_{ij}$$

前缀和数组也是一个矩阵：

$$s_{ij}$$

它表示左上角到当前位置的矩形区域和。

矩阵的第二种用途是表示线性变换。

例如把一个状态向量：

$$\begin{bmatrix} x\\ y \end{bmatrix}$$

变成另一个状态向量：

$$\begin{bmatrix} x'\\ y' \end{bmatrix}$$

如果这个变化是线性的，就可以写成矩阵乘法。

例如：

$$x'=x+y$$ $$y'=x$$

就可以写成：

$$\begin{bmatrix} x'\\ y' \end{bmatrix} = \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix} \begin{bmatrix} x\\ y \end{bmatrix} $$

矩阵的第三种用途是加速固定转移。

如果某个状态每一步都按照同样规则转移，那么一次转移可以写成矩阵，多次转移就可以写成矩阵的幂。

这就是矩阵快速幂的核心来源。

例如一次转移是：

$$S_i=MS_{i-1}$$

那么连续转移 $k$ 次就是：

$$S_{i+k}=M^kS_i$$

如果 $k$ 非常大，就可以用矩阵快速幂快速求出 $M^k$。

矩阵的第四种用途是表示图上的路径计数。

如果有一个图，它的邻接矩阵是 $G$，其中：

$$G_{ij}=1$$

表示从点 $i$ 到点 $j$ 有一条边。

那么 $G^2_{ij}$ 表示从点 $i$ 到点 $j$ 走 $2$ 条边的路径数，$G^k_{ij}$ 表示从点 $i$ 到点 $j$ 走 $k$ 条边的路径数。

这是矩阵乘法在图论中的一个经典意义。

八、学习矩阵时最容易犯的错误

第一个常见错误，是把矩阵乘法当成对应位置相乘。

矩阵加法是对应位置相加，但矩阵乘法不是对应位置相乘。矩阵乘法一定要记住“左边一行，右边一列”。

第二个常见错误，是忘记矩阵乘法的大小限制。

如果 $A$ 是 $n\times m$，$B$ 是 $p\times q$，那么 $AB$ 能计算的条件是：

$$m=p$$

结果大小是：

$$n\times q$$

第三个常见错误，是以为矩阵乘法可以交换顺序。

普通数字中：

$$ab=ba$$

但矩阵中通常：

$$AB\ne BA$$

所以推公式和写代码时，一定要固定好状态是列向量还是行向量。

如果写成列向量，通常是：

$$S_i=MS_{i-1}$$

如果写成行向量，通常是：

$$S_i=S_{i-1}M$$

两种写法都可以，但不能混用。

第四个常见错误，是构造递推矩阵时不知道下面几行怎么写。

可以记住一个方法：第一行负责算新值，下面几行负责平移旧状态。

例如状态是：

$$\begin{bmatrix} f_{n-1}\\ f_{n-2}\\ f_{n-3} \end{bmatrix} $$

新状态是：

$$\begin{bmatrix} f_n\\ f_{n-1}\\ f_{n-2} \end{bmatrix} $$

那么下面几行就是把原来的第一项移到第二项，把原来的第二项移到第三项。

所以通常会出现这种结构：

$$\begin{bmatrix} \cdots&\cdots&\cdots\\ 1&0&0\\ 0&1&0 \end{bmatrix} $$

学矩阵时，不需要一开始就追求抽象理解。先记住三个核心点就够了：

矩阵是按行列排列的数字表。

矩阵乘法是“左边一行乘右边一列”。

矩阵可以表示一次状态转移。