「算法笔记」矩阵入门

发表于 | | 阅读次数:
字数统计: 1.5k 字
矩阵是一个非常有用的工具，经常可以用于几何与代数之间的转化，以此来优化算法。

定义

在数学中，矩阵是一个按照长方阵列排列的复数或实数集合。一个 $n\times m​$ 的矩阵一般这样表示：

如果一个矩阵的行数和列数都等于 $n$，那么称这个矩阵为 $n​$ 阶矩阵。

运算

加法减法

同型矩阵之间可以进行加减法，运算法则为：

乘法

一个 $n\times m$ 的矩阵 $A$ 可以和一个 $m\times p$ 的矩阵 $B$ 进行乘法运算，得到一个 $n\times p$ 的矩阵 $C$，运算法则为：

特殊矩阵

注意：以下矩阵中，没有明确标识的位置均表示 $0$！

初等矩阵

单位矩阵

特征：除了主对角线上的元素为 $1$，其他元素均为 $0$。一般我们用字母 $E$ 来表示单位矩阵。

作用：$P$ 左乘 $A$ 矩阵，所得的结果还是 $A$ 矩阵本身。所以我们可以认为 $E$ 是矩阵乘法的单位元。

交换某两行

特征：在单位矩阵的基础上，将第 $i$ 个 $1$ 向右移动一位，将第 $j$ 个 $1​$ 向左移动一位。

作用：$P$ 左乘 $A$ 矩阵，可以将 $A$ 的第 $i$ 行和第 $j​$ 行交换。

将一行的所有元素乘上 k

特征：在单位矩阵的基础上，将第 $i$ 个 $1$ 乘上 $k$。

作用：$P$ 左乘 $A$ 矩阵，可以将 $A$ 的第 $i$ 行的所有元素乘上 $k​$。

将一行的所有元素乘上 k 加到另一行去

特征：在单位矩阵的基础上，将第 $i$ 行第 $j$ 列的位置变为 $k​$（这个位置不在对角线上）

作用：$P$ 左乘 $A$ 矩阵，可以将 $A$ 矩阵的第 $j$ 行的所有元素乘上 $k$ 加到第 $i$ 行去。

上三角矩阵

特征：除了主对角线及以上的元素（可以为 $0$ 也可以不为 $0$）外，其他元素均为 $0$。

作用：矩阵的秩、高斯消元、求行列式等中的重要矩阵！

初等变换

定义

我们定义矩阵的三种初等行变换：

  1. 换行变换：交换某两行。
  2. 倍法变换：将某一行的所有元素乘上 $k$（其中 $k\neq 0$）。
  3. 消法变换：将某一行的所有元素乘上 $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​$。

一个矩阵的行列式求解公式为：

其中 $\tau(P)$ 表示排列 $P$ 的逆序对数量。

阶数较小的矩阵可以手动求解行列式，比如二阶矩阵的行列式为：

有关行列式的具体求解过程详见：「算法笔记」行列式，其中有具体讲解如何快速地求一个矩阵的行列式。

等价命题

以下这些命题均是等价的，即是彼此的充要条件！

  • 矩阵满秩。
  • 矩阵是可逆的。
  • 矩阵的行列式不为 $0$。

板子

为了方便大家使用，笔者把自己的矩阵板子放在博客里！（可能会更新）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=10;
const int mod=1e9+7;

void upd(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) {
            upd(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]);
    }
};


int main() {
    
    return 0;
}
0%