112 年 國立臺灣大學資訊工程學系碩士班《數學》

本題考驗對 Hamiltonian Cycle 的定義與圖論性質的理解。Hamiltonian Cycle 是指通過圖中所有頂點恰好一次並回到起點的閉路。若一個圖沒有 Hamiltonian Cycle，則稱其為 non-Hamiltonian graph。

圖論中，若一個頂點的度數為 $d$，則該頂點至少有 $d$ 個鄰居。若一個圖 $G=(V,E)$ 具有 $n$ 個頂點，且對於任意不相連的兩個頂點 $u, v$ 都有 $\deg(u) + \deg(v) \ge n$，則 $G$ 必定有 Hamiltonian Cycle (Dirac's Theorem)。反之，若一個圖不滿足此條件，則不一定沒有 Hamiltonian Cycle，但若能找到一對不相連的頂點 $u, v$ 使得 $\deg(u) + \deg(v) < n$，則該圖可能沒有 Hamiltonian Cycle。

我們逐一檢視各選項的圖形：
(A) 該圖是一個完整的五角形（$K_5$），所有頂點度數為 4。對於任意兩個頂點 $u, v$，$\deg(u) + \deg(v) = 4+4 = 8 \ge 5$。根據 Dirac's Theorem，此圖有 Hamiltonian Cycle。
(B) 該圖是一個五角形，其中一條邊被移除，形成一個「缺一邊的五角形」。頂點數 $n=5$。有兩個頂點度數為 2，三個頂點度數為 3。

• 若取兩個度數為 3 的頂點 $u, v$，則 $\deg(u) + \deg(v) = 3+3 = 6 \ge 5$。
• 若取一個度數為 2 的頂點 $u$ 和一個度數為 3 的頂點 $v$，則 $\deg(u) + \deg(v) = 2+3 = 5 \ge 5$。
• 若取兩個度數為 2 的頂點 $u, v$，則 $\deg(u) + \deg(v) = 2+2 = 4 < 5$。這兩個頂點不相連。根據 Dirac's Theorem 的逆否命題，此圖可能沒有 Hamiltonian Cycle。實際上，此圖（稱為 $C_5$ 減一邊）是有 Hamiltonian Cycle 的，例如可以繞過所有頂點。
  (C) 該圖是一個五角形，其中兩條相鄰的邊被移除，形成一個「缺兩條相鄰邊的五角形」。頂點數 $n=5$。有兩個頂點度數為 1，兩個頂點度數為 2，一個頂點度數為 3。
• 考慮兩個度數為 1 的頂點 $u, v$。它們不相連。$\deg(u) + \deg(v) = 1+1 = 2 < 5$。

本題考查線性齊次遞迴關係式的求解。給定的遞迴關係式為 $a_n = -a_{n-1} + 6a_{n-2}$，其初始條件為 $a_0 = A$ 和 $a_1 = B$。

首先，寫出遞迴關係式的特徵方程式（characteristic equation）：
$r^2 = -r + 6$
$r^2 + r - 6 = 0$

因式分解特徵方程式：
$(r+3)(r-2) = 0$

特徵根為 $r_1 = -3$ 和 $r_2 = 2$。

由於特徵根是相異實根，遞迴關係式的通解形式為：
$a_n = c_1 (-3)^n + c_2 (2)^n$
其中 $c_1$ 和 $c_2$ 是待定的常數。

我們利用初始條件來求解 $c_1$ 和 $c_2$：
當 $n=0$ 時，$a_0 = c_1 (-3)^0 + c_2 (2)^0 = c_1 + c_2 = A$。
當 $n=1$ 時，$a_1 = c_1 (-3)^1 + c_2 (2)^1 = -3c_1 + 2c_2 = B$。

現在我們有一個關於 $c_1$ 和 $c_2$ 的線性方程組：

1. $c_1 + c_2 = A$
2. $-3c_1 + 2c_2 = B$

從方程 (1) 中，我們可以得到 $c_2 = A - c_1$。將其代入方程 (2)：
$-3c_1 + 2(A - c_1) = B$
$-3c_1 + 2A - 2c_1 = B$
$-5c_1 = B - 2A$

核心觀念

本題考察線性常係數遞迴關係的生成函數法，以及部分分式分解。

令生成函數為

$$G(x)=\sum_{n=0}^{\infty}a_nx^n。$$

若遞迴式為

$$a_n=a_{n-1}+6a_{n-2},$$

其特徵方程為

$$r^2-r-6=0 \quad\Longrightarrow\quad (r-3)(r+2)=0。$$

因此特徵根為 $3$ 與 $-2$，生成函數的分母應為

$$(1-3x)(1+2x)，$$

而非選項中的 $(1-2x)(1+3x)$。

解題方法

由遞迴式，對 $n\geq 2$ 乘上 $x^n$ 後加總：

$$\sum_{n=2}^{\infty}a_nx^n = \sum_{n=2}^{\infty}a_{n-1}x^n + 6\sum_{n=2}^{\infty}a_{n-2}x^n。$$

各項整理為

$$G(x)-A-Bx=xG(x)+6x^2G(x)。$$

因此

$$G(x)(1-x-6x^2)=A+(B-A)x。$$

因為

$$1-x-6x^2=(1-3x)(1+2x)，$$

所以

$$G(x)=\frac{A+(B-A)x}{(1-3x)(1+2x)}。$$

設

$$G(x)=\frac{C}{1-3x}+\frac{D}{1+2x}。$$

通分得

$$A+(B-A)x = C(1+2x)+D(1-3x)。$$

比較常數項與 $x$ 項：

$$C+D=A,$$ $$2C-3D=B-A。$$

解得

$$C=\frac{2A+B}{5}, \qquad D=\frac{3A-B}{5}。$$

故正確的部分分式形式為

本題考查組合數學中的整數解問題，特別是帶有不等式的線性方程式的解法。

我們要求的是非負整數解的個數，即 $x_i \ge 0$ 對於 $i=1, 2, 3, 4$。
不等式為 $x_1 + x_2 + x_3 + x_4 \le 7$。

為了將不等式轉換為等式，我們可以引入一個鬆弛變數（slack variable）$s \ge 0$。
令 $x_1 + x_2 + x_3 + x_4 + s = 7$，其中 $s$ 也是一個非負整數。
現在問題變為求解非負整數解的個數，即 $(x_1, x_2, x_3, x_4, s)$ 的組合。

這是一個標準的「隔板法」（stars and bars）問題。我們有 $n$ 個 items (stars) 要分給 $k$ 個 bins (variables)，其中 items 和 bins 都可以是空的（非負整數解）。
公式為 $\binom{n+k-1}{k-1}$ 或 $\binom{n+k-1}{n}$。

在這個問題中，我們有 7 個「stars」（總和為 7）要分配給 5 個變數（$x_1, x_2, x_3, x_4, s$）。
所以，$n = 7$ 且 $k = 5$。

使用隔板法公式，解的個數為：
$\binom{n+k-1}{k-1} = \binom{7+5-1}{5-1} = \binom{11}{4}$

計算 $\binom{11}{4}$：
$\binom{11}{4} = \frac{11!}{4!(11-4)!} = \frac{11!}{4!7!} = \frac{11 \times 10 \times 9 \times 8}{4 \times 3 \times 2 \times 1}$

本題考查函數的定義與計數，以及集合的基數（cardinality）。

已知集合 A 的基數 $|A| = 2^4 = 16$。
已知集合 B 的基數 $|B| = 2^3 = 8$。

我們需要計算從集合 A 到集合 B 的函數的個數。
一個函數 $f: A \to B$ 將集合 A 中的每一個元素映射到集合 B 中的一個元素。
對於集合 A 中的每一個元素 $a \in A$，我們有 $|B|$ 種選擇將它映射到 B 中的某個元素。

核心觀念

本題考查：

• 正交矩陣的性質；
• 向量長度在正交變換下保持不變；
• 若向量序列收斂至零向量，其長度也必須收斂至 $0$。

矩陣 $A$ 的兩個欄向量為

$$\begin{pmatrix} \frac35\\[2pt] \frac25 \end{pmatrix}, \qquad \begin{pmatrix} -\frac25\\[2pt] \frac35 \end{pmatrix}.$$

兩者長度皆為 $1$，且內積為

$$\frac35\left(-\frac25\right)+\frac25\left(\frac35\right)=0.$$

因此 $A$ 是正交矩陣，即

$$A^T A=I.$$

所以對任意向量 $y$，都有

$$\|Ay\|=\|y\|.$$

---

解題方法

由於 $A$ 是正交矩陣，連續作用 $n$ 次仍不改變向量長度：

$$\|A^n x\|=\|x\|.$$

其中

$$x= \begin{pmatrix} a\\ b \end{pmatrix}, \qquad \|x\|=\sqrt{a^2+b^2}.$$

題目給定

$$\lim_{n\to\infty}A^n x= \begin{pmatrix} 0\\ 0 \end{pmatrix}.$$

取長度後，得到

$$\lim_{n\to\infty}\|A^n x\|=0.$$

但因為 $\|A^n x\|=\|x\|$ 對所有 $n$ 都成立，因此

$$\|x\|=0.$$

故

核心觀念

本題考查：

• 線性轉換的矩陣表示；
• 矩陣運算
  $(M-I)+2I=M+I;$
• 行列式在相似變換下不變，因此即使題目未明確列出有序基底，仍可選用標準基底計算。

$P_2(\mathbb R)$ 的標準基底取為

$$\mathcal B=(1,x,x^2).$$

解題方法

對標準基底中的各元素計算 $T$：

$$T(1)=1+2(0)-0=1,$$ $$T(x)=x+2(1)-0=x+2,$$ $$T(x^2)=x^2+2(2x)-2=x^2+4x-2.$$

因此，$T$ 相對於基底 $\mathcal B$ 的矩陣為

$$M= \begin{pmatrix} 1&2&-2\\ 0&1&4\\ 0&0&1 \end{pmatrix}.$$

題目要求

$$\det\bigl((M-I)+2I\bigr)=\det(M+I).$$

計算得

核心觀念

本題考查矩陣的跡（trace）與特徵值：

• 跡的線性性：$\operatorname{tr}(X+Y)=\operatorname{tr}(X)+\operatorname{tr}(Y)$。
• 跡的循環性：$\operatorname{tr}(AB)=\operatorname{tr}(BA)$。
• $2\times2$ 矩陣的特徵多項式與判別式。
• 矩陣方程 $A^3=I$ 對特徵值的限制。

---

選項分析

(A) $\operatorname{tr}((A+B)C)=\operatorname{tr}(AC)+\operatorname{tr}(BC)$

由矩陣乘法對加法的分配律，

$$(A+B)C=AC+BC.$$

再利用跡的線性性，

$$\operatorname{tr}((A+B)C) =\operatorname{tr}(AC+BC) =\operatorname{tr}(AC)+\operatorname{tr}(BC).$$

因此 (A) 正確。

---

(B) $\operatorname{tr}(AB)=\operatorname{tr}(A)\operatorname{tr}(B)$

此敘述一般不成立。取 $B=I$，則

$$\operatorname{tr}(AB)=\operatorname{tr}(A),$$

但右側為

$$\operatorname{tr}(A)\operatorname{tr}(I) =n\operatorname{tr}(A).$$

當 $n>1$ 且 $\operatorname{tr}(A)\ne0$ 時，兩者不相等。

例如取 $A=I$、$B=I$，則

$$\operatorname{tr}(AB)=\operatorname{tr}(I)=n,$$

而

$$\operatorname{tr}(A)\operatorname{tr}(B)=n^2.$$

因此 (B) 錯誤。

---

(C) $\operatorname{tr}(AB)=\operatorname{tr}(BA)$

設

$$A=(a_{ij}),\qquad B=(b_{ij}).$$

則

$$\operatorname{tr}(AB) =\sum_{i=1}^n(AB)_{ii} =\sum_{i=1}^n\sum_{j=1}^n a_{ij}b_{ji}.$$

交換求和順序，

$$\operatorname{tr}(AB) =\sum_{j=1}^n\sum_{i=1}^n b_{ji}a_{ij} =\sum_{j=1}^n(BA)_{jj} =\operatorname{tr}(BA).$$

因此 (C) 正確。

注意此性質稱為跡的循環性，但一般不能任意改變多個矩陣的順序；例如 $\operatorname{tr}(ABC)=\operatorname{tr}(BCA)$，不代表等於 $\operatorname{tr}(ACB)$。

---

(D) 若

$$A= \begin{pmatrix} a&b\\ c&d \end{pmatrix}$$

本題考查矩陣的自由度（degree of freedom）概念。自由度是指獨立的參數個數。

1. 對稱矩陣 (Symmetric Matrix)
   一個 $n \times n$ 的對稱矩陣 $S$ 滿足 $S^T = S$。
   矩陣的元素 $S_{ij}$ 需要滿足 $S_{ij} = S_{ji}$。
   對角線上的元素 ($i=j$)，$n$ 個。
   非對角線上的元素，我們只需要考慮上三角（或下三角）部分，因為另一半由對稱性決定。
   上三角部分（不含對角線）的元素個數是 $\binom{n}{2} = \frac{n(n-1)}{2}$。
   所以，對稱矩陣的自由度 $d_S = n + \frac{n(n-1)}{2} = \frac{2n + n^2 - n}{2} = \frac{n^2 + n}{2} = \frac{n(n+1)}{2}$。

2. 對角矩陣 (Diagonal Matrix)
   一個 $n \times n$ 的對角矩陣 $D$ 的形式為 $D_{ii}$，所有非對角線元素為 0。
   我們只需要確定對角線上的 $n$ 個元素。
   所以，對角矩陣的自由度 $d_D = n$。

3. 正交矩陣 (Orthogonal Matrix)
   一個 $n \times n$ 的正交矩陣 $Q$ 滿足 $Q^T Q = I$ (或 $QQ^T = I$)。
   這意味著 $Q$ 的列向量（或行向量）構成一個標準正交基。
   對於第一個列向量，我們有 $n$ 個自由度（可以任意選擇）。
   對於第二個列向量，它必須與第一個列向量正交，且長度為 1。這將減少 1 個自由度（正交性）和 1 個自由度（長度為 1），共減少 2 個自由度。
   對於第三個列向量，它必須與前兩個列向量正交，且長度為 1。這將減少 2 個自由度。

核心觀念

本題為線性代數（Linear Algebra）的綜合觀念題，涵蓋以下核心主題：

1. 矩陣零空間（Nullspace）的等價性：實矩陣中 $\text{Null}(A) = \text{Null}(A^T A)$ 的性質。
2. 正交矩陣（Orthogonal Matrix）的特徵值幾何性質：正交矩陣在複數平面上的特徵值模長必為 $1$。
3. 矩陣對角化（Diagonalizability）的充要條件：具備 $n$ 個線性獨立特徵向量（即幾何重數等於代數重數），而非相異特徵值個數。
4. 實對稱矩陣與譜定理（Spectral Theorem）：實對稱矩陣特徵值必為實數，且對應「相異特徵值」的特徵向量互相正交。
5. 正定矩陣（Positive Definite Matrix）的平方根矩陣：正定矩陣必存在唯一的正定（非奇異）平方根矩陣 $U = A^{1/2}$。

---

解題方法與選項分析

(A) 正確

• 推導說明：
  要證明兩個子空間相同，需證明互相包含：
  1. 若 $x \in \text{Null}(A)$，則 $Ax = 0$。兩邊同左乘 $A^T$ 得 $A^T Ax = A^T 0 = 0$，故 $x \in \text{Null}(A^T A)$。這說明 $\text{Null}(A) \subseteq \text{Null}(A^T A)$。
  2. 若 $x \in \text{Null}(A^T A)$，則 $A^T Ax = 0$。兩邊同左乘 $x^T$： $$x^T A^T A x = 0 \implies (Ax)^T (Ax) = \|Ax\|^2 = 0$$ 由向量範數性質，$\|Ax\| = 0 \implies Ax = 0$，故 $x \in \text{Null}(A)$。這說明 $\text{Null}(A^T A) \subseteq \text{Null}(A)$。
• 結論：$\text{Null}(A) = \text{Null}(A^T A)$ 恆成立。

---

(B) 正確

• 推導說明：
  矩陣 $A + \frac{1}{2}I$ 為不可逆（singular）$\iff \det(A + \frac{1}{2}I) = 0 \iff \det(A - (-\frac{1}{2})I) = 0 \iff -\frac{1}{2}$ 為 $A$ 的特徵值。
  若 $A$ 為正交矩陣（$A^T A = I$），對於 $A$ 的任意複數特徵值 $\lambda$ 及其對應特徵向量 $v \neq 0$： $$\|Av\|^2 = (Av)^H (Av) = v^H A^T A v = v^H v = \|v\|^2$$ 另一方面： $$\|Av\|^2 = \|\lambda v\|^2 = |\lambda|^2 \|v\|^2$$ 因此 $|\lambda|^2 = 1 \implies |\lambda| = 1$，即正交矩陣的所有特徵值模長必為 $1$。
  由於 $|-\frac{1}{2}| = \frac{1}{2} \neq 1$，故 $-\frac{1}{2}$ 絕不可能是正交矩陣 $A$ 的特徵值。
• 結論：$\det(A + \frac{1}{2}I) \neq 0$，$A + \frac{1}{2}I$ 必為可逆矩陣。

---

本題考查線性代數中自伴算子（self-adjoint operator）的性質，包括特徵值、特徵空間、正交投影以及譜定理。

自伴算子（self-adjoint operator）在實內積空間上等價於對稱矩陣。
根據譜定理（Spectral Theorem），對於有限維實內積空間上的自伴算子 $T$，存在一組由 $T$ 的特徵向量構成的正交基，且對應的特徵值是實數。

我們逐一分析每個敘述的正確性。

(A) $\sum_{i=1}^k \lambda_i P_i = T$
這實際上是譜定理的一個表達形式。
對於自伴算子 $T$ 在有限維內積空間 $V$ 上，如果 $\lambda_1, \dots, \lambda_k$ 是其所有的相異特徵值，且 $E_i$ 是對應於 $\lambda_i$ 的特徵空間，那麼 $V = E_1 \oplus E_2 \oplus \dots \oplus E_k$。
$P_i$ 是到 $E_i$ 的正交投影算子。
那麼，任意向量 $v \in V$ 可以唯一地寫成 $v = v_1 + v_2 + \dots + v_k$，其中 $v_i \in E_i$。
$T(v) = T(v_1 + \dots + v_k) = T(v_1) + \dots + T(v_k)$ (線性)。
因為 $v_i \in E_i$, $T(v_i) = \lambda_i v_i$。
所以 $T(v) = \lambda_1 v_1 + \dots + \lambda_k v_k$。
另一方面，$P_i(v) = v_i$ (因為 $v_i$ 是 $v$ 在 $E_i$ 上的投影，且 $E_i$ 是閉子空間，並且 $v_j$ 在 $E_i$ 上的投影為 0 當 $j \ne i$)。
所以，$\sum_{i=1}^k \lambda_i P_i (v) = \sum_{i=1}^k \lambda_i v_i = \lambda_1 v_1 + \dots + \lambda_k v_k$。
因此，$T(v) = \sum_{i=1}^k \lambda_i P_i (v)$ 對於所有 $v \in V$ 成立。
這意味著算子 $T = \sum_{i=1}^k \lambda_i P_i$。
這個敘述是正確的。

(B) $V = E_1 \oplus E_2 \oplus \dots \oplus E_k$
如上所述，譜定理保證了 $V$ 是其所有特徵空間的直和。
$E_i$ 是對應於特徵值 $\lambda_i$ 的特徵空間。
由於 $\lambda_i$ 是相異的，每個 $E_i$ 是非零的。
並且 $\sum_{i=1}^k \dim(E_i) = n$ (矩陣的維度)。
所以 $V = E_1 \oplus E_2 \oplus \dots \oplus E_k$。
這個敘述是正確的。

(C) Given any polynomial $g$, $g(T) = g(\lambda_1)P_1 + g(\lambda_2)P_2 + \dots + g(\lambda_k)P_k$.
令 $g(x) = c_m x^m + \dots + c_1 x + c_0$。
$g(T) = c_m T^m + \dots + c_1 T + c_0 I$。
對於 $v \in E_j$， $T(v) = \lambda_j v$。