4.4 正定矩阵及矩阵的奇异值分解

在前一节的学习中, 我们知道对称矩阵为自伴矩阵的一种, 因此对称矩阵的所有特征值均为实数. 我们本节打算对这一性质进行深入研究: 即我们将研究当对称矩阵的所有特征值均为正数时, 矩阵有什么性质呢? 我们将这类矩阵称作正定矩阵 (Positive Definite Matrix). 在本节中, 我们只考虑实数矩阵.

定义 4.11

若 $\vec A \in M_{n}(\mathbb{R})$ 为对称矩阵且所有的特征值均为正数, 那么我们称 $\vec A$ 为正定矩阵.

正定矩阵有着非常多的性质:

定理 4.16

若 $\vec A$ 为正定矩阵, 那么 $\vec A$ 可逆且 $\det(\vec A)>0$ .

证明

设 $\vec A$ 的特征值为 $\lambda_1\cdots,\lambda_n>0$ (可能存在重复), 由于 $\vec A$ 可对角化, 因此存在对角矩阵 $\vec P = \diag\begin{pmatrix} \lambda_1,\cdots,\lambda_n \end{pmatrix}$ , 使得 $\vec A$ 相似于 $\vec P$ . 由于相似矩阵的行列式相同, 那么 $\det(\vec A)=\det(\vec P) = \lambda_1\cdots\lambda_n >0$ , 因此 $\vec A$ 也可逆.

∎

定理 4.17

$\vec A \in M_n(\mathbb{R})$ 为正定矩阵的充要条件是对任意的非零 $\vec x \in \mathbb{R}^n$ , $\vec x^\top \vec A \vec x >0$ .

证明

$(\Longrightarrow):$ 设 $\vec A\in M_n(\mathbb{R})$ 为正定矩阵, $\lambda_1,\cdots,\lambda_n$ 为 $\vec A$ 的特征值(可能存在重复), 则 $\lambda_i>0$ . 设 $\vec u_i$ 为 $\lambda_i$ 对应的特征向量, 那么记 $\vec Q=\begin{pmatrix} \vec u_1 & \cdots & \vec u_n \end{pmatrix}$ , $\vec P = \diag\begin{pmatrix} \lambda_1 & \cdots & \lambda_n \end{pmatrix}$ , 那么我们知道 $\vec A=\vec Q\vec P\vec Q^{\top}$ . 则对任意的非零 $\vec x=\begin{pmatrix} x_1 & \cdots & x_n \end{pmatrix}^\top$ , $\vec x^\top\vec A\vec x=\vec x^\top(\vec Q\vec P\vec Q^{\top})\vec x.$ 令 $\vec Q^\top\vec x = \vec y = \begin{pmatrix} y_1 & \cdots & y_n \end{pmatrix}^\top$ , 则

(\vec x^\top\vec Q)\vec P(\vec Q^\top\vec x) = \lambda_1y_1^2+\cdots+\lambda_ny_n^2 >0.

$(\Longleftarrow)$ . 设 $\lambda$ 为 $\vec A$ 的特征值, $\vec u$ 为与其对应的非零特征向量, 则

\vec u^\top \vec A \vec u = \vec u^\top\lambda\vec u = \lambda||\vec u||^2>0,

则 $\lambda>0$ .

∎

推论 4.4

设 $\vec A\in M_n(\mathbb{R})$ 可逆, 则 $\vec A^\top\vec A$ 为正定矩阵.

证明

设 $\vec x\in\mathbb{R}^n \neq \vec 0$ . 由于 $\vec A$ 可逆, 则 $\vec A\vec x \neq \vec 0$ , 那么

\vec x^\top(\vec A^\top\vec A)\vec x=(\vec A\vec x)^\top\vec A\vec x = ||\vec A\vec x||^2>0.

∎

我们现在假设 $\vec A \in M_n(\mathbb{R})$ 为正定矩阵，随后我们尝试将 $\vec A$ 写成分块矩阵的形式:

\vec A=\begin{pmatrix} {}^{(r)}\vec A & \vec P \\ \vec Q & \vec R\end{pmatrix},

其中 ${}^{(r)}\vec A \in M_r(\mathbb{R})$ 被称作 $\vec A$ 的主子矩阵 (Principal Submatrix), 即为取 $\vec A$ 中前 $r$ 行与前 $r$ 列所构成的新矩阵. 那么我们设 $\vec x \in\mathbb{R}^r \neq \vec 0$ , $\vec y = \begin{pmatrix} \vec x^\top & \vec 0^\top \end{pmatrix}^\top \in \mathbb{R}^n$ , 那么根据正定矩阵的性质, 我们有

\begin{pmatrix} \vec x^\top & \vec 0^\top \end{pmatrix} \begin{pmatrix} {}^{(r)}\vec A & \vec P \\ \vec Q & \vec R \end{pmatrix} \begin{pmatrix} \vec x \\ \vec 0 \end{pmatrix}=\begin{pmatrix} \vec x^\top & \vec 0^\top\end{pmatrix}\begin{pmatrix} {}^{(r)}\vec A\vec x \\ \vec Q\vec x\end{pmatrix} = \begin{pmatrix} \vec x^\top {}^{(r)}\vec A\vec x \end{pmatrix}>0,

因此我们便得知 ${}^{(r)}\vec A$ 也为正定矩阵.

定理 4.18

$\vec A\in M_n(\mathbb{R})$ 为正定矩阵的充要条件为其所有的主子矩阵 ${}^{(r)}\vec A$ 均为正定矩阵.

根据我们对正定矩阵的定义, 如果 $\vec X$ 为正定矩阵, 那么我们能否将 $\vec X$ 分解为 $\vec X = \vec A^\top\vec A$ 的形式呢? 首先我们知道 $\vec A$ 为正定矩阵便代表了 $\vec A$ 可以正交对角化, 那么此时存在对角矩阵 $\vec P$ 与对称矩阵 $\vec Q$ , 使得 $\vec X = \vec Q\vec P\vec Q^\top$ . 我们知道 $\vec P$ 主对角线上的元素即为 $\vec X$ 的正数特征值. 因此我们令 $\vec R := \vec P^{1/2} := \diag\begin{pmatrix} \sqrt{\lambda_1} & \cdots & \sqrt{\lambda_n} \end{pmatrix}$ , 那么

\vec X = \vec Q\vec P\vec Q^\top = \vec Q\vec R\vec R\vec Q^\top = (\vec R\vec Q)^\top(\vec R\vec Q):=\vec A^\top\vec A.

此时我们该如何去求解 $\vec A$ 呢? 我们回顾矩阵的LU分解, 我们知道 $\vec A \in M_n(\mathbb{R})$ 可以写成下三角矩阵与上三角矩阵的乘积, 那么我们此时可以类比LU分解, 假设 $\vec A^\top\vec A$ 便是下三角矩阵和上三角矩阵的乘积. 如果我们用数学归纳法去证明这一猜想的话, 我们便可以设 $\vec A \in M_n(\mathbb{R})$ , 然后其主子矩阵 ${}^{(n-1)}\vec A := \vec U^\top\vec U$ 可以分解成下三角矩阵 $\vec U^\top$ 与上三角矩阵 $\vec U$ 的乘积, 即

\vec A = \begin{pmatrix} \vec U^\top\vec U & \vec v \\ \vec v^\top & s \end{pmatrix},

其中 $s \in \mathbb{R}, \vec v \in \mathbb{R}^{n-1}$ . 此时我们令 $\vec x =( \vec U^\top)^{-1} \vec v, t = s - \vec x^\top\vec x$ , 那么

\begin{pmatrix} \vec U^\top & \vec 0 \\ \vec x^\top & \sqrt{t} \end{pmatrix} \begin{pmatrix} \vec U & \vec x \\ \vec 0^\top & \sqrt{t} \end{pmatrix} = \begin{pmatrix} \vec U^\top\vec U & \vec v \\ \vec v^\top & s \end{pmatrix}.\tag{4.1}

形如上式的分解被我们称作是Cholesky分解 (Cholesky Decomposition).

定理 4.19

任何正定矩阵 $\vec A$ 均存在分解 $\vec A = \vec U^\top\vec U$ , 使得 $\vec U$ 为主对角线上元素为正数的上三角矩阵. 对正定矩阵 $\vec A$ 进行不换行、不缩放主元行的高斯消元, 得到上三角矩阵 $\vec U_1$ . 设其主元为 $d_1,d_2,\cdots,d_n >0$ . 若将 $\vec U_1$ 的的第 $i$ 行除以 $\sqrt{d_i}$ , 我们便得到 Cholesky分解中的上三角矩阵 $\vec U$ . 由此一来 $\vec A= \vec U^\top\vec U$ .

这里的消元不是为了保持方程组解集, 而是为了构造分解. 因此我们不能随意使用所有初等行变换, 而应采用固定的消元规则: 即只用主元行消去其下方元素,并记录每一步产生的主元. 这样得到的主元和上三角矩阵才可用于构造 Cholesky 分解.

例题 4.7

求出 $\vec A=\begin{pmatrix} 10 & 5 & 2 \\ 5 & 3 & 2 \\ 2 & 2 & 3 \end{pmatrix}$ 的Cholesky分解.

解答 4.7

对 $\vec A$ 进行高斯消元, 不难得到如下的上三角矩阵 $\vec U_1$ :

\vec U_1 = \begin{pmatrix} 10 & 5 & 2 \\ 0 & \frac{1}{2} & 1 \\ 0 & 0 & \frac{3}{5}\end{pmatrix},

因此我们有

\vec U = \begin{pmatrix} \sqrt{10} & \frac{5}{\sqrt{10}} & \frac{2}{\sqrt{10}} \\ 0 & \frac{1}{\sqrt{2}} & \sqrt{2} \\ 0 & 0 & \frac{\sqrt{3}}{\sqrt{5}} \end{pmatrix}, \quad \vec A=\vec U^\top\vec U.

除了正定矩阵之外, 还有一类特征值为非负数的矩阵. 我们将这类矩阵称作半正定矩阵 (Positive Semi-definite Matrix)

定义 4.12

若 $\vec A \in M_{n}(\mathbb{R})$ 为对称矩阵且所有的特征值均为非负数, 那么我们称 $\vec A$ 为半正定矩阵.

半正定矩阵和正定矩阵在性质上非常相似, 唯一的不同便是半正定矩阵中可能出现 $0$ 作为特征值. 因此对定理 $4.17$ 稍作修改, 我们也可以得到半正定矩阵的相应性质:

推论 4.5

$\vec A \in M_n(\mathbb{R})$ 为半正定矩阵的充要条件是对任意的非零 $\vec x \in \mathbb{R}^n$ , $\vec x^\top \vec A \vec x \geq0$ .

证明

证明略.

∎

对于任意的 $\vec A \in M_{mn}(\mathbb{R})$ , 不难发现 $\vec A^\top\vec A$ 为对称矩阵. 设 $\lambda$ 为 $\vec A$ 的特征值, $\vec u$ 为与之对应的特征向量, 那么

\vec u^\top\vec A^\top\vec A\vec u = \vec u^\top\lambda^2\vec u \geq 0,

则 $\vec A^\top\vec A$ 均为半正定矩阵. 由于半正定矩阵的特征值为非负数, 我们可以由此给出任意矩阵 $\vec A$ 的奇异值 (Singular Value)的定义:

定义 4.13

设 $\vec A \in M_{mn}(\mathbb{R})$ 为任意矩阵, 记 $\lambda_i$ 为 $\vec A^\top\vec A$ 的特征值, 我们定义 $\vec A$ 的奇异值为 $\sigma_i = \sqrt{\lambda_i}$ .

我们前面讲到的LU分解, 对角化, Cholesky分解等都用于 $n\times n$ 矩阵. 像是一般的矩阵 $\vec A \in M_{mn}(\mathbb{R})$ , 我们能否也将其分解成类似的形式呢? 在本节的后半部分我将着重讲解这一独特的分解: 矩阵的奇异值分解 (Singular Value Decomposition). 对于 $\vec A \in M_{m\times n}(\mathbb{R}),$ 而言, 我们的目标是找出 $m\times m$ 的正交矩阵 $\vec U$ , $n\times n$ 的正交矩阵 $\vec V$ , 以及 $m\times n$ 的“对角矩阵” $\vec S$ , 使得

\vec A = \vec U\vec S\vec V^\top, \quad \vec S = \begin{pmatrix} \sigma_1 & 0 & \cdots & 0 \\ 0 & \sigma_2 & \ddots & 0 \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & \sigma_n \\ 0 & \cdots & \cdots & 0 \\ \vdots & & &\vdots \\ 0 & \cdots & \cdots & 0 \end{pmatrix}\text{或}\begin{pmatrix} \sigma_1 & 0 & \cdots & 0 & \cdots & 0 \\ 0 & \sigma_2 & \cdots & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & & \vdots \\ 0 & 0 & \cdots & \sigma_n & \cdots & 0 \end{pmatrix},\quad \sigma_1\geq\sigma_2\geq\cdots\geq\sigma_n\geq 0.

其中位于 $\vec S$ 的“对角线”上的元素即为矩阵 $\vec A^\top\vec A$ 的奇异值, 且按照从大到小依次排列. 我们知道, 此时 $\vec A^\top\vec A$ 为 $n\times n$ 对称矩阵, 因此可以正交对角化. 由此存在由 $\mathbb{R}^n$ 的一组单位正交基 $\{ \vec v_1,\cdots,\vec v_n\}$ 为列向量的矩阵 $\vec V$ 以及以 $\vec A^\top\vec A$ 的特征值为对角线元素的对角矩阵 $\vec D$ , 使得

\vec A^\top\vec A = \vec V\vec D\vec V^\top.

推论 4.6

设 $\sigma_i\vec u_i= \vec A\vec v_i$ , $\sigma_1\geq\cdots\geq\sigma_k\geq\sigma_{k+1}=\cdots=\sigma_n=0$ 则 $\vec u_1,\cdots,\vec u_k \in\mathbb{R}^m$ 正交且为单位向量.

证明

根据定义, $\forall i,j \leq k$ ,

\vec u_i^\top\vec u_j = \left(\frac{1}{\sigma_i}\vec A\vec v_i\right)^\top\cdot\frac{1}{\sigma_j}\vec A\vec v_j = \frac{1}{\sigma_i\sigma_j}\vec v_i^\top\vec A^\top\vec A\vec v_j=\frac{1}{\sigma_i\sigma_j}\vec v_i^\top (\vec V\vec D\vec V^\top )\vec v_j=\frac{1}{\sigma_i\sigma_j}\vec v_i^\top\lambda_j\vec v_j.

结合 $\lambda_j = \sigma_j^2$ , 我们有

\vec u_i^\top\vec u_j = \frac{\sigma_j}{\sigma_i}\vec v_i^\top\vec v_j = \begin{cases} 1 & i = j \\ 0 & i \neq j\end{cases}.

∎

此时, 我们便有有了一组单位正交向量. 但值得注意的是此时 $k \leq m$ , 所以当 $k<m$ 的时候我们需要使用Gram-Schmidt算法将 $\vec u_1,\cdots,\vec u_k$ 补全为一组 $\mathbb{R}^m$ 的单位正交基: $\{ \vec u_1,\cdots,\vec u_k,\vec u_{k+1},\cdots,\vec u_m\}$ . 随后记矩阵 $\vec U$ 的列向量为 $\vec u_1,\cdots,\vec u_m$ , 我们便得到了三个矩阵: $\vec U,\vec S,\vec V$ . 此时我们想知道的便是 $\vec A = \vec U\vec S\vec V^\top$ 是否成立. 我们首先注意到 $\vec V^\top=\vec V^{-1}$ , 因此我们只需要验证 $\vec A\vec V=\vec U\vec S$ . 而注意到

\vec A\vec V = \begin{pmatrix} \vec A\vec v_1 & \cdots & \vec A\vec v_n \end{pmatrix}=\begin{pmatrix} \sigma_1\vec u_1 & \cdots & \sigma_k\vec u_k & \vec 0 & \cdots & \vec 0 \end{pmatrix}=\vec U\vec S,

因此矩阵 $\vec A$ 的奇异值分解即为

\vec A = \vec U\vec S\vec V^\top.