行列式值的排列定义

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

其中 \(S_n\) 表示所有 \(n\) 排列的集合，\(\pi\) 表示一个排列，\(\sigma(\pi)\) 表示 \(\pi\) 的逆序对数，即 \[ \sigma(\pi)=\sum_{i<j}[\pi(i) > \pi(j)] \]

等价性证明

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

  1. \(n=1,2,3\) 时显然。

  2. 假设 \(n=k \quad (k \in \mathbb{N^{\ast}})\) 时成立，考虑 \(n=k+1\) 时的情况。

    不失一般性，考虑第 \(i\) 行展开： \[ A_{(k + 1) \times (k + 1)} = \sum_{j=1}^{k+1} a_{i,j}(-1)^{i+j}M_{i,j} \] 其中 \(M_{i, j}\) 为 \(k\) 阶行列式。考虑如何计算 \(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'\) 是为了跳过被删去的第 \(i\) 行和第 \(j\) 列，不改变元素间的大小关系。

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

    观察到 \[ \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} \] 接下来只需要证明 \((-1)^{\Delta\sigma}=(-1)^{i + j}\)。

    注意到，可以通过交换元素在任意两个排列之间变换（证明显然略，冒泡排序算法给出了进行此类交换的步骤构造）。为了简便起见，称 \(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\)。
    2. 如果是前面的大元素和后面的小元素进行交换，交换后的 \(\Delta\sigma\) 项减少 \(2\)。

    综上，我们可以下结论：虽然在变换排列的过程中，\(\Delta\sigma\) 项可能会改变，但是 \((-1)^{\Delta\sigma}\) 的值是不会改变的。

    这等价于在 \((i, j)\) 固定的情况下，对于任意的 \(\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)^{|i-j|} = (-1)^{i+j}\)。

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

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

    回到 \(A\) 的计算式： \[ \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} \] 即归纳命题成立，由数学归纳法，得证。

意义

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