行列式值的按行列展开定义与排列定义等价性证明

Posted on 2019-12-13 Views:

行列式值的排列定义

$A_{n\times n} = \sum_{\pi \in S_n} (-1)^{\sigma(\pi)}\prod_{i=1}^na_{i, \pi(i)}$

其中 S_n 表示所有排列的集合， $\pi$ 表示一个排列， $\sigma(\pi)$ 表示 $\pi$ 的逆序对数，即

$\sigma(\pi)=\sum_{i<j}[\pi(i) > \pi(j)]$

等价性证明

使用归纳证明。（自己想的，觉得可能绕了很大的弯路。）

时显然。
假设 $n=k \quad (k \in \mathbb{N^{\ast}})$ 时成立，考虑时的情况。

不失一般性，考虑第行展开：
$A_{(k + 1) \times (k + 1)} = \sum_{j=1}^{k+1} a_{i,j}(-1)^{i+j}M_{i,j}$
其中为阶行列式。考虑如何计算，由归纳假设。
$M_{i,j} = \sum_{\pi \in S_k}(-1)^{\sigma(\pi)}\prod_{l=1, l \neq i}^{k+1} a_{l, \pi'(l)}$

（后面所有推导用到的 $i,j,\pi$ 都指上式中的相关符号）其中
$\pi'(l) = \pi(l-[l > i]) + [\pi(l-[l > i])\ge j]$
定义是为了跳过被删去的第行和第列，不改变元素间的大小关系。

接下来考虑排列
$\pi^{\ast}(l) = \begin{cases} j, &l=i \\ \pi'(l), &l\neq i \end{cases}$
显然表示了把“插入”的结果。

观察到
$\begin{aligned} \sigma(\pi^{\ast}) &= \sigma(\pi) + \sum_{l=1}^{i-1}[\pi'(l)>j] + \sum_{l=i+1}^{k+1}[\pi'(l)<j] \\ &= \sigma(\pi) + \underbrace{\sum_{l =1}^{i-1}[\pi(l) \ge j] + \sum_{l=i}^k[\pi(l)<j]}_{\Delta\sigma} \end{aligned}$
接下来只需要证明。

注意到，可以通过交换元素在任意两个排列之间变换（证明显然略，冒泡排序算法给出了进行此类交换的步骤构造）。为了简便起见，称 $l=1,2,3,\cdots,i$ 为“前面”， $l=i+1,i+2,\cdots,k$ 为“后面”， $\pi(l)<j$ 为“小”， $\pi(l) \ge j$ 为"大"。

那么显然，前面和前面，后面和后面的交换不改变 $\Delta\sigma$ 。着重考虑前面后面之间交换的情况。

然后注意到：
1. 如果是前面的小元素和后面的大元素进行交换，交换后的 $\Delta\sigma$ 项增加。
2. 如果是前面的大元素和后面的小元素进行交换，交换后的 $\Delta\sigma$ 项减少。
综上，我们可以下结论：虽然在变换排列的过程中， $\Delta\sigma$ 项可能会改变，但是 $(-1)^{\Delta\sigma}$ 的值是不会改变的。

这等价于在固定的情况下，对于任意的 $\pi$ ， $(-1)^{\Delta\sigma}$ 都是相同的。

只需要考察一个特例，选取恒等排列 $\pi(l)=l$ 。

此时
$\begin{aligned} \Delta\sigma&=\sum_{l =1}^{i-1}[l \ge j] + \sum_{l=i}^k[l<j] \\ &= \min(i - j,0) + \min(j-i,0) \\ &= |i - j| \end{aligned}$
显然。

因此 $(-1)^{\Delta\sigma} = (-1)^{i+j}$ 。

因此 $(-1)^{\sigma(\pi^{\ast})} = (-1)^{i+j}(-1)^{\sigma(\pi)}$ 。

回到的计算式：
$\begin{aligned} A_{(k + 1) \times (k + 1)} &= \sum_{j=1}^{k+1} a_{i,j}(-1)^{i+j}M_{i,j} \\ &= \sum_{j=1}^{k+1} a_{i,j}(-1)^{i+j}\sum_{\pi \in S_k}(-1)^{\sigma(\pi)}\prod_{l=1, l \neq i}^{k+1} a_{l, \pi'(l)} \\ &= \sum_{j=1}^{k+1} a_{i,j}\sum_{\pi \in S_k}(-1)^{i+j}(-1)^{\sigma(\pi)}\prod_{l=1, l \neq i}^{k+1} a_{l, \pi'(l)} \\ &= \sum_{j=1}^{k+1} \sum_{\pi \in S_k}(-1)^{\sigma(\pi^{\ast})}a_{i,j}\prod_{l=1, l \neq i}^{k+1} a_{l, \pi'(l)} \\ &= \sum_{j=1}^{k+1} \sum_{\pi \in S_k}(-1)^{\sigma(\pi^{\ast})}\prod_{l=1}^{k+1} a_{l, \pi^{\ast}(l)} \\ &= \sum_{j=1}^{k+1} \sum_{\substack{\pi^{\ast}\in S_{k+1} \\ \pi^{\ast}(i) = j}}(-1)^{\sigma(\pi^{\ast})}\prod_{l=1}^{k+1} a_{l, \pi^{\ast}(l)} \\ &= \sum_{\pi^{\ast}\in S_{k+1}}(-1)^{\sigma(\pi^{\ast})}\prod_{l=1}^{k+1} a_{l, \pi^{\ast}(l)} \\ &= \sum_{\pi\in S_{k+1}}(-1)^{\sigma(\pi)}\prod_{i=1}^{k+1} a_{i, \pi(i)} \end{aligned}$
即归纳命题成立，由数学归纳法，得证。

意义

证明了行列式两种方法的等价性。
证明了行列式挑选任意行/列做展开的结果是等价的，这在行列式按行列展开求值的定义当中并没有那么显然。