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

核心觀念

偏序關係必須同時滿足三個條件：

1. 自反性：對集合中每個元素 $a$，都有 $(a,a)\in R$。
2. 反對稱性：若 $(a,b)\in R$ 且 $(b,a)\in R$，則 $a=b$。
3. 遞移性：若 $(a,b)\in R$ 且 $(b,c)\in R$，則 $(a,c)\in R$。

只要有一項不成立，該關係就不是偏序關係。

解題方法

令 $A=\{0,1,2,3\}$，題目給定的關係為

$$R=\{(0,0),(1,1),(2,0),(2,1),(2,2),(3,2),(3,3)\}$$

依序檢查三個條件。

自反性：成立。
集合 $A$ 中的每個元素都出現在一個自反有序對中：

$$(0,0),(1,1),(2,2),(3,3)\in R$$

核心觀念

偏序關係必須同時滿足：

• 自反性：對集合中每個元素 $a$，都有 $aRa$。
• 反對稱性：若 $aRb$ 且 $bRa$，則 $a=b$。
• 遞移性：若 $aRb$ 且 $bRc$，則 $aRc$。

題目集合為 $\{0,1,2,3\}$，給定關係

$$R=\{(0,0),(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}.$$

解題方法

依序檢查自反性、反對稱性與遞移性；三項都成立，才能判定為偏序關係。

1. 檢查自反性

集合中的每個元素都要與自己形成有序對。關係中包含

$$(0,0),\ (1,1),\ (2,2),\ (3,3),$$

因此 $R$ 具有自反性。

2. 檢查反對稱性

檢查不同元素之間是否同時出現方向相反的有序對。關係中的非對角有序對為

$$(1,2),\ (1,3),\ (2,3).$$

核心觀念

偏序關係必須同時滿足：

• 自反性：對集合中每個元素 $a$，都有 $aRa$。
• 反對稱性：若 $aRb$ 且 $bRa$，則必須有 $a=b$。
• 遞移性：若 $aRb$ 且 $bRc$，則必須有 $aRc$。

只要其中一項不成立，該關係就不是偏序。

解題方法

令題目給定的關係為 $R$。逐一檢查三項定義：

1. 集合 $\{0,1,2,3\}$ 的自反性要求包含 $(0,0)$、$(1,1)$、$(2,2)$、$(3,3)$；這四個有序對都在 $R$ 中，因此 $R$ 具有自反性。

核心觀念

遞迴定義是用前面的項來表示後面的項，並提供足夠的初始值。由於本題的 $(-1)^n$ 每增加 $2$ 次方便回到原值，數列每兩項循環一次。

解題方法

先代入前兩個正整數，求出初始值：

$$a_1=1+(-1)^1=0,\qquad a_2=1+(-1)^2=2.$$

再觀察 $n$ 與 $n-2$ 的奇偶性相同，因此 $(-1)^n=(-1)^{n-2}$，所以

核心觀念

遞迴定義要用前一項或前幾項表示目前項，並指定初始值。此題可利用相鄰兩項的差，將 $a_n=n(n+1)$ 改寫成遞迴關係。

解題方法

先求初始值：

$$a_1=1(1+1)=2.$$

對 $n\ge 2$，計算相鄰兩項的差：

$$a_n-a_{n-1} =n(n+1)-(n-1)n =2n.$$

因此，

核心觀念

有向圖的歐拉迴路會從指定頂點出發，恰好走過每一條有向邊一次，並回到起點。若圖中所有頂點都滿足入度等於出度，且邊所在部分連通，便存在歐拉迴路。

解題方法

圖中頂點為 $a,b,c,d,e$；有向邊依序為
$a\to d$、$b\to a$、$c\to b$、$d\to e$、$d\to b$、$b\to d$、$b\to e$、$e\to b$、$e\to c$。特別注意，$b,d$ 之間及 $b,e$ 之間各有兩條方向相反的邊。

逐點計算入度與出度：

核心觀念

有向圖的歐拉迴路會從指定頂點出發，恰好走過每一條有向邊一次，並回到起點。若圖中所有頂點都滿足入度等於出度，且邊所在部分連通，便存在歐拉迴路。

解題方法

圖中頂點為 $a,b,c,d,e$；有向邊依序為
$a\to d$、$b\to a$、$c\to b$、$d\to e$、$d\to b$、$b\to d$、$b\to e$、$e\to b$、$e\to c$。特別注意，$b,d$ 之間及 $b,e$ 之間各有兩條方向相反的邊。

逐點計算入度與出度：

核心觀念

函數值域是所有輸出值所成的集合。若定義域是有限集合，值域中的元素數量不會超過定義域中的元素數量；當函數為單射時，每個定義域元素都對應到不同的輸出，值域基數便能達到上限。

解題方法

設 $|N|=n$。有限集合 $N$ 的冪集合 $\mathcal{P}(N)$ 包含 $N$ 的所有子集合，因此

$$|\mathcal{P}(N)|=2^n.$$

核心觀念

題目給定的條件表示：對任意集合 $S_1,S_2\subseteq N$，

$$f(S_1)+f(S_2)\leq f(S_1\cup S_2)+f(S_1\cap S_2).$$

這是超模性（supermodularity）的定義。它也蘊含「邊際增加量遞增」：加入同一元素時，原本的集合越大，函數值增加量越大。

解題方法

利用 $C\subseteq T$ 且 $i\in N-T$，選取

$$S_1=C\cup\{i\},\qquad S_2=T.$$

因為 $i\notin T$ 且 $C\subseteq T$，所以

$$S_1\cup S_2=T\cup\{i\},\qquad S_1\cap S_2=C.$$

將這兩個集合代入超模性條件，得到

核心觀念

本題考「反證法」與「質數的基本性質」：每個大於 $1$ 的整數都有質因數。先假設質數只有有限多個，再構造一個整數，使它除以清單中的任一質數都餘 $1$，從而導出矛盾。

解題方法

令假設中的所有質數為 $p_1,p_2,\ldots,p_n$，取

$$q=p_1p_2\cdots p_n+1.$$

對每個 $i=1,2,\ldots,n$，都有

$$q\equiv 1\pmod{p_i},$$

所以清單中的任何質數 $p_i$ 都不整除 $q$。

核心觀念

命題 $P(x)\to Q(x)$ 只有在 $P(x)$ 為真、$Q(x)$ 為假時才為假。因此，全稱命題 $\forall x\in S\,(P(x)\to Q(x))$ 成立，表示 $S$ 不能包含任何使前件為真、後件為假的元素。

存在命題 $\exists x\in S\,(P(x)\land Q(x))$ 不成立，表示 $S$ 不能包含同時滿足 $P(x)$ 與 $Q(x)$ 的元素。

解題方法

先在定義域 $U=\{2,3,4,5,6,7,8,9,10\}$ 中找出質數與符合同餘條件的數：

$$P=\{2,3,5,7\},\qquad Q=\{3,8\}.$$

使 $P(x)\to Q(x)$ 為假的元素，是 $P\setminus Q$：

$$P\setminus Q=\{2,5,7\}.$$

核心觀念

這題考的是歐幾里得算法與貝祖等式。貝祖等式指出，對正整數 $a,b$，存在整數 $s,t$ 使得

$$\gcd(a,b)=sa-tb$$

先用歐幾里得算法求最大公因數，再將最後的餘數逐步回代，就能得到 $s,t$。

解題方法

對 $a=277$、$b=91$ 連續做帶餘除法：

$$277=3\cdot91+4$$ $$91=22\cdot4+3$$ $$4=1\cdot3+1$$

最後一個非零餘數是 $1$，所以 $\gcd(277,91)=1$。由最後一式開始回代：

$$1=4-3$$

由 $91=22\cdot4+3$ 得 $3=91-22\cdot4$，代入：

核心觀念

行列式具有乘法性：對同階方陣 $B,C$，

$$\det(BC)=\det(B)\det(C).$$

第一類初等矩陣 $E_1$ 是由單位矩陣交換兩列而成，因此

$$\det(E_1)=-1.$$

解題方法

將乘積矩陣 $E_1A$ 的行列式拆開：

$$\det(E_1A)=\det(E_1)\det(A).$$

核心觀念

矩陣乘積的行列式滿足

$$\det(BC)=\det(B)\det(C).$$

第二類初等矩陣是將單位矩陣的一列乘上非零常數；其行列式等於該常數。本題的 $E_2$ 將第二列乘以 $3$，因此 $\det(E_2)=3$。

解題方法

核心觀念

行列式具有乘法性質：對同階方陣 $A$ 與 $B$，

$$\det(AB)=\det(A)\det(B).$$

第三型初等矩陣 $E_3$ 表示將某一列加上另一列的倍數。這種列運算不改變行列式，因此 $\det(E_3)=1$。

解題方法

核心觀念

$E_1$ 是第一類初等矩陣，代表交換單位矩陣的兩列。交換兩列會使行列式變號，因此 $\det(E_1)=-1$。同一個列交換連續做兩次，會回復原狀。

解題方法

利用行列式的乘法性：

核心觀念

行列式具有乘法性質：

$$\det(XY)=\det(X)\det(Y)$$

三種初等矩陣的行列式分別為：

• 第一型：交換兩列，行列式乘上 $-1$。
• 第二型：將一列乘以非零常數 $c$，行列式乘上 $c$。
• 第三型：將一列加上另一列的倍數，行列式不變。

解題方法

對乘積 $E_3E_2E_1$ 使用行列式的乘法性質：

$$\det(E_3E_2E_1) =\det(E_3)\det(E_2)\det(E_1)$$

核心觀念

初等矩陣左乘矩陣，等同對矩陣執行一項列運算。以高斯消去法將 $A$ 化為上三角矩陣時，每一步列運算都可用初等矩陣表示。

若

$$F_3F_2F_1A=U,$$

則

$$A=F_1^{-1}F_2^{-1}F_3^{-1}U=LU.$$

其中 $L$ 為下三角矩陣；若對角線元素全為 $1$，則稱為單位下三角矩陣。

解題方法

依序消去第一欄的第 $2$、$3$ 列元素，再消去第二欄的第 $3$ 列元素。

(a) 求 $F_1,F_2,F_3$ 與 $U$

第一步執行 $R_2\leftarrow R_2-3R_1$，其初等矩陣為

$$F_1= \begin{bmatrix} 1&0&0\\ -3&1&0\\ 0&0&1 \end{bmatrix}.$$

第二步執行 $R_3\leftarrow R_3-2R_1$，其初等矩陣為

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

前兩步後，

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

第三步執行 $R_3\leftarrow R_3+R_2$，其初等矩陣為

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

因此

$$U=F_3F_2F_1A= \begin{bmatrix} 2&1&1\\ 0&1&2\\ 0&0&3 \end{bmatrix}.$$

(b) 求逆矩陣、$L$ 並驗證 $A=LU$

初等列運算的逆運算是將列運算反向執行，故

$$F_1^{-1}= \begin{bmatrix} 1&0&0\\ 3&1&0\\ 0&0&1 \end{bmatrix},\qquad F_2^{-1}= \begin{bmatrix} 1&0&0\\ 0&1&0\\ 2&0&1 \end{bmatrix},\qquad F_3^{-1}= \begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&-1&1 \end{bmatrix}.$$

核心觀念

矩陣的秩是其欄空間或列空間的維度。矩陣經過初等列運算化為列簡化階梯形（RREF）後，秩不變；在 RREF 中，秩等於主元個數，也等於非零列數。

解題方法

題目已給出 $A$ 的 RREF：

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

核心觀念

矩陣的列簡化階梯形與原矩陣列等價，因此兩者具有相同的零空間。已知 $A$ 的簡化列階梯形為 $U$，可直接求解齊次方程組 $Ux=0$。

解題方法

令 $x=(x_1,x_2,x_3,x_4)^T$，由 $Ux=0$ 得

$$\begin{cases} x_1+2x_3+x_4=0,\\ x_2+x_3+4x_4=0. \end{cases}$$

主變數為 $x_1,x_2$，自由變數為 $x_3,x_4$。令 $x_3=s$、$x_4=t$，則

$$x_1=-2s-t,\qquad x_2=-s-4t.$$

因此

核心觀念

列運算相當於在矩陣左側乘上一個可逆矩陣，因此不會改變各欄向量之間的線性關係。若 $U$ 是 $A$ 的簡化列梯形矩陣，且 $U=EA$，其中 $E$ 可逆，則 $A$ 的欄向量關係會與 $U$ 的欄向量關係相同。

解題方法

由題目給出的 $U$，比較第 3 欄與前兩欄：

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

因此 $a_3=2a_1+a_2$。代入已知向量：

$$a_3 = 2\begin{bmatrix}-3\\5\\2\\1\end{bmatrix} + \begin{bmatrix}4\\-3\\7\\-1\end{bmatrix} = \begin{bmatrix}-2\\7\\11\\1\end{bmatrix}.$$

同理，第 4 欄滿足

核心觀念

兩組座標基底都是右手正交基底，因此可用叉積求出第三個基底向量。由一組座標轉換到另一組座標時，旋轉矩陣的欄向量是新基底向量在目標基底下的座標；齊次座標則把旋轉與平移合併成一個 $4\times4$ 矩陣。

解題方法

圖中有兩組右手正交座標系：$B_1=\{e_X,e_Y,e_Z\}$、原點為 $o_1$；$B_2=\{e_U,e_V,e_W\}$、原點為 $o_2$。題目給出 $e_X$ 與 $e_Y$ 在 $B_2$ 下的座標，以及 $o_1-o_2$ 在 $B_2$ 下的座標。

(a) 求 $[e_Z]_{B_2}$

因為 $B_1$ 是右手基底，$e_Z=e_X\times e_Y$。在 $B_2$ 座標下計算：

$$[e_Z]_{B_2} = \begin{bmatrix}1\\0\\0\end{bmatrix} \times \begin{bmatrix}0\\\frac12\\\frac{\sqrt3}{2}\end{bmatrix} = \begin{bmatrix}0\\-\frac{\sqrt3}{2}\\\frac12\end{bmatrix}.$$

(b) 求由 $B_2$ 座標轉成 $B_1$ 座標的旋轉矩陣

先將 $B_1$ 的基底向量依序排列為欄，組成它們在 $B_2$ 下的座標矩陣：

$$C= \begin{bmatrix} [e_X]_{B_2}&[e_Y]_{B_2}&[e_Z]_{B_2} \end{bmatrix} = \begin{bmatrix} 1&0&0\\ 0&\frac12&-\frac{\sqrt3}{2}\\ 0&\frac{\sqrt3}{2}&\frac12 \end{bmatrix}.$$

所以 $[v]_{B_2}=C[v]_{B_1}$。兩組基底正交，故 $C^{-1}=C^T$，由 $B_2$ 轉成 $B_1$ 的矩陣為

$$R=C^T= \begin{bmatrix} 1&0&0\\ 0&\frac12&\frac{\sqrt3}{2}\\ 0&-\frac{\sqrt3}{2}&\frac12 \end{bmatrix}.$$

(c) 求 $[o_1-o_2]_{B_1}$

將題目給的 $B_2$ 座標乘上 $R$：

$$[o_1-o_2]_{B_1} = R[o_1-o_2]_{B_2} = \begin{bmatrix} 1&0&0\\ 0&\frac12&\frac{\sqrt3}{2}\\ 0&-\frac{\sqrt3}{2}&\frac12 \end{bmatrix} \begin{bmatrix}1\\2\\1\end{bmatrix} = \begin{bmatrix} 1\\ 1+\frac{\sqrt3}{2}\\ \frac12-\sqrt3 \end{bmatrix}.$$

(d) 求齊次座標轉換矩陣

核心觀念

矩陣 $M$ 為對稱矩陣的定義是 $M^T=M$，其中轉置只交換列與行的位置，不取複數共軛。因此，矩陣對角線上的元素不受限制；對角線兩側對應位置的元素則必須相等。

解題方法

逐一比較每個矩陣的 $(1,2)$ 與 $(2,1)$ 元素。對角矩陣的非對角元素皆為 $0$，因此一定對稱。

• $A$ 的兩個非對角元素都是 $-1$，所以 $A^T=A$。
• $B$ 的非對角元素分別為 $1$ 與 $0$，所以 $B^T\ne B$。
• $C$ 的非對角元素分別為 $i$ 與 $-i$，兩者不相等，所以 $C^T\ne C$。
• $D$ 的兩個非對角元素都是 $1$，所以 $D^T=D$。
• $E$ 是對角矩陣，所以 $E^T=E$。

矩陣逐一判斷

核心觀念

矩陣 $M$ 為 Hermitian 矩陣，定義是

$$M^H=\overline{M}^{\,T}=M,$$

其中 $M^H$ 表示先取複共軛，再轉置。對元素 $m_{jk}$ 而言，Hermitian 條件等價於

$$m_{jk}=\overline{m_{kj}}.$$

因此，對角線元素必須是實數；非對角線的元素則須互為複共軛。

解題方法與逐一判斷

逐一計算各矩陣的共軛轉置，並檢查是否等於原矩陣。

• 矩陣 $A$：
  $A$ 的元素皆為實數，因此共軛轉置就是轉置。由於

  $$A^T= \begin{bmatrix} 1&-1\\ -1&2 \end{bmatrix} =A,$$

  故 $A$ 是 Hermitian 矩陣。

• 矩陣 $B$：
  $B$ 的元素皆為實數，因此

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

  故 $B$ 不是 Hermitian 矩陣。

• 矩陣 $C$：
  對角線元素 $2$、$1$ 都是實數，且兩個非對角線元素互為複共軛，因為 $\overline{i}=-i$。直接計算：

核心觀念

矩陣 $A$ 是 Hermitian 矩陣，因為 $A^*=A$。由 Hermitian 矩陣的譜定理，$A$ 可由酉矩陣對角化；酉矩陣的各欄須為 $A$ 的兩個正交規一特徵向量。題目要求特徵值依遞減排列，因此 $U$ 的欄依序放入對應於較大、較小特徵值的特徵向量。

解題方法

先求特徵值。矩陣的特徵多項式為

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

因此特徵值依遞減順序為 $\lambda_1=3$、$\lambda_2=0$。

對 $\lambda_1=3$，由 $(A-3I)v=0$ 得

$$-2x+(1-i)y=0, \qquad y=(1+i)x.$$

取 $x=1$，得到特徵向量 $\begin{bmatrix}1\\1+i\end{bmatrix}$。其長度為 $\sqrt{1+|1+i|^2}=\sqrt{3}$，所以規一化後為

$$u_1=\frac{1}{\sqrt{3}} \begin{bmatrix} 1\\ 1+i \end{bmatrix}.$$

對 $\lambda_2=0$，由 $Av=0$ 得

$$x+(1-i)y=0.$$