Positive Definite Matrices - 正定矩阵

已完成 · 笔记范围：全

二次型

$f(x,y)=ax^{2}+2bxy+cy^{2}$
这样的（二元）二次型在原点处都是驻点：\frac{ \partial f }{ \partial x }=\frac{ \partial f }{ \partial y }=0。
若 f(x,y) 在原点之外是严格大于零的，称它为正定的（Positive Definite）。
配方之后可以知道，这个二次型正定当且仅当： $a>0,\quad ac>b^{2}$
类似的，也有负定（Negative Definite）的情况：
$a<0\,,\,ac>b^{2}$
正定负定的图形是碗形。
半正定（Positive Semidefinite）当且仅当 a\geq0,c\geq0,ac\geq b^2；半负定（Negative Semidefinite）当且仅当 a\leq0,c\leq0,ac\geq b^2。正定、负定分别也是半正定、半负定的情形。
当 ac=b^2 且二次型不恒为零时，图形为山谷或倒山谷，有一条直线上的函数值为 0；若 a=b=c=0，则处处为 0。
若 ac<b^{2} ，图形会变成马鞍面（Saddle），此时原点叫做鞍点（Saddle Point）。

矩阵表示：
$f(x,y)=\begin{bmatrix} x & y \end{bmatrix} \begin{bmatrix} a & b \\ b & c \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix}=\boldsymbol{x}^{\top}A\boldsymbol{x}$
对于 n 元的二次型：
$f(x_{1},x_{2},\dots,x_{n})=\boldsymbol{x}^{\top}A\boldsymbol{x}=\sum \sum a_{ij}x_{i}x_{j}$
其中 A 是一个实对称矩阵，把它叫作一个二次型矩阵。
这里 f 中，若 i\neq j，则 x_{i}x_{j} 的系数除以二才得到 a_{ij}=a_{ji}。而矩阵的对角元就是平方项的系数。

正定矩阵

若 f=\boldsymbol{x}^{\top}A\boldsymbol{x} 是一个正定二次型，则把对称矩阵 A 叫做正定矩阵。有时记作 A>0。
对对称矩阵 A，TFAE：

\boldsymbol{x}^{\top}A\boldsymbol{x}>0\forall \boldsymbol{x}\neq 0
所有特征值 \lambda_{1},\dots,\lambda_{n}>0
左上角 k\times k 的行列式 \det(A_{k})>0 \forall k
主元 d_{k}>0\,\forall k
存在一个可逆矩阵 R，使得 A=R^{\top}R

TFAE : The following are equivalent.

证明：

【 1\implies 2 】若 \boldsymbol{x}^{\top}A\boldsymbol{x}>0，假设 \lambda _i 是一个特征值，对应特征向量 \boldsymbol{x}_{i}\neq 0，则 \boldsymbol{x}_{i}^{\top}A\boldsymbol{x}_{i}>0。又因为 A\boldsymbol{x}_{i}=\lambda \boldsymbol{x}_{i}，有 \lambda_{i}\boldsymbol{x}_{i}^{\top}\boldsymbol{x}_{i}=\lambda_{i}\lVert \boldsymbol{x}_{i} \rVert^{2}>0，故而 \lambda_{i}>0。
【 2\implies 1 】若 \lambda_{i}>0，由谱定理，因为 A 是一个对称矩阵，它可以被一个正交矩阵对角化，也就是说存在一组规范正交的特征向量 \boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n} 使得 A\boldsymbol{x}_{i}=\lambda_{i}\boldsymbol{x}_{i}。任意向量可以写成这组特征向量的线性组合： \boldsymbol{x}=\sum c_{i}\boldsymbol{x}_{i}。那么 \boldsymbol{x}^{\top}A\boldsymbol{x}=\left( \sum c_{i}\boldsymbol{x}_{i}^{\top} \right)A\left( \sum c_{i}\boldsymbol{x}_{i} \right)=\left( \sum c_{i}\boldsymbol{x}_{i}^{\top} \right)\left( \sum c_{i}\lambda_{i}\boldsymbol{x}_{i} \right)=\sum c_{i}^{2}\lambda_{i}（因为交叉项都为 0）。故而 \boldsymbol{x}^{\top}A\boldsymbol{x}>0。
【 2\implies 3 】 \det(A_{n})=\prod\lambda_{i}>0。设原来的二次型为

$g(x_{1}\dots x_{n})=\begin{bmatrix}x_{1}\dots x_{n}\end{bmatrix}A\begin{bmatrix}x_{1} \\ \vdots\\x_{n}\end{bmatrix}$

，它是正定的。那么考察

$f(x_{1}\dots x_{k})=\begin{bmatrix}x_{1}\dots x_{k}\end{bmatrix}A_k\begin{bmatrix}x_{1} \\ \vdots\\x_{k}\end{bmatrix}$

，它满足 f=g(x_{1}\dots x_{k},0\dots 0)，那么 f 也是正定的。于是 \det(A_{k})>0。
【 3\implies 4 】 d_{k}= \frac{\det(A_{k})}{\det(A_{k-1})}>0。
【 4\implies 1 】假设 A=LDU，由于 A^{\top}=U^{\top}DL^{\top}=A=LDU，有 U=L^{\top}。那么 \forall \boldsymbol{x}\neq 0,\boldsymbol{x}^{\top}A\boldsymbol{x}=\boldsymbol{x}^{\top}(LDU)\boldsymbol{x}=\boldsymbol{x}^{\top}LDL^{\top}\boldsymbol{x}。令 L^{\top}\boldsymbol{x}=\boldsymbol{y}\neq 0，则 \boldsymbol{x}^{\top}A\boldsymbol{x}=\boldsymbol{y}^{\top}D\boldsymbol{y}=\sum d_{i}y_{i}^{2}>0。
【 5\implies 1 】 \forall \boldsymbol{x}\neq 0, \boldsymbol{x}^{\top}A\boldsymbol{x}=\boldsymbol{x}^{\top}R^{\top}R\boldsymbol{x}=\lVert R\boldsymbol{x} \rVert^{2}，这里由于 R 可逆，R\boldsymbol{x} 就不为 0，因此 \boldsymbol{x}^{\top}A\boldsymbol{x}>0。
【 A>0\implies 5 】
- 法一（Cholesky Decomposition ）：A=LDU=LDL^{\top}=(L\sqrt{ D })(\sqrt{ D }L^{\top})，设 R=\sqrt{ D }L^{\top}，则 A=R^{\top}R，这里 R 显然可逆。
- 法二： A=Q\Lambda Q^{\top}=Q\sqrt{ \Lambda }\sqrt{ \Lambda }Q^{\top} ，设 R=\sqrt{ \Lambda }Q^{\top}，则 A=R^{\top}R，这里 R 显然可逆。
- 法三：A=Q\Lambda Q^{\top}=(Q\sqrt{ \Lambda }Q^{\top})(Q\sqrt{ \Lambda }Q^{\top})，设 R=Q\sqrt{ \Lambda }Q^{\top}，则 R 是一个对称的正定矩阵，且 A=R^{\top}R=R^{2}。（这里这种分解方式最好的保留了 A 的对称和正交的性质，所以可以定义 R=\sqrt{ A }>0）
- 这里有无穷多种分解，因为若 A=R^{\top}R，则对任意 R'=QR 其中 Q 是任意正交矩阵，则 A=R'^{\top}R'。

当然，根据定义，也可以去直接把二次多项式给 Complete the square 来判断。
这里你会发现，若 A=LDU，则 \boldsymbol{x}^{\top}A\boldsymbol{x}=\sum d_{i}y_{i}^{2}，这里 \boldsymbol{y}=L^{\top}\boldsymbol{x}，y_i 为 \boldsymbol{y} 的第 i 个分量，且 d_{i} 为第 i 个主元。这就是配方之后的结果！所以配方和高斯消元的过程其实是对应的。

将一个对称矩阵称为半正定的（Semipositive Definite），若
$\boldsymbol{x}^{\top}A\boldsymbol{x}\geq 0\forall \boldsymbol{x}$
记作 A\geq 0。
半负定： \boldsymbol{x}^{\top}A\boldsymbol{x}\leq 0 \forall \boldsymbol{x}。记作 A\leq 0。

TFAE:

A\geq 0
特征值 \lambda_{i} \geq 0
没有主子矩阵（Principal Submatrices）有负的特征值。
- 主矩阵：指标集（Index Set） I\subseteq \{ 1,2,\dots,n \} 对应的主矩阵 A_{I} ，定义为 A 的一个子矩阵，它来自于选取 A 中的所有满足 i,j\in I 的 a_{ij}。
所有主子式 \det(A_I)\geq 0（包括非顺序主子式）
存在矩阵 R 使得 A=R^{\top}R。

要证明这些事情，可以用这个事实：
$A\geq 0 \iff A+\varepsilon I>0 \, \, \forall\text{sufficient small }\varepsilon>0$
这个事实的证明：

左推右： \forall \boldsymbol{x}\neq 0, \boldsymbol{x}^{\top}(A+\varepsilon I)\boldsymbol{x}=\boldsymbol{x}^{\top}A\boldsymbol{x}+\varepsilon \boldsymbol{x}^{\top}\boldsymbol{x}>0。
右推左：\boldsymbol{x}^{\top}A\boldsymbol{x}=\lim_{ \varepsilon \to 0 } \boldsymbol{x}^{\top}(A+\varepsilon I)\boldsymbol{x}\geq 0。
例如要证明 A\geq 0\implies\lambda_{i}\geq 0 ：A\geq 0 \implies A+\varepsilon I > 0 \implies \lambda_{i}+\varepsilon > 0 \implies\lambda_{i}\geq 0。

合同矩阵

对于二次型 f=\boldsymbol{x}^{\top}A\boldsymbol{x}，它可以做换元 \boldsymbol{x}=C\boldsymbol{y} 来研究，且
$\boldsymbol{x}^{\top}A\boldsymbol{x}=\boldsymbol{y}^{\top}(C^{\top}AC)\boldsymbol{y}$
其中 C 是一个可逆的矩阵。

这里定义 A,B 为合同的（Congruent），若存在可逆矩阵 C 使得
$B=C^{\top}AC$
合同关系（Congruence）有如下性质：

对称矩阵的合同矩阵也是对称矩阵。
单位矩阵 A=I 的合同矩阵形如 B=C^{\top}C。也就是说，它是正定的！那么 B 的特征值都是正的。

塞维斯特惯性定律（Sylvester’s Law of Inertia）：

A 的合同矩阵 C^{\top}AC 和 A 有相同数量的正特征值，相同数量的负特征值和相同数量的零特征值。
把正特征值的数量称为正惯性指数（Positive index of inertia），记作 p。
把负特征值的数量称为负惯性指数（Negative index of inertia），记作 q。
这里 p+q=\operatorname{rank}(A)。p-q 称为符号差（Signature）。
该定律也可以表述成：
设 f(x_{1}\dots x_{n})=\boldsymbol{x}^{\top}A\boldsymbol{x} 为秩为 r 的 n 元二次型。存在一个线性变量替换 \boldsymbol{x}=C\boldsymbol{y} 使得 f 变为
$g(y_{1}\dots y_{n})=y_{1}^{2}+y_{2}^{2}+\dots+y_{p}^{2}-y_{{p+1}}^{2}-\dots-y_{r}^{2}$
上述二次型被称为 f 的规范型，其由 f 唯一决定。

应用

二次超曲面（Geometry of Quadratic Hypersurface）可以写成
$\boldsymbol{x}^{\top}A\boldsymbol{x}=1$
要看出它是一种怎样的矩阵，可以做坐标变换 \boldsymbol{x}=Q\boldsymbol{y}，其中 Q 是一个正交矩阵。谱定理指出，由于 A 是对称矩阵，存在这样的正交矩阵 Q，使得 Q^{\top}AQ=\Lambda。
那么原来的曲面等价于
$\boldsymbol{x}^{\top}A\boldsymbol{x}=(Q\boldsymbol{y})^{\top}A(Q\boldsymbol{y})=\boldsymbol{y}^{\top}(Q^{\top}AQ)\boldsymbol{y}=\boldsymbol{y}^{\top}\Lambda \boldsymbol{y}=\sum\lambda_{i}y_{i}^{2}=1$
那么只需要去看 \lambda_{i} 的正负，很容易就可看出来这个曲面是什么形状的。
对于 n=3 的情况，这就可以用来判定三维空间中的二次曲面了：
$\boldsymbol{x}^{\top}A\boldsymbol{x}=\lambda_{1}y_{1}^{2}+\lambda_{2}y_{2}^{2}+\lambda_{3}y_{3}^{2}=1$

若特征值全为正，如 \lambda_{1},\lambda_{2},\lambda_{3}>0，则为椭球面（Ellipsoid）。
$x^{2}+y^{2}+z^{2}=1$
若特征值两正一负，如 \lambda_{1},\lambda_{2}>0,\lambda_{3}<0，则为单叶双曲面（Hyperboloid of One Sheet）。
$x^{2}+y^{2}-z^{2}= 1$
若特征值一正两负，如 \lambda_{1}>0,\lambda_{2},\lambda_{3}<0，则为双叶双曲面（Hyperboloid of Two Sheet）。
$x^{2}-y^{2}-z^{2}=1$
若特征值全为负，如 \lambda_{1},\lambda_{2},\lambda_{3}<0，则为空集。
退化状态：
若特征值两正一零，如 \lambda_{1},\lambda_{2}>0, \lambda_{3}=0，则为椭圆柱面（Elliptic Cylinder）。
$x^{2}+y^{2}=1$
若特征值一正一负一零，如 \lambda_{1}>0,\lambda_{2}<0,\lambda_{3}=0，则为双曲柱面（Hyperbolic Cylinder）。
$x^{2}-y^{2}=1$
若特征值两负一零，如 \lambda_{1},\lambda_{2}<0,\lambda_{3}=0，则为空集。
若特征值一正两零，如 \lambda_{1}>0,\lambda_{2},\lambda_{3}=0，则为两个平行平面（Two Parallel Planes）。
$x^{2}=1$
若特征值一负两零，如 \lambda_{1}<0,\lambda_{2},\lambda_{3}=0，则为空集。
若特征值全为零，\lambda_{1},\lambda_{2},\lambda_{3}=0，则为空集。

要求这个正负惯性指数，就可以利用塞维斯特惯性定律，转换为规范型就直接看出来了。

直接解特征方程。
利用韦达定理判断 \lambda 的正负。
换元，配方转换为规范型。
拉格朗日配方法：若至少一个平方项，那就直接对该平方项进行配方，迭代即可。若没有平方项，则挑一个交叉项 x_{1}x_{2}，令 x_{1}=y_{1}+y_{2},x_{2}=y_{1}-y_{2}，这就用平方差公式创造出了平方项。

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

任何 m\times n 的矩阵 A 可以被分解为
$A=U\Sigma V^{\top}$
其中：

U 是 m\times m 的一个正交矩阵。它是 AA^{\top} 的特征向量构成的。
V 是 n\times n 的一个正交矩阵。它是 A^{\top}A 的特征向量构成的。
\Sigma 是一个 m\times n 的对角矩阵，它可以写成分块矩阵
$\begin{bmatrix} \Sigma_{1} & 0 \\ 0 &0 \end{bmatrix}$
其中
$\Sigma_{1}= \begin{bmatrix} \sigma_{1} \\ & \ddots \\ & & \sigma_{r} \end{bmatrix}$
其中 r 为 A 的秩，这里 \sigma_{i} 称为奇异值（Singular Value）。
定义： A 的奇异值 \sigma_{i}=\sqrt{ \lambda_{i} }=\sqrt{ \mu_{i} } ，其中 \lambda_{i},\mu_{i} 是 AA^{\top} 和 A^{\top}A 的非零特征值（i=1,2,\dots,\operatorname{rank}(A)）。

（可以这么定义是因为，AA^{\top} 和 A^{\top}A 都是半正定矩阵，特征值都大于等于零，而且它们的秩都和 A 相同，且它们的非零特征值也相等。验证一下：这里
$\begin{aligned} A^{\top}A&=(U\Sigma V^{\top})^{\top}U\Sigma V^{\top} \\&=V\Sigma^{\top}U^{\top}U\Sigma V^{\top} \\ &=V\Sigma^{\top}\Sigma V^{\top} \\ &=V\begin{bmatrix} \Sigma_{1}^{\top}\Sigma_{1} & 0 \\ 0 & 0 \end{bmatrix}V^{\top} \\ \end{aligned}$
其中
$\Sigma_{1}^{\top}\Sigma_{1}=\begin{bmatrix} \sigma_{1}^{2} \\ & \ddots \\ & & \sigma_{r}^{2} \end{bmatrix}$
这里就找到了 A^{\top}A 的一个谱分解。那么，\sigma_{i}^{2} 就是 A^{\top}A 的所有非零特征值！
类似的，由于 AB 和 BA 有相同的非零特征值，那么 \sigma_{i}^{2} 也是 AA^{\top} 的所有非零特征值。
有 AA^{\top}=U\Sigma \Sigma^{\top}U^{\top}。
）
这里会发现，由于 AV=U\Sigma，如果对 r进行分块：
$A\begin{bmatrix} V_{r} & V_{n-r} \end{bmatrix}=\begin{bmatrix} U_{r} & U_{m-r} \end{bmatrix}\begin{bmatrix} \Sigma_{r} & 0 \\ 0 & 0 \end{bmatrix}$
也就是 AV_{r}=U_{r}\Sigma_{r},AV_{n-r}=0。
那么 V 的前 r 列就对应 A 的行空间，后 n-r 列就对应 A 的零空间。
同理， U 的前 r 列对应 A 的列空间，后 m-r 列就对应 A 的左零空间。

要求一个矩阵的 SVD 分解，不能随便选取 U,V。
需要选取：
$A\boldsymbol{v}_{j}=\sigma_{j}\boldsymbol{u}_{j}, j=1,\dots,r$
这个从上面的分块矩阵可以看出来。（存在性证明：

若 \boldsymbol{v}_{j} 是 A^{\top}A 的一个单位特征向量，对应特征值 \sigma_{j}^{2}，则 A^{\top}A\boldsymbol{v}_{j}=\sigma_{j}^{2}\boldsymbol{v}_{j}，进而 AA^{\top}A\boldsymbol{v}_{j}=\sigma_{j}^{2}A\boldsymbol{v}_{j}，也就是 A\boldsymbol{v}_{j} 是 AA^{\top} 的一个特征向量，对应特征值 \sigma_{j}^{2}。而且
$\lVert A\boldsymbol{v}_{j} \rVert^{2}=\boldsymbol{v}_{j}^{\top}A^{\top}A\boldsymbol{v}_{j}=\boldsymbol{v}_{j}^{\top}\sigma_{j}^{2} \boldsymbol{v}_{j}=\sigma_{j}^{2}$
那么 A\boldsymbol{v}_{j} / \sigma_{j}=\boldsymbol{u}_{j} 就是 AA^{\top} 的一个单位特征向量，得证。）
那么就应该先求出 A^{\top}A 的 r 个非零特征值对应的向量和 n-r 个 A^{\top}A 的零空间的向量，来构造 V，再利用关系 \boldsymbol{u}_{j}= A\boldsymbol{v}_{j} / \sigma_{j} 来得到前 r 个构造 \boldsymbol{u}_{j}。剩下的 m-r 个 \boldsymbol{u}_{j} 需要去求 N(A^{\top}) 然后再做正交化得到。

定理： 任意可逆方阵 A 都可以写成
$A=Q_{1}SQ_{2}^{-1}$
其中 Q_{1},Q_{2} 为正交矩阵，S 是一个正定矩阵。
证明：
$\boldsymbol{x}^{\top}A^{\top}A\boldsymbol{x}=\lVert A\boldsymbol{x} \rVert^{2}>0 \forall \boldsymbol{x}\neq 0$
所以 A^{\top}A 是正定的实对称矩阵。那么存在谱分解：
$Q_{2}^{\top}A^{\top}AQ_{2}=\Lambda$
令 S=\sqrt{ \Lambda }，那么 S 是一个正定的对角的可逆矩阵。那么有：
$S^{-1}Q_{2}^{\top}A^{\top}AQ_{2}S^{-1}=I$
那么 AQ_{2}S^{-1} 就是一个正交矩阵，记为 Q_{1}。于是有
$A=Q_{1}SQ_{2}^{-1}$

SVD 的应用

极分解（Polar Decomposition）：任何实方阵 A 可以分解成 A=QS，其中 Q 是正交矩阵，S 是对称的半正定的矩阵。
（A=U\Sigma V^{\top}=(UV^{\top})(V\Sigma V^{\top})=QS）
类比 z=re^{i\theta}。这里 S 类似于 r，Q 类似与 e^{i\theta}。

有效秩（Effective Rank）：直接对 A 做 SVD，并按照相对于最大奇异值的容差判断数值秩。形成 A^{\top}A 会平方条件数，使较小奇异值更难准确分辨。

图片压缩（Image Compression）：一个 m\times n 的图像，可以进行 SVD 分解，只需要存储 r 个奇异值和奇异向量，共 r\times(m+n+1) 个值。图片压缩比：\frac{m\times n}{r\times(m+n+1)}。
图片降噪（Noise Reduction）：丢弃较小的奇异值及其对应的奇异向量项。

最小二乘（Least Square）的最优解：最小二乘的 Normal Equation A^{\top}A\boldsymbol{x}=A^{\top}\boldsymbol{b} ，如果 A^{\top}A 不可逆，也就是说，A 不是列满秩的，则可能有多个解 \hat{\boldsymbol{x}}。其中最优解为长度最小的解 \boldsymbol{x}^{+}。

记作 \boldsymbol{x}^{+}=A^+\boldsymbol{b} 中，A^+ 称为 A 的伪逆（Pseudoinverse）。
容易验证，\Sigma^{+} 将非零奇异值求倒数、零奇异值保持为零，并转置矩阵的形状。
一般情况下，由于 \hat{\boldsymbol{x}}=x_{r}+x_{n}，那么由于零空间和行空间正交，有 \lVert \hat{\boldsymbol{x}} \rVert^{2}=\lVert x_{r} \rVert^{2}+\lVert x_{n} \rVert ^{2}，取 x_{n}=0，则得到了最优解，所以最优解是行空间中的。 （可以解 Normal Equation 然后选行空间中的）
一般情况下，伪逆有公式
$A^{+}=V\Sigma^+ U^{\top}$
证明：\lVert A\boldsymbol{x}-\boldsymbol{b} \rVert=\lVert U\Sigma V^{\top}\boldsymbol{x}-\boldsymbol{b} \rVert=\lVert \Sigma V^{\top}\boldsymbol{x}-U^{\top}\boldsymbol{b} \rVert。
令 \boldsymbol{y}=V^{\top}\boldsymbol{x}=V^{-1}\boldsymbol{x}。只需最小化 \lVert \Sigma \boldsymbol{y}-U^{\top}\boldsymbol{b} \rVert。
\boldsymbol{y}^+=\Sigma^+U^{\top}\boldsymbol{b}，故而 \boldsymbol{x}^+=V\Sigma^+U^{\top}\boldsymbol{b}。