线性方程组

参考教程 麻省理工公开课 线性代数 P6~P8

向量空间 (Vector Space)

向量空间是一个由无数个或几个向量组成的集合

在这个集合内, 向量需要对线性组合运算封闭 (数乘与加法), 即空间内的任意两个向量的线性组合仍在此空间内

由此可得, 所有向量空间必须包含 $\vec{0}$ 向量
检查一个集合是否为向量空间, 首先可以检查 $\vec{0}$ 是否在其中

n 维向量空间

$R^n$ 表示由所有具有 $n$ 个实分量的列向量组成的向量空间

对于 $R^2$ 中的一条过原点的直线, 直线上所有向量满足封闭条件, 因此也是向量空间, 并且属于 $R^2$ 的子空间

子空间 (Subspace)

将包含于任意向量空间的向量空间称为子空间

对于向量空间 $R^2$ 的子空间有 $R^2$ 本身; 一维子空间, 过原点的直线; 原点

对于向量空间 $R^3$ 的子空间有 $R^3$ 本身; 二维子空间, 过原点的平面 $P$; 一维子空间, 过原点的直线 $L$; 原点

通常两个向量空间的并集内的向量不对加法封闭, 因此不是向量空间; 但任意两个向量空间的交集仍是向量空间, 并且是一个子空间

列空间 (Column Space)

对于一个有 $n$ 行的矩阵 $A$, 可将其各列视为一个列向量, 这些向量之间的所有线性组合产生的集合为 $R^n$ 的子空间, 也称为列空间 $C(A)$

线性方程组的可解性

对于线性方程组 $A\vec{x}=\vec{b}$, 仅当 $\vec{b}\in C(A)$ 时方程有解

零空间 (Null Space)

有 $m\times n$ 的矩阵 $A$, 对于线性方程组 $A\vec{x}=\vec{0}$, 方程组的解 $\vec{x}$ 也构成一个向量空间, 称为零空间 $N(A)$

注意, 列空间 $C(A)$ 为 $R^m$ 的子空间, 而零空间 $N(A)$ 为 $R^n$ 的子空间

封闭性证明

• 加法封闭性 假设 $A\vec{x}=\vec{0}$ 有解 $\vec{v},\vec{w}$, 根据乘法分配律可得, 加法的结果仍为方程组的解

$$A(\vec{v}+\vec{w})=\vec{0}+\vec{0}=\vec{0}$$

• 根据数乘运算规则, 易得其对数乘封闭

一般的齐次线性方程组求解

现有一般的齐次线性方程组 $A\vec{x}=\vec{0}$ 其中 $A$ 为 $m\times n$ 的矩阵

消元法求解

依然通过消元与行交换来转换矩阵 $A$, 使其变为上阶梯矩阵 $U$ (消元与行交换均不会影响 $\vec{x}$)

对任意矩阵消元时, 当出现完全没有主元的列时 (主元不能为 $0$), 则跳过该列并对下一列消元, 直到对每一列都完成消元

在消元过程中, 由于解不变, 因此零空间不变, 但列空间改变. 因此对于矩阵 $A$ 与 $U$, 其具有相同的零空间 $N(A)=N(U)$

得到矩阵 $U$ 中, 当出现全为 $0$ 的行, 表明该行向量可以由其他行线性组合得到

消元结果分析

根据消元结果 $U$ 的特征, 进行如下定义

1. 秩 (Rank) 由于可能有列不含主元, 因此主元的数量并不总是与矩阵的列数相同 . 以此定义消元结果中主元的数量为矩阵的秩 $r$. 详见矩阵的秩的基本性质
2. 主元列 (Pivot column) 将主元所在的列称为主元列.
3. 自由列 (Free column) 将剩余的列则称为自由列. 通过 $U$ 得形式可得, 自由列必定来自左侧主元列的线性组合.
4. 主变量 (Pivot variable) 在得到结果 $\vec{b}$ 的线性组合中, 与主元列相乘的系数称为主变量. 其为 $\vec{x}$ 中的一个分量. 主变量与主元列的个数即矩阵的秩 $r$
5. 自由变量 (Free variable) $\vec{x}$ 中除主变量以为的分量称为自由变量. 由于自由列可通过主元列线性组合得到, 因此自由变量的效果可通过特定的主变量消除. 自由变量与自由列的个数即 $n-r$

特解求解

由于 $U$ 为阶梯矩阵因此无法直接回代得到结果, 可通过限定自由变量的值再使用回代. 将通过特定自由变量得到的解称为特解, 为了与非齐次方程区分, 也称为特殊解 (Special Solution).

由于解 $\vec{x}$ 也构成一个向量空间, 因此仅需要求出部分特解, 通过向性组合即可得到零空间中的其他解

为了方便求解, 通常令其中一个自由变量为 $1$, 其他自由变量为 $0$, 通过回代求出一个特解. 对每个自由变量都这样做, 将这些特解排列得到的列空间等价于零空间.

由此可得, 表示零空间最少需要 $n-r$ 个向量

简化行阶梯矩阵

对于消元得到的阶梯矩阵 $U$ 可以同过行之间的消元进一步化简使其形式更加简单. 并且可从化简得过程中直接得到构成零空间所需的特解, 避免回代.

定义简化行阶梯矩阵 $R$ 为一个阶梯矩阵并具有以下特点

1. $R$ 仍然为阶梯矩阵
2. $R$ 的主列上除了主元, 其他元素均为 $0$
3. $R$ 的主元为 $1$

易得 $R$ 是仅通过消元 (不改变解) 可得到的最简矩阵

在 matlab 中, 使用函数 rref 可用于求简化行阶梯矩阵

简化行阶梯矩阵的结构

通过列交换矩阵 $P$, 将 $R$ 的主列整理至左侧, 自由列整理至右侧, 可得到一个分块矩阵

$$RP= \begin{bmatrix} I&F\\ 0&0 \end{bmatrix}$$

此分块矩阵共由四个不同的矩阵组成, 分别是

1. 矩阵 $I$ 为一个 $r\times r$ 的单位矩阵, 由主元列构成
2. 矩阵 $F$ 为一个 $r\times n-r$ 的矩阵, 由自由列构成
3. 矩阵 $0$ 为全为 $0$ 的矩阵, 由自由行 (非主元行) 构成

零空间矩阵

定义零空间矩阵 $N$, 即满足 $N(A)=C(N)$ 的矩阵.
易得 $N$ 的各列由方程的特解组成

由于矩阵 $A,U,R$ 均通过消元得到, 因此其具有相同的零空间 (但列空间显然不相同). 易得

$$AN=R(PN')=\vec{0}$$

根据矩阵 $RP$ 的构成, 可得到矩阵 $N=PN'$ 满足

$$N'=\begin{bmatrix} -F\\ I' \end{bmatrix},N=PN'$$

因此零空间矩阵为一个 $n\times n-r$ 的矩阵
该矩阵的各列线性无关 (观察 $N'$ 易得)

注意, $I'$ 是一个 $n-r\times n-r$ 的单位矩阵. 由于通常情况下 $r\neq n-r$, 因此 $I'\neq I$.

也将零空间矩阵的这组列向量称为矩阵 $A$ 的基础解系

齐次方程的通解 (General Solution)

通解即线性方程组解的一般形式

根据组成零空间矩阵 $N$, 可得出方程的通解即 $N$ 的列向量 ($A$ 的基础解系) 的线性组合

$$\vec{x_g}=\sum_{i=1}^{n-r}a_i \vec{n_i},(a_i\in R)$$

其中共有 $n-r$ 个列向量, 也即方程自由变量的个数

求解过程示例

消元

现有消元过程如下

$$\begin{split}A=& \begin{bmatrix} 1&2&2&2\\ 2&4&6&8\\ 3&6&8&10\\ \end{bmatrix}\\ \to& \begin{bmatrix} 1&2&2&2\\ 0&0&2&4\\ 0&0&2&4\\ \end{bmatrix}\\ \to& \begin{bmatrix} \underline{1}&2&2&2\\ 0&0&\underline{2}&4\\ 0&0&0&0 \end{bmatrix}=U\end{split}$$

简化行阶梯

对阶梯矩阵进行简化行阶梯

$$\begin{split} U=& \begin{bmatrix} \underline{1}&2&2&2\\ 0&0&\underline{2}&4\\ 0&0&0&0 \end{bmatrix}\\ \to& \begin{bmatrix} \underline{1}&2&0&-2\\ 0&0&\underline{2}&4\\ 0&0&0&0 \end{bmatrix}\\ \to& \begin{bmatrix} \underline{1}&2&0&-2\\ 0&0&\underline{1}&2\\ 0&0&0&0 \end{bmatrix}=R \end{split}$$

求出零空间矩阵

$$\begin{split} R=& \begin{bmatrix} \underline{1}&2&0&-2\\ 0&0&\underline{1}&2\\ 0&0&0&0 \end{bmatrix}\\ RP_{23}=& \begin{bmatrix} \underline{1}&0&2&-2\\ 0&\underline{1}&0&2\\ 0&0&0&0 \end{bmatrix}\\ \to& \begin{bmatrix} -2&2\\ 0&-2\\ 1&0\\ 0&1 \end{bmatrix}=P_{23}N\\ \to& \begin{bmatrix} -2&2\\ 1&0\\ 0&-2\\ 0&1 \end{bmatrix}=N \end{split}$$

通解

由 $N$ 得到方程通解为

$$\vec{x}=a\begin{bmatrix}-2\\1\\0\\0\end{bmatrix}+b\begin{bmatrix}2\\0\\-2\\1\end{bmatrix}$$

一般非齐次方程组的求解

现有一般的非齐次线性方程组 $A\vec{x}=\vec{b}$ 其中 $A$ 为 $m\times n$ 的矩阵

增广矩阵消元

使用消元与行交换转化增广矩阵 $[A|b]$, 在对 $A$ 消元的同时改变 $\vec{b}$ 中的元素. 最终得到一个上阶梯矩阵 $U$ 与列向量 $\vec{c}$ 组成的增广矩阵 $[U|c]$

根据方程组有解的条件, 对于 $U$ 中全为 $0$ 的行, $\vec{c}$ 中对应位置的元素也将为 $0$

可使用字母 $b_n$ 带入消元, 从而得到方程组可解时 $\vec{b}$ 元素应满足的条件

求解方程组

方程组特解

同样通过向自由变量带入特定值的方式求出特解 (因此特解总是有无数个), 为了区分齐次方程组, 将非齐次方程组的特解称为特定解 (Particular Solution)

通常令所有自由变量为 $0$ 的方式求出特解 $\vec{x_p}$

方程组通解

特解仅是方程组的其中一个解, 根据零空间的性质可得, 零空间中的向量与特解相加并不影响右侧的值. 因此假设 $\vec{x_n}\in N(A)$ 则有

$$A\vec{x_p}=A(\vec{x_p}+\vec{x_n})=\vec{b}$$

因此方程组的通解即基础解系的线性组合与任一特解之和

$$\vec{x_g}=\vec{x_p}+\vec{x_n}=\vec{x_p}+\sum_{i=1}^{n-r}a_i \vec{n_i},(a_i\in R)$$

齐次方程组解的结构

现有线性方程组 $A\vec{x}=\vec{b}$, 其中 $A$ 为 $m\times n$ 的矩阵, 矩阵的秩为 $r$

秩的基本性质

定义矩阵主元数量 $r$ 为矩阵的秩 (Rank), 矩阵的秩有如下性质

1. 矩阵 $A$ 与其转置 $A^T$ 的秩相同
2. 矩阵的秩满足 $r\le n,r\le m$

根据矩阵秩与其行数列数的不同, 解具有不同的结构

矩阵之和的秩

对于矩阵 $A,B$ 其秩为 $r_A,r_B$, 对于两矩阵之和 $C=A+B$ 的秩 $r_c$ 有性质 (证明略)

$$\max(r_A,r_B)\le r_C\le r_A+r_B$$

其中

• 当 $A,B$ 的列空间完全重合 $r_C=\max(r_A,r_B)$
• 当 $A,B$ 的列空间不重合 $r_C= r_A+r_B$

矩阵与其转置之积的秩

对于 $m\times n$ 的矩阵 $A$, $A$ 与其转置 $A^T$ 相乘得到的矩阵 $A^TA$ 具有与 $A$ 相同的秩
证明如下

对于来自 $A$ 零空间的任意向量 $\vec{x}\in N(A)$ 有 $A\vec{x}=\vec{0}$

构造线性方程 $A^TA\vec{y}=\vec{0}$, 对方程两侧乘以 $\vec{y}^T$ 有 $(\vec{y}A)^T(A\vec{y})=0$
仅当向量 $A\vec{y}=\vec{0}$ 方程成立
因此零空间 $N(A^TA)$ 与 $N(A)$ 相同

由零空间的性质可得, 零空间 $N(A)$ 的维数为 $n-r$, $A^TA$ 为 $n\times n$ 的矩阵
因此证得, 矩阵 $A$ 与矩阵 $A^TA$ 的秩相同

特别的, 当 $A$ 列满秩时, $A^TA$ 为可逆矩阵

方程组的可解性 (Solvability)

对于一般的非齐次线性方程组, 不一定有解, 且可能有无数个解.

可能无解的情况

对于方程的最简行形式

$$RP=\begin{bmatrix}I&F\\0&0\end{bmatrix}$$

当其中的 $0$ 矩阵块存在时, 意味着 $c$ 中对应的位置不能为 $0$, 否则方程将无解.
因此当 $R$ 中不存在 $0$ 矩阵块时, 方程一定有解

有解的条件

根据方程形式易得, 方程组有解时将满足以下任意一个条件

1. $\vec{b}$ 来自矩阵 $A$ 列向量的线性组合, 即$\vec{b}\in C(A)$
   特别的, 当 $A$ 行满秩, 表明 $C(A)=R^m$, 必定有解
2. 当矩阵 $A$ 的行向量线性组合产生了 $\vec{0^T}$, 则对 $\vec{b}$ 中元素进行同样的线性组合将得到 $0$
3. 增广矩阵 $[R|c]$ 中, 存在 $R$ 全为 $0$ 的行且 $\vec{c}$ 对应位置为 $0$ 或不存在 $0$ 矩阵块

有唯一解的条件

当矩阵存在自由变量时, 矩阵的零空间内便不仅有 $\vec{0}$, 此时方程的解的形式是其中一个特解 $\vec{x_p}$ 加上任意零空间内的向量 $\vec{x_n}$

因此矩阵有唯一解时满足以下等价条件

1. 矩阵没有自由变量 $n-r=0$ (即列满秩)
2. 矩阵的最简行形式中没有矩阵块 $F$

列满秩 (Column Rank)

当矩阵满足 $n=r,n< m$ 时, 称为列满秩

• 由于 $n=r$, 矩阵每一列均有主元, 因此矩阵的最简行形式为 $R=[I\;0]^T$, 没有自由列部分 $F$.
• 此时矩阵不含自由变量, 因此矩阵的零空间内仅有零向量. 方程 $A\vec{x}=\vec{0}$ 仅有解 $\vec{0}$
• 当方程有解时, 也仅会有一个解, 称为唯一解 (Unique Solution).
• 由于 $m>n$, 可得矩阵的方程数多于未知量, 因此方程的解的个数为 $0$ 或 $1$. 且有解需要满足特定条件.

eg.

$$\begin{bmatrix}1&1\\ 2&1\\ 3&1\end{bmatrix} \vec{x}=\begin{bmatrix}2\\3\\4\end{bmatrix}$$

方程组仅有唯一解 $\vec{x}=(1,1)$

行满秩 (Row Rank)

当矩阵满足 $m=r,n>m$ 时, 称为行满秩

• 由于 $m=r$, 矩阵仅有部分列有主元, 但矩阵的每一行一定有主元. 因此矩阵的最简行形式为 $RP=[I\;F]$, 没有零矩阵部分.
• 此时矩阵一定含有 $n-m$ 个自由变量, 因此矩阵的零空间内不只有零向量, 方程 $A\vec{x}=\vec{0}$ 存在无穷多个解.
• 由于 $R=[I\;F]$, 因此矩阵的列空间 $R(A)$ 即 $R^m$, 对于任意 $\vec{b}$ 矩阵均有无数个解

eg.

$$\begin{bmatrix}1&1&1\\ 1&2&3\end{bmatrix} \vec{x}=\begin{bmatrix}2\\3\end{bmatrix}$$

有

$$R=\begin{bmatrix}1&0&-1\\ 0&1&2\end{bmatrix} N=\begin{bmatrix}1\\-2\\1\end{bmatrix}$$

满秩 (Full Rank)

当矩阵满足 $r=m=n$ 时, 称为满秩, 此时 $A$ 必定为一个方阵, 且是一个可逆矩阵

• 易得, 矩阵的每一行于每一列均有主元, 因此最简行形式即为 $R=I$
• 由于矩阵没有自由向量, 因此方程组仅有一个解
• 由于 $R$ 中不存在 $0$ 矩阵块, 因此方程 $A\vec{x}=\vec{b}$ 一定有且仅有一个解