每週問題 January 5, 2015

這是2008年台大資訊所的碩士班入學試題。

Let \mathbf{u}=(1,-1,-1,1,1)^T. Determine (I+2\mathbf{u}\mathbf{u}^T)(I+\mathbf{u}\mathbf{u}^T)^{-1}\mathbf{u}.

繼續閱讀

張貼在 pow 線性方程與矩陣代數, 每週問題 | 標記 , | 1 則迴響

常態分布與二次型

本文的閱讀等級:中級

服從多變量常態分布 (normal distribution) 的隨機向量 (隨機變數組成的向量) \mathbf{x} 的機率密度函數完全由平均數向量 \boldsymbol{\mu}=E[\mathbf{x}] 和共變異數矩陣 \Sigma=\text{Cov}[\mathbf{x}] 決定,記為 \mathbf{x}\sim\mathcal{N}(\boldsymbol{\mu},\Sigma)。若 \mathbf{z}=(z_1,\ldots,z_p)\sim\mathcal{N}(\mathbf{0},I),我們說隨機向量 \mathbf{z} 服從標準化多變量常態分布,其中隨機變數 z_1,\ldots,z_p\sim\mathcal{N}(0,1) 相互獨立。本文討論具多變量常態分布的隨機向量所構成的二次型 \mathbf{x}^TA\mathbf{x},其中 A 是實對稱矩陣,並引介一個重要的統計分布──卡方分布 (chi-squared distribution)。本文的預備知識包括 (見“多變量常態分布”):

  • 期望值 E[\cdot] 是線性算子,共變異數矩陣 \Sigma 是半正定 (對稱) 矩陣。
  • 服從常態分布的隨機向量的仿射變換 (affine transformation) 也為常態分布。令 \mathbf{x} 為一 p 維隨機向量,且 \mathbf{x}\sim\mathcal{N}(\boldsymbol{\mu},\Sigma)。若 \mathbf{y}=A\mathbf{x}+\mathbf{b},其中 Am\times p 階常數矩陣,\mathbf{b}m 維常數向量,則 \mathbf{y}\sim\mathcal{N}(A\boldsymbol{\mu}+\mathbf{b},A\Sigma A^T),即 E[\mathbf{y}]=A\boldsymbol{\mu}+\mathbf{b}\text{Cov}[\mathbf{y}]=A\Sigma A^T
  • \mathbf{x}\mathbf{y} 為二個隨機向量 (維數可不同)。若交互 (cross) 共變異數矩陣 \text{Cov}[\mathbf{x},\mathbf{y}]=E\left[(\mathbf{x}-E[\mathbf{x}])(\mathbf{y}-E[\mathbf{y}])^T\right]=0,則 \mathbf{x}\mathbf{y} 是獨立的隨機向量,反之亦然。

繼續閱讀

張貼在 特別主題, 主題專欄 | 標記 , , , , , | 2 則迴響

每週問題 December 29, 2014

這是最小平方法應用於矩陣之線性變換的問題。

Let \mathbb{R}^{2\times 2} be the vector space formed by 2\times 2 real matrices. Let A=\begin{bmatrix}  1&2\\  0&1  \end{bmatrix} and B=\begin{bmatrix}  0&1\\  1&1  \end{bmatrix}. Consider the following transformation from \mathbb{R}^{2\times 2} to \mathbb{R}^{2\times 2}:

\displaystyle  T(X)=XA-AX.

Determine a matrix \hat{X} that minimizes \Vert T(\hat{X})-B\Vert_F, where \Vert\cdot\Vert_F denotes Frobenius norm.

繼續閱讀

張貼在 pow 內積空間, 每週問題 | 標記 | 發表留言

答William──關於凸包的映射問題

網友William留言:

老師,您好!我不是您的學生,但是又有一個問題苦無解決辦法,因此想向老師尋求協助。問題是這樣的:群組A內有 A_i(x_i,y_i)1\le i\le 5,五個點。其中 A_1A_2A_3A_4 為一矩形的四個端點,而 A_5 位於矩形的範圍內或邊線上。群組B內有 B_i(\hat{x}_i,\hat{y}_i)1\le i\le 5,五個點。現在假設存在一張對應表:A_i(x_i,y_i) 查表後的值為 B_i(\hat{x}_i,\hat{y}_i)1\le i\le 4,求 A_5(x_5,y_5) 查表後的值 B_5(\hat{x}_5,\hat{y}_5),並以 (x_i,y_i)1\le i\le 5,和 (\hat{x}_j,\hat{y}_j)1\le j\le 4,表示。我不知道這個問題是否適合由線性代數解決,也不曉得應該從哪裡下手。懇請老師提供意見。謝謝。

繼續閱讀

張貼在 答讀者問, 線性變換 | 標記 , , , , | 發表留言

每週問題 December 22, 2014

這是 Hermitian 矩陣的界定性質的證明問題。

Let A be an n\times n matrix. Show that if \mathbf{x}^\ast A\mathbf{x} is real for every \mathbf{x}\in\mathbb{C}^n, then A^\ast=A.

繼續閱讀

張貼在 pow 二次型, 每週問題 | 標記 , | 發表留言

Cesàro 矩陣序列

本文的閱讀等級:高級

給定一數列 \{a_k\}_{1}^\infty,Cesàro 數列定義為 \{\mu_k\}_{1}^\infty,其中 \mu_k\{a_1, a_2,\ldots\} 的前 k 項的平均數,如下:

\displaystyle  \mu_k=\frac{a_1+\cdots+a_k}{k},~~k\ge 1

Cesàro 數列因義大利數學家切薩羅 (Ernesto Cesàro) 而得名。若 \lim_{k\to\infty}\mu_k=\alpha,我們說數列 \{a_k\} 是可累加的 (summable),\alpha 稱為 Cesàro 極限。若數列 \{a_k\} 收斂至 \alpha,則對應的 Cesàro 數列 \{\mu_k\} 也收斂至 \alpha (證明見附註[1])。收斂性蘊含可累加性,但可累加性未必有收斂性。例如,震盪數列 \{0,1,0,1,\ldots\} 不收斂,但對應的 Cesàro 數列收斂至 1/2。Cesàro 數列可以推廣至矩陣序列。令 A 為一 n\times n 階矩陣。若 \lim_{k\to\infty}(I+A+A^2+\cdots+A^{k-1})/k 存在,則稱 A 為可累加矩陣。(如果不取平均,\sum_{k=0}^\infty A^k 稱為 Neumann 無窮級數[2]。) 若 \lim_{k\to\infty}A^k=0,我們稱 A 為收斂矩陣;若 \lim_{k\to\infty}A^k 存在 (但未必是零矩陣),則稱為廣義收斂矩陣。類似純量序列,廣義收斂矩陣蘊含可累加矩陣[3]:若 \lim_{k\to\infty}A^k 存在,則 \lim_{k\to\infty}(I+A+A^2+\cdots+A^{k-1})/k 存在,但反向命題不成立。本文探討下面二個問題:在一般情況下,即 A 未必是廣義收斂矩陣,可累加矩陣 A 的充分與必要條件是甚麼?Cesàro 矩陣序列收斂至何矩陣 (Cesàro 極限)?

繼續閱讀

張貼在 數值線性代數, 主題專欄 | 標記 , , , , , , | 發表留言

每週問題 December 15, 2014

這是實對稱矩陣的二次型極值問題。

Let A be an n\times n Hermitian matrix. Let \lambda_{\min}(A) and \lambda_{\max}(A) be the smallest and largest eigenvalues of A, respectively. For every unit vector \mathbf{x}\in\mathbb{C}^n, show that

\displaystyle  \lambda_{\min}(A)\le\mathbf{x}^\ast A\mathbf{x}\le\lambda_{\max}(A).

繼續閱讀

張貼在 pow 二次型, 每週問題 | 標記 , | 發表留言

每週問題 December 8, 2014

The Leslie matrix is of the form

\displaystyle    L=\begin{bmatrix}    a_1&a_2&a_3&\cdots&a_{n-1}&a_n\\    b_1&0&0&\cdots&0&0\\  0&b_2&0&\cdots&0&0\\  \vdots&\vdots&\vdots&&\vdots&\vdots\\  0&0&0&\cdots&b_{n-1}&0    \end{bmatrix}.

Show that the characteristic polynomial of L is

\displaystyle    p(\lambda)=\det(\lambda I-L)=\lambda^n-a_1\lambda^{n-1}-a_2b_1\lambda^{n-2}-a_3b_1b_2\lambda^{n-3}-\cdots-a_nb_1b_2\cdots b_{n-1}.

繼續閱讀

張貼在 pow 特徵分析, 每週問題 | 標記 , | 發表留言

線性代數在圖論的應用 (三):拉普拉斯矩陣

本文的閱讀等級:中級

G=(V,E) 為一無向圖 (undirected graph),其中 V=\{v_1,\ldots,v_n\} 是端點集合,E 是無向邊集合。若頂點 v_iv_j 之間存在一邊,記為 (v_i,v_j),我們稱 v_iv_j 鄰接 (adjacent),並稱該邊與二頂點有關聯 (incident)。無向邊不具方向性,(v_i,v_j) 等同於 (v_j,v_i),每一邊可視為一無序頂點對。以下考慮簡單無向圖,意思是不存在自迴路 (self-loop),即 (v_i,v_i),且任二相異頂點至多僅存在一關聯邊。對應圖 G=(V,E),鄰接矩陣 A=[a_{ij}] 為一 n\times n 階矩陣,定義如下:a_{ij}=1(v_i,v_j)\in E,否則 a_{ij}=0 (見“線性代數在圖論的應用 (一):鄰接矩陣”)。顯然,a_{ij}=a_{ji}A 是一對稱矩陣。表面上,鄰接矩陣是一圖的最自然的表示方式,但它的實用價值卻不大,原因在於鄰接矩陣的特徵值和特徵向量未能揭露圖結構的重要訊息,此外,鄰接矩陣的二次型亦缺乏明確的涵義。本文介紹一種適於建立矩陣譜 (spectrum,即特徵值集合) 理論的無向圖表示矩陣,稱為拉普拉斯矩陣 (Laplacian)。對於頂點 v_i,分支度 (degree) d_i 是所有與 v_i 有關聯的邊數,此數值可由鄰接矩陣求得:d_i=\sum_{j=1}^na_{ij}。對應無向圖 G,拉普拉斯矩陣 (Laplacian) 定義為 L=D-A,其中 D=\text{diag}(d_1,\ldots,d_n) 稱為分支度矩陣。因為 DA 是對稱矩陣,拉普拉斯矩陣 L 也是對稱矩陣。為簡化符號,我們經常用下標 i 表示頂點 v_i。下圖為一例:G=(V,E),其中 V=\{1,2,3,4\}E=\{(1,2),(1,3),(1,4),(3,4)\}

拉普拉斯矩陣

對應此圖的鄰接矩陣 A、分支度矩陣 D 和拉普拉斯矩陣 L 分別是

\displaystyle  A=\begin{bmatrix}  0&1&1&1\\  1&0&0&0\\  1&0&0&1\\  1&0&1&0  \end{bmatrix},~~D=\begin{bmatrix}  3&0&0&0\\  0&1&0&0\\  0&0&2&0\\  0&0&0&2  \end{bmatrix},~~L=\left[\!\!\begin{array}{rrrr}  3&-1&-1&-1\\  -1&1&0&0\\  -1&0&2&-1\\  -1&0&-1&2  \end{array}\!\!\right]

繼續閱讀

張貼在 應用之道, 主題專欄 | 標記 , , , , | 發表留言

每週問題 December 1, 2014

本週問題是計算一棋盤狀特殊矩陣的特徵多項式。

Let A=[a_{ij}] be an n\times n matrix, in which a_{ij}=0 if i+j is even, and a_{ij}=1 if i+j is odd. For n\ge 2, find the eigenvalues of A.

繼續閱讀

張貼在 pow 特徵分析, 每週問題 | 標記 , | 發表留言