3 矩阵的秩

矩阵的秩(rank)

对于一个一般的$m \times n$的矩阵$A$，它也可以看作$m$个$n$元方程的系数，因此也可以进行高斯消元的操作。但是，消元之后我们不一定能得到一个“完美”的上三角：假设矩阵不是方阵，那么消元后我们无法得到一个上三角，只能得到一个“上梯形”；即便矩阵是方阵，假设矩阵里有一模一样的两行，那么高斯消元后会得到一个全0行，把全零行换到最下方，也会使得上三角变为上梯形。在这些情况下，显然方程组不再有唯一解了，可能有无穷多解或无解。关键的问题是，如何判断一个线性方程组是有唯一解还是有无穷多解还是无解呢？到目前为止，似乎除了实际实施一遍高斯消元以外并没有更好的办法。我们能否从高斯消元的过程中提取出某些矩阵本身的属性，用这一属性来判断方程组的解的特性呢？

在一般情形的高斯消元中，我们把高斯消元结束后的矩阵称为“行阶梯形矩阵”（而不再是上三角矩阵）。我们定义此时每行最左边的非零元素为这一行的pivot。pivot并不一定整齐地排列在对角线上，但从上往下列坐标一定严格向右递增，形成一个倒过来的“阶梯”的形状。同样地，Gauss-Jordan消元也不一定能得到一个单位矩阵，而只能得到“简化行阶梯形矩阵”——它也是一个“阶梯”的形状，同时满足pivot所在的列除了pivot处为1以外其他都是0。我们将会证明，无论采取怎样的消元顺序，一个矩阵的pivot总数是唯一的（该证明留到本章的最后）。于是我们可以定义一个矩阵$A$在高斯消元后的pivot个数为矩阵$A$的一个属性，称为矩阵$A$的秩，记作$\text{rank}(A)$。显然，对于$n\times n$的矩阵$A$，$Ax=b$有唯一解当且仅当$\text{rank}(A)=n$。

对于一般的矩阵$A_{m\times n}$，我们把$A$的行空间（行向量张成的空间）的维数称为$A$的行秩(row rank)，把$A$的列空间的维数称为列秩(column rank)。从定义上看，行秩并不一定等于列秩，行秩与列秩也并不一定等于矩阵的秩。但下面我们就要证明，对于任意矩阵都成立行秩等于列秩等于矩阵的秩：

我们观察到，矩阵$A$的简化行阶梯形矩阵$R$必定与$A$有相同的秩。即$\text{rank}(A)=\text{rank}(R)$恒成立。这是显然的，因为$A$的秩是定义在行阶梯形上的，而从$A$到$R$的过程不会创造也不会消灭pivot。我们又观察到，$R$的秩必定等于$R$的行秩，也等于$R$的列秩。因为$R$的pivot所在的那些列都是单位向量，线性独立。底下的$m-r$行都是全0行不必理会，因此这些向量一定张成了整个列空间，因此这些向量就是列空间的一组基，这组基的向量个数等于pivot的个数，这就是说$R$的秩等于$R$的列秩。又因为，$R$的底下$m-r$行都是全0行，不会对张成行空间有贡献，因此这$r$个pivot所在行一定能张成整个行空间。而pivot所在的列除了pivot以外全是0，因此想让pivot所在的这些行线性组合出一个全0行，只能让每一行都乘上0来得到，这正是线性独立的定义，因此这些行是线性独立的，也就是说这些pivot行是行空间的一组基。这组基中向量的个数等于pivot的个数，所以说$R$的秩等于$R$的行秩。所以：“$A$的秩等于$R$的行秩，也等于$R$的列秩。”从这个结论出发，如果我们能够说明高斯消元的每一步都不会改变一个矩阵的行秩和列秩，我们就可以得到对于任意矩阵$A$都有“行秩等于列秩”的结论。

由于高斯消元进行的是行变换，我们可以证明变换前后行空间是不变的，因此也必然有行秩不变——只需要说明变换前的任意一个行向量的线性组合一定可以被变换后的某个线性组合表示，对称地变换后的也一定可以被变换前的表示。

列秩的情形要复杂一些。行变换可能改变了列空间，但我们会看到列空间的维数是不变的：对变换前的矩阵，我们考虑任意选出一个列向量的子列做线性组合，并在做线性组合时给每个系数一个特定的值。对变换后的矩阵也相应地做这样的一个线性组合。我们发现，前一个线性组合等于零向量“当且仅当”后一个线性组合等于零向量——因为对于这样的行操作，这个“等于零”可以互相从一边推到另一边。因此，前一个向量子列线性独立当且仅当后一个向量子列线性独立。我们能由此进一步说明，前后能选出的“最长”的线性独立子列的“长度”也是相等的。也就说明，前后的列向量极大线性无关组大小相同，也即前后列空间维数相同，因此列秩相等。

综上，我们得到：$R$的秩 = $R$的行秩 = $R$的列秩 = $A$的秩 = $A$的行秩 = $A$的列秩。

零空间(Nullspace)

方程组$Ax=0$的所有解$x$构成的集合称为该方程的解集。我们注意到，任取解集中的两个$x_1,x_2$，有$Ax_1=0$,$Ax_2=0$，因此也有$A(c_1x_1+c_2x_2)=0$，因此解集构成了$\mathbb{R}^n$的一个子空间，因此是一个向量空间。我们把这个向量空间称为$A$的零空间(Nullspace)，记为$N(A)$。

从简化行阶梯形矩阵的角度看，矩阵的每一列对应方程的某个变量。所有没有pivot的列对应的变量称为自由元；有pivot的列对应的变量称为主元。当我们给自由元任意赋一组值时，可以依据它们的值来求出所有主元应当取的值。现在设矩阵$A$的秩为$r$，也即$A$有$r$个pivot。所以$A$有$n-r$个自由元，$r$个主元。令这$n-r$个自由元以$(1,0,\cdots,0),(0,1,\cdots,0)$ $,\cdots,(0,0,\cdots,1)$的方式依次取值，我们就可以得到$n-r$个满足$Ax=0$的向量$x$。显然这$n-r$个向量是线性独立的，并且他们的线性组合恰好能使得所有自由元取得任意值，因此恰好张成了整个零空间。由此我们证明了$\dim(N(A))=n-r$，也即零空间的维数等于矩阵的列数减去矩阵的秩。

线性方程组的通解

$Ax=b$有解当且仅当$b\in C(A)$。我们已经知道$Ax=0$的解空间是一个子空间，称为零空间。我们想知道对于任意的$b$，$Ax=b$的解空间是否也是一个子空间。如果是，那么对于$Ax_1=b$，$Ax_2=b$，必须有$A(x_1+x_2)=b$。这意味着$Ax_1+Ax_2=b+b=b$，由消去律得$b=0$。也就是说只有$b=0$的时候解空间才有可能是子空间，对于非零的$b$，解空间一定不是子空间。

虽然$Ax=b$的解空间不是子空间，但它和子空间非常接近，我们可以把它看作子空间的一个“平移”。假设我们能够找到$Ax=b$的一个特解$x_p$，那么有$Ax_p=b$。而对于零空间里的任意向量$x_n$，都有$Ax_n=0$，相加得$A(x_p+x_n)=b$。也就是说零空间里的任意一个向量加上这个特解一定是一个解。除此之外还有没有可能有别的解呢？假设存在一个解$x'$不能被写作$x_p+x_n$的形式，即$x'-x_p \notin N(A)$，那么有$A(x_p+x_n)-Ax'=b-b=0$，合并得$A(x_p+x_n-x')=0$。而$Ax_n=0$，因此$A(x_p-x')=0$，因此$A(x'-x_p)=0$，于是推出$x'-x_p \in N(A)$，矛盾。综上，$Ax=b$的通解即为“某个特解+零空间中任意一个向量”。

怎么找到一组特解呢？我们对增广矩阵$[A \ b]$做Gauss-Jordan，$A$将变成简化行阶梯形矩阵。此时如果全零行对应了非零的数，那么原方程组一定无解，因为行变换是不改变解空间的；如果全零行对应零，那么没有任何作用；接着，我们让所有自由元都取0，代入就可以解得每行主元的取值——这就是一组特解了。

矩阵的秩的唯一性

事实上，一个矩阵高斯消元得到的“上三角”矩阵可能不止一种的。但如果我们加上一些规定，比如在行交换的时候只找最上面的非零行等等，那么高斯消元的结果可以是唯一的。换句话说，高斯消元的过程可以写成一个确定的程序，而一个确定的程序对于确定的输入只会输出唯一的结果。

但这样的“确定性”只是人为的规定，我们想要验证，高斯消元产生的结果是否真的是唯一的。在高斯消元将任意矩阵变为行阶梯形的过程中，是否有可能由于消元顺序的不同而导致不同的pivot数量。这是需要证明的。

高斯消元的每一步——初等行变换——是不会改变方程组的解空间的，因此也不会改变矩阵的零空间。零空间如果不变，那么零空间的维数是恒定的，那么根据$\dim(N(A))=n-r$，$r$一定也不变。由此我们证明了pivot数量（矩阵的秩）是唯一的。

行阶梯形一定是不唯一的，我们可以随意的给每行乘以系数。而我们发现，简化行阶梯形一定是唯一的。对此，我们先来证明，行阶梯形的主元列的列坐标一定是唯一的。如果$A_{mn}$存在两个主元列坐标不同的阶梯形$A_1,A_2$，那么我们一定能够找到一个最大的$k$，使得$\forall i > k$，第$i$列“是否为主元的属性”都相同（即如果$A_1$和$A_2$的第$i$列要么都是主元列要么都是自由元列），而第$k$列的“是否为主元的属性”不同。不妨设$A_1$的第$k$列是主元列，而$A_2$的第$k$列是自由元列。对于$A_2$，我们可以通过它的自由元来构造一组$A_2x=0$的解，其中$x_k=1$，其余自由元都取0。由于初等行变换是不改变解空间的，因此我们知道这组解一定也是$A_1$的解。而我们知道对于$A_1x=0$，正因为右边的$b$中对应的数为0，而主元列在这一行上也全是0，因此$x_r$由所有列坐标大于$k$的自由元决定，而根据我们的构造，这些自由元的取值都为0，于是得到$x_r=0$，这就产生了矛盾。所以，任何矩阵的阶梯形的主元列必定是完全相同的。

由于阶梯形的主元列是相同的，因此简化行阶梯形的所有的主元列上的数一定是唯一的了。现在要证简化行阶梯形的自由元列上的系数也是唯一的。如果存在两个简化行阶梯形$R_1,R_2$，其中$R_1(i,j) \neq R_2(i,j)$，其中$j$是自由元列的列坐标，那么$R_1(i,j),R_2(i,j)$必定有一个不为0，因此第$i$行存在某个pivot，记为$x_s$。

对于$R_1x=b$，有$x_s+\sum\limits_{k>s且x_k是自由元}R_1(i,k)x_k=b_i$。

对于$R_2x=b$，有$x_s+\sum\limits_{k>s且x_k是自由元}R_2(i,k)x_k=b_i$。

相减得$\sum\limits_{k>s且x_k是自由元}(R_1(i,k)-R_2(i,k))x_k=0$

对于$x_k$取遍所有值，这个等式是恒成立的。因此必须有$R_1(i,k)-R_2(i,k)=0$，这与$R_1(i,j) \neq R_2(i,j)$矛盾。由此证得简化行阶梯形是唯一的。

The Big Picture

现在我们终于完整地认识到：秩是一个矩阵的一个唯一的属性，$A$的秩 = $R$的秩是对任意矩阵成立的。对于任意的矩阵$A$，都有$A$的秩 = $A$的行秩 = $A$的列秩。

我们观察以下四个空间的维数：$C(A),N(A),C(A^\top),N(A^\top)$。我们发现，$\dim(C(A))=r,\dim(N(A))=n-r,\dim(C(A^\top))=r,\dim(N(A^\top))=m-r$。$A$的列秩与$A$的零空间维数互补，它们的和始终等于$A$的列数；考虑$A^\top$，得到$A^\top$的列秩（也就是$A$的行秩）与$A^\top$的零空间维数互补，它们的和始终等于$A$的行数。这是线性代数中最基本的一个定理。

若干矩阵乘积的秩一定分别小于等于每个矩阵的秩。

$\text{rank}(AB) \leq \min\{\text{rank}(A),\text{rank}(B)\}$

观察列空间，设$A=\begin{bmatrix}a_1 & a_2 & \cdots a_n\end{bmatrix}$，$B=\begin{bmatrix}b_1 & b_2 & \cdots b_m\end{bmatrix}$，$AB=\begin{bmatrix}c_1 & c_2 & \cdots c_m\end{bmatrix}$。得到$c_i=\sum\limits_{k \in [n]}b_{ik}a_k$，因此$c_i \in C(A)$。所以$C(AB) \subseteq C(A)$，得到$\text{rank}(AB) \leq \text{rank}(A)$。

将$A$用$B^\top$代换，$B$用$A^\top$代换，得到$\text{rank}(B^\top A^\top) \leq \text{rank}(B^\top)$。由于行秩等于列秩，所以$\text{rank}(AB) \leq \text{rank}(B)$。