費雪不等式

本文的閱讀等級：中級

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

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

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

Ronald Fisher (1890-1962) From http://upload.wikimedia.org/wikipedia/commons/4/46/R._A._Fischer.jpg

為了替線性代數開路，定義 $m\times n$ 階關聯矩陣^[2] (incidence matrix) $A=[ij]$ 為一 (0,1) 矩陣，其中 $a_{ij}=1$ 若 $j\in C_i$ ， $a_{ij}=0$ 若 $j\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_i$ 和 $C_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\vert$ ， $i=1,\ldots,m$ 。明顯地， $p_i>0$ 且 $p_i\ge\lambda$ ， $1\le i\le m$ 。分開兩種情況討論。若存在 $i$ 使得 $p_i=\lambda$ ，這意味所有 $C_j$ 包含 $C_i$ ，且 $C_j\setminus C_i$ ， $j\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>\lambda$ ， $i=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$ 表示所有元皆為 $1$ 的 $m\times m$ 階矩陣，即 $J=\mathbf{e}\mathbf{e}^T$ ，這裡 $\mathbf{e}$ 是所有元為 $1$ 的 $m$ 維向量。注意，實矩陣 $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}_i$ ， $i=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] 本文所稱的關聯矩陣並非圖論中的關聯矩陣，詳見“線性代數在圖論的應用 (二)：關聯矩陣”。

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

費雪不等式

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱

閱讀導引

學習資源

專題探究

急救查詢

其他分頁

Meta

網路狀態

Blog Stats

費雪不等式

Share this:

Like this:

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱