定义
在数学中，矩阵是一个按照长方阵列排列的复数或实数集合。一个 $n\times m$ 的矩阵一般这样表示：
$$ A_{nm}=\begin{bmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1m} \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2m} \\ a_{31} & a_{32} & a_{33} & \cdots & a_{3m} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nm} \\ \end{bmatrix} $$
如果一个矩阵的行数和列数都等于 $n$，那么称这个矩阵为 $n$ 阶矩阵。
运算
加法减法
同型矩阵之间可以进行加减法，运算法则为：
$$ C_{ij}=A_{ij}\pm B_{ij} $$
乘法
一个 $n\times m$ 的矩阵 $A$ 可以和一个 $m\times p$ 的矩阵 $B$ 进行乘法运算，得到一个 $n\times p$ 的矩阵 $C$，运算法则为：
$$ C_{ij}=\sum_{k=1}^m A_{ik}\times B_{kj} $$
特殊矩阵
注意：以下矩阵中，没有明确标识的位置均表示 $0$！
初等矩阵
单位矩阵
$$ P=\begin{bmatrix} 1 & & & \\ & 1 & & \\ & & 1 & \\ & & & 1 \\ \end{bmatrix} $$
特征：除了主对角线上的元素为 $1$，其他元素均为 $0$。一般我们用字母 $E$ 来表示单位矩阵。
作用：$P$ 左乘 $A$ 矩阵，所得的结果还是 $A$ 矩阵本身。所以我们可以认为 $E$ 是矩阵乘法的单位元。
交换某两行
$$ P=\begin{bmatrix} 1 & & & \\ & 0 & 1 & \\ & 1 & 0 & \\ & & & 1 \\ \end{bmatrix} $$
特征：在单位矩阵的基础上，将第 $i$ 个 $1$ 向右移动一位，将第 $j$ 个 $1$ 向左移动一位。
作用：$P$ 左乘 $A$ 矩阵，可以将 $A$ 的第 $i$ 行和第 $j$ 行交换。
将一行的所有元素乘上 k
$$ P=\begin{bmatrix} 1 & & & \\ & 1 & & \\ & & k & \\ & & & 1 \\ \end{bmatrix} $$
特征：在单位矩阵的基础上，将第 $i$ 个 $1$ 乘上 $k$。
作用：$P$ 左乘 $A$ 矩阵，可以将 $A$ 的第 $i$ 行的所有元素乘上 $k$。
将一行的所有元素乘上 k 加到另一行去
$$ P=\begin{bmatrix} 1 & & k & \\ & 1 & & \\ & & 1 & \\ & & & 1 \\ \end{bmatrix} $$
特征：在单位矩阵的基础上，将第 $i$ 行第 $j$ 列的位置变为 $k$（这个位置不在对角线上）
作用：$P$ 左乘 $A$ 矩阵，可以将 $A$ 矩阵的第 $j$ 行的所有元素乘上 $k$ 加到第 $i$ 行去。
上三角矩阵
$$ P=\begin{bmatrix} 1 & 0 & 5 & 0 \\ & 4 & 7 & 0 \\ & & 9 & 7 \\ & & & 5 \\ \end{bmatrix} $$
特征：除了主对角线及以上的元素（可以为 $0$ 也可以不为 $0$）外，其他元素均为 $0$。
作用：矩阵的秩、高斯消元、求行列式等中的重要矩阵！
初等变换
定义
我们定义矩阵的三种初等行变换：
- 换行变换：交换某两行。
- 倍法变换：将某一行的所有元素乘上 $k$（其中 $k\neq 0$）。
- 消法变换：将某一行的所有元素乘上 $k$ 后加到另一行上去。
本质
其实这三种初等行变换和上文的特殊矩阵是有联系的：初等行变换的本质是用初等矩阵左乘矩阵 $A$。那么很显然，初等列变换的本质是用初等矩阵右乘矩阵 $A$。
秩
矩阵的秩分为行秩和列秩。一个矩阵 $A$ 的行秩是 $A$ 的线性无关独立的横行的极大数目；类似的，列秩是 $A$ 的线性无关独立的纵列的极大数目。
对于同一个矩阵而言，其行秩总是等于列秩的。
相抵
如果矩阵 $A$ 可以通过一系列初等行变换和初等列变换变成矩阵 $B$，则称 $A$ 和 $B$ 是相抵的。
可逆
对于一个矩阵 $A$，其可逆的充要条件是 $A$ 和 $E$ 是相抵的（即 $A$ 通过若干次初等行变换可以变成 $E$），也就是说存在一个矩阵 $P$ 使得 $PA=E$，则 $P=A^{-1}$。
有关矩阵求逆的相关过程详见：「算法笔记」矩阵求逆，其中有具体讲解如何方便地求一个矩阵的逆矩阵。
行列式
行列式是一个函数，结果是一个值。矩阵 $A$ 的行列式写作 $\det(A)$ 或 $\vert A\vert$。
一个矩阵的行列式求解公式为：
$$ \det(A)=\sum_{\forall P} [(-1)^{\tau(P)}\prod_{i=1}^n A_{i,P_i}] $$
其中 $\tau(P)$ 表示排列 $P$ 的逆序对数量。
阶数较小的矩阵可以手动求解行列式，比如二阶矩阵的行列式为：
$$ \det(A)=A_{11}A_{22}-A_{12}A_{21} $$
有关行列式的具体求解过程详见：「算法笔记」行列式，其中有具体讲解如何快速地求一个矩阵的行列式。
等价命题
以下这些命题均是等价的，即是彼此的充要条件！
- 矩阵满秩。
- 矩阵是可逆的。
- 矩阵的行列式不为 $0$。
板子
为了方便大家使用，笔者把自己的矩阵板子放在博客里！（可能会更新）
void add(int &x, int y) {
(x += y) >= mod && (x -= mod);
}
struct Matrix {
int n, A[N][N];
Matrix(int _n = 0) {
n = _n, memset(A, 0, sizeof(A));
}
void operator~() {
for (int i = 0; i < n; i++) A[i][i] = 1;
}
Matrix operator+(const Matrix &b) const {
Matrix ret(n);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
ret.A[i][j] = (A[i][j] + b.A[i][j]) % mod;
}
return ret;
}
Matrix operator-(const Matrix &b) const {
Matrix ret(n);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
ret.A[i][j] = (A[i][j] - b.A[i][j] + mod) % mod;
}
return ret;
}
Matrix operator*(const Matrix &b) const {
Matrix ret(n);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) {
add(ret.A[i][k], 1LL * A[i][j] * b.A[j][k] % mod);
}
return ret;
}
Matrix operator^(const long long &b) const {
Matrix ret(n), x = *this;
~ret;
for (long long p = b; p; p >>= 1, x = x * x) {
if (p & 1) ret = ret * x;
}
return ret;
}
void print() {
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
printf("%d%c", A[i][j], " \n"[j == n - 1]);
}
}
};