# 简化阶梯形

在线性代数中，一个给出的矩阵往往会被进行各种各样的预处理，从而提炼出最关心的核心信息
其中，最早，也是现在即将开始接触的其中一种，就是简化阶梯形

定义
将矩阵 $A$ 进行行向量分割

$A = \begin{pmatrix} \boldsymbol{a_1} \\ \boldsymbol{a_2} \\ \vdots \\ \boldsymbol{a_m} \end{pmatrix}$

称矩阵 $A$ 为 阶梯形 (Echelon Form)「階段形」，当且仅当满足以下条件：

所有的零向量都位于矩阵的下方
非零向量最左侧的元素称为该行的先导元
越靠下的行，其先导元位置越靠右

在此基础上，称矩阵 $A$ 为 简化阶梯形 (Reduced Echelon Form)「簡約階段形」，当且仅当其进一步满足以下条件：

含有主元的列，其余元素均为 $0$

如果强调行分割，有时也对应的称其为行阶梯形与简化行阶梯形

称矩阵简约化之后，含有的主元数量为矩阵的 秩 (Rank)「階数」，记作 $\mathrm{rank}(A)$
若 $n$ 阶方阵 $A$ 的秩为 $n$ ，则称其为满秩矩阵
矩阵的秩是其非常重要的概念。通过行化简，可以实现对矩阵的分类，在一定程度上秩相等的矩阵具有共通的性质，这是对矩阵进行化简的重要目的：获取矩阵的秩

命题
若 $A$ 是 $m$ 行 $n$ 列矩阵，则

$\mathrm{rank}(A) \leq \min(m, n)$

证明

显然，矩阵的主元数量不可能超过行数与列数中的较小值

为了实现将矩阵化为简化阶梯形的目标，需要规定一些基本操作

定义
对矩阵 $A$ ，以下三种操作称为矩阵的 行基本变换 (Elementary Row Operations)「行基本変換」：

R1：将某一行乘以非零常数 $c$
R2：将某一行与另一行互换
R3：将某一行加上另一行的常数倍

对称地，可以得到列基本变换的定义

行基本变换可以导向我们的一个目标：将矩阵化为简化阶梯形

接下来以一个矩阵为例，讲解行化简算法，设矩阵

$A = \begin{pmatrix} 0 & 0 & 2 & -3 & 1 \\ 2 & 4 & -8 & 8 & -12 \\ 1 & 2 & -3 & 3 & -4 \end{pmatrix}$

展开过程

第一步是通过交换，先确保最左上方的元素非零

$\xrightarrow{R2 \leftrightarrow R1} \begin{pmatrix} 2 & 4 & -8 & 8 & -12 \\ 0 & 0 & 2 & -3 & 1 \\ 1 & 2 & -3 & 3 & -4 \end{pmatrix}$

第二步是将第一行的首元素化为 $1$ ，获得第一个主元

$\xrightarrow{\frac{1}{2}R1} \begin{pmatrix} 1 & 2 & -4 & 4 & -6 \\ 0 & 0 & 2 & -3 & 1 \\ 1 & 2 & -3 & 3 & -4 \end{pmatrix}$

通过第一行的主元，将其他行的对应列元素化为 $0$

$\xrightarrow{R3 - R1 \to R3} \begin{pmatrix} 1 & 2 & -4 & 4 & -6 \\ 0 & 0 & 2 & -3 & 1 \\ 0 & 0 & 1 & -1 & 2 \end{pmatrix}$

接下来让视线完全离开第一行，关注其他部分，重复上述过程

$\xrightarrow{\frac{1}{2}R2} \begin{pmatrix} 1 & 2 & -4 & 4 & -6 \\ 0 & 0 & 1 & -\frac{3}{2} & \frac{1}{2} \\ 0 & 0 & 1 & -1 & 2 \end{pmatrix}$

$\xrightarrow{R3 - R2 \to R3} \begin{pmatrix} 1 & 2 & -4 & 4 & -6 \\ 0 & 0 & 1 & -\frac{3}{2} & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & \frac{3}{2} \end{pmatrix}$

$\xrightarrow{2R3} \begin{pmatrix} 1 & 2 & -4 & 4 & -6 \\ 0 & 0 & 1 & -\frac{3}{2} & \frac{1}{2} \\ 0 & 0 & 0 & 1 & 3 \end{pmatrix}$

至此所有的主元均已确定，接下来通过回代，将主元所在列的其他元素化为 $0$

$\xrightarrow{R2 + \frac{3}{2}R3 \to R2} \begin{pmatrix} 1 & 2 & -4 & 4 & -6 \\ 0 & 0 & 1 & 0 & 5 \\ 0 & 0 & 0 & 1 & 3 \end{pmatrix}$

$\xrightarrow{R1 - 4R3 \to R1} \begin{pmatrix} 1 & 2 & -4 & 0 & -18 \\ 0 & 0 & 1 & 0 & 5 \\ 0 & 0 & 0 & 1 & 3 \end{pmatrix}$

$\xrightarrow{R1 + 4R2 \to R1} \begin{pmatrix} 1 & 2 & 0 & 0 & 2 \\ 0 & 0 & 1 & 0 & 5 \\ 0 & 0 & 0 & 1 & 3 \end{pmatrix}$

最终得到矩阵的行最简形

让我们更加本质地分析行化简这个过程
首先注意一个基本事实：所有的行基本变换都是可逆的

R1 的逆变换是将该行乘以 $\frac{1}{c} \quad$
R2 的逆变换是再次将该行与另一行互换
R3 的逆变换是将该行减去另一行的相同常数倍（加上负数倍）

接下来看如下三个矩阵

第一个是将单位矩阵 $E_n$ 的第 $i$ 变为常数 $c$ 的矩阵

$P_{i}(c) = \begin{pmatrix} 1 & & & & & \\ & \ddots & & & & \\ & & c & & & \\ & & & \ddots & & \\ & & & & 1 & \end{pmatrix}$

第二个是将单位矩阵 $E_n$ 的第 $i$ 行与第 $j$ 行互换的矩阵

$P_{ij} = \begin{pmatrix} 1 & & & & & & \\ & \ddots & & & & & \\ & & 0 & \cdots & 1 & & \\ & & \vdots & & \vdots & & \\ & & 1 & \cdots & 0 & & \\ & & & & & \ddots & \\ & & & & & & 1 \end{pmatrix}$

第三个是将单位矩阵 $E_n$ 的第 $i$ 行加上第 $j$ 行的常数倍 $c$ 的矩阵

$P_{i j}(c) = \begin{pmatrix} 1 & & & & & & \\ & \ddots & & & & & \\ & & 1 & & & & \\ & & \vdots & \ddots & & & \\ & & c & \ldots & 1 & & \\ & & & & & \ddots & \\ & & & & & & 1 \end{pmatrix}$

那么不难验证，行基本变换实际上就是将矩阵左乘以上述三种矩阵之一，这三个矩阵被称为行基本变换矩阵，具体地：

R1 对应左乘 $P_i(c)$ ，即 $P_i(c)A$
R2 对应左乘 $P_{ij}$ ，即 $P_{ij}A$
R3 对应左乘 $P_{ij}(c)$ ，即 $P_{ij}(c)A$

同样，因为行基本变换是可逆的，所以上述三种矩阵均为可逆矩阵，其逆矩阵分别为

$P_i(c)^{-1} = P_i\left(\frac{1}{c}\right)$
$P_{ij}^{-1} = P_{ij} \quad$
$P_{ij}(c)^{-1} = P_{ij}(-c)$

由此，我们可以重新以更加严格的语言描述行化简的过程

命题
对于任意的矩阵 $A$ ，都存在有限个行基本变换矩阵 $P_1, P_2, \dots, P_k$ ，使得

$P_k P_{k-1} \cdots P_2 P_1 A = R$

其中 $R$ 为矩阵 $A$ 的行最简矩阵

证明

根据行化简的算法可知，可以通过有限次行基本变换将矩阵化为行最简矩阵
$\square$

# 线性无关

定义
令向量 $\boldsymbol{a_1}, \boldsymbol{a_2}, \dots, \boldsymbol{a_r}$ 为矩阵 $A$ 的向量分割，称它们为 线性无关 (Linearly Independent)「線形独立」，当且仅当

$c_1 \boldsymbol{a_1} + c_2 \boldsymbol{a_2} + \cdots + c_r \boldsymbol{a_r} = \boldsymbol{0} \iff c_1 = c_2 = \cdots = c_r = 0$

否则称为 线性相关 (Linearly Dependent)「線形従属」。

在线性相关时，非零系数得到的关系式称为非自明的线性关系

线性无关指示了各个向量之间是否平行。换句话来说非线性无关的向量组携带了冗余的信息，因为其中个别向量是可以被其他向量线性表示出来的，它们的单独存在没有意义

利用线性无关，可以导出行化简的唯一性

命题
令 $\boldsymbol a_1, \boldsymbol a_2, \dots, \boldsymbol a_r$ 为 $n$ 维列向量， $P$ 为 $n$ 维正则矩阵，则

$\boldsymbol a_1, \boldsymbol a_2, \dots, \boldsymbol a_r \text{ Linearly Independent} \iff P\boldsymbol a_1, P\boldsymbol a_2, \dots, P\boldsymbol a_r \text{ Linearly Independent}$

证明

( $\Rightarrow$ )
设方程

$c_1 P \boldsymbol a_1 + c_2 P \boldsymbol a_2 + \cdots + c_n P \boldsymbol a_n = \boldsymbol 0$

从左侧同时左乘 $P^{-1}$ ，得到

$c_1 \boldsymbol a_1 + c_2 \boldsymbol a_2 + \cdots + c_n \boldsymbol a_n = \boldsymbol 0$

由 $\boldsymbol a_1, \boldsymbol a_2, \dots, \boldsymbol a_r$ 线性无关可知 $c_1 = c_2 = \cdots = c_n = 0$ ，因此 $P\boldsymbol a_1, P\boldsymbol a_2, \dots, P\boldsymbol a_r$ 线性无关

( $\Leftarrow$ )
设方程

$c_1 \boldsymbol a_1 + c_2 \boldsymbol a_2 + \cdots + c_n \boldsymbol a_n = \boldsymbol 0$

从左侧同时左乘 $P$ ，得到

$c_1 P \boldsymbol a_1 + c_2 P \boldsymbol a_2 + \cdots + c_n P \boldsymbol a_n = \boldsymbol 0$

由 $P\boldsymbol a_1, P\boldsymbol a_2, \dots, P\boldsymbol a_r$ 线性无关可知 $c_1 = c_2 = \cdots = c_n = 0$ ，因此 $\boldsymbol a_1, \boldsymbol a_2, \dots, \boldsymbol a_r$ 线性无关
$\square$

在之前已经论述：可以确保在有限回内行化简任意矩阵，即

$P_k P_{k-1} \cdots P_2 P_1 A = R$

统合这里的乘积，可以写为

$PA = R$

其中 $P$ 为正则矩阵

命题 行最简矩阵的唯一性
对于任意矩阵 $A$ ，设矩阵 $P$ 满足

$PA = R$

其中 $R$ 为矩阵 $A$ 的行最简矩阵，则 $R$ 唯一

证明

设 $A$ 通过行变换化为简化阶梯形 $R$ 。即 $PA=R$ 。
对矩阵 $A,R$ 进行列向量分割

$\begin{aligned} A &= \begin{pmatrix} \boldsymbol a_1 & \boldsymbol a_2 & \cdots & \boldsymbol a_n \end{pmatrix} \\ R &= \begin{pmatrix} \boldsymbol r_1 & \boldsymbol r_2 & \cdots & \boldsymbol r_n \end{pmatrix} \end{aligned}$

根据前述命题，左乘可逆矩阵 $P$ 不改变向量组的线性相关性。
因此， $\boldsymbol r_1, \dots, \boldsymbol r_n$ 之间的线性关系与 $\boldsymbol a_1, \dots, \boldsymbol a_n$ 完全一致。

考察 $A$ 的列向量。设 $\boldsymbol a_{j_1}$ 是第一个非零列，则 $\boldsymbol r_{j_1}$ 必须是 $R$ 的第一个主元列（即 $\boldsymbol e_1$ ）。
接着寻找 $\boldsymbol a_{j_2}$ ，使得它不能被 $\boldsymbol a_{j_1}$ 线性表示。对应的 $\boldsymbol r_{j_2}$ 即为第二个主元列（ $\boldsymbol e_2$ ）。
依此类推，我们可以唯一确定主元列的下标集合 $\{j_1, j_2, \dots, j_r\}$ 。这些列在 $R$ 中必然是单位坐标向量 $\boldsymbol e_1, \dots, \boldsymbol e_r$ 。

对于任意非主元列 $\boldsymbol a_k$ （ $k \notin \{j_1, \dots\}$ ），由于主元列构成了基底， $\boldsymbol a_k$ 必然可以唯一地表示为主元列的线性组合：

$\boldsymbol a_k = c_1 \boldsymbol a_{j_1} + c_2 \boldsymbol a_{j_2} + \cdots + c_m \boldsymbol a_{j_m}$

根据线性关系的同构性，对应的 $\boldsymbol r_k$ 也必须满足同样的线性组合：

$\boldsymbol r_k = c_1 \boldsymbol r_{j_1} + c_2 \boldsymbol r_{j_2} + \cdots + c_m \boldsymbol r_{j_m}$

代入 $\boldsymbol r_{j_i} = \boldsymbol e_i$ ，可得：

$\boldsymbol r_k = \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_m \\ 0 \\ \vdots \end{pmatrix}$

这意味着 $R$ 的每一列（无论是主元列还是非主元列）都由 $A$ 的列向量间的线性关系唯一确定。
因此， $R$ 是唯一的。
$\square$

# 简化阶梯形

# 线性无关

【线性代数】3-线性方程组

【集合论】3-集合族