线性代数基础

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

一、矩阵

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

1.1$\quad$ 矩阵的定义

矩阵$\quad$对于一个由 $n\times m$ 个数根据某些性质、关系组成的向量表

称为 $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]$：

数乘运算

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

矩阵乘法

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

设 $\mathbf{A}$ 为 $n\times m$ 的矩阵，$\mathbf{B}$ 为 $m\times w$ 的矩阵，设 $\mathbf{C}=\mathbf{A}\times \mathbf{B}$，则：

特殊地，如果 $\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]$​：

矩阵乘法满足结合律，即：

满足分配律，即：

转置运算

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

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

二、高斯消元

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

如，对于下面这个 $n$ 个未知数的线性方程组，求解每个未知数的值。

我们可以由此构造一个 $N$ 行 $N$ 列的增广矩阵 $\mathbf{A}$，其内容为各未知项系数及常数项，如下：

同理，我们也可以构造一个列向量 $\mathbf{X}$ 和列向量 $\mathbf{B}$，分别包含各各未知数与常数，如下：

我们就可以由此转换为矩阵方程：

我们的目标是求出矩阵 $\mathbf{X}$。根据矩阵乘法具有结合律，我们可以设法让等号两边同时乘以若干矩阵，使得矩阵 $\mathbf{A}$ 成为单位矩阵，即可求出矩阵 $\mathbf{X}$。也就是说，在主对角线上的数，通过变换，使其成为 $1$，其他数成为 $0$。

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

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

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

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

注意，等号左右两边需要同时处理，才能保证等号成立。所以我们可以直接合并两个矩阵，更方便地直接对一个矩阵进行变换，如下：

使左部分矩阵成为单位矩阵后，右边的列向量就是答案。

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

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

进行如下操作：

然后消去右上角：

此时，右边的矩阵就是 $\mathbf{X}$ 矩阵，即，解得：

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

高斯消元法 $\quad$ 对于任意一个存在 $n$ 个数、$n$ 个方程的线性方程组：

构造一个 $N$ 行 $N+1$ 列的矩阵：

对于每个未知量 $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}$ 消成 $\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|$，其值为：

其中，$p$ 为 $1..n$ 的排列，$\tau(p)$ 为排列 $p$ 中的逆序对数。

4.2$\quad$ 行列式的部分性质

三角行列式的值

对于上三角行列式，其值为主对角线的乘积，即：

由定义即可推出，证明略。

某行乘系数 $c$，等于整体乘 $c$

即：

由定义即可推出，证明略。

交换两行，符号取反

即：

证明$\quad$ 不妨设原行列式为 $|A|$，变换后的矩阵为 $|A’|$，有：

可以看到，两者的唯一区别就是 $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$ 构造符合要求的行列式并进行推导：

可以发现这个行列式有两行相等，设其为 $|A|$，可知，交换两行后矩阵数值不变，但等于 $-|A|$。故原行列式值为 $0$。