行列式基础知识
FLYC飘云
·
·
算法·理论
1 前置知识
1.1 排列
将 n 个元素按任意顺序，排成一列，称为这 n 个元素的排列。
例： 3,1,2
1.2 逆序对、逆序数、奇偶排列
对于排列 a_1,a_2,…a_n ，若 a_i>a_j ，且 i<j 则称 (a_i,a_j) 为一个逆序对。
例：在排列 3,1,2 中，有2个逆序对 (3,1),(3,2)
排列 p 的逆序数：排列中逆序对的总数。
奇排列：逆序数是奇数的排列。
偶排列：逆序数是偶数的排列。
例：排列 3,1,2 的逆序数为 2 ，是偶排列。
1.3 对换
对换：交换排列中两个数，其余保持不变。
相邻对换：相邻的两个数对换。
定理1：对换改变排列的奇偶性
证明思路：相邻对换会使逆序数+1或-1，而任意一次对换等价于奇数次相邻对换，奇偶性改变奇数次，奇偶性改变。
2 行列式
2.1 定义
对于一个 n×n 矩阵 A ，它的行列式是一个标量，记作 |A| 或 det(A) 。
det(A)=\displaystyle\sum_P (-1)^{σ(P)} \displaystyle\prod_{i=1}^n a_{i,P_i}
枚举所有 n 个数字的排列，其中 P 表示一个 n 个数字的排列， P_i 表示排列 P 中的第 i 个数， σ(P) 为排列 P 的逆序数。
通俗的说，就是从上往下从每行挑一个数，同时保证每列只挑了一个数，将这 n 个数乘起来。再看这次挑选的排列的逆序数奇偶，若为奇排列就再乘 -1 ，最后加到最终的结果上。
这种情况下怎么数逆序对呢？你看公式啊。 a 在 b 的左下方， a 和 b 就构成逆序对（即 a 的行数大于 b 的行数，但 a 的列数小于 b 的行数）
例子：
\begin{aligned}
det(A)=&\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{2,1} & a_{2,2} & a_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | \\
= & +a_{1,1}a_{2,2}a_{3,3} - a_{1,1}a_{2,3}a_{3,2} \\
& - a_{1,2}a_{2,1}a_{3,3} + a_{1,2}a_{2,3}a_{3,1} \\
& + a_{1,3}a_{2,1}a_{3,2} - a_{1,3}a_{2,2}a_{3,1}
\end{aligned}
2.2 性质
以下性质及其证明对所有行列式都可成立，这里拿 3×3 的行列式举例。
性质1：两行互换，行列式的值变为相反数。
例：
\begin{aligned}
\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{2,1} & a_{2,2} & a_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | = -
\left |
\begin{matrix}
a_{2,1} & a_{2,2} & a_{2,3} \\
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right |
\end{aligned}
证明思路：两行互换相当于每一项的排列都发生了一次对换，奇偶性取反，所有每一项的符号都变为相反数，所有整体变为相反数
性质2：某行所有数乘上 k ，行列式的值就乘上 k 。
\begin{aligned}
det(B)=&\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
ka_{2,1} & ka_{2,2} & ka_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | \\
= & + a_{1,1}ka_{2,2}a_{3,3} - a_{1,1}ka_{2,3}a_{3,2} \\
& - a_{1,2}ka_{2,1}a_{3,3} + a_{1,2}ka_{2,3}a_{3,1} \\
& + a_{1,3}ka_{2,1}a_{3,2} - a_{1,3}ka_{2,2}a_{3,1} \\
= & \; det(A)×k
\end{aligned}
性质3：若某一行的元素都是两数之和，则行列式的值为以下（看公式）两个行列式的值之和。
\begin{aligned}
&\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{2,1}+a'_{2,1} & a_{2,2}+a'_{2,1} & a_{2,3}+a'_{2,1} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | \\
= &
\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{2,1} & a_{2,2} & a_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | +
\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a'_{2,1} & a'_{2,2} & a'_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right |
\end{aligned}
证明思路：按定义展开，然后用乘法分配律。
性质4：若有两行成比例，则行列式的值为 0 。
证明思路：
\begin{aligned}
det(C)=&\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
ka_{1,1} & ka_{1,2} & ka_{1,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | \\
= &\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | × k\\
\end{aligned}
将上一个行列式 1,2 行互换，得到
\begin{aligned}
\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | = -
\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | \\
\end{aligned}
解得
\begin{aligned}
\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | = 0
\end{aligned}
故
det(C) = 0 × k = 0
性质5：将某行的所有数乘上一个数 k ，加到另一行对应的数上去，行列式值不变。
\begin{aligned}
\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{2,1} & a_{2,2} & a_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | =
\left |
\begin{matrix}
a_{1,1}+ka_{2,1} & a_{1,2}+ka_{2,2} & a_{1,3}+ka_{2,3} \\
a_{2,1} & a_{2,2} & a_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right |
\end{aligned}
证明思路：先用性质3，再用性质4。
\begin{aligned}
&\left |
\begin{matrix}
a_{1,1}+ka_{2,1} & a_{1,2}+ka_{2,2} & a_{1,3}+ka_{2,3} \\
a_{2,1} & a_{2,2} & a_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | \\
= &
\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{2,1} & a_{2,2} & a_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | +
\left |
\begin{matrix}
ka_{2,1} & ka_{2,2} & ka_{2,3} \\
a_{2,1} & a_{2,2} & a_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | \\
= &
\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
a_{2,1} & a_{2,2} & a_{2,3} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{matrix}
\right | + 0
\end{aligned}
3 求行列式
3.1 就硬算 按定义展开
det(A)=\displaystyle\sum_P (-1)^{σ(P)} \displaystyle\prod_{i=1}^n a_{i,P_i}
行列式按定义展开一共有 n! 项，每项有 n 个数相乘，时间复杂度 Θ(n×n!) 。
3.2 上三角行列式
主对角线：过 a_{i,i},i∈[1,n] 的对角线（从左上↖到右下↘的对角线）
\begin{aligned}
det(D)=\left |
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} \\
0 & a_{2,2} & a_{2,3} \\
0 & 0 & a_{3,3}
\end{matrix}
\right | = a_{1,1} a_{2,2} a_{3,3}
\end{aligned}
上三角行列式的值等于主对角线上所有数之积
按定义展开上三角行列式，发现只有一项不含 0 ，这一项包含主对角线上所有数。
证明思路：
先从倒数第 1 行选数，发现只能选最后一个数，因为选其它的最后算出来都是 0 。
再从倒数第 2 行选数，发现只能选倒数第 2 个数，因为最后一列已经选过了，而选其它的算出来都是 0 。
再从倒数第 3 行选数，发现只能选倒数第 3 个数，因为最后两列已经选过了，而选其它的算出来都是 0 。
......
计算上三角行列式的值，时间复杂度 Θ(n) 。
3.3 辗转相除法
用辗转相除法可把行列式化为上三角行列式。
详见代码。