数学(5)——线性代数：行列式

Reywmp · 2021-03-21 16:42:07 · 题解

~~我也不知道为什么要学这个~~，不过线性代数相关的内容确实是计算机科学非常重要的知识。

关于行列式

前置芝士：矩阵和高斯消元。

行列式的定义

行列式 (\texttt{Determinant}) 是一个函数定义，取值是一个标量。

对一个 n\times n 的矩阵 A（n 阶方阵），其 n 阶行列式写作 \det(A) 或者 |A|，定义为：

\det(A)=|A|=\sum_p(-1)^{\tau(p)}\prod_{i=1}^n a_{i,p_i}

行列式可以理解为所有列向量所夹的几何体的有向体积，这样可以结合从几何直观出发理解为线性变换的伸缩因子。 ~~不过，这些都不重要！~~ 在 OI 中，我们最应该了解的，是如何高效地求出一个矩阵的行列式然后去做题。至于其更深层次的数学意义，交给数学家们吧。 --------------- ## 关于排列的奇偶性我们发现 $\tau(p)$ 的奇偶性对行列式求值起到了很大的影响，所以我们需要了解排列的奇偶性相关。 - 我们约定：如果 $\tau(p)$ 为奇数，则 $p$ 为一个奇排列，否则是一个偶排列； - 对于一个 $n(n\geq2)$ 阶排列的所有排列情况，奇排列与偶排列的情况各 $\displaystyle \frac{1}{2}$； - 对于排列 $p$ 我们交换其中的 $2$ 个元素，其余元素不边，会得到一个新的排列，这种操作叫**对换**； - 一次对换会改变排列的奇偶性； - 一个排列可以通过若干次对换变成一个元素严格递增的**自然排列**，对换次数的奇偶性与原排列的奇偶性相同。 ----------- ## 行列式的性质与定理行列式有着一些有助于我们做题的性质。行列式的不变性从体积的几何意义上理解非常直观，但是我们这里不做讨论。 - 交换对应矩阵的 $2$ 行（列），行列式取反；$(1)

交换 1 行与 1 列（进行一次矩阵转置），行列式不变；(2)

这两个性质的证明，可以考虑结合排列的奇偶性，然后直接重新带入公式观察。

行列式的行（列）所有元素等比例变化，则行列式也等比例变化；(3)
- \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ k\times a_{i,1} &k\times a_{i,2} &\cdots &k\times a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} =k\times \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix}
如果行列式对应矩阵 A 中有一行（列），是对应 2 个矩阵 B,C 中分别的 2 行（列）所有元素之和。那么有 \det(A)=\det(B)+\det(C)；(4)
- \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ b_{i,1}+c_{i,1} &b_{i,2}+c_{i,2} &\cdots &b_{i,n}+c_{i,n}\\ \vdots &\vdots &\ddots &\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 &\ddots &\vdots\\ b_{i,1} &b_{i,2} &\cdots &b_{i,n}\\ \vdots &\vdots &\ddots &\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 &\ddots &\vdots\ c{i,1} &c{i,2} &\cdots &c{i,n}\ \vdots &\vdots &\ddots &\vdots\ a{n,1}&a{n,2}&\cdots&a{n,n}\ \end{vmatrix}
如果一个矩阵存在两行（列）成比例则 \det(A)=0；(5)
- \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ k\times a_{i,1} &k\times a_{i,2} &\cdots &k\times a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix}=0
- 这个证明可以直接代，但也有巧妙的办法：我们可以通过交换有比例关系的这两行得到新的矩阵 A' k\times a_{i,1}, k\times a_{i,2}, \cdots ,k\times a_{i,n} 现在就在上面的位置，一次交换使得 \det(A)=-\det(A') ，我们通过 (3) 将 k 的比例变化放到行列式前，也就是 A,A' 的 k\times a_{i,1} k\times a_{i,2} \cdots k\times a_{i,n} 一行（列）变成 a_{i,1},a_{i,2} \cdots ,a_{i,n}，得到的新的矩阵分别是 A'',A''' 我们发现 A''=A''' 又有 k\times |A''|=|A|=-k\times |A'''|=-|A'|，一个数等于其相反数，所以有 |A|=0；
把一个矩阵的一行（列）的值全部乘一个常数加到另一行（列）上，行列式值不变。(6)
- \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1}+k\times a_{i,1} &a_{j,2}+k\times a_{i,2} &\cdots &a_{j,2}+k\times a_{i,n}\\ \vdots &\vdots &\ddots &\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 &\ddots &\vdots\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1} &a_{j,2} &\cdots &a_{j,2}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix}
- 证明也很简单，根据 (4) 有：
- \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1}+k\times a_{i,1} &a_{j,2}+k\times a_{i,2} &\cdots &a_{j,2}+k\times a_{i,n}\\ \vdots &\vdots &\ddots &\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 &\ddots &\vdots\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1} &a_{j,2} &\cdots &a_{j,2}\\ \vdots &\vdots &\ddots &\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 &\ddots &\vdots\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ k\times a_{i,1} &k\times a_{i,2} &\cdots &k\times a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix}
- \because (5)
- \therefore \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1}+k\times a_{i,1} &a_{j,2}+k\times a_{i,2} &\cdots &a_{j,2}+k\times a_{i,n}\\ \vdots &\vdots &\ddots &\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 &\ddots &\vdots\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1} &a_{j,2} &\cdots &a_{j,2}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix}+0

行列式求值

那么知道了行列式这样一些性质，怎样在 OI 中高效地去求行列式呢。

直接根据定义计算，行列式求值是 \Theta(n\times n!) 的。显然太高了。

有上面这些性质我们怎么该将问题简化呢。

消元

我们考虑一个情况，当一个矩阵任意一个位置出现 0，其对行列式的影响非常大。

因为我们考虑公式中 \displaystyle\prod_{i=1}^n a_{i,p_i} 一项，一旦选到 0 整个 p 在 \displaystyle \sum_p 中就没有贡献了。

我们利用上面的一些性质显然是可以让矩阵不断变化出现 0 的。运用定理 (1),(3),(4) 就可以做到。

显然瞎转化肯定是不行的，我们要让运算次数尽可能少。

如果学习了前置知识。我们知道求解线性方程组的算法高斯消元。其实高斯消元在做增广矩阵行（初等）变换为行最简形时的步骤和我们的转化有异曲同工之妙。

我们现在考虑将矩阵一行（列）消成只有最后一个元素非 0 该怎么做。也就是说：

A=\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \cdots &a_{1,n}\\ a_{2,1} & a_{2,2} & a_{2,3} & \cdots &a_{2,n}\\ a_{3,1} & a_{3,2} & a_{3,3} & \cdots &a_{3,n}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a_{n,1} & a_{n,2} & a_{n,3} & \cdots &a_{n,n}\\ \end{bmatrix}\Rightarrow \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \cdots &a_{1,n}\\ a_{2,1} & a_{2,2} & a_{2,3} & \cdots &a_{2,n}\\ a_{3,1} & a_{3,2} & a_{3,3} & \cdots &a_{3,n}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots &a_{n,n}\\ \end{bmatrix}

对于 1 到第 n-1 列中的第 i 列，我们只需要让第 i 列整列加上第 n 列的 \displaystyle-\frac{a_{n,i}}{a_{n,n}} 倍就可以在 \det(A) 不变的情况下使得整行前 n-1 个元素被消掉。

代数余子式求值

消元有什么用呢，我们引入线性代数中帮助我们求行列式的一个概念——代数余子式。

在一个 n 阶行列式 D 中选定 k 行 k 列可以组成一个 k 阶子行列式 A；

删除在 k 行 k 列后剩下的 n-k 阶行列式称为 A 对应的 n-k 阶余子式 M。

设 A 在 D 中原来的元素行下标有集合 \mathbb I=\{i_1,i_2 ,\dots ,i_k\} 列下标有集合 \mathbb J=\{j_1,j_2 ,\dots ,j_k\}，则有 \displaystyle(-1)^{\displaystyle(i_1+i_2+\dots+i_k)(j_1+j_2+\dots+j_k)}\times \det(M) 为 n 阶行列式 D 的 k 阶子式 A 的代数余子式。

对于单一元素 a_{i,j} 我们令其代数余子式为 A_{i,j} ，余子式为 M_{i,j} 。有 A_{i,j}=(-1)^{i+j}M_{i,j}。

我们有如下命题：

- $$ D=\sum_{j=1}^na_{i,j}\times A_{i,j},(i\in[1,n]) $$ - $$ D=\sum_{i=1}^na_{i,j}\times A_{i,j},(j\in[1,n]) $$
- $$ \sum_{k=1}^na_{i,k}\times A_{j,k}=0,(i,j\in[1,n],i\neq j) $$ - $$ \sum_{k=1}^na_{k,i}\times A_{k,j}=0,(i,j\in[1,n],i\neq j) $$

求值

我们回到刚才最后一行消元后的情况。运用第一个命题我们发现 D 的值只是 a_{n,n}\times A_{n,n}。这个时候如果我们继续对 A_{n,n} 做同样的消元呢？

\begin{vmatrix} \color{red}a_{1,1} & \color{red}a_{1,2} & \color{red}a_{1,3} & \color{red}\cdots &\color{red}a_{1,n-1} &a_{1,n}\\ \color{red}a_{2,1} & \color{red}a_{2,2} & \color{red}a_{2,3} & \color{red}\cdots &\color{red}a_{2,n-1} &a_{2,n}\\ \color{red}a_{3,1} &\color{red} a_{3,2} &\color{red} a_{3,3} &\color{red} \cdots &\color{red}a_{3,n-1} &a_{3,n}\\ \color{red}\vdots & \color{red}\vdots & \color{red}\vdots & \color{red}\ddots &\color{red} \vdots &\vdots\\ \color{red}a_{n-1,1} &\color{red} a_{n-1,2} & \color{red}a_{n-1,3} & \color{red}\cdots &\color{red}a_{n-1,n-1} &a_{n,n-1}\\ a_{n,1} & a_{n,2} & a_{n,3} & \cdots &a_{n,n-1} &a_{n,n}\\ \end{vmatrix}

也就是说如果对于这个 n-1 阶的红色余子式继续做消元使得其变成：

\begin{vmatrix} \color{red}a_{1,1} & \color{red}a_{1,2} & \color{red}a_{1,3} & \color{red}\cdots &\color{red}a_{1,n-1} \\ \color{red}a_{2,1} & \color{red}a_{2,2} & \color{red}a_{2,3} & \color{red}\cdots &\color{red}a_{2,n-1}\\ \color{red}a_{3,1} &\color{red} a_{3,2} &\color{red} a_{3,3} &\color{red} \cdots &\color{red}a_{3,n-1} \\ \color{red}\vdots & \color{red}\vdots & \color{red}\vdots & \color{red}\ddots &\color{red} \vdots \\ 0 & 0 & 0 & \color{red}\cdots &\color{red}a_{n-1,n-1}\\ \end{vmatrix}

我们发现之前余子式 A_{n,n} 又只等于 a_{n-1,n-1}\times A_{n-1,n-1}。

以此类推，如果我们一直：

对当前行列式消元
取最末（右下角）位的指和其余子式，余子式作为新行列式重新做；

\begin{vmatrix} \color{orange}a_{1,1} & \color{green}a_{1,2} & \color{blue}a_{1,3} & \color{red}\cdots &\color{red}a_{1,n-1} &a_{1,n}\\ \color{green}a_{2,1} & \color{green}a_{2,2} & \color{blue}a_{2,3} & \color{red}\cdots &\color{red}a_{2,n-1} &a_{2,n}\\ \color{blue}a_{3,1} &\color{blue} a_{3,2} &\color{blue} a_{3,3} &\color{red} \cdots &\color{red}a_{3,n-1} &a_{3,n}\\ \color{red}\vdots & \color{red}\vdots & \color{red}\vdots & \color{red}\ddots &\color{red} \vdots &\vdots\\ \color{red}a_{n-1,1} &\color{red} a_{n-1,2} & \color{red}a_{n-1,3} & \color{red}\cdots &\color{red}a_{n-1,n-1} &a_{n,n-1}\\ a_{n,1} & a_{n,2} & a_{n,3} & \cdots &a_{n,n-1} &a_{n,n}\\ \end{vmatrix}

按不同颜色一直递归下去做，我们发现最后我们得到

\begin{vmatrix} \color{orange}a_{1,1} & \color{green}a_{1,2} & \color{blue}a_{1,3} & \color{red}\cdots &\color{red}a_{1,n-1} &a_{1,n}\\ 0 & \color{green}a_{2,2} & \color{blue}a_{2,3} & \color{red}\cdots &\color{red}a_{2,n-1} &a_{2,n}\\ 0 &0 &\color{blue} a_{3,3} &\color{red} \cdots &\color{red}a_{3,n-1} &a_{3,n}\\ \color{red}\vdots & \color{red}\vdots & \color{red}\vdots & \color{red}\ddots &\color{red} \vdots &\vdots\\ 0 &0 & 0 & \color{red}\cdots &\color{red}a_{n-1,n-1} &a_{n,n-1}\\ 0 & 0 & 0 & \cdots &0 &a_{n,n}\\ \end{vmatrix}

这样的一个下三角行列式。

我们就会发现这样一个矩阵的行列式是其对角线所有元素的乘积，也就是 \displaystyle\prod_{i=1}^na_{i,i}。

这样就可以做了。

实现的时候有一些细节：

每次取新的余子式的时候需要注意奇偶性，及时变化正负，因为记得代数余子式是要乘上一个 (-1)^{(i_1+i_2+\dots+i_k)(j_1+j_2+\dots+j_k)} 的；
如果题目要求 \bmod p 情况下的行列式，有些数是不一定有逆元的，或者说消元的时候精度出问题，我们可以考虑对两行（列）做辗转相减消元。
- \begin{bmatrix} 10 & a_{1,2} & a_{1,3} & \cdots &a_{1,n}\\ 4 & a_{2,2} & a_{2,3} & \cdots &a_{2,n}\\ a_{3,1} & a_{3,2} & a_{3,3} & \cdots &a_{3,n}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a_{n,1} & a_{n,2} & a_{n,3} & \cdots &a_{n,n}\\ \end{bmatrix}
- 对于这样的情况，求 a_{1,1}=a_{1,1}\bmod a_{2,1}
- 有 \begin{bmatrix}2\\4\\\end{bmatrix}（我们现在只考虑这两个位置）
- swap(a[1][1],a[2][1])
- 有 \begin{bmatrix}4\\2\\\end{bmatrix}
- 再做 a_{1,1}=a_{1,1}\bmod a_{2,1}
- 有 \begin{bmatrix}0\\2\\\end{bmatrix}
- swap(a[1][1],a[2][1])
- 有 \begin{bmatrix}2\\0\\\end{bmatrix}
- 这样分别解决了精度，逆元的一些问题。

消元操作是 \Theta(n^3) 的，辗转相除法是 \Theta(\log p) 的，因为辗转相除和消元每次必然使得数变小，势能只会减少，所以这个是均摊到 \Theta(n^2) 的，最终有复杂度 \Theta(n^2\log n+n^3)。

代码

#include<bits/stdc++.h>

#define INL inline
#define ll long long 

using namespace std;

const int N=605;

int n,a[N][N],MOD;

INL int read()
{
    int x=0,w=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();
    return x*w;
}

INL int sol()
{
    int res=1,w=1;
    for(int i=1;i<=n;i++)
    { 
        for(int j=i+1;j<=n;++j)
        {
            while(a[i][i])
            {
                int div=a[j][i]/a[i][i];
                for(int k=i;k<=n;++k)
                {
                    a[j][k]=(a[j][k]-1ll*div*a[i][k]%MOD+MOD)%MOD;
                }
                swap(a[i],a[j]);w=-w;
            }//对第 i 行和第 j 行做辗转相减。   
            swap(a[i],a[j]);w=-w;
        }
    }
    for(int i=1;i<=n;i++)res=1ll*a[i][i]*res%MOD;
    res=1ll*w*res;
    return (res+MOD)%MOD;//经 典 模 加 模
}

int main()
{
    n=read(),MOD=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=read();
    int ans=sol();printf("%d\n",ans);
    return 0;
}

\text{Determinant}\texttt{——2021.03.21} \text{写在机房}

Reference：