矩阵分解的五种方法

2.1 矩阵QR分解

一、QR分解定义

定理：设\(A\)是\(n\)阶实（复）非奇异方阵，则存在正交（酉）矩阵\(Q\)和正线上三角矩阵\(R\)使\(A\)有QR分解，且分解唯一。其证明可以有施密特正交化的推导过程证明。

对于非方阵\(m\times n\) 实（复）矩阵，且\(n\)个列线性无关，则\(A=QR\)其中\(Q_{m\times m}\)为实（复）正交矩阵，\({R}~=~\begin{pmatrix}{R}_1\\0\end{pmatrix}\)，其中\(R_{1}\)为正线上三角阵。也可以是\(Q_{m\times n}\) 正交矩阵，\(R_{n\times n}\)由\(Q^TA\)计算得到。

第一种方法相当于先将矩阵补成线性无关的方阵，然后再进行与方阵相同的方法。最终的分解结果相当于把R中补上的列切掉就好。

二、计算QR的方法

1. 施密特正交化法

• 先对矩阵A做施密特正交化得到标准正交向量得到矩阵Q，Q为标准正交向量组的列向量，
• 由于正交过程中除了模，所以计算\(\Lambda\)为模的对角矩阵乘正交向量的系数。注意正交向量的系数是以列排序的对角矩阵，每一列倒叙对应着标准化过程的系数，该系数矩阵为\(K\)。
• \[A=Q\Lambda K=QR\]

\[\begin{cases} b_1 &= a_1 \\ b_2 &= a_2 - k_{21}b_1 \\ &\vdots \\ b_n &= a_n - k_{n,n-1}b_{n-1} - \cdots - k_{n,1}b_1 \end{cases}\]

2. Givens变换

• 定义：Givens矩阵形式如下，其中满足\(c^2+s^2=1\) (\(c_{ii}=c_{jj}=c, s_{ij}=s_{ji}=s\))。由Givens矩阵定义的变换为Givens变换， Givens矩阵是正交矩阵

\(T_{ij}=\begin{bmatrix}1&\ldots&0&\ldots&0&\ldots&0\\\vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\0&\ldots&c_{ii}&\ldots&s_{ij}&\ldots&0\\\vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\0&\ldots&-s_{ji}&\ldots&c_{jj}&\ldots&0\\\vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\0&\ldots&0&\ldots&0&\ldots&1\end{bmatrix}_{\begin{array}{c}\\\\\end{array}}\) Givens矩阵的这种形式，相乘可其他向量，合适的位置放\(c\)和\(s\)以将对应位置的元素一个清零，一个放大，因为其有清零效果，所以可以用于QR分解。

• 定理：设\(x=(\xi_{1}, \xi_{2},\dots, \xi_{n})^T \neq O\) 则存在有限个Givens矩阵的乘积，记作\(T\) 使\(Tx=\mid x\mid e_{1}\)

证明：上述矩阵中令\(c=\frac{\xi_{i}}{\sqrt{ \xi_{i}^2 + \xi_{j}^2}},\space s=\frac{\xi_{j}}{\sqrt{ \xi_{i}^2 + \xi_{j}^2}}\) 则有\(T_{ij}x=(\xi_{1}, \xi_{2}, \dots,\xi_{i-1}, \sqrt{ \xi_{i}^2+\xi_{j}^2 },\xi_{i+1}, \dots, \xi_{j-1}, 0,\xi_{j+1}, \dots, \xi_{n-1}, \xi_{n})\) 可以看到其清理了\(j\)位的数据，因此参照此方法，可以不断清理所有数据，直到变为单位向量。

• 定理：任何\(n\)阶实非奇异矩阵可通过左乘有限个Givens矩阵化为上三角矩阵。

使用多个Givens矩阵相乘，最终得到\(TA=R\) 由于\(T\) 为正交矩阵，所以\(A=T^TR\) 为\(QR\)分解，三阶矩阵需要乘3个Givens矩阵，相对简单，四阶矩阵要乘6个，这种方法适合程序完成。

3. Householder变换

• 定义Householder矩阵为单位列向量\(u\in R^n\) 称\(H=I-2uu^T\) 为Householder矩阵。其满足\(H^T=H\), \(H^TH=I\) 。其特征多项式为\((\lambda-1)^{n-1}(\lambda+1)\)

• 定理：任意给定非零列向量\(x\in R^n\) 及单位列向量\(z\in R^n\)，存在Householder矩阵\(H\) 使得 \(Hx=\mid x\mid z\) 。Householder矩阵可以将一个列向量直接变换为单位向量。 \(u=\frac{x-\mid x\mid z}{\mid x-\mid x\mid z\mid }\)

• 定理：任何\(n\)阶实非奇异矩阵可通过左乘有限个Householder矩阵化为上三角矩阵。

总结：Givens矩阵可以变换向量将一个维度变为0，Householder矩阵能直接将整个向量变为只有一个维度的单位向量。Givens矩阵是两个Householder矩阵的乘积。

2.2 正规矩阵及Schur分解

一、Schur分解

设\(A\in C^{n\times n}\) 则存在酉矩阵\(U\)满足下面方程，即任意复方阵酉相似于一个上三角阵，其主对角元为\(A\)的特征值。其根据\(P^{-1}AP=B\)和QR分解可证。 \({U^HAU}=\begin{pmatrix}\lambda_1&&&*\\&\lambda_2&&\\&&\ddots&\\\mathbf{0}&&&\lambda_n\end{pmatrix}\) 若A的特征值均为实数，存在正交矩阵\(Q\)满足下面方程，即任意实数仿真正交相似于一个上三角阵，其对角元为A的特征值。 \({Q^TAQ}=\begin{pmatrix}\lambda_1&&&*\\&\lambda_2&&\\&&\ddots&\\\mathbf{0}&&&\lambda_n\end{pmatrix}\) 因此Schur分解为 \({A}=U\begin{pmatrix}\lambda_1&&&*\\&\lambda_2&&\\&&\ddots&\\\mathbf{0}&&&\lambda_n\end{pmatrix}U^H\) Schur引理根据QR分解说明矩阵通过正交矩阵变换可以换位上三角矩阵，但是如果是对角矩阵可能会有更好的性质，所以接下来我们就要研究加上什么条件可以使得正交矩阵变换后得到对角矩阵。

二、正规矩阵

定义：设\(A\in C^{n\times n}\) 且\(A^HA=AA^H\)。则称\(A\)为正规矩阵。对称矩阵，正交矩阵，Hermite矩阵，酉矩阵都是正规矩阵。

定理：

• 设\(A\in C^{n\times n}\) 且\(A\)酉相似于对角矩阵 等价于 \(A\)为正规矩阵
• 设\(A\in R^{n\times n}\) 且\(A\)的特征值都是实数，则\(A\)正交相似于对角矩阵 等价于 \(A\)为正规矩阵

推论

• \(A\)是正规矩阵，则\(A\)酉相似的矩阵一定是正规矩阵
• \(A\)是正规矩阵，且是三角矩阵，则\(A\)必为对角矩阵
• \(A\)是实对称矩阵，则正交相似对角矩阵
• \(A\)是Hermite矩阵，则酉相似对角矩阵，且满足下列式子，称为矩阵\(A\)的谱分解\(\begin{aligned}A&=\boldsymbol{P}\boldsymbol{\Lambda}P^H=\left(\boldsymbol{p}_1,\boldsymbol{p}_2,\cdots,\boldsymbol{p}_n\right)\begin{pmatrix}\lambda_1&&&\\&\lambda_2&&\\&&\ddots&\\&&&\lambda_n\end{pmatrix}\begin{pmatrix}\boldsymbol{p}_1^H\\\boldsymbol{p}_2^H\\\cdots\\\boldsymbol{p}_n^H\end{pmatrix}\\&=\lambda_1\left(\boldsymbol{p}_1\boldsymbol{p}_1^H\right)+\lambda_2\left(\boldsymbol{p}_2\boldsymbol{p}_2^H\right)+\cdots+\lambda_n\left(\boldsymbol{p}_n\boldsymbol{p}_n^H\right)\end{aligned}\)
• \(n\)阶正规矩阵有\(n\)个线性无关的特征向量
• \(A\)为\(n\)阶正规矩阵 等价于 \(A\)有\(n\)个特征向量构成\(C^n\) 的一组标准正交基
• 正规矩阵属于不同特征值的特征向量彼此正交
• \(A\)为实对称矩阵 等价于\(A\)的特征值均为实数且存在正交矩阵\(Q\)使得 \(Q^TAQ=diag\{\lambda_{1},\dots\lambda_{n}\}\)
• \(A\) 为正交矩阵 等价于 \(A\)的特征值的模为1，\(\mid\lambda_{i}\mid=1\) 且存在正交矩阵\(U\) 使得\(U^TAU=diag\{\lambda_{1},\dots\lambda_{n}\}\)

计算：求解正规矩阵对角化的正交矩阵\(Q\)

其方法与计算相似对角化的方法相同，先计算矩阵的特征值，然后计算每个特征值的特征向量。但是由于计算的矩阵\(Q\) 为正交矩阵，因此需要将相同特征值的特征向量单位正交化，在组成的矩阵即为变换矩阵\(Q\)

2.3 矩阵的满秩分解

定义：设\(A\in C_{r}^{m\times n}(r>0)\) 如果存在矩阵\(F\in C_{r}^{m\times r}\) 和\(G\in C_{r}^{r\times n}\) 使得\(A=FG\) 则称为矩阵\(A\) 的满秩分解。

定理：\(A\in C_{r}^{m\times n}(r>0)\) 有满秩分解。可有初等行变化加分块矩阵证明。且可证明满秩分解不唯一。

定义：初等行变换化为的标准型称为Hermiter标准型，形如如下表示方法。

\[\begin{aligned}B=&\begin{pmatrix} 0&\cdots&0&1&*&\cdots&*&0&*&\cdots&*&0&*&\cdots&*\\ 0&\cdots&0&0&0&\cdots&0&1&*&\cdots&*&0&*&\cdots&*\\ \cdots&&\cdots&&\cdots&&\cdots&&\cdots&&\cdots&&\cdots&&\cdots\\ 0&\cdots&0&0&0&\cdots&0&0&\cdots&\cdots&0&1&*&\cdots&*\\ 0&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&0&\vdots&&0\\ \cdots&&\cdots&&\cdots&&\cdots&&\cdots&&\cdots&&\vdots&&\cdots\\ 0&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&0&0&&0 \end{pmatrix}\\& ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~k_1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~k_2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~k_r\end{aligned}\]

定义：以\(n\) 阶单位矩阵\(I_{n}\) 的\(n\) 个列向量\(e_{1}, e_{2}, \dots, e_{n}\) 构成的\(n\)阶矩阵\(P=(e_{j_{1}}, e_{j_{2}}\dots, e_{j_{n}})\) 称为置换矩阵。置换矩阵的作用是交换行。

满秩分解方法：设\(A\in C_{r}^{m\times n}(r>0)\) 的Hermite标准型为\(B\) ，那么\(A\)的满秩分解中，可取\(F\) 为\(A\) 的\(k_{1}, k_{2}, \dots k_{r}\) 列构成\(m\times r\) 矩阵，其中这些列对应标准型中只有1元素的列，\(G\)为\(B\)的前\(r\)行构成的\(r\times n\)矩阵。

行变换的过程其实是在找矩阵极大线性无关组的过程，最终列中只有1的列就是原始矩阵的极大线性无关组，根据标准型的系数，可以得到其他列如果用极大线性无关组表示，因此最终的形式就是原始矩阵的极大线性无关组这几列乘换件后的Hermite型矩阵，就是满秩分解的结果。

使用满秩分解的方法可以证明 \(rank(A_{1}+A_{2})\leq rank(A_{1})+rank(A_{2})\)

2.4 矩阵的奇异值分解

一、奇异值分解

引理：

• \(A^HA\)与\(AA^H\)为半正定Hermite矩阵，且非0特征值相等。
• \(rank(A^HA)=rank(AA^H)=rank(A)\) ==重要公式，其证明方法是利用核空间的方法，证明秩相等==
• 设\(A \in C^{m\times n}\) 则\(A=O\) 与\(A^HA=O\) 等价

定义：设\(A \in C^{m\times n}\) 则\(A^HA\)的特征值为\(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_r>\lambda_{r+1}=\cdots=\lambda_n=0\) 则称\(\sigma_i=\sqrt{\lambda_i}(i=1,2,\cdots,n)\) 为\(A\)的奇异值。

定理：设\(A \in C^{m\times n}\) 则存在\(m\)阶酉矩阵\(U\)和\(n\)阶酉矩阵\(V\)满足下面等式， \(V_{m\times m}^HA_{\mathrm{m\times n}}{\operatorname*{U_{n\times n}=}}\begin{pmatrix}\Sigma_{\mathrm{r\times r}}&\boldsymbol{O}\\\boldsymbol{O}&\boldsymbol{O}\end{pmatrix}_{\mathrm{m\times n}}\) SVD分解即为如下公式，其中\(\Sigma=diag(\sigma_{1}, \sigma_{2}, \dots, \sigma_{r})\)

\[A_{\mathrm{m\times n}}=V_{m\times m}\begin{pmatrix}\Sigma_{\mathrm{r\times r}}&\boldsymbol{O}\\\boldsymbol{O}&\boldsymbol{O}\end{pmatrix}_{\mathrm{m\times n}}U_{n\times n}^H\]

证明：

• 由于\(A^HA\) 正规矩阵，所以可以正交相似于对角矩阵 。因此有一组标准正交基\(u_{1}, u_{2},\dots u_{n}\) 。
• 根据特征值公式有\(A^HAu_{i}=\lambda_{i}u_{i}\) , 由于\(<Au_{i}, Au_{j}> = u_{j}^TA^TAu_{i}=\lambda_{i}u_{j}^Tu_{i}\) 由于正交基，所以当\(i\neq j\) 且\(i<rank(A)\)即\(\lambda_{i}\neq 0\) 时，\(<Au_{i}, Au_{j}> = 0\) ，当\(i=j\)时，\(<Au_{i}, Au_{j}> = \lambda\) 即\(\frac{Au_i}{\sqrt{\lambda}}\space(i\leq r)\)这组基也是标准正交的。
• 为了得到正交矩阵，还需要将\(\frac{Au_i}{\sqrt{\lambda}}\space(i\leq r)\)这组基扩充为\(m\)个，这样就可以得到\(A(u_{1}, u_{2},\dots u_{n})=(\boldsymbol{v}_1,\boldsymbol{v}_2,\cdots,\boldsymbol{v}_r,\boldsymbol{b}_1,\cdots,\boldsymbol{b}_{m-r})\begin{pmatrix}\sqrt{\lambda_1}&&&&\\&\sqrt{\lambda_2}&&&\boldsymbol{O}\\&&\ddots&&\\&&&\sqrt{\lambda_r}&\\&\boldsymbol{O}&&&\boldsymbol{O}\end{pmatrix}_{m\times n}\)

求法：

• 首先求解\(A^HA\)矩阵的特征值及特征向量，得到正交化的向量组即\(U\)矩阵。
• 利用前\(r\)个正交向量计算\(V\)矩阵向量，即\(V=AU_{r}\Sigma^{-1}\)
• 将该\(r\)个正交向量，扩充为\(m\)个组成\(V\)矩阵
• 最终得到奇异值分解结果为\(A=V\Lambda U^H\)。注意要对原来的特征值开根号作为奇异值。

性质：

• \(U\)的列向量是\(A^HA\)的特征向量，\(V\)的列向量是\(AA^H\)的特征向量。
• \[N(A)=L(u_{r+1}, u_{r+2}, \dots,u_{n})\]
• \[R(A)=L(v_{1}, v_{2}, \dots,v_{r})\]
• \[A=\sigma_1v_1u_1^H+\sigma_2v_2u_2^H+\cdots+\sigma_rv_ru_r^H\]

二、矩阵的正交相抵

设\(A\),\(B\)均为实\(m\times n\)矩阵，如果存在\(m\)阶正交矩阵\(U\)和\(n\)阶正交矩阵\(V\)，使\(B=U^{-1} AV\),则称\(A\)和\(B\)正交相抵。正交相抵可视为正交相似概念的推广。正交相抵矩阵有相同的奇异值。

证明：\(B^HB = V^HA^HUU^{-1}AV=V^HA^HAV\) 由于\(V\)为酉矩阵，因此\(B^HB\)与\(A^HA\) 酉相似，特征值相同，因此\(B\)与\(A\)的奇异值相同。

2.5 单纯形矩阵的谱分解

一、幂等矩阵及其性质

1. 定义

幂等矩阵定义：设\(A \in C^{n\times n}\) 若\(A^2=A\),则成\(A\)为幂等矩阵

投影定义：若\(C^n=V_{1}\oplus V_{2}\)，则对任意的\(x\)，可唯一的分解为\(x=y+z,y \in V_{1}, z\in V_{2}\) 称\(y\)为\(x\)在\(V_{1}\)的投影，称\(z\)为\(x\)在\(V_{2}\)的投影。

投影变换的定义：令\(E\in L(C_{n}, C_{n}), Ex=y\) 则称\(E\)为投影变换。

性质：

• 幂等矩阵为单纯矩阵， 且Jordan标准型为\(\begin{pmatrix}I{\mathrm{r}}&\boldsymbol{O}\\\boldsymbol{O}&\boldsymbol{O}\end{pmatrix}\)
• 幂等矩阵的特征值为0或者1
• \[rank(A)=tr(A)\]
• \(Ax=x\) 等价于\(x \in R(A)\)

定理：\(E\)是投影变换当且仅当\(E\) 是幂等矩阵。

二、谱分解

定理：设\(A\in C^{n\times n}\)的\(k\)个相异的特征值为\(\lambda_{1},\lambda_{2}, \dots, \lambda_{k}\)为\(A\)的单纯矩阵的充要条件是存在唯一的一组幂等矩阵\(E_{i}\in C^{n\times n},i=1,2,\dots,k\) 满足下面三个条件。其中\(\lambda_{i}\) 称为\(A\)的谱值，\(E_{i}\in C^{n \times n},i=1,2,\dots,k\) 称为\(A\)的谱阵，\(A=\sum_{i=1}^k\lambda_{i}E_{i}\)称为\(A\)的谱分解。

• \[E_{i}E_{j} = 0(i\neq j)\]
• \[\sum_{i=1}^{k}E_{i}=I\]
• \[A=\sum_{i=1}^k\lambda_{i}E_{i}\]

其证明是因为\(A\)可相似对角化，所以\(X^{-1}AX=diag(\lambda_{1}, \lambda_{2}, \dots,\lambda_{k})\) 将\(X^{-1}\)按列分块，\(X\)按行分块，分块的标准是统一特征值对应的特征向量的数量，经过计算可以得到谱分解的形式。并可以证明分块的乘积是幂等矩阵。

推论：设\(A\)为谱阵\(E_{i}\in C^{n \times n},i=1,2,\dots,k\)

• \(E_{i}=\frac{1}{\phi_{i}(\lambda_{i})}\phi_{i}(A),i=1,2,\dots,k\)其中\(\phi_{i}(\lambda)=\Pi_{l=1,l\neq i}^k(\lambda-\lambda_{l})\)
• 若\(f(\lambda)\)为任意多项式，则\(f(A)=f(\lambda_1)E_1+f(\lambda_2)E_2\cdots+f(\lambda_k)E_k\)特别地，\(\begin{aligned}A^m=(\sum_{i=1}^n\lambda_iE_i)^m=\lambda_1^mE_1+\lambda_2^mE_2\cdots+\lambda_k^mE_k\end{aligned}\)。利用该公式可以矩阵的高次幂。这也是除了用极小多项式算余式求矩阵高次幂的另一种方法。

谱分解其实是将矩阵分解为以特征向量为列的矩阵和含有特征值的对角矩阵。特征向量表示了此线性变换的主要变换方向，而特征值表示对应特征向量的重要性。

谱分解步骤：

• 计算矩阵\(A\)的特征值和特征向量，得出所有特征向量构成的矩阵\(X\)
• 求解矩阵\(X\)的逆矩阵\(X^{-1}\)
• 矩阵\(X\)的按列分块，每块对应着同一特征值对应的特征与矩阵\(X^{-1}\)对应的按行分块的行向量相乘得到的矩阵该块列或行对应的特征值的谱值。

技巧：计算谱分解也可以使用最小多项式的方法，根据最小多项式，已知谱阵的和为\(I\) 可以根据乘法和加法直接解出来。如果只有两个谱阵，可以直接联立\(A=\sum_{i=1}^k\lambda_{i}E_{i}\) 和\(\sum_{i=1}^{k}E_{i}=I\)。

定理：设\(A\in C^{n\times n}\)的\(k\)个相异的特征值为\(\lambda_{1},\lambda_{2}, \dots, \lambda_{k}\)为\(A\)为正规矩阵的充要条件是存在唯一的一组Hermite矩阵\(E_{i}\in C^{n\times n},i=1,2,\dots,k\) 满足谱分解的三个条件。

因此在算正规矩阵的谱分解的时候得到的特征向量要做正交化。