「算法笔记」行列式

发表于 | | 阅读次数:
字数统计: 251 字
行列式的本质是线性变换的放大率。理解了这个物理意义，很多性质就迎刃而解了！

定义

我们定义一个矩阵 $A$ 的的行列式为 $\det(A)$，这个函数的结果是一个值。其本质是线性变换的放大率。

公式

其中 $\tau(P)$ 表示 $n$ 的一个排列 $P​$ 的逆序对数量。

性质

以下性质对于行和列同样适用！

性质 1：交换某两行，行列式变号

相当于每个全排列中，都有两个数被交换了位置。我们只需要证明交换两个数，逆序对变号即可。

设数字 $a​$ 和 $b​$ 将序列分为了三段：

改变顺序后第一段、第三段的逆序对数量不变。设第二段的长度为 $n​$，第二段中我们设：

那么交换之前的逆序对个数为 $x_1+y_2$，交换之后逆序对的个数为 $x_2+y_1\pm 1$（考虑 $a$ 和 $b$ 的逆序对贡献），我们分析其变化量：

因此逆序对的奇偶性改变，行列式变号。

性质 2：有两行完全相等，行列式为 0

我们可以通过性质 $1$ 来巧妙地证明：如果交换着两行，行列式变号。又由于矩阵没有任何变化，所以行列式又不变。故行列式为 $0$。

性质 3：某行每个元素乘以 / 除以 k，行列式也乘以 / 除以 k

把求和公式的每一项都提出一个 $k$ 或 $\frac{1}{k}$ 即可。

性质 4：某两行成比例，行列式为 0

我们可以把某一行提出一个比例系数 $k$，这样剩下的矩阵中有两行完全相同，那么行列式为 $0$。

性质 5：某行加上另一行的 k 倍，行列式不变

假设第 $i$ 行每个数增加了 $k\times A_{row,j}$，那么我们把这个增加项提出来，得到 $A_{i,j}$ 和 $k\times A_{row,j}$，那么第二个求和式子中有 $A_{row,j}$ 和 $k\times A_{row,j}$ 成比例，第二个式子的值为 $0$，行列式不变。

求解

可以证明，一个矩阵的行列式等于上三角矩阵的主对角线的乘积。

那么我们依据上面的性质，把矩阵 $A$ 通过高斯消元变成上三角矩阵，然后直接计算主对角线乘积即可！

但是，一般来讲我们不允许行列式计算过程中出现小数，而是对整数进行取模。那么我们就不能直接用高斯消元了，要使用辗转相除法的高斯消元，复杂度多了一个 $\log n$。

时间复杂度：$O(n^3\log n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <cstdio>
#include <algorithm>

const int N=305;
const int mod=1e9+7;
int n,a[N][N];

int Gauss(int n) {
    int ans=1;
    for(int i=1;i<=n;++i) {
        for(int k=i+1;k<=n;++k) {
            while(a[k][i]) {
                int d=a[i][i]/a[k][i];
                for(int j=i;j<=n;++j) a[i][j]=(a[i][j]-1LL*d*a[k][j]%mod+mod)%mod;
                std::swap(a[i],a[k]),ans=-ans;
            }
        }
        ans=1LL*ans*a[i][i]%mod,ans=(ans+mod)%mod;
    }
    return ans;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&a[i][j]);
    printf("%d\n",Gauss(n));
    return 0;
}

应用

说了这么多，这个行列式到底有什么用呢？

其实行列式在很多定理中广泛使用，最常见的就是 $\text{Matrix-Tree Theorem}$（矩阵树定理）了，具体证明及实现详见「算法笔记」矩阵树定理。

0%