43. 排列

一般地, 在以组合定义定义行列式的教材里, 排列 (或置换) 的一些基本的性质是必要的, 因为它们对论证行列式的性质有用 (通俗地, 这些教材用排列研究行列式). 我想在本节用行列式研究排列 (通俗地, 我要反过来作).

研究排列时, 有一个行为是重要的.

定义 43.1 (对换). 设 $a_1$, $a_2$, $\dots$, $a_n$ 是一个排列. 设 $i$, $j$ 是不超过 $n$ 的二个不等的正整数. 交换此排列的第 $i$ 个文字与第 $j$ 个文字 (也就是, 交换文字 $a_i$, $a_j$), 且不改变其他的文字, 则, 我们得到一个新的排列 e $b_1$, $b_2$, $\dots$, $b_n$, 其中$$\begin{array}{r}{b}_k=\{\begin{array}{ll}{a}_j,& k=i;\\ a_i,& k=j;\\ a_k,& \text{其他}.\end{array}\end{array}$$我们说, 变 $a_1$, $a_2$, $\dots$, $a_n$ 为 $b_1$, $b_2$, $\dots$, $b_n$ 的行为是一次对换. 特别地, 若 $j=i+1$ 或 $j=i-1$ (通俗地, $a_i$, $a_j$, 或 $a_j$, $a_i$, 在 $a_1$, $a_2$, $\dots$, $a_n$ 里, 是相邻的二个文字), 我们说, 这一次对换是一次相邻对换.

例 43.2. 考虑排列 I: $3$, $2$, $5$, $1$, $4$. 交换 $3$ 与 $1$ 的位置, 得排列 II: $1$, $2$, $5$, $3$, $4$. 我们说, 变 I 为 II 的行为是一次对换.

还是考虑排列 I. 交换 $1$ 与 $4$ 的位置, 得排列 III: $3$, $2$, $5$, $4$, $1$. 变 I 为 III 的行为当然也是一次对换. 不过, 因为 $1$, $4$ 在 I 里是相邻的二个文字, 故我们也可说, 变 I 为 III 的行为是一次相邻对换.

注意, 一次对换的结果可以跟多次相邻对换的结果一样. 比如, 为了变 I 为 II, 我们可以这么作:

交换 $3$ 与 $2$ 的位置, 得排列 IV: $2$, $3$, $5$, $1$, $4$;

交换 $3$ 与 $5$ 的位置, 得排列 V: $2$, $5$, $3$, $1$, $4$;

交换 $3$ 与 $1$ 的位置, 得排列 VI: $2$, $5$, $1$, $3$, $4$;

交换 $5$ 与 $1$ 的位置, 得排列 VII: $2$, $1$, $5$, $3$, $4$;

交换 $2$ 与 $1$ 的位置, 得排列 VIII: $1$, $2$, $5$, $3$, $4$.

可以看到, 我们利用 $5$ 次相邻对换实现了一次 (不是相邻的) 对换. 注意, 这是一个奇数.

其实, 不难看出这么一件事. 设 $a_1$, $a_2$, $\dots$, $a_n$ 是一个排列, $i$, $j$ 是不超过 $n$ 的二个不等的正整数, 且 $i<j$. 则, 我们可作 $2(j-i)-1$ 次相邻对换以交换此排列的第 $i$ 个文字与第 $j$ 个文字.

相邻对换与逆序数有如下关系.

定理 43.3. 设 $a_1$, $a_2$, $\dots$, $a_n$ 是互不相同的 $n$ 个整数. 设排列 I: $a_1$, $a_2$, $\dots$, $a_n$ 的逆序数 $\tau (a_1,a_2,\dots ,a_n)=T$. 那么, 我们可作 $T$ 次相邻对换变排列 I 为其自然排列.

证. 我们先设 $a_1$, $a_2$, $\dots$, $a_n$ 是 $1$, $2$, $\dots$, $n$ 的排列. 作命题 $P(n)$:

对任何 $1$, $2$, $\dots$, $n$ 的一个排列 $a_1$, $a_2$, $\dots$, $a_n$, 我们可作 $\tau (a_1,a_2,\dots ,a_n)$ 次相邻对换变其为自然排列 $1$, $2$, $\dots$, $n$.

我们用数学归纳法证明, 对任何正整数 $n$, $P(n)$ 成立.

$P(1)$ 是对的. 毕竟, $1$ 只有 $1$ 个排列: $1$. 我们不必作任何对换, 它已是自然排列. 排列 $1$ 的逆序数自然是 $0$.

现在, 我们设 $P(m-1)$ 是对的. 我们证 $P(m)$ 也是对的. 任取 $1$, $2$, $\dots$, $m$ 的一个排列 $a_1$, $a_2$, $\dots$, $a_m$. 那么, 恰存在一个不超过 $m$ 的正整数 $k$, 使 $a_k=m$. 交换 $m$ 与 $a_{k+1}$, 再交换 $m$ 与 $a_{k+2}$, ……, 再交换 $m$ 与 $a_m$, 从而可变 $a_1$, $a_2$, $\dots$, $a_m$ 为 $a_1$, $\dots$, $a_{k-1}$, $a_{k+1}$, $\dots$, $a_m$, $m$. 这 $m-k$ 次相邻对换使 $m$ 是最后一个数 (若 $a_m=m$, 则不必作对换了, 故此关系仍成立), 且新排列的前 $m-1$ 个整数 $a_1$, $\dots$, $a_{k-1}$, $a_{k+1}$, $\dots$, $a_m$ 是 $1$, $2$, $\dots$, $m-1$ 的排列. 由假定, 我们可作 $T_{m-1}=\tau (a_1,\dots ,a_{k-1},a_{k+1},\dots ,a_m)$ 次相邻对换, 变 $a_1$, $\dots$, $a_{k-1}$, $a_{k+1}$, $\dots$, $a_m$ 为其自然排列 $1$, $2$, $\dots$, $m-1$. 所以, 我们可作 $T_{m-1}+(m-k)$ 次相邻对换变 $a_1$, $a_2$, $\dots$, $a_m$ 为其自然排列 $1$, $2$, $\dots$, $m$.

注意, 每一个适合条件 $1⩽i<j⩽m$ 的有序整数对 $(i,j)$ 恰适合以下三个条件的一个: (a) $i\ne k$ 且 $j\ne k$; (b) $i=k$ 且 $k<j⩽m$; (c) $1⩽i<k$ 且 $j=k$. 再注意, 对每一个不等于 $k$, 且不超过 $m$ 的正整数 $\ell$, 必有 $a_{\ell }<m$. 故$$\begin{array}{rl}& \tau (a_1,a_2,\dots ,a_m)\\ =& \sum _{1⩽i<j⩽m}\rho (a_i,a_j)\\ =& \sum _{\begin{array}{c}1⩽i<j⩽m\\ i,j\ne k\end{array}}\rho (a_i,a_j)+\sum _{k<j⩽m}\rho (a_k,a_j)+\sum _{1⩽i<k}\rho (a_i,a_k)\\ =& \tau (a_1,\dots ,a_{k-1},a_{k+1},\dots ,a_m)+\sum _{k<j⩽m}1+\sum _{1⩽i<k}0\\ =& T_{m-1}+(m-k).\end{array}$$从而, 我们可作 $\tau (a_1,a_2,\dots ,a_m)$ 次相邻对换变 $a_1$, $a_2$, $\dots$, $a_m$ 为其自然排列 $1$, $2$, $\dots$, $m$.

所以, $P(m)$ 是对的. 由数学归纳法, 对任何正整数 $n$, $P(n)$ 成立.

最后, 我们看一般的情形.

设 $a_1$, $a_2$, $\dots$, $a_n$ 的自然排列是 $c_1$, $c_2$, $\dots$, $c_n$. 我们记 $f(c_i)=i$ ($i=1$, $2$, $\dots$, $n$). (所以, 在 $a_1$, $a_2$, $\dots$, $a_n$ 中, $a_i$ 是第 $f(a_i)$ 小的数.) 那么, 不难看出, 若 $d_1$, $d_2$, $\dots$, $d_n$ 是 $c_1$, $c_2$, $\dots$, $c_n$ 的一个排列, 则 $f(d_1)$, $f(d_2)$, $\dots$, $f(d_n)$ 是 $1$, $2$, $\dots$, $n$ 的一个排列; 反过来, 若 $v_1$, $v_2$, $\dots$, $v_n$ 是 $1$, $2$, $\dots$, $n$ 的一个排列, 则 $c_{v_1}$, $c_{v_2}$, $\dots$, $c_{v_n}$ 是 $c_1$, $c_2$, $\dots$, $c_n$ 的一个排列. 也不难看出, 若 $d_t<d_v$, 必有 $f(d_t)<f(d_v)$. 反过来, 若 $f(d_t)<f(d_v)$, 必有 $d_t<d_v$. 从而, $f(a_1)$, $f(a_2)$, $\dots$, $f(a_n)$ 的逆序数等于 $a_1$, $a_2$, $\dots$, $a_n$ 的逆序数. 我们分别为 $a_1$, $a_2$, $\dots$, $a_n$ 取别名 $f(a_1)$, $f(a_2)$, $\dots$, $f(a_n)$, 即可用老方法, 作跟 $a_1$, $a_2$, $\dots$, $a_n$ 的逆序数一样多的次数的相邻对换, 变 $a_1$, $a_2$, $\dots$, $a_n$ 为其自然排列 $c_1$, $c_2$, $\dots$, $c_n$. (注意, 我们总可用类似的方法, 变一般的排列的研究为 $1$, $2$, $\dots$, $n$ 的排列的研究. 所以, 当我们得到 $1$, $2$, $\dots$, $n$ 的排列的只跟逆序有关的性质后, 我们总可译其为一般的排列的性质.)

证毕.

定理 43.4. 设排列 I: $a_1$, $a_2$, $\dots$, $a_n$. 施一次对换于排列 I, 得排列 II: $b_1$, $b_2$, $\dots$, $b_n$. 则$$\begin{array}{r}s(b_1,b_2,\dots ,b_n)=-s(a_1,a_2,\dots ,a_n).\end{array}$$(通俗地, 一次对换变排列的号.)

证. 无妨设排列 I, II 都是 $1$, $2$, $\dots$, $n$ 的排列; 可用我在前面提到的方法推广此事于任何的排列.

设 $n$ 级单位阵 $I=[e_1,e_2,\dots ,e_n]$. 作二个 $n$ 级阵 $A=[e_{a_1},e_{a_2},\dots ,e_{a_n}]$, $B=[e_{b_1},e_{b_2},\dots ,e_{b_n}]$. 那么, $B$ 可被认为是交换了 $A$ 的二列, 且不改变其他的列得到的阵. 从而, $$\begin{array}{rl}s(b_1,b_2,\dots ,b_n)=& s(b_1,b_2,\dots ,b_n)\det (I)\\ =& \det (B)\\ =& -\det (A)\\ =& -s(a_1,a_2,\dots ,a_n)\det (I)\\ =& -s(a_1,a_2,\dots ,a_n).\end{array}$$

证毕.

定理 43.5. 设 $n⩾2$. 设 $a_1$, $a_2$, $\dots$, $a_n$ 是 $n$ 个互不相同的整数. 那么, 在 $a_1$, $a_2$, $\dots$, $a_n$ 的全部排列中, 符号为 $1$ 的排列跟符号为 $-1$ 的排列的数目相等.

证. 设 $a_1$, $a_2$, $\dots$, $a_n$ 的自然排列是 $c_1$, $c_2$, $\dots$, $c_n$. 不难看出, 每一个 $a_1$, $a_2$, $\dots$, $a_n$ 的排列都是 $c_1$, $c_2$, $\dots$, $c_n$ 的排列, 且每一个 $c_1$, $c_2$, $\dots$, $c_n$ 的排列都是 $a_1$, $a_2$, $\dots$, $a_n$ 的排列,

无妨设 $c_1$, $c_2$, $\dots$, $c_n$ 分别为 $1$, $2$, $\dots$, $n$; 可用我在前面提到的方法推广此事于任何的排列.

作 $n$ 级阵 $U$, 其中 $[U{]}_{i,j}=1$ (通俗地, $U$ 的每一个元都是 $1$). 根据交错性, $\det (U)=0$. 根据完全展开, $$\begin{array}{rl}0=& \det (U)\\ =& \sum _{\begin{array}{c}1⩽i_1,i_2,\dots ,i_n⩽n\\ i_1,i_2,\dots ,i_n\text{互不相同}\end{array}}s(i_1,i_2,\dots ,i_n)[U{]}_{i_1,1}[U{]}_{i_2,2}\dots [U{]}_{i_n,n}\\ =& \sum _{\begin{array}{c}1⩽i_1,i_2,\dots ,i_n⩽n\\ i_1,i_2,\dots ,i_n\text{互不相同}\end{array}}s(i_1,i_2,\dots ,i_n).\end{array}$$我问一个简单的问题: 设有 $k$ 个数, 每一个都是 $1$ 或 $-1$. 若它们的和为 $0$, 请问, 有几个 $1$, 有几个 $-1$? 我想, 您能答出, $1$ 跟 $-1$ 的个数都是 $k/2$.

证毕.

由此可见, 完全展开 $n$ 级阵 ($n⩾2$) 的行列式的公式里, 符号为 $+$ 的项的数目与符号为 $-$ 的项的数目都是 $(n\cdot (n-1)\cdot \cdots \cdot 2\cdot 1)/2$.

最后, 我想说公理定义的事.

或许, 您还记得, 我在第一章, 节 14, “用行列式的性质确定行列式” 里说过, 行列式的规范性、多线性、交错性可确定行列式:

定理 43.6. 设定义在全体 $n$ 级阵上的函数 $f$ 适合:

(1) (多线性) 对任何不超过 $n$ 的正整数 $j$, 任何 $n-1$ 个 $n\times 1$ 阵 $a_1$, $\dots$, $a_{j-1}$, $a_{j+1}$, $\dots$, $a_n$, 任何二个 $n\times 1$ 阵 $x$, $y$, 任何二个数 $s$, $t$, 有$$\begin{array}{rl}& f([a_1,\dots ,a_{j-1},sx+ty,a_{j+1},\dots ,a_n])\\ =& sf([a_1,\dots ,a_{j-1},x,a_{j+1},\dots ,a_n])+tf([a_1,\dots ,a_{j-1},y,a_{j+1},\dots ,a_n]).\end{array}$$

(2) (交错性) 若 $n$ 级阵 $A$ 有二列相同, 则 $f(A)=0$.

那么, 对任何 $n$ 级阵 $A$, $f(A)=f(I)\det (A)$.

特别地, 若 $f(I)=1$ (规范性), 则 $f$ 就是行列式.

还记得我如何证此事吗? 我作了一个辅助函数$$\begin{array}{r}g(A)=f(A)-f(I)\det (A).\end{array}$$可以验证, $g$ 是多线性的、交错性的, 且 $g(I)=0$. 于是, 设法证对任何 $n$ 级阵 $A$, $g(A)=0$ 即可. 我为什么要作这个 $g$?

为解释此事, 我们看, 若我不作此 $g$, 会如何. 首先, 因为 $f$ 的多线性与交错性, 我们可类似地写出$$\begin{array}{r}f(A)=\sum _{\begin{array}{c}1⩽i_1,i_2,\dots ,i_n⩽n\\ i_1,i_2,\dots ,i_n\text{互不相同}\end{array}}[A{]}_{i_1,1}[A{]}_{i_2,2}\dots [A{]}_{i_n,n}f([e_{i_1},e_{i_2},\dots ,e_{i_n}]),\end{array}$$其中 $e_k$ 是 $n$ 级单位阵 $I$ 的列 $k$.

然后, 我们要确定 $f([e_{i_1},e_{i_2},\dots ,e_{i_n}])$. 由多线性与交错性, 我们可推出反称性. 则我们可以适当地交换 $[e_{i_1},e_{i_2},\dots ,e_{i_n}]$ 的列, 变其为 $[e_1,e_2,\dots ,e_n]$, 即 $n$ 级单位阵 $I$. 从而, 存在一个由 $i_1$, $i_2$, $\dots$, $i_n$ 确定的数 $\sigma (i_1,i_2,\dots ,i_n)$, 其等于 $1$ 或 $-1$, 使$$\begin{array}{r}f([e_{i_1},e_{i_2},\dots ,e_{i_n}])=\sigma (i_1,i_2,\dots ,i_n)f(I).\end{array}$$故$$\begin{array}{r}f(A)=f(I)\sum _{\begin{array}{c}1⩽i_1,i_2,\dots ,i_n⩽n\\ i_1,i_2,\dots ,i_n\text{互不相同}\end{array}}\sigma (i_1,i_2,\dots ,i_n)[A{]}_{i_1,1}[A{]}_{i_2,2}\dots [A{]}_{i_n,n}.\end{array}$$问题来了: $\sigma (i_1,i_2,\dots ,i_n)$ 究竟是什么?

我们回想, 任给 $1$, $2$, $\dots$, $n$ 的一个排列 $i_1$, $i_2$, $\dots$, $i_n$, 我们总可作 $\tau (i_1,i_2,\dots ,i_n)$ 次相邻对换变其为自然排列. 所以, 我们可作 $\tau (i_1,i_2,\dots ,i_n)$ 次列的交换 (每次交换二列), 变 $[e_{i_1},e_{i_2},\dots ,e_{i_n}]$ 为 $I$. 由反称性,$$\begin{array}{rl}f([e_{i_1},e_{i_2},\dots ,e_{i_n}])=& (-1{)}^{\tau (i_1,i_2,\dots ,i_n)}f([e_1,e_2,\dots ,e_n])\\ =& s(i_1,i_2,\dots ,i_n)f(I).\end{array}$$所以, $\sigma (i_1,i_2,\dots ,i_n)=s(i_1,i_2,\dots ,i_n)$. 再根据完全展开$$\begin{array}{rl}\det (A)=& \sum _{\begin{array}{c}1⩽i_1,i_2,\dots ,i_n⩽n\\ i_1,i_2,\dots ,i_n\text{互不相同}\end{array}}s(i_1,i_2,\dots ,i_n)[A{]}_{i_1,1}[A{]}_{i_2,2}\dots [A{]}_{i_n,n},\end{array}$$知 $f(A)=f(I)\det (A)$.

由此可见, 理论地, 不作辅助函数 $g$ 也是可证此事的. 不过, 跟作辅助函数 $g$ 的论证相比, 这个试直接计算 $f(A)$ 的论证至少用到了二件事:

(1) 作跟逆序数一样多的次数的相邻对换, 可变一个排列为其自然排列;

(2) 完全展开行列式的公式.

注意, (1) 是我在本节提到的, 而 (2) (在我的教学里) 是选学的内容. 所以, 为了使论证更好地被理解, 也为了使论证简单, 我作了辅助函数. $g$ 的一个特点是 $g(I)=0$. 所以, 利用反称性变 $g([e_{i_1},e_{i_2},\dots ,e_{i_n}])$ 为 $g(I)$ 时, 我们既不必关注变了几次号, 也不必关注如何变 $i_1$, $i_2$, $\dots$, $i_n$ 为 $1$, $2$, $\dots$, $n$ (比如, 要变 $3$, $2$, $5$, $1$, $4$ 为 $1$, $2$, $3$, $4$, $5$, 可以从后向前看, 交换 $5$, $4$ 的位置, 再交换 $4$, $1$ 的位置, 再交换 $3$, $1$ 的位置); 我们知道, 可适当地交换文字的位置, 变 $i_1$, $i_2$, $\dots$, $i_n$ 为 $1$, $2$, $\dots$, $n$, 即可. “$0$ 跟任何数的积都是 $0$” 起了大的作用.

用同样的方法, 可证

定理 43.7. 设 $c$ 是常数. 设定义在全体 $n$ 级阵上的函数 $f$ 适合:

(1) (多线性) 对任何不超过 $n$ 的正整数 $j$, 任何 $n-1$ 个 $n\times 1$ 阵 $a_1$, $\dots$, $a_{j-1}$, $a_{j+1}$, $\dots$, $a_n$, 任何二个 $n\times 1$ 阵 $x$, $y$, 任何二个数 $s$, $t$, 有$$\begin{array}{rl}& f([a_1,\dots ,a_{j-1},sx+ty,a_{j+1},\dots ,a_n])\\ =& sf([a_1,\dots ,a_{j-1},x,a_{j+1},\dots ,a_n])+tf([a_1,\dots ,a_{j-1},y,a_{j+1},\dots ,a_n]).\end{array}$$

(2) (交错性) 若 $n$ 级阵 $A$ 有二列相同, 则 $f(A)=0$.

(3) $f(I)=c$.

设定义在全体 $n$ 级阵上的函数 $h$ 也适合这三条性质. 则对任何 $n$ 级阵 $A$, $f(A)=h(A)$.

证. 作辅助函数 $g(A)=f(A)-h(A)$. 此 $g$ 也有多线性与交错性, 且 $g(I)=0$. 然后, 用我 (在第一章, 节 14) 用过的方法即可. (注意, 此事甚至没提到 “行列式” “det”.)

证毕.