行列式
定义
定义 n 阶方阵 A 的行列式为:
detA=a1,1a2,1⋮an,1a1,2a2,2⋮an,2⋯⋯⋯a1,na2,n⋮an,n=p1,p2,⋯,pn∑(−1)τ(p1,p2,⋯,pn)i=1∏nai,pi
其中 {p1,p2,⋯,pn} 是一个 n 的排列,τ(p1,p2,⋯,pn) 表示 {p1,p2,⋯,pn} 的逆序数。
引理
Lemma 1
a1,1a2,1⋮kai,1⋮an,1a1,2a2,2⋮kai,2⋮an,2⋯⋯⋯⋯a1,na2,n⋮kai,n⋮an,n=ka1,1a2,1⋮ai,1⋮an,1a1,2a2,2⋮ai,2⋮an,2⋯⋯⋯⋯a1,na2,n⋮ai,n⋮an,n
读者自证不难。
Lemma 2
a1,1a2,1⋮ai,1⋮aj,1⋮an,1a1,2a2,2⋮ai,2⋮aj,2⋮an,2⋯⋯⋯⋯⋯a1,na2,n⋮ai,n⋮aj,n⋮an,n=−a1,1a2,1⋮aj,1⋮ai,1⋮an,1a1,2a2,2⋮aj,2⋮ai,2⋮an,2⋯⋯⋯⋯⋯a1,na2,n⋮aj,n⋮ai,n⋮an,n
读者自证不难。
Lemma 3
若矩阵有相同的两行,则行列式为零。
Proof: 交换相同的两行后矩阵不变,且由 Lemma 2 得行列式变号,即 ∣A∣=−∣A∣,所以 ∣A∣=0。□
Lemma 4
若矩阵某一行是另一行的倍数,则行列式为零。
Proof: 由 Lemma 1 & Lemma 3 易证。
Lemma 5
若 ∀j,ai,j=bj+cj,则
a1,1a2,1⋮ai,1⋮an,1a1,2a2,2⋮ai,2⋮an,2⋯⋯⋯⋯a1,na2,n⋮ai,n⋮an,n=a1,1a2,1⋮b1⋮an,1a1,2a2,2⋮b2⋮an,2⋯⋯⋯⋯a1,na2,n⋮bn⋮an,n+a1,1a2,1⋮c1⋮an,1a1,2a2,2⋮c2⋮an,2⋯⋯⋯⋯a1,na2,n⋮cn⋮an,n
读者自证不难。
Lemma 6
a1,1a2,1⋮ai,1⋮aj,1⋮an,1a1,2a2,2⋮ai,2⋮aj,2⋮an,2⋯⋯⋯⋯⋯a1,na2,n⋮ai,n⋮aj,n⋮an,n=a1,1a2,1⋮ai,1⋮aj,1+kai,1⋮an,1a1,2a2,2⋮ai,2⋮aj,2+kai,2⋮an,2⋯⋯⋯⋯⋯a1,na2,n⋮ai,n⋮aj,n+kai,n⋮an,n
Proof: 设
A=a1,1a2,1⋮ai,1⋮aj,1⋮an,1a1,2a2,2⋮ai,2⋮aj,2⋮an,2⋯⋯⋯⋯⋯a1,na2,n⋮ai,n⋮aj,n⋮an,n,B=a1,1a2,1⋮ai,1⋮kai,1⋮an,1a1,2a2,2⋮ai,2⋮kai,2⋮an,2⋯⋯⋯⋯⋯a1,na2,n⋮ai,n⋮kai,n⋮an,nC=a1,1a2,1⋮ai,1⋮aj,1+kai,1⋮an,1a1,2a2,2⋮ai,2⋮aj,2+kai,2⋮an,2⋯⋯⋯⋯⋯a1,na2,n⋮ai,n⋮aj,n+kai,n⋮an,n
由 Lemma 4 得 ∣B∣=0,由 Lemma 5 得 ∣C∣=∣A∣+∣B∣=∣A∣。□
Lemma 7
a1,10⋮0a1,2a2,2⋮0⋯⋯⋱⋯a1,na2,n⋮an,n=i∏ai,i
即上三角矩阵的行列式为主对角线元素的乘积。
Proof: 由行列式的定义得若 ∃i,ai,pi=0,那么整个排列对行列式无贡献。
因此要想对行列式有贡献,pn 必等于 n,同理得 ∀i,pi=i。□
求解
显然有 O(n!n) 的 naive 方法,但如果这样上面的 LATEX 就白写了(
考虑把矩阵转化为上三角矩阵并由 Lemma 7 O(n) 计算行列式。
这个过程形如高斯消元,于是考虑用高斯消元法来求解行列式。
假设目前处理到第 i 行,要使得 ∀j>i,aj,i=0。
显然可以让第 j 行加上第 i 行乘 −ai,iai,j,但对于任意模数情况下 ai,i 不一定有逆元。
因此,我们考虑用辗转相除法。
每次使得 aj,i←aj,imodai,i,并交换第 i 行与第 j 行,直到 ai,i 为 0。
即让第 j 行加上第 i 行乘 −⌊ai,iai,j⌋。
时间复杂度看似是 O(n3logP),但可以证明是 O(n3),其中 P 是模数。
参考代码
应用