111 年 國立臺北大學資訊工程研究所《線性代數與離散數學》

核心觀念

本題考查以 Gauss–Jordan 消去法解線性方程組。將方程組寫成增廣矩陣後，利用初等列運算化為最簡列梯形矩陣：

1. 交換兩列。
2. 某一列乘以非零常數。
3. 將某列加上另一列的倍數。

最終可由主元變數與自由變數表示通解。

---

解題方法

原方程組的增廣矩陣為

$$\left[ \begin{array}{cccc|c} 2&-1&1&2&0\\ 2&-1&3&1&9\\ -1&-1&-1&-1&-4 \end{array} \right]$$

先消去第二列的第一欄：

$$R_2\leftarrow R_2-R_1$$

並以 $R_1+2R_3$ 消去第三列的第一欄：

$$R_3\leftarrow R_1+2R_3$$

得到

$$\left[ \begin{array}{cccc|c} 2&-1&1&2&0\\ 0&0&2&-1&9\\ 0&-3&-1&0&-8 \end{array} \right]$$

交換第二、三列：

$$\left[ \begin{array}{cccc|c} 2&-1&1&2&0\\ 0&-3&-1&0&-8\\ 0&0&2&-1&9 \end{array} \right]$$

將第二列除以 $-3$，第三列除以 $2$：

$$\left[ \begin{array}{cccc|c} 2&-1&1&2&0\\ 0&1&\frac13&0&\frac83\\ 0&0&1&-\frac12&\frac92 \end{array} \right]$$

消去第一、二列中的 $x_3$：

$$R_2\leftarrow R_2-\frac13R_3$$ $$R_1\leftarrow R_1-R_3$$

可得

$$\left[ \begin{array}{cccc|c} 2&-1&0&\frac52&-\frac92\\ 0&1&0&\frac16&\frac76\\ 0&0&1&-\frac12&\frac92 \end{array} \right]$$

再消去第一列中的 $x_2$：

$$R_1\leftarrow R_1+R_2$$

得到

核心觀念

1. 列空間（Row Space, $\text{Row}(A)$）：由矩陣 $A$ 之各列向量所生成（span）的向量空間。對矩陣進行基本列運算（Elementary Row Operations）不改變其列空間。列簡化梯形矩陣（RREF）中的非零列向量即構成列空間的一組基底（Basis）。
2. 零空間（Null Space, $\text{Null}(A)$）：齊次線性方程組 $A\mathbf{x} = \mathbf{0}$ 的所有解向量所構成的向量空間。通解中自由變數（Free Variable）的個數即為零空間的維度（Nullity）。
3. 秩-零化度定理（Rank-Nullity Theorem）：設 $A$ 為一 $m \times n$ 矩陣，則其列空間維度（矩陣的秩 $\text{rank}(A)$）與零空間維度（零化度 $\text{nullity}(A)$）之和等於矩陣的行數 $n$（即變數個數）：
   $\text{rank}(A) + \text{nullity}(A) = n$

---

解題方法

1. (a) 小題切入點：
   • 將矩陣 $A$ 利用高斯-喬登消去法（Gauss-Jordan Elimination）化為簡約列梯形矩陣 $\text{RREF}(A)$。
   • 提取 $\text{RREF}(A)$ 的所有非零列向量，作為 $\text{Row}(A)$ 的一組基底。
   • 根據 $\text{RREF}(A)\mathbf{x} = \mathbf{0}$ 寫出聯立方程組，以自由變數表示出通解向量，解出向量之係數部分即為 $\text{Null}(A)$ 的一組基底。
2. (b) 小題切入點：
   • 由 (a) 小題結果算出 $\text{rank}(A) = \text{dim}(\text{Row}(A))$ 與 $\text{nullity}(A) = \text{dim}(\text{Null}(A))$。
   • 確認矩陣 $A$ 的維度為 $3 \times 4$（即行數 $n = 4$）。
   • 代入公式驗證 $\text{rank}(A) + \text{nullity}(A) = 4$ 是否成立。

---

詳細計算過程

(a) 求 $\text{Row}(A)$ 與 $\text{Null}(A)$ 的基底

步驟一：對矩陣 $A$ 進行列運算化為 $\text{RREF}(A)$

給定 $3 \times 4$ 矩陣：

$$A = \begin{bmatrix} 1 & -2 & -1 & 2 \\ 2 & -1 & 3 & 1 \\ -1 & 1 & -1 & -1 \end{bmatrix}$$

1. 以第 1 列第 1 行元素 $1$ 作為樞鈕（Pivot），進行列運算消去第 1 行其餘元素：

   • $R_2 \leftarrow R_2 - 2R_1$：
     $[2, -1, 3, 1] - 2[1, -2, -1, 2] = [0, 3, 5, -3]$
   • $R_3 \leftarrow R_3 + R_1$：
     $[-1, 1, -1, -1] + [1, -2, -1, 2] = [0, -1, -2, 1]$
     得到：
   $$\begin{bmatrix} 1 & -2 & -1 & 2 \\ 0 & 3 & 5 & -3 \\ 0 & -1 & -2 & 1 \end{bmatrix}$$

2. 交換第 2、3 列，並將新第 2 列乘以 $-1$：

   • $R_2 \leftrightarrow R_3$，接著 $R_2 \leftarrow -R_2$：
   $$\begin{bmatrix} 1 & -2 & -1 & 2 \\ 0 & 1 & 2 & -1 \\ 0 & 3 & 5 & -3 \end{bmatrix}$$

3. 以第 2 列第 2 行元素 $1$ 為樞鈕，消去第 3 列第 2 行元素：

   • $R_3 \leftarrow R_3 - 3R_2$：
     $[0, 3, 5, -3] - 3[0, 1, 2, -1] = [0, 0, -1, 0]$
   • $R_3 \leftarrow -R_3$：
     $[0, 0, 1, 0]$
     得到列梯形矩陣（REF）：
   $$\begin{bmatrix} 1 & -2 & -1 & 2 \\ 0 & 1 & 2 & -1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$

4. 向上消去第 3 行與第 2 行，化為簡約列梯形矩陣（RREF）：

   • $R_2 \leftarrow R_2 - 2R_3$：
     $[0, 1, 2, -1] - 2[0, 0, 1, 0] = [0, 1, 0, -1]$
   • $R_1 \leftarrow R_1 + R_3$：
     $[1, -2, -1, 2] + [0, 0, 1, 0] = [1, -2, 0, 2]$
   • $R_1 \leftarrow R_1 + 2R_2$：
     $[1, -2, 0, 2] + 2[0, 1, 0, -1] = [1, 0, 0, 0]$

得到最終簡約列梯形矩陣：

$$\text{RREF}(A) = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$

步驟二：求 $\text{Row}(A)$ 的基底

核心觀念

1. 正交補空間（Orthogonal Complement）的定義：
   設 $S$ 為實向量空間 $\mathbb{R}^n$ 的子空間，則 $S$ 的正交補空間 $S^\perp$ 定義為與 $S$ 中所有向量皆正交的向量集合：
   $S^\perp = \{ y \in \mathbb{R}^n \mid y \cdot x = 0, \, \forall x \in S \}$

2. 生成集與正交性：
   若子空間 $S$ 由向量集合 $\{x_1, x_2\}$ 所生成（即 $S = \text{span}\{x_1, x_2\}$），則向量 $y \in S^\perp$ 的充要條件為 $y$ 同時正交於 $x_1$ 與 $x_2$：
   $y \in S^\perp \iff x_1^T y = 0 \quad \text{且} \quad x_2^T y = 0$

3. 基本子空間關係：
   將 $x_1^T, x_2^T$ 作為列向量構成矩陣 $A = \begin{bmatrix} x_1^T \\ x_2^T \end{bmatrix}$，則 $S^\perp$ 即為矩陣 $A$ 的零空間（Null Space, $\text{Null}(A)$）。
   根據維度定理（Rank-Nullity Theorem）：
   $\dim(S) + \dim(S^\perp) = \dim(\mathbb{R}^3) = 3$
   因為 $x_1, x_2$ 線性獨立，$\dim(S) = 2$，故正交補空間之維度 $\dim(S^\perp) = 3 - 2 = 1$。

---

解題方法

方法一：齊次線性方程組法（求解零空間）

設向量 $y = \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} \in S^\perp$，根據正交定義可列出齊次聯立方程組：

$$\begin{cases} x_1^T y = 1 \cdot y_1 + 0 \cdot y_2 + 2 \cdot y_3 = 0 \\ x_2^T y = 0 \cdot y_1 + 1 \cdot y_2 - 4 \cdot y_3 = 0 \end{cases}$$

寫成矩陣型態 $Ay = 0$：
$\begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & -4 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$

此係數矩陣已經為簡列階梯形（Reduced Row Echelon Form, RREF），其中第一行與第二行為主列（Pivot columns），第三行為自由變數（Free variable）。

令自由變數 $y_3 = t$（其中 $t \in \mathbb{R}$）：
$y_1 = -2t$
$y_2 = 4t$
$y_3 = t$

解集合可表為：
$y = t \begin{bmatrix} -2 \\ 4 \\ 1 \end{bmatrix}, \quad t \in \mathbb{R}$

核心觀念

1. 矩陣轉置與對稱矩陣（Symmetric Matrix）：
   一個 $n \times n$ 的實數方陣 $A$，若滿足轉置矩陣等於原矩陣，即 $A^T = A$，則稱 $A$ 為對稱矩陣。

2. 列空間維度與矩陣之秩（Rank of Matrix）：

   • 矩陣 $B$ 的列空間（Row Space）維度等於 $B$ 的秩（Rank），即 $\dim(\text{Row}(B)) = \text{rank}(B) = n$。
   • 由於 $B$ 為 $m \times n$ 矩陣，且行數（Column number）為 $n$，$\text{rank}(B) = n$ 代表矩陣 $B$ 為滿行秩（Full Column Rank）。

3. 秩與零化度定理（Rank-Nullity Theorem）：
   對於 $m \times n$ 矩陣 $B$，其定義域空間維度為 $n$，滿足：
   $\text{rank}(B) + \text{nullity}(B) = n$
   其中 $\text{nullity}(B) = \dim(\text{Null}(B))$ 為零空間維度。當 $\text{rank}(B) = n$ 時，$\text{nullity}(B) = 0$，代表零空間只包含零向量，即齊次方程組 $B\mathbf{x} = \mathbf{0}$ 只有唯一解 $\mathbf{x} = \mathbf{0}$。

4. 正定矩陣定義（Positive Definite Matrix）：
   一個 $n \times n$ 的實數對稱矩陣 $A$ 為正定矩陣，當且僅當對所有非零向量 $\mathbf{x} \in \mathbb{R}^n$（$\mathbf{x} \neq \mathbf{0}$），其二次型（Quadratic Form）皆嚴格大於零：
   $\mathbf{x}^T A \mathbf{x} > 0$

---

解題方法

要證明 $n \times n$ 方陣 $B^T B$ 為對稱正定矩陣，必須分別證明其滿足「對稱性」與「正定性」兩個條件。

階段一：證明 $B^T B$ 為對稱矩陣（Symmetric）

1. 維度確認：矩陣 $B$ 的維度為 $m \times n$，其轉置矩陣 $B^T$ 的維度為 $n \times m$。兩者相乘後，$B^T B$ 的維度為 $n \times n$，為實數方陣。
2. 轉置運算：根據矩陣乘法轉置公式 $(XY)^T = Y^T X^T$，對 $B^T B$ 取轉置可得：
   $(B^T B)^T = B^T (B^T)^T = B^T B$
3. 結論：因為 $(B^T B)^T = B^T B$，所以 $B^T B$ 為對稱矩陣。

階段二：證明 $B^T B$ 為正定矩陣（Positive Definite）

1. 建立二次型：任意選取一個非零向量 $\mathbf{x} \in \mathbb{R}^n$（即 $\mathbf{x} \neq \mathbf{0}$），考慮二次型 $\mathbf{x}^T (B^T B) \mathbf{x}$。
2. 轉換為範數長度平方：利用矩陣乘法結合律與向量轉置定義化簡：
   $\mathbf{x}^T (B^T B) \mathbf{x} = (\mathbf{x}^T B^T)(B\mathbf{x}) = (B\mathbf{x})^T (B\mathbf{x}) = \|B\mathbf{x}\|^2$
   其中 $\| \cdot \|$ 為 $\mathbb{R}^m$ 空間上的歐幾里得範數（Euclidean norm）。
3. 判定長度平方之符號：
   • 根據向量範數性質，任何向量長度的平方恆為非負數，即 $\|B\mathbf{x}\|^2 \ge 0$。
   • 依題意，矩陣 $B$ 的列空間維度 $\dim(\text{Row}(B)) = n$。因為列秩等於行秩，故 $\text{rank}(B) = n$。
   • 根據秩與零化度定理：

核心觀念

本題考查離散數學中的命題邏輯（Propositional Logic）與論證有效性證明（Validity of Arguments）。

1. 命題符號化（Propositional Symbolization）：將自然語言敘述轉譯為邏輯命題變數與邏輯連結詞（如蘊涵 $\rightarrow$、否定 $\neg$）。
2. 等價律與推理規則（Rules of Inference）：
   • 換質換位律（Contrapositive Law）：$P \rightarrow Q \equiv \neg Q \rightarrow \neg P$。
   • 假言三段論（Hypothetical Syllogism, HS）：若 $P \rightarrow Q$ 且 $Q \rightarrow R$，則 $P \rightarrow R$。
   • 肯定前項律（Modus Ponens, MP）：若 $P \rightarrow Q$ 且 $P$，則 $Q$。
3. 有效論證的定義（Valid Argument）：
   當所有前提（Premises）皆為真（True）時，結論（Conclusion）必然為真。即前提的連言蘊涵結論：$(P_1 \land P_2 \land P_3) \rightarrow C$ 為永真式（Tautology）。

---

解題方法

步驟一：定義命題變數

定義以下原子命題（Atomic Propositions）：

• $R$：天氣下雨（It is a rainy day / It rains）。
• $G$：花園植物生長（Gardens grow）。
• $H$：天氣炎熱（It is hot）。

步驟二：轉譯前提與結論

將題目中的自然語言敘述轉化為邏輯符號：

1. 前提一（Premise 1, $P_1$）："Rainy days make gardens grow."（下雨天會讓花園生長。）
   $P_1: R \rightarrow G$
2. 前提二（Premise 2, $P_2$）："Gardens don't grow if it is not hot."（如果不熱，花園就不會生長。）
   $P_2: \neg H \rightarrow \neg G$
   利用換質換位律（Contrapositive），$P_2$ 可等價表示為：
   $P_2': G \rightarrow H$
3. 前提三（Premise 3, $P_3$）："It always rains on a day that is not hot."（不熱的日子總是會下雨。）
   $P_3: \neg H \rightarrow R$
4. 結論（Conclusion, $C$）："Therefore, if it is not hot, then it is hot."（因此，如果不熱，那就是熱。）
   $C: \neg H \rightarrow H$

步驟三：邏輯推導證明（Proof of Validity）

方法一：推理規則法（Direct Proof using Rules of Inference）

1. 由 $P_3: \neg H \rightarrow R$ 與 $P_1: R \rightarrow G$，套用假言三段論（Hypothetical Syllogism），可得：
   $\neg H \rightarrow G$
2. 再由 $\neg H \rightarrow G$ 與 $P_2'$ 的等價式 $G \rightarrow H$，再次套用假言三段論，可得：
   $\neg H \rightarrow H$

完整推導鏈如下：
$\neg H \xrightarrow{P_3} R \xrightarrow{P_1} G \xrightarrow{P_2'} H$
由此證明前提 $P_1, P_2, P_3$ 能夠完美邏輯蘊涵結論 $\neg H \rightarrow H$。

核心觀念

本題屬於離散數學與機率論中「離散型隨機變數（Discrete Random Variables）」與「期望值（Expected Value）」的基礎計算題，核心定理與公式包含：

1. 離散隨機變數的期望值定義：
   若離散隨機變數 $X$ 的取值集合為 $\{x_1, x_2, \dots, x_n\}$，對應機率為 $P(X = x_i)$，則期望值定義為：
   $E[X] = \sum_{i=1}^{n} x_i \cdot P(X = x_i)$
2. 期望值的線性性質（Linearity of Expectation）：
   對於任意兩個隨機變數 $X$ 與 $Y$，無論兩者是否獨立，均滿足：
   $E[X + Y] = E[X] + E[Y]$
3. 獨立隨機變數的乘積期望值（Product of Independent Random Variables）：
   若隨機變數 $X$ 與 $Y$ 相互獨立（Independent），則其乘積之期望值滿足：
   $E[X \cdot Y] = E[X] \cdot E[Y]$

---

解題方法

設 $X$ 代表第一顆骰子擲出的點數，$Y$ 代表第二顆骰子擲出的點數。
由於兩顆骰子均為公正的六面骰，點數可能取值為 $\{1, 3, 5, 7, 9, 11\}$，出現各點數的機率均相等，即：
$P(X = x) = P(Y = y) = \frac{1}{6}, \quad \forall x, y \in \{1, 3, 5, 7, 9, 11\}$

步驟一：計算單顆骰子點數的期望值 $E[X]$ 與 $E[Y]$

由期望值定義：

核心觀念

• 平面圖是能在平面上繪製，且任兩條邊只在共同端點相交的圖。
• 在連通無向圖中，歐拉迴路存在的條件是每個頂點的度數皆為偶數；歐拉路徑存在的條件是奇度頂點恰有 $0$ 個或 $2$ 個。
• 哈密頓迴路與哈密頓路徑分別要求每個頂點恰好經過一次並回到起點，或每個頂點恰好經過一次。二分圖的路徑與迴路會在兩個頂點分割間交替。

解題方法

依原卷圖讀取，圖有 $17$ 個頂點、$24$ 條邊；例如頂點 $8$ 的鄰點為 $4,7,9,12$，頂點 $10$ 的鄰點為 $6,9,11,14$。各頂點的鄰點與度數如下：

頂點 $v$	鄰點	度數 $d(v)$
$1$	$2,7$	$2$
$2$	$1,3,5$	$3$
$3$	$2,11$	$2$
$4$	$5,8$	$2$
$5$	$2,4,6,9$	$4$
$6$	$5,10$	$2$
$7$	$1,8,15$	$3$
$8$	$4,7,9,12$	$4$
$9$	$5,8,10,13$	$4$
$10$	$6,9,11,14$	$4$
$11$	$3,10,17$	$3$
$12$	$8,13$	$2$
$13$	$9,12,14,16$	$4$
$14$	$10,13$	$2$
$15$	$7,16$	$2$
$16$	$13,15,17$	$3$
$17$	$11,16$	$2$

度數總和為 $48=2\cdot24$，與握手定理相符。圖連通，奇度頂點是 $2,7,11,16$，共 $4$ 個。

各項判斷

核心觀念

本題考查演算法的遞迴呼叫次數分析與**非齊次線性遞迴關係式（Non-homogeneous Linear Recurrence Relation）**的求解。

關鍵觀念與公式如下：

1. 遞迴關係式建立：透過追蹤程式碼的執行流程與邊界條件（Base Cases），建立代表執行次數的遞迴方程式。
2. 常係數非齊次線性遞迴求解：
   • 將遞迴式寫為 $C(n) - c_1 C(n-1) - c_2 C(n-2) = f(n)$。
   • 齊次解 $C^{(h)}(n)$：由對應齊次方程式之特徵方程式（Characteristic Equation） $r^2 - c_1 r - c_2 = 0$ 的特徵根 $r_1, r_2$ 組成，即 $C^{(h)}(n) = k_1 r_1^n + k_2 r_2^n$。
   • 特解 $C^{(p)}(n)$：根據非齊次項 $f(n)$ 的形式（常數項），設定待定係數進行求解。
   • 通解：$C(n) = C^{(h)}(n) + C^{(p)}(n)$，再利用初始條件求出待定係數 $k_1, k_2$。

---

解題方法

1. 建立遞迴關係式與初始條件

設 $C(n)$ 為呼叫 XXX(n) 時，全域變數 count 所累加的總次數。

• 邊界條件（$n=1, 2$）：
  當 $n=1$ 或 $n=2$ 時，滿足 if (n=1) or (n=2) 條件，直接執行 count = count + 1 後返回，故初始條件為：
  $C(1) = 1$
  $C(2) = 1$

• 遞迴關係式（$n \ge 3$）：
  當 $n \ge 3$ 時，進入 else 區塊，依次執行：

  1. XXX(n-2)：增加 count 次數 $C(n-2)$
  2. XXX(n-1)：增加 count 次數 $C(n-1)$
  3. XXX(n-2)：增加 count 次數 $C(n-2)$
  4. count = count + 1：增加 count 次數 $1$

  因此可得遞迴關係式：
  $C(n) = C(n-2) + C(n-1) + C(n-2) + 1 = C(n-1) + 2C(n-2) + 1 \quad (n \ge 3)$
  移項整理得：
  $C(n) - C(n-1) - 2C(n-2) = 1$

2. 計算 XXX(5) 執行後 count 的最終值

利用遞迴關係式逐步計算：

• $C(1) = 1$
• $C(2) = 1$
• $C(3) = C(2) + 2C(1) + 1 = 1 + 2(1) + 1 = 4$
• $C(4) = C(3) + 2C(2) + 1 = 4 + 2(1) + 1 = 7$
• $C(5) = C(4) + 2C(3) + 1 = 7 + 2(4) + 1 = 16$

執行 XXX(5) 後 count 的最終值為 16。

3. 求解一般式 $C(n)$

(a) 求解齊次解 $C^{(h)}(n)$

對應的齊次方程式為：
$C(n) - C(n-1) - 2C(n-2) = 0$
特徵方程式為：
$r^2 - r - 2 = 0 \implies (r-2)(r+1) = 0$
解得特徵根為 $r_1 = 2, r_2 = -1$。
故齊次解為：
$C^{(h)}(n) = k_1 \cdot 2^n + k_2 \cdot (-1)^n$

(b) 求解特解 $C^{(p)}(n)$

由於非齊次項為常數 $1$，且 $r=1$ 非齊次根，設特解為常數 $C^{(p)}(n) = A$。
代入非齊次遞迴式：
$A - A - 2A = 1 \implies -2A = 1 \implies A = -\frac{1}{2}$
故特解為：
$C^{(p)}(n) = -\frac{1}{2}$