1. 线性方程组的通解
对于二元一次方程组:
{a11x+a12y=b1a21x+a22y=b2
如果它有唯一解,那么利用高斯消元法,可以将它的解为:
{x=a11a22−a12a21b1a22−a12b2y=a11a22−a12a21b2a11−a21b1
这个解的分子和分母的形式非常相似,写成方阵形式时都是交叉相乘再相减,以分母为例:
a11a22−a12a21=a11a21a12a22
这样,上面方程组的解就可以表示为:
⎩⎨⎧x=a11a21a12a22b1b2a12a22y=a11a21a12a22a11a21b1b2
同样的,用高斯消元法可以求解三元一次方程组的解:
⎩⎨⎧x=a11a22a33−a11a23a32−a12a21a33+a12a23a31+a13a21a32−a13a22a31b1a22a33−b1a23a32−a12b2a33+a12a23b3+a13b2a32−a13a22b3y=a11a22a33−a11a23a32−a12a21a33+a12a23a31+a13a21a32−a13a22a31a11b2a33−a11a23b3−b1a21a33+b1a23a31+a13a21b3−a13b2a31z=a11a22a33−a11a23a32−a12a21a33+a12a23a31+a13a21a32−a13a22a31a11a22b3−a11b2a32−a12a21b3+a12b2a31+b1a21a32−b1a22a31
显然解的各项的分子与分母的形式都相似,如果将这种形式的参数用方阵表示,就是:
⎩⎨⎧x=a11a21a31a12a22a32a13a23a33b1b2b3a12a22a32a13a23a33y=a11a21a31a12a22a32a13a23a33a11a21a31b1b2b3a13a23a33z=a11a21a31a12a22a32a13a23a33a11a21a31a12a22a32b1b2b3
同样的,扩展到n元时,解可以表示为:
xi=a11a21⋮an1a12a22⋮an2⋯⋯⋱⋯a1na2n⋮anna11a21⋮an1⋯⋯⋯b1b2⋱bn⋯⋯⋯a1na2n⋮annith
这种方阵表示为解析式时,有n!项,每一项由前面的符号和n项系数的乘积组成,即:
(−1)ta1p1a2p2⋯anpn
其中p1p2⋯pn为{1,2,⋯,n}的全排列,aij为参数方阵的元素,t由排列的逆序数来确定。
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,则称为一个逆序对(英语:reverse pair)。一个排列中逆序对的个数称为该排列的逆序数(英语:reverse count)。
例如,对于数列A={3,2,5,4,1},用ti分别表示数列里第i个元素左侧比它大的元素的个数,那么:
⎩⎨⎧t1t2t3t4t5=0=1=0=1=4
该数列的逆序数为tA=∑i=15ti=6。
上面的数列,交换一下5和4的顺序,即B={3,2,4,5,1},用ti分别表示数列里第i个元素左侧比它大的元素的个数,那么:
⎩⎨⎧t1t2t3t4t5=0=1=0=0=4
此时,该数列的逆序数为tB=∑i=15ti=5。
交换排列的任意两个元素,排列的逆序数会改变奇偶性。
求解线性方程组时,总结出来的方阵即为行列式(Determinant)。
2. 行列式的定义
方阵A的行列式(英语:determinant),是一种数学运算,结果是一个数,记作∣A∣或det(A)。 n×n的方阵A,其行列式可以表示为:
det(A)=∣A∣=a11a21⋮an1a12a22⋮an2⋯⋯⋱⋯a1na2n⋮ann且
det(A)=∑(−1)ta1p1a2p2⋯anpn或
det(A)=∑(−1)tap11ap22⋯apnn其中t为排列p1p2⋯pn的逆序数,aij为A的元素。
2.1. 二阶行列式
det[acbd]=acbd=ad−bc
等于列向量 [ac] 和 [bd] 张成的平行四边形面积。
2.2. 三阶行列式
a11a21a31a12a22a32a13a23a33=a11a22a32a23a33−a12a21a31a23a33+a13a21a31a22a32
等于三个列向量张成的平行六面体体积,这与向量的混合积一致:
det[abc]=a⋅(b×c)
。
2.3. 行列式的计算复杂度
直接根据其定义进行行列式计算,以3阶行列式为例,它共有3!种排列方式,每种排列需要2次乘法,所以总共需要2×3!=12次乘法。同时,它还需要3!−1=5次加/减法,所以总的计算量为12+5=17次。
对于n阶,它共有n!种排列方式,每种排列需要n−1次乘法,所以总共需要(n−1)n!次乘法。
同时,它还需要n!−1次加/减法,所以总的计算量为(n−1)n!+n!−1=n×n!−1次。
直接计算n阶行列式的计算复杂度为O(n!),对于复杂的方阵,计算行列式的代价是很大的。
3. 拉普拉斯展开
对于一个3×3的方阵A=a11a21a31a12a22a32a13a23a33,将其行列式按第一行的项合并,有:
det(A)=a11a22a33−a11a23a32−a12a21a33+a12a23a31+a13a21a32−a13a22a31=a11(a22a33−a23a32)−a12(a21a33−a23a31)+a13(a21a32−a22a31)=a11×a22a32a23a33−a12×a21a31a23a33+a13×a21a31a22a32=a11∣A11∣−a12∣A12∣+a13∣A13∣=j=1∑3(−1)1+ja1jdet(A1j)
其中Aij表示A的去掉第i行第j列后的子阵(英语:sub matrix),其对应的行列式det(Aij),称作余子式(英语:minor)。
将上述形式推广到n阶方阵,有:
det(A)=∣A∣=j=1∑n(−1)i+jaijdet(Aij)=j=1∑naijCij
其中,Cij为代数余子式(英语:cofactor),表示的是余子式和它前面的符号结合起来,即:
Cij=(−1)i+jdet(Aij)
除了可以按第一行展开,还可以按第一列展开,甚至可以按任意一行或列展开,这就定义了一种递归的计算行列式的方法,即拉普拉斯展开(英语:Laplace expansion)。
对于任意n×n的方阵A,n≥2,都有:
- 以第i行展开:
det(A)=∣A∣=j=1∑n(−1)i+jaijdet(Aij)=j=1∑naijCij
- 以第j列展开:
det(A)=∣A∣=i=1∑n(−1)i+jaijdet(Aij)=i=1∑naijCij其中,Cij=(−1)i+jdet(Aij),为代数余子式。
例如,∣A∣=147258369的计算过程如下:
∣A∣=1×(−1)1+1×5869+2×(−1)1+2×4769+3×(−1)1+3×4758=1×5869−2×4769+3×4758=1×(5×9−6×8)−2×(4×9−6×7)+3×(4×8−5×7)=1×(−3)−2×(−6)+3×(−3)=0
3.1 计算复杂度
令M(n)为n阶行列式需要的乘法次数,A(n)为n阶行列式需要的加法/减法次数。显然,M(2)=2,A(2)=1。
对于n≥3,有:
A(n)=n−1+nA(n),M(n)=n+nM(n−1)
先化简A(n):
A(n)+1=n(A(n−1)+1)=n(n−1)(A(n−2)+1)=n(n−1)⋯3(A(2)+1)=n⋅(n−1)⋯3⋅2⋅1=n!
那么,A(n)=n!−1。
再化简M(n):
M(n)=n+nM(n−1)=n+n(⋯(5+5⋅(4+4⋅(3+3⋅M(2)))))=n+n(⋯(5+5⋅(4+4⋅(3+3⋅2))))=n+n(⋯(5+5⋅4+5⋅4⋅3+5⋅4⋅3⋅2))=n+n⋅(n−1)+n⋅(n−1)⋅(n−2)+⋯+n!=n!(1+2!1+⋯+(n−1)!1)
那么,有:n!<M(n)<(1−e)n!
因此,通过拉普拉斯定理展开行列式计算复杂度为A(n)+M(n),即O(n!)。
使用拉普拉斯展开计算行列式的计算复杂度为O(n!),对于复杂的矩阵,计算行列式的代价是很大的。
4. 行列式的性质
4.1 基本性质
对于一个n×n的方阵A,其行列式有如下性质:
- 如果A某行或列的元素全为0,则行列式为0。
- 如果A的某两行或两列相等,则行列式为0。
- 交换A的两行或两列得到B,则∣B∣=−∣A∣,即交换两行或两列会改变行列式的符号。
- A的某行或某列乘以k得到B,则∣B∣=k∣A∣。
- ∣kA∣=kn∣A∣
- 将某一行/列的k倍,加减到另一行/列,得到的行列式不变。
4.2 三角阵的行列式
对于一个n×n的方阵A,如果它是上三角阵或下三角阵,则其行列式可以用对角线元素的乘积得到,即:
∣A∣=i=1∏naii
通过不断进行行/列变换得到三角阵的复杂度为O(n3),三角阵的行列式计算复杂度是O(n)。先化为三角阵再计算行列式,可大幅降低行列式的计算复杂度。
例如计算A=390−1−54627的行列式:
∣A∣=390−1−54627(第二行减去第一行的3倍)=300−1−246−167(第三行加第二行的2倍)=300−1−206−16−25=3×(−2)×(−25)=150
4.3 矩阵与行列式
- 对于方阵A,当且仅当det(A)=0时,A可逆,且有det(A−1)=det(A)1
- det(AB)=det(A)det(B)
- det(A+B)=det(A)+det(B)
- det(AT)=det(A)
5. 行列式的几何意义
将方阵 A 视为一个线性变换,det(A) 的绝对值表示变换后单位体积被缩放了多少倍,其符号表示变换是否改变了空间的定向(英语:orientation):
- det(A)>0:变换保持空间定向不变(右手系仍为右手系)。
- det(A)<0:变换反转了空间定向(右手系变为左手系)。
- det(A)=0:变换将空间压缩到了更低维度(降维),即 A 为奇异矩阵,不可逆。
6. 克拉默法则
以三元一次方程组的解为例:
x=a11a21a31a12a22a32a13a23a33b1b2b3a12a22a32a13a23a33,y=a11a21a31a12a22a32a13a23a33a11a21a31b1b2b3a13a23a33,z=a11a21a31a12a22a32a13a23a33a11a21a31a12a22a32b1b2b3
显然,分母是参数方阵的行列式,分子是b替换参数方阵的第i列得到的矩阵的行列式。
推广到n阶时,A是一个n×n矩阵,b是一个n×1列向量。Ai(b)表示用b替代A在第i列得到的新矩阵,即:
Ai(b)=[a1⋯b⋯an]ith
单位矩阵In的每一列都是一个单位向量,即In=[e1e2⋯en],其中ei是i号单位向量。
如果Ax=b,那么有:
AIi(x)=A[e1⋯x⋯en]=[Ae1⋯Ax⋯Aen]=[a1⋯b⋯an]=Ai(b)
因此,
det(AIi(x))=det(A)det(Ii(x))=det(Ai(b))
而
det(Ii(x))=10⋮0⋮0001⋮0⋮00⋯⋯⋱⋯⋯⋯x1x2⋮xi⋮xn−1xn⋯⋯⋯⋱⋯⋯00⋮0⋮0000⋮0⋮01=xi
于是,
xi=det(A)det(Ai(b))
这就是克拉默法则(英语:Cramer's rule)。
设A是一个n×n矩阵,b是一个n×1列向量,那么Ax=b的解x满足:
x=det(A)1det(A1(b))⋮det(An(b))即:
xi=det(A)det(Ai(b))其中i∈{1,2,⋯,n}。
6.1 应用
设A是一个n×n矩阵,如果A可逆,那么存在矩阵X,使得AX=In,令xj为X的第j列。每次求解一列,即Axj=ej,应用克拉默法则,有:
xij=det(A)det(Ai(ej))
而,
det(Ai(ej))=a11⋮aj1⋮an1⋯⋱⋯⋯0⋮1⋮0⋯⋯⋱⋯a1n⋮ajn⋮ann=(−1)j+idet(Aji)=Cji
于是,xij=det(A)Cji。因此X=det(A)1[Cji]=det(A)1[Cij]T。
其中
[Cji]=[Cij]T=C11⋮C1n⋯⋱⋯Cn1⋮Cnn
称为A的伴随矩阵(英语:adjoint matrix),记作adj(A)。
设A是一个n×n矩阵,如果A可逆,那么有:
A−1=det(A)1adj(A)其中,adj(A)是A的伴随矩阵。
例如,求解A=2111−1223−2的逆。
首先,A的各代数余子式为:
C11C21C31=+−123−2=−4,C12=−113−2=5,C13=+11−12=3,=−122−2=6,C22=+212−2=−6,C23=−2112=−3,=+1−123=5,C32=−2123=−4,C33=+211−1=−3
因此,
det(A)=2×(−4)+1×5+2×3=3
同时,A的伴随矩阵为:
adj(A)=−4655−6−43−3−3T=−4536−6−35−4−3
因此,A的逆为:
A−1=31−4536−6−35−4−3=3−43512−2−135−34−1