特殊矩陣 (17)：組合矩陣

Posted on 12/21/2012 by ccjou

本文的閱讀等級：初級

組合矩陣 (combinatorial matrix)^[1] $A=[a_{ij}]$ 是具有下列形式的 $n\times n$ 階矩陣：

$A=\begin{bmatrix} x+y&y&\cdots&y\\ y&x+y&\cdots&y\\ \vdots&\vdots&\ddots&\vdots\\ y&y&\cdots&x+y \end{bmatrix}$ ，

也就是說， $a_{ij}=\delta_{ij}x+y$ ，其中 $\delta_{ij}$ 是 Kronecker 函數： $\delta_{ij}=1$ 若 $i=j$ ， $\delta_{ij}=0$ 若 $i\neq j$ 。令 $J$ 代表所有元皆為 $1$ 的 $n\times n$ 階矩陣，組合矩陣亦可表示成 $A=xI+yJ$ 。以下設 $x,y$ 為實數，本文討論組合矩陣 $A$ 的行列式、逆矩陣，以及特徵值和特徵向量。

行列式

從第 $2,\ldots,n$ 行減去第 $1$ 行，再將第 $2,\ldots,n$ 列加進第 $1$ 列，可得下三角型態行列式：

$\det A=\begin{vmatrix} x+y&y&\cdots&y\\ y&x+y&\cdots&y\\ \vdots&\vdots&\ddots&\vdots\\ y&y&\cdots&x+y \end{vmatrix}=\begin{vmatrix} x+y&-x&\cdots&-x\\ y&x&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ y&0&\cdots&x \end{vmatrix}=\begin{vmatrix} x+ny&0&\cdots&0\\ y&x&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ y&0&\cdots&x \end{vmatrix}$ 。

所以， $\det A=x^{n-1}(x+ny)$ 。下面再介紹另一個作法。令 $n$ 維向量 $\mathbf{e}=(1,1,\ldots,1)^T$ ，則 $J=\mathbf{e}\mathbf{e}^T$ 。使用矩陣行列式引理 (見“矩陣和之行列式 (上)”)，可得

$\displaystyle\begin{aligned} \det A&=\det(xI+yJ)=\det\left(xI+(y\mathbf{e})\mathbf{e}^T\right)\\ &=\det\left(1+\mathbf{e}^T(xI)^{-1}(y\mathbf{e})\right)\det(xI)\\ &=\left(1+\frac{y}{x}\mathbf{e}^T\mathbf{e}\right)x^n=\left(1+\frac{ny}{x}\right)x^n\\ &=x^{n-1}(x+ny).\end{aligned}$

逆矩陣

因為 $J^2=nJ$ ，可知

$\begin{aligned} (cI+dJ)(xI+yJ)&=cxI+(cy+dx)J+dyJ^2\\ &=cxI+(cy+dx+ndy)J.\end{aligned}$

設 $cx=1$ 和 $cy+dx+ndy=0$ ，則 $c=1/x$ ， $d=-y/x(x+ny)$ 。對於 $n\ge 2$ ，若 $x(x+ny)\neq 0$ ，則組合矩陣 $A$ 可逆， $A^{-1}$ 亦為組合矩陣：

$\displaystyle A^{-1}=\frac{1}{x}I-\frac{y}{x(x+ny)}J$ ，

即 $(A^{-1})_{ij}=(-y+\delta_{ij}(x+ny))/x(x+ny)$ 。另外，我們也可以使用 Sherman-Morrison 公式計算 $A=xI+y\mathbf{e}\mathbf{e}^T$ 的逆矩陣 (見“Sherman-Morrison-Woodbury 公式”)，如下：

$\begin{aligned}\displaystyle A^{-1}&=\left(xI+(y\mathbf{e})\mathbf{e}^T\right)^{-1}\\ &=(xI)^{-1}-\frac{(xI)^{-1}(y\mathbf{e})\mathbf{e}^T(xI)^{-1}}{1+\mathbf{e}^T(xI)^{-1}(y\mathbf{e})}\\ &=\frac{1}{x}I-\frac{y/x^2}{1+ny/x}J\\ &=\frac{1}{x}I-\frac{y}{x(x+ny)}J.\end{aligned}$

伴隨矩陣

寫出恆等式

$A(\hbox{adj}\,A)=(\det A)I$ ，

或 $\hbox{adj}\,A=(\det A)A^{-1}$ 。代入 $\det A=x^{n-1}(x+ny)$ 和 $A^{-1}=(1/x)I-y(x(x+ny))^{-1}J$ ，可得

$\hbox{adj}\,A=x^{n-2}(x+ny)I-x^{n-2}yJ$ 。

特徵值和特徵向量

因為 $x$ 和 $y$ 是實數，組合矩陣是實對稱矩陣。我們使用探索法來解特徵值和特徵向量 (見“實對稱矩陣特徵值和特徵向量的探索解法”)。考慮組合矩陣表達式 $A=xI+y\mathbf{e}\mathbf{e}^T$ ，立得

$A\mathbf{e}=(xI+y\mathbf{e}\mathbf{e}^T)\mathbf{e}=x\mathbf{e}+y\mathbf{e}\left(\mathbf{e}^T\mathbf{e}\right)=(x+ny)\mathbf{e}$ ，

即知 $A$ 有一特徵值 $x+ny$ ，對應特徵向量 $\mathbf{e}$ 。因為實對稱矩陣 $A$ 有完整的單範正交 (orthonormal) 特徵向量集，設 $\{\mathbf{u}_1,\ldots,\mathbf{u}_{n-1}\}$ 為正交補餘 $\mathrm{span}\{\mathbf{e}\}^{\perp}$ 的一組基底，即有 $\mathbf{e}^T\mathbf{u}_i=0$ ， $i=1,\ldots,n-1$ 。利用此性質，可得

$A\mathbf{u}_i=(xI+y\mathbf{e}\mathbf{e}^T)\mathbf{u}_i=x\mathbf{u}_i+y\mathbf{e}\left(\mathbf{e}^T\mathbf{u}_i\right)=x\mathbf{u}_i,~~i=1,\ldots,n-1$ 。

上式指出 $A$ 有 $n-1$ 個特徵值 $x$ ，對應特徵向量 $\mathbf{u}_1,\ldots,\mathbf{u}_{n-1}$ ；或者換個說法，特徵值 $x$ 的代數重數等於 $n-1$ ，對應的特徵空間是 $\mathrm{span}\{\mathbf{e}\}^{\perp}$ 。因為行列式等於特徵值之積，由此並可驗證 $\det A=x^{n-1}(x+ny)$ 。

參考來源：
[1] Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 2nd edition, 1973, pp 36.

This entry was posted in 特殊矩陣, 線性代數專欄 and tagged 特徵值, 特徵向量, 特殊矩陣, 組合矩陣, 逆矩陣, 行列式. Bookmark the permalink.

7 Responses to 特殊矩陣 (17)：組合矩陣

陳威丞 says:

01/29/2013 at 12:17 am

老師您好，這幾天煩惱於一個統計學上carl pearson 統計量的證明，好不容易網路上找到資料了，確卡在最後一個地方看不懂，可以麻煩老師幫我看一下下面這一篇文章中證明那一部份的最後一段空間變換的地方到底是在表達什麼，我完全理不出頭緒!
文章在google查詢打:proof of chi-squared statistics
搜尋結果的第一項,篇名為:section10 chi-squared goodness of fit test

Reply
- ccjou says:
  
  01/29/2013 at 8:42 am
  
  這是連結：
  
  Click to access lecture11.pdf
  
  但不確定你說的空間變換是哪一部分？麻煩你指出頁號還有你的疑問。
  
  這裡面使用的方法類似下文：
  https://ccjou.wordpress.com/2012/05/23/%E6%A8%A3%E6%9C%AC%E5%B9%B3%E5%9D%87%E6%95%B8%E3%80%81%E8%AE%8A%E7%95%B0%E6%95%B8%E5%92%8C%E5%85%B1%E8%AE%8A%E7%95%B0%E6%95%B8/
  
  Reply
陳威丞 says:

01/29/2013 at 9:43 am

頁碼是在66-67
疑問的部分是~~
座標系統中的P1,P2,P3代表的是什麼意思，因為文中的式子只有出現一個P
以及文中的V矩陣也不清楚它的意義所以也就不知道文中所提到的為什麼V*g中的每一個元素互相為iid standard normal

Reply
- ccjou says:
  
  01/29/2013 at 10:55 am
  
  從頁66第二式開始，令 $\mathbf{v}_1=(\mathbf{g}\cdot\mathbf{p})\mathbf{p}$ ， $\mathbf{v}_2=\mathbf{g}-\mathbf{v}_1$ ，我們要計算向量長度平方 $\Vert \mathbf{v}_2\Vert^2$ 。我將文章的粗體大寫改成粗體小寫。這裡 $\mathbf{g}=(g_1,\ldots,g_r)^T$ 是參考標準基底 $\{\mathbf{e}_1,\ldots,\mathbf{e}_r\}$ 的座標向量，即有 $\mathbf{g}=g_1\mathbf{e}_1+\cdots+g_r\mathbf{e}_r$ 。因為 $\Vert\mathbf{p}\Vert=1$ ， $\mathbf{v}_1=(\mathbf{g}\cdot\mathbf{p})\mathbf{p}$ 代表 $\mathbf{g}$ 至單位長向量 $\mathbf{p}$ 的指向軸的正交投影，見
  https://ccjou.wordpress.com/2010/04/19/%E6%AD%A3%E4%BA%A4%E6%8A%95%E5%BD%B1-%E5%A8%81%E5%8A%9B%E5%BC%B7%E5%A4%A7%E7%9A%84%E4%BB%A3%E6%95%B8%E5%B7%A5%E5%85%B7/
  因此 $\mathbf{v}_2$ 就是 $\mathbf{g}$ 扣除正交投影後的「殘餘量」，說明 $\mathbf{v}_2$ 正交於 $\mathbf{p}$ ，也可以說 $\mathbf{v}_2$ 屬於子空間 $\mathrm{span}\{\mathbf{p}\}$ 的「正交補集」(即所有與 $\mathbf{p}$ 垂直的向量形成的集合)，記為 $\mathrm{span}\{\mathbf{p}\}^{\perp}$ ，見 Figure 10.2。
  
  等一下繼續……
  
  接下來我們在正交補集 $\mathrm{span}\{\mathbf{p}\}^{\perp}$ 中建立一組標準正交 (orthonormal) 基底。因為 $\dim\mathrm{span}\{\mathbf{p}\}^{\perp}=r-1$ ，總共有 $r-1$ 個基底向量 $\{\mathbf{p}_2,\ldots,\mathbf{p}_r\}$ ，其中 $\mathbf{p}_i\cdot\mathbf{p}_j=1$ 若 $i=j$ ，否則 $\mathbf{p}_i\cdot\mathbf{p}_j=0$ 。顯然 $\{\mathbf{p},\mathbf{p}_2,\ldots,\mathbf{p}_r\}$ 構成 $\mathbb{R}^r$ 的一組標準正交基底。所以 $\mathbf{g}$ 可唯一表示成
  $\mathbf{g}=g'_1\mathbf{p}+g'_2\mathbf{p}_2+\cdots+g'_r\mathbf{p}_r=\begin{bmatrix} \mathbf{p}&\mathbf{p}_2&\cdots&\mathbf{p}_r \end{bmatrix}\begin{bmatrix} g'_1\\ g'_2\\ \vdots\\ g'_r \end{bmatrix}=V\mathbf{g}'$ 。
  參照頁66最底下，怎麼剛好相反？因為作者(不是我，是他)寫錯了。這裡 $V$ 稱為正交矩陣 (orthogonal matrix)， $V^TV=VV^T=I$ ，你可以將它想成「座標系統旋轉」，標準基底向量 $\mathbf{e}_1$ 轉至 $\mathbf{p}$ ，其他各軸轉至 $\mathbf{p}_2,\ldots,\mathbf{p}_r$ 。但 $\mathbf{g}$ 維持不動，所以它的座標就變成 $\mathbf{g}'=(g'_1,g'_2,\ldots,g'_r)=V^T\mathbf{g}$ 。座標系統旋轉不改變座標向量長度，以及二向量之間的夾角，當然也不會改變分布的本質 (iid 標準常態等)，見
  https://ccjou.wordpress.com/2013/01/11/%E5%85%B1%E8%AE%8A%E7%95%B0%E6%95%B8%E7%9F%A9%E9%99%A3%E8%88%87%E5%B8%B8%E6%85%8B%E5%88%86%E4%BD%88/
  
  剩下的工作很簡單。使用 $\mathbf{g}$ 參考新基底的表達式，計算 $\mathbf{v}_1=(\mathbf{g}\cdot\mathbf{p})\mathbf{p}=g'_1\mathbf{p}$ ，則 $\mathbf{v}_2=\mathbf{g}-\mathbf{v}_1=g'_2\mathbf{p}_2+\cdots+g'_r\mathbf{p}_r$ ，所以 $\Vert\mathbf{v}_2\Vert^2=(g'_2\mathbf{p}_2+\cdots+g'_r\mathbf{p}_r)\cdot(g'_2\mathbf{p}_2+\cdots+g'_r\mathbf{p}_r)=(g'_2)^2+\cdots+(g'_r)^2$ 。
  
  Reply
ccjou says:

01/30/2013 at 4:11 pm

本來想寫一篇從線性代數觀點介紹「卡方檢定」，因為事情多，等過完年開學時再說了。這裡我提供一個簡單的解釋：為甚麼 $\displaystyle \sum_{j=1}^r\frac{(\nu_j-np_j)^2}{np_j}$ 趨於 $\chi^2_{r-1}$ 分配？僅解釋自由度這部分。令 $Z_j=\displaystyle\frac{\nu_j-np_j}{\sqrt{np_j}}$ ，上面那篇 MIT OCW 的文章已經證明當 $n$ 增大時， $Z_j\sim N(0,1-p_j)$ 。我們的問題是確定 $S=Z_1^2+\cdots+Z_r^2$ 的分配。利用 $p_1+\cdots+p_r=1$ ，可知 $\nu_1+\cdots+\nu_r=n$ 等價於 $\sqrt{p_1}Z_1+\cdots+\sqrt{p_r}Z_r=0$ 。換句話說，向量 $(Z_1,\ldots,Z_r)^T$ 正交於 $(\sqrt{p_1},\ldots,\sqrt{p_r})^T$ ，這表示 $(Z_1,\ldots,Z_r)^T$ 屬於法向量是 $(\sqrt{p_1},\ldots,\sqrt{p_r})^T$ 的超平面，這個子空間的維度等於 $r-1$ ，也就是統計學說的自由度為 $r-1$ 。

Reply
陳威丞 says:

02/02/2013 at 9:01 am

感謝老師的解釋，讓我有一點頭緒，我想我對於線性代書的一些較高維度的定理還不是非常地熟悉~~所以在面對一些多變數的證明會比較沒有概念~往後我想時間多一點的時候先去多讀一些線代的基本觀念應該會比較來的有效率一些~~~

Reply
- ccjou says:
  
  02/02/2013 at 11:34 am
  
  ＜統計，改變了世界＞有這一段話：「自由度的新觀念是費雪發現的，這與他特有的幾何洞察力，以及他把數學問題轉化成多維空間幾何的能力有直接關係。」這裡多維空間幾何指的就是線性代數。
  
  Reply

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