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

本文的閱讀等級:初級

組合矩陣 (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}=1i=j\delta_{ij}=0i\neq j。令 J 代表所有元皆為 1n\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=1cy+dx+ndy=0,則 c=1/xd=-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

 
特徵值和特徵向量

因為 xy 是實數,組合矩陣是實對稱矩陣。我們使用探索法來解特徵值和特徵向量 (見“實對稱矩陣特徵值和特徵向量的探索解法”)。考慮組合矩陣表達式 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=0i=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

上式指出 An-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.

廣告
本篇發表於 特殊矩陣, 線性代數專欄 並標籤為 , , , , , 。將永久鏈結加入書籤。

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

  1. 陳威丞 說道:

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

  2. 陳威丞 說道:

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

  3. ccjou 說道:

    本來想寫一篇從線性代數觀點介紹「卡方檢定」,因為事情多,等過完年開學時再說了。這裡我提供一個簡單的解釋:為甚麼 \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

  4. 陳威丞 說道:

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

    • ccjou 說道:

      <統計,改變了世界>有這一段話:「自由度的新觀念是費雪發現的,這與他特有的幾何洞察力,以及他把數學問題轉化成多維空間幾何的能力有直接關係。」這裡多維空間幾何指的就是線性代數。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s