线性代数基础

线性代数是OI中常用的一部分数学知识。本篇主要记录高斯消元法和基础矩阵变换。

一、矩阵

矩阵是数学中常用的代数工具。当然，信息代数中的重点也许与数学不同，但大体思路相仿。

1.1\(\quad\) 矩阵的定义

矩阵\(\quad\)对于一个由 \(n\times m\) 个数根据某些性质、关系组成的向量表 \[ \begin{bmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,m}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,m}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,m}\\ \end{bmatrix} \] 称为 \(n\times m\) 的矩阵，记作矩阵 \(\mathbf{A}\)。

若矩阵 \(\mathbf{A}\) 和矩阵 \(\mathbf{B}\) 都是 \(n\times m\) 的矩阵，则称 \(\mathbf{A}\) 与 \(\mathbf{B}\) 为 同形矩阵。

若矩阵 \(\mathbf{A}\) 和矩阵 \(\mathbf{B}\) 为同形矩阵，并且 \(\forall i\in [1,n],j\in [1,m]\)，都有 \(a_{i,j}=b_{i,j}\)，则称 \(\mathbf{A}=\mathbf{B}\) 。

1.2\(\quad\)​ 特殊矩阵

方阵：有 \(n\) 行 \(n\) 列的矩阵。

零矩阵：每个元素都是 \(0\) 的矩阵，记为 \(\mathbf{0}\)。

行向量：只有一行的矩阵称为行矩阵。

列向量：只有一列的矩阵称为列举阵。

单位矩阵：主对角线元素均为 \(1\)，其余元素全为 \(0\) 的 \(n\) 阶方阵。

数量矩阵：主对角线元素均为 \(k\)，其余元素全为 \(0\) 的 \(n\) 阶方阵。

1.3\(\quad\) 矩阵的基本运算

矩阵加法

只有同形矩阵才能进行矩阵加法。

矩阵加法即同位置的数相加。设 \(\mathbf{A}\)、\(\mathbf{B}\)为 \(n\times m\) 的矩阵，\(\mathbf{C}=\mathbf{A}+\mathbf{B}\)，则 \(\forall i\in[1,n],j\in[1,m]\)： \[ C_{i,j}=A_{i,j}+B_{i,j} \]

数乘运算

数乘运算即矩阵中每一个数都乘这个数。设 \(\mathbf{A}\)为 \(n\times m\) 的矩阵，\(\mathbf{C}=\lambda\mathbf{A}\)，则 \(\forall i\in[1,n],j\in[1,m]\)： \[ C_{i,j}=\lambda A_{i,j} \]

矩阵乘法

两个矩阵能够相乘，当且仅当其中一个矩阵的第二维等于另一个矩阵的第一维。

设 \(\mathbf{A}\) 为 \(n\times m\) 的矩阵，\(\mathbf{B}\) 为 \(m\times w\) 的矩阵，设 \(\mathbf{C}=\mathbf{A}\times \mathbf{B}\)，则： \[ C_{i,j}=\sum^m_{k=1}A_{i,k}+B_{k,j} \] 特殊地，如果 \(\mathbf{A}\) 为 \(n\times n\) 的矩阵，\(\mathbf{B}\) 为 \(1\times n\) 的列矩阵，那么 \(\mathbf{B}\) 可省略一维，记 \(\mathbf{C}=\mathbf{A}\times \mathbf{B}\)，则 \(\mathbf{C}\) 为与 \(\mathbf{B}\) 同型的矩阵，\(\forall i\in [1,n]\)​： \[ C_{i}=\sum^n_{k=1}A_{i,k}+B_{k} \] 矩阵乘法满足结合律，即： \[ (\mathbf{A}\times\mathbf{B})\times\mathbf{C}=\mathbf{A}\times(\mathbf{B}\times\mathbf{C}) \] 满足分配律，即： \[ (\mathbf{A}+\mathbf{B})\times\mathbf{C}=\mathbf{A}\times\mathbf{C}+\mathbf{B}\times\mathbf{C} \]

转置运算

矩阵转置就是将矩阵行列调换位置。

设 \(\mathbf{A}\) 为 \(n\times m\) 的矩阵，设 \(\mathbf{A^T}\) 为矩阵 \(\mathbf{A}\) 的转置，则 \(\forall i\in[1,n],j\in[1,m]\)：

\[ A^T_{i,j}=A_{j,i} \]

二、高斯消元

高斯消元是求解线性方程组的一个方法。

如，对于下面这个 \(n\) 个未知数的线性方程组，求解每个未知数的值。 \[ \begin{cases} x_1&+2x_2&-x_3&=-6\\ 2x_1&+x_2&-3x_3&=-9\\ -x_1&-x_2&+2x_3&=7 \end{cases} \] 我们可以由此构造一个 \(N\) 行 \(N\) 列的增广矩阵 \(\mathbf{A}\)，其内容为各未知项系数及常数项，如下： \[ \mathbf{A}= \begin{bmatrix} 1&2&-1\\ 2&1&-3\\ -1&-1&2 \end{bmatrix} \] 同理，我们也可以构造一个列向量 \(\mathbf{X}\) 和列向量 \(\mathbf{B}\)，分别包含各各未知数与常数，如下： \[ \mathbf{X}= \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} \qquad \mathbf{B}= \begin{bmatrix} -6\\ -9\\ 7 \end{bmatrix} \] 我们就可以由此转换为矩阵方程： \[ \begin{bmatrix} 1&2&-1\\ 2&1&-3\\ -1&-1&2 \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix} = \begin{bmatrix} -6\\-9\\7 \end{bmatrix} \] 我们的目标是求出矩阵 \(\mathbf{X}\)。根据矩阵乘法具有结合律，我们可以设法让等号两边同时乘以若干矩阵，使得矩阵 \(\mathbf{A}\) 成为单位矩阵，即可求出矩阵 \(\mathbf{X}\)。也就是说，在主对角线上的数，通过变换，使其成为 \(1\)，其他数成为 \(0\)。

考虑在保证数量关系的前提下消元，使用如下方法：

  1. 对这一行消元，使得该行对角线上的数为 \(1\)。也就是除以这一行对角线上的数即可。

  2. 对其他行消元，利用对角线上的数和其他行的数的关系，使得其他行不在对角线上的数为 \(0\)。

如此重复处理，直至形成单位矩阵。

注意，等号左右两边需要同时处理，才能保证等号成立。所以我们可以直接合并两个矩阵，更方便地直接对一个矩阵进行变换，如下： \[ \left[\begin{array}{ccc|c} 1&2&-1&-6\\ 2&1&-3&-9\\ -1&-1&2&7 \end{array}\right] \] 使左部分矩阵成为单位矩阵后，右边的列向量就是答案。

我们可以进行如下操作，即 初等行变换：

  1. 用一个非零的数乘到某一行；
  2. 把其中一行的若干倍加到零一行上；
  3. 交换两行的位置。

进行如下操作： \[ \left[\begin{array}{ccc|c} 1&2&-1&-6\\ 2&1&-3&-9\\ -1&-1&2&7 \end{array}\right]\Longrightarrow \left[\begin{array}{ccc|c} 1&2&-1&-6\\ 0&-3&-1&3\\ -1&-1&2&7 \end{array}\right]\Longrightarrow \left[\begin{array}{ccc|c} 1&2&-1&-6\\ 0&-3&-1&3\\ 0&1&1&1 \end{array}\right] \]

\[ \Longrightarrow \left[\begin{array}{ccc|c} 1&2&-1&-6\\ 0&1&1&1\\ 0&-3&-1&3 \end{array}\right]\Longrightarrow \left[\begin{array}{ccc|c} 1&2&-1&-6\\ 0&1&1&1\\ 0&0&2&6 \end{array}\right]\Longrightarrow \left[\begin{array}{ccc|c} 1&2&-1&-6\\ 0&1&1&1\\ 0&0&1&3 \end{array}\right] \]

然后消去右上角： \[ \left[\begin{array}{ccc|c} 1&2&-1&-6\\ 0&1&1&1\\ 0&0&1&3 \end{array}\right]\Longrightarrow \left[\begin{array}{ccc|c} 1&2&0&-3\\ 0&1&0&-2\\ 0&0&1&3 \end{array}\right]\Longrightarrow \left[\begin{array}{ccc|c} 1&0&0&1\\ 0&1&0&-2\\ 0&0&1&3 \end{array}\right] \] 此时，右边的矩阵就是 \(\mathbf{X}\) 矩阵，即，解得： \[ \begin{cases} x_1=1\\ x_2=-2\\ x_3=3 \end{cases} \]

为了更格式化、更方便地处理问题，下面给出高斯消元的标准方法。

高斯消元法 \(\quad\) 对于任意一个存在 \(n\) 个数、\(n\) 个方程的线性方程组： \[ \begin{cases} a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=b_1\\ a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2\\ \vdots\\ a_{n,1}x_1+a_{n,2}x_2+\cdots+a_{n,n}x_n=b_n\\ \end{cases} \] 构造一个 \(N\) 行 \(N+1\) 列的矩阵： \[ \left[\begin{array}{cccc|c} a_{1,1}&a_{1,2}&\cdots&a_{1,n}&b_1\\ a_{2,1}&a_{2,2}&\cdots&a_{2,n}&b_2\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}&b_n\\ \end{array}\right] \] 对于每个未知量 \(x_i\)，找到一个 \(x_i\) 的系数非零，但 \(x_1\sim x_{i-1}\) 的系数都被消成了 \(0\) 的方程，利用初等行变换把其他方程的 \(x_i\) 的系数全部消成 \(0\)。

需要注意的是，如果有任意一个 \(x_i\)，找不到非零的方程，则无解。

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
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAXN 105
int n;
double a[MAXN][MAXN];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n+1;j++) cin>>a[i][j];
    }
    int nowi=1;
    for(int j=1;j<=n;j++){
        int t;
        for(t=nowi;t<=n;t++){
            if(fabs(a[t][j])>0) break;
        }
        if(t==n+1) continue;
        for(int i=j;i<=n+1;i++) swap(a[nowi][i],a[t][i]);
        for(int i=n+1;i>=j;i--) a[nowi][i]/=a[nowi][j];
        for(int i=1;i<=n;i++){
            if(i==nowi) continue;
            for(int k=n+1;k>=j;k--){
                a[i][k]-=a[i][j]*a[nowi][k];
            }
        }
        nowi++;
    }
    if(nowi<=n){
        puts("No Solution");
        return 0;
    }
    for(int i=1;i<=n;i++) printf("%.2lf\n",a[i][n+1]);
    return 0;
}

三、矩阵求逆

逆矩阵\(\quad\) 对于一个矩阵 \(\mathbf{A}\)，若存在一个矩阵 \(\mathbf{A'}\)，有 \(\mathbf{AA'=E(单位矩阵)}\)，则称 \(\mathbf{A'}\) 为 \(\mathbf{A}\) 的逆矩阵。

现在给定一个矩阵 \(\mathbf{A}\)，求他的逆矩阵 \(\mathbf{A'}\)。

我们可以考虑如下的思路。我们可以通过构造多个矩阵，考虑将矩阵 \(\mathbf{A}\) 消成单位矩阵，也对 \(\mathbf{E}\) 做相同操作，这样一来，就可以得出 \(\mathbf{A'}\)。

进而，我们通过矩阵乘法，构造多个矩阵，有： \[ \mathbf{A_1A_2\cdots A_k A=EA_1A_2\cdots A_k} \] 得出答案 \[ \mathbf{A'=A_1A_2\cdots A_k} \] 简化考虑，我们的目标是将 \(\mathbf{A}\) 消成 \(\mathbf{E}\)。因为矩阵乘法具有结合律所以我们可以同时在 \(\mathbf{A}\) 和原单位矩阵 \(\mathbf{E}\) 同时进行高斯消元，目标是使 \(\mathbf{A}\) 成为单位矩阵。即对于两部分的矩阵 \(\left[\begin{array}{c|c}\mathbf{A}&\mathbf{E}\end{array}\right]\)，对左半部分消元即可。

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
49
50
#include<iostream>
using namespace std;
#define MAXN 405
#define mod 1000000007
typedef long long ll;
ll n,a[MAXN][MAXN<<1];
ll qpow(ll a,ll b){
    ll w=1;
    while(b){
        if(b&1) w=w*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return w;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cin>>a[i][j];
    }
    for(int i=1;i<=n;i++) a[i][i+n]=1;
    for(int i=1;i<=n;i++){
        int r=i;
        for(int j=i;j<=n;j++){
            if(a[j][i]){
                r=j;
                break;
            }
        }
        if(r!=i) swap(a[i],a[r]);
        if(!a[i][i]) return puts("No Solution"),0;
        ll x=qpow(a[i][i],mod-2);
        for(int k=1;k<=n;k++){
            if(k==i) continue;
            ll t=a[k][i]*x%mod;
            for(int j=i;j<=(n<<1);j++){
                a[k][j]=((a[k][j]-t*a[i][j])%mod+mod)%mod;
            }
        }
        for(int j=1;j<=(n<<1);j++) a[i][j]=a[i][j]*x%mod;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j+n]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

四、行列式及求值

行列式和矩阵相似，都是用来解决线性问题的工具。

4.1\(\quad\) 行列式的定义

行列式\(\quad\) 对于一个 \(n\) 阶的方阵，它的行列式记作 \(|A|\)，其值为： \[ |A|=\sum_p\prod_{i=1}^n a_{i,p_i}(-1)^{\tau(p)} \] 其中，\(p\) 为 \(1..n\) 的排列，\(\tau(p)\) 为排列 \(p\) 中的逆序对数。

4.2\(\quad\) 行列式的部分性质

三角行列式的值

对于上三角行列式，其值为主对角线的乘积，即： \[ \begin{vmatrix} a_{1,1}&a_{1,2}&a_{1,3}&\cdots&a_{1,n}\\ 0&a_{2,2}&a_{2,3}&\cdots&a_{2,n}\\ 0&0&a_{3,3}&\cdots&a_{3,n}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&a_{n,n}\\ \end{vmatrix}=\prod_{i=1}^n a_{i,i} \] 由定义即可推出，证明略。

某行乘系数 \(c\)，等于整体乘 \(c\)

即： \[ \begin{vmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\ ca_{i,1}&ca_{i,2}&\cdots&ca_{i,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix}=c \begin{vmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i,1}&a_{i,2}&\cdots&a_{i,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} \] 由定义即可推出，证明略。

交换两行，符号取反

即： \[ \begin{vmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i,1}&a_{i,2}&\cdots&a_{i,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{j,1}&a_{j,2}&\cdots&a_{j,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} =-\begin{vmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{j,1}&a_{j,2}&\cdots&a_{j,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i,1}&a_{i,2}&\cdots&a_{i,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} \] 证明\(\quad\) 不妨设原行列式为 \(|A|\)，变换后的矩阵为 \(|A'|\)，有： \[ \begin{aligned} |A|=\sum_p (-1)^{\tau(p)}a_{1,p_1}a_{2,p_2}\cdots a_{i,p_i}\cdots a_{j,p_j}\cdots a_{n,p_n}\\ |A'|=\sum_p (-1)^{\tau(p)}a_{1,p_1}a_{2,p_2}\cdots a_{i,p_j}\cdots a_{j,p_i}\cdots a_{n,p_n} \end{aligned} \] 可以看到，两者的唯一区别就是 \(a_{i,p_i},a_{j,p_j}\) 和 \(a_{i,p_j},a_{j,p_i}\)。

由于 \(p\) 为前排列，所以可以忽略 \(p\) 位置的影响，只用考虑调换 \(p_i,p_j\) 对 \(\tau(p)\) 的影响。

考虑每一个 \(k,i,j\in[1,n],k\not=i,k\not=j,i<j\)：

  1. 若 \(k<i\)：调换 \(p_i,p_j\) 之后关于 \(p_k\) 的逆序对数不变。

  2. 若 \(k>j\)：调换 \(p_i,p_j\) 之后关于 \(p_k\) 的逆序对数也不变。

  3. 若 \(i<k<j\)：调换 \(p_i,p_j\) 之后关于 \(p_k\) 逆序对数会 成对地变化。

  4. \(p_i,p_j\) 位置变化会带来逆序对数变化 \(1\) 个。

综上，变化之后 \(\tau(p)\) 的 奇偶性 会发生变化，也就是 \(|A|=-|A'|\)。

证毕。

若存在两行对应成比例，则行列式值为 \(0\)

证明\(\quad\) 构造符合要求的行列式并进行推导： \[ \begin{vmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i,1}&a_{i,2}&\cdots&a_{i,n}\\ \vdots&\vdots&\ddots&\vdots\\ ca_{j,1}&ca_{j,2}&\cdots&ca_{j,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} =c\begin{vmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i,1}&a_{i,2}&\cdots&a_{i,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{j,1}&a_{j,2}&\cdots&a_{j,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} \] 可以发现这个行列式有两行相等，设其为 \(|A|\)，可知，交换两行后矩阵数值不变，但等于 \(-|A|\)。故原行列式值为 \(0\)。