114 年 國立陽明交通大學資訊工程學系碩士班《線性代數與離散數學》

核心觀念

「四個紅色棋子連成一排」表示第 2 列中，存在四個相鄰欄位都放有紅色棋子。題目以 $R(i,j)$ 表示第 $i$ 列、第 $j$ 欄有紅色棋子。

解題方法

圖中的棋盤有 6 列、7 欄。第 2 列的四個相鄰欄位，可能從第 1、2、3 或 4 欄開始；對每種起點，將連續四格的 $R$ 命題用 $\land$ 連接，再將四種情況用 $\lor$ 連接。

解題技巧

核心觀念

「每一欄至少有一個黃色棋子」包含兩個條件：對每一欄而言，該欄六個格子中至少有一格是黃色；而七欄都必須符合此條件。

解題方法

圖中棋盤有 $6$ 列、$7$ 欄，列由 $1$ 到 $6$ 編號，欄由 $1$ 到 $7$ 編號。固定一欄 $j$，用 $\bigvee_{i=1}^{6}Y(i,j)$ 表示該欄至少有一個格子是黃色；再將七欄的條件合取。

核心觀念

「若 $P$，則 $Q$」要寫成 $P\to Q$。「有紅色或黃色，但不能兩者都有」要同時表達「至少一種」與「不是兩種都有」，因此寫成 $(R\lor Y)\land\neg(R\land Y)$。

解題方法

圖中棋盤有 6 列、7 行；$B(i,j)$ 表示該格沒有棋子，因此「該格有棋子」可寫成 $\neg B(i,j)$。

核心觀念

$R$ 與 $S$ 分別是使 $P(x)$、$Q(x)$ 為真的元素集合：

$$R=\{x\in D:P(x)\text{ 為真}\},\qquad S=\{x\in D:Q(x)\text{ 為真}\}.$$

因此，$P(x)\to Q(x)$ 對所有 $x\in D$ 成立，等價於每個使 $P(x)$ 為真的元素也使 $Q(x)$ 為真，也就是 $R\subseteq S$。此外，命題 $P(x)\to Q(x)$ 等價於 $\neg P(x)\lor Q(x)$。

解題方法

逐項將敘述轉成集合關係或命題邏輯，再判斷是否必然成立。若敘述試圖從集合大小推論集合包含，須注意「基數較小或相等」本身不代表「是其子集」。

選項分析

I. $|R|\leq|D|$：正確。

因為 $R$ 是 $D$ 的子集合，即 $R\subseteq D$，子集合的基數不會大於整個集合的基數。因此此敘述必定成立。

II. 若 $\forall x\in D,\ P(x)\to Q(x)$，則 $R\subseteq S$：正確。

對每個 $x\in D$，只要 $P(x)$ 為真，$Q(x)$ 就為真。換言之，每個屬於 $R$ 的元素也屬於 $S$，所以 $R\subseteq S$。

III. 若 $R\cap S=\varnothing$，則 $P(x)\lor Q(x)=T$：錯誤。

核心觀念

本題考查可數無限集合的基數，以及集合的容斥原理。若兩集合 $A$、$B$ 不相交，容斥原理可寫成：

$$|A\cup B|=|A|+|B|$$

其中 $|A|$ 表示集合 $A$ 的基數。題目要求忽略容斥原理是否適用於無限集合，依此形式推導即可。

解題方法

取正偶數集合與正奇數集合：

$$A=\{2,4,6,\ldots\},\qquad B=\{1,3,5,\ldots\}$$

兩集合都能與正整數集合一一對應，因此：

$$|A|=|B|=\aleph_0$$

而且 $A\cap B=\varnothing$，且 $A\cup B=\{1,2,3,\ldots\}$，所以 $|A\cup B|=\aleph_0$。

核心觀念

伺服器是「相同的」，因此只看每個伺服器分到哪些任務，不區分伺服器的名稱。這等同於把 8 個相異任務分成至多 3 個非空群組；允許伺服器空著，所以群組數可以是 1、2 或 3。

將 $n$ 個相異物件分成恰好 $k$ 個非空、彼此不標號的群組，其方法數是第二類 Stirling 數 $S(n,k)$。因此本題所求為

$$S(8,1)+S(8,2)+S(8,3)$$

解題方法

分別計算任務分成 1、2、3 個非空群組的方式。

分成 1 群只有一種：

$$S(8,1)=1$$

核心觀念

這題要把 $8$ 個彼此不同的工作分配給 $3$ 台完全相同的伺服器，且每台都至少分到一項工作。等價於將 $8$ 個不同元素分成 $3$ 個非空、彼此不標號的集合，數量是第二類 Stirling 數 $S(8,3)$。

解題方法

先暫時把伺服器標記為 $A,B,C$，用容斥原理計算每台都至少分到一項工作的分配數。

所有工作分配到三台有標號伺服器的方式共有 $3^8$ 種。扣除至少有一台空著的分配，再加回重複扣除的情形：

核心觀念

任務彼此不同，伺服器彼此相同，因此每種分配對應到一個把 8 個任務分成 3 個非空、互不重疊群組的集合分割。

每台伺服器至少處理 1 項、至多處理 4 項，所以三台伺服器的任務數必須是正整數，且總和為 8。符合條件的任務數組合只有：

$$(4,3,1),\qquad (4,2,2),\qquad (3,3,2)$$

解題方法

先依任務數組合計算分配方式。若三組大小為 $a,b,c$，且大小相異，分組數為

$$\frac{8!}{a!b!c!}$$

若有大小相同的群組，還要再除以相同大小群組的排列數，因為伺服器相同，交換這些群組不會產生新分配。

• 大小為 $(4,3,1)$： 三個群組大小都不同，不需額外除以排列數。

$$\frac{8!}{4!3!1!}=280$$

• 大小為 $(4,2,2)$： 兩個大小為 2 的群組相同，需除以 $2!$。

核心觀念

任務彼此不同、伺服器已標記，因此可先決定三台伺服器各自分配到幾項任務，再用多項式係數計算任務的分配方式。

每台伺服器至少處理一項、至多處理四項，所以若三台伺服器的任務數為 $k_1,k_2,k_3$，必須滿足

$$k_1+k_2+k_3=8,\qquad 1\le k_i\le 4.$$

固定一組任務數後，分配方式為

$$\binom{8}{k_1,k_2,k_3}=\frac{8!}{k_1!k_2!k_3!}.$$

解題方法

先找出符合條件的任務數組合，忽略伺服器標記後只有三種：

• $4,3,1$：排列成三台伺服器的任務數，有 $3!=6$ 種。每種配置的分配方式為 $$\frac{8!}{4!3!1!}=280.$$ 合計 $6\times280=1680$ 種。

核心觀念

關係 $R$ 定義在集合 $A$ 上時，若對每個 $x\in A$，都有 $(x,x)\in R$，則稱 $R$ 為自反關係（reflexive）。

本題的集合為 $A=\{a,b,c,d,e\}$，因此要檢查的有序對是

$$(a,a),\ (b,b),\ (c,c),\ (d,d),\ (e,e).$$

解題方法

核心觀念

關係 $R$ 在集合 $A$ 上為對稱關係，若對所有 $x,y\in A$，只要 $(x,y)\in R$，就必須有 $(y,x)\in R$。也就是說，每一組有序對都要有方向相反的有序對相伴。

解題方法

核心觀念

關係 $R$ 在集合 $A$ 上具有遞移性，是指對任意 $x,y,z\in A$，只要 $(x,y)\in R$ 且 $(y,z)\in R$，就必須有 $(x,z)\in R$。

解題方法

只要找到一組符合前兩個條件、但缺少 $(x,z)$ 的反例，就能判定 $R$ 不具遞移性。

核心觀念

偏序關係須同時滿足：

1. 自反性：對每個 $x\in A$，都有 $(x,x)\in R$。
2. 反對稱性：若 $(x,y)\in R$ 且 $(y,x)\in R$，則 $x=y$。
3. 遞移性：若 $(x,y)\in R$ 且 $(y,z)\in R$，則 $(x,z)\in R$。

解題方法

原關係包含

$$(a,b),\ (b,c),\ (c,d),\ (d,e).$$

它不是偏序關係，因為缺少自反所需的 $(a,a),(b,b),(c,c),(d,d),(e,e)$；也不具遞移性，例如 $(a,b)$ 和 $(b,c)$ 都在 $R$ 中，卻沒有 $(a,c)$。

要補成偏序，原有關係會依遞移性迫使所有較前元素與較後元素之間都成立關係：

核心觀念

兩個圖同構，是指存在頂點間的雙射 $f:V(G)\to V(H)$，使任意兩個頂點的相鄰關係都保持不變：

$$uv\in E(G)\iff f(u)f(v)\in E(H).$$

頂點數、邊數與度數分布相同，是同構的必要條件；要證明同構，仍須給出保持相鄰關係的頂點對應。

解題方法

由原圖可讀出，$G$ 中確實有邊 $ab$；頂點 $e$ 與 $b,c,d,f$ 相鄰。兩圖皆有 $8$ 個頂點、$10$ 條邊，度數分布皆為 $(4,3,3,2,2,2,2,2)$。

完整邊集合如下，其中 $uv$ 表示連接頂點 $u,v$ 的無向邊：

$$E(G)=\{ab,ac,ah,bd,be,ce,de,ef,fg,gh\},$$ $$E(H)=\{12,15,16,23,24,34,45,48,67,78\}.$$

先依度數配對：$G$ 中唯一度數為 $4$ 的頂點 $e$，須對應到 $H$ 中唯一度數為 $4$ 的頂點 $4$；度數為 $3$ 的 $a,b$，則對應到 $1,2$。沿著各頂點的相鄰關係，可建立以下雙射：

核心觀念

兩個圖同構，表示存在一個頂點間的雙射 $f:V(G)\to V(H)$，使得任意兩個頂點 $u,v$ 都滿足

$$uv\in E(G)\iff f(u)f(v)\in E(H).$$

因此，頂點名稱與畫法可以不同，但相鄰關係必須完全一致。頂點度數、三角形及路徑結構，可用來找出對應關係。

解題方法

依原圖，$G$ 有邊 $ab$，沒有邊 $ae$；$H$ 的水平連線經過頂點 $5$，形成邊 $4\!-\!5$ 與 $5\!-\!1$，沒有直接的 $4\!-\!1$ 邊。兩圖皆有 $8$ 個頂點、$10$ 條邊，線段交叉處若未標示頂點，就不視為頂點。

1. 利用度數與三角形決定對應

各頂點的度數為：

度數	$G$ 的頂點	$H$ 的頂點
$4$	$e$	$4$
$3$	$a,b$	$1,2$
$2$	$c,d,f,g,h$	$3,5,6,7,8$

唯一的度數 $4$ 頂點必須對應，因此

$$f(e)=4.$$

$G$ 中的三角形為 $b,d,e$，$H$ 中的三角形為 $2,3,4$。配合度數，可取

$$f(b)=2,\qquad f(d)=3.$$

剩下的度數 $3$ 頂點對應為

$$f(a)=1.$$

2. 利用連接路徑決定其餘頂點

$G$ 中連接 $e$ 與 $a$ 的兩條路徑，分別對應到 $H$ 中連接 $4$ 與 $1$ 的路徑：

核心觀念

矩陣 $A$ 可逆的判準是 $\det(A)\ne 0$，等價於 $0$ 不是 $A$ 的特徵值。另一方面，$1$ 是 $A$ 的特徵值，等價於存在非零向量 $v$ 使得 $Av=v$，也等價於 $\det(A-I)=0$。這兩個條件一般並不等價。

解題方法與敘述分析

要判斷「若且唯若」是否成立，須檢查兩個方向；只要有一個反例，整個敘述便為假。

• 可逆不代表 $1$ 是特徵值。 取 $A=2I$。此矩陣可逆，但其特徵值皆為 $2$，所以 $1$ 不是特徵值。
• $1$ 是特徵值不代表矩陣可逆。 取

核心觀念

$W$ 的正交補空間定義為

$$W^\perp=\{x\in\mathbb{R}^n:\ x\cdot w=0\text{，對所有 }w\in W\}.$$

要判斷 $W^\perp$ 是否為 $\mathbb{R}^n$ 的子空間，可檢查它是否包含零向量，並且對向量加法與純量乘法封閉。

解題方法

因為 $W$ 是子空間，所以 $0\in W$；依定義，$W^\perp$ 中的向量必須與 $W$ 中每個向量都正交。

首先，對所有 $w\in W$，有 $0\cdot w=0$，因此 $0\in W^\perp$。

再取任意 $x,y\in W^\perp$ 與純量 $c\in\mathbb{R}$。對所有 $w\in W$，

$$(x+y)\cdot w=x\cdot w+y\cdot w=0+0=0,$$

核心觀念

矩陣 $A$ 的零空間定義為

$$\mathcal{N}(A)=\{x\in\mathbb{R}^n:Ax=0\}.$$

初等矩陣 $E$ 是由單位矩陣經一次初等列運算得到的矩陣，因此 $E$ 可逆。左乘 $E$ 相當於對矩陣方程的等式左側施行可逆的列運算，不會改變方程的解集合。

解題方法

比較 $EAx=0$ 與 $Ax=0$ 的解。由於 $E$ 可逆，

$$EAx=0 \iff E^{-1}EAx=E^{-1}0 \iff Ax=0.$$

核心觀念

函數 $h$ 位於 $f$ 與 $g$ 張成的空間，表示存在常數 $a,b$，使得對所有 $x$ 都有

$$h(x)=a f(x)+b g(x).$$

因此，只要找到兩個輸入值，使 $f,g$ 的值相同、但 $h$ 的值不同，就能否定這種線性組合的存在。

解題方法

取 $x=0$ 與 $x=\pi$。由三角函數的週期性，

$$f(0)=f(\pi)=1,\qquad g(0)=g(\pi)=0.$$

核心觀念

齊次線性系統 $A\mathbf{x}=0$ 的解集合是 $A$ 的零空間。依秩－零度定理，

$$\operatorname{rank}(A)+\operatorname{nullity}(A)=n,$$

其中 $n$ 是未知數的個數，而零度也就是通解中自由參數的個數。

解題方法

核心觀念

矩陣 $A$ 有 $6$ 個欄，因此線性映射 $A\mathbf{x}=0$ 的定義域是 $\mathbb{R}^6$。此齊次方程組的解空間就是 $A$ 的零空間，其維度稱為零度（nullity）。

秩－零度定理指出：

$$\operatorname{rank}(A)+\operatorname{nullity}(A)=\text{欄數}$$

解題方法

核心觀念

向量 $(k,21,-12)$ 是 $(-2,2,1)$ 與 $(2,1,-2)$ 的線性組合，表示存在純量 $a,b$，使得

$$(k,21,-12)=a(-2,2,1)+b(2,1,-2).$$

將向量分量相等，可得到聯立方程；先由已知的第二、第三分量求出 $a,b$，再計算第一分量的 $k$。

解題方法

分量相等後，得到

$$\begin{cases} -2a+2b=k,\\ 2a+b=21,\\ a-2b=-12. \end{cases}$$

核心觀念

$6\times6$ 行列式的展開式 $\sum_\sigma \operatorname{sgn}(\sigma)\prod_i a_{i,\sigma(i)}$ 中，一項非零的條件是：每一列各選一個 $*$，而且選到的六個位置欄都不相同。所以要數的是「在 $*$ 的位置上放 6 個互不同列、不同欄的棋子」有幾種放法。

把各列的 $*$ 位置列出（欄編號 1–6）：

列	$*$ 所在的欄
1	1, 3, 4, 6
2	3, 4, 6
3	2, 3, 4, 5
4	2, 3, 5
5	2, 3, 4, 5
6	1, 3, 4, 6

解題方法

觀察結構。 第 2 欄與第 5 欄的 $*$ 只出現在第 3、4、5 列；而第 3、4、5 列在第 1、6 欄都是 0。所以第 3、4、5 列必須占用第 2、5 欄，再加上第 3、4 欄中的一欄；剩下的那一欄連同第 1、6 欄，交給第 1、2、6 列。

情況一：第 3、4、5 列用欄 $\{2,3,5\}$。

核心觀念

二次型可寫成矩陣形式：

$$\begin{bmatrix}x&y\end{bmatrix} A \begin{bmatrix}x\\y\end{bmatrix}.$$

若 $A$ 是實對稱矩陣，依據譜定理，存在正交矩陣 $Q$ 與對角矩陣 $D$，使 $A=QDQ^T$。$D$ 的對角元素是 $A$ 的特徵值，$Q$ 的各欄則是對應的單位特徵向量。

解題方法

由於 $xy$ 項的係數是 $24$，矩陣的兩個非對角元素各為 $12$，因此

$$A= \begin{bmatrix} 6&12\\ 12&-1 \end{bmatrix}.$$

先求特徵值：

$$\det(A-\lambda I) = \begin{vmatrix} 6-\lambda&12\\ 12&-1-\lambda \end{vmatrix} = \lambda^2-5\lambda-150 = (\lambda-15)(\lambda+10).$$

因此特徵值為 $15$ 與 $-10$。

對應 $\lambda=15$，解 $(A-15I)v=0$，可取特徵向量 $(4,3)^T$。正規化後為

$$q_1=\begin{bmatrix}4/5\\3/5\end{bmatrix}.$$

核心觀念

線性轉換 $L:V\to W$ 相對於定義域基底 $B_1$ 與值域基底 $B_2$ 的矩陣，記為 $[L]_{B_2\leftarrow B_1}$。它的第 $j$ 欄，是 $L(B_1)$ 中第 $j$ 個基底向量以 $B_2$ 表示的座標：

$$[L]_{B_2\leftarrow B_1} = \begin{bmatrix} \big| & \big| \\ [L(b_1)]_{B_2} & [L(b_2)]_{B_2} \\ \big| & \big| \end{bmatrix}.$$

解題方法

依序計算 $L$ 對 $B_1$ 兩個基底向量的像，再將每個像寫成 $B_2$ 的線性組合。

令

$$b_1=\begin{bmatrix}1\\2\end{bmatrix}, \qquad b_2=\begin{bmatrix}1\\1\end{bmatrix}.$$

先計算 $b_1$ 的像：

$$L(b_1) = \begin{bmatrix} 5(1)-3(2)\\ 1+2\\ -3(1)+2(2) \end{bmatrix} = \begin{bmatrix}-1\\3\\1\end{bmatrix}.$$

設其 $B_2$ 座標為 $(a,b,c)^T$，則

$$a\begin{bmatrix}1\\2\\1\end{bmatrix} +b\begin{bmatrix}0\\0\\1\end{bmatrix} +c\begin{bmatrix}1\\1\\2\end{bmatrix} = \begin{bmatrix}-1\\3\\1\end{bmatrix}.$$

比較分量可得

$$\begin{cases} a+c=-1,\\ 2a+c=3,\\ a+b+2c=1. \end{cases}$$

由第二式減第一式得 $a=4$，代入第一式得 $c=-5$；再代入第三式得 $b=7$。因此

$$[L(b_1)]_{B_2} = \begin{bmatrix}4\\7\\-5\end{bmatrix}.$$

接著計算 $b_2$ 的像：