109 年 國立成功大學人工智慧科技碩士學位學程《計算機數學》

核心觀念

本題考查：

• 矩陣平方與秩的關係。
• 線性映射的合成與標準矩陣表示。
• 線性算子的加法。
• 最小平方法解的唯一性。
• 正交歸一向量組與投影矩陣。

---

解題方法與選項分析

（a）錯誤

相同的秩不代表矩陣平方後的秩相同。

取

$$A= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix}, \qquad B= \begin{bmatrix} 0&1\\ 0&0 \end{bmatrix}.$$

兩者皆為秩 $1$ 的矩陣：

$$\operatorname{rank}(A)=\operatorname{rank}(B)=1.$$

但是

$$A^2= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix},$$

因此

$$\operatorname{rank}(A^2)=1.$$

而

$$B^2= \begin{bmatrix} 0&1\\ 0&0 \end{bmatrix} \begin{bmatrix} 0&1\\ 0&0 \end{bmatrix} = \begin{bmatrix} 0&0\\ 0&0 \end{bmatrix},$$

所以

$$\operatorname{rank}(B^2)=0.$$

故相同秩的 $A,B$，其平方的秩不一定相同。

---

（b）正確

因為 $L$ 是線性算子，對任意 $\mathbf{x},\mathbf{y}\in\mathbb{R}^2$ 與純量 $c$，有

$$L(\mathbf{x}+\mathbf{y})=L(\mathbf{x})+L(\mathbf{y}),$$

以及

$$L(c\mathbf{x})=cL(\mathbf{x}).$$

定義

$$L^2(\mathbf{x})=L(L(\mathbf{x})).$$

則

$$\begin{aligned} L^2(\mathbf{x}+\mathbf{y}) &=L\bigl(L(\mathbf{x}+\mathbf{y})\bigr)\\ &=L\bigl(L(\mathbf{x})+L(\mathbf{y})\bigr)\\ &=L(L(\mathbf{x}))+L(L(\mathbf{y}))\\ &=L^2(\mathbf{x})+L^2(\mathbf{y}), \end{aligned}$$

且

$$\begin{aligned} L^2(c\mathbf{x}) &=L\bigl(L(c\mathbf{x})\bigr)\\ &=L\bigl(cL(\mathbf{x})\bigr)\\ &=cL(L(\mathbf{x}))\\ &=cL^2(\mathbf{x}). \end{aligned}$$

因此 $L^2$ 是線性算子。

若 $A$ 是 $L$ 的標準矩陣表示，則

$$L(\mathbf{x})=A\mathbf{x}.$$

因此

$$L^2(\mathbf{x}) =L(A\mathbf{x}) =A(A\mathbf{x}) =A^2\mathbf{x}.$$

所以 $L^2$ 的標準矩陣表示為 $A^2$。

---

（c）正確

定義

$$(L_1+L_2)(\mathbf{v}) =L_1(\mathbf{v})+L_2(\mathbf{v}).$$

對任意 $\mathbf{u},\mathbf{v}\in V$，由 $L_1,L_2$ 的線性性，

核心觀念

本題考查 Gram–Schmidt 正交化法，以及矩陣的 QR 分解。

設矩陣 $A$ 的欄向量為

$$A=\begin{bmatrix} \boldsymbol a_1 & \boldsymbol a_2 & \boldsymbol a_3 \end{bmatrix}.$$

Gram–Schmidt 法依序建立正交單位向量 $\boldsymbol q_1,\boldsymbol q_2,\boldsymbol q_3$：

$$\boldsymbol u_1=\boldsymbol a_1,\qquad \boldsymbol q_1=\frac{\boldsymbol u_1}{\|\boldsymbol u_1\|},$$ $$\boldsymbol u_k = \boldsymbol a_k-\sum_{j=1}^{k-1} (\boldsymbol q_j^{T}\boldsymbol a_k)\boldsymbol q_j, \qquad \boldsymbol q_k=\frac{\boldsymbol u_k}{\|\boldsymbol u_k\|}.$$

QR 分解寫成

$$A=QR,$$

其中 $Q$ 的欄向量為正交單位向量，$R$ 為上三角矩陣，且

$$r_{ij}=\boldsymbol q_i^T\boldsymbol a_j\quad (i<j), \qquad r_{jj}=\|\boldsymbol u_j\|.$$

---

解題方法

將 $A$ 的三個欄向量寫出：

$$\boldsymbol a_1= \begin{bmatrix}1\\2\\-2\end{bmatrix}, \qquad \boldsymbol a_2= \begin{bmatrix}2\\-4\\0\end{bmatrix}, \qquad \boldsymbol a_3= \begin{bmatrix}-1\\-3\\-1\end{bmatrix}.$$

第一步：求 $\boldsymbol q_1$

$$\|\boldsymbol a_1\| = \sqrt{1^2+2^2+(-2)^2} =3.$$

因此

$$\boldsymbol q_1 = \frac{\boldsymbol a_1}{\|\boldsymbol a_1\|} = \frac{1}{3} \begin{bmatrix}1\\2\\-2\end{bmatrix}.$$

---

第二步：求 $\boldsymbol q_2$

先計算 $\boldsymbol a_2$ 在 $\boldsymbol q_1$ 上的投影係數：

$$r_{12} = \boldsymbol q_1^T\boldsymbol a_2 = \frac{1}{3} \begin{bmatrix}1&2&-2\end{bmatrix} \begin{bmatrix}2\\-4\\0\end{bmatrix} = \frac{2-8}{3} =-2.$$

去除 $\boldsymbol a_2$ 在 $\boldsymbol q_1$ 方向的分量：

$$\boldsymbol u_2 = \boldsymbol a_2-r_{12}\boldsymbol q_1 = \boldsymbol a_2+2\boldsymbol q_1.$$

所以

$$\boldsymbol u_2 = \begin{bmatrix}2\\-4\\0\end{bmatrix} + \frac{2}{3} \begin{bmatrix}1\\2\\-2\end{bmatrix} = \begin{bmatrix} \frac83\\[2pt] -\frac83\\[2pt] -\frac43 \end{bmatrix}.$$

其長度為

$$\|\boldsymbol u_2\| = 4.$$

因此

$$\boldsymbol q_2 = \frac{\boldsymbol u_2}{4} = \frac{1}{3} \begin{bmatrix}2\\-2\\-1\end{bmatrix}.$$

同時

$$r_{22}=\|\boldsymbol u_2\|=4.$$

---

第三步：求 $\boldsymbol q_3$

先計算 $\boldsymbol a_3$ 在前兩個單位向量上的投影係數：

此題要求計算矩陣指數函數 $e^{At}$。對於一個 $2 \times 2$ 的矩陣 $A$，計算 $e^{At}$ 的常見方法有幾種：

1. 使用定義 $e^{At} = \sum_{k=0}^{\infty} \frac{(At)^k}{k!}$。
2. 使用特徵值和特徵向量。
3. 使用 Cayley-Hamilton 定理。
4. 對於 $2 \times 2$ 矩陣，有特定的公式。

我們將採用特徵值和特徵向量的方法，因為它通常比較直接。

步驟 1: 計算矩陣 $A$ 的特徵值 (Eigenvalues)
特徵值 $\lambda$ 滿足 $\det(A - \lambda I) = 0$。
$A - \lambda I = \begin{bmatrix} 0-\lambda & 1 \\ -8 & 6-\lambda \end{bmatrix} = \begin{bmatrix} -\lambda & 1 \\ -8 & 6-\lambda \end{bmatrix}$.
$\det(A - \lambda I) = (-\lambda)(6-\lambda) - (1)(-8) = -6\lambda + \lambda^2 + 8 = \lambda^2 - 6\lambda + 8$.
令 $\lambda^2 - 6\lambda + 8 = 0$。
因式分解得到 $(\lambda - 2)(\lambda - 4) = 0$。
所以特徵值為 $\lambda_1 = 2$ 和 $\lambda_2 = 4$。

步驟 2: 計算對應的特徵向量 (Eigenvectors)
對於 $\lambda_1 = 2$:
$(A - 2I)\mathbf{v}_1 = \mathbf{0}$
$\begin{bmatrix} -2 & 1 \\ -8 & 4 \end{bmatrix} \begin{bmatrix} v_{11} \\ v_{12} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$.
$-2v_{11} + v_{12} = 0 \implies v_{12} = 2v_{11}$。
令 $v_{11} = 1$，則 $v_{12} = 2$。
特徵向量 $\mathbf{v}_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$.

對於 $\lambda_2 = 4$:
$(A - 4I)\mathbf{v}_2 = \mathbf{0}$
$\begin{bmatrix} -4 & 1 \\ -8 & 2 \end{bmatrix} \begin{bmatrix} v_{21} \\ v_{22} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$.
$-4v_{21} + v_{22} = 0 \implies v_{22} = 4v_{21}$。
令 $v_{21} = 1$，則 $v_{22} = 4$。
特徵向量 $\mathbf{v}_2 = \begin{bmatrix} 1 \\ 4 \end{bmatrix}$.

步驟 3: 構建矩陣 P 和對角矩陣 D
令 $P$ 為由特徵向量組成的矩陣，其列向量是特徵向量。
$P = [\mathbf{v}_1 \ \mathbf{v}_2] = \begin{bmatrix} 1 & 1 \\ 2 & 4 \end{bmatrix}$.
令 $D$ 為由對應特徵值組成的對角矩陣。
$D = \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 0 & 4 \end{bmatrix}$.

矩陣 $A$ 可以被對角化，即 $A = PDP^{-1}$。
我們需要計算 $P^{-1}$。
$\det(P) = (1)(4) - (1)(2) = 4 - 2 = 2$.
$P^{-1} = \frac{1}{\det(P)} \begin{bmatrix} 4 & -1 \\ -2 & 1 \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 4 & -1 \\ -2 & 1 \end{bmatrix} = \begin{bmatrix} 2 & -1/2 \\ -1 & 1/2 \end{bmatrix}$.

步驟 4: 計算 $e^{At}$
矩陣指數函數的性質是 $e^{At} = P e^{Dt} P^{-1}$。
$e^{Dt}$ 是一個對角矩陣，其對角元素是 $e^{\lambda_i t}$。
$e^{Dt} = \begin{bmatrix} e^{\lambda_1 t} & 0 \\ 0 & e^{\lambda_2 t} \end{bmatrix} = \begin{bmatrix} e^{2t} & 0 \\ 0 & e^{4t} \end{bmatrix}$.

核心觀念

本題考查「前綴和」與鴿籠原理。

設第 $i$ 天寄出的履歷數為 $a_i$，則

$$a_i\ge 1,\qquad \sum_{i=1}^{49}a_i\le 70$$

定義前綴和

$$S_0=0,\qquad S_k=\sum_{i=1}^{k}a_i\quad (1\le k\le49)$$

因為每天至少寄出一份履歷，所以

$$0=S_0<S_1<S_2<\cdots<S_{49}\le70$$

因此共有 $50$ 個互不相同的整數前綴和，全部落在 $0$ 到 $70$ 之間。

若某一段連續日子的寄出總數恰為 $27$，則存在 $0\le i<j\le49$，使得

$$S_j-S_i=27$$

也就是兩個前綴和相差 $27$。

解題方法

將 $0$ 到 $70$ 的整數依照除以 $27$ 的餘數分組。

對於餘數 $r=0,1,\ldots,16$，各組為

$$\{r,\ r+27,\ r+54\}$$

共 $17$ 組。每組有 $3$ 個數；若三個數全部被選為前綴和，則其中必有兩個相差 $27$。因此，在不出現差 $27$ 的情況下，每組至多選出 $2$ 個數。

對於餘數 $r=17,18,\ldots,26$，各組為

$$\{r,\ r+27\}$$

共 $10$ 組。每組有 $2$ 個數；為避免出現差 $27$，每組至多選出 $1$ 個數。

核心觀念

此題考察三對角矩陣行列式的遞迴關係。令 $D_n$ 表示 $n\times n$ 矩陣 $A_n$ 的行列式，則沿著第一列展開，可得到：

• 第一項 $y$ 乘上左下方的 $(n-1)\times(n-1)$ 同型矩陣，其行列式為 $D_{n-1}$。
• 第二項 $x$ 的代數餘子式會再產生一個 $x$，並留下 $(n-2)\times(n-2)$ 同型矩陣，因此形成 $x^2D_{n-2}$。

初始條件為

$$D_0=1,\qquad D_1=y.$$

其中 $D_0=1$ 是空矩陣行列式的慣例定義。

解題方法

沿第一列展開：

$$D_n = yD_{n-1} - x^2D_{n-2}.$$

因此一般遞迴關係為

$$\boxed{D_n=yD_{n-1}-x^2D_{n-2}} \qquad (n\ge 2),$$

且

$$\boxed{D_0=1,\quad D_1=y}.$$

---

(a) 遞迴關係

直接由三對角矩陣的第一列展開，得到

$$\boxed{D_n=yD_{n-1}-x^2D_{n-2}},$$

初始條件為

$$\boxed{D_0=1,\quad D_1=y}.$$

---

(b) 當 $y=x$ 時

將 $y=x$ 代入遞迴式：

$$D_n=xD_{n-1}-x^2D_{n-2}.$$

令

$$D_n=x^na_n,$$

則

$$x^na_n=x\cdot x^{n-1}a_{n-1} -x^2\cdot x^{n-2}a_{n-2}.$$

除以 $x^n$ 得

$$a_n=a_{n-1}-a_{n-2}.$$

初始值為

$$a_0=1,\qquad a_1=1.$$

依序計算：

$$\begin{aligned} a_0&=1,\\ a_1&=1,\\ a_2&=1-1=0,\\ a_3&=0-1=-1,\\ a_4&=-1-0=-1,\\ a_5&=-1-(-1)=0,\\ a_6&=0-(-1)=1. \end{aligned}$$

因此序列以 $6$ 為週期：

$$1,1,0,-1,-1,0,\;1,1,0,-1,-1,0,\ldots$$

所以

$$D_n=x^n a_n,$$

其中

核心觀念

本題考核**圖論（Graph Theory）**中「平面圖（Planar Graph）的邊數上限定理」以及「補圖（Complementary Graph）的邊數關係」：

1. 平面圖的邊數上限定理：
   設 $G = (V, E)$ 為頂點數 $|V| = n \ge 3$ 的簡單平面圖（Simple Planar Graph），則其邊數 $e = |E|$ 滿足： $$e \le 3n - 6$$
2. 互補圖（Complementary Graphs）：
   若 $G$ 為 $n$ 個頂點的簡單圖，$\overline{G}$ 為其補圖，則完全圖 $K_n$ 的邊數會被 $G$ 與 $\overline{G}$ 完全平分包含，即兩者邊數總和為： $$e(G) + e(\overline{G}) = \binom{n}{2} = \frac{n(n-1)}{2}$$
3. 反證法（Proof by Contradiction）：
   欲證明「$G$ 或 $\overline{G}$ 至少有一者為非平面圖」，可假設「$G$ 與 $\overline{G}$ 皆為平面圖」，推導出邊數總和矛盾，進而求出臨界整數 $X$。

---

解題方法

(a) 求 $X$ 的數值

1. 利用平面圖性質設立不等式：
   假設 $G$ 與 $\overline{G}$ 皆為平面圖，且頂點數為 $n \ge 3$。
   根據平面圖的邊數上限定理：

   $$e(G) \le 3n - 6$$ $$e(\overline{G}) \le 3n - 6$$

   將兩式相加，可得兩圖邊數和的必要上限：

   $$e(G) + e(\overline{G}) \le (3n - 6) + (3n - 6) = 6n - 12$$

2. 代入互補圖的邊數總和恆等式：
   因為 $e(G) + e(\overline{G}) = \frac{n(n-1)}{2}$，若兩者皆為平面圖，必須滿足：

   $$\frac{n(n-1)}{2} \le 6n - 12$$

   同乘以 2 並展開移項：

   $$n^2 - n \le 12n - 24$$ $$n^2 - 13n + 24 \le 0$$

3. 求解不等式並判斷臨界值：
   解二次方程式 $n^2 - 13n + 24 = 0$：

   $$n = \frac{13 \pm \sqrt{169 - 96}}{2} = \frac{13 \pm \sqrt{73}}{2}$$

   因 $8 < \sqrt{73} < 9$（約 $8.544$）：

   $$\frac{13 + \sqrt{73}}{2} \approx \frac{13 + 8.544}{2} = 10.772$$

   因此，使不等式成立的整數 $n$ 必須滿足 $n \le 10$。
   換言之，當 $n \ge 11$ 時：

   $$\frac{n(n-1)}{2} > 6n - 12$$

   此時 $e(G) + e(\overline{G})$ 必然大於 $2(3n - 6)$，故 $G$ 與 $\overline{G}$ 不可能同時為平面圖（至少有一者的邊數必定嚴格大於 $3n - 6$，從而非平面圖）。

4. 確認 $X$ 是否可為 9 或 10（非平面圖充要判斷）：
   上述的邊數上限為平面圖的「必要條件」而非「充分條件」。根據圖論已知定理（Battle, Harary, Kodama 等人於 1962 年發表的經典結論）：

   • 當 $n \le 8$ 時，存在自補平面圖（Self-complementary planar graph）或互補的一對平面圖（例如 $n=8$ 時可構造出 $G$ 與 $\overline{G}$ 皆為平面圖）。
   • 當 $n \ge 9$ 時，任何 $n$ 個頂點的圖 $G$ 與其補圖 $\overline{G}$ 至少有一者包含 $K_5$ 或 $K_{3,3}$ 的小圖（Minor）或同胚子圖，因而至少有一者必為非平面圖。