数学笔记（四）

这一篇纯属自娱自乐。顺便试一下格志新的DruTex。

设A是可换环。对于A上的n阶矩阵M，把它的特征多项式det(Ix-M)（I是单位矩阵）记为f(x)。Cayley-Hamilton定理说，如果把矩阵M代入它的特征多项式里，得到的结果f(M)是零矩阵。这个学过线性代数的人都知道，不过既然这篇纯属自娱自乐，我就来扯扯这个定理。

关于这个定理我看到过三个证明。

第一个大概是最普通的吧，假设A是代数闭域，比如复数域，我们可以把M化成Jordan标准形，于是定理是显然的。对于A是一般可换环的情形，我们可以把n阶矩阵的各项(a_ij)看成是独立变量，然后只要在环Z[a₁₁,a₁₂,...,a_nn]上证明即可。这是一个整环，所以我们可以考虑它的分数域，然后把这个分数域埋入一个代数闭域里（我们有大定理说这总是可能的），然后就可以把矩阵化成Jordan标准形了。不过如此证明实在有点杀鸡用牛刀，不值得提倡。

第二个证明是这样子的：令N=Ix-M，把N的余因子矩阵记为N'。N'的各项都可以写成x的n-1次多项式，所以N'可以写成矩阵系数的多项式N'=P_n-1x^n-1+...+P₁x+P₀。由NN'=N'N=f(x)I，我们得到矩阵系数多项式的恒等式：
(Ix-M)(P_n-1x^n-1+...+P₁x+P₀)=(P_n-1x^n-1+...+P₁x+P₀)(Ix-M)=f(x)I

特别的，由前一半等式知道M和P_i (i=0,1,...,n-1)是可换的，所以我们可以把M代入x（注意可换性是重要的，否则的话是不能代入的！），于是得到f(M)为零矩阵。这个证明很有技巧性不大容易明白，不过比第一个证明是要简洁明快的多了。

第三个证明是我最喜欢的，在我看来这才是直奔问题的本质：关键在于，要找到一个正当的借口把矩阵代入到det(Ix-M)中的x里面去。这个借口是这样的：我们可以把M看成是A上的n阶自由加群F的线性变换。把这个线性变换记为T，然后考虑A上的多项式环A[x]，把x的作用规定为T（这就是借口！），则F可以看成是A[x]-加群。设F的基为e₁,...,e_n，令M=(a_ij)，根据定义我们有：
$ $$ x \left(\begin{array}{c} \mbox{\textbf{e}}_{1} \\ \mbox{\textbf{e}}_{2} \\ \vdots \\ \mbox{\textbf{e}}_{n} \\ \end{array}\right) = \left(\begin{array}{rrcc} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & & a_{2n} \\ \vdots & & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{array}\right) \left(\begin{array}{c} \mbox{\textbf{e}}_{1} \\ \mbox{\textbf{e}}_{2} \\ \vdots \\ \mbox{\textbf{e}}_{n} \\ \end{array}\right) $$ $
注意这里列向量的各项是F的元（而不是A的元！），并且把F看成是A[x]上的加群。左边减右边即得：
$ $$ \left(\begin{array}{rrcc} x-a_{11} & -a_{12} & \ldots & -a_{1n} \\ -a_{21} & x-a_{22} & & -a_{2n} \\ \vdots & & \ddots & \vdots \\ -a_{n1} & -a_{n2} & \cdots & x-a_{nn} \\ \end{array}\right) \left(\begin{array}{c} \mbox{\textbf{e}}_{1} \\ \mbox{\textbf{e}}_{2} \\ \vdots \\ \mbox{\textbf{e}}_{n} \\ \end{array}\right) = \left(\begin{array}{c} \mbox{\textbf{0}} \\ \mbox{\textbf{0}} \\ \vdots \\ \mbox{\textbf{0}} \\ \end{array}\right) $$ $
再在左右两边乘上(Ix-M)的余因子矩阵，就有
$ $$ f(x) \left(\begin{array}{c} \mbox{\textbf{e}}_{1} \\ \mbox{\textbf{e}}_{2} \\ \vdots \\ \mbox{\textbf{e}}_{n} \\ \end{array}\right) = \left(\begin{array}{c} \mbox{\textbf{0}} \\ \mbox{\textbf{0}} \\ \vdots \\ \mbox{\textbf{0}} \\ \end{array}\right) $$ $
这意思是说，f(x)作用于F，结果是0。由于x的作用就是M所对应的线性变换，于是当然f(x)就是f(M)所对应的线性变换。所以f(M)是零矩阵。
这个证明很能体现抽象代数的威力，不过大概不适合初学者吧。

下面我要说说我自己的证明。这个证明既不易懂，也不简洁，更不适合初学者，如果说它有什么优点，大概在于其动机的天真无邪还有其过程的坚持不懈吧。呵呵。

这个证明的动机是这样的：如果把矩阵M的各项a_ij看成是独立变量，那么（按照定义来原原本本地计算）f(M)的各项都是关于a_ij的多项式。Cayley-Hamilton定理说，这些多项式都正好等于0。那么这些多项式究竟具体是什么样子的呢？它们各项的系数又是怎么互相抵消，正好为0的呢？这个抵消是显而易见的还是不那么显然的？我们是否可以从这个方向上给出Cayley-Hamilton定理的一个证明？
下面我们将会看到，这个各项系数的抵消确实不那么显然，不过仍然是可以理解的。通过单纯地按照定义来计算f(M)的各项而给出Cayley-Hamilton定理的证明，确实是可能的。且听我慢慢道来。

设M=(a_ij)，那么易知M^k的(i,j)项是：
$\sum_{l_1,l_2,\ldots,l_k}a_{il_1}a_{l_1l_2}\cdots a_{l_{k-1}l_k}a_{l_kj}$
其中 $l_1,l_2,\ldots,l_k$ 都分别从1跑到n。这个和中的每一项可以用一条从i走到j的长度为k的路径来表示，这条路径的每一段连接了1到n中（允许重复）的两个标号。

另一方面，特征多项式f(x)的k次项系数，是把矩阵(-M)去掉第h₁行h₁列，第h₂行h₂列，...第h_k行h_k列之后得到的所有小矩阵的行列式之和。这里h₁,h₂,...,h_k跑过在1到n里选取k个的所有组合。把从1到n中去掉h₁,h₂,...,h_k后得到的补集记为{g₁,g₂,...,g_n-k}，然后把行列式完全展开地写出来，我们就得到f(x)的k次项系数是：
$\sum_{g_1,g_2,\ldots,g_{n-k}}\sum_{\sigma}(-1)^{n-k}\mbox{sign(}\sigma\mbox{)}\cdot a_{g_1g_{\sigma(1)}}a_{g_2g_{\sigma(2)}}\cdots a_{g_{n-k}g_{\sigma(n-k)}}$
其中g₁<g₂<...<g_n-k跑过在1到n里选取n-k个的所有组合， $\sigma$ 跑过1到(n-k)上的所有置换。大家都知道置换可以写成互不相连的循环的积。如果 $\sigma$ 分解成p个循环的积，容易知道 $(-1)^{n-k}\mbox{sign(}\sigma\mbox{)}=(-1)^p$ 。所以上面这个和中的每一项可以表示成几个互不相交的圈，项的符号由圈的个数决定。

由以上的考察可知f(M)的各项都是a_ij的n次齐次多项式，为了看出这多项式是怎么抵消为0的，我们考察每个n次单项式前面的系数。一个这样的单项式可以由一个有向图来表达。图的顶点是从1到n的标号，一条从顶点i到顶点j的边表示这单项式的一个因子a_ij。显然这样一个图共有n条边。

那么对于f(M)的第(i,j)项，每一个这样的n条边的有向图（所对应的单项式）的系数是多少呢？由以上的考察可知，如果我们能在这个图中找到一条从i到j的路径，并且在这个图上把这路径中的边都去掉以后剩下来的正好是几个互不相交的圈，那么它就正好对应于我们要计算的和中的一项。这一项的符号由圈的个数决定。

总结一下我们做出下面的定义：
对于有n个顶点、并且顶点被从1到n编了号的一个有向图G，把 $\Lambda(G)_{i,j}^{p}$ 定义为G中满足下列性质的所有路径P的集合：
1。P的始点为i，终点为j。并且P中没有重复的边。
2。把G中属于P的边去掉，得到的图正好由p个互不相交的圈组成。

于是Cayley-Hamilton定理被翻译成下面这个定理：
对于有n个顶点、并且顶点被从1到n编了号的任意一个有向图G和任意的(i,j)，如果G有n条边，则
$\sum_{p=0}^{\infty}(-1)^p\#\Lambda(G)_{i,j}^{p}=0$
其中 $\#\Lambda(G)_{i,j}^{p}$ 表示集合 $\Lambda(G)_{i,j}^{p}$ 的元的个数。

这是怎么回事？我们有办法理解这个看起来有点神秘的等式吗？如果你中毒和我一样深或者比我还要深，一定会看出这个等式的左边看起来象是一个欧拉数的形状。这个欧拉数等于0，暗示了一个恰当序列（exact sequence）的存在。是的，你没猜错，确实有这样一个恰当序列，而且上面要求G有n条边的这个条件其实也不是本质性的。这就是下面这个定理：

对于任意一个顶点编号的有向图G和任意的(i,j)，把 $\mbox{\textbf{Z}}\Lambda(G)_{i,j}^{p}$ 定义为以 $\Lambda(G)_{i,j}^{p}$ 中元为基生成的自由Abel群。只要G不是由一条从i到j的简单开路径和若干个圈的非交和构成的（如图一的那种情况。注意这种情况下边数总是比顶点数少1），那么就存在一个恰当序列：
$0\leftarrow \mbox{\textbf{Z}}\Lambda(G)_{i,j}^{0}\leftarrow \mbox{\textbf{Z}}\Lambda(G)_{i,j}^{1}\leftarrow\cdots\leftarrow\mbox{\textbf{Z}}\Lambda(G)_{i,j}^{p-1}\stackrel{d_p}{\leftarrow}\mbox{\textbf{Z}}\Lambda(G)_{i,j}^{p}\leftarrow\cdots\mbox{ (exact)}$

证明。首先定义微分 $d_p:\mbox{\textbf{Z}}\Lambda(G)_{i,j}^{p}\rightarrow\mbox{\textbf{Z}}\Lambda(G)_{i,j}^{p-1}$ 。对于 $\mbox{\textbf{Z}}\Lambda(G)_{i,j}^{p}$ 的一个基也就是 $\Lambda(G)_{i,j}^{p}$ 的一个元P，把G中属于P的边去掉得到p个互不相交的圈。假设这p个圈中与路径P相交的共有q个。把这q个圈按照这样的方式来排一个序：对于两个圈R和S，我们从顶点i开始沿着路径P往前走，如果最先碰到的是R的顶点，则规定R<S，反之亦然。如此我们把这q个圈从小到大依次记为C₁,C₂,...,C_q。对于这里面的每一个圈C_r，从顶点i开始沿着P往前走，在最初碰到C_r的那个顶点处停下，绕着C_r转上一圈，然后再继续沿着路径P走下去，这样就定义了一个新的路径L_r，显然L_r是 $\Lambda(G)_{i,j}^{p-1}$ 的元。于是d_p定义为：
$d_p(P)=\sum_{r=1}^{q}(-1)^{r-1}L_r$
容易知道 $d_{p-1}\circ d_p=0$ ，所以这确实是一个chain complex（锁复形？）。下面要证明它的恰当性。为此我们这样来构造一个chain homotopy（锁同伦？） $\Phi_p:\mbox{\textbf{Z}}\Lambda(G)_{i,j}^{p}\rightarrow\mbox{\textbf{Z}}\Lambda(G)_{i,j}^{p+1}$ ：和上面一样，对于 $\Lambda(G)_{i,j}^{p}$ 的一个元P，把G中属于P的边去掉得到p个互不相交的圈。从顶点i开始沿着P往前走，设依次经过的顶点为i=v₀,v₁,...,v_r,...,v_s,... 假设v_s是第一个重复经过的顶点，比如说v_s=v_r，并且在从i到v_s的过程中没有和任何一个圈相交过，那么我们这样来定义一条新的路径K：从顶点i开始沿着P往前走，在到达v_r之后跳过v_r到v_s中间的部分直接从v_s开始往后走下去。显然这个新路径是 $\Lambda(G)_{i,j}^{p+1}$ 的元。如果没有发生上面假设中的情形，则把K理解为0。这样我们把 $\Phi_p$ 定义为 $\Phi_p(P)=K$ 。
为了验证这确实是一个chain homotopy，我们只需要说明 $\Phi_{p-1}\circ d_p(P)+d_{p+1}\circ \Phi_p(P)=P$ 。这应该是不难确认的。证毕。

由同调代数的一般论我们知道恰当序列的欧拉数必然等于0。所以这个定理把Cayley-Hamilton定理作为一个推论。如此我们就给出了Cayley-Hamilton定理的一个组合论的解释，并且用同调代数的方法证明了它。

最后给一个具体的例子。考虑2阶的情形。
令 $M= \left(\begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{array}\right) $ 。则f(M)=
$ \left(\begin{array}{cc} a_{11}a_{11}+a_{12}a_{21} & a_{11}a_{12}+a_{12}a_{22} \\ a_{21}a_{11}+a_{22}a_{21} & a_{21}a_{12}+a_{22}a_{22} \\ \end{array}\right) $$ $$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -(a_{11}+a_{22}) \left(\begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{array}\right) +(a_{11}a_{22}-a_{12}a_{21}) $
考虑f(M)的第(1,2)项中单项式a₁₂a₂₂的系数。这个单项式对应的图画在图二中。从1到2，再在2上绕一圈这样一条路径对应与M²中的那一项。从1直接到2的路径对应于-(a₁₁+a₂₂)M中的那一项，图中去掉这条路径以后剩下的那个圈正是f(x)的一次项系数里的a₂₂。因为是1个圈，所以要在乘上-1。于是两项加起来正好等于0。

周一, 2007-06-11 17:23 — 过客 (未验证)

There's in fact a better

There's in fact a better statement of the C-H theorem, which says that every linear operator over a finite dimensional vector space satisfies its own characteristic equation.

[Szekeres' book]

周二, 2007-06-12 10:13 — 过客 (未验证)