行列式
逆序数
定义 \(p\) 为一个长度为 \(n\) 的排列，\(p_i\) 为这个排列的第 \(i\) 项。定义 \(\pi(p)\) 为排列 \(p\) 的逆序对数。若一个排列的逆序对数为奇数，则称这个排列是一个奇排列；若一个排列的逆序对数为偶数，则称这个排列是一个偶排列。
结论 1
交换排列 \(p\) 中的任意两项，排列 \(p\) 的奇偶性改变。
证明
假设交换后的排列为 \(p'\)，交换的两项为 \(i, j\) 且 \(i < j\)。如果 \(p_i < p_j\)，那么 \(\pi(p') = \pi(p) + 1\)；如果 \(p_i > p_j\)，那么 \(\pi(p') = \pi(p) - 1\)。因此奇偶性改变。
结论 2
若对排列 \((1, 2, \cdots, n)\) 进行若干次交换得到排列 \(p\)，那么交换次数的奇偶性与排列 \(p\) 的奇偶性相同。
证明
排列 \((1, 2, \cdots, n)\) 的逆序数是 \(0\)，因此是一个偶排列，同时交换次数也是 \(0\)。每对其中两个数进行交换，都会改变排列的奇偶性，同时也改变交换次数的奇偶性，因此结论成立。
定义
对于一个 \(n\) 阶方阵 \(A\)，定义 \(A\) 的行列式为 \(\det A\)：
\[
\det A = \det
\begin{pmatrix}
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{pmatrix}
= \sum_{p} (-1)^{\pi(p)} \prod_{j = 1}^n a_{j, p_j} \\
\]
其中，\(\sum_p\) 表示枚举全排列。
性质
性质 1
一个方阵的行列式和其转置的行列式相等，即 \(\det A = \det A^T\)。
证明
对于一个排列 \(p\)，我们需要找到一个排列 \(p'\)，使得若 \(i = p'_j\)，那么有 \(j = p_i\)，此时有 \(a_{i, p_i} = a_{p'_j, j}\)，因此 \(\prod_{i = 1}^n a_{i, p_i} = \prod_{i = 1}^n a_{p'_i, i}\)。这个 \(p'\) 可以通过交换 \(a\) 的顺序得到。我们将下标看成一个二元组，排列 \(p\) 对应的下标为 \((i, p_i)\)，\(p'\) 对应 \((p'_i, i)\)，我们按第二个值排序（冒泡排序），相当于将第二个值交换得到排列 \((1, 2, \cdots, n)\)，交换次数的奇偶性与 \(p\) 的奇偶性相同。此时， 第一个值相当于从排列 \((1, 2, \cdots, n)\) 交换得到排列 \(p'\)，因此交换次数的奇偶性与 \(p'\) 的奇偶性相同。容易看出 \(p\) 与 \(p'\) 奇偶性相同，前面的系数 \((-1)^{\pi(p)} = (-1)^{\pi(p')}\)。同时，因为这是个排序过程，不同的排列 \(p, q\) 一定会有与之对应的 \(p', q'\)，同时它们也互不相同，因此有：
\[
\sum_{p} (-1)^{\pi(p)} \prod_{j = 1}^n a_{j, p_j} = \sum_{p} (-1)^{\pi(p)} \prod_{j = 1}^n a_{p_j, j} \\
\]
注意到等号右边即为转置矩阵的行列式，因此结论成立。
注意
接下来的性质对于行和列都成立，但只证明行的情况，列的情况可以由转置矩阵的行列式得到。
性质 2
若一个方阵的一行（列）全为 \(0\)，那么行列式为 \(0\)，即：
\[
\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix}
= 0 \\
\]
证明
\[
\begin{aligned}
&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=& \sum_{p} (-1)^{\pi(p)} \left(\prod_{j = 1}^{m - 1} a_{j, p_j} \right) k \times 0 \times \left(\prod_{j = m + 1}^n a_{j, p_j} \right) \\
=& 0 \\
\end{aligned}
\]
性质 3
一个方阵的一行（列）若乘上 \(k\)，那么行列式的值也乘 \(k\)，即：
\[
\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
k a_{m, 1} & k a_{m, 2} & k a_{m, 3} & \cdots & k a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix}
= k \det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
\]
证明
\[
\begin{aligned}
&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
k a_{m, 1} & k a_{m, 2} & k a_{m, 3} & \cdots & k a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=& \sum_{p} (-1)^{\pi(p)} \left(\prod_{j = 1}^{m - 1} a_{j, p_j} \right) k a_{m, p_m} \left(\prod_{j = m + 1}^n a_{j, p_j} \right) \\
=& k \sum_{p} (-1)^{\pi(p)} \left(\prod_{j = 1}^{m - 1} a_{j, p_j} \right) a_{m, p_m} \left(\prod_{j = m + 1}^n a_{j, p_j} \right) \\
=& k \det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
\end{aligned}
\]
性质 4
我不知道怎么描述这个性质
\[
\begin{aligned}
&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} + b_1 & a_{m, 2} + b_2 & a_{m, 3} + b_3 & \cdots & a_{m, n} + b_n \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=& \det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix}
+ \det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
b_1 & b_2 & b_3 & \cdots & b_n \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
\end{aligned}
\]
证明
\[
\begin{aligned}
&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} + b_1 & a_{m, 2} + b_2 & a_{m, 3} + b_3 & \cdots & a_{m, n} + b_n \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=& \sum_{p} (-1)^{\pi(p)} \left(\prod_{j = 1}^{m - 1} a_{j, p_j} \right) (a_{m, p_m} + b_{p_m}) \left(\prod_{j = m + 1}^n a_{j, p_j} \right) \\
=& \sum_{p} (-1)^{\pi(p)} \left(\prod_{j = 1}^{m - 1} a_{j, p_j} \right) a_{m, p_m} \left(\prod_{j = m + 1}^n a_{j, p_j} \right) + \sum_{p} (-1)^{\pi(p)} \left(\prod_{j = 1}^m a_{j, p_j} \right) b_{p_m} \left(\prod_{j = m + 1}^n a_{j, p_j} \right) \\
=& \det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix}
+ \det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
b_1 & b_2 & b_3 & \cdots & b_n \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
\end{aligned}
\]
性质 5
交换任意两行（列），行列式变为原来的相反数，即：
\[
\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{q, 1} & a_{q, 2} & a_{q, 3} & \cdots & a_{q, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix}
= -\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{q, 1} & a_{q, 2} & a_{q, 3} & \cdots & a_{q, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
\]
证明
\[
\begin{aligned}
&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{q, 1} & a_{q, 2} & a_{q, 3} & \cdots & a_{q, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=& \sum_{p} (-1)^{\pi(p)} \prod_{j = 1}^n a_{j, p_j} \\
\end{aligned}
\]
假设排列 \(p' = (p_1, \cdots, p_q, \cdots, p_m, \cdots p_n)\)，可以看出，\(p'\) 是通过在 \(p\) 中交换两个元素的位置得到的，因此 \(p'\) 的奇偶性与 \(p\) 相反。同时，因此有：
\[
\begin{aligned}
& \sum_{p} (-1)^{\pi(p)} \prod_{j = 1}^n a_{j, p_j} \\
=& -\sum_{p'} (-1)^{\pi(p')} \prod_{j = 1}^n a_{j, p'_j} \\
=& -\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{q, 1} & a_{q, 2} & a_{q, 3} & \cdots & a_{q, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
\end{aligned}
\]
性质 6
若方阵的其中一行（列）是另一行（列）的 \(k\) 倍，那么行列式为 \(0\)，即：
\[
\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
k a_{m, 1} & k a_{m, 2} & k a_{m, 3} & \cdots & k a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
= 0 \\
\]
证明
首先考虑 \(k = 1\) 的情况。交换这两行，行列式变为相反数，但矩阵的形式不变，即：
\[
\begin{aligned}
&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=&-\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
\end{aligned}
\]
因此：
\[
\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
= 0 \\
\]
对于 \(k \ne 1\) 的情况，有：
\[
\begin{aligned}
&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
k a_{m, 1} & k a_{m, 2} & k a_{m, 3} & \cdots & k a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=&k \det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=& 0 \\
\end{aligned}
\]
性质 7
一个方阵的一行（列）加上另一行（列）的若干倍，行列式的值不变，即：
\[
\begin{aligned}
&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{q, 1} + k a_{m, 1} & a_{q, 2} + k a_{m, 2} & a_{q, 3} + k a_{m, 3} & \cdots & a_{q, n} + k a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{q, 1} & a_{q, 2} & a_{q, 3} & \cdots & a_{q, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix}
\end{aligned}
\]
证明
由性质 4 和性质 6，有：
\[
\begin{aligned}
&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{q, 1} + k a_{m, 1} & a_{q, 2} + k a_{m, 2} & a_{q, 3} + k a_{m, 3} & \cdots & a_{q, n} + k a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{q, 1} & a_{q, 2} & a_{q, 3} & \cdots & a_{q, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix}
+ \det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
k a_{m, 1} & k a_{m, 2} & k a_{m, 3} & \cdots & k a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix} \\
=&\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m, 1} & a_{m, 2} & a_{m, 3} & \cdots & a_{m, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{q, 1} & a_{q, 2} & a_{q, 3} & \cdots & a_{q, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n, 1} & a_{n, 2} & a_{n, 3} & \cdots & a_{n, n} \\
\end{pmatrix}
\end{aligned}
\]
性质 8
上三角矩阵的行列式为对角线元素的乘积，即：
\[
\det
\begin{pmatrix}
a_{1, 1} & a_{1, 2} & a_{1, 3} & \cdots & a_{1, n} \\
0 & a_{2, 2} & a_{2, 3} & \cdots & a_{2, n} \\
0 & 0 & a_{3, 3} & \cdots & a_{3, n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & a_{n, n} \\
\end{pmatrix}
= \prod_{i = 1}^n a_{i, i} \\
\]
证明
在枚举全排列 \(p\) 时，如果要使 \(a_{1, p_1}\) 不为 \(0\)，那么 \(p_1 = 1\)；如果要使 \(a_{2, p_2}\) 也不为 \(0\)，因为 \(1\) 已经被使用，因此 \(p_2 = 2\)；以此类推，可以发现如果要使 \(\prod_{i = 1}^n a_{i, p_i} \ne 0\)，那么一定有 \(p_i = i\)。也就是说，只有这一种排列对应的乘积是不为 \(0\) 的，因此行列式的值就是这种排列对应的乘积，即对角线元素的乘积。
高斯消元
用定义求行列式的值需要枚举全排列，复杂度过高，因此考虑使用高斯消元将矩阵消成上三角矩阵来求。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | int det(vector<int> num[]) {
int ans = 1;
for (int i = 1; i <= n; i++) {
int pos = i;
while (!num[pos][i] && pos <= n)
++pos;
if (pos > n)
return 0;
if (pos != i)
swap(num[pos], num[i]), ans = dec(0, ans);
for (int j = i + 1; j <= n; j++) {
int tmp = mul(num[j][i], inv(num[i][i]));
for (int l = i; l <= n; l++)
num[j][l] = dec(num[j][l], mul(tmp, num[i][l]));
}
ans = mul(ans, num[i][i]);
}
return ans;
}
|
如果模数不是质数，那么模意义下的逆元不一定存在，我们需要使用辗转相除法代替求逆元：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | int det(vector<int> num[]) {
int ans = 1;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j)
while (num[j][i]) {
int tmp = num[i][i] / num[j][i];
if (tmp)
for (int k = i; k <= n; ++k)
num[i][k] = dec(num[i][k], mul(tmp, num[j][k]));
swap(num[i], num[j]), ans = dec(0, ans);
}
ans = mul(ans, num[i][i]);
if (!ans)
return 0;
}
return ans;
}
|
因为辗转相除的复杂度是 \(\log m\)，其中 \(m\) 为模数（即数的值域）。乍一看这个东西的时间复杂度是 \(O(n^3\log m)\)，但实际上它的复杂度为 \(O(n^2\log m + n^3)\)
时间复杂度证明
先考虑这样一个问题：
奇妙的问题
给定 \(n\) 个数，求它们的 \(\gcd\)。
考虑一个朴素的辗转相除法：
| ans = num[1];
for (int i = 2; i <= n; ++i)
ans = gcd(ans, num[i]);
|
若所有数都小于等于 \(m\)，那么这个算法的时间复杂度是 \(O(n \log m)\) 吗？当然不是，应该是 \(O(n + \log m)\)。
假设当前求出前 \(k\) 个数的 \(\gcd\) 为 \(d\)，在求 \(\gcd(d, a_{k + 1})\) 时，只需常数次除法就能将 \(a_{k + 1}\) 除成一个小于 \(d\) 的数，这样，我们就继续了之前的辗转相除。因此，除了每个数进行的常数次除法之外，剩下的除法次数就是 \(O(\log m)\)，也就是说，整个过程的时间复杂度就是 \(O(n + \log m)\)。
回到高斯消元这里，第 \(4 \sim 11\) 行代码是辗转相除的部分，根据上面的结论，这一层 while 循环的总数也就是 \(O(n + \log m)\)，因为第 \(3, 8\) 行各有一个循环 \(n\) 次的 for 循环，因此总时间复杂度为 \(O(n^2 \log m + n^3)\)。
行列式与体积
如果我们将行列式的每一行看作一个向量，那么 \(n\) 个向量 \(v_1, v_2, \cdots, v_n\) 所围成的一个 \(n\) 维立方体（一个有 \(2^n\) 个顶点的立方体，其中每个顶点都是若干个向量加和的端点）即为矩阵行列式的绝对值。
关于体积的求法，我们任选一个向量 \(v'_1\)，然后进行 \(n - 1\) 次操作，第 \(k\) 次操作选出一个向量 \(v'_{k + 1}\)，作它与前 \(k\) 个向量构成的 \(k\) 维空间的法向量，这样其实就是做了高，然后再用 \(k\) 维立方体的体积乘这个法向量的模长。
对于体积，我们有如下性质：
性质 2
若一个向量的每一维坐标都是 \(0\)，那么体积也为 \(0\)。
证明
这个向量无论对哪个空间作法向量，模长都是 \(0\)，因此体积为 \(0\)。
性质 3
若一个向量的每一维坐标变为原来的 \(k\) 倍，则体积变为原来的 \(k\) 倍。
证明
如果把这个向量作为 \(v_1\)，那么这个一维立方体的体积变为原来的 \(k\) 倍，因此体积变为原来 \(k\) 倍。
证明
交换两个向量的顺序后，我们仍然可以按照原来选择的顺序求体积，因此体积不变。
性质 6
若一个向量是另一个向量的若干倍，体积为 \(0\)。
证明
我们选择这两个向量作为 \(v'_1, v'_2\)，可以发现这两个向量共线，它们所构成二维立方体的体积（也就是平行四边形的面积）为 \(0\)，因此体积为 \(0\)。
性质 7
将一个向量加上另一个向量的若干倍，体积不变。
证明
我们选择这两个向量作为 \(v'_1, v'_2\)，我们发现，若将 \(v'_1\) 加上 \(kv'_2\)，这两个向量构成的平行四边形只是被拉伸了，高（即 \(v'_2\) 对 \(v'_1 + kv'_2\) 做的垂线的模长）不变，因此加之前和之后这个平行四边形面积不变。因此体积不变。
性质 8
对角矩阵对应的立方体体积为对角线上元素乘积的绝对值（也就是这个矩阵的行列式的绝对值）。
证明
可以看出这些向量两两垂直，因此体积就是所有向量模长的乘积，也就是矩阵对角线上元素乘积的绝对值。
可以看出，我们将一些体积的性质与行列式的性质对应起来了，我们可以利用性质 7 对这个立方体进行消元，这样能够得到一个两两垂直的向量组，再利用性质 8 即可算出立方体的体积。这个过程对应在矩阵中即为高斯消元，因此我们可以说体积就是矩阵行列式的绝对值了。
有了这个结论，我们可以在体积上推导出性质 1 和 4：
性质 1
若将向量组 \(v\) 中每一个向量的同一维坐标按向量的顺序排成一个新的向量组 \(v'\)，则这两个向量组对应立方体的体积相等。
性质 4
若将向量 \(v_m\) 加上一个向量 \(w\)，记向量组 \(v_1, \cdots, v_m + w, \cdots, v_n\) 对应的体积为 \(V_1\)；\(v_1, \cdots, w, \cdots, v_n\) 对应的体积为 \(V_2\)；\(v_1, \cdots, w, \cdots, v_n\) 对应的体积为 \(V_3\)。那么 \(V_1 = V_2 + V_3\) 或 \(V_1 = |V_2 - V_3|\)。