111 年 國立成功大學資訊工程系碩士班《計算機數學》

核心觀念

長度為 $20$ 的位元字串中，每個位置都可填入 $0$ 或 $1$，所以全部字串數為 $2^{20}$。「至多十九個 $1$」表示 $1$ 的個數可以是 $0$ 到 $19$，唯一不符合條件的是含有二十個 $1$ 的字串。

解題方法

先計算所有長度為 $20$ 的位元字串，再扣除唯一不符合條件的字串：

$$2^{20}-1$$

核心觀念

這題考查最小生成樹的環交換性質：在一棵最小生成樹中加入一條不在樹內的邊，會形成一個環；從該環移除另一條邊，仍會得到一棵生成樹。

設邊 $e=(u,v)$ 是圖 $G$ 中權重最小的邊，因此對每條邊 $f$ 都有 $w(e)\leq w(f)$。

解題方法

取 $G$ 的任意一棵最小生成樹 $T$。

若 $e\in T$，則 $e$ 已屬於一棵最小生成樹，命題成立。

若 $e\notin T$，將 $e$ 加入 $T$。因為 $T$ 原本連通且沒有環，加入 $e$ 後會形成一個環。這個環包含 $e$，也包含 $T$ 中連接 $u$ 與 $v$ 的路徑。從該環中選一條不同於 $e$ 的邊 $f$，並將 $f$ 刪除，得到圖 $T'$。

核心觀念

• 有限集合 $S$ 的冪集 $\mathcal{P}(S)$，是由 $S$ 的所有子集合組成的集合；若 $|S|=n$，則 $|\mathcal{P}(S)|=2^n$。
• 笛卡兒積 $A\times B$ 包含所有第一個元素取自 $A$、第二個元素取自 $B$ 的有序對，因此 $|A\times B|=|A||B|$。
• 空集合的冪集只有一個元素：空集合本身，所以 $|\mathcal{P}(\varnothing)|=1$。

解題方法

集合 $A=\{5,6,7,8\}$ 有 $4$ 個元素，因此

$$a=|\mathcal{P}(A)|=2^4=16$$

核心觀念

正多邊形的任四個不同頂點，依圓周順序連接後，都會形成唯一的四邊形。因此，(a) 是從 $n$ 個頂點中選出 $4$ 個；(b) 則要額外限制所選頂點之間不能有相鄰的一對。

(a) 不加限制的四邊形數

任選 $4$ 個頂點，就確定一個四邊形，所以共有

$$\binom{n}{4}$$

個。

(b) 四邊形不能有正多邊形的邊作為邊

四邊形若包含正多邊形的一條邊，代表它選到了一對沿正多邊形圓周相鄰的頂點。因此，本題等同於：在 $n$ 個圓周排列的頂點中，選出 $4$ 個，且任兩個被選頂點都不相鄰。

沿圓周依序看四個被選頂點，它們之間各有一段未選頂點。因為被選頂點不能相鄰，每一段至少要有 $1$ 個未選頂點。總共有 $n-4$ 個未選頂點，分配至四段。

核心觀念

圖的色數 $\chi(G)$ 是使所有相鄰頂點顏色不同時，所需的最少顏色數。求色數可分成兩步：

• 下界：證明三種顏色不足。
• 上界：給出合法的四種顏色著色。

兩者成立，即可確定 $\chi(G)=4$。

解題方法

圖中外圈有十個頂點，依標號排列為 $v_1,v_2,\ldots,v_{10}$；邊包括外圈相鄰頂點的連線、隔一個頂點的連線，以及相對頂點的連線。中央只是線段交叉處，不是頂點。

一、證明三色無法完成著色

外圈任意連續三個頂點 $v_i,v_{i+1},v_{i+2}$ 均兩兩相鄰，因此形成三角形，必須使用三種不同顏色。

假設全圖可用三種顏色著色。比較相鄰的兩個三角形
$\{v_i,v_{i+1},v_{i+2}\}$ 與 $\{v_{i+1},v_{i+2},v_{i+3}\}$，其中 $v_i$ 與 $v_{i+3}$ 都必須使用不同於 $v_{i+1},v_{i+2}$ 的第三種顏色，所以

$$c(v_{i+3})=c(v_i).$$

因此，顏色被迫每三個頂點重複，得到

$$c(v_1)=c(v_4)=c(v_7)=c(v_{10}).$$

核心觀念

圖的色數 $\chi(G)$ 是使每條邊的兩端皆不同色所需的最少顏色數。要證明 $\chi(G)=4$，必須同時證明「三色無法完成合法著色」及「四色可以完成合法著色」。

解題方法

原圖有外側五邊形與內側五角星，各含 $5$ 個頂點；每個外側頂點連到兩個內側頂點，共有 $10$ 條內外連接邊。線段交叉處若沒有黑點，就不算頂點。

將外側頂點由最上方開始，順時針標為 $v_1,v_2,v_3,v_4,v_5$；將位於外側邊 $v_iv_{i+1}$ 內側、且同時連到這兩端的內側頂點標為 $u_i$，其中 $v_6=v_1$。因此，$u_1$ 位於內側右上方，依序為右下方、下方、左下方、左上方。

內側五角星的邊為

$$u_1u_3,\quad u_1u_4,\quad u_2u_4,\quad u_2u_5,\quad u_3u_5.$$

一、證明三色不夠

假設可以用三色著色。外側是五邊形奇環，因此必須用到三色；每種顏色最多出現兩次，故顏色出現次數必為 $2,2,1$。

利用旋轉標號及交換顏色名稱，可將外側顏色寫成

$$\bigl(c(v_1),c(v_2),c(v_3),c(v_4),c(v_5)\bigr) =(3,1,2,1,2).$$

核心觀念

Rayleigh 商是 Hermitian 矩陣的特徵值加權平均。利用正交規一特徵向量展開 $x$，分子可化成特徵值的加權和，分母則是係數平方絕對值的總和。

**題目有一處定義域需留意：**對一般 Hermitian 矩陣，特徵向量可能是複數，因此標準 Rayleigh 商定理的向量範圍是 $\mathbb{C}^n$。若要限定 $x\in\mathbb{R}^n$，則需假設 $A$ 是實對稱矩陣，才能保證第 (c) 小題成立。

解題方法

設 $A$ 的正交規一特徵向量為 $u_1,\ldots,u_n$，滿足

$$Au_i=\lambda_i u_i,\qquad u_i^H u_j= \begin{cases} 1,&i=j,\\ 0,&i\ne j. \end{cases}$$

將非零向量 $x$ 展開為

$$x=\sum_{i=1}^{n}c_i u_i.$$

由於特徵向量構成一組正交規一基底，係數向量 $c=(c_1,\ldots,c_n)^T$ 滿足

$$x^H x=\sum_{i=1}^{n}|c_i|^2=\|c\|^2.$$

另一方面，利用 $Au_i=\lambda_i u_i$，以及特徵向量的正交性，

$$\begin{aligned} x^H A x &=\left(\sum_{i=1}^{n}c_i u_i\right)^H A\left(\sum_{j=1}^{n}c_j u_j\right)\\ &=\sum_{i=1}^{n}\sum_{j=1}^{n}\overline{c_i}c_j\lambda_j u_i^H u_j\\ &=\sum_{i=1}^{n}|c_i|^2\lambda_i. \end{aligned}$$

(a) 推導 Rayleigh 商公式

代入 Rayleigh 商的定義：

$$\rho(x)=\frac{x^H A x}{x^H x} =\frac{\sum_{i=1}^{n}|c_i|^2\lambda_i}{\sum_{i=1}^{n}|c_i|^2} =\frac{|c_1|^2\lambda_1+\cdots+|c_n|^2\lambda_n}{\|c\|^2}.$$

因此所求公式成立。

(b) 證明上下界

令

$$w_i=\frac{|c_i|^2}{\|c\|^2}.$$

因為 $x\ne 0$，所以 $\|c\|^2>0$；又 $|c_i|^2\ge 0$，故 $w_i\ge 0$，且

$$\sum_{i=1}^{n}w_i=1.$$

由 $\lambda_n\le\lambda_i\le\lambda_1$，將每項乘上非負的 $w_i$ 再加總，可得

核心觀念

這題考的是 Frobenius 範數、矩陣內積與跡的連結。對 $A,B\in\mathbb{R}^{m\times n}$，Frobenius 內積為

$$\langle A,B\rangle_F=\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}b_{ij} =\operatorname{tr}(A^T B).$$

因此，Frobenius 範數平方可寫成矩陣與自身的內積：

$$\|A\|_F^2=\langle A,A\rangle_F.$$

以下分別依照題目定義，以矩陣乘法與跡的定義證明兩式。

解題方法

(a) 證明 $\|A\|_F^2=\operatorname{tr}(A^T A)$

矩陣 $A^T A$ 的大小為 $n\times n$。其第 $j$ 個對角元素為

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

將所有對角元素相加，即為跡：

$$\operatorname{tr}(A^T A) =\sum_{j=1}^{n}(A^T A)_{jj} =\sum_{j=1}^{n}\sum_{i=1}^{m}a_{ij}^2 =\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}^2.$$

由 Frobenius 範數的定義，

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

所以

$$\boxed{\|A\|_F^2=\operatorname{tr}(A^T A)}.$$

(b) 證明 $\|A+B\|_F^2=\|A\|_F^2+2\operatorname{tr}(A^T B)+\|B\|_F^2$

將 (a) 套用在矩陣 $A+B$：

核心觀念

矩陣指數由冪級數定義：

$$e^A=\sum_{k=0}^{\infty}\frac{A^k}{k!}.$$

本題要證明兩件事：$e^A$ 的轉置等於自身，因此是對稱矩陣；對每個非零實向量 $x$，二次型 $x^T e^A x$ 都嚴格大於 $0$，因此 $e^A$ 是正定矩陣。以下採用實對稱矩陣的慣例。

解題方法

由於 $A$ 是實對稱矩陣，根據譜定理，存在正交矩陣 $Q$ 與實數特徵值 $\lambda_1,\ldots,\lambda_n$，使得

$$A=Q\Lambda Q^T, \qquad \Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_n), \qquad Q^TQ=I.$$

利用矩陣指數的冪級數定義，可得

$$e^A =Qe^\Lambda Q^T =Q\operatorname{diag}(e^{\lambda_1},\ldots,e^{\lambda_n})Q^T.$$

證明對稱性： 對上式取轉置：

核心觀念

對實對稱矩陣 $M$：

• 若對所有非零向量 $x$，都有 $x^T Mx\ge 0$，則 $M$ 為正半定。
• 若對所有非零向量 $x$，都有 $x^T Mx>0$，則 $M$ 為正定。

矩陣 $A^T A$ 是對稱矩陣，因為 $(A^T A)^T=A^T A$。判斷其正半定或正定，可直接計算二次型 $x^T A^T A x$。

解題方法

任取向量 $x\in\mathbb{R}^n$，有

$$x^T A^T A x=(Ax)^T(Ax)=\|Ax\|_2^2\ge 0.$$

因此，對所有 $x$，二次型皆非負，故 $A^T A$ 為正半定。