# 简化阶梯形

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

定义
将矩阵 $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)$
矩阵的秩是其非常重要的概念。通过行化简，可以实现对矩阵的分类，在一定程度上秩相等的矩阵具有共通的性质，这是对矩阵进行化简的重要目的：获取矩阵的秩

命题
若 $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}
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_
$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$ 的行最简矩阵，则 $P$ 唯一

证明

首先 $P$ 的存在性无需置疑，对矩阵 $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}$

取子集 $\{i_1, i_2, \dots, i_r\} \subseteq \{1, 2, \dots, n\}$ ，满足列向量组

$\boldsymbol a_{i_1}, \boldsymbol a_{i_2}, \dots, \boldsymbol a_{i_r}$

线性无关，且任意添加其他列向量后均线性相关，即

$j \not\in \{i_1, i_2, \dots, i_r\},\ i_s \lt j \lt i_{s+1} \implies \boldsymbol a_{i_1}, \boldsymbol a_{i_2}, \dots, \boldsymbol a_{i_r}, \underbrace{\boldsymbol a_j}_{\text{New}} \text{ Linearly Dependent}$

规定

$j \lt i_1 \implies \boldsymbol a_j = \boldsymbol 0$
$i_{r+1} = n + 1$

通过按照顺序从 $\boldsymbol a_1$ 开始构建这样的线性无关的向量，集合 $\{i_1, i_2, \dots, i_r\}$ 是唯一确定的

根据等式 $PA = R$ 可知 $\boldsymbol b_i = P \boldsymbol a_i$ ，因此前述命题给出

$\boldsymbol b_{i_1}, \boldsymbol b_{i_2}, \dots, \boldsymbol b_{i_r}$

线性无关，且

$j \not\in \{i_1, i_2, \dots, i_r\},\ i_s \lt j \lt i_{s+1} \implies \boldsymbol b_{i_1}, \boldsymbol b_{i_2}, \dots, \boldsymbol b_{i_r}, \underbrace{\boldsymbol b_j}_{\text{New}} \text{ Linearly Dependent}$

由于 $R$ 为行最简矩阵，从定义可以知道含有主元的列向量是基本向量，不含主元的列可以由基本向量线性表示出来，因此

$\begin{pmatrix} \boldsymbol b_{i_1} & \boldsymbol b_{i_2} & \cdots & \boldsymbol b_{i_r} \end{pmatrix} = \begin{pmatrix} \boldsymbol e_1 & \boldsymbol e_2 & \cdots & \boldsymbol e_r \end{pmatrix} = E_r$

取 $i_i \lt j \lt i_{i+1}$ ，则可以得到非自明的线性关系

$c_1 \boldsymbol a_{i_1} + c_2 \boldsymbol a_{i_2} + \cdots + c_r \boldsymbol a_{i_r} + b \boldsymbol a_j = \boldsymbol 0$

显然 $b \neq 0$ ，因此

$\boldsymbol a_j = -\frac{c_1}{b} \boldsymbol a_{i_1} - \frac{c_2}{b} \boldsymbol a_{i_2} - \cdots - \frac{c_r}{b} \boldsymbol a_{i_r}$

同乘 $P$ ，得到

$\boldsymbol b_j = -\frac{c_1}{b} \boldsymbol b_{i_1} - \frac{c_2}{b} \boldsymbol b_{i_2} - \cdots - \frac{c_r}{b} \boldsymbol b_{i_r}$

综上可知，矩阵 $R$ 的列向量组 $\boldsymbol b_1, \boldsymbol b_2, \dots, \boldsymbol b_n$ 唯一确定，因此矩阵 $P$ 也唯一确定
$\square$

# 简化阶梯形

# 线性无关

【集合论】1-集合

【集合论】5-势