114 年 國立成功大學人工智慧科技碩士學位學程《計算機數學（含線性代數、離散數學）》

核心觀念

圖中的有限狀態機有四個狀態，輸入為 $0$ 時停留在原狀態；輸入為 $1$ 時依序循環：

$$s_0\to s_1\to s_2\to s_3\to s_0.$$

因此，輸入字串中每出現一個 $1$，狀態沿循環前進一格；輸入 $0$ 不影響狀態。

要使

$$v(s_0,x)=s_0,$$

輸入字串中的 $1$ 的個數必須是 $4$ 的倍數。

---

解題方法

I. $|x|=8$

長度為 $8$ 的二元輸入字串，其 $1$ 的個數可能為 $0,1,\ldots,8$。符合四的倍數的情況為：

$$\#1=0,\quad 4,\quad 8.$$

固定有 $k$ 個 $1$ 時，字串數量為 $\binom{8}{k}$，所以總數為

$$\binom{8}{0}+\binom{8}{4}+\binom{8}{8} =1+70+1 =72.$$

因此第一小題答案為：

$$\boxed{(a)\ 72}$$

II. $|x|=12$

符合條件的 $1$ 的個數為：

$$\#1=0,\quad 4,\quad 8,\quad 12.$$

所以字串總數為

$$\binom{12}{0}+\binom{12}{4}+\binom{12}{8}+\binom{12}{12}.$$

計算得

$$1+495+495+1=992.$$

因此第二小題答案為：

核心觀念

本題屬於離散數學（Discrete Mathematics）中的**組合計數（Combinatorics）**問題，主要評量以下觀念：

1. 變數變換（Variable Transformation）：將具有非零下限的變數範圍平移為從 $0$ 開始的標準非負整數變數，簡化方程式。
2. 限制條件下的非負整數解個數：求解形如 $y_1 + 2y_2 + y_3 = k$ 且帶有上下限限制的方程式，常見切入點包含分類討論法（Case Analysis）、排容原理（Inclusion-Exclusion Principle）與生成函數（Generating Function）。

---

解題方法

步驟一：變數平移（變數變換）
定義新變數以消除非零下限：
$y_1 = x_1 - 2 \implies 0 \le y_1 \le 3$
$y_2 = x_2 - 3 \implies 0 \le y_2 \le 3$
$y_3 = x_3 - 4 \implies 0 \le y_3 \le 3$

將 $x_1 = y_1 + 2$、$x_2 = y_2 + 3$、$x_3 = y_3 + 4$ 代入原方程式 $x_1 + 2x_2 + x_3 = 17$：
$(y_1 + 2) + 2(y_2 + 3) + (y_3 + 4) = 17$
$y_1 + 2y_2 + y_3 + 12 = 17$
$y_1 + 2y_2 + y_3 = 5$

因此，問題轉化為求滿足 $y_1 + 2y_2 + y_3 = 5$ 且 $0 \le y_1, y_2, y_3 \le 3$ 的非負整數解 $(y_1, y_2, y_3)$ 之組數。

步驟二：按大係數變數 $y_2$ 分類討論

由於 $y_2$ 的係數為 $2$，且 $y_2 \in \{0, 1, 2, 3\}$，按 $y_2$ 的可能取值討論：

1. 當 $y_2 = 0$ 時：
   方程式化為 $y_1 + y_3 = 5$，限制為 $0 \le y_1 \le 3$ 且 $0 \le y_3 \le 3$。

   • 若 $y_1 = 2$，則 $y_3 = 3$
   • 若 $y_1 = 3$，則 $y_3 = 2$
     共 2 組解：$(2, 0, 3), (3, 0, 2)$。

2. 當 $y_2 = 1$ 時：
   方程式化為 $y_1 + 2(1) + y_3 = 5 \implies y_1 + y_3 = 3$，限制為 $0 \le y_1 \le 3$ 且 $0 \le y_3 \le 3$。

   • $y_1$ 可取 $0, 1, 2, 3$，對應的 $y_3$ 分別為 $3, 2, 1, 0$。

核心觀念
本題考查離散數學中**集合論（Set Theory）**的基本概念，包含：

1. 集合的基數（Cardinality of a Set）：有限集合 $S$ 中所含元素的個數，記作 $|S|$ 或 $n(S)$。
2. 冪集（Power Set）：由集合 $S$ 之所有子集合（Subsets，包含空集 $\emptyset$ 與 $S$ 本身）所構成的集合，記作 $\mathcal{P}(S)$ 或 $2^S$。
3. 冪集的元素個數定理：若有限集合 $S$ 的基數為 $n$（即 $|S| = n$），則其冪集的基數（即 $S$ 的子集合總數）為：
   $|\mathcal{P}(S)| = 2^n$

解題方法

1. 確定集合 $S$ 的元素個數：
   已知集合 $S = \{1, 2, 3, 4, 5, 6, 7\}$，直接計數可得 $S$ 共有 $7$ 個元素，即 $|S| = 7$。
2. 套用冪集基數公式：
   根據冪集定義，集合 $S$ 的每個子集合在構成時，對於 $S$ 中的每一個元素 $x \in S$，都有「選入子集合」或「不選入子集合」兩種選擇。
   依據乘法原理（Rule of Product），$7$ 個獨立元素的選擇組合總數為：
   $|\mathcal{P}(S)| = \underbrace{2 \times 2 \times \cdots \times 2}_{7 \text{ 個 }} = 2^7 = 128$

核心觀念

本題考查離散數學（Discrete Mathematics）中的**一階非齊次線性遞迴關係式（First-Order Nonhomogeneous Linear Recurrence Relation）**求解。

求解一般形式 $a_n - c a_{n-1} = f(n)$ 的主要步驟如下：

1. 齊次解（Homogeneous Solution, $a_n^{(h)}$）：求解對應齊次方程 $a_n - c a_{n-1} = 0$ 的通解。其特徵方程式（Characteristic Equation）為 $r - c = 0$，解得 $r = c$，故齊次解形如 $a_n^{(h)} = k \cdot c^n$。
2. 特解（Particular Solution, $a_n^{(p)}$）：根據非齊次項 $f(n)$ 的形式假設特解。若 $f(n) = A \cdot c^n$，且 $c$ 恰好為齊次特徵根（重根數 $m=1$），則特解假設形式需乘以 $n$，即 $a_n^{(p)} = d \cdot n \cdot c^n$。
3. 通解（General Solution, $a_n$）：將齊次解與特解相加，得 $a_n = a_n^{(h)} + a_n^{(p)}$。
4. 代入初始條件：利用初始條件 $a_0$ 求解未知係數 $k$。

---

解題方法

步驟一：求齊次解 $a_n^{(h)}$
考慮對應的齊次遞迴關係式：
$a_n - 3a_{n-1} = 0$
特徵方程式為：
$r - 3 = 0 \implies r = 3$
因此齊次解形式為：
$a_n^{(h)} = k \cdot 3^n \quad (k \text{ 為任意常數})$

步驟二：求特解 $a_n^{(p)}$
觀察右式非齊次項 $f(n) = 5 \cdot 3^n$。由於指數底數 $3$ 與齊次特徵根 $r=3$ 重複，特解假設形式需乘以 $n$：
$a_n^{(p)} = d \cdot n \cdot 3^n$
將 $a_n^{(p)}$ 代回原遞迴關係式 $a_n - 3a_{n-1} = 5(3^n)$：
$d \cdot n \cdot 3^n - 3 \cdot [d \cdot (n-1) \cdot 3^{n-1}] = 5 \cdot 3^n$
提出公因式並化簡左式：
$d \cdot n \cdot 3^n - d \cdot (n-1) \cdot 3^n = 5 \cdot 3^n$
$[d \cdot n - d(n-1)] \cdot 3^n = 5 \cdot 3^n$
$d \cdot 3^n = 5 \cdot 3^n$
比較兩端係數可得 $d = 5$，因此特解為：
$a_n^{(p)} = 5n \cdot 3^n$

核心觀念

本題考查線性方程組 $Ax = b$ 的解性（Existence and Uniqueness of Solutions）與矩陣的秩（Rank）、列維度 $m$、行維度 $n$ 之間的結構關係。

對於一個 $m \times n$ 矩陣 $A$（秩為 $\text{rank}(A) = r$），方程組 $Ax = b$ 的解具有以下兩大核心定理：

1. 解的存在性（Existence）：

   • 方程組 $Ax = b$ 有解當且僅當向量 $b$ 屬於 $A$ 的行空間（Column space），即 $b \in \mathcal{C}(A)$。
   • 若 $\text{rank}(A) = r = m$（滿列秩, Full row rank），則行空間維度等於目標空間維度，即 $\mathcal{C}(A) = \mathbb{R}^m$。此時對於任意 $b \in \mathbb{R}^m$，方程組都必定有解（永不無解）。
   • 若 $\text{rank}(A) = r < m$，則 $\mathcal{C}(A) \subsetneq \mathbb{R}^m$（行空間僅為 $\mathbb{R}^m$ 的真子空間）。此時存在部分向量 $b \notin \mathcal{C}(A)$，使得方程組無解。

2. 解的唯一性（Uniqueness）：

   • 當方程組有解時，通解結構為 $x = x_p + x_h$，其中 $x_p$ 為特解，$x_h \in \text{Null}(A)$ 為零空間（Null space）中的齊次解。
   • 根據秩－零化度定理（Rank-Nullity Theorem），零空間維度（零化度）為 $\dim(\text{Null}(A)) = n - r$。
   • 若 $\text{rank}(A) = r = n$（滿行秩, Full column rank），則零空間僅包含零向量（$\dim(\text{Null}(A)) = 0$），自由變數為 0。此時只要解存在，就必為唯一解（恰有一組解）。
   • 若 $\text{rank}(A) = r < n$，則零化度 $n - r > 0$，存在自由變數。此時只要解存在，就必有無窮多組解。

---

解題方法

題幹給定條件為：對某些 $b$ 有「恰有一組解（唯一解）」，對其他 $b$ 有「無解」。我們將這兩個條件分別拆解推導：

1. 條件一：「對某些 $b$ 有恰有一組解（唯一解）」

   • 若要保證方程組有解時能達到「唯一解」，零空間必須只含有零向量，即 $\dim(\text{Null}(A)) = n - r = 0$。
   • 由此可明確推導出：
     $r = n$
   • （若 $r < n$，則一旦有解就必定是無窮多組解，絕不可能出現唯一解。）

2. 條件二：「對其他某些 $b$ 無解」

   • 若要保證方程組會出現「無解」的情況，說明行空間未張成整個目標空間，即

核心觀念

本題考查**矩陣的可逆性（Nonsingularity / Invertibility）與范德蒙矩陣（Vandermonde Matrix）**的行列式計算。

1. 矩陣可逆（Nonsingular）的充要條件：
   對於一個 $n \times n$ 方陣 $A$，若其行列式 $\det(A) \neq 0$，則 $A$ 為非特異矩陣（Nonsingular Matrix，即可逆矩陣）；若 $\det(A) = 0$，則 $A$ 為特異矩陣（Singular Matrix，即不可逆矩陣）。

2. 范德蒙行列式（Vandermonde Determinant）：
   矩陣 $A$ 為標準的 $3 \times 3$ 范德蒙矩陣。一般而言，$n \times n$ 范德蒙矩陣的行列式公式為：
   $\det(A) = \prod_{1 \le i < j \le n} (x_j - x_i)$
   當且僅當所有 $x_i$ 兩兩互異（All $x_i$ values are distinct）時，$\det(A) \neq 0$。

---

解題方法

Step 1：計算矩陣 $A$ 的行列式 $\det(A)$

給定矩陣：
$A = \begin{pmatrix} 1 & x_1 & x_1^2 \\ 1 & x_2 & x_2^2 \\ 1 & x_3 & x_3^2 \end{pmatrix}$

對 $A$ 進行列運算（Row Operations）以簡化行列式計算：

1. 第 2 列減去第 1 列（$R_2 \leftarrow R_2 - R_1$）：
   $\begin{pmatrix} 1 & x_1 & x_1^2 \\ 0 & x_2 - x_1 & x_2^2 - x_1^2 \\ 1 & x_3 & x_3^2 \end{pmatrix}$

2. 第 3 列減去第 1 列（$R_3 \leftarrow R_3 - R_1$）：
   $\begin{pmatrix} 1 & x_1 & x_1^2 \\ 0 & x_2 - x_1 & x_2^2 - x_1^2 \\ 0 & x_3 - x_1 & x_3^2 - x_1^2 \end{pmatrix}$

沿第 1 欄進行降階展開（Cofactor Expansion）：
$\det(A) = 1 \cdot \det \begin{pmatrix} x_2 - x_1 & x_2^2 - x_1^2 \\ x_3 - x_1 & x_3^2 - x_1^2 \end{pmatrix}$

利用平方差公式 $a^2 - b^2 = (a-b)(a+b)$，提出第 1 列公因式 $(x_2 - x_1)$ 與第 2 列公因式 $(x_3 - x_1)$：
$\det(A) = (x_2 - x_1)(x_3 - x_1) \cdot \det \begin{pmatrix} 1 & x_2 + x_1 \\ 1 & x_3 + x_1 \end{pmatrix}$

計算 $2 \times 2$ 行列式：
$\det \begin{pmatrix} 1 & x_2 + x_1 \\ 1 & x_3 + x_1 \end{pmatrix} = (x_3 + x_1) - (x_2 + x_1) = x_3 - x_2$

整理可得矩陣 $A$ 的行列式為：
$\det(A) = (x_2 - x_1)(x_3 - x_1)(x_3 - x_2)$

Step 2：判定 Nonsingular 的條件

核心觀念

本題旨在考查線性代數中數個基本主題的核心性質與定理：

1. 矩陣的秩（Rank）與轉置性質：實數矩陣 $A$ 之秩、轉置矩陣之秩，以及與 $AA^T$、$A^T A$ 秩的關係。
2. 正交矩陣（Orthogonal Matrix）之定義與性質：若 $Q^T Q = Q Q^T = I$，則 $Q$ 為正交矩陣。
3. 線性轉換（Linear Transformation）與核空間（Kernel）之定義：線性轉換具備加法性與齊次性，且 $\text{ker}(L) = \{v \in V \mid L(v) = 0\}$。
4. 列等價（Row Equivalence）與行列式（Determinant）之關係：基本列運算（Elementary Row Operations）對矩陣行列式的縮放與變號效應。

---

解題方法

本題為概念性選擇題，解題切入點採用定義與定理直接推導配合反例驗證：

1. 針對敘述正確的選項（A、B、C），依據線性代數標準定理與定義進行嚴謹推導證明。
2. 針對敘述錯誤的選項（D），分析基本列運算對行列式的影響，並構造具體反例進行駁斥。

---

選項分析

• (A) 正確（非本題解答）：
  設 $A$ 為 $m \times n$ 之實數矩陣。考慮齊次線性方程組 $Ax = 0$ 與 $A^T A x = 0$：

  • 若 $Ax = 0$，則等式兩邊左乘 $A^T$ 可得 $A^T A x = 0$。
  • 反之，若 $A^T A x = 0$，則兩邊左乘 $x^T$ 可得 $x^T A^T A x = (Ax)^T (Ax) = \|Ax\|^2 = 0$。由範數（Norm）之性質可得 $Ax = 0$。

  因此，零空間相等 $\text{Null}(A) = \text{Null}(A^T A)$，零化度（Nullity）亦相同 $\text{nullity}(A) = \text{nullity}(A^T A)$。
  依據秩與零化度定理（Rank-Nullity Theorem）：
  $\text{rank}(A) = n - \text{nullity}(A) = n - \text{nullity}(A^T A) = \text{rank}(A^T A)$
  同理，對轉置矩陣 $A^T$ 施加相同推導可得 $\text{rank}(A^T) = \text{rank}(AA^T)$。
  又因矩陣轉置後其秩保持不變（$\text{rank}(A) = \text{rank}(A^T)$），故推導出：
  $\text{rank}(AA^T) = \text{rank}(A) = \text{rank}(A^T A)$
  本選項敘述為真。

• (B) 正確（非本題解答）：
  依據正交矩陣之定義， $n \times n$ 實數矩陣 $Q$ 為正交矩陣若且唯若 $Q^T Q = Q Q^T = I$。
  檢驗 $Q^T$ 之轉置矩陣 $(Q^T)^T = Q$ 與其本身之相乘關係：

核心觀念

1. 分塊對角矩陣（Block Diagonal Matrix）的特徵值：若 $n \times n$ 矩陣 $A$ 為分塊對角矩陣，即 $A = \begin{pmatrix} B & 0 \\ 0 & C \end{pmatrix}$，則其特徵多項式可分解為 $\det(A - \lambda I) = \det(B - \lambda I) \cdot \det(C - \lambda I) = 0$。因此 $A$ 的特徵值即為子矩陣 $B$ 與 $C$ 的特徵值聯集。
2. $2 \times 2$ 矩陣特徵值公式：對矩陣 $B = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$，特徵方程式為 $\lambda^2 - \text{tr}(B)\lambda + \det(B) = 0$。
3. 特徵空間（Eigenspace）定義：矩陣 $A$ 對應特徵值 $\lambda$ 的特徵空間為齊次線性方程組 $(A - \lambda I)\mathbf{x} = \mathbf{0}$ 的解空間（Null Space/Kernel），即 $E_\lambda = \ker(A - \lambda I)$。

---

解題方法

步驟一：求解矩陣 $A$ 的全體特徵值

將矩陣 $A$ 視為分塊對角矩陣：
$A = \begin{pmatrix} B & 0_{2\times 2} \\ 0_{2\times 2} & C \end{pmatrix}$
其中：
$B = \begin{pmatrix} 2 & 1 \\ 3 & 4 \end{pmatrix}, \quad C = \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix}$

1. 計算子矩陣 $B$ 的特徵值：

   • 跡（Trace）：$\text{tr}(B) = 2 + 4 = 6$
   • 行列式（Determinant）：$\det(B) = 2 \cdot 4 - 1 \cdot 3 = 5$
   • 特徵方程式：
     $\lambda^2 - 6\lambda + 5 = 0 \implies (\lambda - 1)(\lambda - 5) = 0$
   • 解得特徵值為 $\lambda = 5$ 與 $\lambda = 1$。

2. 計算子矩陣 $C$ 的特徵值：

   • 因 $C$ 為對角矩陣，特徵值直接為對角線元素，即 $\lambda = 2$ 與 $\lambda = 1$。

綜合以上，矩陣 $A$ 的全體特徵值為：
$\lambda = 5, 2, 1, 1$
其中 $\lambda = 1$ 的代數重數（Algebraic Multiplicity）為 2。

步驟二：求解 $\lambda = 5$ 所對應的特徵空間

將 $\lambda = 5$ 代入方程 $(A - 5I)\mathbf{x} = \mathbf{0}$：

(a) True

• 理由：若 $Q \in \mathbb{R}^{3 \times 2}$ 擁有正交規範列（orthonormal columns），則 $Q^T Q = I_2$。
• 推導：對任意 $x \in \mathbb{R}^2$，其歐幾里得範數平方為：
  $\|Qx\|^2 = (Qx)^T (Qx) = x^T Q^T Q x = x^T I_2 x = x^T x = \|x\|^2$
  兩邊開根號即得 $\|Qx\| = \|x\|$。

(b) True

• 理由：$P$ 為正交投影矩陣（projection matrix），具有等冪性（idempotent property），即 $P^2 = P$。
• 推導：
  $P^2 = \left(A(A^TA)^{-1}A^T\right) \left(A(A^TA)^{-1}A^T\right) = A(A^TA)^{-1} (A^TA) (A^TA)^{-1}A^T = A(A^TA)^{-1}A^T = P$
  利用數學歸納法，對任意正整數 $k = 1, 2, \dots$，皆滿足 $P^k = P$。

(c) False

• 理由：矩陣 $U \in \mathbb{R}^{m \times k}$ 滿足 $U^T U = I_k$，但 $U U^T = I_m$ 僅在 $m = k$（即 $U$ 為正方矩陣）時才成