矩阵
矩阵是一种非常重要的数学对象，它通常由一个由数字排成的矩形阵列来定义。一个矩阵由若干行和若干列组成，被称为矩阵的行数和列数。一般情况下，矩阵的行数和列数分别用 n n n m m m
矩阵中的每个元素都用一个下标表示，第 i i i j j j A i , j A_{i,j} A i , j i i i j j j
单位矩阵是指矩阵的主对角线上为 1 1 1 0 0 0 I \mathbf{I} I
I = [ 1 0 ⋯ 0 0 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ 1 ] \mathbf{I}=\begin{bmatrix}1 & 0 & \cdots & 0 \\0 & 1 & \cdots & 0 \\\vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 1\end{bmatrix}
I = 1 0 ⋮ 0 0 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ 1
单位矩阵性质：设有一个矩阵 A A A I × A = A \mathbf{I} \times A= A I × A = A
矩阵加法
设矩阵 A A A B B B A + B A+B A + B A i , j + B i , j A_{i,j}+B_{i,j} A i , j + B i , j
矩阵乘法
矩阵乘法是一种在两个矩阵之间进行的运算，其中一个矩阵的列数需等于另一个矩阵的行数。假设有两个矩阵 A n × p A_{n \times p} A n × p B p × m B_{p \times m} B p × m
A = [ a 1 , 1 a 1 , 2 ⋯ a 1 , p a 2 , 1 a 2 , 2 ⋯ a 2 , p ⋮ ⋮ ⋱ ⋮ a n , 1 a n , 2 ⋯ a n , p ] B = [ b 1 , 1 b 1 , 2 ⋯ b 1 , m b 2 , 1 b 2 , 2 ⋯ b 2 , m ⋮ ⋮ ⋱ ⋮ b p , 1 b p , 2 ⋯ b p , m ] A=\begin{bmatrix}a_{1,1} & a_{1,2} & \cdots & a_{1,p}\\a_{2,1} & a_{2,2} & \cdots & a_{2,p}\\\vdots & \vdots & \ddots &\vdots\\a_{n,1} & a_{n,2} & \cdots & a_{n,p}\\\end{bmatrix}\quad B=\begin{bmatrix}b_{1,1} & b_{1,2} & \cdots & b_{1,m}\\b_{2,1} & b_{2,2} & \cdots & b_{2,m}\\\vdots & \vdots & \ddots &\vdots\\b_{p,1} & b_{p,2} & \cdots & b_{p,m}\\\end{bmatrix}
A = a 1 , 1 a 2 , 1 ⋮ a n , 1 a 1 , 2 a 2 , 2 ⋮ a n , 2 ⋯ ⋯ ⋱ ⋯ a 1 , p a 2 , p ⋮ a n , p B = b 1 , 1 b 2 , 1 ⋮ b p , 1 b 1 , 2 b 2 , 2 ⋮ b p , 2 ⋯ ⋯ ⋱ ⋯ b 1 , m b 2 , m ⋮ b p , m
矩阵乘积 C n × m C_{n \times m} C n × m c i , j c_{i,j} c i , j
c i , j = ∑ k = 1 p a i , k b k , j c_{i,j} = \sum_{k=1}^p a_{i,k}b_{k,j}
c i , j = k = 1 ∑ p a i , k b k , j
上式中的 k k k 1 ≤ k ≤ p 1 \leq k \leq p 1 ≤ k ≤ p
矩阵乘法不满足交换律，即 A × B ≠ B × A A \times B \neq B \times A A × B = B × A A × ( B × C ) = ( A × B ) × C A \times (B \times C) = (A \times B) \times C A × ( B × C ) = ( A × B ) × C
例题：
广义矩阵乘法
定义：
⊗ \otimes ⊗ a ⊗ b = b ⊗ a ; a\otimes b=b\otimes a; a ⊗ b = b ⊗ a ; ⊗ \otimes ⊗ ( a ⊗ b ) ⊗ c = a ⊗ ( b ⊗ c ) ; (a\otimes b)\otimes c=a\otimes(b\otimes c); ( a ⊗ b ) ⊗ c = a ⊗ ( b ⊗ c ) ; ⊗ \otimes ⊗ ⊕ \oplus ⊕ a ⊗ ( b ⊕ c ) = ( a ⊗ b ) ⊕ ( a ⊗ c ) ; a\otimes(b\oplus c)=(a\otimes b)\oplus(a\otimes c); a ⊗ ( b ⊕ c ) = ( a ⊗ b ) ⊕ ( a ⊗ c ) ;
对于矩阵 $ A$ 和 $ B$，若 ⊗ \otimes ⊗ ⊗ \otimes ⊗ ⊕ \oplus ⊕
( A × B ) i , j = ⨁ k ( A i , k ⊗ B j , k ) ( A\times B)_{i,j}=\bigoplus_k(A_{i,k}\otimes B_{j,k})
( A × B ) i , j = k ⨁ ( A i , k ⊗ B j , k )
广义矩阵乘法同样满足普通矩阵乘法的结合律。
常见的有：
⊕ \oplus ⊕ + + + ⊗ \otimes ⊗ × \times × ⊕ \oplus ⊕ min \min min max \max max ⊗ \otimes ⊗ + + +
扩展阅读
高斯消元
实数域上的高斯消元：
bool gauss(int n) {
int c = 1, r = 1, t = r;
for (; c <= n; c ++ , t = r) {
for (int i = r; i <= n; i ++ ) if (fabs(a[i][c]) > fabs(a[t][c])) t = i;
if (fabs(a[t][c]) < eps) continue;
swap(a[t], a[r]);
for (int i = n + 1; i >= c; i -- ) a[r][i] /= a[r][c];
for (int i = r + 1; i <= n; i ++ ) {
if (fabs(a[i][c]) > eps) {
for (int j = n + 1; j >= c; j -- ) {
a[i][j] -= a[r][j] * a[i][c];
}
}
}
r ++ ;
}
if (r <= n) {
for (int i = r; i <= n; i ++ ) if (fabs(a[i][n + 1]) > eps) return puts("No Solution"), 0;
return puts("Cannot Determine"), 0;
}
for (int i = n; i >= 1; i -- ) {
for (int j = i + 1; j <= n; j ++ ) {
a[i][n + 1] -= a[i][j] * a[j][n + 1];
}
}
return 1;
}异或空间上的高斯消元：
见 线性基学习笔记 #构造-高斯消元
线性空间
线性空间 是一个关于 向量加法 和 标算乘法 两个运算构成的向量集合。
向量加法：a + b a + b a + b a , b a, b a , b
标算乘法：k × a k \times a k × a k k k
给定若干个向量 a 1 , a 2 , a 3 … a k a_1, a_2, a_3 \dots a_k a 1 , a 2 , a 3 … a k b b b a 1 , a 2 , a 3 … a k a_1, a_2, a_3 \dots a_k a 1 , a 2 , a 3 … a k 向量加法 和 标算乘法 得到，则称向量 b b b a 1 , a 2 , a 3 … a k a_1, a_2, a_3 \dots a_k a 1 , a 2 , a 3 … a k 表出 ，显然，所有的 a 1 , a 2 , a 3 … a k a_1, a_2, a_3 \dots a_k a 1 , a 2 , a 3 … a k a 1 , a 2 , a 3 … a k a_1, a_2, a_3 \dots a_k a 1 , a 2 , a 3 … a k 生成子集 。
从线性空间中的任选出若干个向量，如果其中一个向量能被其他向量能表出，则称这些向量 线性相关 ，否则称这些向量 线性无关 。
线性无关的生成子集，成为这个线性空间的 基底 （极大线性无关子集）。
小提示：
线性空间与矩阵
对于一个 n × m n \times m n × m m m m 行向量 ，矩阵的 n n n 行秩 ，类似的，我们可以定义矩阵的 列向量 和 行秩 。实际上矩阵的行秩等于列秩，他们被共同称为矩阵的 秩 。
可以发现，高斯消元后得到的 简化阶梯矩阵 中的主元个数即为矩阵的秩，主元是这个线性空间的基底。
初等行变换实际上就对应了向量的两个运算。
线性基
见 线性基学习笔记 。
行列式基础
定义
对于一个矩阵 A A A
det ( A ) = ∣ A ∣ = ∑ p ( − 1 ) τ ( p ) ∏ i = 1 n a i , p i \det(A)=|A|=\sum_p(-1)^{\tau(p)}\prod_{i=1}^na_{i,p_i}
det ( A ) = ∣ A ∣ = p ∑ ( − 1 ) τ ( p ) i = 1 ∏ n a i , p i
其中 p p p p p p 1 1 1 n n n n n n τ ( p ) \tau(p) τ ( p ) p p p
性质
交换对应矩阵的两行或两列，行列式取反。
某一行加上若干倍的另外一行，行列式不变。
某一行乘一个数，行列式也乘那个数。
行列式内某一行的公因子可以提出。
1. 对角行列式
形如 ∣ a 1 , 1 0 ⋯ 0 0 a 2 , 2 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ a n , n ∣ \begin{vmatrix} a_{1,1}& 0& \cdots & 0\\ 0& a_{2,2}& \cdots & 0\\ \varvdots & \varvdots & \ddots & \varvdots \\ 0& 0& \cdots & a_{n,n}\end{vmatrix} a 1 , 1 0 ⋮ 0 0 a 2 , 2 ⋮ 0 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ a n , n a 1 , 1 × a 2 , 2 ⋯ a n , n a_{1,1}\times a_{2,2}\cdots a_{n,n} a 1 , 1 × a 2 , 2 ⋯ a n , n
2. 三角行列式
形如 ∣ a 1 , 1 a 1 , 2 ⋯ a 1 , n 0 a 2 , 2 ⋯ a 2 , n ⋮ ⋮ ⋮ 0 0 0 a n , n ∣ \begin{vmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\0&a_{2,2}&\cdots&a_{2,n}\\\varvdots&\varvdots&&\varvdots\\0&0&0&a_{n,n}\end{vmatrix} a 1 , 1 0 ⋮ 0 a 1 , 2 a 2 , 2 ⋮ 0 ⋯ ⋯ 0 a 1 , n a 2 , n ⋮ a n , n
求值
直接根据定义求值的复杂度为 O ( n ! × n ) O(n!\times n) O ( n ! × n )
我们可以考虑将原矩阵消元成上三角矩阵，行列式即为对角线的积。
例如有行列式 ∣ 2 3 5 3 4 7 4 3 2 ∣ \begin{vmatrix}2&3&5\\3&4&7\\4&3&2\end{vmatrix} 2 3 4 3 4 3 5 7 2 2 ∼ 3 2\sim3 2 ∼ 3 − 3 2 , − 2 -\frac32,-2 − 2 3 , − 2 ∣ 2 3 5 0 − 1 2 − 1 2 0 − 3 − 8 ∣ \begin{vmatrix}2&3&5\\0&-\frac12&-\frac12\\0&-3&-8\end{vmatrix} 2 0 0 3 − 2 1 − 3 5 − 2 1 − 8
接下来，把第三行加上第二行的 − 6 -6 − 6 ∣ 2 3 5 0 − 1 2 − 1 2 0 0 − 5 ∣ \begin{vmatrix}2&3&5\\0&-\frac{1}{2}&-\frac{1}{2}\\0&0&-5\end{vmatrix} 2 0 0 3 − 2 1 0 5 − 2 1 − 5
于是原式化为了一个三角行列式。对角线乘积即为答案 5 5 5
带模行列式求值
注意到 m o d \bmod mod
我们发现求解 gcd \gcd g cdgcd \gcd g cd0 0 0
我们模仿辗转相除法。
int ans = 1, coe = 1;
for (int i = 1; i <= n; i ++ ) {
for (int j = i + 1; j <= n; j ++ ) {
while (a[i][i]) { // 没消掉
int d = a[j][i] / a[i][i];
for (int k = i; k <= n && d; k ++ ) {
int v = mod - 1ll * d * a[i][k] % mod;
a[j][k] = (a[j][k] + v) % mod;
}
swap(a[i], a[j]), coe = -coe;
}
swap(a[i], a[j]), coe = -coe;
}
if (!a[i][i]) return puts("0"), 0;
}
for (int i = 1; i <= n; i ++ ) ans = 1ll * a[i][i] * ans % mod;
ans = (ans * coe + mod) % mod;
printf("%d\n", ans);