114 年 國立成功大學電腦與通信工程研究所丁組《線性代數與機率》

本題考驗聯合機率密度函數的計算，包含期望值、變異數、共變異數以及線性組合的變異數。

首先，我們需要確定 $X$ 和 $Y$ 的邊緣機率密度函數 (marginal pdf)。
聯合 pdf 的積分區域為一個三角形，其頂點為 (0,0), (1,0), (1,1)。

計算 $f_X(x)$:
$f_X(x) = \int_{-\infty}^{\infty} f_{X,Y}(x,y) dy = \int_{0}^{x} 2 dy = 2y \big|_{0}^{x} = 2x$, for $0 \le x \le 1$.
所以，$f_X(x) = 2x$ for $0 \le x \le 1$, and 0 otherwise.

計算 $f_Y(y)$:
$f_Y(y) = \int_{-\infty}^{\infty} f_{X,Y}(x,y) dx$. 積分範圍為 $y \le x \le 1$。
$f_Y(y) = \int_{y}^{1} 2 dx = 2x \big|_{y}^{1} = 2(1-y)$, for $0 \le y \le 1$.
所以，$f_Y(y) = 2(1-y)$ for $0 \le y \le 1$, and 0 otherwise.

a. Find $E(X)$ and $Var(X)$.
$E(X) = \int_{-\infty}^{\infty} x f_X(x) dx = \int_{0}^{1} x (2x) dx = \int_{0}^{1} 2x^2 dx = \frac{2}{3}x^3 \big|_{0}^{1} = \frac{2}{3}$.
$E(X^2) = \int_{-\infty}^{\infty} x^2 f_X(x) dx = \int_{0}^{1} x^2 (2x) dx = \int_{0}^{1} 2x^3 dx = \frac{2}{4}x^4 \big|_{0}^{1} = \frac{1}{2}$.
$Var(X) = E(X^2) - (E(X))^2 = \frac{1}{2} - (\frac{2}{3})^2 = \frac{1}{2} - \frac{4}{9} = \frac{9-8}{18} = \frac{1}{18}$.

【答案】$E(X) = \frac{2}{3}$, $Var(X) = \frac{1}{18}$.

b. Find $E(Y)$ and $Var(Y)$.

本題屬於期望值問題，與機率中的「Coupon Collector's Problem」（收集優惠券問題）類似。

問題的核心是：我們希望收集到所有 $k$ 種不同的物品，每次抽取都獨立且機率均等。問平均需要抽取多少次才能收集到所有 $k$ 種物品？

在此問題中，有 $k=6$ 種不同的 grades: {A, A-, B+, B, B-, C+}。
每種 grade 的出現機率均等，即 $p = \frac{1}{6}$。

我們將這個問題分解為收集到第 $i$ 種新 grade 所需的額外抽取次數。
設 $T$ 為收集到所有 6 種 grade 所需的總抽取次數。
設 $T_i$ 為在已經收集到 $i-1$ 種 grade 的情況下，收集到第 $i$ 種新 grade 所需的額外抽取次數。
則 $T = T_1 + T_2 + T_3 + T_4 + T_5 + T_6$.
我們要求的是 $E[T] = E[T_1] + E[T_2] + E[T_3] + E[T_4] + E[T_5] + E[T_6]$.

當我們已經收集到 $i-1$ 種 grade 時，剩下 $k - (i-1)$ 種 grade 是我們尚未收集到的。
每次抽取，我們收集到一種「新」grade 的機率是 $\frac{k-(i-1)}{k}$。
這意味著，在已經收集到 $i-1$ 種 grade 的情況下，下一次抽取恰好是我們還沒收集到的 grade 的機率是 $p_i = \frac{k-(i-1)}{k}$。
因此，$T_i$ 服從參數為 $p_i$ 的幾何分佈 (Geometric distribution)，其期望值為 $E[T_i] = \frac{1}{p_i} = \frac{k}{k-(i-1)}$。

在此問題中，$k=6$。
$E[T_1]$: 收集到第一種 grade。此時還沒有任何 grade，所以任何 grade 都是新 grade。機率為 $\frac{6}{6} = 1$。$E[T_1] = \frac{6}{6} = 1$.
$E[T_2]$: 已經收集到 1 種 grade，剩下 5 種未收集。

本題考驗矩陣的對角化 (diagonalization) 和矩陣的冪次計算。然而，題目給出的矩陣 $A$ 是 $3 \times 4$ 的，這意味著它不是一個方陣，因此無法進行對角化，也無法計算 $A^n$。通常，對角化和矩陣冪次是針對方陣定義的。

假設題目意圖是給一個方陣，並且要求的是相似對角化 (similarity diagonalization)。如果 $A$ 是一個 $m \times m$ 的方陣，我們可以找到一個可逆矩陣 $P$ 使得 $P^{-1}AP = D$ 為對角矩陣，其中 $D$ 的對角元素是 $A$ 的特徵值 (eigenvalues)，而 $P$ 的列向量是對應的特徵向量 (eigenvectors)。
那麼 $A = PDP^{-1}$。
$A^n = (PDP^{-1})^n = PD P^{-1} P D P^{-1} \cdots P D P^{-1} = PD^n P^{-1}$。
如果 $D = \text{diag}(\lambda_1, \lambda_2, \ldots, \lambda_m)$，則 $D^n = \text{diag}(\lambda_1^n, \lambda_2^n, \ldots, \lambda_m^n)$。

如果題目給的矩陣 $A$ 是 $3 \times 4$ 的，那麼：
a. 找不到一個矩陣 $P$ 使得 $P^{-1}AP$ 是對角矩陣。因為 $P$ 必須是方陣，才能有逆矩陣 $P^{-1}$。如果 $P$ 是 $3 \times 3$ 的，那麼 $P^{-1}AP$ 的維度是 $3 \times 4$，不可能是對角矩陣（對角矩陣必須是方陣）。如果 $P$ 是 $4 \times 4$ 的，那麼 $P^{-1}AP$ 的維度是 $4 \times 4$。然而，對角化通常是針對 $m \times m$ 矩陣，其中 $P$ 也是 $m \times m$ 的。
b. 無法計算 $A^n$，因為 $A$ 不是方陣。
c. 無法計算 $B = \lim_{n\to\infty} A^n$，因為 $A^n$ 未定義。

重要勘誤與推測：
根據題目格式和常見的研究所考題，極有可能題目給的矩陣 $A$ 應為一個方陣，例如 $3 \times 3$ 或 $4 \times 4$。
另外，題目中的 "rank $A = 2$" 似乎是獨立於矩陣 $A$ 的敘述，可能屬於下一題（題號 4）。

假設矩陣 A 應為 3x3 且為對稱矩陣 (以求對角化)：
如果 $A$ 是一個 $3 \times 3$ 的對稱矩陣，那麼它一定可以被正交對角化，即存在一個正交矩陣 $P$ ($P^T = P^{-1}$) 使得 $P^T A P = D$。
此時 $A = P D P^T$。
$A^n = (P D P^T)^n = P D P^T P D P^T \cdots P D P^T = P D^n P^T$。
其中 $D$ 是對角矩陣，對角元素是 $A$ 的特徵值。

假設矩陣 A 應為 3x3 且有 3 個線性獨立的特徵向量：
若 A 是一個 3x3 矩陣，且存在 3 個線性獨立的特徵向量，則可以對角化。
$A = PDP^{-1}$
$A^n = PD^n P^{-1}$

針對題目給出的矩陣 A (3x4)：
由於原題明確給出 $A$ 是 $3 \times 4$ 的矩陣，且沒有其他上下文說明，我們只能依照題目內容作答。

a. Find a matrix P such that $P^{-1}AP$ is diagonal.
要使 $P^{-1}AP$ 為對角矩陣，首先 $P$ 必須是方陣，且 $P$ 和 $A$ 的維度需相容，使得乘積 $P^{-1}AP$ 是方陣。
若 $P$ 是 $m \times m$ 的矩陣，則 $P^{-1}$ 也是 $m \times m$。
若 $A$ 是 $3 \times 4$，則 $P^{-1}AP$ 的維度是 $m \times m$ 乘以 $3 \times 4$ 乘以 $m \times m$。
為了使乘積有意義，中間的 $A$ 必須能與前後的 $P, P^{-1}$ 相容。

本題考驗奇異值分解 (SVD)、偽逆 (Moore-Penrose pseudoinverse, $A^+$) 和最小平方解 (least-squares solution)。

給定矩陣 $A = \begin{bmatrix} 3 & 2 & 2 \\ 2 & 3 & -2 \end{bmatrix}$，維度為 $2 \times 3$，且 rank $A = 2$。

a. Find an SVD of $A$.
SVD 的形式為 $A = U \Sigma V^T$，其中 $U$ 是 $2 \times 2$ 的正交矩陣，$V$ 是 $3 \times 3$ 的正交矩陣，$\Sigma$ 是 $2 \times 3$ 的對角矩陣。
$\Sigma$ 的對角元素是奇異值 (singular values) $\sigma_1, \sigma_2, \ldots, \sigma_r$，其中 $r = \text{rank}(A)$。
奇異值是 $A A^T$ 或 $A^T A$ 的特徵值的平方根。由於 $A$ 是 $2 \times 3$，$A A^T$ 是 $2 \times 2$ 矩陣，計算較簡單。

計算 $A A^T$:
$A A^T = \begin{bmatrix} 3 & 2 & 2 \\ 2 & 3 & -2 \end{bmatrix} \begin{bmatrix} 3 & 2 \\ 2 & 3 \\ 2 & -2 \end{bmatrix} = \begin{bmatrix} 9+4+4 & 6+6-4 \\ 6+6-4 & 4+9+4 \end{bmatrix} = \begin{bmatrix} 17 & 8 \\ 8 & 17 \end{bmatrix}$.

計算 $A A^T$ 的特徵值：
$\det(A A^T - \lambda I) = \det \begin{bmatrix} 17-\lambda & 8 \\ 8 & 17-\lambda \end{bmatrix} = (17-\lambda)^2 - 8^2 = 0$.
$(17-\lambda)^2 = 64$
$17-\lambda = \pm 8$.
$\lambda_1 = 17 - 8 = 9$.
$\lambda_2 = 17 + 8 = 25$.

奇異值為特徵值的平方根：
$\sigma_1 = \sqrt{25} = 5$.
$\sigma_2 = \sqrt{9} = 3$.
（按照慣例，奇異值通常由大到小排列，所以 $\sigma_1=5, \sigma_2=3$）。

計算 $U$ 的特徵向量：
對於 $\lambda_1 = 25$:
$(A A^T - 25I)u = 0 \implies \begin{bmatrix} -8 & 8 \\ 8 & -8 \end{bmatrix} u = 0$.
$-8u_1 + 8u_2 = 0 \implies u_1 = u_2$.
取 $u_2 = 1$, 則 $u_1 = 1$. 特徵向量為 $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$.
正規化得到 $u^{(1)} = \frac{1}{\sqrt{1^2+1^2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}$.

對於 $\lambda_2 = 9$:
$(A A^T - 9I)u = 0 \implies \begin{bmatrix} 8 & 8 \\ 8 & 8 \end{bmatrix} u = 0$.
$8u_1 + 8u_2 = 0 \implies u_1 = -u_2$.
取 $u_2 = 1$, 則 $u_1 = -1$. 特徵向量為 $\begin{bmatrix} -1 \\ 1 \end{bmatrix}$.
正規化得到 $u^{(2)} = \frac{1}{\sqrt{(-1)^2+1^2}} \begin{bmatrix} -1 \\ 1 \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} -1 \\ 1 \end{bmatrix}$.

所以 $U = \begin{bmatrix} u^{(1)} & u^{(2)} \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix}$.

計算 $\Sigma$:
$\Sigma = \begin{bmatrix} \sigma_1 & 0 & 0 \\ 0 & \sigma_2 & 0 \end{bmatrix} = \begin{bmatrix} 5 & 0 & 0 \\ 0 & 3 & 0 \end{bmatrix}$.

計算 $V$:
$v^{(i)} = \frac{1}{\sigma_i} A^T u^{(i)}$.
對於 $\sigma_1 = 5$ 和 $u^{(1)} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}$:
$v^{(1)} = \frac{1}{5} A^T u^{(1)} = \frac{1}{5} \begin{bmatrix} 3 & 2 & 2 \\ 2 & 3 & -2 \end{bmatrix}^T \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \frac{1}{5\sqrt{2}} \begin{bmatrix} 3 & 2 & 2 \\ 2 & 3 & -2 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}$ (假設矩陣 $A$ 的第三個數字是 2，不是 0)
修正： $A = \begin{bmatrix} 3 & 2 & 2 \\ 2 & 3 & -2 \end{bmatrix}$
$v^{(1)} = \frac{1}{5} A^T u^{(1)} = \frac{1}{5} \begin{bmatrix} 3 & 2 \\ 2 & 3 \\ 2 & -2 \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \frac{1}{5\sqrt{2}} \begin{bmatrix} 3(1)+2(1) \\ 2(1)+3(1) \\ 2(1)-2(1) \end{bmatrix} = \frac{1}{5\sqrt{2}} \begin{bmatrix} 5 \\ 5 \\ 0 \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}$.

對於 $\sigma_2 = 3$ 和 $u^{(2)} = \frac{1}{\sqrt{2}} \begin{bmatrix} -1 \\ 1 \end{bmatrix}$:
$v^{(2)} = \frac{1}{3} A^T u^{(2)} = \frac{1}{3} \begin{bmatrix} 3 & 2 \\ 2 & 3 \\ 2 & -2 \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} -1 \\ 1 \end{bmatrix} = \frac{1}{3\sqrt{2}} \begin{bmatrix} 3(-1)+2(1) \\ 2(-1)+3(1) \\ 2(-1)-2(1) \end{bmatrix} = \frac{1}{3\sqrt{2}} \begin{bmatrix} -1 \\ 1 \\ -4 \end{bmatrix}$.
這裡的 $v^{(2)}$ 沒有被正規化，因為 $A^T u^{(2)}$ 的模長是 $\sigma_2 = 3$。
$v^{(2)}$ 的模長是 $\frac{1}{3\sqrt{2}} \sqrt{(-1)^2 + 1^2 + (-4)^2} = \frac{1}{3\sqrt{2}} \sqrt{1+1+16} = \frac{\sqrt{18}}{3\sqrt{2}} = \frac{3\sqrt{2}}{3\sqrt{2}} = 1$.
所以 $v^{(2)} = \frac{1}{3\sqrt{2}} \begin{bmatrix} -1 \\ 1 \\ -4 \end{bmatrix}$.

$V$ 的第三個列向量 $v^{(3)}$ 是 $A^T A$ 的零空間 (null space) 的一個單位向量。
計算 $A^T A$:
$A^T A = \begin{bmatrix} 3 & 2 \\ 2 & 3 \\ 2 & -2 \end{bmatrix} \begin{bmatrix} 3 & 2 & 2 \\ 2 & 3 & -2 \end{bmatrix} = \begin{bmatrix} 9+4 & 6+6 & 6-4 \\ 6+6 & 4+9 & 4-6 \\ 6-4 & 4-6 & 4+4 \end{bmatrix} = \begin{bmatrix} 13 & 12 & 2 \\ 12 & 13 & -2 \\ 2 & -2 & 8 \end{bmatrix}$.
$A^T A$ 的特徵值是 $\sigma_1^2=25$, $\sigma_2^2=9$, 以及 $\lambda_3$。
由於 rank $A = 2$, $A^T A$ 的 rank 也為 2，所以 $\det(A^T A) = 0$, 意味著其中一個特徵值為 0。
所以 $A^T A$ 的特徵值是 25, 9, 0。
我們需要找到對應於特徵值 0 的特徵向量，它會是 $V$ 的第三個向量 $v^{(3)}$。
$(A^T A - 0I)v = 0 \implies A^T A v = 0$.
$\begin{bmatrix} 13 & 12 & 2 \\ 12 & 13 & -2 \\ 2 & -2 & 8 \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \\ v_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$.
從第三列：$2v_1 - 2v_2 + 8v_3 = 0 \implies v_1 - v_2 + 4v_3 = 0$.
從第一列：$13v_1 + 12v_2 + 2v_3 = 0$.
從第二列：$12v_1 + 13v_2 - 2v_3 = 0$.
用第一和第三列聯立：
$v_1 = v_2 - 4v_3$.
$13(v_2 - 4v_3) + 12v_2 + 2v_3 = 0 \implies 13v_2 - 52v_3 + 12v_2 + 2v_3 = 0 \implies 25v_2 - 50v_3 = 0 \implies v_2 = 2v_3$.
代回 $v_1 = v_2 - 4v_3 = 2v_3 - 4v_3 = -2v_3$.
所以，特徵向量是 $\begin{bmatrix} -2v_3 \\ 2v_3 \\ v_3 \end{bmatrix}$.
取 $v_3 = 1$, 得到 $\begin{bmatrix} -2 \\ 2 \\ 1 \end{bmatrix}$.
正規化：$v^{(3)} = \frac{1}{\sqrt{(-2)^2+2^2+1^2}} \begin{bmatrix} -2 \\ 2 \\ 1 \end{bmatrix} = \frac{1}{\sqrt{4+4+1}} \begin{bmatrix} -2 \\ 2 \\ 1 \end{bmatrix} = \frac{1}{3} \begin{bmatrix} -2 \\ 2 \\ 1 \end{bmatrix}$.

所以 $V = \begin{bmatrix} v^{(1)} & v^{(2)} & v^{(3)} \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{3\sqrt{2}} & -\frac{2}{3} \\ \frac{1}{\sqrt{2}} & \frac{1}{3\sqrt{2}} & \frac{2}{3} \\ 0 & -\frac{4}{3\sqrt{2}} & \frac{1}{3} \end{bmatrix}$.
檢查 $V$ 是否為正交矩陣：