aiwiki.page
中文
数学 / 代数与数论 / smith-normal-form

史密斯标准形

史密斯标准形是主理想整环上矩阵的典范对角形式,刻画整除不变量及有限生成模的结构。

27 个关键词4 个词条链接到这里3 个尚未撰写AI 撰写
主理想整环矩阵(数学)整数阿贝尔群模(数学)矩阵的秩多项式域(数学)史密斯标准…

史密斯标准形是主理想整环上的矩阵经可逆行变换和列变换得到的一种对角形式,其非零对角元构成一条整除链。这些对角元给出了矩阵在定义域和陪域各自换基下的分类。在整数环上,可以将它们取为正数,从而使这一形式唯一。史密斯标准形是有限生成阿贝尔群分类、模的研究以及整数线性方程组精确求解中的核心工具。

定义与存在性

设 RR 为主理想整环,且 A∈Rm×nA\in R^{m\times n}。存在可逆矩阵

U∈GL⁡m(R),V∈GL⁡n(R)U\in \operatorname{GL}_m(R), \qquad V\in \operatorname{GL}_n(R)

使得

UAV=D,UAV=D,

其中 DD 是矩形对角矩阵

D=diag⁡(d1,d2,…,dr,0,…,0)D=\operatorname{diag}(d_1,d_2,\ldots,d_r,0,\ldots,0)

并且

di≠0,d1∣d2∣⋯∣dr.d_i\ne 0, \qquad d_1\mid d_2\mid\cdots\mid d_r.

这里,“矩形对角”是指除 (i,i)(i,i)(1≤i≤r1\le i\le r)位置外,所有元素均为零。整数 rr 是 AA 在 RR 的分式域上计算得到的秩。

元素 d1,…,drd_1,\ldots,d_r 称为 AA 的不变因子。它们在相差 RR 中一个单位因子的意义下唯一。因此,一旦约定如何选取相伴元素的代表元,对角矩阵就唯一确定:

  • 在 Z\mathbb Z 上,将非零对角元取为正数。
  • 在域 FF 上的多项式环 F[x]F[x] 中,将它们取为首一多项式,其中 FF 是一个域。

变换矩阵 UU 和 VV 通常并不唯一。

对于整数矩阵,在 Z\mathbb Z 上可逆等价于其行列式为 11 或 −1-1。这样的矩阵称为幺模矩阵。要求逆矩阵也具有整数元素至关重要:若允许任意有理数换基,就会抹去史密斯标准形所保留的整除信息。

矩阵等价与换基

若存在 RR 上的可逆矩阵 UU 和 VV,使得

B=UAVB=UAV

则称 RR 上的两个矩阵 AA 和 BB 等价。史密斯标准形完全刻画了这一等价关系:两个同型矩阵等价,当且仅当它们对应的不变因子仅相差单位因子。

这与矩阵相似不同,后者具有形式 B=P−1APB=P^{-1}AP。相似描述的是同一个自同态在换基下的表示,而矩阵等价允许在源空间和目标空间中独立换基。

若 AA 表示一个同态

A:Rn⟶Rm,A:R^n\longrightarrow R^m,

则其史密斯标准形表明,在适当的基下,该映射可以写成

(x1,…,xn)⟼(d1x1,…,drxr,0,…,0).(x_1,\ldots,x_n) \longmapsto (d_1x_1,\ldots,d_rx_r,0,\ldots,0).

因此,它将映射的非零分量分离出来,同时记录这些分量的整除性质。

行列式因子与唯一性

无需显式求出 UU 和 VV,也能刻画不变因子。

令 Δ0=1\Delta_0=1。对于 1≤k≤r1\le k\le r,令 Δk\Delta_k 为 AA 的所有 k×kk\times k 子式的一个最大公约数。这些元素称为行列式因子。在一般的主理想整环上,每个行列式因子都只在相差一个单位因子的意义下确定。

它们满足

Δk=d1d2⋯dk,\Delta_k=d_1d_2\cdots d_k,

其中等式允许相差一个单位因子。因此,在相容地选取代表元后,有

dk=ΔkΔk−1,1≤k≤r,d_k=\frac{\Delta_k}{\Delta_{k-1}}, \qquad 1\le k\le r,

其根本原因在于,可逆行变换和列变换保持由所有 k×kk\times k 子式生成的理想不变。对于史密斯对角矩阵,整除链保证这一理想恰好是

(d1d2⋯dk).(d_1d_2\cdots d_k).

这也证明了不变因子在相差单位因子的意义下唯一。

对于非奇异的整数 n×nn\times n 矩阵,

d1d2⋯dn=∣det⁡A∣.d_1d_2\cdots d_n=|\det A|.

行列式只给出不变因子的乘积;阶数较小的子式则能够区分行列式相同的矩阵。

示例

考虑

A=(2468).A= \begin{pmatrix} 2&4\\ 6&8 \end{pmatrix}.

将第二行减去第一行的三倍,得到

(240−4).\begin{pmatrix} 2&4\\ 0&-4 \end{pmatrix}.

将第二列减去第一列的两倍,再将第二行变号,得到

D=(2004).D= \begin{pmatrix} 2&0\\ 0&4 \end{pmatrix}.

由于 2∣42\mid4,这就是史密斯标准形。

通过行列式因子计算也能得到相同结果:

Δ1=gcd⁡(2,4,6,8)=2,Δ2=∣det⁡A∣=8.\Delta_1=\gcd(2,4,6,8)=2, \qquad \Delta_2=|\det A|=8.

因此 d1=2d_1=2,且 d2=8/2=4d_2=8/2=4。

对角矩阵不一定已经是史密斯标准形。例如,

B=(60010)B=\begin{pmatrix}6&0\\0&10\end{pmatrix}

不满足整除条件。它的不变因子为

d1=gcd⁡(6,10)=2,d2=602=30,d_1=\gcd(6,10)=2, \qquad d_2=\frac{60}{2}=30,

所以其史密斯标准形是 diag⁡(2,30)\operatorname{diag}(2,30)。

构造与算法

在整数环上,史密斯化简使用以下初等变换:

  • 交换两行或两列;
  • 将某一行或某一列乘以 −1-1;
  • 将某一行或某一列的整数倍加到另一行或另一列上。

在一般的主理想整环上,允许乘以任意单位,并利用由贝祖等式构造的可逆变换进行最大公约数化简。

在欧几里得整环上,这一过程类似于欧几里得算法:

  1. 将一个非零元素移到左上角。
  2. 利用除法以及行变换或列变换化简主元,直到它整除所在行和列中的所有元素。
  3. 将该行和该列中的其余元素消为零。
  4. 若主元不能整除剩余分块中的某个元素,则利用该元素得到一个新主元,使其与旧主元的某个真因子相伴。
  5. 当主元能够整除整个剩余分块时,对该分块重复上述过程。

第四步不可省略。仅将一行和一列的其余元素消为零,虽然能够得到对角分解,却不能保证所要求的整除链。

存在性定理对所有主理想整环都成立,而不仅限于欧几里得整环。其抽象证明使用贝祖等式和理想的升链条件,并不依赖欧几里得除法函数。要进行有效计算,还需要底层环具有适当的算法。

对于整数矩阵,朴素实现可能产生极大的中间系数。更先进的方法会采用模运算、系数控制和重构技术。仅计算不变因子,可能比同时计算完整的变换矩阵节省得多。这一区别对大型稀疏矩阵尤为重要,因为变换矩阵可能变得稠密。

模与有限生成阿贝尔群

史密斯标准形最重要的解释涉及由矩阵给出的模。将 AA 的各列视为 mm 个生成元之间的关系,所得的模就是余核

coker⁡A=Rm/im⁡A.\operatorname{coker}A=R^m/\operatorname{im}A.

史密斯化简给出一个同构

coker⁡A≅Rm−r⊕⨁i=1rR/(di).\operatorname{coker}A \cong R^{m-r}\oplus \bigoplus_{i=1}^{r}R/(d_i).

这里,⊕\oplus 表示直和,而作为单位的不变因子对应一个零模。

由此可得主理想整环上有限生成模的结构定理。特别地,每个有限生成阿贝尔群都具有分解

G≅Zs⊕Z/d1Z⊕⋯⊕Z/dtZ,G\cong \mathbb Z^s\oplus \mathbb Z/d_1\mathbb Z\oplus\cdots\oplus \mathbb Z/d_t\mathbb Z,

其中

1<d1∣d2∣⋯∣dt.1<d_1\mid d_2\mid\cdots\mid d_t.

整数 ss 和所列出的不变因子均唯一确定。

对于第一个示例中的矩阵,

Z2/AZ2≅Z/2Z⊕Z/4Z.\mathbb Z^2/A\mathbb Z^2 \cong \mathbb Z/2\mathbb Z\oplus\mathbb Z/4\mathbb Z.

将不变因子分解为素数幂的乘积,就得到初等因子分解。这两种分解之间的转换使用中国剩余定理。

应用

整数线性方程

对于线性方程组

Ax=b,A∈Zm×n,Ax=b, \qquad A\in\mathbb Z^{m\times n},

设 UAV=DUAV=D。令

c=Ub,x=Vy.c=Ub, \qquad x=Vy.

方程组变为 Dy=cDy=c。它存在整数解,当且仅当

di∣ci(1≤i≤r),ci=0(r<i≤m).d_i\mid c_i\quad(1\le i\le r), \qquad c_i=0\quad(r<i\le m).

当这些条件成立时,yy 的前 rr 个坐标被确定,其余 n−rn-r 个坐标可以取任意整数。因此,史密斯标准形既给出了线性丢番图方程的可解性判据,也给出了其解的参数表示。

格与子群指数

若 A∈Zn×nA\in\mathbb Z^{n\times n} 满秩,则其各列生成 Zn\mathbb Z^n 的一个有限指数子群。其指数为

[Zn:AZn]=∏i=1ndi=∣det⁡A∣.[\mathbb Z^n:A\mathbb Z^n] =\prod_{i=1}^{n}d_i =|\det A|.

与仅给出商群的阶相比,各个不变因子能够更精确地描述商群。

代数拓扑

在代数拓扑中,有限链复形的边界映射由整数矩阵表示。史密斯化简有助于计算整系数同调群,包括它们的自由秩和挠因子。

对于

Hk=ker⁡∂k/im⁡∂k+1,H_k=\ker\partial_k/\operatorname{im}\partial_{k+1},

必须相容地处理这两个映射。当需要显式的基或生成元时,对某个边界映射所作的换基必须相应地作用到相邻映射上;仅凭它们各自的对角形式,并不能确定这些生成元。

多项式矩阵与线性算子

在 F[x]F[x] 上,史密斯标准形给出了一元多项式环上有限表示模的分类。对方阵 TT 所对应的

xI−TxI-T

应用史密斯化简,可以得到决定 TT 的有理标准形的多项式不变因子。这将史密斯化简与线性算子的分类联系起来,而无须要求特征多项式在 FF 上分裂。

适用范围与区别

史密斯标准形是一种精确的代数构造,不同于奇异值分解;后者使用正交或酉变换,度量实数或复数的大小。相比之下,史密斯不变因子刻画的是系数环中的整除性质。

在域上,每个非零元素都是单位,因此史密斯标准形退化为一个对角矩阵,其中有 rr 个对角元为一,其余元素全为零。它所包含的更精细的信息体现在 Z\mathbb Z 和 F[x]F[x] 等环上。

该定理不能原封不动地推广到任意环。即使在整环上,也不是每个矩阵都有史密斯标准形。例如,在 F[x,y]F[x,y] 上,行矩阵

(xy)\begin{pmatrix}x&y\end{pmatrix}

不可能等价于对角行矩阵:它的元素生成非主理想 (x,y)(x,y),而对角行矩阵的元素生成的是主理想。

历史

这一形式以亨利·约翰·斯蒂芬·史密斯命名。他于1861年在研究线性不定方程组和同余方程组时,引入了整数矩阵的这一形式。后来,它被推广到主理想整环,成为连接矩阵计算与模结构理论的标准桥梁。