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

核心觀念

本題考查平面圖、歐拉路徑與歐拉迴路，以及哈密頓路徑與哈密頓迴路的判定。

• 歐拉迴路：每條邊恰好走一次並回到起點。連通圖要有歐拉迴路，所有頂點的度數都必須是偶數。
• 歐拉路徑：每條邊恰好走一次。連通圖要有歐拉路徑，奇度頂點數必須是 $0$ 或 $2$。
• 哈密頓迴路：每個頂點恰好經過一次，並回到起點。
• 哈密頓路徑：每個頂點恰好經過一次。

圖中是正十二面體的骨架圖，共有 $20$ 個頂點，且每個頂點的度數為 $3$。由握手定理，邊數為

$$|E|=\frac{20\cdot 3}{2}=30.$$

解題方法與逐項判斷

1. 是否為平面圖？是

圖形是正十二面體的骨架；將十二面體表面取一個面作為外部面並展開，可得到沒有邊交叉的平面嵌入。因此這個圖是平面圖。

也可用面數驗算：十二面體有 $12$ 個五邊形面，故

$$|V|-|E|+|F|=20-30+12=2,$$

符合連通平面圖的歐拉公式。

2. 是否有歐拉迴路？否

歐拉迴路要求每個頂點的度數都是偶數。此圖的 $20$ 個頂點度數全為 $3$，都是奇數，因此沒有歐拉迴路。

3. 是否有歐拉路徑？否

核心觀念

本題考查離散數學中二元關係（Binary Relation）的基本性質。設 $R$ 為定義在整數集 $\mathbb{Z}$ 上的關係，三大關鍵性質的定義如下：

1. 自反性（Reflexiveness）：
   $\forall x \in \mathbb{Z}, \, (x, x) \in R$
   即集合中的每一個元素都必須與自身滿足關係。

2. 對稱性（Symmetry）：
   $\forall x, y \in \mathbb{Z}, \, (x, y) \in R \implies (y, x) \in R$
   即若 $x$ 與 $y$ 具備關係，則 $y$ 與 $x$ 也必具備關係。

3. 遞移性（Transitivity）：
   $\forall x, y, z \in \mathbb{Z}, \, ((x, y) \in R \land (y, z) \in R) \implies (x, z) \in R$
   即若 $x$ 與 $y$ 具備關係且 $y$ 與 $z$ 具備關係，則 $x$ 與 $z$ 也必具備關係。

邏輯證明原則：

• 證明性質成立：必須對全域 $\mathbb{Z}$ 中的「任意元素」進行一般性代數推導。
• 證明性質不成立：僅需舉出一個具體的「反例（Counterexample）」說明即可。

---

解題方法

本題給定定義在整數集 $\mathbb{Z}$ 上的五個二元關係 $R_1 \sim R_5$。解題時應依序針對每一個關係，分別檢驗其自反性、對稱性與遞移性：

1. 觀察關係之代數結構或算術性質。
2. 若符合定義，以代數符號進行嚴謹推導。
3. 若不符合定義，構造最簡單的整數三元組 $(x, y, z)$ 或二元組 $(x, y)$ 作為反例破除該性質。

---

選項分析

1. 關係 $R_1 = \{(x, y) \mid (x - y)^2 < 10\}$

• 自反性（Reflexive）：成立
  • 證明：對任意 $x \in \mathbb{Z}$，$(x - x)^2 = 0^2 = 0 < 10$，故 $(x, x) \in R_1$。
• 對稱性（Symmetric）：成立
  • 證明：對任意 $x, y \in \mathbb{Z}$，若 $(x, y) \in R_1$，則 $(x - y)^2 < 10$。因為 $(y - x)^2 = (-(x - y))^2 = (x - y)^2 < 10$，故 $(y, x) \in R_1$。
• 遞移性（Transitive）：不成立
  • 反例：取 $x = 0, y = 3, z = 6 \in \mathbb{Z}$。
    • $(0 - 3)^2 = 9 < 10 \implies (0, 3) \in R_1$
    • $(3 - 6)^2 = 9 < 10 \implies (3, 6) \in R_1$
    • 但 $(0 - 6)^2 = 36 \not< 10 \implies (0, 6) \notin R_1$

---

2. 關係 $R_2 = \{(x, y) \mid x + y = 0\}$

• 自反性（Reflexive）：不成立
  • 反例：取 $x = 1 \in \mathbb{Z}$。因 $1 + 1 = 2 \neq 0$，故 $(1, 1) \notin R_2$。
• 對稱性（Symmetric）：成立
  • 證明：對任意 $x, y \in \mathbb{Z}$，若 $(x, y) \in R_2$，則 $x + y = 0$。由加法交換律可得 $y + x = 0$，故 $(y, x) \in R_2$。
• 遞移性（Transitive）：不成立
  • 反例：取 $x = 1, y = -1, z = 1 \in \mathbb{Z}$。
    • $1 + (-1) = 0 \implies (1, -1) \in R_2$
    • $(-1) + 1 = 0 \implies (-1, 1) \in R_2$
    • 但 $1 + 1 = 2 \neq 0 \implies (1, 1) \notin R_2$

---

3. 關係 $R_3 = \{(x, y) \mid \gcd(x, y) = 1\}$

• 自反性（Reflexive）：不成立
  • 反例：取 $x = 2 \in \mathbb{Z}$。因 $\gcd(2, 2) = 2 \neq 1$，故 $(2, 2) \notin R_3$。
• 對稱性（Symmetric）：成立

核心觀念

本題旨在考驗離散數學中組合計數領域的經典主題——錯排問題（Derangement Problem），以及利用排容原理（Inclusion-Exclusion Principle）與樹狀結構分類法求解的技巧。

1. 錯排（Derangement）定義
   對應於集合 $S = \{1, 2, \dots, n\}$ 的全排列 $P = (a_1, a_2, \dots, a_n)$，若滿足對任意 $1 \le i \le n$ 皆有 $a_i \neq i$（即無任何元素留在原本的位置），則稱排列 $P$ 為集合 $S$ 的一個錯排。錯排總個數一般記作 $D_n$ 或 $!n$。

2. 錯排公式（排容原理推導）
   利用排容原理，定義 $P_i$ 為「第 $i$ 個元素落在原位（$a_i = i$）」的性質，錯排總數 $D_n$ 的計算公式為：
   $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)$

3. 錯排遞迴關係式（Recurrence Relation）
   錯排數亦滿足以下二階遞迴關係：
   $D_n = (n-1)(D_{n-1} + D_{n-2}), \quad \text{初始條件：} D_1 = 0, \, D_2 = 1$

---

解題方法

本題分為兩個部分：計算 1234 的錯排總數 $D_4$，以及列出所有 1234 的錯排。

第一部分：計算錯排總數 $D_4$

方法一：排容原理公式法
將 $n = 4$ 代入錯排公式：
$D_4 = 4! \left( \frac{(-1)^0}{0!} + \frac{(-1)^1}{1!} + \frac{(-1)^2}{2!} + \frac{(-1)^3}{3!} + \frac{(-1)^4}{4!} \right)$
$D_4 = 24 \left( 1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} \right)$
$D_4 = 24 \times \left( \frac{12 - 4 + 1}{24} \right) = 24 \times \frac{9}{24} = 9$

方法二：遞迴關係式法
已知初始條件：
$D_1 = 0, \quad D_2 = 1$
計算 $D_3$ 與 $D_4$：
$D_3 = (3-1)(D_2 + D_1) = 2 \times (1 + 0) = 2$
$D_4 = (4-1)(D_3 + D_2) = 3 \times (2 + 1) = 9$

經由上述方法求得錯排總數皆為 9。

第二部分：列舉 1234 的所有錯排

設排列為 $a_1 a_2 a_3 a_4$，原位限制條件為 $a_1 \neq 1, a_2 \neq 2, a_3 \neq 3, a_4 \neq 4$。
採用樹狀結構分類法，依據第一個數位 $a_1$ 的可能取值（$2, 3, 4$）進行系統化列舉：

1. 當 $a_1 = 2$ 時：可選的剩餘數字為 $\{1, 3, 4\}$。

   • 若 $a_2 = 1$，剩餘 $\{3, 4\}$ 填入第 3, 4 位，因 $a_3 \neq 3, a_4 \neq 4$，故只能填 $a_3=4, a_4=3 \implies \mathbf{2143}$。
   • 若 $a_2 = 3$，剩餘 $\{1, 4\}$ 填入第 3, 4 位，因 $a_4 \neq 4$，故只能填 $a_3=4, a_4=1 \implies \mathbf{2341}$。
   • 若 $a_2 = 4$，剩餘 $\{1, 3\}$ 填入第 3, 4 位，因 $a_3 \neq 3$，故只能填 $a_3=1, a_4=3 \implies \mathbf{2413}$。
   • （註：$a_2$ 不能為 2，故此分支共 3 個錯排）

2. 當 $a_1 = 3$ 時：可選的剩餘數字為 $\{1, 2, 4\}$。

   • 若 $a_2 = 1$，剩餘 $\{2, 4\}$ 填入第 3, 4 位，因 $a_4 \neq 4$，故只能填 $a_3=4, a_4=2 \implies \mathbf{3142}$。
   • 若 $a_2 = 4$，剩餘 $\{1, 2\}$ 填入第 3, 4 位，此時填入第 3, 4 位均不違反原位限制，產生兩種填法：
     • $a_3=1, a_4=2 \implies \mathbf{3412}$
     • $a_3=2, a_4=1 \implies \mathbf{3421}$

核心觀念

本題考查離散數學與數論中的線性同餘方程式（Linear Congruence Equation）與簡化法則。

主要涉及的定義與定理如下：

1. 線性同餘方程式的可解性定理：
   對於同餘方程式 $ax \equiv b \pmod m$，設 $d = \gcd(a, m)$：
   • 若 $d \nmid b$（$d$ 無法整除 $b$），則該同餘方程式無整數解。
   • 若 $d \mid b$（$d$ 能整除 $b$），則該同餘方程式在模 $m$ 下恰有 $d$ 個互不同餘的解。
2. 同餘方程式的簡化法則：
   若 $ax \equiv b \pmod m$，且 $d = \gcd(a, b, m)$，可將同餘式各項與模數同時除以 $d$，簡化為：
   $\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{m}{d}}$
3. 模逆元（Modular Multiplicative Inverse）：
   在簡化後的同餘式 $a'x \equiv b' \pmod{m'}$ 中，若 $\gcd(a', m') = 1$，則 $a'$ 在模 $m'$ 下存在乘法逆元 $(a')^{-1}$，其解可表示為 $x \equiv (a')^{-1} \cdot b' \pmod{m'}$。

---

解題方法

步驟一：求最大公因數並判斷解的存在性
給定同餘方程式 $18x \equiv 6 \pmod{141}$。
令 $a = 18$, $b = 6$, $m = 141$。使用輾轉相除法求 $d = \gcd(18, 141)$：
$141 = 18 \times 7 + 15$
$18 = 15 \times 1 + 3$
$15 = 3 \times 5 + 0$
得 $d = \gcd(18, 141) = 3$。

因為 $3 \mid 6$（最大公因數整除右側常數），故本題存在整數解，且在模 $141$ 下恰有 $3$ 個互不同餘的解。

步驟二：同除公因數簡化同餘方程式
將同餘式係數與模數同時除以 $d = 3$：
$\frac{18}{3}x \equiv \frac{6}{3} \pmod{\frac{141}{3}}$
得到簡化後的同餘式：
$6x \equiv 2 \pmod{47}$

步驟三：求解簡化後的同餘方程式
因為 $\gcd(2, 47) = 1$，可將兩邊係數同除以 $2$：
$3x \equiv 1 \pmod{47}$

求解 $3$ 在模 $47$ 下的乘法逆元。利用凑數法，注意到 $1 + 47 = 48$ 為 $3$ 的倍數：
$3x \equiv 48 \pmod{47}$
兩邊同除以 $3$（因 $\gcd(3, 47) = 1$）：
$x \equiv 16 \pmod{47}$

設 $B=(A^T)^T$。因 $A$ 為 $m\times n$ 矩陣，故 $B$ 亦為 $m\times n$ 矩陣，且對所有 $1\le i\le m$、$1\le j\le n$，

$$b_{ij}=(A^T)_{ji}=a_{ij}.$$

因此 $A$ 與 $B$ 大小相同且對應元素皆相等，故

$$(A^T)^T=A.$$

又 $\vec e_i$ 的第 $i$ 個分量為 $1$，其餘分量皆為 $0$。故對每個 $1\le r\le m$，

核心觀念

本題考查矩陣的**高斯消去法（Gauss Elimination）與高斯–若爾當消去法（Gauss-Jordan Elimination）**求反矩陣（Inverse Matrix）。

1. 增廣矩陣與列運算：
   若 $A$ 為 $n \times n$ 可逆矩陣，求其反矩陣 $A^{-1}$ 的標準程序為建立增廣矩陣 $[A \mid I_n]$，透過**基本列運算（Elementary Row Operations, EROs）**將左側矩陣 $A$ 化簡為單位矩陣 $I_n$。當左側化為 $I_n$ 時，右側即為反矩陣 $A^{-1}$：
   $[A \mid I_n] \xrightarrow{\text{EROs}} [I_n \mid A^{-1}]$

2. 題目指定之兩階段化簡：

   • 第一階段（高斯消去）：將增廣矩陣進行向下消去，化為列階梯形（Row Echelon Form, REF）。
   • 第二階段（高斯–若爾當消去）：自 REF 繼續向上消去，化為簡化列階梯形（Reduced Row Echelon Form, RREF），以獲取反矩陣 $A^{-1}$。

---

解題方法

建立 $3 \times 3$ 增廣矩陣 $[A \mid I_3]$：
$[A \mid I_3] = \begin{bmatrix} 1 & 2 & 3 & \mid & 1 & 0 & 0 \\ 2 & 5 & 6 & \mid & 0 & 1 & 0 \\ 3 & 4 & 8 & \mid & 0 & 0 & 1 \end{bmatrix}$

第一階段：將增廣矩陣化為列階梯形（Row Echelon Form, REF）

1. 以第 1 列的主項（Pivot） $a_{11} = 1$ 消去第 2 列與第 3 列的第一行元素：

   • $R_2 \leftarrow R_2 - 2R_1$
   • $R_3 \leftarrow R_3 - 3R_1$

   $\begin{bmatrix} 1 & 2 & 3 & \mid & 1 & 0 & 0 \\ 0 & 1 & 0 & \mid & -2 & 1 & 0 \\ 0 & -2 & -1 & \mid & -3 & 0 & 1 \end{bmatrix}$

2. 以第 2 列的主項 $a_{22} = 1$ 消去第 3 列的第二行元素：

   • $R_3 \leftarrow R_3 + 2R_2$

   $\begin{bmatrix} 1 & 2 & 3 & \mid & 1 & 0 & 0 \\ 0 & 1 & 0 & \mid & -2 & 1 & 0 \\ 0 & 0 & -1 & \mid & -7 & 2 & 1 \end{bmatrix}$

3. 將第 3 列的主項化為 $1$：

   • $R_3 \leftarrow -1 \cdot R_3$

   得到列階梯形（REF）：
   $\begin{bmatrix} 1 & 2 & 3 & \mid & 1 & 0 & 0 \\ 0 & 1 & 0 & \mid & -2 & 1 & 0 \\ 0 & 0 & 1 & \mid & 7 & -2 & -1 \end{bmatrix}$

---

第二階段：由列階梯形繼續化為簡化列階梯形（Reduced Row Echelon Form, RREF）

核心觀念

特徵值 $\lambda$ 的定義是存在非零向量 $\mathbf{x}$，使得

$$A\mathbf{x}=\lambda\mathbf{x}.$$

等價地，

$$(A-\lambda I)\mathbf{x}=\mathbf{0}$$

具有非零解，因此特徵值必須滿足特徵方程

$$\det(\lambda I-A)=0.$$

求出特徵值後，再對每個 $\lambda$ 解齊次方程組 $(A-\lambda I)\mathbf{x}=\mathbf{0}$，其解集合即為對應的特徵空間。

---

解題方法

給定

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

一、求特徵多項式

計算 $\det(A-\lambda I)$：

$$A-\lambda I= \begin{bmatrix} -2-\lambda&-6&-6\\ -3&2-\lambda&-2\\ 3&2&6-\lambda \end{bmatrix}.$$

沿第一列展開：

$$\begin{aligned} \det(A-\lambda I) ={}&(-2-\lambda) \begin{vmatrix} 2-\lambda&-2\\ 2&6-\lambda \end{vmatrix} +6 \begin{vmatrix} -3&-2\\ 3&6-\lambda \end{vmatrix}\\ &-6 \begin{vmatrix} -3&2-\lambda\\ 3&2 \end{vmatrix}. \end{aligned}$$

各二階行列式為

$$\begin{vmatrix} 2-\lambda&-2\\ 2&6-\lambda \end{vmatrix} =(2-\lambda)(6-\lambda)+4 =(\lambda-4)^2,$$ $$\begin{vmatrix} -3&-2\\ 3&6-\lambda \end{vmatrix} =-3(6-\lambda)+6 =3(\lambda-4),$$ $$\begin{vmatrix} -3&2-\lambda\\ 3&2 \end{vmatrix} =-6-3(2-\lambda) =3(\lambda-4).$$

因此

$$\begin{aligned} \det(A-\lambda I) &=(-2-\lambda)(\lambda-4)^2 +18(\lambda-4)-18(\lambda-4)\\ &=-(\lambda+2)(\lambda-4)^2. \end{aligned}$$

採用首項係數為正的特徵多項式：

$$p_A(\lambda)=\det(\lambda I-A) =(\lambda+2)(\lambda-4)^2.$$

所以特徵值為

$$\lambda=-2,\qquad \lambda=4.$$

其中 $\lambda=4$ 的代數重數為 $2$。

---

二、求 $\lambda=-2$ 的特徵空間

令 $\lambda=-2$，解

$$(A+2I)\mathbf{x}=\mathbf{0}.$$

有

$$A+2I= \begin{bmatrix} 0&-6&-6\\ -3&4&-2\\ 3&2&8 \end{bmatrix}.$$

令 $\mathbf{x}=(x,y,z)^T$，方程組為

$$\begin{cases} -6y-6z=0,\\ -3x+4y-2z=0,\\ 3x+2y+8z=0. \end{cases}$$

第一式給出

$$y+z=0\quad\Longrightarrow\quad z=-y.$$