Hadamard 不等式

本文的閱讀等級:中級

匈牙利數理哲學家拉卡托斯 (Imre Lakatos, 1922-1974) 主張數學研習應以一種探索和發現的情境邏輯推展,稱為啟發法或助探論 (heuristic)。他強調非形式、準經驗的數學的發展並不是只靠逐步增加毋庸置疑的定理數目,而是靠以思辨與批評、證明與反駁之邏輯對最初猜想的持續不斷的改進 (見“線性代數的演繹主義”)。具體來說,啟發法常從簡單的特例展開,透過提出猜想,設立命題,證明或反駁,從而發現定理並建構理論。本文按照這個探索模式介紹矩陣理論中一個重要的不等式──Hadamard 不等式。

 
A=\mathrm{diag}(a_{11},\ldots,a_{nn}),我們知道對角矩陣 A 的行列式即主對角元之積:

\det A=a_{11}\cdots a_{nn}

推及至任意 n\times n 階矩陣 A,行列式與主對角元之積具有什麼關係?以二階行列式為例,

\begin{aligned}  \det A&=\begin{vmatrix}    a_{11}&a_{12}\\    a_{21}&a_{22}    \end{vmatrix}=a_{11}a_{22}-a_{12}a_{21}\end{aligned}

因為 a_{12}a_{21} 是任意數,我們無法確定 \det Aa_{11}a_{22} 的大小關係。數學探索的旨趣在於鼓勵不同想法,下面我提供兩個。第一,我們可以針對其他特殊矩陣,看能否獲得什麼結論。第二,我們可以從行列式的幾何意義著手,尋找可用的行列式不等關係。

 
為了比較大小,我們要求 \det A 以及所有 a_{ii} 必須是實數。若 A 是 Hermitian 矩陣,A^{\ast}=A,則所有 a_{ii} 都是實數,且 A 的特徵值也全是實數,故 \det A 亦為實數 (行列式等於特徵值之積)。上例二階矩陣 A 若為 Hermitian,a_{21}=\overline{{a}_{12}},就有

\det A=a_{11}a_{22}-\vert a_{12}\vert^2\le a_{11}a_{22}

根據此結果,我們或許認為只要 A 是 Hermitian,即有 \det A\le a_{11}\cdots a_{nn}。不過,當 A 是三階矩陣時,這個猜想很容易就被推翻,例如,

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

此例中,\det A=-5,而 a_{11}\cdot a_{22}\cdot a_{33}=-6。值得注意的是,若將 a_{11}=-1 替換為 a_{11}=1,那麼 \det A 便小於主對角元之積。於是,我們又有了另一個猜想:若限制 A 為半正定矩陣,則 \det A 必不大於 a_{11}\cdots a_{nn}。事實上,這個猜想於公元 1893 年由法國數學家阿達馬 (Jacques Hadamard, 1865-1963) 提出並予以證明。

 
Hadamard 不等式(一)

A=[a_{ij}]n\times n 階半正定矩陣,則

\det A\le\displaystyle\prod_{i=1}^n{a}_{ii}

惟當 A 不可逆或 A 是對角矩陣時,等號成立。

 
先回顧正定矩陣的基本性質。若 An\times n 階複正定矩陣,則 A 是 Hermitian,A^{\ast}=AA 的特徵值皆為正數,也就有 \det A>0A 的所有主對角元 a_{ii}>0A 可表示為 A=B^{\ast}B,其中 B 可逆 (見“正定矩陣的性質與判別方法”,“Cholesky 分解”)。

 
Hadamard 不等式(一)的證明包含兩種情況。若 A 不可逆,則 \det A=0,不等式自然成立。若 A 可逆,即 A 是正定,也就有 a_{ii}>0i=1,\ldots,n。令 D=\mathrm{diag}(\frac{1}{\sqrt{a_{11}}},\ldots,\frac{1}{\sqrt{a_{nn}}}),顯然 D 可逆,且 D^{\ast}=D。令 C=[c_{ij}]=D^{\ast}AD,展開等號右邊可確認所有 c_{ii}=1。對於任意 \mathbf{x}\in\mathbb{C}^n

\begin{aligned}  \mathbf{x}^{\ast}C\mathbf{x}&=\mathbf{x}^{\ast}D^{\ast}AD\mathbf{x}=(D\mathbf{x})^{\ast}A(D\mathbf{x})>0\end{aligned}

換句話說,C 是正定矩陣,令 \lambda_i>0i=1,\ldots,n,為 C 的特徵值。寫出 A=D^{-1}CD^{-1},計算行列式

\begin{aligned}  \det A&=\det(D^{-1}CD^{-1})\\  &=(det D^{-1})(\det C)(\det D^{-1})\\  &=(\det D^{-1})^{2}(\det C)\\  &=\displaystyle\left(\prod_{i=1}^na_{ii}\right)(\det C)\end{aligned}

利用算術—幾何平均值不等式,即得

\begin{aligned}  \det C&=\displaystyle\prod_{i=1}^n\lambda_i\le\left(\frac{1}{n}\sum_{i=1}^n\lambda_i\right)^n=\left(\frac{1}{n}\mathrm{trace}C\right)^n=1\end{aligned}

因此證得所求。當 A 可逆時,等號發生於所有 \lambda_i=1。因為 C 正定,故可對角化為 C=U\mathrm{diag}(\lambda_1,\ldots,\lambda_n)U^{\ast},其中 U^{\ast}U=I,也就推得 C=I,所以 A 是對角矩陣。

 
我們還有第二個想法:若從行列式的幾何意義出發,又能得到什麼結論?對於任意 n\times n 階矩陣 A,行列式的絕對值 \vert\det A\vert 等於 A 的行向量 (或列向量) 於 \mathbb{C}^n 空間所張開的「平行多面體體積」(見“行列式的幾何意義”)。從幾何直觀,行向量是平行多面體的邊,當所有的行向量彼此正交時,平行多面體具有最大體積,該體積即為各邊長的乘積。這個幾何性質可轉換為下列代數不等描述。

 
Hadamard 不等式(二)

Bn\times n 階矩陣,令 \mathbf{b}_1,\ldots,\mathbf{b}_n 代表 B 的行向量,則

\displaystyle\vert\det B\vert\le\prod_{i=1}^n\Vert\mathbf{b}_i\Vert

B 可逆時,等號僅發生於 B 的行向量彼此正交,即 \mathbf{b}_i^{\ast}\mathbf{b}_j=0,若 i\neq j

 
同樣分開兩個情況證明。若 B 不可逆,\det B=0,不等式自然成立。若 B 可逆,令 A=B^{\ast}B,或者寫為

A=\begin{bmatrix}    \mathbf{b}_1^{\ast}\\    \vdots\\    \mathbf{b}_n^{\ast}    \end{bmatrix}\begin{bmatrix}    \mathbf{b}_1&\cdots&\mathbf{b}_n    \end{bmatrix}

察覺 A 是正定矩陣,根據 Hadamard 不等式(一),

\begin{aligned}  \det A&\le\displaystyle\prod_{i=1}^na_{ii}=\prod_{i=1}^n\mathbf{b}_i^{\ast}\mathbf{b}_i=\prod_{i=1}^n\Vert\mathbf{b}_i\Vert^2\end{aligned}

另一方面,

\begin{aligned}  \det A&=\det(B^{\ast}B)=(\det B^{\ast})(\det B)=\vert\det B\vert^2\end{aligned}

上面兩式同取平方根,即得證。當 B 的行向量相互正交時,A 為對角矩陣,這正是 Hadamard 不等式(一)等號成立的條件。

 
令人驚訝的是,Hadamard 不等式(一)和不等式(二)是等價的。由不等式(二)也可以證明不等式(一),過程與不等式(二)的證明雷同:若 A 正定,則存在可逆矩陣 B 使得 A=B^{\ast}B,再將 Hadamard 不等式(二)應用於 B,即得不等式(一)。

 
拉卡托斯在其大作《證明與反駁》(Proofs and Refutations) 中,以一種帶有理想主義的口吻為他所提倡的啟發法辯護:「有些邏輯學家、哲學家和其他怪癖狂干涉內政的務實數學家說,引入助探體例,教科書就得重寫,准會長得誰也無法從頭讀到尾。文章也要拉得很長很長。我對這種世俗的論據的回答是:那就試試看吧。」 於是乎,我寫了這篇全憑個人想像的追溯數學概念與定理發現過程的文章。

相關閱讀:
Advertisements
本篇發表於 線性代數專欄, 行列式 並標籤為 , , 。將永久鏈結加入書籤。

4 則回應給 Hadamard 不等式

  1. Liang Dai 說道:

    周老师,我读完这篇文章的感觉倒是normalization的重要。假如在证明Hadamard不等式(一)的时候不作normalization,则是走不通的。比如,

    det(A)
    = lambda_1*lambda_2*…*lambda_n
    <= ((a_11+a_22+…+a_nn)/n )^n

    再往下走就比较困难了。而如果先做normalization,即把对角线元素都变为1,则a_11+a_22+…+a_nn = 1,右端被简化,不等式就得到了。

  2. ccjou 說道:

    哈!你說的對,不等式(一)的助探論腳本應該這麼寫:
    \det A=\lambda_1(A)\cdots\lambda_n(A)
    \le(\frac{1}{n}(\lambda_1(A)+\cdots+\lambda_n(A)))^n=(\frac{1}{n}(a_{11}+\cdots+a_{nn}))^n
    這時碰壁了,所以才想到將 A 分解(正規化)為
    A=\begin{bmatrix} a_{11}&~&\ast\\ ~&\ddots&~\\ \ast&~&a_{nn} \end{bmatrix}=\begin{bmatrix} \sqrt{a_{11}}&~&~\\ ~&\ddots&~\\ ~&~&\sqrt{a_{nn}} \end{bmatrix}\begin{bmatrix} 1&~&\ast\\ ~&\ddots&~\\ \ast&~&1 \end{bmatrix}\begin{bmatrix} \sqrt{a_{11}}&~&~\\ ~&\ddots&~\\ ~&~&\sqrt{a_{nn}} \end{bmatrix}

  3. Liang.Dai 說道:

    谢谢周老师。
    第一个不等式其实可以用归纳法来证明。只需要利用将n*n的矩阵分块成四块,其中对角线上两块的体积为(n-1)*(n-1),1*1,然后将n*n矩阵的行列式值表示为(n-1)*(n-1)行列式值与shur complement的乘积,即可发现结果。

  4. ccjou 說道:

    好的,下一篇就來討論分塊矩陣的做法:若
    \begin{bmatrix} A&B\\ B^{\ast}&C \end{bmatrix} 正定,則
    \begin{vmatrix} A&B\\ B^{\ast}&C \end{vmatrix}\le(\det A)(\det C)

發表迴響

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

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s