[Maths] 线性代数：行列式

reywmp

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

关于行列式

行列式的定义

行列式 (\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}
p 表示一个排列，所有可能的 p 则是 1 到 n 这 n 个数的全排列。\tau(p) 表示一个排列 p 的逆序对个数。

行列式可以理解为所有列向量所夹的几何体的有向体积，这样可以结合从几何直观出发理解为线性变换的伸缩因子。

~~不过，这些都不重要！~~ 在 OI 中，我们最应该了解的，是如何高效地求出一个矩阵的行列式然后去做题。至于其更深层次的数学意义，交给数学家们吧。

关于排列的奇偶性

我们发现 \tau(p) 的奇偶性对行列式求值起到了很大的影响，所以我们需要了解排列的奇偶性相关。

我们约定：如果 \tau(p) 为奇数，则 p 为一个奇排列，否则是一个偶排列；
对于一个 n(n\geq2) 阶排列的所有排列情况，奇排列与偶排列的情况各 \displaystyle \frac{1}{2}；
对于排列 p 我们交换其中的 2 个元素，其余元素不边，会得到一个新的排列，这种操作叫对换；
一次对换会改变排列的奇偶性；
一个排列可以通过若干次对换变成一个元素严格递增的自然排列，对换次数的奇偶性与原排列的奇偶性相同。

行列式的性质与定理

行列式有着一些有助于我们做题的性质。

行列式的不变性从体积的几何意义上理解非常直观，但是我们这里不做讨论。

交换对应矩阵的 2 行（列），行列式取反；[链接登录后可见]$
交换 1 行与 1 列（进行一次矩阵转置），行列式不变；[链接登录后可见]$

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

行列式的行（列）所有元素等比例变化，则行列式也等比例变化；[链接登录后可见]$
- \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)；[链接登录后可见]$
- \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；[链接登录后可见]$
- \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') ，我们通过 [链接登录后可见]$ 将 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；
把一个矩阵的一行（列）的值全部乘一个常数加到另一行（列）上，行列式值不变。[链接登录后可见]$
- \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\\ 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 的。运用定理 [链接登录后可见],(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}。

我们有如下命题：

n 阶行列式 D 等于其任意一行（列）所有元素与其对应代数余子式的乘积之和。
- 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])
n 阶行列式 D 的任意一行（列）余另不同的一行（列）对应元素的代数余子式之和为 0。
- \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}。

这样就可以做了。

实现的时候有一些细节：

每次取新的余子式的时候需要注意奇偶性，及时变化正负，因为记得代数余子式是要乘上一个 [链接登录后可见]^{(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：

\text{Zhaoyuhang2008} - [链接登录后可见]