111 年 國立成功大學電機資訊學院碩士班─資訊聯招《計算機數學》

核心觀念

長度為 $20$ 的位元字串，每一位皆可為 $0$ 或 $1$，因此不加限制時共有

$$2^{20}$$

個位元字串。

題目要求「至多十九個 $1$」，也就是允許有 $0,1,2,\ldots,19$ 個 $1$，唯一不符合條件的情形是全部 $20$ 位都是 $1$：

$$111\cdots111$$

因此，符合條件的位元字串數量為

$$2^{20}-1.$$

解題方法

亦可用組合數表示：

$$\sum_{k=0}^{19}\binom{20}{k} = \sum_{k=0}^{20}\binom{20}{k}-\binom{20}{20} = 2^{20}-1.$$

其中使用二項式定理：

$$\sum_{k=0}^{20}\binom{20}{k}=(1+1)^{20}=2^{20}.$$

題目格式的說明

題目明確寫成

$$A\cdot B+C$$

但未指定 $A$、$B$、$C$ 必須是何種數字、是否要求最簡形式，因此同一個數可以有無限多種表示方式。例如：

這題是圖論中關於最小生成樹（Minimum Spanning Tree, MST）的一個基本性質證明，稱為「切點定理」（Cut Property）或「最小權邊定理」。

核心觀念： 證明一個圖的最小生成樹（MST）存在性的一種基本性質，即任何一條連接切點兩側的最小權重邊，必定屬於某個 MST。

證明：
假設 G 是一個連通圖，其中 $(u, v)$ 是一條最小權重的邊。我們需要證明 $(u, v)$ 屬於 G 的某個最小生成樹。

考慮一個切點（cut）S，它將圖 G 的頂點集合 V 分成兩個非空子集 $S$ 和 $V \setminus S$。
邊 $(u, v)$ 是一條連接 $S$ 和 $V \setminus S$ 的邊，其中 $u \in S$ 且 $v \in V \setminus S$（或者 $u \in V \setminus S$ 且 $v \in S$）。
假設 $(u, v)$ 是所有連接 $S$ 和 $V \setminus S$ 的邊中權重最小的。

令 T 為 G 的任意一個最小生成樹。
我們分兩種情況討論：

情況 1：邊 $(u, v)$ 已經在 T 中。
如果 $(u, v)$ 已經是 T 的一部分，那麼證明就完成了，因為 T 是一個最小生成樹，而 $(u, v)$ 屬於 T。

情況 2：邊 $(u, v)$ 不在 T 中。
如果 $(u, v)$ 不在 T 中，那麼當我們將邊 $(u, v)$ 加入 T 時，T 中必然會形成一個環。
這個環包含邊 $(u, v)$ 以及 T 中連接 $u$ 和 $v$ 的唯一路徑。
假設 T 中連接 $u$ 和 $v$ 的路徑上的邊集合為 $P = \{e_1, e_2, ..., e_k\}$。
那麼，由 T 和 $(u, v)$ 組成的環 C 上的邊為 $\{(u, v)\} \cup P$。

由於 $(u, v)$ 是連接切點 $S$ 和 $V \setminus S$ 的最小權重邊，且 $u \in S, v \in V \setminus S$，
那麼環 C 上的其他邊 $e_i \in P$ 必定至少有一條邊連接 $S$ 和 $V \setminus S$。
否則，如果 P 上的所有邊都只連接 $S$ 內部的頂點或 $V \setminus S$ 內部的頂點，那麼 $u$ 和 $v$ 在 T 中就無法被連通，這與 T 是連通圖的生成樹矛盾。
因此，環 C 上的至少一條邊 $e_j \in P$ 必定連接 $S$ 和 $V \setminus S$。

這題考驗集合論中的基本概念，包括集合的基數、冪集（Power Set）的定義，以及笛卡爾積（Cartesian Product）的計算。

核心觀念：

1. 集合的基數 (Cardinality)： 集合中元素的個數，記為 $|S|$。
2. 冪集 (Power Set)： 一個集合的所有子集的集合，記為 $P(S)$ 或 $2^S$。如果集合 $S$ 有 $n$ 個元素，那麼其冪集 $P(S)$ 的基數為 $|P(S)| = 2^n$。
3. 笛卡爾積 (Cartesian Product)： 兩個集合 $A$ 和 $B$ 的笛卡爾積 $A \times B$ 是所有有序對 $(a, b)$ 的集合，其中 $a \in A$ 且 $b \in B$。如果 $|A|=m$ 且 $|B|=n$，那麼 $|A \times B| = m \times n$。

題目分析與計算：
給定三個集合：
$A = \{5, 6, 7, 8\}$
$B = \{u, v\}$
$C = \{\}$ (空集合)

計算以下值：

1. $a = |Power Set(A)|$
   集合 $A$ 有 4 個元素：$|A| = 4$。
   $Power Set(A)$ 是集合 $A$ 的所有子集的集合。
   其基數為 $2^{|A|} = 2^4$。
   $a = 2^4 = 16$。

核心觀念

本題使用兩個觀念：

1. 從正 $n$ 邊形的 $n$ 個頂點中選出 $4$ 個頂點，每組頂點唯一決定一個四邊形。
2. (b) 額外限制所選頂點之間不能相鄰，因此轉化為「圓排列中選取 $4$ 個互不相鄰頂點」的問題。

組合數公式為

$$\binom{n}{4}=\frac{n(n-1)(n-2)(n-3)}{24}.$$

---

(a) 任意四邊形的數量

正多邊形為凸多邊形，任取其中 $4$ 個不同頂點，依照頂點在多邊形上的順序連接，即可得到唯一的四邊形。

因此只需從 $n$ 個頂點中選取 $4$ 個：

$$\binom{n}{4} = \frac{n(n-1)(n-2)(n-3)}{24}.$$

所以四邊形總數為

$$\boxed{\binom{n}{4}}.$$

---

(b) 四邊形的邊不可為正多邊形的邊

解題方法

將正 $n$ 邊形的頂點沿著圓周編號。若所選的四個頂點中有兩個相鄰，這兩點連成的線段就是原正多邊形的一條邊，不符合題目要求。

因此，所選的四個頂點必須兩兩不相鄰。

設依圓周順序選出的四個頂點為 $A_1,A_2,A_3,A_4$，並令

• $x_1$：$A_1$ 與 $A_2$ 之間未選取的頂點數；
• $x_2$：$A_2$ 與 $A_3$ 之間未選取的頂點數；
• $x_3$：$A_3$ 與 $A_4$ 之間未選取的頂點數；
• $x_4$：$A_4$ 與 $A_1$ 之間未選取的頂點數。

因為任意兩個所選頂點不可相鄰，所以每個間隔至少要有一個未選取頂點：

$$x_i\geq 1\qquad (i=1,2,3,4).$$

四個所選頂點之外共有 $n-4$ 個未選取頂點，因此

$$x_1+x_2+x_3+x_4=n-4.$$

正整數解的數量為

核心觀念

圖的染色數 $\chi(G)$ 是使相鄰頂點具有不同顏色時，所需的最少顏色數。

判斷方式：

• 若圖中含有三角形，則 $\chi(G)\ge 3$。
• 若能明確給出三種顏色的合法配置，則 $\chi(G)\le 3$。
• 上下界相同時，即可確定 $\chi(G)=3$。

Figure (a)

此圖為輪圖：外圍是偶數個頂點組成的環，中央頂點與所有外圍頂點相鄰。

外圍環可使用兩種顏色交替染色：

$$v_1,v_3,v_5,v_7,v_9：\text{顏色 1}$$ $$v_2,v_4,v_6,v_8,v_{10}：\text{顏色 2}$$

中央頂點與所有外圍頂點相鄰，因此使用第三種顏色。故：

$$\chi(G)\le 3$$

此外，中央頂點與外圍任一條邊形成三角形，因此至少需要三種顏色：

$$\chi(G)\ge 3$$

所以：

$$\boxed{\chi(\text{figure(a)})=3}$$

Figure (b)

這題考驗線性代數中關於特徵值、特徵向量以及 Rayleigh quotient 的性質。

核心觀念：

• Hermitian Matrix： 自共軛矩陣，即 $A^H = A$。對於實數矩陣，Hermitian 矩陣就是對稱矩陣 ($A^T = A$)。Hermitian 矩陣的特徵值是實數，且存在一組標準正交的特徵向量。
• 特徵值與特徵向量： 對於矩陣 $A$，若 $Ax = \lambda x$ 且 $x \ne 0$，則 $\lambda$ 是特徵值， $x$ 是對應的特徵向量。
• 標準正交基： 一組互相正交且長度為 1 的向量 $\{u_1, \dots, u_n\}$。對於任何向量 $x$，都可以表示為這些基向量的線性組合：$x = c_1 u_1 + \dots + c_n u_n$。
• 內積： 在複數向量空間中，對於向量 $x, y$，內積定義為 $(y, x) = y^H x$。對於實數向量空間，$(y, x) = y^T x$。這裡題目用了 $(Ax, x)$，通常表示 $x^H A x$。
• Rayleigh Quotient： $\rho(x) = \frac{x^H A x}{x^H x}$。

題目分析與證明：

給定一個 Hermitian 矩陣 $A$，其特徵值為 $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$，對應的標準正交特徵向量為 $u_1, \dots, u_n$。
對於任何非零向量 $x \in \mathbb{R}^n$（或 $\mathbb{C}^n$），Rayleigh quotient 定義為 $\rho(x) = \frac{x^H A x}{x^H x}$。

(a) 證明當 $x = c_1 u_1 + \dots + c_n u_n$ 時，Rayleigh quotient 的形式。

由於 $\{u_1, \dots, u_n\}$ 是標準正交基，任何向量 $x$ 都可以表示為這些基向量的線性組合。
$x = \sum_{i=1}^n c_i u_i$
$x^H = (\sum_{i=1}^n c_i u_i)^H = \sum_{i=1}^n \bar{c_i} u_i^H$ （這裡 $\bar{c_i}$ 是 $c_i$ 的複數共軛）

首先計算分母 $x^H x$:
$x^H x = (\sum_{i=1}^n \bar{c_i} u_i^H) (\sum_{j=1}^n c_j u_j)$
$= \sum_{i=1}^n \sum_{j=1}^n \bar{c_i} c_j (u_i^H u_j)$
由於 $\{u_1, \dots, u_n\}$ 是標準正交基，所以 $u_i^H u_j = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{if } i \ne j \end{cases}$。
因此，
$x^H x = \sum_{i=1}^n \bar{c_i} c_i (u_i^H u_i) = \sum_{i=1}^n |c_i|^2 \cdot 1 = \sum_{i=1}^n |c_i|^2$。

接下來計算分子 $x^H A x$:
$A x = A (\sum_{j=1}^n c_j u_j)$
由於 $u_j$ 是 $A$ 的特徵向量，對應的特徵值是 $\lambda_j$，即 $A u_j = \lambda_j u_j$。
所以，$A x = \sum_{j=1}^n c_j (A u_j) = \sum_{j=1}^n c_j (\lambda_j u_j) = \sum_{j=1}^n \lambda_j c_j u_j$。

現在計算 $x^H (A x)$:
$x^H (A x) = (\sum_{i=1}^n \bar{c_i} u_i^H) (\sum_{j=1}^n \lambda_j c_j u_j)$
$= \sum_{i=1}^n \sum_{j=1}^n \bar{c_i} (\lambda_j c_j) (u_i^H u_j)$
再次利用標準正交性 $u_i^H u_j = \delta_{ij}$：
$x^H A x = \sum_{i=1}^n \bar{c_i} (\lambda_i c_i) (u_i^H u_i)$ （因為只有當 $i=j$ 時，項才不為零）
$= \sum_{i=1}^n \lambda_i \bar{c_i} c_i = \sum_{i=1}^n \lambda_i |c_i|^2$。

將分子和分母組合起來，得到 Rayleigh quotient：
$\rho(x) = \frac{x^H A x}{x^H x} = \frac{\sum_{i=1}^n \lambda_i |c_i|^2}{\sum_{i=1}^n |c_i|^2}$。
這與題目要求的形式一致（將 $i$ 寫成 $1, 2, \dots, n$）。

(b) 證明 $\lambda_n \le \rho(x) \le \lambda_1$。

核心觀念

本題考查 Frobenius norm（Frobenius 範數）與矩陣內積的關係。

對於 $m\times n$ 矩陣 $A=(a_{ij})$，Frobenius 範數定義為

$$\|A\|_F=\sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}^2}.$$

此外，矩陣 $A^TA$ 為 $n\times n$ 矩陣，其對角線元素可表示為

$$(A^TA)_{jj}=\sum_{i=1}^{m}a_{ij}^2.$$

因此，$tr(A^TA)$ 正好會累加矩陣 $A$ 的所有元素平方。

---

（a）證明 $\|A\|_F=\sqrt{tr(A^TA)}$

由矩陣乘法，

$$(A^TA)_{jj} = \sum_{i=1}^{m}(A^T)_{ji}A_{ij} = \sum_{i=1}^{m}a_{ij}^2.$$

所以 $A^TA$ 的跡為

$$\begin{aligned} tr(A^TA) &=\sum_{j=1}^{n}(A^TA)_{jj}\\ &=\sum_{j=1}^{n}\sum_{i=1}^{m}a_{ij}^2\\ &=\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}^2. \end{aligned}$$

根據 Frobenius 範數的定義，

$$\|A\|_F = \sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}^2} = \sqrt{tr(A^TA)}.$$

因此，

$$\boxed{\|A\|_F=\sqrt{tr(A^TA)}}.$$

---

（b）Frobenius 範數平方的展開

題目原式寫成

$$\|A+B\|_F=\|A\|_F+2tr(A^TB)+\|B\|_F$$

此式一般不成立。以 $m=n=1$ 且 $A=B=[1]$ 為例：

$$\|A+B\|_F=2,$$

但右側為

$$1+2(1)(1)+1=4.$$

正確的恆等式應為

$$\boxed{\|A+B\|_F^2 = \|A\|_F^2+2tr(A^TB)+\|B\|_F^2}.$$

以下證明此正確形式。

由（a）可得

這題考驗線性代數中關於矩陣指數函數 (Matrix Exponential) 的性質，以及對稱矩陣和正定矩陣的定義。

核心觀念：

• 對稱矩陣 (Symmetric Matrix)： $A^T = A$。
• 正定矩陣 (Positive Definite Matrix)： 對稱矩陣 $M$ 是正定的，如果對於所有非零向量 $x$，都有 $x^T M x > 0$。
• 矩陣指數函數 (Matrix Exponential)： 對於方陣 $A$，其指數函數定義為：
  $e^A = \sum_{k=0}^{\infty} \frac{A^k}{k!} = I + A + \frac{A^2}{2!} + \frac{A^3}{3!} + \dots$
  其中 $A^0 = I$ (單位矩陣)。
• 性質：
  • 如果 $A$ 是對稱矩陣，那麼 $A^k$ 對於所有非負整數 $k$ 也是對稱矩陣。
  • 如果 $M$ 是正定矩陣，那麼 $M$ 也是對稱矩陣。

題目分析與證明：
給定一個對稱 $n \times n$ 矩陣 $A$。我們需要證明 $e^A$ 是對稱矩陣且是正定矩陣。

第一部分：證明 $e^A$ 是對稱矩陣。

一個矩陣 $M$ 是對稱的，當且僅當 $M^T = M$。
我們需要證明 $(e^A)^T = e^A$。

首先，我們知道如果 $A$ 是對稱矩陣，那麼 $A^T = A$。
對於任意非負整數 $k$，矩陣 $A^k$ 的轉置是 $(A^k)^T = (A^T)^k$。
由於 $A$ 是對稱的， $A^T = A$。
所以，$(A^k)^T = (A^T)^k = A^k$。
這意味著 $A^k$ 對於所有 $k \ge 0$ 都是對稱矩陣。

現在考慮 $e^A$ 的定義：
$e^A = I + A + \frac{A^2}{2!} + \frac{A^3}{3!} + \dots = \sum_{k=0}^{\infty} \frac{A^k}{k!}$。
對 $e^A$ 取轉置：
$(e^A)^T = (\sum_{k=0}^{\infty} \frac{A^k}{k!})^T$
由於轉置運算和求和運算可以交換順序：
$(e^A)^T = \sum_{k=0}^{\infty} (\frac{A^k}{k!})^T$
$= \sum_{k=0}^{\infty} \frac{1}{k!} (A^k)^T$
由於我們已經證明了 $(A^k)^T = A^k$：

這題考驗線性代數中關於矩陣的奇異性 (Singularity)、半正定 (Positive Semidefinite) 和正定 (Positive Definite) 的性質。

核心觀念：

• 奇異矩陣 (Singular Matrix)： 方陣 $A$ 是奇異的，當且僅當其行列式為零 ($\det(A) = 0$)，或者其零空間 (Null Space) 包含非零向量，或者其秩 (Rank) 小於 $n$。
• 半正定矩陣 (Positive Semidefinite Matrix, PSD)： 對稱矩陣 $M$ 是半正定的，如果對於所有非零向量 $x$，都有 $x^T M x \ge 0$。
• 正定矩陣 (Positive Definite Matrix, PD)： 對稱矩陣 $M$ 是正定的，如果對於所有非零向量 $x$，都有 $x^T M x > 0$。
• 矩陣 $A^T A$ 的性質： 對於任何實數矩陣 $A$，矩陣 $A^T A$ 總是半正定的。如果 $A$ 的列是線性獨立的（即 $A$ 的秩為 $n$），那麼 $A^T A$ 是正定的。

題目分析與證明：
給定一個奇異的 $n \times n$ 矩陣 $A$。我們需要證明 $A^T A$ 是半正定的，但不是正定的。

第一部分：證明 $A^T A$ 是半正定的。

首先，我們知道對於任何實數矩陣 $A$，矩陣 $A^T A$ 總是半正定的。
證明如下：
對於任意向量 $x \in \mathbb{R}^n$，考慮 $x^T (A^T A) x$。
$x^T (A^T A) x = (x^T A^T) (A x)$
令 $y = A x$。則 $y$ 是一個 $n \times 1$ 的向量。
$x^T A^T = (A x)^T = y^T$。
所以，$x^T (A^T A) x = y^T y$。
$y^T y$ 是向量 $y$ 與其自身的點積（或歐幾里得內積），其值等於 $y$ 的所有元素平方和：
$y^T y = \sum_{i=1}^n y_i^2$。
由於平方和總是 الدوال非負的，所以 $y^T y \ge 0$。