108 年 國立清華大學生命科學院聯招：分子與細胞生物研究所、分子醫學研究所、生物資訊與結構生物研究所、生物科技研究所、系統神經科學研究所丙組《計算機概論(演算法與計算機數學)》

這題主要在考察幾個重要的矩陣分解（Matrix Decomposition）的定義與目的。

核心觀念：
矩陣分解是將一個矩陣表示成幾個特定矩陣的乘積或組合，這在線性代數、數值分析、機器學習等領域有廣泛應用。

詳解：
(a) LU-decomposition for A.
LU分解（或稱 LDU 分解）是將一個方陣 A 分解成一個下三角矩陣 L (Lower triangular matrix) 和一個上三角矩陣 U (Upper triangular matrix) 的乘積，即 $A = LU$。如果 A 是可逆的，且其所有主子式（leading principal minors）均不為零，則其 LU 分解是唯一的（若 L 的對角元素為 1，則 U 的對角元素可任意縮放）。有時也會寫成 $A = LDU$，其中 D 是對角矩陣。
這個分解對於求解線性方程組 $Ax=b$ 非常有效，因為可以轉化為 $LUx=b$，進而解 $Ly=b$ (前向代換) 和 $Ux=y$ (後向代換)，計算量比直接求逆矩陣小。

(b) QR-factorization for A.
QR分解（或稱 QR 分解）是將一個矩陣 A 分解成一個正交矩陣 Q (Orthogonal matrix) 和一個上三角矩陣 R (Upper triangular matrix) 的乘積，即 $A = QR$。如果 A 是 n×m 矩陣，則 Q 是 n×n 的正交矩陣，R 是 n×m 的上三角矩陣。
QR分解在最小平方法問題、特徵值計算（QR 演算法）等方面有重要應用。Gram-Schmidt 正交化過程就是一種計算 QR 分解的方法。

(c) Singular value decomposition for A.
奇異值分解（Singular Value Decomposition, SVD）是將任何一個 m×n 的實數或複數矩陣 A 分解成三個矩陣的乘積：$A = U \Sigma V^T$ (或 $A = U \Sigma V^*$, 其中 $V^*$ 是 V 的共軛轉置)。
其中：

• U 是一個 m×m 的酉矩陣（Unitary matrix，若 A 是實數矩陣，則 U 是正交矩陣）。

核心觀念

題目給定 Householder 矩陣

$$H_u=I-2\vec{u}\vec{u}^{T},$$

其中 $\vec{u}\in R^n$ 且

$$\|\vec{u}\|_2=1.$$

由二範數定義可得

$$\|\vec{u}\|_2^2=\vec{u}^{T}\vec{u}=1.$$

本題利用三個矩陣性質：

1. 轉置運算：$(AB)^T=B^TA^T$。
2. 單位向量條件：$\vec{u}^T\vec{u}=1$。
3. 正交矩陣定義：矩陣 $Q$ 若滿足 $Q^TQ=I$，則 $Q$ 為正交矩陣。

---

解題方法

直接從定義

$$H_u=I-2\vec{u}\vec{u}^{T}$$

出發，分別計算 $H_u^T$、$H_u^2$ 與 $H_u^TH_u$，即可證明三項性質。

---

(a) 證明 Householder 矩陣為對稱矩陣

矩陣 $H_u$ 的轉置為

$$H_u^T = \left(I-2\vec{u}\vec{u}^{T}\right)^T.$$

利用轉置的線性與乘法性質：

$$H_u^T = I^T-2\left(\vec{u}\vec{u}^{T}\right)^T = I-2\left(\vec{u}^{T}\right)^T\vec{u}^{T}.$$

因為

$$\left(\vec{u}^{T}\right)^T=\vec{u},$$

因此

$$H_u^T = I-2\vec{u}\vec{u}^{T} = H_u.$$

所以 $H_u$ 等於自己的轉置，故為對稱矩陣。

---

(b) 證明 Householder 矩陣的反矩陣為自身

先計算 $H_u^2$：

$$H_u^2 = \left(I-2\vec{u}\vec{u}^{T}\right) \left(I-2\vec{u}\vec{u}^{T}\right).$$

展開乘積：

$$H_u^2 = I-2\vec{u}\vec{u}^{T} -2\vec{u}\vec{u}^{T} +4\vec{u}\vec{u}^{T}\vec{u}\vec{u}^{T}.$$

整理前面兩項：

核心觀念

本題考查三個重點：

• 特徵值：由特徵方程
  $\det(A-\lambda I)=0$
  求得。
• 譜分解（spectrum decomposition）：實對稱矩陣可正交對角化：
  $A=Q\Lambda Q^T=\sum_i \lambda_i P_i,$
  其中 $Q$ 的欄向量是單位正交特徵向量，$P_i$ 是對應的正交投影矩陣。
• Rayleigh 商：對實對稱矩陣 $A$，
  $\max_{\|\vec{x}\|_2=1}\vec{x}^TA\vec{x}=\lambda_{\max}(A).$

矩陣 $A$ 為實對稱矩陣，因此上述定理皆可直接使用。

解題方法

矩陣為

$$A= \begin{bmatrix} 3&-1&0\\ -1&0&0\\ 0&0&3 \end{bmatrix}.$$

其前兩列、前兩行形成一個 $2\times 2$ 區塊：

$$B= \begin{bmatrix} 3&-1\\ -1&0 \end{bmatrix},$$

而第三個座標方向獨立對應特徵值 $3$。因此可先求 $B$ 的特徵值，再併入 $3$。

---

（a）求 $A$ 的特徵值

特徵方程為

$$\det(A-\lambda I) = \det \begin{bmatrix} 3-\lambda&-1&0\\ -1&-\lambda&0\\ 0&0&3-\lambda \end{bmatrix}.$$

利用區塊結構：

$$\det(A-\lambda I) = (3-\lambda) \det \begin{bmatrix} 3-\lambda&-1\\ -1&-\lambda \end{bmatrix}.$$

計算 $2\times 2$ 行列式：

$$\det \begin{bmatrix} 3-\lambda&-1\\ -1&-\lambda \end{bmatrix} = (3-\lambda)(-\lambda)-1 = \lambda^2-3\lambda-1.$$

因此

$$\det(A-\lambda I) = (3-\lambda)(\lambda^2-3\lambda-1).$$

解得

$$3-\lambda=0 \quad\Longrightarrow\quad \lambda=3,$$

以及

$$\lambda^2-3\lambda-1=0.$$

由一元二次方程公式：

$$\lambda_{\pm}=\frac{3\pm\sqrt{13}}{2}.$$

所以 $A$ 的三個特徵值為

$$\boxed{ \lambda_+=\frac{3+\sqrt{13}}{2},\qquad \lambda_-= \frac{3-\sqrt{13}}{2},\qquad \lambda_3=3 }.$$

---

（b）求 $A$ 的譜分解

1. 求特徵向量

對應 $\lambda_{\pm}$，令特徵向量為

$$\vec{v}_{\pm} = \begin{bmatrix} 1\\ 3-\lambda_{\pm}\\ 0 \end{bmatrix}.$$

因為

$$3-\lambda_+ = \frac{3-\sqrt{13}}{2}, \qquad 3-\lambda_- = \frac{3+\sqrt{13}}{2},$$

可寫成

$$\vec{v}_+ = \begin{bmatrix} 1\\ \dfrac{3-\sqrt{13}}{2}\\ 0 \end{bmatrix}, \qquad \vec{v}_- = \begin{bmatrix} 1\\ \dfrac{3+\sqrt{13}}{2}\\ 0 \end{bmatrix}.$$

對應 $\lambda_3=3$，可取

$$\vec{v}_3= \begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix}.$$

由於 $A$ 是實對稱矩陣，不同特徵值的特徵向量彼此正交。將前兩個特徵向量正規化：

這題主要測試求和符號（Summation）的計算、二項式定理的應用以及 Gamma 函數的定義與計算。

核心觀念：

• 等差級數求和：$\sum_{k=1}^n k = \frac{n(n+1)}{2}$
• 二項式定理：$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k} b^k$
• Gamma 函數：$\Gamma(x) = \int_{0}^{\infty} t^{x-1} e^{-t} dt$
• Gamma 函數與階乘的關係：$\Gamma(n) = (n-1)!$
• Gamma 函數的特殊值：$\Gamma(\frac{1}{2}) = \sqrt{\pi}$

詳解：
(a) $\sum_{k=1}^{n}(2k-1) = ?$
這是計算前 n 個奇數的和。
$\sum_{k=1}^{n}(2k-1) = \sum_{k=1}^{n} 2k - \sum_{k=1}^{n} 1$
$= 2 \sum_{k=1}^{n} k - n \cdot 1$
$= 2 \cdot \frac{n(n+1)}{2} - n$
$= n(n+1) - n$
$= n^2 + n - n$
$= n^2$
也可以理解為，前 n 個奇數的和是 $n^2$。例如，n=1: 1 = $1^2$；n=2: 1+3 = 4 = $2^2$；n=3: 1+3+5 = 9 = $3^2$。

(b) $\sum_{k=0}^{n} \binom{n}{k} = ?$
根據二項式定理，令 $a=1, b=1$：
$(1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k$
$2^n = \sum_{k=0}^{n} \binom{n}{k}$
這是計算所有二項式係數的和，結果是 $2^n$。

(c) $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = ?$
根據二項式定理，令 $a=1, b=-1$：
$(1+(-1))^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} (-1)^k$
$0^n = \sum_{k=0}^{n} (-1)^k \binom{n}{k}$
如果 $n > 0$，則 $0^n = 0$。
如果 $n = 0$，則 $\sum_{k=0}^{0} (-1)^k \binom{0}{k} = (-1)^0 \binom{0}{0} = 1 \cdot 1 = 1$。
題目沒有明確 n 的範圍，但通常此類題目預設 $n \ge 1$。
因此，對於 $n \ge 1$，結果是 0。

核心觀念

本題考查二項分布的基本性質。每個 $X_i$ 都是獨立且成功機率為 $p$ 的 Bernoulli 隨機變數：

$$P(X_i=1)=p,\qquad P(X_i=0)=q=1-p.$$

$n$ 次獨立試驗中成功的總次數

$$X=X_1+X_2+\cdots+X_n$$

服從二項分布：

$$X\sim\operatorname{Binomial}(n,p).$$

因此可直接使用二項分布的機率質量函數、動差生成函數、期望值與變異數公式。

---

解題方法

（a）$X$ 的機率質量函數

$X=k$ 表示 $n$ 次試驗中恰好有 $k$ 次成功、$n-k$ 次失敗。

固定一種排列時，其機率為

$$p^kq^{n-k}.$$

在 $n$ 次試驗中選出 $k$ 次成功的位置，共有

$$\binom{n}{k}$$

種排列，因此

$$P(X=k)=\binom{n}{k}p^kq^{n-k}, \qquad k=0,1,2,\ldots,n.$$

由於 $X$ 是離散型隨機變數，嚴格來說應稱為「機率質量函數」：

$$f_X(k)=\binom{n}{k}p^kq^{n-k}, \qquad k=0,1,\ldots,n.$$

其他 $k$ 值的機率為 $0$。

---

（b）$X$ 的動差生成函數

動差生成函數定義為

$$M_X(t)=E(e^{tX}).$$

因為

$$X=X_1+\cdots+X_n,$$

所以

$$M_X(t) =E\left(e^{t(X_1+\cdots+X_n)}\right) =E\left(e^{tX_1}\cdots e^{tX_n}\right).$$

由於 $X_1,\ldots,X_n$ 相互獨立，期望值可以分解：

$$M_X(t) =\prod_{i=1}^{n}E(e^{tX_i}).$$

對單一 Bernoulli 隨機變數 $X_i$：

$$\begin{aligned} E(e^{tX_i}) &=e^{t\cdot 1}P(X_i=1)+e^{t\cdot 0}P(X_i=0)\\ &=pe^t+q. \end{aligned}$$

因此

$$\boxed{M_X(t)=(q+pe^t)^n}.$$

使用 $q=1-p$，也可寫成

$$\boxed{M_X(t)=(1-p+pe^t)^n}.$$

這題考察常態分佈（Normal Distribution）及其相關變數的機率密度函數（PDF）的轉換，特別是標準化過程和變數變換。

核心觀念：

• 常態分佈 PDF：$f_X(x) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$
• 標準化：將任意常態變數轉換為標準常態變數 $Z = (X-\mu)/\sigma$。
• 變數變換法（Transformation of Variables）：若 $Y = g(X)$，則 $f_Y(y) = f_X(g^{-1}(y)) | \frac{d}{dy} g^{-1}(y) |$。
• 卡方分佈（Chi-squared Distribution）：標準常態變數的平方服從自由度為 1 的卡方分佈。

詳解：
已知 X 服從平均值 $\mu=3$ 和變異數 $\sigma^2=4$ 的常態分佈。因此，標準差 $\sigma = \sqrt{4} = 2$。

(a) Write down the probability density function of X.
根據常態分佈的 PDF 公式：
$f_X(x) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$
代入 $\mu=3$ 和 $\sigma^2=4$：
$f_X(x) = \frac{1}{\sqrt{2\pi(4)}} e^{-\frac{(x-3)^2}{2(4)}}$
$f_X(x) = \frac{1}{\sqrt{8\pi}} e^{-\frac{(x-3)^2}{8}}$
$f_X(x) = \frac{1}{2\sqrt{2\pi}} e^{-\frac{(x-3)^2}{8}}$

(b) Write down the probability density function of Z.
已知 $Z = (X-3)/2$。
這是一個標準化過程。我們知道，如果 X 服從 $\mathcal{N}(\mu, \sigma^2)$，那麼 $Z = (X-\mu)/\sigma$ 服從標準常態分佈 $\mathcal{N}(0, 1)$。
所以，Z 服從平均值 $\mu_Z=0$ 和變異數 $\sigma_Z^2=1$ 的常態分佈。
其 PDF 為：
$f_Z(z) = \frac{1}{\sqrt{2\pi(1)}} e^{-\frac{(z-0)^2}{2(1)}}$
$f_Z(z) = \frac{1}{\sqrt{2\pi}} e^{-\frac{z^2}{2}}$

我們也可以使用變數變換法來推導：
由 $Z = (X-3)/2$，我們可以得到 $X = 2Z + 3$。
$\frac{dX}{dZ} = 2$。
$f_Z(z) = f_X(x(z)) |\frac{dx}{dz}|$
$f_Z(z) = f_X(2z+3) |2|$
$f_X(2z+3) = \frac{1}{2\sqrt{2\pi}} e^{-\frac{((2z+3)-3)^2}{8}} = \frac{1}{2\sqrt{2\pi}} e^{-\frac{(2z)^2}{8}} = \frac{1}{2\sqrt{2\pi}} e^{-\frac{4z^2}{8}} = \frac{1}{2\sqrt{2\pi}} e^{-\frac{z^2}{2}}$
$f_Z(z) = \frac{1}{2\sqrt{2\pi}} e^{-\frac{z^2}{2}} \times 2 = \frac{1}{\sqrt{2\pi}} e^{-\frac{z^2}{2}}$。
結果一致。

這題考察次序統計量（Order Statistics）的機率密度函數（PDF）和期望值。

核心觀念：

• 次序統計量：對隨機樣本進行排序後得到的變數。
• 最小/最大值次序統計量的 CDF：
  • $F_{X_{(1)}}(x) = 1 - (1 - F_X(x))^n$ (最小值的 CDF)
  • $F_{X_{(n)}}(x) = (F_X(x))^n$ (最大值的 CDF)
• PDF 由 CDF 求導得到：$f(x) = \frac{d}{dx} F(x)$。
• 期望值：$E[X] = \int_{-\infty}^{\infty} x f(x) dx$。

詳解：
樣本 $\{X_1, X_2, ..., X_n\}$ 來自於均勻分佈 $U(0,1)$。
其累積分佈函數 (CDF) 為：
$F_X(x) = \begin{cases} 0 & \text{if } x < 0 \\ x & \text{if } 0 \le x \le 1 \\ 1 & \text{if } x > 1 \end{cases}$
其機率密度函數 (PDF) 為：
$f_X(x) = \begin{cases} 1 & \text{if } 0 \le x \le 1 \\ 0 & \text{otherwise} \end{cases}$

(a) Find the probability density function of $X_{(n)}$.
$X_{(n)}$ 是樣本中的最大值。
首先，我們求 $X_{(n)}$ 的累積分佈函數 (CDF)：
$F_{X_{(n)}}(x) = P(X_{(n)} \le x)$
由於 $X_{(n)}$ 是樣本中的最大值，這意味著所有樣本值都必須小於或等於 x。
$P(X_{(n)} \le x) = P(X_1 \le x, X_2 \le x, ..., X_n \le x)$
由於樣本是獨立的，所以：
$P(X_{(n)} \le x) = P(X_1 \le x) P(X_2 \le x) ... P(X_n \le x)$
$= [F_X(x)]^n$
因此，$F_{X_{(n)}}(x) = (F_X(x))^n$。

現在我們根據 x 的範圍來寫出 $F_{X_{(n)}}(x)$：

• 如果 $x < 0$: $F_X(x) = 0$，所以 $F_{X_{(n)}}(x) = 0^n = 0$。
• 如果 $0 \le x \le 1$: $F_X(x) = x$，所以 $F_{X_{(n)}}(x) = x^n$。