答謝一誠──關於判斷正定、負定或未定二次型的問題

網友謝一誠留言：

老師您好，我想請問周老師，關於Quadratic Forms的定理。在 Elementary Linear Algebra (作者Howard Anton，Chris Rorres，第9版，2005)，書中Exercise set 9.5 (page 486)：

11. In each part, classify the quadratic form as positive definite, positive semidefinite, negative definite, negative semidefinite, or indefinite.
(f) $x_1x_2$

方法一：用此書中定理9.5.2 (page 482)
A symmetric matrix $A$ is positive definite if and only if all the eigenvalues of $A$ are positive.
找出此quadratic form的實對稱矩陣，求其特徵值，得到特徵值為 $1/2$ 及 $-1/2$ ，所以答案是indefinite(未定)。

方法二：用此書中定理9.5.3 (page 484)
A symmetric matrix $A$ is positive definite if and only if the determinant of every principal submatrix is positive.
判斷這個實對稱矩陣，得出negative semidefinite，但這個結論是錯誤的！

page 484中間REMARK的內容有說定理9.5.2和9.5.3可以修改用來判斷 positive semidefinite，negative definite，negative semidefinite：

A symmetric matrix $A$ and the quadratic form $\mathbf{x}^TA\mathbf{x}$ are called
positive semidefinite if $\mathbf{x}^TA\mathbf{x}\ge 0$ for all $\mathbf{x}$
negative definite if $\mathbf{x}^TA\mathbf{x}<0$ for $\mathbf{x}\neq\mathbf{0}$
negative semidefinite if $\mathbf{x}^TA\mathbf{x}\le 0$ for all $\mathbf{x}$
indefinite if $\mathbf{x}^TA\mathbf{x}$ has both positive and negative values

Theorems 9.5.2 and 9.5.3 can be modified in an obvious way to apply to matrices of the first three types. For example, a symmetric matrix $A$ is positive semidefinite if and only if all of its eigenvalues are nonnegative. Also, $A$ is positive semidefinite if and only if all its principal submatrices have nonnegative determinants.

那indefinite的部分，是否可以藉由principal submatrices of $A$ 的行列式值來判斷呢？課本後面的習題，我都有用這兩種方式去算算看，就唯獨這一題很奇怪。所以想請教老師，我對於書中的定理有哪邊有了誤解？

答曰：

將給定的二次型表示如下：

$x_1x_2=\mathbf{x}^TA\mathbf{x}=\begin{bmatrix} x_1 & x_2 \end{bmatrix}\begin{bmatrix} 0&\frac{1}{2}\\[0.3em] \frac{1}{2}&0 \end{bmatrix}\begin{bmatrix} x_1\\ x_2 \end{bmatrix}$ 。

根據REMARK的說法，定理9.5.2和9.5.3皆可用於判斷 $A=\begin{bmatrix} 0&\frac{1}{2}\\[0.3em] \frac{1}{2}&0 \end{bmatrix}$ 是 (半) 正定或 (半) 負定矩陣。使用方法一，以特徵值來判斷，寫出 $A$ 的特徵多項式

$\displaystyle p(t)=\det(A-tI)=\begin{vmatrix} 0-t&\frac{1}{2}\\[0.3em] \frac{1}{2}&0-t \end{vmatrix}=t^2-\frac{1}{4}=\left(t-\frac{1}{2}\right)\left(t+\frac{1}{2}\right)$ ，

即得特徵值 $\lambda_1=1/2$ ， $\lambda_2=-1/2$ 。根據定理9.5.2，可知 $A$ 既非正定或半正定，也不是負定或半負定，故 $A$ 是一個未定矩陣。

使用方法二，以領先主子陣的行列式來判斷，可得

$\displaystyle \det A_1=\begin{vmatrix} 0 \end{vmatrix}=0,~~\det A_2=\begin{vmatrix} 0&\frac{1}{2}\\[0.3em] \frac{1}{2}&0 \end{vmatrix}=-\frac{1}{4}$ 。

根據定理9.5.3， $A$ 的領先主子陣的行列式皆不為正，故推論 $A$ 是半負定矩陣。方法一和方法二得到不同的結論，究竟孰對孰錯？從 $A$ 的特徵值 $\lambda_1=1/2$ ， $\lambda_2=-1/2$ ，可求出對應的特徵向量

$\mathbf{x}_1=\left[\!\!\begin{array}{c} 1\\ 1 \end{array}\!\!\right],~\mathbf{x}_2=\left[\!\!\begin{array}{r} 1\\ -1 \end{array}\!\!\right]$ 。

將特徵向量代入二次型計算，

$\begin{aligned}\displaystyle \mathbf{x}_1^TA\mathbf{x}_1&=\mathbf{x}_1^T(\lambda_1\mathbf{x}_1)=\lambda_1\Vert\mathbf{x}_1\Vert^2=\frac{1}{2}\cdot 2=1\\ \mathbf{x}_2^TA\mathbf{x}_2&=\mathbf{x}_2^T(\lambda_2\mathbf{x}_2)=\lambda_2\Vert\mathbf{x}_2\Vert^2=-\frac{1}{2}\cdot 2=-1, \end{aligned}$

故可確認 $A$ 是一個未定矩陣。

方法一所依據的定理9.5.2的確可用於判斷 (半) 正定、(半) 負定或未定矩陣，但方法二採用的領先主子陣行列式僅適用於判斷正定矩陣，不能推廣至半正定、負定、半負定或未定矩陣 (見補註)。試舉一例， $A=\left[\!\!\begin{array}{cr} 0&0\\ 0&-1 \end{array}\!\!\right]$ 有特徵值 $0$ 和 $-1$ ，它是半負定矩陣。然而， $A$ 的領先主子陣行列式都是 $0$ ，故無從判斷 $A$ 到底是半正定或半負定。所以並不是你對書中的定理那邊有了誤解，而是課本REMARK給出錯誤的陳述。課本出錯不是甚麼大不了的事情，但為何刊行至第9版的教科書仍出現這麼嚴重的錯誤？原因或許在於定理9.5.3沒有提出相應的證明，作者只寫了一句話：“We omit the proof.”

以領先主子陣行列式判斷正定矩陣的理論基礎在於正定矩陣的所有軸元 (pivot) 皆為正數 (見“正定矩陣的性質與判別方法”，定理三)，相反命題也成立，證明於下。設 $n\times n$ 階實對稱矩陣 $A$ 有 LDU 分解式 $A=LDL^T$ (見“LU 分解”)，其中 $D=\mathrm{diag}(d_1,\ldots,d_n)$ ， $d_i$ 稱為軸元， $L$ 是一 $n\times n$ 階下三角矩陣，主對角元等於 $1$ 。若 $d_i>0$ ， $i=1,\ldots,n$ ，對於任一非零向量 $\mathbf{x}$ ，即有

$\displaystyle \mathbf{x}^TA\mathbf{x}=\mathbf{x}^TLDL^T\mathbf{x}=(L^T\mathbf{x})^TD(L^T\mathbf{x})=\mathbf{y}^TD\mathbf{y}=\sum_{i=1}^nd_iy_i^2>0$ ，

上式中， $\mathbf{y}=L^T\mathbf{x}\neq\mathbf{0}$ (因為 $L$ 是可逆矩陣)。為甚麼定理9.5.3使用領先主子陣的行列式來判斷正定矩陣呢？將 $A=LDL^T$ 表示為分塊矩陣形式：

$A=\begin{bmatrix} L_i&0\\ B&C \end{bmatrix}\begin{bmatrix} D_i&0\\ 0&E \end{bmatrix}\begin{bmatrix} L_i^T&B^T\\ 0&C^T \end{bmatrix}=\begin{bmatrix} L_iD_iL_i^T&L_iD_iB^T\\ BD_iL_i^T&BD_iB^T+CEC^T \end{bmatrix}$ ，

其中 $L_i$ 是主對角元為 $1$ 的 $i\times i$ 階下三角矩陣， $D_i=\mathrm{diag}(d_1,\ldots,d_i)$ 。注意， $A_i=L_iD_iL_i^T$ ， $i=1,\ldots,n$ ，即為 $A$ 的領先主子陣。因為

$\det A_i=(\det L_i)(\det D_i)(\det L^T_i)=\det D_i=d_1\cdots d_i$ ，

軸元 $d_i$ 和領先主子陣 $A_i$ 的行列式有下列關係： $d_1=\det A_1$ ，對於 $i=2,3,\ldots,n$ ，若 $\det A_{i-1}\neq 0$ ，則 $d_i=\det A_i/\det A_{i-1}$ 。如果 $\det A_i>0$ ， $i=1,\ldots,n$ ，則 $d_i>0$ ， $i=1,\ldots,n$ ，即知 $A$ 是正定矩陣。

最後補充解釋何以二次型總是以實對稱矩陣表示。如果我們將給定的二次型寫成

$x_1x_2=\mathbf{x}^TB\mathbf{x}=\begin{bmatrix} x_1&x_2 \end{bmatrix}\begin{bmatrix} 0&1\\ 0&0 \end{bmatrix}\begin{bmatrix} x_1\\ x_2 \end{bmatrix}$ ，

矩陣 $B=\begin{bmatrix} 0&1\\ 0&0 \end{bmatrix}$ 有重複特徵值 $0, 0$ 。這時定理9.5.2也不管用，因為定理要求被檢測的矩陣必須是實對稱。將 $B$ 改寫成

$\displaystyle B=\frac{B+B^T}{2}+\frac{B-B^T}{2}=\begin{bmatrix} 0&\frac{1}{2}\\[0.3em] \frac{1}{2}&0 \end{bmatrix}+\begin{bmatrix} 0&\frac{1}{2}\\[0.3em] -\frac{1}{2}&0 \end{bmatrix}=A+C$ ，

其中 $A$ 是實對稱矩陣， $C$ 是反對稱矩陣 (anti-symmetric)。很容易確認任一 $\mathbf{x}$ 滿足 $\mathbf{x}^TC\mathbf{x}=0$ ，故 $\mathbf{x}^TB\mathbf{x}=\mathbf{x}^TA\mathbf{x}$ 。再看一個特別的例子， $B=\left[\!\!\begin{array}{cr} 1&-3\\ 0&1 \end{array}\!\!\right]$ 有重複特徵值 $1, 1$ ，但 $\mathbf{x}^TB\mathbf{x}>0$ ( $\mathbf{x}\neq\mathbf{0}$ ) 不總是成立，因為實對稱矩陣 $\frac{1}{2}(B+B^T)=\left[\!\!\begin{array}{rr} 1&-\frac{3}{2}\\ -\frac{3}{2}&1 \end{array}\!\!\right]$ 有特徵值 $-1/2$ 和 $5/2$ 。對於非實對稱矩陣 $B$ ，縱使所有的特徵值皆為正數也不能保證它滿足 $\mathbf{x}^TB\mathbf{x}>0$ ( $\mathbf{x}\neq\mathbf{0}$ )。為了不給自己添麻煩，我們總是用實對稱矩陣來定義二次型。

補註：

實對稱矩陣 $A$ 是負定等價於 $-A$ 是正定，因此欲判定 $A$ 是負定，我們可以檢查 $-A$ 的領先主子陣行列式是否為正。不過，若 $A$ 的領先主子陣行列式皆為負數，仍不足以能斷定 $A$ 是負定。例如， $A=\left[\!\!\begin{array}{rc} -1&1\\ 1&0 \end{array}\!\!\right]$ 有特徵值 $(-1+\sqrt{5})/2$ ， $(-1-\sqrt{5})/2$ ，可知 $A$ 是一個未定矩陣，但 $A$ 的領先主子陣行列式是 $\det A_1=-1$ ， $\det A_2=-1$ 。從矩陣 $A$ 的領先主子陣行列式全為負值無法推論 $A$ 的軸元皆為負數，因為 $d_1=\det A_1=-1$ ，但 $d_2=\det A_2/\det A_1=(-1)/(-1)=1$ 。

若實對稱矩陣 $A$ 的所有 (不僅僅是領先) 主子陣行列式皆不為負，則 $A$ 是半正定矩陣。例如， $A=\begin{bmatrix} 0&0\\ 0&1 \end{bmatrix}$ 的所有主子陣包括 $A_{\{1\}}=\begin{bmatrix} 0 \end{bmatrix}$ ， $A_{\{2\}}=\begin{bmatrix} 1 \end{bmatrix}$ ， $A_{\{1,2\}}=A$ ，則 $\det A_{\{1\}}=0$ ， $\det A_{\{2\}}=1$ ， $\det A_{\{1,2\}}=0$ ，可推論 $A$ 是半正定。證明如下：考慮 $A$ 的特徵多項式
$p(t)=\det(tI-A)=t^n-\delta_1t^{n-1}+\delta_2t^{n-2}-\cdots(-1)^n\det A$ ，

其中 $\delta_i$ 是所有 $i$ 階主子陣行列式的和 (見“特徵多項式蘊藏的訊息”)。若 $A$ 的所有主子陣行列式皆不為負值，則每一 $i$ 都有 $\delta_i\ge 0$ ，這指出 $p(t)$ 不可能存在負根。
假設實矩陣 $A$ 不對稱且每一 $\mathbf{x}\neq\mathbf{0}$ ，都有 $\mathbf{x}^TA\mathbf{x}>0$ 。因為 $\mathbf{x}^TA\mathbf{x}=\frac{1}{2}\mathbf{x}^T(A+A^T)\mathbf{x}$ ，可知 $A+A^T$ 是正定矩陣，即有 $\det(A+A^T)>0$ 。但能否推論出 $\det A>0$ ？使用逆否命題法。假設 $\det A\le 0$ ，則至少存在一特徵值 $\lambda\le 0$ (因為共軛特徵值 $a\pm bi$ ， $i=\sqrt{-1}$ ，滿足 $(a+bi)(a-bi)=a^2+b^2\ge 0$ )，也就存在一特徵向量 $\mathbf{x}$ 使得 $\mathbf{x}^TA\mathbf{x}=\lambda\Vert\mathbf{x}\Vert^2\le 0$ ，故得證。

2 Responses to 答謝一誠──關於判斷正定、負定或未定二次型的問題

一誠 says:

01/07/2013 at 9:50 pm

謝謝老師的指點，讓我獲益良多!

- ccjou says:
  
  01/08/2013 at 2:29 pm
  
  事有湊巧。今日收到書商寄來的樣書，打開一看，書名是
  Elementary Linear Algebra, 10th edition, Howard Anton and Chris Rorres, 2011.
  翻至7.3 Quadratic Forms，第9版的定理9.5.2和9.5.3變成了7.3.2和7.3.4(page 412-414)，第9版的錯誤REMARK已經刪除，但定理7.3.4仍然沒有提供證明。
  
  先前的回覆有一個錯誤，順便訂正，請見補註。

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