線性代數筆記11：正定矩陣了解及推導

title: 線性代數筆記11：正定矩陣了解及推導

tags:

• linear algebra

  categories:

• linear algebra

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

  mathjax: true

正定矩陣及半正定矩陣在機器學習和深度學習中有很重要的應用。

引言

1. 定義：特征值全是正實數的實對稱矩陣為正定矩陣（positive definite matrix）。
2. 類似的，若實對稱矩陣的特征值均非負，則為半正定矩陣（positive semidefinite matrix）。

可能用到的概念

• 主子式

  定義：在 n n n階行列式中任選 k k k行，再取相應的 k k k列，将行列交彙處元素組成新的矩陣行列式，稱為 n n n階行列式的一個 k k k階主子式。

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

  定義：在 n n n階行列式中由第 1 , . . . , k 1,...,k 1,...,k行和第 1 , . . . , k 1,...,k 1,...,k列所确定的主子式稱為 k k k階順序主子式。直覺上看就是矩陣中左上方的子矩陣。

實對稱矩陣 A A A正定的充要條件

注意，這裡的所有進行判别的矩陣都是實對稱矩陣。

以下條件都是判别實對稱矩陣是否正定的充要條件。

1. A A A的所有特征值 λ i \lambda_i λi​均為正。
2. x T A x > 0 x^TAx > 0 xTAx>0對所有非零向量 x x x都成立。
3. A A A的所有順序主子式都是正的。
4. A A A的所有主元（無行交換）都是正的。
5. 存在列滿秩矩陣 R R R，使得 A = R T R A=R^TR A=RTR.
6. A A A的所有主子式都是正的。

證明

(1) => (2)

對實對稱矩陣 A A A，存在正交陣 Q Q Q，使得 A = Q Λ Q R A=Q\Lambda Q^R A=QΛQR。

是以，對任意非零向量 x x x：

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

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

(2) => (1)

因為 A A A為實對稱矩陣，是以一定可以對角化 A = Q λ Q T A = Q\lambda Q^T A=QλQT

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

令 y = Q T x y = Q^Tx y=QTx，是以 y Λ y T > 0 ⇒ ∑ λ i y i 2 = 0 y\Lambda y^T > 0\Rightarrow \sum \lambda_iy_i^2 = 0 yΛyT>0⇒∑λi​yi2​=0

∵ ∀ y ≠ 0 s . t ∑ λ i y i 2 = 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) => d e t ( A ) = λ 1 . . . λ n > 0 det(A) = \lambda_1 ...\lambda_n > 0 det(A)=λ1​...λn​>0

x T A x = ( x k T 0 ) ( A k ∗ ∗ ∗ ) ( x k 0 ) = x k T A x k > 0 x^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

∴ d e t ( x k T ) d e t ( A k ) d e t ( k k ) = d e t ( A k ) > 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)

順序主子式與主元有直接關系，第 k k k個主元：

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

其中 A k A_k Ak​是第 k k k個順序主子矩陣（the k-th leading principal submatrix)。

(4) => (2)

由對稱矩陣的Gauss消元法得LDU分解： A = L D L T A = LDL^T A=LDLT，其中對角陣的對角元為 A A A的主元：

D = d i a g ( d 1 , . . . , d n ) D = diag (d_1,...,d_n) D=diag(d1​,...,dn​)

則對任意非零向量：

x T A x = x T L D L T x = y T D y = d 1 y 1 2 + . . . + d n y n 2 > 0 x^TAx = x^TLDL^Tx = y^TDy = d_1y_1^2 + ...+ d_ny_n^2> 0 xTAx=xTLDLTx=yTDy=d1​y12​+...+dn​yn2​>0

(2) => (5)

A = L D L T = L D D L T = ( D L T ) T ( D L T ) = R T R A = LDL^T = L\sqrt {D} \sqrt {D} L^T = ( \sqrt {D} L^T)^T ( \sqrt {D} L^T) = R^TR A=LDLT=LD

​D

​LT=(D

​LT)T(D

​LT)=RTR

(5) => (2)

設 A = R T R A = R^TR A=RTR，則對任意非零向量 x x x:

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

(6) => (2)

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

(2) => (6)

對 k k k階主子矩陣 A i 1 , . . . , i k A_{i1,...,ik} Ai1,...,ik​，任取 x = ( x 1 , . . . , x n ) ≠ 0 x = (x_1,...,x_n) \ne 0 x=(x1​,...,xn​)̸​=0，使其除 x i 1 , . . . , x i k x_{i1},...,x_{ik} xi1​,...,xik​的其餘分量全為0，則

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

∴ d e t ( A i 1 , . . . i k ) > 0 \therefore det (A_{i1,...ik}) > 0 ∴det(Ai1,...ik​)>0

判斷

是以，我們可以用以上充要條件來判斷矩陣是否正定。常用的判斷方法有：

1. 看順序主子式是否都大于0
2. Gauss消元後主元是否都大于0
3. 看特征值是否都大于0
4. 找任意一個向量計算 x T A x x^TAx xTAx是否大于0

5. 找 A = L D L T A = LDL^T A=LDLT分解，看 R = D L T R = \sqrt {D} L^T R=D

   ​LT是否滿秩

正定矩陣的常見性質

1. 設 A , B A,B A,B為正定矩陣，則 A + B A+B A+B也為正定矩陣。

2. 設 A A A為正定矩陣，則存在矩陣C，使得 A = C 2 A = C^2 A=C2。

   證明： A A A為正定矩陣，則存在正交矩陣 Q Q Q，使得:

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

   ​QT)(QΛ

   ​QT)=C2

3. 設 A A A為正定矩陣，則矩陣 A 2 A^2 A2和 A − 1 A^{-1} A−1也正定。
4. 設 A A A為正定矩陣，矩陣 C C C可逆，則 B = C T A C B = C^TAC B=CTAC也正定。

半正定矩陣

充要條件

1. A A A的所有特征值 λ i \lambda_i λi​均非負。
2. x T A x ≥ 0 x^TAx \ge 0 xTAx≥0對所有向量 X X X成立。
3. 存在矩陣 R R R，使得 A = R T R A =R^TR A=RTR（ R R R可能不是可逆陣）。
4. A A A的所有主子式均非負。（注意，不是所有順序主子式）