【暖*墟】#逆矩阵# 矩阵求逆的思路与方法

矩阵求逆的思路与方法

逆矩阵的定义

若一个n*n的方阵A可逆，则存在一个n*n的方阵B，

使得

。则称B是A的一个逆矩阵。A的逆矩阵记作A^-1。

（1）验证两个矩阵互为逆矩阵

矩阵

按照矩阵的乘法满足：

。故A，B互为逆矩阵。

（2）逆矩阵的唯一性

若矩阵A是可逆的，则A的逆矩阵是唯一的。

【证明】若B,C都是A的逆矩阵，则有：

。

所以B=C，即A的逆矩阵是唯一的。

（3）判定简单的矩阵不可逆

如

。假设有

是A的逆矩阵，

则有：

逆矩阵的性质定理

如果矩阵A是可逆的，其逆矩阵是唯一的。
A的逆矩阵的逆矩阵还是A。记作（A^-1）^-1=A。
可逆矩阵A的转置矩阵A^T也可逆，并且（A^T）^-1=（A^-1）^{T _。}
若矩阵A可逆，则矩阵A满足消去律。即：若AB=AC，则B=C。
两个可逆矩阵的乘积依然可逆。

转置矩阵：将矩阵的行列互换得到的新矩阵，转置矩阵的行列式不变。

可逆等价条件

若|A|≠0，则矩阵A可逆，且

。其中，A^*为矩阵A的伴随矩阵。

求逆矩阵的初等变换法

将一n阶可逆矩阵A和n阶单位矩阵I写成一个nX2n的矩阵

。

对B施行初等行变换，即对A与I进行完全相同的若干初等行变换，目标是把A化为单位矩阵。

当A化为单位矩阵I的同时，B的右一半矩阵同时化为了A的逆矩阵。

如求

的逆矩阵A^-1。

，

故A可逆并且，由右一半可得逆矩阵A^-1=

。

初等变换法计算原理

若n阶方阵A可逆，即A行等价I，即存在初等矩阵P₁，P₂,...,P_k；

使得

，在此式子两端同时右乘A^-1得：

。

比较两式可知：对A和I施行完全相同的若干初等行变换，

在这些初等行变化把A变成单位矩阵的同时，这些初等行变换也将单位矩阵化为A^-1。

如果矩阵A和B互逆，则AB=BA=I。这两个矩阵的秩等于它们的级数（或称为阶）。

换句话说，这两个矩阵可以只经由初等行变换，或者只经由初等列变换，变为单位矩阵^_。

实例分析说明

相关知识介绍可以看这里

假设孩子和家长出去旅游，去程坐的是bus，小孩票价为3元，家长票价为3.2元；

回程坐的是Train，小孩票价为3.5元，家长票价为3.6元。问题是分别求小孩和家长的人数。

我们亦可以用下列矩阵求之（纵向）。

洛谷P4783 【模板】矩阵求逆

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;

const int mod=1e9+7,N=888;

int n,a[N][N];

inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}

#define mul(a,b) (1ll*(a)*(b)%mod)

int ksm(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);
   d=mul(d,d),k>>=1;}return f;} //ksm用于求逆元

int read(){ int x=0;char c=getchar(); while(!isdigit(c)) c=getchar();
   while(isdigit(c)) x=x*10+c-'0',c=getchar(); return x; }

int main(){ n=read();
    for(int i=1;i<=n;i++) //在原矩阵右边接一个单位矩阵↓↓
     { for(int j=1;j<=n;j++) a[i][j]=read(); a[i][i+n]=1; }
    for(int i=1;i<=n;i++){ //矩阵初等变换，即高斯消元
        int id=-1; for(int j=i;j<=n;j++) if(a[j][i]){id=j;break;}
        if(id==-1) return puts("No Solution"),0;
        std::swap(a[i],a[id]); int inv=ksm(a[i][i],mod-2);
        for(int j=i;j<=n<<1;j++) a[i][j]=mul(a[i][j],inv);
        for(int j=i+1;j<=n;j++) for(int k=n<<1;k>=i;k--)
            a[j][k]=add(a[j][k],mod-mul(a[i][k],a[j][i]));
    } /* 【原理】把原矩阵通过初等变换消成单位矩阵，
              右边的单位矩阵做同样的变换，就成了逆矩阵。 */
    for(int i=n;i;i--) for(int j=i-1;j;j--)
        for(int k=n<<1;k>=i;k--)
            a[j][k]=add(a[j][k],mod-mul(a[i][k],a[j][i]));
    for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)
        printf("%d ",a[i][j+n]); puts(""); }
}

洛谷P4100 [HEOI2013]钙铁锌硒维生素

#include <cmath>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

/*【p4100】钙铁锌
给定n个线性无关(不能用其他的加减表示)的向量A[1..n](如果不是线性无关直接输出无解即可)，
另外n个向量B[1..n]，求能否给A中的每一个向量选择一个B中的备用向量，
使得任意两个备用向量在B中编号不同，且A中的一个向量的备用向量和A中其余向量线性无关。*/

//【标签】二分图匹配 + 矩阵求逆

/*【分析】先对A中的每一个向量确定哪些向量可以备用，进行二分图最小字典序完美匹配。
首先可以考虑一个系数矩阵V,V[i][j]表示“B中第i个向量用A的线性组合表示时，A[j]项的系数”。
容易证明A[i]可以使用B[j]作为备用向量当且仅当Vji≠0（如果Vji=0,B[j]是A中其余向量的线性组合）。
那么Bij=∑(k=1~n)Vik*Akj，B=VA，即V=BA-1，求A矩阵的逆即可。*/

void reads(int &x){
    int fx=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')fx=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s-'0');s=getchar();}
    x=x*fx;//正负号
}

const int mod=998244353,N=666; //mod必须是质数

//----------------矩阵求逆---------------------\

inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}

#define mul(x,y) (1ll*(x)*(y)%mod)

int ksm(int a,int b){int anss=1;while(b){if(b&1)anss=mul(anss,a);
   a=mul(a,a),b>>=1;}return anss;} //ksm用于求逆元

int a[N][N],b[N][N],V[N][N],g[N][N],n;

bool Matrixinv(){ //矩阵求逆
    for(int i=1;i<=n;i++) a[i][i+n]=1; //右接单位矩阵
    for(int i=1;i<=n;i++){ //矩阵初等变换，即高斯消元
        int id=-1; for(int j=i;j<=n;j++) if(a[j][i]){id=j;break;}
        if(id==-1) return false; std::swap(a[i],a[id]);
        int inv=ksm(a[i][i],mod-2); //a[i][i]位置元素的逆元
        for(int j=n<<1;j>=i;j--) a[i][j]=mul(a[i][j],inv);
        for(int j=i+1;j<=n;j++) for(int k=n<<1;k>=i;k--)
            a[j][k]=add(a[j][k],mod-mul(a[j][i],a[i][k]));
    }/*【原理】把原矩阵通过初等变换消成单位矩阵，
          右边的单位矩阵做同样的变换，就成了逆矩阵。 */
    for(int i=n;i;i--) for(int j=i-1;j;j--)
        for(int k=n<<1;k>=i;k--)
            a[j][k]=add(a[j][k],mod-mul(a[j][i],a[i][k]));
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) 
        a[i][j]=a[i][j+n]; return true; //将逆矩阵复制回原矩阵
}

//----------------二分图匹配---------------------\

int used[N],match[N],to[N],ban[N];

bool dfs(int x){
    for(int i=1;i<=n;i++)
      if(g[x][i]&&!used[i]&&!ban[i]){ 
        used[i]=1; if(!match[i]||dfs(match[i]))
         { match[i]=x,to[x]=i; return true; }
    } return false;
}

//----------------主程序---------------------\

int main(){
    reads(n); for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++) reads(a[i][j]);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) reads(b[i][j]);

    if(!Matrixinv()) return puts("NIE"),0; //不是可逆矩阵，没有答案

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++) //矩阵乘法，即V=B*(A^(-1))
            V[i][j]=add(V[i][j],mul(b[i][k],a[k][j]));
    for(int i=1;i<=n;i++) //逆向记录可行性
        for(int j=1;j<=n;j++) if(V[i][j]) g[j][i]=1;

    for(int i=1;i<=n;i++){ //二分图匹配
        memset(used,0,sizeof(used));
        if(!dfs(i)) return puts("NIE"),0;
    } puts("TAK"); int tto[N],tmatch[N];

    for(int i=1;i<=n;i++){
        memset(used,0,sizeof(used));
        for(int j=1;j<=n;j++) //用于保存原数据
            tto[j]=to[j],tmatch[j]=match[j];
        int ver=to[i],flag=0; match[ver]=0;
        for(int j=1;j<ver;j++)
            if(g[i][j]&&!ban[j]&&!used[j]){
                used[j]=1; if(!ban[j]&&dfs(match[j]))
                 { to[i]=j; match[j]=i; flag=1; break; }
        } if(!flag) for(int j=1;j<=n;j++) //此处只能用to[i]
            to[j]=tto[j],match[j]=tmatch[j]; ban[to[i]]=1;

    } for(int i=1;i<=n;i++) printf("%d
",to[i]); //输出方案
}

——时间划过风的轨迹，那个少年，还在等你。