线性代数笔记11：正定矩阵理解及推导

title: 线性代数笔记11：正定矩阵理解及推导

tags:

linear algebra

categories:linear algebra

date: 2018-04-12 15:55:43

mathjax: true

正定矩阵及半正定矩阵在机器学习和深度学习中有很重要的应用。

引言

定义：特征值全是正实数的实对称矩阵为正定矩阵（positive definite matrix）。类似的，若实对称矩阵的特征值均非负，则为半正定矩阵（positive semidefinite matrix）。

可能用到的概念

主子式

定义：在nnn阶行列式中任选kkk行，再取相应的kkk列，将行列交汇处元素组成新的矩阵行列式，称为nnn阶行列式的一个kkk阶主子式。

顺序主子式（the k-th leading principal minor）

定义：在nnn阶行列式中由第1,...,k1,...,k1,...,k行和第1,...,k1,...,k1,...,k列所确定的主子式称为kkk阶顺序主子式。直观上看就是矩阵中左上方的子矩阵。

实对称矩阵AAA正定的充要条件

注意，这里的所有进行判别的矩阵都是实对称矩阵。

以下条件都是判别实对称矩阵是否正定的充要条件。

AAA的所有特征值λi\lambda_iλi​均为正。xTAx>0x^TAx > 0xTAx>0对所有非零向量xxx都成立。AAA的所有顺序主子式都是正的。AAA的所有主元（无行交换）都是正的。存在列满秩矩阵RRR，使得A=RTRA=R^TRA=RTR.AAA的所有主子式都是正的。

证明

(1) => (2)

对实对称矩阵AAA，存在正交阵QQQ，使得A=QΛQRA=Q\Lambda Q^RA=QΛQR。

因此，对任意非零向量xxx：

xTAx=xTQΛQTx=yTΛy=λ1y12+...+λnyn2>0x^TAx = x^TQ\Lambda Q^Tx = y^T\Lambda y=\lambda_1y_1^2 + ... + \lambda_ny_n^2 > 0xTAx=xTQΛQTx=yTΛy=λ1​y12​+...+λn​yn2​>0

其中y=QTx=(y1,...,yn)≠0y = Q^Tx = (y_1,...,y_n) \ne 0y=QTx=(y1​,...,yn​)̸​=0

(2) => (1)

因为AAA为实对称矩阵，因此一定可以对角化A=QλQTA = Q\lambda Q^TA=QλQT

∵xTAx>0∴xTQΛQTx>0\because x^TAx > 0 \quad \therefore x^TQ\Lambda Q^Tx > 0∵xTAx>0∴xTQΛQTx>0

令y=QTxy = Q^Txy=QTx，因此yΛyT>0⇒∑λiyi2=0y\Lambda y^T > 0\Rightarrow \sum \lambda_iy_i^2 = 0yΛyT>0⇒∑λi​yi2​=0

∵∀y≠0s.t∑λiyi2=0\because \forall y \ne 0 \quad s.t \quad \sum \lambda_iy_i^2 = 0∵∀y̸​=0s.t∑λi​yi2​=0

λi=0\lambda_i = 0λi​=0

(2) => (3)

由(2) => (1) => det(A)=λ1...λn>0det(A) = \lambda_1 ...\lambda_n > 0det(A)=λ1​...λn​>0

xTAx=(xkT0)(Ak∗∗∗)(xk0)=xkTAxk>0x^TAx = \begin{pmatrix}x_k^T & 0\end{pmatrix}\begin{pmatrix}A_k &* \\ * & *\end{pmatrix} \begin{pmatrix}x_k\\0 \end{pmatrix} = x^T_k A x_k > 0 xTAx=(xkT​​0​)(Ak​∗​∗∗​)(xk​0​)=xkT​Axk​>0

∴det(xkT)det(Ak)det(kk)=det(Ak)>0\therefore det (x_k^T)det(A_k)det(k_k) = det(A_k) > 0∴det(xkT​)det(Ak​)det(kk​)=det(Ak​)>0

(3) => (4)

顺序主子式与主元有直接关系，第kkk个主元：

dk=det(Ak)detAk(k−1)>0d_k = \frac{det(A_k)}{detA_k(k-1)} > 0dk​=detAk​(k−1)det(Ak​)​>0

其中AkA_kAk​是第kkk个顺序主子矩阵（the k-th leading principal submatrix)。

(4) => (2)

由对称矩阵的Gauss消元法得LDU分解：A=LDLTA = LDL^TA=LDLT，其中对角阵的对角元为AAA的主元：

D=diag(d1,...,dn)D = diag (d_1,...,d_n)D=diag(d1​,...,dn​)

则对任意非零向量：

xTAx=xTLDLTx=yTDy=d1y12+...+dnyn2>0x^TAx = x^TLDL^Tx = y^TDy = d_1y_1^2 + ...+ d_ny_n^2> 0xTAx=xTLDLTx=yTDy=d1​y12​+...+dn​yn2​>0

(2) => (5)

A=LDLT=LDDLT=(DLT)T(DLT)=RTRA = LDL^T = L\sqrt {D} \sqrt {D} L^T = ( \sqrt {D} L^T)^T ( \sqrt {D} L^T) = R^TRA=LDLT=LD​D​LT=(D​LT)T(D​LT)=RTR

(5) => (2)

设A=RTRA = R^TRA=RTR，则对任意非零向量xxx:

xTAx=xTRTRx=(Rx)T(Rx)=∣∣Rx∣∣2>0x^TAx = x^TR^TRx = (Rx )^T(Rx) = ||Rx||^2 > 0xTAx=xTRTRx=(Rx)T(Rx)=∣∣Rx∣∣2>0

(6) => (2)

(6) => (3) => (2)

(2) => (6)

对kkk阶主子矩阵Ai1,...,ikA_{i1,...,ik}Ai1,...,ik​，任取x=(x1,...,xn)≠0x = (x_1,...,x_n) \ne 0x=(x1​,...,xn​)̸​=0，使其除xi1,...,xikx_{i1},...,x_{ik}xi1​,...,xik​的其余分量全为0，则

xTAx=(xi1,...,xik)Ai1,...ik(xi1...xik)>0x^TAx = (x_{i1},...,x_{ik})A_{i1,...ik}\begin{pmatrix}x_{i1}\\... \\ x_{i_k}\end{pmatrix} > 0xTAx=(xi1​,...,xik​)Ai1,...ik​⎝⎛​xi1​...xik​​​⎠⎞​>0

∴det(Ai1,...ik)>0\therefore det (A_{i1,...ik}) > 0∴det(Ai1,...ik​)>0

判断

因此，我们可以用以上充要条件来判断矩阵是否正定。常用的判断方法有：

看顺序主子式是否都大于0Gauss消元后主元是否都大于0看特征值是否都大于0找任意一个向量计算xTAxx^TAxxTAx是否大于0找A=LDLTA = LDL^TA=LDLT分解，看R=DLTR = \sqrt {D} L^TR=D​LT是否满秩

正定矩阵的常见性质

设A,BA,BA,B为正定矩阵，则A+BA+BA+B也为正定矩阵。

设AAA为正定矩阵，则存在矩阵C，使得A=C2A = C^2A=C2。

证明：AAA为正定矩阵，则存在正交矩阵QQQ，使得:

A=QΛQT=(QΛQT)(QΛQT)=C2A = Q\Lambda Q^T = (Q\sqrt{\Lambda}Q^T) (Q\sqrt{\Lambda}Q^T) = C^2A=QΛQT=(QΛ​QT)(QΛ​QT)=C2

设AAA为正定矩阵，则矩阵A2A^2A2和A−1A^{-1}A−1也正定。

设AAA为正定矩阵，矩阵CCC可逆，则B=CTACB = C^TACB=CTAC也正定。

半正定矩阵

充要条件

AAA的所有特征值λi\lambda_iλi​均非负。xTAx≥0x^TAx \ge 0xTAx≥0对所有向量XXX成立。存在矩阵RRR，使得A=RTRA =R^TRA=RTR（RRR可能不是可逆阵）。AAA的所有主子式均非负。（注意，不是所有顺序主子式）