（Gauss-Jordan）高斯消元法求逆矩阵（含C/C++实现代码）

一、问题引出

给定一个 n × n n \times n n×n 的矩阵 A A A ，我们想求得一个矩阵 B B B 使得 ∣ A × B ∣ |A \times B| ∣A×B∣ 即 A A A 矩阵和 B B B 矩阵的积矩阵的行列式为 1 1 1 ，那么这个 B B B 矩阵就是 A A A 矩阵的逆矩阵，或者说 A × B A \times B A×B 得到单位矩阵 E E E

二、原理 2.1 矩阵求逆原理

• 我们先构造出一个 n × 2 n n\times 2n n×2n 的增广矩阵 ( A , I n ) (A,I_n) (A,In​)
• 然后用高斯消元法将这个增广矩阵化为最简形式 ( I n , A − 1 ) (I_n,A^{-1}) (In​,A−1) ，此时的增广部分就是 A A A 矩阵的逆矩阵，如果最后简化的左半部分矩阵不是单位矩阵那么说明矩阵 A A A 不可逆

2.2 矩阵消元原理

• 对于一个矩阵 A A A ，我们从第 1 1 1 行到第 n n n 行不断选取第 i i i 列不为 0 0 0 的行，然后做一个行变换（交换两行，使得当前的第 i i i 行的第 i i i 列不为0）
• 然后将当前的第 i i i 行做一个初等变换，也就是都除以 A [ i ] [ i ] A[i][i] A[i][i] 这样的话就能让第 i i i 行第 i i i 列变为 1 1 1
• 将第 i i i 行下面的所有行的第 i i i 列全部消掉，此时就构成了一个上三角矩阵
• 此时已经构成了一个阶梯型矩阵，我们再从下往上不断将上半矩阵同理消掉即可

三、举例

我们要求的 A A A 矩阵如下： [ 2   1   1 3   2   1 2   1   2 ] \begin{bmatrix} 2 \ 1 \ 1 \\ 3 \ 2 \ 1 \\ 2 \ 1 \ 2 \\ \end{bmatrix} ⎣⎡​2 1 13 2 12 1 2​⎦⎤​

1. 我们构造出增广矩阵：

[ 2   1   1   1   0   0 3   2   1   0   1   0 2   1   2   0   0   1 ] \begin{bmatrix} 2 \ 1 \ 1 \ 1 \ 0 \ 0 \\ 3 \ 2 \ 1 \ 0 \ 1 \ 0\\ 2 \ 1 \ 2 \ 0 \ 0 \ 1 \\ \end{bmatrix} ⎣⎡​2 1 1 1 0 03 2 1 0 1 02 1 2 0 0 1​⎦⎤​

2. 开始行变换，消除下三角

[ 1    1 / 2    1 / 2   1 / 2   0   0 0   1     − 1   − 3     2    0 0    0      1   − 1      0    1 ] \begin{bmatrix} 1 \ \ 1/2 \ \ 1/2 \ 1/2 \ 0 \ 0 \\ 0 \ 1 \ \ \ -1 \ -3 \ \ \ 2 \ \ 0\\ 0 \ \ 0 \ \ \ \ 1 \ -1 \ \ \ \ 0 \ \ 1 \\ \end{bmatrix} ⎣⎡​1  1/2  1/2 1/2 0 00 1   −1 −3   2  00  0    1 −1    0  1​⎦⎤​ 3. 从下往上消除上三角形

[ 1   0    0   3   − 1   − 1 0   1   0   − 4   2   1 0   0   1   − 1   0   1 ] \begin{bmatrix} 1 \ 0 \ \ 0 \ 3 \ -1 \ -1 \\ 0 \ 1 \ 0 \ -4 \ 2 \ 1\\ 0 \ 0 \ 1 \ -1 \ 0 \ 1 \\ \end{bmatrix} ⎣⎡​1 0  0 3 −1 −10 1 0 −4 2 10 0 1 −1 0 1​⎦⎤​

四、题目链接

https://www.luogu.com.cn/problem/P4783

五、代码实现 5.1 整数逆元逆矩阵

对于这个整数逆元逆矩阵，需要注意的一点是模数最好选择一个质数，否则很容易存在逆元不存在的情况，导致求解出来的逆矩阵不正确

#include
#define re register
#define il inline
#define ll long long
using namespace std;

il ll read(){
    ll s=0,f=0;char c=getchar();
    while(c'9') f=(c=='-'),c=getchar();
    while(c>='0'&&c