定义
我们定义一个矩阵 $A$ 的的行列式为 $\det(A)$,这个函数的结果是一个值。其本质是线性变换的放大率。
公式
$$ \det(A)=\sum_{\forall P}[(-1)^{\tau(P)}\prod_{i=1}^n A_{i,P_i}] $$
其中 $\tau(P)$ 表示 $n$ 的一个排列 $P$ 的逆序对数量。
性质
以下性质对于行和列同样适用!
性质 1:交换某两行,行列式变号
相当于每个全排列中,都有两个数被交换了位置。我们只需要证明交换两个数,逆序对变号即可。
设数字 $a$ 和 $b$ 将序列分为了三段:
$$ \{\text{第一段}\quad a\quad\text{第二段}\quad b\quad\text{第三段}\} $$
改变顺序后第一段、第三段的逆序对数量不变。设第二段的长度为 $n$,第二段中我们设:
$$ x_1\ \text{个元素} < a < y_1\ \text{个元素} \\ x_2\ \text{个元素} < b < y_2\ \text{个元素} $$
那么交换之前的逆序对个数为 $x_1+y_2$,交换之后逆序对的个数为 $x_2+y_1\pm 1$(考虑 $a$ 和 $b$ 的逆序对贡献),我们分析其变化量:
$$ \begin{aligned} \Delta&=(x_2+y_1)-(x_1+y_2\pm 1) \\ &=(x_2+n-x_1)-(x_1+n-x_2\pm 1) \\ &=2x_2\pm 1 \end{aligned} $$
因此逆序对的奇偶性改变,行列式变号。
性质 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$。
时间复杂度:$\mathcal O(n^3\log n)$
代码
#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 = mod - ans;
}
}
ans = 1LL * ans * a[i][i] % 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}$(矩阵树定理)了,具体证明及实现详见「算法笔记」矩阵树定理。