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

讀圖

有限狀態機有四個狀態 $s_0,s_1,s_2,s_3$，起始狀態為 $s_0$。每條邊標示「輸入, 輸出」：

• 每個狀態讀到輸入 0：停在原狀態（自迴圈 $0,0$）。
• 讀到輸入 1：沿環前進一格，$s_0\to s_1\to s_2\to s_3\to s_0$（$s_3\to s_0$ 那一步輸出 1，其餘輸出 0）。

核心觀念

狀態只由「目前讀過幾個 1」決定：讀過 $k$ 個 1 之後，位於 $s_{k \bmod 4}$。所以

讀圖

有限狀態機有四個狀態 $s_0,s_1,s_2,s_3$，起始狀態為 $s_0$：

• 讀到輸入 0：停在原狀態。
• 讀到輸入 1：沿環前進一格，$s_0\to s_1\to s_2\to s_3\to s_0$。

核心觀念

讀過 $k$ 個 1 之後位於 $s_{k\bmod 4}$，因此

解題方法

長度 12 的二元字串中，1 的個數可為 0、4、8、12：

核心觀念

這題考非負整數解的計數。遇到變數有下界時，先扣除下界，把變數平移成從 $0$ 起算；再依照各變數的上界限制，逐一計數。

解題方法

令

由題目範圍可得 $0\leq a,b,c\leq 3$。代回原式：

整理得

固定 $b$ 後，計算 $a+c=5-2b$ 的解數。由於 $0\leq a,c\leq 3$，且 $b$ 必須是非負整數，只有 $b=0,1,2$ 可能成立。

核心觀念

有限集合 $S$ 的冪集是由 $S$ 的所有子集合所組成的集合。若 $S$ 有 $n$ 個元素，則冪集的元素個數為

每個元素都有「放入子集合」與「不放入子集合」兩種選擇，因此共有 $2^n$ 個子集合。

解題方法

題目給定

集合 $S$ 的元素是 $1$、$2$、$3$、$4$、$5$，以及 $\{6,7\}$。其中 $\{6,7\}$ 本身是一個元素；它內部的 $6$ 和 $7$ 不另外算作 $S$ 的元素。

因此 $S$ 有 $6$ 個元素，冪集的元素個數為

核心觀念

這是一階線性遞迴關係，且右側的非齊次項 $5\cdot 3^n$ 與齊次遞迴的解同底數，屬於共振情形。

齊次遞迴為 $a_n-3a_{n-1}=0$，其解的形式是 $C\cdot 3^n$。由於非齊次項也含 $3^n$，特解需乘上 $n$，因此通解的形式為 $(C+kn)3^n$。

解題方法

令

也就是把遞迴關係中的 $a_n$ 寫成 $3^n b_n$，並把 $a_{n-1}$ 寫成 $3^{n-1}b_{n-1}$。代入原式：

因為 $3\cdot 3^{n-1}=3^n$，兩邊除以 $3^n$，得到

因此 $b_n$ 每增加一個索引就增加 $5$。又 $a_0=2$，所以 $b_0=a_0/3^0=2$，進而

換回 $a_n=3^n b_n$：

選項分析

核心觀念

線性方程組 $Ax=b$ 的解是否存在，以及解是否唯一，分別由 $A$ 的欄空間與零空間決定：

• $Ax=b$ 有解，代表 $b$ 位於 $A$ 的欄空間。
• 若 $Ax=b$ 有解，且 $\operatorname{Null}(A)=\{0\}$，則解唯一。
• 由秩－零度定理，$\dim\operatorname{Null}(A)=n-r$。因此解唯一要求 $n-r=0$，也就是 $r=n$。
• 若某些 $b$ 無解，表示 $A$ 的欄空間不等於 $\mathbb{R}^m$，所以 $r<m$。

解題方法

題目要求同時滿足兩項條件：

1. 對某個 $b$，方程組恰有一解。這要求零空間只有零向量，因此
   $r=n.$

2. 對其他某些 $b$，方程組無解。這表示欄空間沒有涵蓋整個 $\mathbb{R}^m$，因此
   $r<m.$

合併可得
$r=n<m.$

選項分析

核心觀念

這題考的是 Vandermonde 矩陣的行列式與矩陣可逆的判準。方陣 $A$ 非奇異（nonsingular）當且僅當 $\det(A)\ne 0$。

本題的矩陣是三階 Vandermonde 矩陣，其行列式可寫成：

因此，行列式非零的條件是任意兩個 $x_i$ 都不相等。

解題方法

對矩陣的第二列、第三列分別減去第一列，不會改變行列式：

利用 $a^2-b^2=(a-b)(a+b)$，並沿第一欄展開：

核心觀念

本題考查矩陣的秩、正交矩陣、線性轉換的核，以及列等價與行列式的關係。

• 矩陣的秩是其欄空間或列空間的維度。
• 若 $Q$ 是正交矩陣，則 $Q^TQ=QQ^T=I$。
• 線性轉換 $L$ 的核為 $\ker L=\{v\in V:L(v)=0\}$。
• 對方陣進行列運算會改變或保留行列式，取決於所使用的列運算；列等價只保證可透過列運算互相轉換，不保證行列式相等。

解題方法

逐一用定義檢查前三個敘述，再用列運算對行列式的影響檢驗選項 (D)。特別要注意：列等價描述的是矩陣能否透過初等列運算互相轉換，並沒有要求轉換過程中的行列式維持不變。

選項分析

(A) 正確。 若 $A$ 是 $m\times n$ 矩陣，則

且

因此 $AA^T$ 與 $A^TA$ 的秩相同。這也可由 $\ker(AA^T)=\ker(A^T)$ 及 $\ker(A^TA)=\ker(A)$ 推得；兩者分別對應 $A$ 的列秩與欄秩，而列秩等於欄秩。

核心觀念

矩陣 $A$ 的特徵值 $\lambda$ 必須滿足特徵方程

對應於 $\lambda$ 的特徵空間是

也就是所有滿足 $Ax=\lambda x$ 的向量所構成的子空間。

解題方法

題目矩陣由左上角的 $2\times2$ 區塊，以及右下角的 $2$ 和 $1$ 組成。因此可直接計算特徵多項式：

計算左上角區塊的行列式：

所以

特徵值為 $1,1,2,5$，其中 $\lambda=1$ 重複兩次。

核心觀念

若 $Q$ 的欄向量彼此正交且長度皆為 $1$，則稱 $Q$ 的欄向量為正交規一。對本題的 $3\times 2$ 矩陣 $Q$，這代表

此性質表示 $Q$ 將 $\mathbb{R}^2$ 中的向量映到 $\mathbb{R}^3$ 時，會保留向量的長度。

解題方法

對任意 $x\in\mathbb{R}^2$，以歐幾里得範數計算：

核心觀念

題目考查正交投影矩陣的冪等性。當 $A$ 為 $m\times n$ 矩陣且 $\operatorname{rank}(A)=n$ 時，$A$ 的欄向量線性獨立，因此 $A^TA$ 可逆。矩陣

是投影到 $A$ 的欄空間上的正交投影矩陣，滿足 $P^2=P$。

解題方法

先直接計算 $P^2$，並利用 $A^TA$ 與其反矩陣相乘為單位矩陣：

核心觀念

若 $U=(u_1,u_2,\ldots,u_k)$，表示將 $k$ 個向量依序放成矩陣的欄，因此 $U$ 是 $n\times k$ 矩陣。

向量組正交標準，表示

因此

但 $UU^T$ 是 $n\times n$ 矩陣，代表投影到 $\operatorname{span}\{u_1,\ldots,u_k\}$ 的投影矩陣；它不一定等於 $I_n$。只有當這些向量張成整個 $\mathbb{R}^n$ 時，投影才是恆等映射。

解題方法

檢查題目給的條件是否足以確保 $u_1,\ldots,u_k$ 張成 $\mathbb{R}^n$。正交標準只保證向量彼此垂直且長度為 $1$，並不保證向量數量足夠。

例如取 $n=2$、$k=1$，令

這是正交標準向量組，但

核心觀念

矩陣 $A$ 為正定，定義是對所有非零向量 $x$，都有

對稱矩陣的特徵值皆為實數，而行列式等於所有特徵值的乘積。因此，$\det(A)>0$ 只表示特徵值的乘積為正，不能保證每個特徵值都為正；其中可能有偶數個負特徵值。

解題方法

用一個滿足題目條件、但不正定的對稱矩陣作反例：

此矩陣是對稱矩陣，且

核心觀念

對稱正定矩陣 $A$ 的定義是：$A$ 為對稱矩陣，且對每個非零向量 $x$，都有

矩陣的第 $i$ 個對角元素可用第 $i$ 個標準基底向量 $e_i$ 表示：

解題方法

任取一個索引 $i$。標準基底向量 $e_i$ 非零，因此由正定性的定義，

而 $e_i^{T}Ae_i$ 正是 $A$ 的第 $i$ 個對角元素 $a_{ii}$，所以