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

· · 题解

严格证明来了！

如果还不用学习线性代数的童鞋们，可以直接看下文的简化题解，跳过中间的证明；但是要是卑微的大学牲，建议还是康康吧（大雾）

完整证明版

需要以下前置知识：

1.矩阵的逆及其存在的判定方法

2.初等矩阵及其性质

矩阵的逆

由于我们在定义矩阵运算的时候只定义了数乘和矩阵乘法，而没有除法运算。和逆元的产生一样，我们为了定义出除法，我们采用乘一个数/矩阵得到单位 1/单位矩阵的方法，并定义这个数/矩阵为原数/原矩阵的乘法。

注：单位矩阵是一个除了主对角线为 1，其他全为 0 的方阵。由于阶数不固定，因而有无穷多种单位矩阵。

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

定义：设 A 为 n 阶方阵，若存在n阶方阵 B，使得 AB=BA=I，则称 B 为 A 的逆，并称 A 为可逆矩阵。 记 A^{-1} 为 A 的逆。

若 A 可逆，则逆唯一。

证明：若 B 与 C 都是 A 的逆，由定义 AB=BA=I，AC=CA=I，则有：

B=IB=(CA)B=C(AB)=CI=C

即 B=C。

有一种用行列式来判定和计算矩阵是否可逆的方法，过于繁琐，不适用于计算，只在此介绍。

定义：设 n 阶方阵

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

由 A 的行列式 |A| 中元素 a_{ij} 的代数余子式 A_{ij} 构成的如下 n 阶方阵：

A^*=\begin{bmatrix} A_{11} & A_{21} & A_{31} & \cdots & A_{n1} \\ A_{12} & A_{22} & A_{32} & \cdots & A_{n2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ A_{n1} & A_{n2} & A_{3n} & \cdots & A_{nn} \\ \end{bmatrix}

称 A^* 为 A 的伴随矩阵，而 A 可逆的充要条件为 |A| \neq 0，且

A^{-1}=\frac{A^*}{|A|}

此处证明需要用到行列式的性质，在此略去。

下文有更简单的判定和计算方法。

逆变换有一重要性质：若A,B均可逆，则AB也可逆，且(AB)^{-1}=B^{-1}A^{-1}。该性质可以反复利用，因此可以拓展到k个可逆行列式相乘：

(A_1A_2……A_k)^{-1}=A_k^{-1}A_{k-1}^{-1}……A_1^{-1}

初等矩阵

把单位矩阵进行一次初等行变换，就得到了初等矩阵。其中，初等行变换有以下三种：

1.交换矩阵的任意两行。

2.用一个非零整数 k 乘矩阵的任意一行。

3.将矩阵中某一行乘以 k 倍加到另外一行。

因此对于三阶单位矩阵 I_3

\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0\\ -4 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0\\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0\\ 0 & 0 & 5 \\ \end{bmatrix}

均为初等矩阵。

由于初等行变换可逆（可以改过去又可以改回来），因此初等矩阵可逆。

证明：设 E 为一初等矩阵，由于 EI=E，因此任意一个初等矩阵可以视为对 I 矩阵的一种变换，使其变为 E 矩阵。由于初等行变换可逆，则存在 E 变换的逆变换 F，将 E 矩阵变回 I，因此 EF=I，即 E 可逆，且其逆为 E 的逆变换。

到此可以引出本题的证明了：

方阵 A 可逆，当且仅当 A 行等价于 I_n ，即 A 经过若干次行变换可以变成 I_n。

充分性：由于 A 可逆，则方程 Ax=b 必有解，其中 x,b 均为向量（求解只需要在等式两边左乘以 A^{-1} 即可）。那么，对于解 x：

x=\begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n\\ \end{bmatrix}

必可写出与 A 等价的增广矩阵 A'（因为解一样）：

A'=\left[ \begin{array}{cccc|c} 1&&&&x_1\\ &1&&&x_2\\ &&\ddots\ && \vdots\\ &&&1&x_n \end{array} \right]

那么原矩阵必与 I_n 等价，否则无法化简成 A'

必要性：如果 A 等价于 I_n，则 A 是由若干次初等行变换得到。对于每次初等行变换都有一个对应的初等矩阵，那么这些操作可以被记作：

E_pE_{p-1}……E_1A=I_n

由矩阵逆的另一种定义，若 A 可逆，则必存在一种能让 A 回到 I_n 的方法。考虑对上式两边左乘 (E_pE_{p-1}……E_1)^{-1}

((E_pE_{p-1}……E_1)^{-1}E_pE_{p-1}……E_1)A=(E_pE_{p-1}……E_1)^{-1}I_n

即 A=(E_pE_{p-1}……E_1)^{-1}，为可逆矩阵的乘积，因此 A 可逆，且 A^{-1}=E_pE_{p-1}……E_1。因此，A^{-1} 可以由 E_1,E_2,……,E_p 依次作用于 I_n 得到。

得证。

接下来就是解法时间

我们把 A 和 I_n 置于同一矩阵中：

\begin{bmatrix} A & I_n \end{bmatrix}

对其进行高斯-若尔当消元操作将A变换为I_n。由于是在同一矩阵中，因此A和I_n得到的操作都是一样的。我们只需要让前面的A变换为I_n，那么对于同一过程，I_n就会变成矩阵的逆。

用一张图来表示这个互相转化关系：

A\stackrel{P}{\underset{P'}{\Leftrightarrow}}I_n\stackrel{P}{\underset{P'}{\Leftrightarrow}}A^{-1}

所以剩下的就是代码功夫了。代码附上：

#include <cstdio>
#include <algorithm>
using namespace std;
const long long mod = 1000000007;
long long power(long long a,int x)//快速幂板子
{
    long long ans = 1;
    while(x)
    {
        if(x&1)
        {
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        x >>= 1;
    }
    return ans % mod;
}
long long a[405][805];
int main()
{
    int n, m;
    scanf("%d", &n);
    m = 2 * n;//矩阵的宽
    for (int i = 1; i <= n;i++)
    {
        for (int j = 1; j <= n;j++)
            scanf("%lld", &a[i][j]);
        a[i][i + n] = 1;//后面要跟上一个n阶单位矩阵
    }
    for (int i = 1; i <= n; i++)//高斯-若尔当消元的板子
    {
        int place = i;
        for (int j = i + 1; j <= n; j++)//找到绝对值最大的元素开始消元
            if(abs(a[j][i])>abs(a[place][i]))
                place = j;
        if (i != place)
            swap(a[i], a[place]);
        if(!a[i][i])//如果某行没有主元则A无法化为单位矩阵，无解
        {
            printf("No Solution");
            return 0;
        }
        long long inv = power(a[i][i], mod - 2);//本题加入的逆元特色
        for (int j = 1; j <= n; j++)
            if(j!=i)
            {
                long long multiple = a[j][i] * inv % mod;//等价于除以a[i][i]，消去其他行在第i列上的数，使之变成简化阶梯形矩阵
                for (int k = i; k <= m; k++)
                    a[j][k] = ((a[j][k] - a[i][k] * multiple) % mod + mod) % mod;
            }
        for (int j = 1; j <= m; j++)//由于此处需要简化阶梯型矩阵，要把原矩阵化为简化矩阵的必须操作。
        //“在使用高斯-若尔当消元的时候，计算机计算的时候通常采用回带法，而人操作的时候建议采用此法。”——《线性代数及其应用》
            a[i][j] = (a[i][j] * inv % mod);
    }
    for (int i = 1; i <= n;i++)
    {
        for (int j = n + 1; j <= m; j++)//只打印后面，前面的单位矩阵不要打出来了
            printf("%lld ", a[i][j]);
        printf("\n");
    }
    return 0;
}