跳转至

行列式

定义

定义 nn 阶方阵 AA 的行列式为:

detA=a1,1a1,2a1,na2,1a2,2a2,nan,1an,2an,n=p1,p2,,pn(1)τ(p1,p2,,pn)i=1nai,pi \det A=\begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} =\sum_{p_1,p_2,\cdots,p_n} (-1)^{\tau(p_1,p_2,\cdots,p_n)} \prod_{i=1}^n a_{i,p_i}

其中 {p1,p2,,pn}\{p_1,p_2,\cdots,p_n\} 是一个 nn 的排列,τ(p1,p2,,pn)\tau(p_1,p_2,\cdots,p_n) 表示 {p1,p2,,pn}\{p_1,p_2,\cdots,p_n\} 的逆序数。

引理

Lemma 1

a1,1a1,2a1,na2,1a2,2a2,nkai,1kai,2kai,nan,1an,2an,n=ka1,1a1,2a1,na2,1a2,2a2,nai,1ai,2ai,nan,1an,2an,n \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ ka_{i,1} & ka_{i,2} & \cdots & ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = k \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix}

读者自证不难。

Lemma 2

a1,1a1,2a1,na2,1a2,2a2,nai,1ai,2ai,naj,1aj,2aj,nan,1an,2an,n=a1,1a1,2a1,na2,1a2,2a2,naj,1aj,2aj,nai,1ai,2ai,nan,1an,2an,n \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = -\begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix}

读者自证不难。

Lemma 3

若矩阵有相同的两行,则行列式为零。

Proof: 交换相同的两行后矩阵不变,且由 Lemma 2 得行列式变号,即 A=A|A|=-|A|,所以 A=0|A|=0\square

Lemma 4

若矩阵某一行是另一行的倍数,则行列式为零。

Proof:Lemma 1 & Lemma 3 易证。

Lemma 5

j,ai,j=bj+cj\forall j,a_{i,j} = b_j + c_j,则

a1,1a1,2a1,na2,1a2,2a2,nai,1ai,2ai,nan,1an,2an,n=a1,1a1,2a1,na2,1a2,2a2,nb1b2bnan,1an,2an,n+a1,1a1,2a1,na2,1a2,2a2,nc1c2cnan,1an,2an,n \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ b_1 & b_2 & \cdots & b_n \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} + \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ c_1 & c_2 & \cdots & c_n \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix}

读者自证不难。

Lemma 6

a1,1a1,2a1,na2,1a2,2a2,nai,1ai,2ai,naj,1aj,2aj,nan,1an,2an,n=a1,1a1,2a1,na2,1a2,2a2,nai,1ai,2ai,naj,1+kai,1aj,2+kai,2aj,n+kai,nan,1an,2an,n \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} = \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1}+ka_{i,1} & a_{j,2}+ka_{i,2} & \cdots & a_{j,n}+ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix}

Proof:

A=a1,1a1,2a1,na2,1a2,2a2,nai,1ai,2ai,naj,1aj,2aj,nan,1an,2an,n,B=a1,1a1,2a1,na2,1a2,2a2,nai,1ai,2ai,nkai,1kai,2kai,nan,1an,2an,nC=a1,1a1,2a1,na2,1a2,2a2,nai,1ai,2ai,naj,1+kai,1aj,2+kai,2aj,n+kai,nan,1an,2an,n A = \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1} & a_{j,2} & \cdots & a_{j,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix}, B = \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ ka_{i,1} & ka_{i,2} & \cdots & ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} \\ C = \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{i,1} & a_{i,2} & \cdots & a_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{j,1}+ka_{i,1} & a_{j,2}+ka_{i,2} & \cdots & a_{j,n}+ka_{i,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix}

Lemma 4B=0|B|=0,由 Lemma 5C=A+B=A|C| = |A| + |B| = |A|\square

Lemma 7

a1,1a1,2a1,n0a2,2a2,n00an,n=iai,i \begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ 0 & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_{n,n} \\ \end{vmatrix} = \prod_i a_{i,i}

即上三角矩阵的行列式为主对角线元素的乘积。

Proof: 由行列式的定义得若 i,ai,pi=0\exists i, a_{i,p_i} = 0,那么整个排列对行列式无贡献。

因此要想对行列式有贡献,pnp_n 必等于 nn,同理得 i,pi=i\forall i, p_i = i\square

求解

显然有 O(n!n)\mathrm O(n! n) 的 naive 方法,但如果这样上面的 LaTeX\LaTeX 就白写了(

考虑把矩阵转化为上三角矩阵并由 Lemma 7 O(n)\mathrm O(n) 计算行列式。

这个过程形如高斯消元,于是考虑用高斯消元法来求解行列式。

假设目前处理到第 ii 行,要使得 j>i,aj,i=0\forall j > i, a_{j,i} = 0

显然可以让第 jj 行加上第 ii 行乘 ai,jai,i- \frac{a_{i,j}}{a_{i,i}},但对于任意模数情况下 ai,ia_{i,i} 不一定有逆元。

因此,我们考虑用辗转相除法。

每次使得 aj,iaj,imodai,ia_{j,i} \gets a_{j,i} \bmod a_{i,i},并交换第 ii 行与第 jj 行,直到 ai,ia_{i,i}00

即让第 jj 行加上第 ii 行乘 ai,jai,i- \lfloor \frac{a_{i,j}}{a_{i,i}} \rfloor

时间复杂度看似是 O(n3logP)\mathrm O(n^3 \log P),但可以证明是 O(n3)\mathrm O(n^3),其中 PP 是模数。

参考代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int n,p,a[N + 2][N + 2];
int det() {
    int sgn=0;
    for(int i=1; i<=n; ++i)
        for(int j=i+1; j<=n; ++j) {
            while(a[i][i]) {
                ll d=a[j][i]/a[i][i];
                for(int k=1; k<=n; ++k)
                    a[j][k]=(a[j][k]-d*a[i][k]%p)%p;
                swap(a[i],a[j]);
                sgn^=1;
            }
            swap(a[i],a[j]);
            sgn^=1;
        }
    ll ans=sgn?-1:1;
    for(int i=1; i<=n; ++i) ans=ans*a[i][i]%p;
    return (ans+p)%p;
}

应用

  • 矩阵树定理