我也不知道为什么要学这个,不过线性代数相关的内容确实是计算机科学非常重要的知识。
关于行列式
前置芝士:[链接登录后可见]和[链接登录后可见]。
行列式的定义
行列式 (\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}。
我们有如下命题:
求值
我们回到刚才最后一行消元后的情况。运用第一个命题我们发现 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}。
这样就可以做了。
实现的时候有一些细节:
消元操作是 \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: