线性代数——矩阵引入矩阵
一般用圆括号或方括号表示矩阵，形如：
\(A = \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn}\end{pmatrix}\)
矩阵表示线性方程组
例如，将线性方程组：
\(\left\{\begin{matrix} 7x_1+8x_2+9x_3=13 \\ 4x_1+5x_2+6x_3=12 \\ x_1+2x_2+3x_3=11\end{matrix}\right.\)
写成矩阵乘法的形式（将系数抽出来）：
\(\begin{pmatrix} 7 & 8 & 9 \\ 4 & 5 & 6 \\ 1 & 2 & 3\end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3\end{pmatrix}=\begin{pmatrix} 13 \\ 12 \\ 11\end{pmatrix}\)
简记为：\(Ax = b\)，其中系数矩阵 \(A = \begin{pmatrix} 7 & 8 & 9 \\ 4 & 5 & 6 \\ 1 & 2 & 3\end{pmatrix}\)；未知量 \(x = \begin{pmatrix} x_1 \\ x_2 \\ x_3\end{pmatrix}\)；常数项 \(b = \begin{pmatrix} 13 \\ 12 \\ 11\end{pmatrix}\)；
即未知数列向量 \(x\)，左乘一个矩阵 \(A\)，得到列向量 \(b\)。
运算矩阵的线性运算
矩阵的线性运算分为加减法与数乘，它们均为逐个元素进行。只有同型矩阵之间可以对应相加减。
例如：\(3 \times \begin{pmatrix} 1 & 2 \\ 3 & 4\end{pmatrix} = \begin{pmatrix} 3 \times 1 & 3 \times 2 \\ 3 \times 3 & 3 \times 4\end{pmatrix} = \begin{pmatrix} 3 & 6 \\ 9 & 12\end{pmatrix}\)
矩阵的转置
矩阵的转置，就是在矩阵的右上角写上转置「\(\text{T}\)」记号，表示将矩阵的行与列互换。
例如：\(\begin{pmatrix} 1 & 2 & 3 \\ 3 & 4 & 5\end{pmatrix}^\text{T}=\begin{pmatrix} 1 & 3 \\ 2 & 4 \\ 3 & 5\end{pmatrix}\)
向量内积
对应相乘再相加。
例如：\(\begin{pmatrix} 1 & 2 & 3\end{pmatrix} \times \begin{pmatrix} 4 & 5 & 6\end{pmatrix} = 1 \times 4 + 2 \times 5 + 3 \times 6 = 52\).
矩阵乘法
算法
设 \(A\) 为 \(n \times m\) 的矩阵，\(B\) 为 \(m \times r\) 的矩阵，即前一矩阵列数等于后一矩阵行数；
设矩阵 \(C = A \times B\)，则 \(\displaystyle C_{i, j} = \sum_{k = 1}^m A_{i, k} B_{k, j}\)。乘积矩阵中第 \(i\) 行第 \(j\) 列的数恰好是乘数矩阵 \(A\) 第 \(i\) 个行向量与乘数矩阵 \(B\) 第 \(j\) 个列向量的内积，口诀为左行右列。
性质
矩阵乘法满足结合律，不满足一般的交换律；利用结合律，矩阵乘法可以利用快速幂的思想来优化。由于线性递推式可以表示成矩阵乘法的形式，也通常用矩阵快速幂来求线性递推数列的某一项。
演示网站：https://rainppr.gitee.io/matrixmultiplication.xyz/.
矩阵乘法的特殊化——矩阵乘向量
将向量调转，先相乘再相加。
例如：\(\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6\end{pmatrix}\begin{pmatrix} 3 \\ 6 \\ 9\end{pmatrix}=\begin{pmatrix} 1 \times 3 + 2 \times 6 + 3 \times 9 \\ 4 \times 3 + 5 \times 6 + 6 \times 9\end{pmatrix}=\begin{pmatrix} 42 \\ 96\end{pmatrix}\)
矩阵乘法的特殊化——单位矩阵 I
单位矩阵 \(I\)：一个方阵（行数 \(=\) 列数），只有主对角线（左上、右左下）元素为 \(1\)，其他都为 \(0\)。
单位矩阵乘任何矩阵都得该矩阵（就像 \(1\) 一样），即 \(IA = AI = A\)。
举例：\(\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 7 \\ 7 & 8 & 9 & 0\end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 7 \\ 7 & 8 & 9 & 0\end{pmatrix}\)
矩阵乘法优化线性递推讲解与例题分析斐波那契数列
在斐波那契数列当中，\(f_1 = f_2 = 1\)，\(f_i = f_{i – 1} + f_{i – 2}\)，求 \(f_n\)。
而分析式子可以知道，求 \(f_k\) 仅与 \(f_{k – 1}\) 和 \(f_{k – 2}\) 有关；
所以我们设矩阵 \(F_i = \begin{bmatrix} f_{i – 1} & f_{i – 2} \end{bmatrix}\)。
设矩阵 \(\text{Base}\)，使得 \(F_{i – 1} \times \text{Base} = F_i\)，接下来考虑 \(\text{Base}\) 是什么；
带入可得 \(\begin{bmatrix} f_{i – 2} & f_{i – 3} \end{bmatrix} \times \text{Base} = \begin{bmatrix} f_{i – 1} & f_{i – 2} \end{bmatrix}\)。
即 \(\begin{bmatrix} f_{i – 2} & f_{i – 3} \end{bmatrix} \times \text{Base} = \begin{bmatrix} f_{i – 2} + f_{i – 3} & f_{i – 2} \end{bmatrix}\)；
根据矩阵乘法的规则可知 \(\text{Base}\) 的第 \(1\) 列应为 \(\begin{bmatrix} 1 & 1 \end{bmatrix}^\text{T}\)，第 \(2\) 列应为 \(\begin{bmatrix} 1 & 0 \end{bmatrix}^\text{T}\)。
所以求得 \(\text{Base} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\)。
然后考虑 \(f_i\) 的值应该是多少；
根据前面的公式可以知道 \(f_i = F_{n + 1}\) 的第一个数，所以就是求这个数。
根据 \(f_1 = f_2 = 1\)，可以知道 \(F_3 = \begin{bmatrix} f_2 & f_1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \end{bmatrix}\)，我们将这个作为边界值；
然后有 \(F_4 = F_3 \times \text{Base}\)，\(F_5 = F_4 \times \text{Base} = F_3 \times \text{Base} \times \text{Base}\)。
因为矩阵乘法有结合律，所以 \(F_{n + 1} = F_3 \times \text{Base}^{n – 2} = \begin{bmatrix} 1 & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n – 2}\)。
因为矩阵没有交换律，所以 \(F_3\)（前）和 \(\text{Base}^{n – 2}\)（后）一定不能写反了！
例题１
\(\left\{\begin{array}{l}f_1 = f_2 = 0 \\f_i = f_{i – 1} + f_{i – 2} + 1\end{array}\right.\)
点击查看题解
\(f_i\) 仅与 \(f_{i – 1}\) 和 \(f_{i – 2}\) 有关，同时还包括了常数 \(1\)，
所以我们设 \(F_i = \begin{bmatrix} f_{i – 1} & f_{i – 2} & 1 \end{bmatrix}\)，
然后设 \(\text{Base}\) 使得 \(F_{i – 1} \times \text{Base} = F_i\)，
即 \(\begin{bmatrix} f_{i – 2} & f_{i – 3} & 1 \end{bmatrix} \times \text{Base} = \begin{bmatrix} f_{i – 1} & f_{i – 2} & 1 \end{bmatrix}\)。
因为 \(f_{i – 1} = f_{i – 2} + f_{i – 3} + 1\)，所以易知：
\(\text{Base} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix}\).
边界条件为 \(F_3 = \begin{bmatrix} 0 & 0 & 1\end{bmatrix}\)，
所以 \(F_{n + 1} = F_3 \times \text{Base}^{n – 2}\)。
即可求出 \(f_n\).
例题２
\(\left\{\begin{array}{l}f_1 = 0 \text{，} f_2 = 1 \\f_i = f_{i – 1} + f_{i – 2} + i\end{array}\right.\)
点击查看题解
\(f_i\) 仅与 \(f_{i – 1}\)、\(f_{i – 2}\) 和 \(i\) 有关，为实现 \(i\) 的递增，还需设置常量 \(1\)；
所以我们设 \(F_i = \begin{bmatrix} f_{i – 1} & f_{i – 2} & i & 1 \end{bmatrix}\)，
由 \(F_{i – 1} \times \text{Base} = F_i\) 得 \(\text{Base} = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix}\).
边界条件为 \(F_3 = \begin{bmatrix} 1 & 0 & 3 & 1 \end{bmatrix}\).
\(F_{n + 1} = F_3 \times \text{Base}^{n – 2}\)；即可求出 \(f_n\)。
例题３（来自 OI-Wiki）
\(\left\{\begin{array}{l}f_{1} = f_{2} = 0 \\f_{n} = 7f_{n-1}+6f_{n-2}+5n+4\times 3^n\end{array}\right.\)
点击查看题解
我的解法与 OI-Wiki 上的有所不同：
设 \(F_n = \begin{bmatrix} f_{n – 1} & f_{n – 2} & n & 3^n & 1 \end{bmatrix}\).
易知 \(\text{Base} = \begin{bmatrix} 7 & 1 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 & 0 \\ 5 & 0 & 1 & 0 & 0 \\ 4 & 0 & 0 & 3 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}\).
边界值 \(F_3 = \begin{bmatrix} 0 & 0 & 3 & 27 & 1 \end{bmatrix}\).
则 \(F_{n + 1} = F_3 \times \text{Base}^{n – 2}\).
例题４
\(\left\{\begin{array}{l}f_1 = f_2 = 0 \text{，} f_3 = 1 \\f_i = 3f_{i – 1} + 2f_{i – 2} + f_{i – 3} + 5i + 7\end{array}\right.\)
点击查看题解
增加了 \(f_{i – 3}\)，但是本质是一样的。
可以设 \(F_i = \begin{bmatrix} f_{i – 1} & f_{i – 2} & f_{i – 3} & i & 1 \end{bmatrix}\)，
易得 \(\text{Base} = \begin{bmatrix} 3 & 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 1 & 0 \\ 7 & 0 & 0 & 1 & 1 \end{bmatrix}\).
而 \(F_4 = \begin{bmatrix} 1 & 0 & 0 & 4 & 1 \end{bmatrix}\)，
则 \(F_{n + 1} = F_4 \times \text{Base}^{n – 3}\)。
例题５
洛谷 P1939 矩阵加速（数列）：https://www.luogu.com.cn/problem/P1939
考虑这道题 \(\text{Base}\) 该如何设置。
点击查看代码
#include #define rr read()using namespace std;const long long MOD = 1e9 + 7;inline int read(){ int num = 0, flag = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') flag = -1; for (; isdigit(ch); ch = getchar()) num = (num << 3) + (num << 1) + ch - '0'; return num * flag;}struct matrix{ long long a[4][4]; matrix operator*(const matrix &t) const { matrix res; memset(res.a, 0, sizeof res.a); for (int i = 1; i <= 3; ++i) for (int j = 1; j <= 3; ++j) for (int k = 1; k <= 3; ++k) res.a[i][j] = (res.a[i][j] + a[i][k] * t.a[k][j] % MOD) % MOD; return res; }};int main(){ int T = rr; while (T--) { int n = rr; if (n >= 1, Base = Base * Base; } printf("%lld\n", (res.a[1][1] + res.a[2][1] + res.a[3][1]) % MOD); } return 0;}时间复杂度
矩阵乘法 \(O(k^3)\) 其中 \(k\) 为矩阵的长（或宽）；
快速幂 \(O(\log n)\)；
所以［矩阵乘法优化线性递推］的时间复杂度为 \(O(k^3 \log n)\)。
代码实现
const int N = 110;// 矩阵的最大大小const int MOD = 1e9 + 7;// 取模struct matrix{ int n, m, a[N][N]; // 初始矩阵 matrix() { memset(a, 0, sizeof a); } matrix(int _n, int _m) { n = _n, m = _m, memset(a, 0, sizeof a); } // 单位矩阵 matrix(int _n) { n = m = _n; for (int i = 1; i <= n; ++i) a[i][i] = 1; } // 定义矩阵 matrix(int _n, int _m, const int t[N][N]) { n = _n, m = _m; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) a[i][j] = t[i][j]; } // 矩阵乘法 matrix operator*(const matrix &b) const { matrix res; res.n = n, res.m = b.m; for (int i = 1; i <= n; ++i) for (int j = 1; j <= b.m; ++j) for (int k = 1; k >= 1, a = a * a; } return res;}资料来源
- 矩阵左乘和右乘的区别
- 矩阵 – OI Wiki
- Matrix Multiplication