题解：P4783 【模板】矩阵求逆

· · 题解

题目传送门

题目要求

要求给定一个矩阵 A，输出它的逆矩阵 A^{-1}。

解法

首先给出逆矩阵的定义：若对于矩阵 A，存在矩阵 B 使得 A \times B=I，则称 B 是矩阵 A 的逆矩阵，记作 A^{-1}。

:::info[I 是什么] 若一个矩阵从左上角到右下角的对角线（主对角线）上的元素均为 1，除此以外全都为 0，则称这个矩阵为单位矩阵，记作 I 或 E。如下就是一个 4 阶单位矩阵：

I=\begin{bmatrix}1 &0 &0 &0 \\0 &1 &0 &0 \\0 &0 &1 &0 \\0 &0 &0 &1\end{bmatrix}

单位矩阵具有一些很好的性质，下面给出三个例子：

（注意矩阵乘法不满足交换律，所以上面两种写法是不等价的）

读者可以试着证明以上几条性质，也可以自行搜索相关知识。 :::

求一个矩阵 A 的逆矩阵 A^{-1} 常见的方法有高斯 - 约旦消元法、LU 分解、利用伴随矩阵。下面着重介绍一下高斯 - 约旦消元法。

:::info[简单介绍伴随矩阵解法] 定义矩阵

A=\begin{bmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{1,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1} &a_{n,2} &\cdots &a_{n,n}\\ \end{bmatrix}

那么它的伴随矩阵

A^*=\begin{bmatrix} A_{1,1} &A_{2,1} &\cdots &A_{n,1}\\ A_{1,2} &A_{2,2} &\cdots &A_{n,2}\\ \vdots &\vdots &\ddots &\vdots\\ A_{1,n} &A_{2,n} &\cdots &A_{n,n}\\ \end{bmatrix}

（其中 A_{i,j} 表示 A 关于 (i,j) 的代数余子式）。

所以我们可以对一个矩阵先求代数余子式再转置，得到 A 的伴随矩阵 A^*。

可以得到 A\times A^*= \left | A \right | \times I，所以有 A^{-1} = \frac{A^*}{\left | A \right | }。

但是在 A 的规模很大时，由于代数余子式的数量巨多，所以会导致时间复杂度较差 O(n^5)，所以只具有理论意义，一般不推荐使用。 :::

高斯 - 约旦消元法

我们构造 n \times 2n 的增广矩阵 [A \mid I]，然后通过行变换将左边化为单位矩阵 I，右边即为 A 的逆矩阵 A^{-1}。

所以我们可以先构造增广矩阵 [A \mid I]，然后逐列消元，得到结果。

消元的具体操作：

  1. 从左到右逐列处理，设当前列号为 c。
  2. 在 [c, n] 行中寻找第 c 列元素非零的行，若找不到则不存在 A 的逆矩阵 A^{-1}，即矩阵不可逆，无解。
  3. 将该行交换到第 c 行。
  4. 将当前行的第 c 列元素通过乘以逆元（利用费马小定理即可）化为 1。
  5. 用当前行消去其他所有行的第 c 列元素，使其变为 0。
  6. 继续处理下一列。

时间复杂度 O(n^3)。

AC 代码

#include <bits/stdc++.h>
#define N 410
#define P 1000000007
using namespace std;
typedef long long LL;
//十年OI一场空，不开long long见祖宗 
LL qp(LL a , LL b){
    LL res = 1;
    while(b){
        if(b & 1)
            res *= a,res %= P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
LL inv(LL a){
    return qp(a , P - 2);
}
int n;
LL a[N][N * 2];
int main(){
    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= n ; ++j)
            scanf("%lld" , &a[i][j]);
        a[i][n + i] = 1;
    }
    for(int c = 1 ; c <= n ; ++c){
        int r = c;
        while(r <=  n && a[r][c] == 0)
            r += 1;
        if(r > n){
            printf("No Solution");
            return 0;
        }
        if(r != c)
            for(int i = 1 ; i <= 2 * n ; ++i)
                swap(a[c][i] , a[r][i]);
        LL inv_ = inv(a[c][c]);
        for(int i = 1 ; i <= 2 * n ; ++i)
            a[c][i] *= inv_ , a[c][i] %= P;
        for(int i = 1 ; i <= n ; ++i){
            if(i == c || a[i][c] == 0)
                continue;
            LL num = a[i][c];
            for(int j = 1 ; j <= 2 * n ; ++j){
                a[i][j] = (a[i][j] - num * a[c][j]) % P;
                if(a[i][j] < 0)
                    a[i][j] += P;
            }   
        }
    }
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= n ; ++j)
            printf("%lld " , a[i][n + j]);
        printf("\n");
    }
    return 0;
}