矩阵求逆

矩阵求逆

矩阵乘法运算

复习一下矩阵乘法的运算规则。

矩阵快速幂

$$\left[ \begin{matrix} a&b&c\\ d&e&f\\ g&h&i\\ \end{matrix} \right] \left[ \begin{matrix} j&k&l\\ m&n&o\\ p&q&r\\ \end{matrix} \right] = \left[ \begin{matrix} aj+bm+cp&ak+bn+cq&al+bo+cr\\ dj+em+fp&dk+en+fq&dl+eo+fr\\ gj+hm+ip&gk+hn+iq&gl+ho+ir\\ \end{matrix} \right]$$

行列式

有：

$$A= \left[ \begin{matrix} a&b\\ c&d\\ \end{matrix} \right]$$

则：

$$|A|=ad-bc$$

逆矩阵

现在有矩阵：

$$A= \left[ \begin{matrix} 1&0\\ 1&4\\ \end{matrix} \right]$$

什么是逆矩阵呢？

就是我们要找到一个 $A^{-1}$，使得：

$$AA^{-1}= \left[ \begin{matrix} 1&0\\ 0&1\\ \end{matrix} \right]$$

二阶矩阵求逆直接套用公式即可：

$$A= \left[ \begin{matrix} a&b\\ c&d\\ \end{matrix} \right]$$ $$A^{-1}=|A| \left[ \begin{matrix} d&-b\\ -c&a\\ \end{matrix} \right] = \left[ \begin{matrix} \frac{d}{ad-bc}&\frac{-b}{ad-bc}\\ \frac{-c}{ad-bc}&\frac{a}{ad-bc}\\ \end{matrix} \right]$$

所以

$$A= \left[ \begin{matrix} 1&0\\ 1&4\\ \end{matrix} \right]$$

的逆矩阵为：

$$A^{-1}= \left[ \begin{matrix} 1&0\\ -\frac{1}{4}&\frac{1}{4}\\ \end{matrix} \right]$$ $$AA^{-1}= \left[ \begin{matrix} 1&0\\ 1&4\\ \end{matrix} \right] \left[ \begin{matrix} 1&0\\ -\frac{1}{4}&\frac{1}{4}\\ \end{matrix} \right] = \left[ \begin{matrix} 1&0\\ 0&1\\ \end{matrix} \right]$$

初等变换

基本求逆矩阵的方法。

假设我们现在有一个三阶矩阵：

$$A= \left[ \begin{matrix} 1&3&4\\ 6&2&4\\ 0&1&2\\ \end{matrix} \right]$$

我们需要一个伴随矩阵 $E$，当 $A$ 变成 $E$ 时，$E$ 即为 $A^{-1}$。

$$\left[ \begin{matrix} 1&3&4&|&1&0&0\\ 6&2&4&|&0&1&0\\ 0&1&2&|&0&0&1\\ \end{matrix} \right]$$

虚线右边即为伴随矩阵。

这是我们通过不断的消数，使 $A$ 变成 $E$ 的样子。

消数的方式是将两整行相减。或者是将整行乘或除一个数，使关键位置变成 $1$。

以下为其中一种过程：

$$\left[ \begin{matrix} 1&3&4&|&1&0&0\\ 6&2&4&|&0&1&0\\ 0&1&2&|&0&0&1\\ \end{matrix} \right]$$

消去第二行第一列的 $6$，可以让第二行减去六倍的第一行。

$$\left[ \begin{matrix} 1&3&4&|&1&0&0\\ 0&-16&-20&|&-6&1&0\\ 0&1&2&|&0&0&1\\ \end{matrix} \right]$$

将第二行关键位置变成 $1$，整行 $\times -\frac{1}{16}$。

$$\left[ \begin{matrix} 1&3&4&|&1&0&0\\ 0&1&\frac{5}{4}&|&\frac{3}{8}&-\frac{1}{16}&0\\ 0&1&2&|&0&0&1\\ \end{matrix} \right]$$

消去第三行第二列的 $1$，让第三行将去第二行即可。

$$\left[ \begin{matrix} 1&3&4&|&1&0&0\\ 0&1&\frac{5}{4}&|&\frac{3}{8}&-\frac{1}{16}&0\\ 0&0&\frac{3}{4}&|&-\frac{3}{8}&\frac{1}{16}&1\\ \end{matrix} \right]$$

将第三行关键位置变成 $1$，整行 $\times \frac{4}{3}$。

$$\left[ \begin{matrix} 1&3&4&|&1&0&0\\ 0&1&\frac{5}{4}&|&\frac{3}{8}&-\frac{1}{16}&0\\ 0&0&1&|&-\frac{1}{2}&\frac{1}{12}&\frac{4}{3}\\ \end{matrix} \right]$$

将第一行第二列的 $3$ 消掉，第一行减去三倍的第二行……

笔者的方法可能比较麻烦（一边先通过行之间加减，只剩关键位置，再处理整行的乘除），但是通过类似的方式，就会得到：

$$\left[ \begin{matrix} 1&0&0&|&0&\frac{1}{6}&-\frac{1}{3}\\ 0&1&0&|&1&-\frac{1}{6}&-\frac{5}{3}\\ 0&0&1&|&-\frac{1}{2}&\frac{1}{12}&\frac{4}{3}\\ \end{matrix} \right]$$

此时的

$$E= \left[ \begin{matrix} 0&\frac{1}{6}&-\frac{1}{3}\\ 1&-\frac{1}{6}&-\frac{5}{3}\\ -\frac{1}{2}&\frac{1}{12}&\frac{4}{3}\\ \end{matrix} \right] = A^{-1}$$

注意

有时一行的关键位置为零，可以通过交换两行，或加减其它行，来解决问题。

例如：

$$\left[ \begin{matrix} 0&1&1&|&1&0&0\\ 1&1&2&|&0&1&0\\ 0&1&0&|&0&0&1\\ \end{matrix} \right]$$

交换一二行。

$$\left[ \begin{matrix} 1&1&2&|&0&1&0\\ 0&1&1&|&1&0&0\\ 0&1&0&|&0&0&1\\ \end{matrix} \right]$$

交换二三行。

$$\left[ \begin{matrix} 1&1&2&|&0&1&0\\ 0&1&0&|&0&0&1\\ 0&1&1&|&1&0&0\\ \end{matrix} \right]$$

现在就可以对矩阵进行处理，得带逆矩阵了。

逆矩阵无解

如果一行消项时，全部为零（$A$ 矩阵，不包括伴随矩阵），那么矩阵无逆。

程序思路

P4783 【模板】矩阵求逆

• 找到有效值（不为 $0$ 的值，可以当成关键位置使用）

• 将有效值所在行、列与当前行、当前列交换，并且记录下交换的行和列

• 把当前行元素乘关键位置的逆元（同时判无解：逆元不存在）

• 若果要将关键位置化为 $1$，整行乘关键位置的逆元即可

• 对矩阵中的其他行做和 高斯消元 几乎完全一样的操作，只有每行的有关键位置列不一样。

• 最后把第 $2$ 步中的交换逆序地交换回来。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cctype>
using namespace std;
const long long m_d=1e9+7;
const int o_o=1e3+10; 
long long a_a[o_o][o_o];
int n,i_x[o_o],j_x[o_o];
long long r_r(){//快读 
    long long x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
void e_g(int a,int b,int &x,int &y){//找逆元 
    if(!b){
        x=1;
        y=0;
        return;
    }
    e_g(b,a%b,y,x);
    y-=x*(a/b);
}
int n_y(int p){//逆元 
    int x,y;
    e_g(p,m_d,x,y);
    return (x+m_d)%m_d;
}
void c_z(){
    for(int k=1;k<=n;k++){//每行进行遍历 
        for(int i=k;i<=n;i++)
            for(int j=k;j<=n;j++)
            if(a_a[i][j]){
                i_x[k]=i,j_x[k]=j;//找到一个有效值（不为 0 的值） 
                break;
            }
        for(int i=1;i<=n;i++)//交换行 
            swap(a_a[k][i],a_a[i_x[k]][i]);
        for(int i=1;i<=n;i++)//交换列 
            swap(a_a[i][k],a_a[i][j_x[k]]);
        if(!a_a[k][k]){//找不到有效值，无解 
            puts("No Solution");
            exit(0);//结束程序 
        }
        a_a[k][k]=n_y(a_a[k][k]);//关键位置求逆元 
        for(int j=1;j<=n;j++)//关键位置变为 1，整行都要乘它的逆元 
            if(j!=k)(a_a[k][j]*=a_a[k][k])%=m_d;
        for(int i=1;i<=n;i++)
            if(i!=k)
                for(int j=1;j<=n;j++)//每个位置的数更新 
                    if(j!=k)(a_a[i][j]+=m_d-a_a[i][k]*a_a[k][j]%m_d)%=m_d;
        for(int i=1;i<=n;i++)//消列 
            if(i!=k)a_a[i][k]=(m_d-a_a[i][k]*a_a[k][k]%m_d)%m_d;
    }
    for(int k=n;k;k--){//交换的行列交换回来 
        for(int i=1;i<=n;i++)swap(a_a[j_x[k]][i],a_a[k][i]);
        for(int i=1;i<=n;i++)swap(a_a[i][i_x[k]],a_a[i][k]);
        
        //注意，j_x,i_x 的位置，改变，要正确的变换，以下错误 
        /*
            for(int i=1;i<=n;i++)swap(a_a[i_x[k]][i],a_a[k][i]);
            for(int i=1;i<=n;i++)swap(a_a[i][j_x[k]],a_a[i][k]);
        */
    }
}
int main(){
    n=r_r();
    for(int i=1;i<=n;i++)//读入矩阵 
        for(int j=1;j<=n;j++)a_a[i][j]=r_r();
    c_z();//对矩阵操作 
    for(int i=1;i<=n;i++){//输出逆矩阵 
        for(int j=1;j<=n;j++)printf("%lld ",a_a[i][j]);
        puts("");
    }
    return 0;
}