半正定矩陣的判別方法

本文的閱讀等級:中級

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 即可。

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

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

舉例來說,

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

的特徵值是 24。矩陣 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 有軸元 38/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]。下面列舉一些與正定矩陣相仿的半正定矩陣等價性質及判別方法 (含定義):

  1. 定義:對於任一 \mathbf{x}\in\mathbb{R}^n\mathbf{x}^TA\mathbf{x}\ge 0
  2. 特徵值:A 的所有特徵值為非負數。
  3. 矩陣分解:存在一個 n\times n 階實矩陣 B 使得 \mathrm{rank}B=\mathrm{rank}AA=B^TB
  4. 主子陣之行列式: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 0i=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 0i=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}

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

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

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

有特徵值 02,並可分解為

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 是半正定矩陣。

This entry was posted in 線性代數專欄, 二次型 and tagged , , , , , , , . Bookmark the permalink.

2 則回應給 半正定矩陣的判別方法

  1. levinc417 說:

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

    • ccjou 說:

      上面介紹的四個半正定矩陣判別方式都是有效的,差異在於操作的難易度。
      (1)定義必須檢驗每一x\in\mathbb{R}^n,使得x^TAx\ge 0
      (2)必須算出An個特徵值;
      (3)可透過正交對角化實現,如證明過程顯示,但既然已經知道特徵值,這個做法也就失去實用價值;
      (4)必須計算n^2-1個尺寸不一的行列式。

      實際應用時,我們通常採用方法(2)或(4)。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s