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

核心觀念

本題考察 RSA 非對稱加密系統（RSA Cryptosystem） 之原理與數論計算，涵蓋以下核心定義與公式：

1. 歐拉函數（Euler's Totient Function）：若 $n = p \times q$（其中 $p, q$ 為相異質數），則其歐拉函數值為：
   $\phi(n) = (p - 1)(q - 1)$
2. 私鑰指數 $d$ 的計算（模逆元）：私鑰指數 $d$ 為公鑰指數 $e$ 在同餘模 $\phi(n)$ 下的模逆元（Modular Inverse），滿足同餘方程式：
   $e \cdot d \equiv 1 \pmod{\phi(n)}$
3. RSA 加密運算：給定明文 $M$（滿足 $0 \le M < n$），其對應之密文 $C$ 的加密公式為：
   $C \equiv M^e \pmod n$

---

解題方法

步驟一：計算歐拉函數 $\phi(n)$
已知兩相異質數 $p = 11$ 與 $q = 29$，模數 $n = p \cdot q = 11 \times 29 = 319$。
計算歐拉函數值：
$\phi(n) = (p - 1)(q - 1) = (11 - 1) \times (29 - 1) = 10 \times 28 = 280$

步驟二：求解私鑰指數 $d$
由 RSA 原理，私鑰指數 $d$ 滿足 $e \cdot d \equiv 1 \pmod{\phi(n)}$，將 $e = 3$ 與 $\phi(n) = 280$ 代入：
$3 \cdot d \equiv 1 \pmod{280}$
利用輾轉相除法觀察 $280$ 與 $3$ 的關係：
$280 = 3 \times 93 + 1 \implies 1 = 280 - 3 \times 93$
兩邊對模 $280$ 取同餘：
$-93 \times 3 \equiv 1 \pmod{280}$
將負同餘轉換為正整數解：
$d \equiv -93 \equiv 280 - 93 = 187 \pmod{280}$
因此，私鑰中使用的指數 $d = 187$。

步驟三：計算明文 $M = 100$ 之加密密文 $C$
根據加密公式 $C \equiv M^e \pmod n$，代入 $M = 100$、$e = 3$ 與 $n = 319$：
$C \equiv 100^3 \pmod{319}$

利用模算術分割指數進行計算：

1. 先求 $100^2 \pmod{319}$：
   $100^2 = 10000$
   除以 $319$ 得：

核心觀念

• 尤拉迴路：經過圖中每條邊恰好一次，並回到起點。連通圖有尤拉迴路的充要條件是每個頂點的度數都是偶數。
• 尤拉路徑：經過圖中每條邊恰好一次。連通圖有尤拉路徑的充要條件是奇數度頂點恰有 $0$ 個或 $2$ 個。
• 哈密頓迴路：恰好經過每個頂點一次，並回到起點。
• 哈密頓路徑：恰好經過每個頂點一次，不要求回到起點。

解題方法

依圖計算各頂點的度數，可得

$$\deg(a)=\deg(b)=\deg(f)=\deg(k)=\deg(m)=2,$$

而

$$\deg(c)=\deg(d)=\deg(e)=\deg(g)=\deg(h)=\deg(i)=\deg(j)=\deg(l)=4.$$

圖形連通，且所有頂點的度數都是偶數，因此有尤拉迴路，也有尤拉路徑。

判斷哈密頓問題時，先利用度數為 $2$ 的頂點：若這類頂點不是哈密頓路徑的端點，哈密頓路徑就必須使用它的兩條相 incident 邊。

逐項判斷

1. 尤拉迴路：有。
   圖連通，且所有頂點都是偶數度，符合尤拉迴路判定定理。

核心觀念

本題涵蓋離散數學（Discrete Mathematics）中組合計數（Combinatorics）的四大核心概念：

1. 不異物排列（Permutations of Multisets）：當待排列元素中包含相同字母時，需除以相同字母數量的階乘以扣除重複計算。
2. 取捨原理／排容原理（Inclusion-Exclusion Principle）：求「滿足條件 A 或條件 B」的集合大小時，利用公式 $|A \cup B| = |A| + |B| - |A \cap B|$。
3. 重複組合與非負整數解（Combinations with Repetition）：方程式 $x_1 + x_2 + \cdots + x_n = k$ 之非負整數解個數為 $H^n_k = C^{n+k-1}_k$。
4. 有限制條件的變數變換（Variable Substitution with Lower Bounds）：當變數存在下界限制（如 $x \ge a$）時，透過變數平移定義新非負變數，將問題轉化為標準重複組合模型。

---

子題詳細推導與分析

(a) 在有多少種排列字母 "APPLE" 的方法？

• 推導與步驟：
  字詞 "APPLE" 共包含 $5$ 個字母，其中字母種類與數量分別為：$\text{A}: 1$ 個、$\text{P}: 2$ 個、$\text{L}: 1$ 個、$\text{E}: 1$ 個。
  根據不異物排列公式，其所有不同的排列數為：
  $\frac{5!}{1! \times 2! \times 1! \times 1!} = \frac{120}{2} = 60$

(b) 這些排列法中，有多少種是以字母 P 開頭或結尾？

• 推導與步驟：
  設 $S$ 為 "APPLE" 所有可能排列的集合，$|S| = 60$。
  定義以下事件集合：

  • $A$：以 $\text{P}$ 開頭的排列集合。
  • $B$：以 $\text{P}$ 結尾的排列集合。

  求「以 $\text{P}$ 開頭或以 $\text{P}$ 結尾」即計算 $|A \cup B|$。由排容原理：
  $|A \cup B| = |A| + |B| - |A \cap B|$

  1. 計算 $|A|$（以 $\text{P}$ 開頭）：
     固定第 1 個位置為 $\text{P}$，剩餘 4 個位置由 $\{\text{A}, \text{P}, \text{L}, \text{E}\}$ 共 $4$ 個互不相同的字母全排列：
     $|A| = 4! = 24$

  2. 計算 $|B|$（以 $\text{P}$ 結尾）：
     固定第 5 個位置為 $\text{P}$，剩餘 4 個位置由 $\{\text{A}, \text{P}, \text{L}, \text{E}\}$ 共 $4$ 個互不相同的字母全排列：
     $|B| = 4! = 24$

  3. 計算 $|A \cap B|$（以 $\text{P}$ 開頭且以 $\text{P}$ 結尾）：
     固定第 1 個與第 5 個位置皆為 $\text{P}$，中間第 2、3、4 位置由剩餘 $3$ 個互異字母 $\{\text{A}, \text{L}, \text{E}\}$ 全排列：
     $|A \cap B| = 3! = 6$

  4. 帶入排容原理：
     $|A \cup B| = 24 + 24 - 6 = 42$

(c) 求 $x + y + z = 25$ 的非負整數解個數，其中 $x, y, z$ 為非負整數。

• 推導與步驟：

核心觀念

本題考查三個基本概念：

1. LU 分解：將矩陣 $A$ 寫成
   $A=LU$
   其中 $L$ 為下三角矩陣，$U$ 為上三角矩陣。高斯消去過程中的消去乘數會放入 $L$。

2. 零空間（nullspace）：
   $\mathcal{N}(A)=\{\mathbf{x}:A\mathbf{x}=\mathbf{0}\}$
   需解齊次方程組 $A\mathbf{x}=\mathbf{0}$。

3. 行空間（column space）：
   欄空間由 $A$ 的所有欄向量張成。其基底應選取原矩陣中對應於主元欄的欄向量。

---

(a) LU 分解

給定

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

以第一欄的 $-6$ 作為第一個主元。

第一步消去第一欄下方元素

第二列的消去乘數為

$$\ell_{21}=\frac{3}{-6}=-\frac12$$

第三列的消去乘數為

$$\ell_{31}=\frac{2}{-6}=-\frac13$$

進行列運算：

$$R_2\leftarrow R_2-\ell_{21}R_1 =R_2+\frac12R_1$$ $$R_2= \begin{bmatrix} 3&-3 \end{bmatrix} +\frac12 \begin{bmatrix} -6&-6 \end{bmatrix} = \begin{bmatrix} 0&-6 \end{bmatrix}$$

同理，

$$R_3\leftarrow R_3-\ell_{31}R_1 =R_3+\frac13R_1$$ $$R_3= \begin{bmatrix} 2&6 \end{bmatrix} +\frac13 \begin{bmatrix} -6&-6 \end{bmatrix} = \begin{bmatrix} 0&4 \end{bmatrix}$$

此時矩陣變為

$$\begin{bmatrix} -6&-6\\ 0&-6\\ 0&4 \end{bmatrix}$$

第二步消去第二欄下方元素

第二個主元為 $-6$，消去乘數為

$$\ell_{32}=\frac{4}{-6}=-\frac23$$

因此

$$R_3\leftarrow R_3-\ell_{32}R_2 =R_3+\frac23R_2$$ $$\begin{bmatrix} 0&4 \end{bmatrix} +\frac23 \begin{bmatrix} 0&-6 \end{bmatrix} = \begin{bmatrix} 0&0 \end{bmatrix}$$

所以

$$U= \begin{bmatrix} -6&-6\\ 0&-6\\ 0&0 \end{bmatrix}$$

將消去乘數放入下三角矩陣，對角線填入 $1$：

$$L= \begin{bmatrix} 1&0&0\\ -\frac12&1&0\\ -\frac13&-\frac23&1 \end{bmatrix}$$

因此

$$\boxed{ A= \begin{bmatrix} 1&0&0\\ -\frac12&1&0\\ -\frac13&-\frac23&1 \end{bmatrix} \begin{bmatrix} -6&-6\\ 0&-6\\ 0&0 \end{bmatrix} }$$

驗算第三列：

$$-\frac13 \begin{bmatrix} -6&-6 \end{bmatrix} -\frac23 \begin{bmatrix} 0&-6 \end{bmatrix} = \begin{bmatrix} 2&6 \end{bmatrix}$$

與原矩陣第三列一致。

---

(b) 零空間

令

核心觀念

本題考查奇異值分解（Singular Value Decomposition, SVD）與特徵值分解的關係。

對於矩陣 $B\in\mathbb{R}^{m\times n}$：

• $B^T B$ 是 $n\times n$ 的對稱矩陣。
• $B^T B$ 的特徵值皆為非負數。
• 若 $\lambda_i$ 是 $B^T B$ 的特徵值，則對應的奇異值為

$$\sigma_i=\sqrt{\lambda_i}.$$

• 若 $v_i$ 是 $B^T B$ 對應於 $\lambda_i$ 的單位特徵向量，則

$$u_i=\frac{Bv_i}{\sigma_i}$$

是左奇異向量。

SVD 可寫成

$$B=U\Sigma V^T.$$

其中 $U$ 與 $V$ 為正交矩陣，$\Sigma$ 為對角形的矩形矩陣。

---

解題方法

題目給定

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

先計算 $B^T B$，再由其特徵值求出奇異值與奇異向量。

---

（a）求 $B^T B$ 的特徵值與特徵向量

由

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

可得

$$B^T B = \begin{bmatrix} 1&0&0\\ 0&2&0 \end{bmatrix} \begin{bmatrix} 1&0\\ 0&2\\ 0&0 \end{bmatrix} = \begin{bmatrix} 1&0\\ 0&4 \end{bmatrix}.$$

特徵值由特徵方程求得：

$$\det(B^T B-\lambda I) = \det \begin{bmatrix} 1-\lambda&0\\ 0&4-\lambda \end{bmatrix} =(1-\lambda)(4-\lambda).$$

因此特徵值為

$$\lambda_1=1,\qquad \lambda_2=4.$$

對應於 $\lambda_1=1$ 的特徵向量

解

$$(B^T B-I)v=0,$$

即

$$\begin{bmatrix} 0&0\\ 0&3 \end{bmatrix} \begin{bmatrix} x\\y \end{bmatrix} = \begin{bmatrix} 0\\0 \end{bmatrix}.$$

可得 $y=0$，因此特徵向量為

$$v_1= \begin{bmatrix} 1\\0 \end{bmatrix}$$

的任意非零倍數。取單位特徵向量為

$$v_1= \begin{bmatrix} 1\\0 \end{bmatrix}.$$

對應於 $\lambda_2=4$ 的特徵向量

解

$$(B^T B-4I)v=0,$$

即

$$\begin{bmatrix} -3&0\\ 0&0 \end{bmatrix} \begin{bmatrix} x\\y \end{bmatrix} = \begin{bmatrix} 0\\0 \end{bmatrix}.$$

可得 $x=0$，因此取單位特徵向量為

$$v_2= \begin{bmatrix} 0\\1 \end{bmatrix}.$$

所以：

$$\boxed{\lambda_1=1,\quad v_1=\begin{bmatrix}1\\0\end{bmatrix}}$$ $$\boxed{\lambda_2=4,\quad v_2=\begin{bmatrix}0\\1\end{bmatrix}}$$

---

（b）求 $B$ 的奇異值分解

第一步：求奇異值

由

$$\sigma_i=\sqrt{\lambda_i},$$

得到

$$\sigma_1=\sqrt{1}=1,\qquad \sigma_2=\sqrt{4}=2.$$

因此奇異值為 $1$ 與 $2$。

---

第二步：求左奇異向量

對於 $\sigma_1=1$：

$$u_1=\frac{Bv_1}{\sigma_1} = B \begin{bmatrix} 1\\0 \end{bmatrix} = \begin{bmatrix} 1\\0\\0 \end{bmatrix}.$$

對於 $\sigma_2=2$：

核心觀念

1. 線性算子（Linear Operator）的定義：
   設 $V$ 為一向量空間（本題中 $V = \mathbb{R}^{n \times n}$）。若映射 $L: V \to V$ 稱為線性算子，當且僅當對所有 $\mathbf{x}, \mathbf{y} \in V$ 及純量 $k \in \mathbb{R}$，皆滿足以下兩條線性公理：

   • 加法性（Additivity）：$L(\mathbf{x} + \mathbf{y}) = L(\mathbf{x}) + L(\mathbf{y})$
   • 齊次性（Homogeneity）：$L(k\mathbf{x}) = k L(\mathbf{x})$

2. 矩陣空間的線性運算性質：
   在矩陣向量空間 $\mathbb{R}^{n \times n}$ 中，純量乘法在矩陣次方運算時滿足 $(k D)^3 = k^3 D^3$。由於次方運算會產生純量的三次項 $k^3$，一般無法保持一次齊次性（$k^1$）。

---

解題方法

要判定映射 $L$ 是否為線性算子，需檢驗其是否對任意矩陣輸入皆滿足「齊次性」與「加法性」。

給定固定矩陣 $C \in \mathbb{R}^{n \times n}$ 與自變數矩陣 $D \in \mathbb{R}^{n \times n}$，映射定義為 $L(D) = C D^3$：

1. 齊次性檢驗：計算純量倍數下的映射值 $L(kD)$，與 $k L(D)$ 比對。
2. 反例證明：選定具體純量 $k = 2$ 與單位矩陣 $I_n$，證明當 $C \neq O$（零矩陣）時兩式矛盾，從而否定其線性性質。

---

選項與命題分析

本題為是非判斷題，需論證「$L(D) = CD^3$ 是否為 $\mathbb{R}^{n \times n}$ 至 $\mathbb{R}^{n \times n}$ 的線性算子」：

1. 齊次性（Homogeneity）分析：
   對任意純量 $k \in \mathbb{R}$ 與矩陣 $D \in \mathbb{R}^{n \times n}$：
   $L(kD) = C(kD)^3 = C(k^3 D^3) = k^3 C D^3 = k^3 L(D)$
   若 $L$ 為線性算子，必須恆滿足 $L(kD) = k L(D)$。