優超關係與雙隨機矩陣

本文的閱讀等級:高級

A=[a_{ij}] 為一 n\times n 階 Hermitian 矩陣,令 \lambda_1,\ldots,\lambda_n 代表 A 的特徵值。Hermitian 矩陣 A 的特徵值 \lambda_i 皆是實數,所有主對角元 a_{ii} 也是實數(見“特殊矩陣(9):Hermitian 矩陣”)。我們知道矩陣跡數等於特徵值之和,也就是說,主對角元之和等於特徵值之和,即

\displaystyle\sum_{i=1}^na_{ii}=\sum_{i=1}^n\lambda_{i}

除此之外,特徵值 \lambda_i 和主對角元 a_{ii} 還具有某種不易察覺的關係,稱為優超(majorization),它不但是研究許多不等式的重要理論,也是探討矩陣不等式的一個強力武器[1,2]。

 
我們從一個簡單的例子開始談起,考慮對稱矩陣

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

矩陣 A 的特徵值為 1, 4, 5,主對角元為 3, 3, 4。這兩組數列有什麼關係?將兩數列以遞減方式排序,隨即可見主對角元數列 (4, 3, 3) 的分布比特徵值數列 (5,4,1) 來得緊湊,或者說 (4,3,3) 的分配比 (5,4,1) 來得平均。不過這些說法都過於含糊,我們需要更精確的定義。上面第二說法提供了一個思路。將 (4,3,3)(5,4,1) 想像是母親和父親給三名子女零用錢的分配方式,我們的問題只要決定母親抑或父親的分配方式較為平均,並不在乎三名子女孰多得孰少得。考慮極端況狀,最均等的分配方式是平分總額,即 \left(\frac{10}{3},\frac{10}{3},\frac{10}{3}\right),最不均等的方式則是一人通吃,(10,0,0)。這點出一個判斷兩數列何者分配較平均的計算方法:先比較兩數列的最大元,再比較最大二元和,以此類推,倘若結果呈現一面倒,即可斷言那一個數列分配比較平均。上例中,由

\begin{aligned} 4&\le 5\\  4+3&\le 5+4\\  4+3+3&=5+4+1\end{aligned}

可知母親的分配方式 (4,3,3) 比父親的分配方式 (5,4,1) 來得平均。但請讀者特別注意,並非任意兩數列都可按上述方法判定何者較平均,例如,(6,2,2)(5,4,1)

 
由前面的討論可以給出正式的定義。設 \mathbf{x}=(x_1,\ldots,x_n)\mathbf{y}=(y_1,\ldots,y_n)n 維實向量(或視之為數列),令

x_{[1]}\ge\cdots\ge x_{[n]}

y_{[1]}\ge\cdots\ge y_{[n]}

表示二向量所有元按照遞減排序。若

\displaystyle\sum_{i=1}^kx_{[i]}\le\sum_{i=1}^ky_{[i]},~~k=1,\ldots,n-1

\displaystyle\sum_{i=1}^nx_{[i]}=\sum_{i=1}^ny_{[i]}

我們說 \mathbf{y} 優超(majorize)\mathbf{x},記為 \mathbf{x}\prec\mathbf{y}。上例中,特徵值數列優超主對角元數列,

(4,3,3)\prec(5,4,1)

優超一詞雖然典雅,卻不達意。較富直覺的通俗說法是 (5,4,1) 的分布「蓋過」(4,3,3)。根據定義,兩數列的優超關係與數列各元排序無關,因此也有

(3,4,3)\prec(4,1,5)

下面再舉兩個例子以幫助我們迅速掌握優超的概念:

\left(\frac{1}{n},\ldots,\frac{1}{n}\right)\prec\left(\frac{1}{n-1},\ldots,\frac{1}{n-1},0\right)\prec\left(\frac{1}{2},\frac{1}{2},0,\ldots,0\right)\prec(1,0,\ldots,0)

更一般情況,若 a_i\ge a_{i+1}\ge 0\sum_{i=1}^na_i=1,則

\left(\frac{1}{n},\ldots,\frac{1}{n}\right)\prec(a_1,\ldots,a_n)\prec(1,0,\ldots,0)

 
在不失一般性原則下,以下假設 n\times n 階 Hermitian 矩陣 A 的特徵值 \lambda_i 和主對角元 a_{ii} 皆按遞減排序。德國數學家 Issai Schur 於公元 1923 年率先證明 Hermitian 矩陣的特徵值優超主對角元,

(a_{11},\ldots,a_{nn})\prec(\lambda_1,\ldots,\lambda_n)

Schur 的證明從 Hermitian 矩陣的基本性質出發。Hermitian 矩陣 A 可對角化為 A=U\Lambda U^{\ast},其中 \Lambda=\mathrm{diag}(\lambda_1,\ldots,\lambda_n)U=[u_{ij}] 是么正矩陣,U^{\ast}U=I。直接乘開 A=U\Lambda U^{\ast},比較等號兩邊主對角元,可得

a_{ii}=\displaystyle\sum_{j=1}^nu_{ij}\bar{u}_{ij}\lambda_j=\sum_{j=1}^n\vert u_{ij}\vert^2\lambda_j,~~i=1,\ldots,n

將上式改寫成矩陣向量乘積,

\begin{bmatrix}  a_{11}\\  \vdots\\  a_{nn}  \end{bmatrix}=\begin{bmatrix}  \vert u_{11}\vert^2&\cdots&\vert u_{1n}\vert^2\\  \vdots&\ddots&\vdots\\  \vert u_{n1}\vert^2&\cdots&\vert u_{nn}\vert^2  \end{bmatrix}\begin{bmatrix}  \lambda_1\\  \vdots\\  \lambda_n  \end{bmatrix}

n\times n 階矩陣 Q=[q_{ij}]=[\vert u_{ij}\vert^2],因為 U^{\ast}U=UU^{\ast}=I,對於所有 i,j=1,\ldots,n,即知 Q 滿足下列三個性質:

(1) q_{ij}\ge 0

(2) \sum_{j=1}^nq_{ij}=1

(3) \sum_{i=1}^nq_{ij}=1

稱作雙隨機矩陣(doubly stochastic matrix)。令 n 維向量 \mathbf{e} 的每一元都是 1,式 (2) 和 (3) 也可用向量式表達,分別為

Q\mathbf{e}=\mathbf{e}

\mathbf{e}^TQ=\mathbf{e}^T

上式說明 1Q 的一特徵值,\mathbf{e} 是對應的特徵向量。若 Q_1Q_2 是兩個雙隨機矩陣,則 Q_1Q_2 僅含非負元,且 Q_1Q_2\mathbf{e}=Q_1\mathbf{e}=\mathbf{e}\mathbf{e}^TQ_1Q_2=\mathbf{e}^TQ_2=\mathbf{e}^T,故 Q_1Q_2 也是雙隨機矩陣。

 
雙隨機矩陣 Q(a_{11},\ldots,a_{nn})(\lambda_1,\ldots,\lambda_n) 之間的優超關係似乎存在某種關連。見下例,

Q=\begin{bmatrix}  0.4&0.5&0.1\\  0.6&0.2&0.2\\  0.0&0.3&0.7  \end{bmatrix}

標準單位向量 (1,0,0)(0,1,0)(0,0,1) 經雙隨機矩陣 Q 的像即為 Q 的三個行向量,顯然有以下優超關係:

(0.4, 0.6, 0.0)\prec(1,0,0)

(0.5, 0.2, 0.3)\prec(0,1,0)

(0.1, 0.2, 0.7)\prec(0,0,1)

因此我們猜想:若 Q 是雙隨機矩陣,任一向量 \mathbf{y} 優超 Q\mathbf{y}。事實上,此猜想確實為真,更叫人訝異的是,\mathbf{y} 優超 Q\mathbf{y} 也是 Q 為雙隨機矩陣的充分條件,下面是描述此性質的定理。

 
定理一 利用優超關係界定雙隨機矩陣

Q=[q_{ij}] 為一 n\times n 階矩陣,若對於任何 \mathbf{y}\in\mathbb{R}^nQ\mathbf{y}\prec\mathbf{y},則 Q 是雙隨機矩陣;反之亦然。

 
此定理的證明講求完全掌握雙隨機矩陣基本性質和優超關係,詳述於下。

(\Rightarrow):對於任意 n 維實向量 \mathbf{y},假設 Q\mathbf{y}\prec\mathbf{y} 成立。當 \mathbf{y}=\mathbf{e},就有 Q\mathbf{e}\prec\mathbf{e}。若存在 \mathbf{x}\prec\mathbf{e},必然 \mathbf{x}=\mathbf{e},因為所有元相同的向量比任何其他向量來得緊湊。合併以上結果,即知 Q\mathbf{e}=\mathbf{e}。接著令 \mathbf{y}=\mathbf{e}_j,即 y_j=1y_i=0i\neq j,由假設條件可知

Q\mathbf{e}_j=\begin{bmatrix}  q_{1j}\\  \vdots\\  q_{nj}  \end{bmatrix}\prec\mathbf{e}_j

這表示 \sum_{i=1}^nq_{ij}=1,即 \mathbf{e}^TQ=\mathbf{e}^T。另外,由 (a_1,\ldots,a_n)\prec(b_1,\ldots,b_n) 可推論 \min_{1\le i\le n}a_i\ge\min_{1\le i\le n}b_i,所以 q_{ij}\ge 0,證得 Q 是一雙隨機矩陣。

(\Leftarrow):設 Q 為雙隨機矩陣,\mathbf{x}=Q\mathbf{y},且 \mathbf{x}\mathbf{y} 按遞減排序。(若此情況不成立,可將 Q 替換為 P^{-1}_1QP_2\mathbf{x} 替換為 P_1\mathbf{x}\mathbf{y} 替換為 P_2\mathbf{y}P_1P_2 是排列矩陣。)因為 x_i=\sum_{j=1}^nq_{ij}y_j,就有

\begin{aligned} \displaystyle\sum_{i=1}^kx_i&=\sum_{i=1}^k\left(\sum_{j=1}^nq_{ij}y_j\right)\\ &=\sum_{j=1}^n\left(\sum_{i=1}^kq_{ij}\right)y_j=\sum_{j=1}^nt_jy_j\end{aligned}

上式中 0\le t_j=\sum_{i=1}^kq_{ij}\le 1,因此

\displaystyle\sum_{j=1}^nt_{j}=\sum_{j=1}^n\sum_{i=1}^kq_{ij}=\sum_{i=1}^k\sum_{j=1}^nq_{ij}=k

將此結果代入下式計算,可得

\begin{aligned} \displaystyle\sum_{i=1}^kx_i-\sum_{i=1}^ky_i&=\sum_{j=1}^nt_jy_j-\sum_{i=1}^ky_i+y_k\left(k-\sum_{j=1}^nt_j\right)\\  &=\sum_{j=1}^k(y_j-y_k)(t_j-1)+\sum_{j=k+1}^nt_j(y_j-y_k)\le 0\end{aligned}

不等式成立的原因是 \{y_j\} 為遞減數列,且 0\le t_j\le 1。還有

\displaystyle\sum_{i=1}^nx_i=\mathbf{e}^T\mathbf{x}=\mathbf{e}^TQ\mathbf{y}=\mathbf{e}^T\mathbf{y}=\sum_{i=1}^ny_i

因此證明 \mathbf{x}=Q\mathbf{y}\prec\mathbf{y}

 
給定一雙隨機矩陣 Q,不僅 \mathbf{y} 優超 Q\mathbf{y},對於任意優超關係 \mathbf{x}\prec\mathbf{y},也存在一雙隨機矩陣 Q 使得 \mathbf{x}=Q\mathbf{y},換句話說,優超與雙隨機矩陣是等價的,見以下定理。

 
定理二 優超與雙隨機矩陣的等價關係

\mathbf{x}\mathbf{y} 為兩個 n 維實向量,若存在一雙隨機矩陣 Q 使得 \mathbf{x}=Q\mathbf{y},則 \mathbf{x}\prec\mathbf{y};反之亦然。

 
(\Rightarrow):設 Q 為一雙隨機矩陣,\mathbf{x}=Q\mathbf{y},根據定理一,就有 Q\mathbf{y}\prec\mathbf{y},所以 \mathbf{x}\prec\mathbf{y}

 
反向證明比較麻煩,假設 \mathbf{x}\prec\mathbf{y},我們需要一個將 \mathbf{y} 變換為 \mathbf{x} 的運算程序。令

T=\alpha I+(1-\alpha)P

其中 0\le\alpha\le 1P 是對調兩行(列)指標 jk 的基本排列矩陣(見“矩陣視覺化”),很容易驗證 T 也是雙隨機矩陣,這個工作留給讀者完成。考慮

\mathbf{z}=T\mathbf{y}=(\alpha I+(1-\alpha)P)\mathbf{y}=\alpha\mathbf{y}+(1-\alpha)P\mathbf{y}

展開上式,比較等號兩邊各元,得知 z_i=y_i,若 i\neq ji\neq k,而

\begin{aligned} z_j&=\alpha y_j+(1-\alpha)y_k\\ z_k&=\alpha y_k+(1-\alpha)y_j\end{aligned}

 
接著說明如何透過 T 變換逐步將 \mathbf{y} 化為 \mathbf{x},並證明中間產物 \mathbf{z} 仍保有優超關係,即 \mathbf{x}\prec\mathbf{z}\prec\mathbf{y}。假設 x_\ge\cdots\ge x_ny_1\ge\cdots\ge y_n。先以逆向次序 i=n,n-1,\ldots,1 搜尋滿足 x_i<y_i 的第一個指標,設該指標為 j,再依順向次序 i=j+1,j+2,\ldots,n 搜尋滿足 x_i>y_i 的第一個指標,設該指標為 kk>j,就有

y_j>x_j\ge x_k>y_k

\delta=\min\{y_j-x_j,x_k-y_k\}1-\alpha=\frac{\delta}{y_j-y_k},將 \alpha 代入計算 \mathbf{z}=T\mathbf{y},得到

\begin{aligned} z_j&=\displaystyle\left(1-\frac{\delta}{y_j-y_k}\right)y_j+\frac{\delta}{y_j-y_k}y_k=y_j-\delta\\  z_k&=\left(1-\frac{\delta}{y_j-y_k}\right)y_k+\frac{\delta}{y_j-y_k}y_j=y_k+\delta\end{aligned}

除了 j,k 元不同,其餘 z_i=y_i。因為 z_j<y_jz_k>y_k,直接比較 \mathbf{z}\mathbf{y},可確認 \mathbf{z}\prec\mathbf{y}。接下來,我們研究 \mathbf{x}\mathbf{z} 的大小關係。若 \delta=y_j-x_j,即 y_j-x_j\le x_k-y_k,則

\begin{aligned} z_j&=y_j-(y_j-x_j)=x_j\\  z_k&=y_k+(y_j-x_j)\le y_k+(x_k-y_k)=x_k\end{aligned}

\delta=x_k-y_k,即 x_k-y_k\le y_j-x_j,則

\begin{aligned} z_j&=y_j-(x_k-y_k)\ge y_j-(y_j-x_j)=x_j\\  z_k&=y_k+(x_k-y_k)=x_k\end{aligned}

由以上結果可知 z_j\ge x_jz_k\le x_k。欲證明 \mathbf{x}\prec\mathbf{z},區分四種情況討論:

(1) 若 p=1,\ldots,j-1,k,\ldots,n-1z_p=y_p

\displaystyle\sum_{i=1}^{p}z_i=\sum_{i=1}^{p}y_i\ge\sum_{i=1}^{p}x_i

(2) 若 p=j,因為 z_j\ge x_j,利用 (1),

\displaystyle\sum_{i=1}^{j}z_i=\sum_{i=1}^{j-1}z_i+z_j\ge\sum_{i=1}^{j-1}x_i+x_j=\sum_{i=1}^{j}x_i

(3) 若 p=j+1,\ldots,k-1z_p=y_py_p\ge x_p(因為 k>j 是第一個滿足 x_k>y_k 的指標),利用 (2),

\displaystyle\sum_{i=1}^pz_i=\sum_{i=1}^{j}z_i+\sum_{i=j+1}^py_i\ge\sum_{i=1}^{j}x_i+\sum_{i=j+1}^px_i=\sum_{i=1}^px_i

(4) 若 p=n

\displaystyle\sum_{i=1}^nz_i=\sum_{i=1}^ny_i=\sum_{i=1}^nx_i

因此證得 \mathbf{x}\prec\mathbf{z}

 
上例中,令 \mathbf{x}=(4,3,3)\mathbf{y}=(5,4,1)。比較兩數列, x_2<y_2,故 j=2,且 x_3>y_3,故 k=3。令 \delta=\min\{4-3,3-1\}=1,所以 1-\alpha=\frac{1}{4-1}=\frac{1}{3},立得

T\displaystyle =\left(1-\frac{1}{3}\right)\begin{bmatrix}  1&0&0\\  0&1&0\\  0&0&1  \end{bmatrix}+\frac{1}{3}\begin{bmatrix}  1&0&0\\  0&0&1\\  0&1&0  \end{bmatrix}=\begin{bmatrix}  1&0&0\\  0&\frac{2}{3}&\frac{1}{3}\\[0.3em]  0&\frac{1}{3}&\frac{2}{3}  \end{bmatrix}

向量 \mathbf{y}T 變換結果為

\mathbf{z}=T\mathbf{y}=\begin{bmatrix}  5\\  3\\  2  \end{bmatrix}

顯然,(4,3,3)\prec(5,3,2)\prec(5,4,1)。令 d(\mathbf{x},\mathbf{y}) 代表遞減排序的兩數列非零差額 x_i-y_i 總數,此例中,d(\mathbf{x},\mathbf{y})=3,而 d(\mathbf{x},\mathbf{z})=2,故知 T 變換具有減少兩數列相異個數的效果。再對 \mathbf{x}\prec\mathbf{z} 執行一次 T 變換即得 \mathbf{x}=T\mathbf{z},這個工作留給讀者自行確認。

 
準備就緒,利用 T 變換提供的計算程序即可證明定理二的反向陳述。

(\Leftarrow):設 \mathbf{x}\prec\mathbf{y},對向量 \mathbf{y} 執行有限次數的 T 變換,得到

T_m\cdots T_1\mathbf{y}=Q\mathbf{y}=\mathbf{x}

因為 T_1,\ldots,T_m 全是雙隨機矩陣,雙隨機矩陣乘積亦為雙隨機矩陣,所以存在一雙隨機矩陣 Q 使得 Q\mathbf{y}=\mathbf{x}

 
最後,回到 Schur 推得的中間結果,雙隨機矩陣 Q 滿足

\begin{bmatrix}  a_{11}\\  \vdots\\  a_{nn}  \end{bmatrix}=Q\begin{bmatrix}  \lambda_1\\  \vdots\\  \lambda_n  \end{bmatrix}

利用定理二的雙隨機矩陣和優超等價性質,即證得

(a_{11},\ldots,a_{nn})\prec(\lambda_1,\ldots,\lambda_n)

 
總結本文的討論。我們從探討 Hermitian 矩陣的特徵值和主對角元之間的關係出發,透過觀察提出猜想,接著定義優超關係,並於嘗試證明的過程中「意外」發現優超和雙隨機矩陣具有等價關係。這個發現不僅解決了原始問題,也為矩陣特徵值、奇異值和主對角元的相關不等式探索提供了一個全新的分析處理工具。

 
本文參考:
[1] Albert W. Marshall and Ingram Olkin, Inequalities: Theory of Majorization and its Applications, Academic Press, 1979.
[2] Barry C. Arnold, Majorization: Here, There and Everywhere.

廣告
本篇發表於 線性代數專欄, 二次型 並標籤為 , , , 。將永久鏈結加入書籤。

3 Responses to 優超關係與雙隨機矩陣

  1. Liang Dai 說道:

    谢谢周老师!
    只是觉得优超关系对应于双随机矩阵是多么优美的结论,却需要那么一个\dirty\的证明,实在是让人不爽。

  2. ccjou 說道:

    你是說定理一還是定理二的證明dirty?或兩個都是?這兩個證明取自 Marshall 與 Olkin 的書,我只是加入一些補充說明。動筆之前我曾想過是否能避開使用大量的 \sum,問題在於 majorization 的定義本身就是這樣子,又想過或許能用矩陣運算表達,例如,
    L\mathbf{x}=\begin{bmatrix} 1&0&0\\ 1&1&0\\ 1&1&1 \end{bmatrix}\begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix}=\begin{bmatrix} x_1\\ x_1+x_2\\ x_1+x_2+x_3 \end{bmatrix}
    \mathbf{x}\prec\mathbf{y}L\mathbf{x}\le L\mathbf{y} 同義。最後不了了之,沒有下文,但我相信應該還有更簡潔優美的證明。

  3. Liang Dai 說道:

    周老师,我是说定理二的证明。您的思路跟我不谋而合,我也想那样尝试下。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s