矩阵对角化与分解

1 相似对角化（特征值分解）

1.1 结论

一个 特征向量都线性无关（特征值对应的子空间维度等于特征值重数） 的 \(n\) 维矩阵 \(A\)，可以写成如下形式

\[A = W \Sigma W^{-1}\]

其中，\(\Sigma\) 是由 \(A\) 的特征值组成的对角阵，\(W\) 是由 \(A\) 的特征向量组成的矩阵，\(W\) 的每一列都是 \(A\) 的一个特征向量。

进一步地，将 \(W\) 的列向量长度归一化后，得到的 \(W_{norm}\) 是一个正交矩阵，继而有

\[A = W_{norm} \Sigma W_{norm}^\top\]

1.2 思考过程

我们讨论一个 \(n\) 维矩阵 \(A\)。

首先，我们考察矩阵 \(A\) 的特征值，它们满足

\[A\mathbf{x}_i = \lambda_i \mathbf{x}_i\]

这里的 \(\mathbf{x}_i\) 是一个 \(n\times 1\) 的向量。

一个很自然的想法是，我们把 \(n\) 个特征值对应的上式合在一起，用矩阵表示，那么就是

\[A\begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 &...&\mathbf{x}_n\end{bmatrix} = \begin{bmatrix}\lambda_1\mathbf{x}_1 & \lambda_2\mathbf{x}_2 &...&\lambda_n\mathbf{x}_n\end{bmatrix}\]

下面这一步思考需要一点灵感。构造一个矩阵 \(B\)：

\[B = \begin{bmatrix}\mathbf{b}_{1,1\times n}\\\mathbf{b}_2\\...\\\mathbf{b}_n\end{bmatrix}_{n\times n}\]

让 \(B\) 左乘 \(A\begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n\end{bmatrix}\) ：

\[\begin{bmatrix}\mathbf{b}_1\\\mathbf{b}_2\\...\\\mathbf{b}_n\end{bmatrix}\begin{bmatrix}\lambda_1\mathbf{x}_1 & \lambda_2\mathbf{x}_2 &...&\lambda_2\mathbf{x}_n\end{bmatrix} = \begin{bmatrix}\lambda_1\mathbf{b}_1\mathbf{x}_1 & \lambda_2\mathbf{b}_1\mathbf{x}_2 &...&\lambda_n\mathbf{b}_1\mathbf{x}_n\\ \lambda_1\mathbf{b}_2\mathbf{x}_1 & \lambda_2\mathbf{b}_2\mathbf{x}_2 & ... & \lambda_n\mathbf{b}_2\mathbf{x}_n\\ ...\\ \lambda_1\mathbf{b}_n\mathbf{x}_1 & \lambda_2\mathbf{b}_n\mathbf{x}_2 & ... & \lambda_n\mathbf{b}_n\mathbf{x}_n\end{bmatrix}\]

不难发现，如果 \(\mathbf{b}_i\mathbf{x}_i = 1\) 且 \(\mathbf{b}_i\mathbf{x}_j = 0, \ i \neq j\)，上式的结果就是一个由矩阵 \(A\) 的特征值组成的对角阵。

什么样的矩阵 \(B\) 能够满足 \(\mathbf{b}_i\mathbf{x}_i = 1\) 且 \(\mathbf{b}_i\mathbf{x}_j = 0, \ i \neq j\) 呢？其实只要把所有 \(\lambda\) 都去了，就很容易发现，\(B\) 就是特征向量组成的矩阵的逆矩阵（ \(\begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 &...&\mathbf{x}_n\end{bmatrix}^{-1}\) ）。

这里还有一个观察：如果 \(\mathbf{x}_i, \ i=1,2,...,n\) 两两正交，单位长度，那么，矩阵 \(B = \begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n\end{bmatrix}^{-1} = \begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n\end{bmatrix}^T\) 。这时候的 \(B\) 就是一个正交矩阵。

---

现在有一个问题，矩阵 \(A\) 的特征向量组成的这个矩阵可逆吗（ \(\begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 &...&\mathbf{x}_n\end{bmatrix}^{-1}\) 存在吗）？

当矩阵 \(A\) 特征向量都线性无关的时候，显然矩阵可逆。

当矩阵 \(A\) 的每个特征值都不一样时，该矩阵也是可逆的。我们可以说明：此时，\(A\) 的特征向量都线性无关。

利用反证法。假设 \(\mathbf{x}_i = a\mathbf{x}_j + b\mathbf{x}_k\) ，然后等号左右两边同时左乘一个矩阵 \(A\) ，得到

\[\begin{aligned}A\mathbf{x}_i &= aA\mathbf{x}_j + bA\mathbf{x}_k\\ \lambda_i\mathbf{x}_i &= a\lambda_j\mathbf{x}_j + b\lambda_k\mathbf{x}_k\\ \mathbf{x}_i &= a\frac{\lambda_j}{\lambda_i}\mathbf{x}_j + b\frac{\lambda_k}{\lambda_i}\mathbf{x}_k\end{aligned}\]

从而，我们有

\[a(1-\frac{\lambda_j}{\lambda_i})\mathbf{x}_j = b(\frac{\lambda_k}{\lambda_i}-1)\mathbf{x}_k\]

因为 \(A\mathbf{x}_j = \lambda_j \mathbf{x}_j\) ，把 \(\mathbf{x}_j\) 用 \(\mathbf{x}_k\) 表示，就可以得到 \(A\mathbf{x}_k = \lambda_j \mathbf{x}_k\) . 但是 \(A\mathbf{x}_k = \lambda_k \mathbf{x}_k\) ，推导得到 \(\lambda_j = \lambda_k\) .

这与“每个特征值都不一样的条件”不符，说明我们假设错误，说明 \(A\) 的特征向量都线性无关。

所以特征向量组成的这个矩阵可逆（ \(\begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 &...&\mathbf{x}_n\end{bmatrix}^{-1}\) 存在）。

---

综上所述，当一个 \(n\) 维矩阵 \(A\) 的特征向量线性无关（所有特征值都不同）时，可以用它的特征值向量构成的矩阵来将其对角化：

\[\begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 &...&\mathbf{x}_n\end{bmatrix}^{-1}A\begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 &...&\mathbf{x}_n\end{bmatrix} = diag\begin{bmatrix}\lambda_1 & \lambda_2 &...&\lambda_n\end{bmatrix}\]

1.3 更进一步

我们 callback 一下上文的观察，当 \(n\) 维矩阵 \(A\) 的所有特征值都不一样时，\(A\) 的所有特征向量就是一组基，两两正交。但是，特征向量的长度是不确定的，不一定是 1 。这问题不大，我们将其长度归 1 化处理。

我们构造一个新的矩阵 \(W\) ：

\[W = \begin{bmatrix}\frac{\mathbf{x}_1}{\left\| \mathbf{x}_1 \right\|} & \frac{\mathbf{x}_2}{\left\| \mathbf{x}_2 \right\|} & \cdots & \frac{\mathbf{x}_n}{\left\| \mathbf{x}_n \right\|}\end{bmatrix}\]

首先，\(W\) 的每一列向量仍然是矩阵 \(A\) 的特征向量：

\[A \frac{\mathbf{x}_i}{\left\| \mathbf{x}_i \right\|} = \lambda_i \frac{\mathbf{x}_i}{\left\| \mathbf{x}_i \right\|}\]

其次，\(W\) 是一个正交矩阵：

\[W^TW = I\]

利用矩阵 \(W\)，我们可以做一个更加优美的矩阵对角化：

\[A = W\Sigma W^T\]

1.4 实对称矩阵相似对角化

并非所有矩阵都能进行相似对角化，但是所有的实对称矩阵都可以。

定理 1 实对称矩阵的特征向量必实。

考虑实对称矩阵 \(A\) 和它的一个特征值 \(\lambda\) 以及对应的特征向量 \(x\) 。用 \((\cdot)^*\) 表示共轭转置，矩阵 \(A\) 的共轭转置就是它本身；用 \(\bar{(\cdot)}\) 表示共轭，有

\[\begin{aligned} x^{*}Ax &= \lambda x^* x \\ &= (A^*x)^*x = (Ax)^*x = \bar{\lambda}x^*x \end{aligned}\]

因为特征向量非零，所以 \(x^*x \neq 0\) ，所以 \(\lambda = \bar{\lambda}\) ，特征向量是实数。

定理 2 实对称矩阵的属于不同特征值的特征向量必正交。

考虑 \(Ax_1 = \lambda_1x_1\) 和 \(Ax_2 = \lambda_2x_2\) ，且 \(\lambda_1 \neq \lambda_2\) ，有

\[\begin{aligned} \lambda_1(x_1\cdot x_2) &= (Ax_1) \cdot x_2 = (Ax_1)^\top x_2\\ &= x_1^\top A^\top x_2 = x_1^\top A x_2 = \lambda_2 x_1^\top x_2\\ &= \lambda_2 (x_1\cdot x_2) \end{aligned}\]

因为特征值不相等，所以只能是特征向量正交。

构造标准正交基

之所以要构造标准正交基，是因为标准正交基的排列就形成了相似对角化需要的可逆矩阵。

通过选取矩阵 \(A\) 的所有特征子空间的标准正交基，组合到一起，我们就得到了 \(\mathbb{R}^n\) 的一组正交基。

---

2 SVD（Singular Value Decomposition）奇异值分解

上文讲了一个方阵如何对角化，现在我们试着将结论推广到 \(m\times n\) 的矩阵上来。当然，此时“对角阵”不是严格意义上的对角阵。

2.1 结论

一个 \(m\times n\) 的矩阵 \(A\) 可以写成

\[A = U \Sigma V^* \tag{2-1}\]

的形式。其中 \(A \in \mathbb{R}^{m\times n}\) 或 \(A\in \mathbb{C}^{m\times n}\)。 \(U_{m\times m}\) 和 \(V_{n\times n}\) 都是酉矩阵。\(V^*\) 是 \(V\) 的共轭转置。

酉矩阵指满足矩阵的逆等于矩阵共轭转置的一类矩阵。正交矩阵是一类特殊的酉矩阵。

不妨令 \(m > n\) 。若 \(m < n\)，只需要先计算共轭转置的 SVD 分解，再将结果取共轭转置即可。

这里的 \(\Sigma\) 是一个“对角阵”，也就是说

\[\Sigma = \begin{bmatrix}\Sigma_1 \\ 0\end{bmatrix}\]

\[\Sigma_1 = \begin{bmatrix}\sigma_1\\ & \sigma_2\\ & & \cdots\\ & & & \sigma_n\end{bmatrix}\]

\(\sigma_i\) 称为奇异值，是 \(AA^*\) 或 \(A^*A\) 的非零特征值开根号的结果，\(U\) 是由 \(AA^*\) 的正交单位特征向量组成的矩阵，\(V\) 是由 \(A^*A\) 的正交单位特征向量组成的矩阵。

2.2 思考过程

我们假设结论成立，来试着反推一下 \(U\)，\(\Sigma\) 和 \(V\) 分别应当如何表示。

首先，我们有

\[A^* = V \Sigma^* U^*\]

则有

\[\begin{aligned} AA^* &= U\Sigma V^* V \Sigma^* U^*\\ &= U \Sigma\Sigma^* U^*\\ A^*A &= V\Sigma^* U^* U \Sigma V^*\\ &= V\Sigma^* \Sigma V^*\\ \end{aligned} \tag{2-2}\]

这里的 \(\Sigma\Sigma^*\) 和 \(\Sigma^*\Sigma\) 都是对角阵：

\[\begin{aligned} \begin{bmatrix}\Sigma_1 \\ 0\end{bmatrix}\begin{bmatrix}\Sigma_1^* & 0\end{bmatrix} &= \begin{bmatrix}\Sigma_1\Sigma_1^* & 0\\ 0 & 0\end{bmatrix}\\ \begin{bmatrix}\Sigma_1^* & 0\end{bmatrix}\begin{bmatrix}\Sigma_1 \\ 0\end{bmatrix} &= \begin{bmatrix} \Sigma_1^* \Sigma_1 \end{bmatrix}\\ \end{aligned}\]

我们观察一下 (2-2) 式，可以发现其形式酷似矩阵对角化。也就是说，\(\Sigma\Sigma^*\) 是一个由 \(AA^*\) 的特征值组成的对角阵，\(U\) 是一个由 \(AA^*\) 的正交单位特征向量组成的矩阵。\(\Sigma^*\Sigma\) 是一个由 \(A^*A\) 的特征值组成的对角阵，\(V\) 是一个由 \(A^*A\) 的正交单位特征向量组成的矩阵。

\[\begin{aligned} AA^*\mathbf{u}_i &= \sigma_i^2 \mathbf{u}_i\\ A^*A\mathbf{v}_i &= \sigma_i^2 \mathbf{v}_i \end{aligned} \tag{2-3}\]

---

首先，我们证明一下，\(AA^*\) 的特征值中，有 \(m-n\) 个 0.

特征值用 \(A\mathbf{v} = \lambda \mathbf{v}\) 定义。当特征值为 0 时，即代表有不为 \(\mathbf{0}\) 的向量 \(\mathbf{v}\)，使得 \(A\mathbf{v} = \mathbf{0}\)，也即 \(v_1\mathbf{a}_1 + v_2\mathbf{a}_2 + ... + v_n\mathbf{a}_n = \mathbf{0}\) ，即 \(A\) 的列向量中，至少有一个列向量与其它列向量线性相关。

所以我们需要证明，\(AA^*\) 的列向量中，至少有 \(m-n\) 个列向量与其它列向量线性相关。

设 \(A^* = \begin{bmatrix}\mathbf{a}_1 & \mathbf{a}_2 & \cdots & \mathbf{a}_m \end{bmatrix}\)，那么 \(AA^*\) 的列向量就是 \(A\mathbf{a}_1, A\mathbf{a}_2 , \cdots, A\mathbf{a}_m\)，那么 \(AA^*\) 的列向量维度小于等于 \(A^*\) 的列向量维度，而 \(A^*_{n\times m}\) 维度小于等于 \(n\) 。因此，\(AA^*\) 的列向量维度小于等于 \(n\)，也就是说至少有 \(m-n\) 个列向量与其它列向量线性相关。

接下来，我们证明 \(AA^*\) 的非零特征值和 \(A^*A\) 的非零特征值相同。

对于 \(AA^*\) 的非零特征值 \(\lambda\)，有 \(AA^* \mathbf{v} = \lambda \mathbf{v}\)，这里的 \(A^*\mathbf{v}\) 显然不可能为 0. 我们在该式等号左右两边都左乘一个 \(A^*\)，有 \((A^*A)(A^*\mathbf{v}) = \lambda (A^*\mathbf{v})\)，我们将 \(A^*\mathbf{v}\) 看成 \(A^*A\) 的特征向量，\(\lambda\) 也就是 \(A^*A\) 的特征值了。因此，我们就证明了 \(AA^*\) 的非零特征值和 \(A^*A\) 的非零特征值相同。

再者，我们证明 \(AA^*\) 和 \(A^*A\) 都是半正定的。

对于 \(AA^*\)，取其特征值有 \(AA^* \mathbf{v} = \lambda \mathbf{v}\)，左乘 \(\mathbf{v}^*\)，有 \(\mathbf{v}^*AA^* \mathbf{v} = (A^*\mathbf{v})^*(A^*\mathbf{v}) = \lambda \mathbf{v}^* \mathbf{v} \ge 0\) 。\(A^*A\) 同理。

综上，我们足以说明 (2-3) 式是成立的。我们称呼 (2-3) 式为特征值方程。

根据特征值方程，我们可以知道，\(\Sigma\) 是由 \(AA^*\) 的特征值开根号组成的“对角阵”，\(U\) 是由 \(AA^*\) 的正交单位特征向量组成的矩阵，\(V\) 是由 \(A^*A\) 的正交单位特征向量组成的矩阵。

此外，还有奇异值方程

\[A\mathbf{v}_i = \sigma_i \mathbf{u}_i \ \ \ A^*\mathbf{u}_i = \bar{\sigma}_i \mathbf{u}_i\]

2.3 SVD 的用处

2.3.1 求伪逆

SVD 奇异值分解经常用来求伪逆。

\[A_{m\times n} = U\Sigma V^*\]

那么矩阵 \(A\) 的伪逆 \(A^{+}\) 是

\[A^{+}_{n\times m} = V\Sigma^{+}U^{*}\]

其中 \(\Sigma^{+}\) 是由 \(\Sigma\) 的倒数组成的对角阵，即

\[\begin{aligned} &\Sigma = \begin{bmatrix}\sigma_1 \\ & \sigma_2\\ & & \cdots\\ & & & \sigma_m & 0 & \cdots & 0 \end{bmatrix} \ \ \Sigma^{+} = \begin{bmatrix}\frac{1}{\sigma_1}\\ & \frac{1}{\sigma_2}\\ & & \cdots\\ & & & \frac{1}{\sigma_m}\\ & & & 0\\ & & & \vdots\\ & & & 0\end{bmatrix}\\ & \Sigma = \begin{bmatrix}\sigma_1 \\ & \sigma_2\\ & & \cdots\\ & & & \sigma_n \\ & & & 0 \\ & & &\vdots \\ & & &0 \end{bmatrix} \ \ \Sigma^{+} = \begin{bmatrix}\frac{1}{\sigma_1}\\ & \frac{1}{\sigma_2}\\ & & \cdots\\ & & & \frac{1}{\sigma_n} & 0 & \cdots & 0\end{bmatrix} \end{aligned}\]