矩阵的满秩分解
设$A\in \mathbb{C}_r^{m\times n}$，则存在$B\in \mathbb{C}_r^{m\times r}, C\in \mathbb{C}_r^{r\times n}$，满足
$$ A = BC $$
$\mathbb{C}_r$表示矩阵的秩为$r$
实际上上述定理用文字描述就是，一个亏秩的矩阵可以分解成一个列满秩与行满秩矩阵的乘积
证明：因为$\mathrm{rank}(A)=r$，所以一定可以找到与$A$相似的一个矩阵
$$ A \simeq \begin{bmatrix}E_r&0_{r\times (n-r)}\\0_{(m-r)\times r}&0_{(m-r)\times (n-r)}\end{bmatrix}=\begin{bmatrix}E_r\\0_{(m-r)\times r}\end{bmatrix}\begin{bmatrix}E_r&0_{r\times (n-r)}\end{bmatrix} $$
因此存在两个可逆矩阵$P,Q$，使$PAQ=\begin{bmatrix}E_r&0\\0&0\end{bmatrix}$，则
$$ \begin{aligned} A &= P^{-1}\begin{bmatrix}E_r\\0\end{bmatrix}\begin{bmatrix}E_r&0\end{bmatrix}Q^{-1}\\ &\triangleq BC \end{aligned} $$
因为$P^{-1}$是可逆矩阵，$\begin{bmatrix}E_r\\0\end{bmatrix}$是一个列满秩矩阵，所以$B=P^{-1}\begin{bmatrix}E_r\\0\end{bmatrix}$仍是一个列满秩矩阵；同理，$C=\begin{bmatrix}E_r&0\end{bmatrix}Q^{-1}$是一个行满秩矩阵
矩阵满秩分解的计算
如何在给定矩阵$A$的情况下，求出矩阵$B,C$呢？
设
$$ A = [\alpha_1,\alpha_2,...,\alpha_n]\\ B = [\beta_1,\beta_2,...,\beta_r], 其中\beta_1,...,\beta_r线性无关 $$
所以
$$ \begin{aligned} &A=BC\\ &\Rightarrow[\alpha_1,\alpha_2,...,\alpha_n]=[\beta_1,...,\beta_r]\begin{bmatrix}c_{11}&\cdots &c_{1n}\\\vdots &\ddots&\vdots\\c_{r1}&\cdots &c_{rn}\end{bmatrix} \end{aligned} $$
实际上我们可以取$\beta_1,...,\beta_r$为$\alpha_1,...,\alpha_n$的一个极大线性无关组，因此$B$就是矩阵$A$列向量组的一个极大线性无关组，$C$就是用该线性无关组去表示$A$时的系数
例1
求矩阵$A=\begin{bmatrix}1&4&-1&5&6\\2&0&0&0&-14\\-1&2&-4&0&1\\2&6&-5&5&-7\end{bmatrix}$的满秩分解
解：对矩阵$A$只作初等行变换
$$ A=\begin{bmatrix}1&4&-1&5&6\\2&0&0&0&-14\\-1&2&-4&0&1\\2&6&-5&5&-7\end{bmatrix}\to ···\to\begin{bmatrix}1&0&0&0&-7\\0&1&0&\frac{10}{7}&\frac{29}{7}\\0&0&1&\frac{5}{7}&\frac{25}{7}\\0&0&0&0&0\end{bmatrix} $$
$A$的秩为3，且前三个列向量线性无关，故
$$ B = \begin{bmatrix}1&4&-1\\2&0&0\\-1&2&-4\\2&6&-5\end{bmatrix}，C=\begin{bmatrix}1&0&0&0&-7\\0&1&0&\frac{10}{7}&\frac{29}{7}\\0&0&1&\frac{5}{7}&\frac{25}{7}\end{bmatrix} $$
例2
求矩阵$A=\begin{bmatrix}2&1&-2&3&1\\2&5&-1&4&1\\1&3&-1&2&1\end{bmatrix}$的满秩分解
解：对矩阵$A$只作初等行变换
$$ A=\begin{bmatrix}2&1&-2&3&1\\2&5&-1&4&1\\1&3&-1&2&1\end{bmatrix}\to ···\to \begin{bmatrix}1&0&0&\frac{8}{5}&-\frac{2}{5}\\0&1&0&\frac{1}{5}&\frac{1}{5}\\0&0&1&\frac{1}{5}&-\frac{4}{5}\end{bmatrix} $$
$A$的秩为3，且前三个列向量线性无关，故
$$ B = \begin{bmatrix}2&1&-2\\2&5&-1\\1&3&-1\end{bmatrix},C = \begin{bmatrix}1&0&0&\frac{8}{5}&-\frac{2}{5}\\0&1&0&\frac{1}{5}&\frac{1}{5}\\0&0&1&\frac{1}{5}&-\frac{4}{5}\end{bmatrix} $$
QR分解的应用
QR分解的内容请看矩阵分析（十一）
请用$QR$分解的方法解方程组$Ax=b$，实际上$A$可逆的情况下，$x=A^{-1}b$，但是由于直接求$A^{-1}$过于复杂或者当$A$不可逆时，我们可以利用QR分解，将其转换为求$QRx=b$，于是就是求
$$ \begin{cases} Qy=b\\ Rx=y \end{cases} $$
因为$Q$是酉矩阵，所以$Q^{-1}=Q^H$，因此$y=Q^Hb$
由于$R$是正线上三角矩阵，不妨设$R = \begin{bmatrix}r_{11}&\cdots \\&r_{22}&\cdots \\&&\ddots\\&&&r_{nn}\end{bmatrix}$，则有
$$ \begin{bmatrix}r_{11}&\cdots \\&r_{22}&\cdots \\&&\ddots\\&&&r_{nn}\end{bmatrix}\begin{bmatrix}x_1\\\vdots \\x_n\end{bmatrix}=\begin{bmatrix}y_1\\\vdots \\y_n\end{bmatrix}\\ \Rightarrow \begin{cases}x_n=\frac{y_n}{r_{nn}}\\x_{n-1}=\frac{y_{n-1}-r_{nn}x_n}{r_{n-1,n-1}}\\\vdots\end{cases} $$
例3
用$QR$分解的方法解方程组$Ax=b$，其中$A=\begin{bmatrix}-3&1&2\\1&1&1\\1&-1&0\\1&-1&1\end{bmatrix},b=\begin{bmatrix}1\\0\\-2\\1\end{bmatrix}$
解：将$A=(\alpha_1,\alpha_2,\alpha_3)$的列向量$\alpha_1,\alpha_2,\alpha_3$用Schmidt方法标准正交化得
$$ \begin{aligned} v_1 &= (-\frac{3}{\sqrt{12}},\frac{1}{\sqrt{12}},\frac{1}{\sqrt{12}},\frac{1}{\sqrt{12}})^T\\ v_2&=(0,\frac{2}{\sqrt{6}},-\frac{1}{\sqrt{6}},-\frac{1}{\sqrt{6}})^T\\ v_3&=(0,0,-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})^T \end{aligned} $$
令$Q=(v_1,v_2,v_3)$，则
$$ \begin{aligned} &R=Q^HA=\begin{bmatrix}2\sqrt{3}&-\frac{2}{3}&\frac{4}{\sqrt{3}}\\0&\frac{4}{\sqrt{6}}&\frac{1}{\sqrt{6}}\\0&0&\frac{1}{\sqrt{2}}\end{bmatrix}\\ &R^{-1}=\begin{bmatrix}\frac{\sqrt{3}}{6} & \frac{\sqrt{6}}{12} & -\frac{3 \sqrt{2}}{4} \\ 0 & \frac{\sqrt{6}}{4} & -\frac{\sqrt{2}}{4} \\ 0 & 0 & \sqrt{2}\end{bmatrix} \end{aligned} $$
所以
$$ x = R^{-1}Q^Hb=\begin{bmatrix}-\frac{1}{4} & \frac{1}{4} & \frac{3}{4} & -\frac{3}{4} \\ 0 & \frac{1}{2} & 0 & -\frac{1}{2} \\ 0 & 0 & -1 & 1\end{bmatrix}\begin{bmatrix} 1 \\ 0 \\ -2 \\ 1 \end{bmatrix}=\begin{bmatrix} -\frac{5}{2} \\ -\frac{1}{2} \\ 3 \end{bmatrix} $$
矩阵的LU分解
LU分解（LU Decomposition）是矩阵分解的一种，可以将一个矩阵分解为一个单位下三角矩阵和一个上三角矩阵的乘积，以四阶矩阵为例
$$ L = \begin{bmatrix}1&0&0&0\\*&1&0&0\\*&*&1&0\\*&*&*&1\end{bmatrix}, U=\begin{bmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{bmatrix} $$
LU矩阵是否一定存在？答案是否，具体看下面的例子
设$\begin{bmatrix}0&1\\1&0\end{bmatrix}=\begin{bmatrix}a&0\\b&c\end{bmatrix}\begin{bmatrix}l&m\\0&n\end{bmatrix}$，则应该满足如下4个式子
$$ \begin{cases} al=0\\ am=1\\ bl=1\\ bm+cn=0 \end{cases} $$
由$al=0$得$a=0$或$l=0$，但实际上这两种情况带入上面的式子都会推出矛盾，因此不是所有情况LU分解都存在
LU分解定理：设$A\in \mathbb{C}_n^{n\times n}$，$A$有唯一的LU分解$\Leftrightarrow A$的各阶顺序主子式$\Delta k \neq 0,\ k=1,2...,n$
$k$阶顺序主子式指的是矩阵左上角$k\times k$个元素组成的行列式
将矩阵$A$分解为$L$和$U$之后，解方程组$Ax=b$就变得简单了，因为$A=LU$，所以$(LU)x=b\Rightarrow L(Ux)=b\Rightarrow \begin{cases}Ly=b\\Ux=y\end{cases}$
所以$x=U^{-1}y=U^{-1}L^{-1}b$
LU矩阵的求法
实际上LU矩阵有非常多的求法，这里我举一种比较简单的待定系数法
设$A = \begin{bmatrix}2&3&4\\1&1&9\\1&2&-6\end{bmatrix}$，求矩阵$A$的LU分解矩阵$L$和$U$
解：令
$$ L=\begin{bmatrix}1&0&0\\l_1&1&0\\l_2&l_3&1\end{bmatrix},U = \begin{bmatrix}u_1&u_2&u_3\\0&u_4&u_5\\0&0&u_6\end{bmatrix} $$
由于$A=LU$，所以有
$$ \begin{cases} u_1=2\\ u_2=3\\ u_3=4\\ l_1u_1=1\\ l_1u_2+u_4=1\\ l_1u_3+u_5=9\\ l_2u_1=1\\ l_2u_2+l_3u_4=2\\ l_2u_3+l_3u_5+u_6=-6 \end{cases} $$
上面的方程组非常容易解，最后求出
$$ L = \begin{bmatrix}1&0&0\\\frac{1}{2}&1&0\\\frac{1}{2}&-1&1\end{bmatrix},U=\begin{bmatrix}2&3&4\\0&-\frac{1}{2}&7\\0&0&-1\end{bmatrix} $$
矩阵的SVD分解
SVD分解定理：设$A\in \mathbb{C}_r^{m\times n}$，则
- 对$\mathrm{rank}(A)=r$的矩阵$A$，矩阵$A^HA$的非零特征值有$\lambda_1 \geqslant \lambda_2 \geqslant ··· \geqslant \lambda_r >0$，则称正数$\sigma_i = \sqrt{\lambda_i}$为矩阵$A$的奇异值
- 存在酉矩阵$U,V$使$U^{-1}AV = \Sigma = \left[ \begin{array}{c c c|c} \sigma_1\\ &\ddots \\&& \sigma_n& 0 \\ \hline 0&&& 0 \end{array} \right]_{m\times n}$，其中$\sigma_1≥\sigma_2≥···≥\sigma_r>0$
SVD分解的求法
- 由特征多项式$|\lambda E - A^HA| = 0$求得特征值$\lambda_1 \geqslant \lambda_2 \geqslant .. \geqslant \lambda_n$（务必按照从大到小排列），以及每个特征值对应的特征向量$(\alpha_1, \alpha_2, ..., \alpha_n)$
- 对特征向量进行施密特正交化和单位化，得到单位正交向量组$V = (v_1, v_2, ..,v_n)$
- 对于非零特征值$\lambda_1, ..., \lambda_r$对应奇异值$\sigma_1, ... , \sigma_r$，于是有${\color{red} {u_i = \frac{1}{\sigma_i}Av_i}}$，这样得到了$r$个列向量，剩余的$u_{r+1},...,u_{n}$通过方程$u_i^T x = 0$求得（$u_i$必须是标准正交的）
- 于是得到$A=U \Sigma V^H$
实际上$A^HA$是一个半正定矩阵，其特征值一定非负
例4
已知$A = \begin{bmatrix}1&2\\0&0\\0&0\end{bmatrix}$，求$A$的奇异值
解：因为$A^HA=\begin{bmatrix}5&0&0\\0&0&0\\0&0&0\end{bmatrix}$，$A^HA$的特征值为$5,0,0$，故$A$的奇异值为$\sqrt{5}$
例5
已知$A = \begin{bmatrix}1&1\\0&0\\1&1\end{bmatrix}$，求$A$的SVD分解矩阵$U$和$V$
解：$A^HA = \begin{bmatrix}2&2\\2&2\end{bmatrix}$，求得$A^HA$的特征值为$\lambda_1=4,\lambda_2=0$，且对应的特征向量分别为$\alpha_1=\begin{bmatrix}1,1\end{bmatrix}^T,\alpha_2=[-1,1]^T$，将其单位正交化后得
$$ \begin{aligned} v_1&=\begin{bmatrix}\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\end{bmatrix}^T\\ v_2&=\begin{bmatrix}-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\end{bmatrix}^T \end{aligned} $$
于是有
$$ V = \begin{bmatrix}\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix} $$
因为$u_1=\frac{1}{2}Av_1=\begin{bmatrix}\frac{1}{\sqrt{2}}\\0\\\frac{1}{\sqrt{2}}\end{bmatrix}$，解方程组$u_1^Tx=0$得
$$ \begin{aligned} x_1 &= u_2 = \begin{bmatrix}\frac{1}{\sqrt{2}}\\0\\-\frac{1}{\sqrt{2}}\end{bmatrix}\\ x_2 &= u_3 = \begin{bmatrix}0\\1\\0\end{bmatrix} \end{aligned} $$
故
$$ U = \begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0\\0&0&1\\\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&0\end{bmatrix} $$
验算可得$U^{-1}AV=\Sigma$
例6
求$A=\begin{bmatrix}1&1&1\\1&1&1\end{bmatrix}$的奇异值分解
解：$A^HA = \begin{bmatrix}2&2&2\\2&2&2\\2&2&2\end{bmatrix}$，求得$A^HA$的特征值为$\lambda_1=6,\lambda_2=\lambda_3=0$，且对应的特征向量分别为$\alpha_1=\begin{bmatrix}1,1,1\end{bmatrix}^T,\alpha_2=[1, 0,-1]^T,\alpha_3 = [0,1,-1]^T$，将其单位正交化后得
$$ \begin{aligned} v_1&=\begin{bmatrix}\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}}\end{bmatrix}^T\\ v_2&=\begin{bmatrix}\frac{1}{\sqrt{2}},0,-\frac{1}{\sqrt{2}}\end{bmatrix}^T\\ v_3&=\begin{bmatrix}-\frac{1}{\sqrt{6}}, \frac{\sqrt{6}}{3},-\frac{1}{\sqrt{6}}\end{bmatrix}^T \end{aligned} $$
于是有
$$ V = \begin{bmatrix}\frac{1}{\sqrt{3}}&\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{6}}\\\frac{1}{\sqrt{3}}&0&\frac{\sqrt{6}}{3}\\\frac{1}{\sqrt{3}}&-\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{6}}\end{bmatrix} $$
因为$u_1=\frac{1}{\sqrt{6}}Av_1=\begin{bmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{bmatrix}$，解方程组$u_1^Tx=0$得
$$ \begin{aligned} x_1 &= u_2 = \begin{bmatrix}\frac{1}{\sqrt{2}}\\-\frac{1}{\sqrt{2}}\end{bmatrix}\\ \end{aligned} $$
故
$$ U = \begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\end{bmatrix} $$
验算可得$U^{-1}AV=\Sigma$
