行列式

本文是作者自己对行列式的理解，不甚严谨，但希望有启发性，若有错漏，欢迎指出。

本文只讨论方阵。

行列式的定义和理解

$\det A$ 表示方阵 $A$ 的行列式。

其的全排列定义为

$$\det A = \sum_p (-1)^{\tau(p)} \prod_{i=1}^n A_{i,p_i}$$

其中 $p$ 为 $1$ 到 $n$ 的排列， $\tau(p)$ 为排列 $p$ 的逆序对个数。

（由于对于 $n$ 阶方阵，其考虑的是 $n$ 为的向量空间，由于对于 $4$ 维及以上空间，没有相应的词汇描述，故使用 $3$ 维空间的相关词汇描述，例如： $4$ 维 「长方体」的「体积」，各位读者可以感性理解。）

个人认为更好的理解是：一个方阵的行列式，是这个矩阵的列向量夹成的有向「体积」，或这个矩阵对应的线性变换前后一个任意的「体积」的后与前的比值。

行列式的特殊情况

考虑一些特殊情况。

单位矩阵

首先，单位矩阵 $I$ 的行列式 $\det I = 1$ 。

根据行列式的定义，只有当 $p = {1, 2, \cdots , n}$ 时， $\prod A_{i, p_i}$ 为对角线上的元素相乘，为 $1$ ，此时 $p$ 的逆序对个数为 $0$ ，而其他情况 $\prod A_{i, p_i} = 0$ ，所以 $\det I = 1$

这不难理解，相当于一个「边长」为 $1$ 的 「正方体」，其「体积」为 $1$ 。

对角矩阵

其次对于一个对角矩阵：

$$A = \text{diag}\{\lambda_1, \lambda_2, \lambda_3, \cdots \lambda_n \}$$

其的行列式为对角线上各数的乘积，同理当 $p = {1, 2, \cdots, n}$ 时，

$$\det A = \prod A_{i, i} = \lambda_1\lambda_2\cdots\lambda_n$$

也不难理解，考虑一个边长的 $\lambda_1, \lambda_2, \cdots ,\lambda_n$ 的「正方体」即可。

三角矩阵

继续推广到三角矩阵。

对于一个主对角线为 $\lambda_1, \lambda_2, \cdots, \lambda_n$ 的上三角矩阵 $A$ 来说，显然只有 $p = {1, 2, \cdots , n}$ 时，会对答案有贡献，故 $\det A = \prod_{i=1}^n \lambda_i$ 。

下三角矩阵同理。

为 0 的情况

考虑 $\det A$ 什么时候会为 $0$ 。

显然有一行或一列均为 $0$ 是 $\det A$ 为 $0$ 的充分情况。

考虑定义的式子，连乘必然包含每一列，而假如一列都是 $0$ ，显然每次都是 $0$ ，所以答案也是 $0$ 。

行同理。

行列式的部分性质

行列式和矩阵乘法

接下来将行列式和矩阵乘法结合起来：

$$\det (AB) = (\det A)(\det B)$$

至于证明，我不会，不过可以根据行列式的几何意义理解。

应用线性变换 $B$ 后，体积乘以 $\det B$ ，再应用线性变换 $A$ 体积再乘以 $\det A$ ，所以把线性变换 $B$ 和 $A$ 组合起来，应用线性变换 $AB$ ，体积乘以 $\det AB$ 。

或者对 $B$ 应用线性变换 $A$ ，原来的体积是 $\det A$ ，然后乘上 $\det B$ ，和得到的新体积 $\det (AB)$ 相等。

行列式和转置

考虑一个重要的性质：一个矩阵转置，行列式不变，即：

$$\det A = \det A^T$$

至于证明，我还是不会（太菜了），不过可以根据组合数组合数的定义感性理解一下，每一种排列都可以进行同样的「转置」操作，同时逆序对数不变。

这也可以说明为什么上三角矩阵和下三角矩阵的行列式情况相似。

这两个性质记下来即可，证明反倒不是那么重要。

行列式和初等变换

（这里只考虑初等行变换）

对于一个矩阵进行初等变换，相当于对其左乘初等矩阵，因此一个矩阵进行初等变换后的行列式等于原来的行列式乘上初等矩阵的行列式。

倍乘

倍乘矩阵是单位矩阵上某个数为 $k$ ：

$$D_i(k) = \text{diag}\{1, 1, \cdots, 1, k, 1, \cdots, 1\}$$

其主对角线上第 $i$ 个数为 $k$ ，对一个矩阵进行倍乘操作，就是将第 $i$ 行的数乘上 $k$ ，由于倍乘矩阵的行列式为 $k$ ，所以操作后行列式也乘上 $k$ 。

$$\det (AD_i(k)) = (\det A)(\det D_i(k)) = k \det A$$

倍加

倍加矩阵如下所示：（来自 oi-wiki）

$$T_{i, j}(k) = \begin{pmatrix} 1 & & & & & & \\ & \ddots & & & & & \\ & & 1 & \cdots & k & & \\ & & & \ddots & \vdots & & \\ & & & & 1 & & \\ & & & & & \ddots & \\ & & & & & & 1\\ \end{pmatrix}$$

其中 $(T_{i, j}(k))_{i, j} = k$ 。

倍加矩阵就是单位矩阵同时第 $i$ 行 $j$ 列为 $k$ ，倍加矩阵是三角矩阵，其行列式为 $1$ 。

进行倍加操作，就是把第 $j$ 列乘上 $k$ 加到第 $i$ 行，操作后行列式不变。

这里可以引出行列式的一个性质，即假如有一行（列）是另一行（列）的若干倍，那么其行列式为 $0$ 。

证明也很简单，假如矩阵 $A$ 满足 $A_{a, i} = kA_{b, i}$ ，那么把 $i$ 行加上 $-k$ 倍的 $j$ 行，第 $i$ 行全是 $0$ ，行列式为 $0$ ，可知原来的矩阵的行列式也为 $0$ 。

\because&A' \larr A (T_{i,j}(-k)) \\ \because& \det A' = (\det A)(\det T_{i, j}(-k)) = 0 \\ \therefore& \det A = 0

对换

对换操作可以由倍加和倍乘操作组合而成，其作用是调换两行（列），操作后行列式乘 $-1$ 。

设要调换的两行（列）为 $A$ 和 $B$ ，初始时为 $A_0$ 和 $B_0$ ，下面用表格展示如何操作。

操作	行列式
$A_0, B_0$	$1$
$A_1 \larr A_0 + B_0$	$1$
$B_1 \larr -2B_0$	$-2$
$B_2 \larr B_1 + 2A_0 = 2A_0$	$-2$
$B_3 \larr \frac 1 2 B_2 = A_0$	$-1$
$A_2 \larr A_1 - B_3 = B_0$	$-1$

如何求行列式

题目：luogu P7112 行列式求值

提交记录

由于倍加操作不改变行列式，所以可以多次应用倍加操作。

对于每一个 $i$ ：

$$i + 1\le j \le n,\ A_i = A_j - \frac {A_{j, i}}{A_{i, i}} A_i$$

这样可以将它化成上三角矩阵，然后把对角线上的数乘起来即可。

for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        auto d = mat[j][i] / mat[i][i];
        for (int k = i; k <= n; k++) {
            mat[j][k] = (mat[j][k] - d * mat[i][k] % mod + mod) % mod;
        }
    }
}

行列式的应用

据本人所知，在 OI 中，大概只有 Matrix Tree 定理 。