aiwiki.page
中文
数学 / 代数与数论 / row-echelon-form

行阶梯形

行阶梯形是矩阵首个非零元呈阶梯状排列的形式,用于求解线性方程组、计算秩和判定线性相关性。

22 个关键词2 个词条链接到这里AI 撰写
线性代数矩阵(数学)域(数学)线性方程组实数复数高斯消元法有限域行阶梯形

在线性代数中,行阶梯形是矩阵的一种形式:所有零行位于底部,且每个非零行的首个非零元都严格位于上一非零行首个非零元的右侧。这种阶梯状排列使矩阵的结构更易于分析。域(数学)上的每个矩阵都可以通过初等行变换化为行阶梯形。它是求解线性方程组、计算秩以及判定行与列之间线性相关关系的核心工具。

定义

设 AA 是某个域上的 m×nm\times n 矩阵,例如实数域或复数域。非零行的首非零元是指从左向右读时遇到的第一个非零元素。

如果矩阵满足以下条件,就称其为行阶梯形矩阵:

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

这些条件意味着,每个首非零元下方的所有元素均为零。教科书中的定义常将这一推论列为第三个条件。

首非零元通常称为主元,其所在位置称为主元位置。包含主元位置的列称为主元列。在描述消元算法时,“主元”也可以指为执行某一步消元而选定的元素。

例如,

U=(2−1340005210000−300000)U= \begin{pmatrix} 2&-1&3&4&0\\ 0&0&5&2&1\\ 0&0&0&0&-3\\ 0&0&0&0&0 \end{pmatrix}

是行阶梯形矩阵。其主元位于第 11、33 和 55 列。

零矩阵也属于行阶梯形矩阵:由于没有非零行,关于非零行的要求自然成立。

约定

按照本文采用的一种常见定义,主元不必等于 11。有些教材要求每个首非零元均为 11,并将所得形式称为行阶梯形或规范行阶梯形。这些约定之间的差别仅在于是否对非零行进行数乘。

行阶梯形与上三角形并不相同。上三角矩阵的主对角线下方元素均为零,但它可能不满足阶梯状排列的条件。例如,

(0102)\begin{pmatrix} 0&1\\ 0&2 \end{pmatrix}

是上三角矩阵,却不是行阶梯形矩阵,因为两行的首非零元位于同一列。

初等行变换与消元

初等行变换包括:

  • 交换两行。
  • 将某一行乘以一个非零标量。
  • 将某一行的标量倍加到另一行上。

每种变换都是可逆的。能够通过一系列此类变换相互转化的矩阵称为行等价的矩阵。

高斯消元法通过从左到右逐列处理来构造阶梯形矩阵。对于尚未处理的部分中含有非零元素的每一列,算法选取一个主元,必要时通过换行将其移至适当位置,然后消去它下方的元素。若某列尚未处理的部分没有非零元素,则跳过该列。

例如,

A=(121243132).A= \begin{pmatrix} 1&2&1\\ 2&4&3\\ 1&3&2 \end{pmatrix}.

施行变换

R2←R2−2R1,R3←R3−R1R_2\leftarrow R_2-2R_1, \qquad R_3\leftarrow R_3-R_1

得到

(121001011).\begin{pmatrix} 1&2&1\\ 0&0&1\\ 0&1&1 \end{pmatrix}.

交换最后两行,得到

U=(121011001),U= \begin{pmatrix} 1&2&1\\ 0&1&1\\ 0&0&1 \end{pmatrix},

这就是一个行阶梯形矩阵。

等价地,行化简给出

U=EA,U=EA,

其中 EE 是表示这些行变换合成结果的可逆矩阵。

简化行阶梯形

如果一个矩阵为行阶梯形,并且还满足以下条件,就称其为简化行阶梯形,英文缩写为 RREF:

  1. 每个主元都等于 11。
  2. 每个主元都是其所在列中唯一的非零元素。

因此,阶梯形要求主元下方的元素为零,而简化阶梯形要求主元上方和下方的元素都为零。

例如,

(120−100130000)\begin{pmatrix} 1&2&0&-1\\ 0&0&1&3\\ 0&0&0&0 \end{pmatrix}

是简化行阶梯形矩阵。非主元列中仍然可以包含非零元素。

继续消去主元上方的元素,并将主元化为一的过程,通常称为高斯—若尔当消元法。

同一个矩阵可以有许多不同的行阶梯形,因为行的数乘和其他允许的变换都可能改变其中的元素。相比之下,域上的每个矩阵都恰好有一个简化行阶梯形。因此,两个同型矩阵行等价,当且仅当它们的简化行阶梯形相同。

求解线性方程组

对于线性方程组

Ax=bAx=b

可以对其增广矩阵

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

施行行变换来进行化简。由于这些变换将方程替换为等价的方程,因此不会改变解集。

考虑如下阶梯形增广矩阵:

(12−1301240000).\left( \begin{array}{ccc|c} 1&2&-1&3\\ 0&1&2&4\\ 0&0&0&0 \end{array} \right).

变量 x1x_1 和 x2x_2 对应于系数矩阵的主元列;x3x_3 是自由变量。令 x3=tx_3=t,得到

x2=4−2t,x1=3−2x2+t=−5+5t.x_2=4-2t, \qquad x_1=3-2x_2+t=-5+5t.

因此,解为

x=(−540)+t(5−21).x= \begin{pmatrix} -5\\4\\0 \end{pmatrix} +t \begin{pmatrix} 5\\-2\\1 \end{pmatrix}.

这种从最后一个非零方程开始向上逐步求解的过程称为回代。

形如

(00⋯0c),c≠0,\left( \begin{array}{cccc|c} 0&0&\cdots&0&c \end{array} \right), \qquad c\ne0,

的行表示矛盾 0=c0=c,因此方程组无解。特别地,增广列中出现主元就表明方程组不相容。

对于含有 nn 个未知数、系数矩阵的秩为 rr 的相容方程组,自由变量共有 n−rn-r 个。当且仅当 r=nr=n 时,解唯一。在无限域上,含有至少一个自由变量的相容方程组有无穷多个解;在含有 qq 个元素的有限域上,它有 q n−rq^{\,n-r} 个解。

秩与基本子空间

矩阵的秩等于其任一行阶梯形中的主元个数,也等于其中非零行的个数。

行化简还可以提供有关若干相关线性子空间的信息。

行空间

初等行变换保持行空间不变:每个新行都是原有各行的线性组合,而变换的可逆性又给出反向的包含关系。阶梯形中的非零行线性无关,因此构成原矩阵行空间的一组基(线性代数)。

列空间

行变换通常会改变列空间本身,但会保持对应列之间的所有线性相关关系。事实上,若 U=EAU=EA,且 EE 可逆,则

Ac=0⟺Uc=0.Ac=0\quad\Longleftrightarrow\quad Uc=0.

UU 的主元列指出了原矩阵 AA 中哪些列构成其列空间的一组基。如果改为取出 UU 中的主元列,通常得到的是 UU 的列空间的一组基,而不是 AA 的列空间的一组基。

零空间

行变换保持零空间不变,因为齐次方程组 Ax=0Ax=0 和 Ux=0Ux=0 的解完全相同。

如果 AA 有 nn 列,秩为 rr,则通过对自由变量进行参数化,可以得到一组包含 n−rn-r 个向量的零空间基。由此得到

dim⁡(ker⁡A)=n−r,\dim(\ker A)=n-r,

这是秩—零化度定理的一个具体体现。

其他计算用途

对于方阵,阶梯形还可用于以下计算:

  • 可逆性: 一个 n×nn\times n 矩阵可逆,当且仅当它有 nn 个主元。此时,它的简化行阶梯形就是单位矩阵。
  • 求逆: 在可行的情况下,将 [ A∣I ][\,A\mid I\,] 化为 [ I∣A−1 ][\,I\mid A^{-1}\,],即可求出逆矩阵。
  • 行列式: 对于阶梯形方阵,其行列式等于对角线上各元素的乘积。要由此求回原矩阵的行列式,需要记录换行和行的数乘;将某一行的倍数加到另一行上不改变行列式。
  • 矩阵分解: 记录消元乘数可以得到LU分解;若过程中交换了行,通常还需要引入置换矩阵。

精确计算与数值计算

在采用精确运算的域上,阶梯形和简化阶梯形具有严格的代数意义。采用浮点运算时,舍入误差可能使理论上为零的元素表现为一个很小的非零数。

因此,实际的消元算法会采用选主元策略。部分选主元法在当前列尚未处理的部分中选取绝对值最大的元素,有助于控制消元乘数的大小。但它并不能消除所有可能的数值稳定性问题。

当矩阵接近奇异时,区分精确秩和数值秩尤为重要。数值秩取决于容差和矩阵的尺度,而不仅仅取决于计算所得的元素是否严格为零。在这类情况下估计秩时,带列选主元的QR分解和奇异值分解是常用的替代方法,可用来取代直接的阶梯形化简。

矩阵定义在域上的这一假设也很重要。在一般的环上,非零主元未必可逆,因此通常的行归一化与消元论证并不能直接适用。如果只允许使用保持元素为整数的变换来化简整数矩阵,就需要采用其他标准形。