引入
矩阵的引入来自线性方程组，将其左边每一项的系数和右边的常数抽象出来就是矩阵。
\[\left\{ \begin{array}{} x_1 + 2x_2 = 4 \\ 2x_1 + 3x_2 = 5 \end{array} \right. \Leftrightarrow \left[ \begin{array}{} 1 & 2 \\ 2 & 3 \end{array} \right] \left[ \begin{array}{} x_1\\ x_2 \end{array} \right] = \left[ \begin{array}{} 4 \\ 5 \end{array} \right] \]一般用 \([]\) 或 \(()\) 表示矩阵。
定义
主对角线
对于一个矩阵 \(A\)，\(A_{i,i}\) 为该矩阵主对角线。
单位矩阵
一般用 \(I\) 表示，它的主对角线是 \(1\)，其余的是 \(0\)。
全零矩阵
对于一个矩阵，如果其所有元素均为 \(0\)，则称其为全零矩阵，记作 \(0\)。
同型矩阵
两个矩阵，行数与列数对应相同，称为同型矩阵。
转置矩阵
如果矩阵 \(A\) 和矩阵 \(B\) 满足：
- 矩阵 \(A\) 的行数等于矩阵 \(B\) 的列数，矩阵 \(A\) 的列数等于矩阵 \(B\) 的行数。
- 对于 \(\forall i,j, A_{i,j} = B_{j,i}\)。
则称 \(A\) 是 \(B\) 的转置矩阵，记作 \(A = B^T\)。
方阵
一个行数和列数相等的矩阵。
一个大小为 \(n\) 的矩阵叫作 \(n\) 阶矩阵或 \(n\) 阶方阵。
三角矩阵
如果方阵主对角线左下方的元素均为 \(0\)，称为上三角矩阵。如果方阵主对角线右上方的元素均为 \(0\)，称为下三角矩阵。
两个上（下）三角矩阵的乘积仍然是上（下）三角矩阵。如果对角线元素均非 \(0\)，则上（下）三角矩阵可逆，逆也是上（下）三角矩阵。
单位三角矩阵
如果上三角矩阵 \(A\) 的对角线全为 \(1\)，则称 \(A\) 是单位上三角矩阵。如果下三角矩阵 \(A\) 的对角线全为 \(1\)，则称 \(A\) 是单位下三角矩阵。
两个单位上（下）三角矩阵的乘积仍然是单位上（下）三角矩阵，单位上（下）三角矩阵的逆也是单位上（下）三角矩阵。
运算
线性运算
对两个同型矩阵可以作加（减）法，得到的答案是对应元素的和（差）。
矩阵的转置
即将一个矩阵变成它的转置矩阵。
矩阵乘法
如果矩阵 \(A\) 的行数等于矩阵 \(B\) 的列数，列数等于矩阵 \(B\) 行数，则这两个矩阵可以相乘，相乘的积矩阵 \(C\)，满足 \(C_{i,j} = \sum A_{i,k} \times B_{k,j}\)，即矩阵 \(C\) 的第 \(i\) 行第 \(j\) 列等于矩阵 \(A\) 的第 \(i\) 行乘上矩阵 \(B\) 的第 \(j\) 列。
可以发现，矩阵 \(C\) 的行数等于矩阵 \(A\) 的行数，列数等于矩阵 \(B\) 的列数。
因此矩阵乘法不满足交换律。
矩阵乘法运算律
- 乘法结合律，\(A \times (B \times C) = (A \times B) \times C\)。
- 乘法分配律，\(A \times (B + C) = A \times B + A \times C\)。
矩阵的逆
如果 \(A \times B = I\)，那么 \(B\) 是 \(A\) 的逆矩阵，记作 \(A^{-1}\)。
注意：逆矩阵不一定存在，但如果逆矩阵存在则是唯一的，至于怎么求，可以用高斯消元。
行列式
行列式。
实现
可以发现矩阵可以使用二维数组进行模拟。
显然地，线性运算时间复杂度 \(\mathcal{O}(n ^ 2)\)，乘法运算时间复杂度 \(\mathcal{O}(n^3)\)。
对于普通的矩阵这两个复杂度是不能优化的。
常数优化
当然进行矩阵乘法时，可以通过改变循环顺序加速高速缓存的访问优化部分常数（还挺猛），对于小矩阵也可以通过循环展开实现。
struct Matrix{
int mat[N][N];
Matrix(){
memset(mat, 0, sizeof(mat));
}
int * operator [] (const int & x){
return mat[x];
}
Matrix operator * (const Matrix & x){
Matrix ans;
for (int k = 1; k <= m; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= x.m; j++) {
//multi
}
}
}
return ans;
}
};
矩阵乘法的运用
矩阵快速幂
过程
因为矩阵有结合律，所以自然可以使用快速幂进行优化矩乘。
实现
Matrix qpow(int b, Matrix & mat){//mat 是转移矩阵
Matrix ans;
//prework
for (; b; b >>= 1, mat = mat * mat) {
if (b & 1) {
ans = ans * mat;// matrix multi
}
}
return ans;
}
矩阵加速递推
一个经典的矩阵快速幂问题，斐波拉契数列。
在斐波拉契数列中，
\[F_i = \begin{cases} 1 & i = 1 \vee i = 2 \\ F_{i - 1} + F_{i - 2} & \text{otherwise} \end{cases} \]很显然的可以构造矩阵，
\[\left[ \begin {array} {} F_{i} & F_{i - 1} \end {array} \right] \left[ \begin {array} {} 1 & 0 \\ 1 & 1 \end {array} \right] = \left[ \begin {array} {} F_{i + 1} & F_{i} \end {array} \right] \]实现
此处求斐波拉契第 \(n\) 项模 \(10 ^ 9 + 7\) 的结果的部分代码。
i64 n;
Matrix qpow(i64 b){
Matrix mat, ans;
ans[1][1] = 1, ans[1][2] = 0;
ans[2][1] = 0, ans[2][2] = 1;
mat[1][1] = 1, mat[1][2] = 1;
mat[2][1] = 1, mat[2][2] = 0;
for (; b; b >>= 1, mat = mat * mat) {
if (b & 1) {
ans = ans * mat;
}
}
return ans;
}
int main(){
scanf("%lld", &n);
Matrix ans = qpow(n - 1);
printf("%lld", ans[1][1]);
return 0;
}
线性常系数齐次递推式
当然，有时会在递推式中给定一些常数。
比如：
\(F_i = F_{i - 1} + F_{i - 2} + i ^ 2 + i\)。
\(i\) 的递推可以由 \(i - 1 + 1\) 得到，\(i ^ 2\) 可以由 \((i - 1) ^ 2 + i ^ 2 - (i - 1) ^ 2 = 2i - 1 + (i - 1)^2\) 得到。
所以维护 \(i^0,i^1, i^2\) 即可，就可以构造如下矩阵实现状态转移。
\[\left [ \begin{array} {} F_i & F_{i - 1} & i^2 & i & 1 \end{array} \right] \left [ \begin{array} {} 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 2 & 1 & 0 \\ 0 & 0 &-1 & 1 & 1 \end{array} \right] = \left [ \begin{array} {} F_{i + 1} & F_{i} & {i + 1}^2 & i + 1 & 1 \end{array} \right] \]