矩阵分解

具有特殊结构和性质的矩阵

数学中常见的具有特殊结构的矩阵

方阵

行数与列数都等于n 的叫做n阶方阵

只有方阵才可以计算行列式
方阵才有逆矩阵，且方阵有逆矩阵当且仅当方阵满秩
只有方阵才有伴随矩阵
只有方阵才有特征值与特征向量

对称矩阵

矩阵A是对称矩阵当且仅当

$A^T = A$

正(半)定矩阵

对角矩阵

非对角元素都为零元素的方阵叫做对角矩阵

三角矩阵

三角矩阵是对角元下方或对角元上方全是0的方阵

三角矩阵主对角线上元素均非零 $\Leftrightarrow$ 三角矩阵可逆
上三角、下三角矩阵的乘积还是上、下三角矩阵
上、下三角矩阵可逆则其逆矩阵也是上、下三角矩阵
设矩阵 A 为三角矩阵，那么矩阵 $A^k$ 主对角线上的元素满足 $(A^k)_{ii} =(A_ii)^k,i=1,2\cdots,n$

正交矩阵

正交矩阵指行向量和列向量是分别标准正交的方阵即

$A^TA = AA^T = I$

所以, $A^{-1} = A^T$

如果矩阵 $U\in \mathbb R^{m\times m},V\in\mathbb R^{n\times n} $ 是正交矩阵， $M\in \mathbb R^{m\times n},x\in \mathbb R^m$
- $||U||_2 =1, ||U||_F = \sqrt {m}$
- $||Ux||_2 = ||x||_2, ||Ux||_F = ||x||_F$
- $||UMV||_2 = ||M||_2,||UMV||_F = ||M||_F$

Dyads(并向量或单纯矩阵或秩1矩阵)

矩阵 $A\in \mathbb R^{m\times n}$ 具有如下形式：

$A = uv^T$

其中向量 $u\in \mathbb R^m,v\in \mathbb R^n$ ，则称其为dyad，也称并向量或单纯矩阵。如果 u 和 v 不为0，则我们称其为 秩1矩阵

LU 分解

LU 分解指将$n\times n$ 的矩阵A分解成两个三角矩阵的乘积

其中， L 为 $n\times n$ 单位下三角矩阵(对角元素为1)，U 是 $n\times n$ 上三角矩阵。

从秩1分解的角度分析 $A=LU$ , 可以将 A 写成若干个秩1矩阵和的形式：

$A = l_1u_1+\cdots+l_ru_r = \sum_{i=1}^r l_iu_i$

其中r为矩阵A的秩，若A是满秩，则 $r=n$ 。 $l_i$ 是 $L$ 的第$i$列；$u_i$ 是 $U$ 的第$i$行。 $l_iu_i$ 都是秩为1的矩阵，并且这个矩阵的前 $i-1$行和前$i-1$列的元素都是0

求矩阵A

$A=\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{pmatrix}$

的LU分解

我们要像剥洋葱一样一层一层地分解矩阵A，同时要记得 L 的对角线都是1

第一步

令 $u1$ 是 A 的第1行，$l_1$ 是A的第1列除以 $u{11}$ ,则：

$l_1u_1 =\begin{pmatrix} 1 \\ 4 \\ 7 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3\end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 8 & 12 \\ 7 & 14 & 21 \end{pmatrix}\\~~\\ A-l_1u_1 = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{pmatrix}-\begin{pmatrix} 1 & 2 & 3 \\ 4 & 8 & 12 \\ 7 & 14 & 21 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 \\ 0 & -3 & -6 \\ 0 & -6 & -11 \end{pmatrix}$

第二步

令 $u2$ 是 $A-l_1 u_1$ 的第2行，$l_2$ 是 $A-l_1u_1$ 的第二列除以$u{22}$

$l_2u_2 =\begin{pmatrix} 0 \\ 1 \\ 2 \end{pmatrix}\begin{pmatrix} 0 & -3 & -6\end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 \\ 0 & -3 & -6 \\ 0 & -6 & -12 \end{pmatrix}\\~~\\ A-l_1u_1-l_2u_2 = \begin{pmatrix} 0 & 0 & 0 \\ 0 & -3 & -6 \\ 0 & -6 & -11 \end{pmatrix}-\begin{pmatrix} 0 & 0 & 0 \\ 0 & -3 & -6 \\ 0 & -6 & -12 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$

第三步

令$u3$ 是$A-l_1u_1-l_2u_2$ 的第3行，$l_3$ 是 $A-l_1u_1-l_2u_2$ 的第3列除以$u{33}$ 即

$l_3 =\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}, u_3 = \begin{pmatrix} 0 & 0 & 1 \end{pmatrix}$

第四步，我们要把$l_1,l_2,l_3$ 相加得到$L$ ,$u_1,u_2,u_3$ 相加得到$U$

$A = LU = \begin{pmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 7 & 2 & 1 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 \\ 0 & -3 & -6 \\ 0 & 0 & 1 \end{pmatrix}$

QR 分解

QR分解指将矩阵A分解成列正交矩阵和上三角矩阵的乘积，形式如下：

$A = QR = \begin{pmatrix} q_1 & q_2 & q_3 \end{pmatrix} \begin{pmatrix} r_1 \\ r_2 \\ r_3 \end{pmatrix} = q_1r_1+q_2r_2+\cdots+q_nr_n$

其中 Q 是列正交矩阵，R是上三角矩阵。 $q_i$ 是 $Q$ 的列向量，$r_i$ 是 $R$ 的行向量。且 $q_ir_i$ 的前 $i-1$ 列都为0。

矩阵的QR分解可以通过 Gram-Schmidt 正交化，Household 变换，Givens变换等方法实现

Gram-Schmidt 正交化法

首先要求出单位化后的特征向量。我们定义投影操作为： $proj_u= \frac{}{}u$, 也就是获取a在u方向上的分量

对于一个满秩矩阵：$A=[a_1,\cdots,a_n]$

$u_1 = a_1, ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~e_1=\frac{u_1}{||u_1||}\\ u_2 = a_2-proj_{u_1}a_2 ~~~~~~~~~~~~~~~~~~~~~e_2=\frac{u_2}{||u_2||}\\ u_3=a_3-proj_{u_1}a_3-proj_{u_2}a_3~~e_3=\frac{u_3}{||u_3||}\\ u_k = a_k-\sum_{j=1}^{k-1}proj_{u_j}a_k,~~~~~~~~~~~~~~e_k=\frac{u_k}{||u_k||}$

矩阵A的QR分解就可以写为：

$Q = [e_1,\cdots,e_n]$

和

$R=$

分解方阵

$a_1 = (0,1,1)^T ,a_2=(1,1,0)^T,a_3=(1,0,1)^T$

我们先用正交化方法可得：其中$q_i$代表标准化后的 $b_i$

$b_1 = a_1 = (0,1,1)^T,~~|b_1| = \sqrt{2}\\ b_2 = a_2-\frac{[a_2,b_1]}{[b_1,b_1]}b_1=(1,1,0)^T-\frac{1}{2}(0,1,1)^T = (1,\frac{1}{2},-\frac{1}{2})^T,|b_2| = \frac{\sqrt{6}}{2}\\ b_3 = a_3-\frac{[a_3,b_2]}{[b_2,b_2]}b_1-\frac{[a_3,b_2]}{[b_2,b_2]}b_2 = (1,0,1)^T-\frac{1}{2}(0,1,1)^T-\frac{0.5}{1.5}(1,\frac{1}{2},-\frac{1}{2})^T = (\frac{2}{3},-\frac{2}{3},\frac{2}{3})^T \\$

现在来计算标准化后的矩阵：

$q_1 = \frac{1}{\sqrt 2}(0,1,1)^T\\ q_2 = \frac{1}{\sqrt 6}(2,1,-1)^T\\ q_3 = \frac{\sqrt 3}{2}(\frac{2}{3},-\frac{2}{3},\frac{2}{3})^T\\$

因此，

$Q = (q_1,q_2,q_3) = \begin{bmatrix} 0 & \dfrac{2}{\sqrt{6}} & \dfrac{1}{\sqrt{3}} \\ \dfrac{1}{\sqrt{2}} & \dfrac{1}{\sqrt{6}} & -\dfrac{1}{\sqrt{3}} \\ \dfrac{1}{\sqrt{2}} & \dfrac{-1}{\sqrt{6}} & \dfrac{1}{\sqrt{3}} \end{bmatrix}$ $R = \begin{bmatrix} |b_1| & [a_2,q_1] & [a_3,q_1] \\ 0 & |b_2| & [a_3,q_2] \\ 0 & 0 & |b_3| \end{bmatrix} =\begin{bmatrix} \sqrt{2} & \dfrac{1}{\sqrt{2}} & \dfrac{1}{\sqrt{2}} \\ 0 & \dfrac{\sqrt{6}}{2} & \dfrac{1}{\sqrt{6}} \\ 0 & 0 & \dfrac{2}{\sqrt{3}} \end{bmatrix}$

谱分解

设对称矩阵A为n阶方阵，如果A可以被分解为$A=Q\Lambda Q^T$ , 其中 $Q=[q_1,q_2,\cdots,q_n]$ 是由特征向量 $q_1,q_2\cdots,q_n$ 组成的n阶方阵， $\Lambda = diag(\lambda_1,\lambda_2,\cdots,\lambda_n)$ 是由特征值$\lambda_1,\lambda_2\cdots,\lambda_n$ 组成的n阶对角矩阵，则这种分解叫做对称矩阵的谱分解或者特征分解

求解对称方程 $A\in \mathbb R^{n\times n}$ 的特征分解步骤

计算矩阵A的特征值$\lambda_1\cdots,\lambda_n$ 即求特征方程 $|A-\lambda I| = 0$ 的n个根
求特征值对应的n个相互正交的特征向量 $q_1,\cdots,q_n$即求解方程组并单位化
$Aq_i = \lambda_iq_i,i=1,\cdots,n$
记矩阵 $Q=(q_1,\cdots,q_n)$
最终得到矩阵A的特征分解为
$A = Q\begin{pmatrix} \lambda_1 & & \\ & \cdots & \\ & & \lambda_n \end{pmatrix}Q^T$

求实对称矩阵的特征分解

$A =\begin{bmatrix} 2& 1\\ 1 & 2 \end{bmatrix}$

首先我们计算特征向量

$|\lambda I-A| =\begin{bmatrix}\lambda-2& -1\\ -1 & \lambda-2 \end{bmatrix}=0\\$

特征值：$\lambda_1=3,\lambda_2=1$

带入求解并单位化： $q_1 = (\frac{1}{\sqrt 2},\frac{1}{\sqrt 2})^T,q_2 = (-\frac{1}{\sqrt2},\frac{1}{\sqrt2})^T$

写出左特征向量方阵Q和特征值方阵 $\Lambda$

$Q =[q_1,q_2] =\begin{bmatrix} \frac{1}{\sqrt2}& -\frac{1}{\sqrt 2}\\ \frac{1}{\sqrt 2} & \frac{1}{\sqrt2} \end{bmatrix},\Lambda =\begin{bmatrix} \lambda_1 & \\ & \lambda_2 \end{bmatrix} = \begin{bmatrix} 3 &\\ & 1 \end{bmatrix}$

$p=(\alpha_1,\alpha_2,\alpha_3),(p^{-1})^T=(\beta_1,\beta_2,\beta_3)$

$G_1 = \alpha_1\beta_1^T+\alpha_2\beta_2^T\\~\\ G_2 = \alpha_3\beta_3^T$

A和$G_1,G_2$的关系就是谱分解

Cholesky 分解

设 $A = (a_{ij})\in R^{n\times n}$是对称正定矩阵， $A=GG^T$称为矩阵A的Cholesky 分解。其中，$G\in R^{n\times n}$ 是一个具有正的对角线元素的下三角矩阵。

$G =\begin{pmatrix} g_{11} & & & \\ g_{21} & g_{22} & & \\ \cdots & \cdots & \cdots &\\g_{n1}&g_{n2}&\cdots&g_{nn} \end{pmatrix}$ $l_{11}=\sqrt{a_{11}}\\~\\ l_{i1} = \frac{a_{i1}}{l_{11}} ~(i=2,3,\cdots,n)$

这样就得到了第一列元素

假设已经算出L的前 $k-1$ 列元素，通过 $a{kk} = \sum{i=1}^k l^2_{ki}$

得到：

$l_{kk} = \sqrt{a_{kk}-\sum_{i=1}^{k-1}l_{ki}^2}$

进一步再由：

$a_{ik} = \sum_{j=1}^{k-1}l_{ij}l_{kj}+l_{ik}l_{kk}$

得到：

$l_{ik} = \frac{a_{ik}-\sum_{j=1}^{k-1}l_{ij}l_{kj}}{l_{kk}},(i = k+1,\cdots,n)$

也就是可以通过L的前k-1列来求出第k列

一般来说只会让我们求3阶的矩阵分解，这时候要求六个元素

第一阶段，求 $l{11}=\sqrt{a{11}}$
再求第一列的两个元素： $l{21}=\frac{a{21}}{l{11}},l{31}=\frac{a{31}}{l{11}}$
第二阶段，求$l{22} = \sqrt{a{22}-l^2_{21}}$
求$l{32}=\frac{a{32}-l{31}l{21}}{l_{22}}$
第三阶段，求 $l{33}=\sqrt{a{33}-(l{31}^2+l^2{32})}$