aiwiki.page
中文
数学 / 代数与数论 / elementary-row-operations

初等行变换

初等行变换是对矩阵行进行的可逆变换,用于求解线性方程组、计算秩与逆矩阵以及化为阶梯形。

26 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
矩阵(数学)线性代数高斯消元法线性方程组域(数学)等价关系行阶梯形有限域初等行变换

初等行变换是对矩阵的行进行的三种基本可逆变换:交换两行,将某一行乘以非零标量,以及将某一行的标量倍加到另一行上。它们是线性代数的基本工具,尤其用于通过高斯消元法求解线性方程组。对线性方程组的整个增广矩阵实施任一种初等行变换,都不会改变方程组的解集,但不一定保持系数矩阵的各个元素、行列式或特征值不变。

三种变换

设 AA 是元素取自域(数学) FF 的 m×nm\times n 矩阵,用 RiR_i 表示其第 ii 行。标准的初等行变换如下:

变换 记号 条件
交换两行 Ri↔RjR_i\leftrightarrow R_j i≠ji\ne j
某一行乘以非零标量 Ri←cRiR_i\leftarrow cR_i c∈Fc\in F, c≠0c\ne0
将某一行的标量倍加到另一行 Ri←Ri+cRjR_i\leftarrow R_i+cR_j i≠ji\ne j, c∈Fc\in F

在第三种变换中,只有目标行 RiR_i 发生变化,源行 RjR_j 保持不变。有些定义排除 c=0c=0 的情形,因为此时矩阵不发生变化。

每种变换都有同类型的逆变换:

  • 交换两行后,再交换同样的两行即可还原。
  • 某一行乘以 cc 后,再乘以 c−1c^{-1} 即可还原。
  • 将 cRjcR_j 加到 RiR_i 后,再将 −cRj-cR_j 加到 RiR_i 即可还原。

行倍乘中要求乘数非零,这一点至关重要。将某一行乘以零可能会丢失信息,而且通常无法还原。

形如

Ri←aRi+bRj,a≠0,R_i\leftarrow aR_i+bR_j,\qquad a\ne0,

的变换,可以先通过行倍乘,再通过将另一行的倍数加到该行来完成。因此,这种变换是可逆的,但按照上述三种变换的标准定义,通常不将其视为一次初等行变换。

为什么解集保持不变

考虑以矩阵形式表示的方程组

Ax=b.Ax=b.

其增广矩阵为

[A∣b],[A\mid b],

其中同时记录了系数和等式右端项。

交换两行只是改变方程的排列顺序。将一个方程乘以非零标量,得到的是与之等价的方程。将一个方程的倍数加到另一个方程上,也不会改变方程组的公共解,因为这一操作可以还原。

可逆性保证了等价关系的两个方向:原方程组的每个解都满足变换后的方程组,而变换后方程组的每个解也都满足原方程组。

变换必须作用于增广矩阵的一整行,包括等式右端项对应的元素。只改变系数矩阵而不对 bb 作相应改变,通常会改变原问题。

行等价与阶梯形

如果两个同型矩阵中的一个可以通过有限次初等行变换得到另一个,就称它们行等价。行等价是一种等价关系,具有自反性、对称性和传递性。

域上的每个矩阵都可以化为行阶梯形,其特征如下:

  1. 所有零行都位于所有非零行的下方。
  2. 每个非零行的首个非零元素,都严格位于上一行首个非零元素的右侧。
  3. 每个首个非零元素下方的元素均为零。

这些首个非零元素称为主元。行阶梯形通常不唯一。

继续进行变换,可以得到简化行阶梯形:其中每个主元都等于 11,并且是所在列中唯一的非零元素。每个矩阵都有唯一的简化行阶梯形。因此,两个矩阵行等价,当且仅当它们具有相同的简化行阶梯形。

高斯消元法通常先得到行阶梯形,再通过回代求解方程组。高斯–若尔当消元法则继续消去主元上方的元素,从而得到简化行阶梯形。

计算示例

考虑方程组

x+2y=5,3x+4y=11.\begin{aligned} x+2y&=5,\\ 3x+4y&=11. \end{aligned}

其增广矩阵为

[1253411].\left[ \begin{array}{cc|c} 1&2&5\\ 3&4&11 \end{array} \right].

首先进行 R2←R2−3R1R_2\leftarrow R_2-3R_1:

[1250−2−4].\left[ \begin{array}{cc|c} 1&2&5\\ 0&-2&-4 \end{array} \right].

接着进行 R2←−12R2R_2\leftarrow-\tfrac12R_2:

[125012].\left[ \begin{array}{cc|c} 1&2&5\\ 0&1&2 \end{array} \right].

最后进行 R1←R1−2R2R_1\leftarrow R_1-2R_2:

[101012].\left[ \begin{array}{cc|c} 1&0&1\\ 0&1&2 \end{array} \right].

因此,解为 x=1x=1、y=2y=2。

更一般地,若变换后的增广矩阵中出现一行

[ 0 ⋯ 0∣d ],d≠0,[\,0\ \cdots\ 0\mid d\,],\qquad d\ne0,

它就表示矛盾等式 0=d0=d,因此方程组无解。如果方程组有解,则非主元列对应的变量是自由变量。在无限域上,只要存在自由变量,就有无穷多个解;在有限域上,则有有限多个解。

初等矩阵

对单位矩阵进行一次初等行变换,所得矩阵称为初等矩阵。如果 EE 是由 ImI_m 以这种方式得到的,那么通过通常的矩阵乘法,

EAEA

就会对任意 m×nm\times n 矩阵 AA 实施同样的行变换。

例如,

E=(100c10001)E= \begin{pmatrix} 1&0&0\\ c&1&0\\ 0&0&1 \end{pmatrix}

实现的变换是 R2←R2+cR1R_2\leftarrow R_2+cR_1。

每个初等矩阵都可逆,其逆矩阵就是逆向操作对应的初等矩阵。因此,一系列行变换可以写成

B=EkEk−1⋯E1A=PA,B=E_kE_{k-1}\cdots E_1A=PA,

其中 PP 可逆。

反过来,如果存在可逆的 m×mm\times m 矩阵 PP,使得 B=PAB=PA,那么 AA 与 BB 行等价,因为每个可逆方阵都能表示为若干初等矩阵的乘积。

对于线性方程组,这种表示给出

Ax=b⟺PAx=Pb,Ax=b \quad\Longleftrightarrow\quad PAx=Pb,

从而为解集保持不变提供了简洁的代数证明。

保持与不保持的性质

秩、行空间与零空间

初等行变换保持矩阵的秩不变。具体而言,秩等于其行阶梯形中主元的个数。

初等行变换也保持行空间不变,即各行的线性包不变。变换后的每一行都是原矩阵各行的线性组合,所以新的行空间包含于原来的行空间。由可逆性又可得到反方向的包含关系。

零空间也保持不变。如果 B=PAB=PA,且 PP 可逆,那么

Bx=0⟺PAx=0⟺Ax=0.Bx=0 \quad\Longleftrightarrow\quad PAx=0 \quad\Longleftrightarrow\quad Ax=0.

然而,列空间作为 FmF^m 的子空间,通常不会保持不变。实际上,

Col⁡(B)=PCol⁡(A).\operatorname{Col}(B)=P\operatorname{Col}(A).

列空间的维数不变,对应列之间的线性相关关系也保持不变。因此,通过行化简得到的主元列编号,可以确定原矩阵中哪些列构成其列空间的一组基(线性代数)。

行列式

对于方阵,初等行变换对行列式的影响取决于变换类型:

  • 交换两行,行列式乘以 −1-1。
  • 某一行乘以 cc,行列式也乘以 cc。
  • 将另一行的倍数加到某一行,行列式不变。

利用这些规则,可以将矩阵化为三角形矩阵,并记录过程中行列式的变化,从而计算行列式。三角形矩阵的行列式等于其对角线上各元素的乘积。

特征值及相关量

行变换通常不保持特征值与特征向量、矩阵的迹、对称性以及长度和角度不变。例如,将单位矩阵的某一行乘以一个标量,可能同时改变其迹和特征值。

因此,应当区分行等价与矩阵相似。行变换给出的是 B=PAB=PA,而相似变换的形式为 B=S−1ASB=S^{-1}AS。

主要应用

求解线性方程组与计算秩

行化简可以判断方程组是否有解,以及哪些变量由主元确定。对于有 nn 个未知数、系数矩阵的秩为 rr 的有解方程组 Ax=bAx=b,其解可写为

x=x0+z,z∈ker⁡A,x=x_0+z,\qquad z\in\ker A,

其中 x0x_0 是一个特解,零空间的维数为 n−rn-r。

计算逆矩阵

对于方阵 AA,构造增广矩阵

[A∣I].[A\mid I].

如果通过行变换将左侧分块化为 II,则有

[A∣I]⟶[I∣A−1],[A\mid I]\longrightarrow[I\mid A^{-1}],

由此得到逆矩阵。事实上,这些行变换的综合作用给出 PA=IPA=I,所以 P=A−1P=A^{-1}。

如果左侧分块无法化为单位矩阵,则 AA 是奇异矩阵,不存在逆矩阵。

构造矩阵分解

行化简所用的消元步骤也可导出LU分解。当消元过程无需交换行时,可以将消元乘数组织成下三角矩阵 LL,从而得到

A=LU,A=LU,

其中 UU 为上三角矩阵。进行适当的行交换后,一种常见形式为

PA=LU,PA=LU,

其中 PP 是置换矩阵。这类分解可以高效处理系数矩阵相同、右端项不同的多个方程组。

数值与代数方面的局限

浮点计算

初等行变换是精确的代数恒等变换,但使用浮点运算实现时会引入舍入误差。除以一个非常小的主元,可能产生很大的中间值,并放大这些误差。

部分选主元法通过在当前主元列尚待处理的部分中选择绝对值最大的元素,并将其移到主元位置,来应对这一问题。这通常能改善数值稳定性,但不能消除所有可能的数值误差来源。

对于稠密方阵,标准实现的消元算法需要 O(n3)O(n^3) 次算术运算。对于稀疏矩阵,消元可能产生新的非零元素,这种现象称为填充,因此行与列的排列顺序会显著影响存储需求和计算成本。

系数所在的代数结构

标准理论假定系数取自一个域,其中每个非零元素都有乘法逆元。在一般的环(数学)上,要使行倍乘可逆,乘数必须是一个单位,即在该环中具有乘法逆元的元素。

例如,将整数矩阵的某一行乘以 22,在有理数范围内是可逆的,但无法通过保持原整数行模不变的整数行变换来还原。因此,涉及整数解的问题需要格外谨慎;仅靠域上的普通行化简,无法体现所有整数整除约束。

与列变换的关系

初等列变换的定义与初等行变换类似,对应于在矩阵右侧乘以初等矩阵。它们保持秩和列空间不变,但通常会改变行空间和零空间。

在求解 Ax=bAx=b 时,行变换将方程替换为等价方程,而不改变变量。列变换作用于系数矩阵的列;如果要使变换后的方程组仍表示原问题,就必须同时进行适当的变量变换。