高斯消元求行列式

前言

我原在博客园上发表的这篇文章是阅读排行榜最高的一篇。然而，作为一个刚学竞赛的学生写的东西，它的质量实在堪忧。行列式又是一个及其重要、基础和困难的概念，无论对于大学数学还是高中竞赛。因此，我决定将这篇文章重新编辑，以便更好地帮助学习的人。

如果你想知道行列式是什么，强烈建议先去学习线性代数基础知识，了解什么是向量、矩阵、线性变换以及会用矩阵描述线性方程组，然后认真理解学习行列式的概念。千万不要从形式上（如计算）学习行列式，而是要先理解它。

由于概念部分较深入，本文不会对线性代数的基础知识做过多介绍，而是着重于行列式的计算。

行列式

定义

行列式（Determinant）是一个线性代数里的数学概念。它可以被看做是有向面积或体积的概念在一般的欧几里得空间中的推广。或者说，在 n 维欧几里得空间中，行列式描述的是一个线性变换对“体积”所造成的影响。

形式上讲，行列式是一个函数，接受一个矩阵作为输入，输出一个标量。对于一个\(n\times n\)的矩阵\(A\)，它的行列式的值记为：

\[\det(A)=\begin{vmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\a_{21} & a_{22} & \cdots & a_{2n}\\\vdots & \vdots & \ddots & \vdots\\a_{n1} & a_{n2} & \cdots & a_{nn}\end{vmatrix}\]

其中\(a_{ij}\)表示矩阵\(A\)的第\(i\)行第\(j\)列元素。

行列式的定义有很多种。以下是一个通过展开式的定义：

设 \(R\) 是交换环，\(A = (a_{i, j})\) 是 \(R\) 上的 \(n \times n\) 矩阵。则 \(A\) 的定义为 \[ \det (A) = \sum_{\sigma \in \mathfrak{S}_n} (-1)^{\sigma} \, a_{1, \sigma(1)} \cdots a_{n, \sigma(n)}, \] 其中 \(\mathfrak{S}_n\) 是 \(n\) 元置换群，\((-1)^\sigma\) 是 \(\sigma\) 的符号（偶置换为 \(+1\), 奇置换为 \(-1\)）。

仅从如上定义我们无法知道如何计算行列式。除了二阶、三阶行列式可以快速计算外，一般的行列式的计算需要借助于高斯消元法。该方法需要用到一些行列式的性质。

性质

1. 行列式与其转置行列式值相等。
2. 交换行列式的两行，行列式的值取相反数。
3. 行列式的某一行乘以一个数，行列式的值乘以这个数。
4. 行列式的某一行乘以一数加到另一行上，行列式不变。

以上结论都可以由其定义推出。

高斯消元法

高斯消元法（Gauss Elimination）是一种数值计算方法，它可以用来求解线性方程组和行列式。其基本思想是将矩阵化简为上三角矩阵，然后化为对角矩阵。化简的基本操作是将一行减去另一行乘以一个非零数，使得本行某一列的元素被消为 0。时间复杂度为 \(O(n^3)\)。

以下为数据为浮点数时的代码。若有模数，求逆元即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

double Gauss()
{
    double ans=1;
    for(int i=1;i<=n;i++){
        int x=0;
        for(int j=i;j<=n and !x;j++) if(a[j][i]) x=j;
        if(!x) return (void)puts("No Solution");
        if(a[i]!=a[x]) swap(a[i],a[x]),ans=-ans;
        for(int j=1;j<=n;j++) if(j!=i){
            double tmp=a[j][i]/a[i][i];
            for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*tmp;
        }
        ans*=a[i][i];
    }
    return ans;
}

若模数不为质数，也可以通过辗转相除法消元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

long long Gauss(int n){
    long long ans=1;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            while(a[j][i]){
                long long t=a[i][i]/a[j][i];
                for(int k=i;k<=n;k++) a[i][k]=(a[i][k]-t*a[j][k]%mod+mod)%mod;
                swap(a[i],a[j]);
                ans=-ans;
            }
        }
        ans=(ans*a[i][i]%mod+mod)%mod;
    }
    return ans;
}