在进行矩阵的运算的时候,我们会发现我们没有定义矩阵的除法,但是经常又需要做类似的操作,因而我们引入矩阵的逆的概念,用以填补这个空白。
矩阵的逆
由于我们在定义矩阵运算的时候只定义了数乘和矩阵乘法,而没有除法运算。和逆元的产生一样,我们为了定义出除法,我们采用乘一个数/矩阵得到单位1/单位矩阵的方法,并定义这个数/矩阵为原数/原矩阵的乘法。
注:单位矩阵是一个除了主对角线为1,其他全为0的方阵。由于阶数不固定,因而有无穷多种单位矩阵。
[
1
0
0
0
1
0
0
0
1
]
\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\\end{bmatrix}
⎣⎡100010001⎦⎤
定义:设
A
A
A为
n
n
n阶方阵,若存在
n
n
n阶方阵
B
B
B,使得
A
B
=
B
A
=
I
AB=BA=I
AB=BA=I,则称
B
B
B为
A
A
A的逆,并称
A
A
A为可逆矩阵。 记
A
−
1
A^{-1}
A−1为
A
A
A的逆。
若
A
A
A可逆,则逆唯一。
证明:若
B
B
B与
C
C
C都是
A
A
A的逆,由定义
A
B
=
B
A
=
I
AB=BA=I
AB=BA=I,
A
C
=
C
A
=
I
AC=CA=I
AC=CA=I,则有:
B
=
I
B
=
(
C
A
)
B
=
C
(
A
B
)
=
C
I
=
C
B=IB=(CA)B=C(AB)=CI=C
B=IB=(CA)B=C(AB)=CI=C
即
B
=
C
B=C
B=C
有一种用行列式来判定和计算矩阵是否可逆的方法,过于繁琐,不适用于计算,只在此介绍。
定义:设
n
n
n阶方阵
[
a
11
a
12
a
13
⋯
a
1
n
a
12
a
22
a
23
⋯
a
2
n
⋮
⋮
⋮
⋱
⋮
a
n
1
a
n
2
a
n
3
⋯
a
n
n
]
\begin{bmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\ a_{12} & a_{22} & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nn} \\ \end{bmatrix}
⎣⎢⎢⎢⎡a11a12⋮an1a12a22⋮an2a13a23⋮an3⋯⋯⋱⋯a1na2n⋮ann⎦⎥⎥⎥⎤
由
A
A
A的行列式
∣
A
∣
|A|
∣A∣中元素
a
i
j
a_{ij}
aij的代数余子式
A
i
j
A_{ij}
Aij构成的如下
n
n
n阶方阵:
A
∗
=
[
A
11
A
21
A
31
⋯
A
n
1
A
12
A
22
A
32
⋯
A
n
2
⋮
⋮
⋮
⋱
⋮
A
n
1
A
n
2
A
3
n
⋯
A
n
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∗=⎣⎢⎢⎢⎡A11A12⋮An1A21A22⋮An2A31A32⋮A3n⋯⋯⋱⋯An1An2⋮Ann⎦⎥⎥⎥⎤
称
A
∗
A^*
A∗为
A
A
A的伴随矩阵,而
A
A
A可逆的充要条件为
∣
A
∣
≠
0
|A| \neq 0
∣A∣=0,且
A
−
1
=
A
∗
∣
A
∣
A^{-1}=\frac{A^*}{|A|}
A−1=∣A∣A∗
此处证明需要用到行列式的性质,在此略去。
下文有更简单的判定和计算方法。
逆变换有一重要性质:若
A
,
B
A,B
A,B均可逆,则
A
B
AB
AB也可逆,且
(
A
B
)
−
1
=
B
−
1
A
−
1
(AB)^{-1}=B^{-1}A^{-1}
(AB)−1=B−1A−1。该性质可以反复利用,因此可以拓展到
k
k
k个可逆行列式相乘:
(
A
1
A
2
…
…
A
k
)
−
1
=
A
k
−
1
A
k
−
1
−
1
…
…
A
1
−
1
(A_1A_2……A_k)^{-1}=A_k^{-1}A_{k-1}^{-1}……A_1^{-1}
(A1A2……Ak)−1=Ak−1Ak−1−1……A1−1
初等矩阵
把单位矩阵进行一次初等行变换,就得到了初等矩阵。复习一下,初等行变换有以下三种:
1.交换矩阵的任意两行。
2.用一个非零整数
k
k
k乘矩阵的任意一行。
3.将矩阵中某一行乘以
k
k
k倍加到另外一行。
因此对于三阶单位矩阵
I
3
I_3
I3
[
1
0
0
0
1
0
−
4
0
1
]
[
0
1
0
1
0
0
0
0
1
]
[
1
0
0
0
1
0
0
0
5
]
\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}
⎣⎡10−4010001⎦⎤⎣⎡010100001⎦⎤⎣⎡100010005⎦⎤
均为初等矩阵。
由于初等行变换可逆(可以改过去又可以改回来),因此初等矩阵可逆。
证明:设
E
E
E为一初等矩阵,由于
E
I
=
E
EI=E
EI=E,因此任意一个初等矩阵可以视为对
I
I
I矩阵的一种变换,使其变为
E
E
E矩阵。由于初等行变换可逆,则存在
E
E
E变换的逆变换
F
F
F,将
E
E
E矩阵变回
I
I
I,因此
E
F
=
I
EF=I
EF=I,即
E
E
E可逆,且其逆为
E
E
E的逆变换。
到此可以引出本题的证明了:
方阵
A
A
A可逆,当且仅当
A
A
A行等价于
I
n
I_n
In ,即
A
A
A经过若干次行变换可以变成
I
n
I_n
In
充分性:由于
A
A
A可逆,则方程
A
x
=
b
Ax=b
Ax=b必有解,其中
x
,
b
x,b
x,b均为向量(求解只需要在等式两边左乘以
A
−
1
A^{-1}
A−1即可)。那么,对于解
x
x
x:
x
=
[
x
1
x
2
⋮
x
n
]
x=\begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n\\ \end{bmatrix}
x=⎣⎢⎢⎢⎡x1x2⋮xn⎦⎥⎥⎥⎤
必可写出与
A
A
A等价的增广矩阵
A
′
A'
A′(因为解一样):
A
′
=
[
1
x
1
1
x
2
⋱
⋮
1
x
n
]
A'=\left[ \begin{array}{cccc|c} 1&&&&x_1\\ &1&&&x_2\\ &&\ddots\ && \vdots\\ &&&1&x_n \end{array} \right]
A′=⎣⎢⎢⎢⎡11⋱ 1x1x2⋮xn⎦⎥⎥⎥⎤
那么原矩阵必与
I
n
I_n
In等价,否则无法化简成
A
′
A'
A′
必要性:如果
A
A
A等价于
I
n
I_n
In,则
A
A
A是由若干次初等行变换得到。对于每次初等行变换都有一个对应的初等矩阵,那么这些操作可以被记作:
E
p
E
p
−
1
…
…
E
1
A
=
I
n
E_pE_{p-1}……E_1A=I_n
EpEp−1……E1A=In
由矩阵逆的另一种定义,若
A
A
A可逆,则必存在一种能让
A
A
A回到
I
n
I_n
In的方法。考虑对上式两边左乘
(
E
p
E
p
−
1
…
…
E
1
)
−
1
(E_pE_{p-1}……E_1)^{-1}
(EpEp−1……E1)−1
(
(
E
p
E
p
−
1
…
…
E
1
)
−
1
E
p
E
p
−
1
…
…
E
1
)
A
=
(
E
p
E
p
−
1
…
…
E
1
)
−
1
I
n
((E_pE_{p-1}……E_1)^{-1}E_pE_{p-1}……E_1)A=(E_pE_{p-1}……E_1)^{-1}I_n
((EpEp−1……E1)−1EpEp−1……E1)A=(EpEp−1……E1)−1In
即
A
=
(
E
p
E
p
−
1
…
…
E
1
)
−
1
A=(E_pE_{p-1}……E_1)^{-1}
A=(EpEp−1……E1)−1,为可逆矩阵的乘积,因此
A
A
A可逆,且
A
−
1
=
E
p
E
p
−
1
…
…
E
1
A^{-1}=E_pE_{p-1}……E_1
A−1=EpEp−1……E1。因此,
A
−
1
A^{-1}
A−1可以由
E
1
,
E
2
,
…
…
,
E
p
E_1,E_2,……,E_p
E1,E2,……,Ep依次作用于
I
n
I_n
In得到。
得证。
接下来就是解法时间
我们把
A
A
A和
I
n
I_n
In置于同一矩阵中:
[
A
I
n
]
\begin{bmatrix} A & I_n \end{bmatrix}
[AIn]
对其进行高斯-若尔当消元操作将
A
A
A变换为
I
n
I_n
In。由于是在同一矩阵中,因此
A
A
A和
I
n
I_n
In得到的操作都是一样的。我们只需要让前面的
A
A
A变换为
I
n
I_n
In,那么对于同一过程,
I
n
I_n
In就会变成矩阵的逆。
用一张图来表示这个互相转化关系:
A
⇔
P
′
P
I
n
⇔
P
′
P
A
−
1
A\stackrel{P}{\underset{P'}{\Leftrightarrow}}I_n\stackrel{P}{\underset{P'}{\Leftrightarrow}}A^{-1}
AP′⇔PInP′⇔PA−1
下面是洛谷P4783的代码,内含逆元,但是大体思路一样,因而还是放上代码。
#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;
}