半正定矩陣的判別方法

本文的閱讀等級：中級

令 $A$ 為一個 $n\times n$ 階實對稱矩陣。若任一向量 $\mathbf{x}\in\mathbb{R}^n$ 使得二次型 $\mathbf{x}^TA\mathbf{x}>0$ ，我們稱 $A$ 是正定 (positive definite) 矩陣 (見“特殊矩陣 (6)：正定矩陣”)。若任一向量 $\mathbf{x}\in\mathbb{R}^n$ 皆滿足 $\mathbf{x}^TA\mathbf{x}\ge 0$ ，則稱 $A$ 為半正定 (positive semidefinite) 矩陣。本文介紹幾個半正定矩陣的判別方法。如欲將本文內容推廣至 Hermitian 複矩陣，僅須將實數系 $\mathbb{R}$ 替換為複數系 $\mathbb{C}$ ，並且將轉置 $(\cdot)^T$ 替換為共軛轉置 $(\cdot)^\ast$ 即可。

正定矩陣存在多種等價性質和判別方法 (見“正定矩陣的性質與判別方法”)：

特徵值： $A$ 的所有特徵值皆為正數。
軸元 (pivot)： $A$ 的所有軸元皆為正數。
Cholesky 分解：存在一個 $n\times n$ 階可逆矩陣 $B$ ，使得 $A=B^TB$ (見“Cholesky 分解”)。
領先主子陣 (leading principal submatrix) 的行列式： $A$ 的所有領先主子陣的行列式皆為正數。

舉一例，實對稱矩陣

$A=\left[\!\!\begin{array}{rr} 3&-1\\ -1&3 \end{array}\!\!\right]$

的特徵值是 $2$ 和 $4$ 。矩陣 $A$ 的 LDU 分解為

$A=\left[\!\!\begin{array}{rr} 1&0\\[0.3em] -\frac{1}{3}&1 \end{array}\!\!\right]\left[\!\!\begin{array}{cc} 3&0\\[0.3em] 0&\frac{8}{3} \end{array}\!\!\right]\left[\!\!\begin{array}{rr} 1&-\frac{1}{3}\\[0.3em] 0&1 \end{array}\!\!\right]$ ，

可知 $A$ 有軸元 $3$ 和 $8/3$ 。矩陣 $A$ 的 Cholesky 分解為

$A=\left[\!\!\begin{array}{rr} \sqrt{3}&0\\[0.3em] -\frac{1}{\sqrt{3}}&\frac{\sqrt{8}}{\sqrt{3}} \end{array}\!\!\right]\left[\!\!\begin{array}{rr} \sqrt{3}&-\frac{1}{\sqrt{3}}\\[0.3em] 0&\frac{\sqrt{8}}{\sqrt{3}} \end{array}\!\!\right]=B^TB$ ，

其中 $B$ 是可逆矩陣。最後， $A$ 的領先主子陣的行列式如下：

$\det A_1=\begin{vmatrix} 3 \end{vmatrix}=3,~\det A_2=\left|\!\!\begin{array}{rr} 3&-1\\[0.3em] -1&3 \end{array}\!\!\right|=8$ 。

上述結果都指出 $A$ 是一個正定矩陣。

如果不仔細考量，你或許認為直接將正定矩陣判別方法中的「正數」改為「非負數」即可套用至半正定矩陣，但事實並非完全如此。若 $A$ 是不可逆的，則 $A$ 不存在 LU 分解，而且縱使 $A$ 的領先主子陣行列式皆非負值也不能保證 $A$ 是半正定 (見“答謝一誠──關於判斷正定、負定或未定二次型的問題”)，例如， $\left[\!\!\begin{array}{rr} 0&0\\ 0&-1 \end{array}\!\!\right]$ 。下面列舉一些與正定矩陣相仿的半正定矩陣等價性質及判別方法 (含定義)：

定義：對於任一 $\mathbf{x}\in\mathbb{R}^n$ ， $\mathbf{x}^TA\mathbf{x}\ge 0$ 。
特徵值： $A$ 的所有特徵值為非負數。
矩陣分解：存在一個 $n\times n$ 階實矩陣 $B$ 使得 $\mathrm{rank}B=\mathrm{rank}A$ 且 $A=B^TB$ 。
主子陣之行列式： $A$ 的所有主子陣之行列式為非負值。

以下證明過程使用實對稱矩陣的兩個關鍵性質：實對稱矩陣 $A$ 的特徵值 $\lambda_1,\ldots,\lambda_n$ 必為實數，並可正交對角化 (見“實對稱矩陣可正交對角化的證明”)，也就是說，存在單範正交 (orthonormal) 特徵向量 $\mathbf{x}_1,\ldots,\mathbf{x}_n$ 。

(1) $\Rightarrow$ (2)：考慮特徵方程 $A\mathbf{x}_i=\lambda_i\mathbf{x}_i$ 。利用半正定矩陣定義，可得

$\mathbf{x}_i^TA\mathbf{x}_i=\mathbf{x}_i^T(\lambda_i\mathbf{x}_i)=\lambda_i\Vert\mathbf{x}_i\Vert^2\ge 0$ ，

故知 $\lambda_i\ge 0$ ， $i=1,\ldots,n$ 。

(2) $\Rightarrow$ (1)：因為 $\mathbf{x}_1,\ldots,\mathbf{x}_n$ 構成 $\mathbb{R}^n$ 的一組基底，任一 $\mathbf{x}\in\mathbb{R}^n$ 可唯一表示成 $\mathbf{x}=c_1\mathbf{x}_1+\cdots+c_n\mathbf{x}_n$ 。若 $\lambda_i\ge 0$ ， $i=1,\ldots,n$ ，則

$\displaystyle \begin{aligned} \mathbf{x}^TA\mathbf{x}&=\left(\sum_{i=1}^nc_i\mathbf{x}_i\right)^TA\left(\sum_{i=1}^nc_i\mathbf{x}_i\right)=\left(\sum_{i=1}^nc_i\mathbf{x}_i\right)^T\left(\sum_{i=1}^nc_iA\mathbf{x}_i\right)\\ &=\left(\sum_{i=1}^nc_i\mathbf{x}_i\right)^T\left(\sum_{i=1}^nc_i\lambda_i\mathbf{x}_i\right)=\sum_{i=1}^nc_i^2\lambda_i\Vert\mathbf{x}_i\Vert^2\ge 0,\end{aligned}$

證得 $A$ 是一個半正定矩陣。

(2) $\Rightarrow$ (3)：在不失一般性的原則下，假設 $\lambda_1\ge\cdots\ge\lambda_r>0$ ， $\lambda_{r+1}=\cdots=\lambda_n=0$ 。令 $\Lambda=\mathrm{diag}(\lambda_1,\ldots,\lambda_n)$ 且 $Q=\begin{bmatrix} \mathbf{x}_1&\cdots&\mathbf{x}_n \end{bmatrix}$ 為一個正交 (orthogonal) 矩陣， $Q^T=Q^{-1}$ 。實對稱矩陣 $A$ 可正交對角化如下：

$A=Q\Lambda Q^T=Q\Lambda^{1/2}\Lambda^{1/2}Q^T=(\Lambda^{1/2}Q^T)^T(\Lambda^{1/2}Q^T)=B^TB$ ，

上式中， $\Lambda^{1/2}=\mathrm{diag}(\sqrt{\lambda_1},\ldots,\sqrt{\lambda_n})$ 。因為 $Q$ 是可逆的， $\mathrm{rank}A=\mathrm{rank}(Q\Lambda Q^T)=\mathrm{rank}\Lambda$ 且 $\mathrm{rank}B=\mathrm{rank}(\Lambda^{1/2}Q^T)=\mathrm{rank}\Lambda^{1/2}$ ，但是 $\mathrm{rank}\Lambda=\mathrm{rank}\Lambda^{1/2}=r$ ，故可推得 $\mathrm{rank}A=\mathrm{rank}B=r$ 。

(3) $\Rightarrow$ (4)：設 $A=B^TB$ 。令 $A_k$ 代表 $A$ 的任一 $k\times k$ 階主子陣 (未必是領先主子陣)， $P$ 為一個排列矩陣使得

$\begin{bmatrix} A_k&\ast\\ \ast&\ast \end{bmatrix}=P^TAP=P^TB^TBP=\begin{bmatrix} F^T\\ G^T \end{bmatrix}\begin{bmatrix} F&G \end{bmatrix}$ ，

其中 $F$ 是 $n\times k$ 階分塊，乘開比較可得 $A_k=F^TF$ 。對於任一 $\mathbf{y}\in\mathbb{R}^k$ ， $\mathbf{y}^TA_k\mathbf{y}=\mathbf{y}^TF^TF\mathbf{y}=\Vert F\mathbf{y}\Vert^2\ge 0$ ，故知 $A_k$ 是實對稱半正定。根據 (2)， $A_k$ 的特徵值皆非負值，可推論 $\det A_k\ge 0$ (因為行列式等於特徵值的積)。

(4) $\Rightarrow$ (2)：考慮 $A$ 的特徵多項式

$\begin{aligned} p(t)&=\det(tI-A)\\ &=t^n-d_{n-1}t^{n-1}+d_{n-2}t^{n-2}-\cdots+(-1)^{n-1}d_1t+(-1)^nd_0\\ &=\displaystyle\sum_{i=0}^n(-1)^{n-i}d_{i}t^{i}=\sum_{i=0}^n(-1)^{n+i}d_{i}t^{i}\\ &=(-1)^n\sum_{i=0}^nd_{i}(-t)^{i},\end{aligned}$

其中 $d_i$ ， $0\le i\le n-1$ ，是所有 $i\times i$ 階主子陣行列式的和 (見“特徵多項式蘊藏的訊息”)，並定義 $d_n\equiv 1$ 。若 $A$ 的所有主子陣行列式大於或等於零，則 $d_i\ge 0$ ， $0\le i\le n-1$ 。所以， $t<0$ 蘊含 $p(t)\neq 0$ ，這說明 $p(t)$ 不含負根，也就是說， $A$ 的特徵值不為負數。

最後舉一個簡單的例子說明半正定矩陣的判別方法。見下例，

$A=\begin{bmatrix} 0&0\\ 0&2 \end{bmatrix}$

有特徵值 $0$ 和 $2$ ，並可分解為

$A=\begin{bmatrix} 0&0\\ 0&\sqrt{2} \end{bmatrix}\begin{bmatrix} 0&0\\ 0&\sqrt{2}\end{bmatrix}=B^TB$ ，

其中 $\mathrm{rank}A=\mathrm{rank}B=1$ 。又 $A$ 的所有主子陣包括 $[0]$ ， $[2]$ ，及 $A$ 本身，行列式分別是 $\det[0]=0$ ， $\det[2]=2$ ， $\det A=0$ 。這三種檢查方式一致判定 $A$ 是半正定矩陣。

2 Responses to 半正定矩陣的判別方法

levinc417 says:

01/22/2013 at 8:01 pm

連續看了幾篇一點小疑惑: 難道沒有一個比較robust且一致性的判斷檢驗嗎？雖然我還是覺得不明朗時從定義來比較合理欸…

- ccjou says:
  
  01/22/2013 at 9:54 pm
  
  上面介紹的四個半正定矩陣判別方式都是有效的，差異在於操作的難易度。
  (1)定義必須檢驗每一 $x\in\mathbb{R}^n$ ，使得 $x^TAx\ge 0$ ；
  (2)必須算出 $A$ 的 $n$ 個特徵值；
  (3)可透過正交對角化實現，如證明過程顯示，但既然已經知道特徵值，這個做法也就失去實用價值；
  (4)必須計算 $n^2-1$ 個尺寸不一的行列式。
  
  實際應用時，我們通常採用方法(2)或(4)。

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨