排列

本书的主要主题通常被称为线性代数。然而，在过去的三个章节中，重点在于一种被称为多重线性代数的内容。很难确切地说这两个学科之间的分界线在哪里。既然在任何情况下，这两者都相当广泛，那么试图将这两者的详细讨论塞进同一卷书中是不切实际的。在绝对纯粹的状态下讨论线性代数也是不可取的；即使加入一小部分多重线性理论（例如现代张量积和行列式观点中所涉及的内容），也能使线性理论的适用范围得到令人愉悦的扩展，其效果远超所付出的努力。因此，我们建议继续研究多重线性代数；我们的意图是在我们已经掌握的知识与关于行列式的基本事实之间画一条或多或少笔直的线。考虑到这一点，我们将用三个章节来讨论关于组合学的一些简单事实；这些事实与多重线性代数之间的联系将在该讨论之后立即呈现。

我们所说的介于 $1$ 和 $k$ 之间（含）的整数的排列，是指一个一一变换，它将每个这样的整数分配给另一个整数（或者可能是同一个整数）。说变换 $\pi$ 是一一的，当然意味着如果 $\pi (1),\dots ,\pi (k)$ 分别是 $\pi$ 分配给 $1,\dots ,k$ 的整数，那么只有在 $i=j$ 的情况下才会发生 $\pi (i)=\pi (j)$ 。由于这意味着集合 $\{1,\dots ,k\}$ 和 $\{\pi (1),\dots ,\pi (k)\}$ 都恰好由 $k$ 个元素组成，因此它们由完全相同的元素组成。由此，我们反过来推断，集合 $\{1,\dots ,k\}$ 的排列 $\pi$ 将该集合满射到其自身，也就是说，如果 $1\le j\le k$ ，那么存在至少一个 $i$ （实际上，恰好有一个）使得 $\pi (i)=j$ 。在接下来的讨论中，所考虑的整数的总数，即 $k$ ，将保持不变。

排列理论和其它任何事物一样，最好通过仔细观察一些非平凡的例子来理解。然而，在给出任何例子之前，我们将首先提及一些可以对排列进行的通用操作；通过这种方式，这些例子不仅能说明基本概念，还能说明其基本性质。

如果 $\sigma$ 和 $\tau$ 是任意排列，那么可以通过对每个 $i$ 写入 $$(\sigma \tau )(i)=\sigma (\tau (i))$$ 来定义一个排列（记作 $\sigma \tau$ ）。为了证明 $\sigma \tau$ 确实是一个排列，观察到如果 $(\sigma \tau )(i)=(\sigma \tau )(j)$ ，那么 $\tau (i)=\tau (j)$ （因为 $\sigma$ 是一一的），因此 $i=j$ （因为 $\tau$ 是一一的）。排列 $\sigma \tau$ 被称为排列 $\sigma$ 和 $\tau$ 的乘积。也就是说，顺序是重要的。一般情况下 $\sigma \tau \ne \tau \sigma$ ，或者换句话说，排列乘法不满足交换律。

排列的乘法满足结合律；也就是说，如果 $\pi$ 、$\sigma$ 和 $\tau$ 是排列，那么 为了证明这一点，我们必须证明对于每个 $i$ ，都有 $$((\pi \sigma )\tau )(i)=(\pi (\sigma \tau ))(i)$$ 。证明由乘积定义的几次应用组成，如下所示： $$((\pi \sigma )\tau )(i)=(\pi \sigma )(\tau (i))=\pi (\sigma (\tau (i))),$$ 以及 $$(\pi (\sigma \tau ))(i)=\pi ((\sigma \tau )(i))=\pi (\sigma (\tau (i))).$$ 

鉴于这一结果，我们在书写三个或更多排列的乘积时，可以且应当省略括号。该结果还使我们能够证明显而易见的指数定律。排列 $\pi$ 的幂是通过归纳定义的，即对于所有 $p=1,2,3,\dots$ ，写入 ${\pi }^1=\pi$ 和 ${\pi }^{p+1}=\pi \cdot {\pi }^p$ ；结合律意味着对于所有 $p$ 和 $q$ ，有 ${\pi }^p\cdot {\pi }^q={\pi }^{p+q}$ 和 $({\pi }^p{)}^q={\pi }^{pq}$ 。观察到，一个排列的任意两个幂彼此交换，也就是说，${\pi }^p\cdot {\pi }^q={\pi }^q\cdot {\pi }^p$ 。

最简单的排列是恒等排列（记作 $ϵ$ ）；它对每个 $i$ 定义为 $ϵ(i)=i$ 。如果 $\pi$ 是任意排列，那么 或者换句话说，乘以 $ϵ$ 不会改变任何排列。证明是直接的；对于每个 $i$ ，我们有 $$(ϵ\pi )(i)=ϵ(\pi (i))=\pi (i)$$ 以及 $$(\pi ϵ)(i)=\pi (ϵ(i))=\pi (i).$$ 

从乘法的角度来看，排列 $ϵ$ 的行为就像数字 $1$ 。类比于通常的数值约定，每个排列 $\pi$ 的零次幂是通过写入 ${\pi }^0=ϵ$ 来定义的。

如果 $\pi$ 是任意排列，那么存在一个排列（记作 ${\pi }^{-1}$ ）使得 为了定义 ${\pi }^{-1}(j)$ （其中当然有 $1\le j\le k$ ），寻找唯一的 $i$ 使得 $\pi (i)=j$ ，并写入 ${\pi }^{-1}(j)=i$ ；式 (3) 的有效性是这些定义的直接推论。排列 ${\pi }^{-1}$ 被称为 $\pi$ 的逆。

设 ${𝒮}_k$ 为介于 $1$ 和 $k$ 之间的所有整数的排列集合。我们目前所证明的是，可以为 ${𝒮}_k$ 的元素定义一种乘法运算，使得 (1) 乘法满足结合律，(2) 存在一个单位元，即一个使得与其相乘能保持 ${𝒮}_k$ 的每个元素不变的元素，以及 (3) 每个元素都有一个逆元，即一个与给定元素的乘积为单位元的元素。一个满足 (1)–(3) 的集合，关于这些条件所指的乘积概念，被称为一个群；特别地，集合 ${𝒮}_k$ 被称为 次数为 $k$ 的对称群。观察到，整数 $1,\dots ,k$ 可以被任何 $k$ 个不同的对象所替代，而不影响上面定义的任何概念；这种改变仅仅是符号上的问题。