矩阵分析（十三）矩阵分解

矩阵的满秩分解

设A\in \mathbb{C}_r^{m\times n}，则存在B\in \mathbb{C}_r^{m\times r}, C\in \mathbb{C}_r^{r\times n}，满足

\mathbb{C}_r表示矩阵的秩为r

实际上上述定理用文字描述就是，一个亏秩的矩阵可以分解成一个列满秩与行满秩矩阵的乘积

证明：因为rank(A)=r，所以一定可以找到与A相似的一个矩阵

因此存在两个可逆矩阵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的秩为3，且前三个列向量线性无关，故

例2

求矩阵A=\begin{bmatrix}2&1&-2&3&1\\2&5&-1&4&1\\1&3&-1&2&1\end{bmatrix}

解：对矩阵A只作初等行变换

A的秩为3，且前三个列向量线性无关，故

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）是矩阵分解的一种，可以将一个矩阵分解为一个单位下三角矩阵和一个上三角矩阵的乘积，以四阶矩阵为例

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}

$$ \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

解：令

由于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} $$

上面的方程组非常容易解，最后求出

矩阵的SVD分解

SVD分解定理：设A\in \mathbb{C}_r^{m\times n}，则

1. 对rank(A)=r的矩阵A，矩阵A^HA的非零特征值有\lambda_1 \geqslant \lambda_2 \geqslant ··· \geqslant \lambda_r >0\sigma_i = \sqrt{\lambda_i}为矩阵A的奇异值
2. 存在酉矩阵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分解的求法

1. 由特征多项式|\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} $$

于是有

因为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^{-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} $$

于是有

因为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^{-1}AV=\Sigma