費雪不等式

本文的閱讀等級:中級

英國統計學家、演化生物學家與遺傳學家費雪 (Ronald Fisher) 是現代統計學的創建者之一。今天我們使用的許多統計方法,例如,變異數分析 (方差分析,簡稱ANOVA)、最大似然估計與費雪線性判別等,都是他的發明貢獻。本文要探討的主題是在實驗設計時碰到的一個組合數學問題。考慮包含 n 個元素的集合 \Psi=\{1,2,\ldots,n\}。令 C_1,\ldots,C_m\Psim 個相異非空子集合。令 \vert S\vert 代表一集合 S 的基數 (cardinal number),即所包含的元素個數。

費雪不等式:若所有的 i\neq j 滿足 \vert C_i\cap C_j\vert =\lambda,則 m\le n

費雪的原始論文以組合數學解釋[1],本文討論多種線性代數證法,使用的基本工具包括矩陣秩、行列式、特徵值、線性獨立與正定 (類似應用見“有限體與模算術”)。

 
為了替線性代數開路,定義 m\times n 階關聯矩陣[2] (incidence matrix) A=[ij] 為一 (0,1) 矩陣,其中 a_{ij}=1j\in C_ia_{ij}=0j\notin C_i。例如,n=6

\displaystyle C_1=\{1,2,3,4\},~~C_2=\{2,4,5\},~~C_3=\{3,4,5\},~~C_4=\{2,3,5,6\}

關聯矩陣為

\displaystyle A=\begin{bmatrix} 1&1&1&1&0&0\\ 0&1&0&1&1&0\\ 0&0&1&1&1&0\\ 0&1&1&0&1&1 \end{bmatrix}

其中每一列所有元的和表示子集合的元素數,任兩列的內積表示兩子集合的共同元素數。這個事實引領我們考慮 m\times m 階交互乘積 AA^T,其中 (i,j)

\displaystyle  (AA^T)_{ij}=\sum_{k=1}^na_{ik}a_{jk}

表示 C_iC_j 的共同元素數,即 \vert C_i\cap C_j\vert。上例中,

\displaystyle  AA^T=\begin{bmatrix} 4&2&2&2\\ 2&3&2&2\\ 2&2&3&2\\ 2&2&2&4 \end{bmatrix}

 
假定所有的 i\neq j 滿足 \vert C_i\cap C_j\vert=\lambda。令 p_i=\vert C_i\verti=1,\ldots,m。明顯地,p_i>0p_i\ge\lambda1\le i\le m。分開兩種情況討論。若存在 i 使得 p_i=\lambda,這意味所有 C_j 包含 C_i,且 C_j\setminus C_ij\neq i,為 m-1 個相異非空集合。但 C_i 不為空集合,即有

\displaystyle m-1\le \vert\Psi\setminus C_i\vert=n-\vert C_i\vert\le n-1

故得 m\le n

 
接著我們討論另一個情況:p_i>\lambdai=1,\ldots,m。在此條件下,

\displaystyle  AA^T=\begin{bmatrix} p_1&\lambda&\lambda&\cdots&\lambda\\ \lambda&p_2&\lambda&\cdots&\lambda\\ \lambda&\lambda&p_3&\cdots&\lambda\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ \lambda&\lambda&\lambda&\cdots&p_m \end{bmatrix}=D+\lambda J

其中 D=\hbox{diag}(p_1-\lambda,p_2-\lambda,\ldots,p_m-\lambda)J 表示所有元皆為 1m\times m 階矩陣,即 J=\mathbf{e}\mathbf{e}^T,這裡 \mathbf{e} 是所有元為 1m 維向量。注意,實矩陣 A 滿足 \hbox{rank}(AA^T)=\hbox{rank}A (見“利用 Gramian 矩陣證明行秩等於列秩”)。如果能證明 \hbox{rank}A=m\hbox{rank}(AA^T)=m,也就是說,A 有線性獨立的列向量或 AA^T 是一可逆矩陣,則

\displaystyle   \hbox{rank}(AA^T)=\hbox{rank}A\le n

可推得 m\le n。下面分別介紹一致版與非一致版的證明,並展示線性代數的多樣方法。

 
一致版

所謂一致版是指每一 p_i=p,這時 AA^T 可化簡為

\displaystyle  AA^T=(p-\lambda)I+\lambda J

稱作組合矩陣。下面列舉二個基於組合矩陣性質的證明 (詳見“特殊矩陣 (17):組合矩陣”)。

(1) 行列式:m\times m 階組合矩陣 xI+yJ 的行列式為 \det(xI+yJ)=x^{m-1}(x+my)。套用此公式,

\displaystyle \det (AA^T)=(p-\lambda)^{m-1}\left(p+(m-1)\lambda\right)

因為 p>\lambda\ge 0\det(AA^T)>0,推知 AA^T 是一可逆矩陣。

(2) 特徵值:組合矩陣 xI+yJ 有一特徵值 x+my,以及 m-1 個特徵值 x,可知 AA^T 有一特徵值 p+(m-1)\lambda,以及 m-1 個特徵值 p-\lambda。因為 AA^T 的特徵值皆不為零,故為可逆矩陣。

 
非一致版

所謂非一致版是指 p_i 未必完全相等。下面提供基於行列式、線性獨立與正定的三種證法。

(1) 行列式:套用二矩陣和的行列式公式 (見“矩陣和之行列式 (上)”)

\displaystyle \det(A+\mathbf{u}\mathbf{v}^T)=(1+\mathbf{v}^TA^{-1}\mathbf{u})(\det A)

因為 D=\hbox{diag}(p_1-\lambda,\ldots,p_m-\lambda) 的主對角元都是正數,

\displaystyle\begin{aligned}  \det(AA^T)&=\det\left(D+\lambda\mathbf{e}\mathbf{e}^T\right)\\ &=\left(1+\lambda\mathbf{e}^TD^{-1}\mathbf{e}\right)(\det D)\\ &=\left(1+\lambda\sum_{i=1}^m\frac{1}{p_i-\lambda}\right)\prod_{i=1}^m(p_i-\lambda)>0,\end{aligned}

即知 AA^T 是可逆矩陣。

(2) 線性獨立:令 \mathbf{v}_ii=1,\ldots,m,表示 m\times n 階關聯矩陣 A 的列向量。根據題意,若 i=j,則 \mathbf{v}_i^T\mathbf{v}_j=p_i;若 i\neq j,則 \mathbf{v}_i^T\mathbf{v}_j=\lambda。假設 \{\mathbf{v}_1,\ldots,\mathbf{v}_m\} 為一線性相關集,也就是說,存在不全為零的數組 c_1,\ldots,c_m 使得 c_1\mathbf{v}_1+\cdots+c_m\mathbf{v}_m=\mathbf{0}。使用前述性質,

\displaystyle\begin{aligned}  0&=\left(\sum_{i=1}^mc_i\mathbf{v}_i\right)^T\left(\sum_{j=1}^mc_j\mathbf{v}_j\right)\\ &=\sum_{i=1}^mc_i^2\mathbf{v}_i^T\mathbf{v}_i+\sum_{i\neq j}c_ic_j\mathbf{v}_i^T\mathbf{v}_j\\ &=\sum_{i=1}^mc_i^2p_i+\sum_{i\neq j}c_ic_j\lambda\\ &=\sum_{i=1}^mc_i^2(p_i-\lambda)+\lambda\left(\sum_{i=1}^mc_i\right)^2. \end{aligned}

但每一 p_i>\lambda 迫使第一項必為正數 (第二項不為負數),產生矛盾。故原假設不成立,A 有線性獨立的列向量,即 \hbox{rank}A=m

(3) 正定矩陣:對於任一非零向量 \mathbf{x}=(x_1,\ldots,x_m)^T

\displaystyle\begin{aligned} \mathbf{x}^T(AA^T)\mathbf{x}&=\mathbf{x}^T(D+\lambda J)\mathbf{x}\\ &=\mathbf{x}^T(D+\lambda \mathbf{e}\mathbf{e}^T)\mathbf{x}\\ &=\mathbf{x}^TD\mathbf{x}+\lambda(\mathbf{x}^T\mathbf{e})(\mathbf{e}^T\mathbf{x})\\ &=\sum_{i=1}^m(p_i-\lambda)x_i^2+\lambda\left(\sum_{i=1}^mx_i\right)^2>0. \end{aligned}

上式表明 AA^T 是一正定矩陣,因此可逆 (見“正定矩陣的性質與判別方法”)。

 
註解:
[1] 出自 An examination of the different possible solutions of a problem in incomplete blocks,Annals of Eugenics,1940,頁52-75。費雪的論文並不淺顯易讀。費雪從小體弱多病,而且視力不佳,為了保護他的眼睛,醫生不讓他在人工光源下閱讀。由於不能使用電燈,中學的數學導師會提早在傍晚教他數學,並且完全不使用紙筆或其他視覺輔助教材。費雪因此發展出非常特殊的幾何直覺,在往後的歲月裡,他憑藉非凡的幾何洞察力,解決了許多數理統計的難題。因為這種能力對費雪來說十分明顯自然,以致於他往往無法清楚地解釋自己的想法讓別人明白 (見《統計,改變了世界》,The Lady Tasting Tea,天下文化,2001,頁49-50)。費雪極可能知道上述線性代數證明,不過就像他的大作《研究工作者的統計方法》(Statistical Methods for Research Workers) 一樣,裡面所有的數學公式都沒有推導過程或說明。
[2] 本文所稱的關聯矩陣並非圖論中的關聯矩陣,詳見“線性代數在圖論的應用 (二):關聯矩陣”。

Advertisements
本篇發表於 線性代數專欄, 應用之道 並標籤為 , , , , , , 。將永久鏈結加入書籤。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s