『linear algebra-1』determinant
行列式
本篇是对高等代数中"行列式"的定义、性质、定理以及计算方法的速记，不涉及严密的推导证明。
一、行列式的定义
余子式 和 代数余子式：两者相差一个符号
- 余子式：将 \(|\text{A}|\) 中第 \(i\) 行、第 \(j\) 列的所有元素删除得到的 \(n-1\) 阶行列式即为余子式，记作 \(\text{M}_{ij}\)
- 代数余子式：在余子式前加一个符号，正负由角标和决定，记 \(\text{A}_{ij} = (-1)^{i+j}\text{ M}_{ij}\)
行列式的递归定义：按行列式阶数 \(n\) 归纳
\(n = 1\) 时：\(|\text{A}| = |a_{ij}| = a_{ij}\)
归纳推理：假设所有 \(n - 1\) 阶的行列式已经定义好，故所有 \(\text{M}_{ij}\) 都已经定义好了；按第 1 列展开
则有 \(|\text{A}| = a_{11}\text{M}_{11} - a_{21}\text{M}_{21} + \cdots + (-1)^{n + 1}a_{n1}\text{M}_{n1}\)，或 \(|\text{A}| = a_{11}\text{A}_{11} + a_{21}\text{A}_{21} + \cdots + a_{n1}\text{A}_{n1}\)
注意：可以证明，行列式可以按任意第 \(s\) 列展开，即 \(|\text{A}| = a_{1s}\text{A}_{1s} + \dots a_{ns}\text{A}_{ns}\)
全排列与逆序数：
常序排列 与 逆序排列：设 1, 2, ..., n 的全排列集合为 \(\text{S}_n\)
- 常序排列：指标从小到大的全排列，有且仅有一个（1, 2, ..., n）
- 逆序排列：不是常序排序的全排列；若\(j > i\) 且 \(j\) 排在 \(i\) 之前，称 \((j, i)\) 为一个逆序对
逆序数：设任意一个全排列为 \((k_1, \dots, k_n) \in \text{S}_n\)
求解方法： 设 \(k_1\) 后面有 \(m_1\) 个数比它小，...，\(k_{n-1}\) 后面有 \(m_{n-1}\) 个数比它小，则逆序数 \(N(k_1, \dots k_{n}) = \sum_{i}^{n-1} m_i\)
奇排列 和 偶排列：\(N(k_1, \dots k_n)\) 为奇数则为奇排列，\(N(k_1, \dots k_n)\) 为偶数则为偶排列
奇偶排列的性质：
调换全排列中的任意两个不同元素 \(k_i, k_j\)，则全排列的奇偶性发生改变
集合 \(S_n\) 中，奇排列和偶排列的个数各占一半（\(n > 2\)），即 \(\dfrac{n!}{2}\) 个
全排列 \((k_1, \dots, k_n)\) 可经过 \(N(k_1, \dots , k_n)\) 次相邻元素调换得到常序排列 \((1, \dots n)\)
注意：每轮迭代选取当前未在有序位置上的最大的数 \(k_i\)，让其与右侧相邻元素调换 \(m_i\) 次，直至得到常序排列
行列式的组合定义：设 \(|\text{A}|\) 为 \(n\) 阶行列式，借助全排列和逆序数可得到 \[ |\text{A}| = \sum_{(k_1, \dots, k_n) \in S_n} (-1)^{N(k_1, \dots k_n)} a_{k_11}a_{k_22} \cdots a_{k_nn} \]
二、行列式的性质
设 \(|\text{A}|\) 为 \(n\) 阶上三角（下三角）行列式，则 \(|\text{A}| = a_{11}a_{22}\dots a_{nn}\)，即对角线元素的乘积
设 \(|\text{A}|\) 为 \(n\) 阶行列式，将 \(|\text{A}|\) 中的一行（或一列）元素同时乘以常数 \(c\) 得到行列式 \(|\text{B}| = c|\text{A}|\)
若 \(|\text{A}|\) 中有一行（一列）的元素全为 0，则 \(|\text{A}| = \textbf{0}\)
交换 \(|\text{A}|\) 中的两个不同的行（列），所得行列式 \(|\text{B}| = -|\text{A}|\)
若 \(|\text{A}|\) 的两行（两列）成比例（或就是相等的），则有 \(|\text{A}| = 0\)
行列可拆分：讨论行的情形，设第 \(r\) 行（\(1 \le r \le n\)）可拆分成两向量的和，则有 \[ \begin{align} \left| \begin{matrix} a_{11} & \dots & a_{1n} \\ \vdots & \cdots & \vdots \\ a_{r1} + b_{r1} & \cdots & a_{rn} + b_{rn} \\ \vdots & \cdots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{matrix} \right| \end{align} = \left| \begin{matrix} a_{11} & \dots & a_{1n} \\ \vdots & \cdots & \vdots \\ a_{r1} & \cdots & a_{rn} \\ \vdots & \cdots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{matrix} \right| + \left| \begin{matrix} a_{11} & \dots & a_{1n} \\ \vdots & \cdots & \vdots \\ b_{r1} & \cdots & b_{rn} \\ \vdots & \cdots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{matrix} \right| \] 按列拆分情形同理，注意除了被拆分行（列），其余行（列）全部应前后相同
初等变换值不变：讨论行的情形，将 \(|\text{A}|\) 的第 \(i\) 行乘以常数倍加到第 \(j\) 行上，行列式的值不改变 \[ \begin{align} \left| \begin{matrix} a_{11} & \dots & a_{1n} \\ \vdots & \cdots & \vdots \\ a_{i1} & \cdots & a_{in} \\ \vdots & \cdots & \vdots \\ c a_{i1} + a_{j1} & \cdots & ca_{in}+a_{jn} \\ \vdots & \cdots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{matrix} \right| = \left| \begin{matrix} a_{11} & \dots & a_{1n} \\ \vdots & \cdots & \vdots \\ a_{i1} & \cdots & a_{in} \\ \vdots & \cdots & \vdots \\ a_{j1} & \cdots & a_{jn} \\ \vdots & \cdots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{matrix} \right| = |\text{A}| \end{align} \] 按列初等变换情形同理
转置不改变行列式的值，即 \(|\text{A}^T| = |\text{A}|\)
Cramer's Rule：克拉默法则，用于求解线性方程组，设线性方程组为 \[ \begin{cases} a_{11}x_1 + \dots + a_{1n}x_n = b_1 \\ a_{12}x_1 + \dots + a_{2n}x_n = b_2 \\ \qquad \qquad \vdots \\ a_{n1}x_1 + \dots + a_{nn}x_{n} = b_n \\ \end{cases} \] 并根据以上方程组引出以下行列式，其中 \(|\text{A}_i|\) 表示将 \(b\) 替换入 \(|\text{A}|\) 的第 \(i\) 列 \[ \text{A} = \left| \begin{matrix} a_{11} & \dots & a_{1n} \\ \vdots & \cdots & \vdots \\ a_{n1} & \cdots & a_{nn} \\ \end{matrix} \right| \qquad \text{A}_i = \left| \begin{matrix} a_{11} & \dots & b_{1} & \cdots & a_{1n} \\ \vdots & \cdots & b_{r} & \cdots & \vdots \\ a_{n1} & \cdots & b_{n} & \cdots & a_{nn} \\ \end{matrix} \right| \] 假设原线性方程组有解（\(|\text{A}| \ne 0\)），则 \(x_i = \dfrac{|\text{A}_i|}{|\text{A}|}\)；相当于把解方程组的问题转化为求行列式的问题
三、行列式的计算
行列式的计算原则：利用行列式的性质（提公因子 + 初等变换）将某一行（列）尽可能多地消成 0，再按该行（列）展开 降阶
- "提公因子"性质：提出某一行（列）的公因子 \(c\)，得到 \(|\text{B}| = c|\text{A}|\)
- 初等变换性质：某一行（列）乘以常数 \(c\) 累加到另一行（列）上 消元
VanderMonde 行列式："递推法"求解；关于未定元 \(x_i\) 的范德蒙行列式，每一行按升幂排列，形式如下 \[ \text{V}_n = \left| \begin{matrix} 1 & x_1 & x_1^2 & \dots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \dots & x_2^{n-1} \\ \vdots & \cdots & \cdots & \cdots & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1}\end{matrix} \right| \] 将最后一行尽可能消成 0，得到 \(1, 0, \dots, 0\)；降阶化简可得到递推式 \(\text{V}_n = (x_n - x_1)\cdots(x_n - x_{n-1}) \text{V}_{n-1}\)
解得 \(\text{V}_n = \prod_{1 \le i \lt j \le n}(x_j - x_i)\)，即"大指标 - 小指标，再求累乘"
多项式友阵行列式："递推法"求解，可从原行列式中找到"递归子结构"，例题形式如下（右下角是"递归子结构"） \[ \text{F}_n = \left| \begin{matrix} \lambda & 0 & 0 & \cdots & 0 & a_n \\ -1 & \lambda & 0 & \dots & 0 & a_{n-1} \\ 0 & -1 & \lambda & \dots & 0 & a_{n-2} \\ \vdots & \cdots & \cdots & \cdots & \cdots & \vdots \\ 0 & 0 & 0 & \cdots & \lambda & a_2 \\ 0 & 0 & 0 & \cdots & -1 & \lambda + a_1 \end{matrix} \right| \] 按第一行展开得到递推式 \(\text{F}_n = \lambda \text{F}_{n-1} + (-1)^{n+1}a_n \times (-1)^{n-1} = \lambda \text{F}_{n-1} + a_n = \lambda(\lambda\text{F}_{n-2}+a_{n-1}) + a_{n} = \dots\)
依此类推，解得 \(\text{F}_n = \lambda^n + a_1\lambda^{n-1} + \dots a_{n-1}\lambda + a_n\)
"求和法"求行列式：特别适用于每一行（每一列）求和相等的情形，例题形式如下 \[ |\text{A}| = \left| \begin{matrix} x & a & a & \dots & a & a \\ a & x & a & \dots & a & a \\ \vdots & \cdots & \cdots & \cdots & \cdots & \vdots \\ a & a & a & \cdots & x & a \\ a & a & a & \cdots & a & x \\\end{matrix} \right| \] 观察可知每一行（列）的求和相等，故考虑把其它行都累加到第一行上，提取公因式得到全 1 的第一行： \[ |\text{A}| = [x + (n - 1)a] \cdot \left| \begin{matrix} 1 & 1 & 1 & \dots & 1 & 1 \\ a & x & a & \dots & a & a \\ \vdots & \cdots & \cdots & \cdots & \cdots & \vdots \\ a & a & a & \cdots & x & a \\ a & a & a & \cdots & a & x \\\end{matrix} \right| \] 把第 1 行乘以 \(-a\) 累加到其它行上，消得很多"1"，得到如下形式： \[ |\text{A}| = [x + (n - 1)a] \cdot \left| \begin{matrix} 1 & 1 & 1 & \dots & 1 & 1 \\ 0 & x-a & 0 & \dots & 0 & 0 \\ \vdots & \cdots & \cdots & \cdots & \cdots & \vdots \\ 0 &0 & a & \cdots & x - a & 0 \\ 0 & 0 & 0 & \cdots & 0 & x-a \\\end{matrix} \right| \] 对于上三角行列式，可直接求得 \(|\text{A}| = [x + (n - 1)a] \cdot (x-a)^{n-1}\)
"拆分法"求行列式：例题形式如下，证明以下恒等式 \[ \left| \begin{matrix} ax+by & ay+bz & az+bx \\ ay+bz & az+bx & ax+by \\ az+bx & ax+by & ay+bz\end{matrix} \right| = (a^3+b^3)\left| \begin{matrix} x & y & z \\ y & z & x \\ z & x & y \end{matrix} \right| \] 按第 1 列拆开，提出该列第一项公因子 \(a\) 的同时可乘以 \(b\) 消去第 3 列的第二项；
按第 3 列拆开，提出该列第一项公因子 \(a\) 的同时可乘以 \(b\) 消去第 2 列的第二项；
最终得到公因子 \((a^3+b^3)\) 的同时化简出右边的行列式，证毕。
四、Laplace 定理
\(k\) 阶子式 和 \(k\) 阶余子式：设 \(|\text{A}|\) 为 \(n\) 阶行列式，\(1 \le k \lt n\)
\(k\) 阶子式：将 \(|\text{A}|\) 的第 \(i_1, \dots i_k\) 行，第 \(j_1, \dots j_k\) 列的交叉元素提取出来，按原先顺序摆放，得到 \(k\) 阶行列式，形式如下 \[ \text{A}\begin{pmatrix} i_1 \dots i_k \\ j_1 \dots j_k \end{pmatrix} = \left| \begin{matrix} a_{i_1j_1} & \dots & a_{i_1j_k} \\ \vdots & \cdots & \vdots \\ a_{i_kj_1} & \cdots & a_{i_kj_k} \end{matrix} \right| \]
\(k\) 阶余子式 与 \(k\) 阶代数余子式：将第 \(i_1, \dots , i_k\) 行，第 \(j_1, \dots j_k\) 列的交叉元素删除，剩余元素按原先顺序摆放，得到 \((n-k)\) 阶余子式 \(\text{M}\) \[ \begin{align} &\text{M}\begin{pmatrix} i_1 \dots i_k \\ j_1 \dots j_k \end{pmatrix} \\ \end{align} \] 代数余子式和余子式 \(\text{M}\) 之间仅相差一个符号，记作 \(\hat{\text{A}}\)，形式如下 \[ \hat{\text{A}}\begin{pmatrix} i_1 \dots i_k \\ j_1 \dots j_k \end{pmatrix} = (-1)^{(i_1 + \dots + i_k + j_1 + \dots j_k)}\text{M}\begin{pmatrix} i_1 \dots i_k \\ j_1 \dots j_k \end{pmatrix} \]
Laplace 展开：\(|\text{A}|\) 中给定 \(k\) 行（列），则包含于这 \(k\) 行（列）中的所有 \(k\) 阶子式与其代数余子式乘积之和 = \(|\text{A}|\)
给定 \(1 \le i_1 \lt \dots \lt l_k \le n\) 行：枚举枚举所有 \(k\) 列的组合 \[ |\text{A}| = \sum_{1 \le j_1 \lt \dots \lt j_k \le n} \text{A}\begin{pmatrix} i_1 \dots i_k \\ j_1 \dots j_k \end{pmatrix} \hat{\text{A}}\begin{pmatrix} i_1 \dots i_k \\ j_1 \dots j_k \end{pmatrix} \]
给定 \(1 \le j_1 \lt \dots \lt j_k \le n\) 列：枚举所有 \(k\) 行的组合 \[ |\text{A}| = \sum_{1 \le i_1 \lt \dots \lt i_k \le n} \text{A}\begin{pmatrix} i_1 \dots i_k \\ j_1 \dots j_k \end{pmatrix} \hat{\text{A}}\begin{pmatrix} i_1 \dots i_k \\ j_1 \dots j_k \end{pmatrix} \]
注意：Laplace 定理是行列式的递归定义（\(k = 1\)）的推广形式
Laplace 定理推论：设分块上三角行列式为 \(|\text{A}|\)，形式如下 \[ |\text{A}| = \left| \begin{matrix} \text{B}_{k\times k} & \text{C} \\ \textbf{O} & \text{D} \end{matrix} \right| \] 则 \(|\text{A}| = |\text{B}| \cdot |\text{D}|\)；分块下三角行列式同理，证明只需要对前 \(k\) 行进行 Laplace 展开即可