矩阵学习笔记

#矩阵

由 $n \times m$ 个数 $a_{i, j}$ 排成的 $n$ 行 $m$ 列的数表叫做 $n$ 行 $m$ 列的矩阵，简称 $n \times m$ 矩阵。记作：

$$A = \begin{bmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, m} \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n, 1} & a_{n, 2} & \cdots & a_{n, m} \\ \end{bmatrix}$$

这 $n \times m$ 个数称为矩阵 $A$ 的元素，简称为元。数 $a_{i, j}$ 位于矩阵 $A$ 的第 $i$ 行第 $j$ 列，称为矩阵 $A$ 的 $(i, j)$ 元。以数 $a_{i, j}$ 为 $(i, j)$ 元的矩阵也可记作 $[a_{i, j}]$ 或 $[a_{i, j}]_{n \times m}$。

如果矩阵 $A$ 的元素可以写成只与其行数 $i$ 与列数 $j$ 有关的统一函数 $f$，那么也可以使用 $A = [f(i, j)]_{n \times m}$ 作为 $A$ 的简写。

$n \times m$ 矩阵 $A$ 也可记作 $A_{nm}$。

#矩阵的基本运算

矩阵的基本运算包括加法、减法、数乘、转置、共轭等。

#加（减）法

对于两个同型（行数、列数均相同）的矩阵 $A$ 和 $B$，加法就是将对应 $(i, j)$ 元做加法运算。如：

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

减法运算同理。

矩阵的加（减）法运算满足结合律和交换律：

$$\begin{aligned} A + B &= B + A \\ (A + B) + C &= A + (B + C) \end{aligned}$$

#数乘

矩阵的数乘是指一个数乘以一个矩阵，只需要将这个数乘到矩阵的每个元素上即可。如：

$$2 \times \begin{bmatrix} 1 & 1 & 4 \\ 5 & 1 & 4 \\ \end{bmatrix} = \begin{bmatrix} 2 \times 1 & 2 \times 1 & 2 \times 4 \\ 2 \times 5 & 2 \times 1 & 2 \times 4 \\ \end{bmatrix} = \begin{bmatrix} 2 & 2 & 8 \\ 10 & 2 & 8 \\ \end{bmatrix}$$

矩阵的数乘运算满足结合律和分配律：

$$\begin{aligned} (\lambda \mu) A &= \lambda (\mu A) \\ (\lambda + \mu) A &= \lambda A + \mu A \\ \lambda (A + B) &= \lambda A + \lambda B \\ \end{aligned}$$

矩阵的加法、减法和数乘运算合称为矩阵的线性运算。

#转置

将矩阵 $A$ 的行换成同序数的列所得到的新矩阵称为 $A$ 的转置矩阵，这一过程称为矩阵的转置，记为 $A^T$。如：

$$\begin{bmatrix} 1 & 1 & 4 \\ 5 & 1 & 4 \\ \end{bmatrix}^T = \begin{bmatrix} 1 & 5 \\ 1 & 1 \\ 4 & 4 \\ \end{bmatrix}$$

矩阵的转置运算满足以下运算律：

$$\begin{aligned} (A^T)^T &= A \\ (\lambda A)^T &= \lambda A^T \\ (A B)^T &= B^T A^T \\ \end{aligned}$$

#共轭

对于一个复矩阵，其共轭矩阵定义为 $A_{i, j} = \overline{A_{i, j}}$。如：

$$\begin{array}{cc} A = \begin{bmatrix} 3 + i & 5 \\ 2 - 2i & i \\ \end{bmatrix} & \overline{A} = \begin{bmatrix} 3 - i & 5 \\ 2 + 2i & -i \\ \end{bmatrix} \end{array}$$

矩阵的共轭转置定义为 ${A^*}_{i, j} = \overline{A_{j, i}}$（也可记作 $A^* = (\overline{A})^T = \overline{A^T}$）。如：

$$\begin{array}{cc} A = \begin{bmatrix} 3 + i & 5 \\ 2 - 2i & i \\ \end{bmatrix} & A^* = \begin{bmatrix} 3 - i & 2 + 2i \\ 5 & -i \\ \end{bmatrix} \end{array}$$

#矩阵乘法

两个矩阵的乘法运算仅当第一个矩阵 $A$ 的列数和第二个矩阵 $B$ 的行数相等时才能定义。如 $A_{n \times m}, B_{m \times p}$ 的乘积 $C$ 是一个 $n \times p$ 矩阵 $C = [c_{i, j}]$，它的任意一个元素值为：

$$c_{i, j} = a_{i, 1} \times b_{1, j} + a_{i, 2} \times b_{2, j} + \cdots + a_{i, m} \times b_{m, j} = \sum_{k=1}^m (a_{i, k} \times b_{k, j})$$

将此乘积记为 $C = AB$。如：

$$\begin{aligned} & \begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \\ \end{bmatrix} \times \begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \\ \end{bmatrix} \\ = & \begin{bmatrix} (1 × 3 + 0 × 2 + 2 × 1) & (1 × 1 + 0 × 1 + 2 × 0) \\ (-1 × 3 + 3 × 2 + 1 × 1) & (-1 × 1 + 3 × 1 + 1 × 0) \\ \end{bmatrix} \\ = & \begin{bmatrix} 5 & 1 \\ 4 & 2 \\ \end{bmatrix} \end{aligned}$$

矩阵乘法满足结合律、左分配律、右分配律，但不满足交换律：

$$\begin{aligned} (AB)C &= A(BC) \\ (A+B)C &= AC + BC \\ C(A+B) &= CA + CB \\ \end{aligned}$$

#单位矩阵

$n$ 阶单位矩阵 $I_n$ 是一个 $n \times n$ 的方形矩阵，其主对角线上的所有数为 $1$，其余数为 $0$。

$$\begin{array}{ccccc} I_1 = \begin{bmatrix} 1 \\ \end{bmatrix} , & I_2 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} , & I_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} , & \cdots , & I_n = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \\ \end{bmatrix} \end{array}$$

单位矩阵有一个特殊性质：任何矩阵乘上这个矩阵都得它本身，即 $AI = A$。这个性质在进行矩阵快速幂的时候会用到。

#矩阵快速幂

矩阵快速幂和一般的快速幂类似，都是通过运用结合律来减少乘法运算的次数来达到提速的目的的。

$$\large A^k = \begin{cases} \begin{array}{ll} I & \normalsize \text{if } k = 0 \\ A \times A^{k - 1} & \normalsize \text{if } k \bmod 2 = 1 \\ A^{ {2}^{k \div 2} } & \normalsize \text{if } k \bmod 2 = 0 \\ \end{array} \end{cases}$$

#矩阵加速递推

#斐波那契数列

斐波那契数列的递推公式如下：

$$f_{n} = \begin{cases} 1 & \text{if } n \in \{1, 2\} \\ f_{n - 1} + f_{n - 2} & \text{if } n \geq 3 \\ \end{cases}$$

可以看出 $f_n$ 和 $f_{n - 1}$ 是存在一定关系的，可以构造一个多项式来找出关系：

$$\tag{1} \begin{aligned} f_{n} &= f_{n - 1} + f_{n - 2} \\ f_{n - 1} &= f_{n - 1} \\ \end{aligned}$$

设 $x_1 = f_{n - 1}, x_2 = f_{n - 2}, y_1 = f_{n}, y_2 = f_{n - 1}$，则 1 式可化为以下形式：

$$\tag{2} \begin{aligned} y_1 &= x_1 + x_2 \\ y_2 &= x_1 \\ \end{aligned}$$

这种齐次线性方程组可以使用 $\text{系数矩阵} \times \text{N 维向量}$ 的形式来表示，即：

$$AX = B$$

则有：

$$\tag{3} \begin{bmatrix} y1 \\ y2 \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} x1 \\ x2 \\ \end{bmatrix}$$

设 $F(n) = \begin{bmatrix} f_n \\ f_{n - 1} \end{bmatrix}$，由 3 式得：

$$\tag{4} F(n) = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^{n - 1} \begin{bmatrix} f_1 \\ f_0 \\ \end{bmatrix}$$

这样就将本节刚开始的递推式转换成了一个求解矩阵幂运算的通项公式，使用上一节中提到的矩阵快速幂的知识即可将复杂度优化到 $\log$ 级别。

#推广

例题：P1939 【模板】矩阵加速（数列）

由题可得该数列的递推公式：

$$f_{n} = \begin{cases} 1 & \text{if } n \in \{1, 2, 3\} \\ f_{n - 1} + f_{n - 3} & \text{if } n \geq 4 \\ \end{cases}$$

与上题相同，可以构造一组多项式来找出关系：

$$\tag{1} \begin{aligned} f_n &= f_{n - 1} + f_{n - 3} \\ f_{n - 1} &= f_{n - 1} \\ f_{n - 2} &= f_{n - 2} \\ f_{n - 3} &= f_{n - 3} \\ \end{aligned}$$

设 $x_1 = f_{n - 1}, x_2 = f_{n - 2}, x_3 = f_{n - 3}, x_4 = f_{n - 4}, y_1 = f_{n}, y_2 = f_{n - 1}, y3 = f_{n - 2}, y4 = f_{n - 3}$，则 1 式可化为以下形式：

$$\tag{2} \begin{aligned} y_1 &= x_1 + x_3 \\ y_2 &= x_1 \\ y_3 &= x_2 \\ y_4 &= x_3 \\ \end{aligned}$$

用 $\text{系数矩阵} \times \text{N 维向量}$ 的形式来表示，有：

$$\tag{3} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ \end{bmatrix}$$

从 3 式可以看出，$x_4$ 的系数恒为 $0$，可以化简为：

$$\tag{4} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \end{bmatrix}$$

设 $F(n) = \begin{bmatrix}f_n \\ f_{n - 1} \\ f_{n - 2}\end{bmatrix}$，由 4 式得：

$$F(n) = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{bmatrix}^{n - 1} \begin{bmatrix} f_3 \\ f_2 \\ f_1 \\ \end{bmatrix}$$

参照此种方法，就可以使用矩阵加速递推了。

#参考资料

1. 6.1 矩阵及其运算，《信息学奥赛之数学一本通》（ISBN 978-7-5641-6576-5，东南大学出版社），林厚从，2019 年 11 月第 9 次修订版。
2. 矩阵，OI Wiki，2022 年 2 月 13 日。
3. 矩阵快速幂，一瓜算法小册，2020 年 2 月 18 日。