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

核心觀念

線性轉換 $T:V\to P_3$ 的秩是像空間 $\operatorname{Im}(T)$ 的維度，零度是核空間 $\ker(T)$ 的維度。由秩零度定理，

$$\dim V=\operatorname{rank}(T)+\operatorname{nullity}(T).$$

$V$ 是 $2\times2$ 實矩陣空間，因此 $\dim V=4$。把 $T(A)$ 寫成多項式係數，可以直接判斷哪些係數彼此獨立。

解題方法

設

$$T\left(\begin{bmatrix}a&b\\c&d\end{bmatrix}\right) =2a+(b-d)x-(a+c)x^2+(a+b-c-d)x^3.$$

要找核空間，令 $T(A)$ 為零多項式。零多項式的各次方係數都必須為零，因此

$$\begin{aligned} 2a&=0,\\ b-d&=0,\\ -(a+c)&=0,\\ a+b-c-d&=0. \end{aligned}$$

核心觀念

本題考查行列式的乘法性質，以及奇數階負單位矩陣的行列式：

$$\det(AB)=\det(A)\det(B),\qquad \det(-I)=(-1)^n.$$

由題設 $A^2+I=O$，可得 $A^2=-I$。對等式兩側取行列式，即可比較兩邊的值。

解題方法

由 $A^2=-I$，取行列式：

$$\det(A^2)=\det(-I).$$

利用行列式的乘法性質，左側為

$$\det(A^2)=\det(A)\det(A)=\bigl(\det(A)\bigr)^2.$$

右側則為

$$\det(-I)=(-1)^n\det(I)=(-1)^n=-1,$$

核心觀念

判斷 $V$ 是否為 $C[-1,1]$ 的子空間，使用子空間判別法：確認零向量在 $V$ 中，且 $V$ 對向量加法與純量乘法封閉。這裡的向量是定義在 $[-1,1]$ 上的連續函數，向量加法與純量乘法皆以函數的方式逐點進行。

解題方法

先確認 $V$ 中的函數都屬於 $C[-1,1]$。由於 $e^x$、$e^{2x}$、$e^{3x}$ 在 $[-1,1]$ 上皆連續，它們的任意線性組合

$$f(x)=ae^x+be^{2x}+ce^{3x}$$

也連續。因此 $V\subseteq C[-1,1]$。

再驗證零函數屬於 $V$。令 $a=b=c=0$，便有

$$f(x)=0e^x+0e^{2x}+0e^{3x}=0,$$

所以零向量在 $V$ 中。

核心觀念

向量空間中的一組向量構成基底，必須同時滿足：

1. 張成空間：空間中的每個向量都能寫成這組向量的線性組合。
2. 線性獨立：這組向量的線性組合等於零向量時，所有係數都必須為零。

本題的向量是函數，因此零向量是區間 $[-1,1]$ 上的零函數。

解題方法

先依照 $V$ 的定義確認 $B$ 張成 $V$，再證明三個函數線性獨立。對線性獨立的部分，將共同因子 $e^x$ 提出，轉化為二次多項式在一整段區間上為零的問題。

證明張成 $V$

依照題目定義，任取 $f\in V$，皆存在 $a,b,c\in\mathbb{R}$，使得

$$f(x)=ae^x+be^{2x}+ce^{3x} =a\,e^x+b\,e^{2x}+c\,e^{3x}.$$

因此，每個 $V$ 中的函數都能由 $B=\{e^x,e^{2x},e^{3x}\}$ 中的函數線性組合表示，故 $B$ 張成 $V$。

證明線性獨立

假設存在 $\alpha,\beta,\gamma\in\mathbb{R}$，使得

核心觀念

要證明 $B'$ 是 $V$ 的一組基底，須證明它張成 $V$且線性獨立。由題目定義，$V$ 由 $e^x,e^{2x},e^{3x}$ 張成；先確認這三個函數線性獨立，便知 $\dim V=3$。接著可將 $B'$ 的三個函數寫成這組基底的座標，利用行列式是否為零判斷線性獨立。

解題方法

先證明 $\{e^x,e^{2x},e^{3x}\}$ 線性獨立。若

$$\alpha e^x+\beta e^{2x}+\gamma e^{3x}=0$$

對所有 $x\in[-1,1]$ 成立，令 $t=e^x$，則 $t$ 遍歷區間 $[e^{-1},e]$，且

$$\alpha t+\beta t^2+\gamma t^3=0.$$

左側是多項式，若它在整個區間上皆為零，便只能是零多項式，因此 $\alpha=\beta=\gamma=0$。所以 $\{e^x,e^{2x},e^{3x}\}$ 線性獨立。由 $V$ 的定義，這三個函數也張成 $V$，故它們是 $V$ 的一組基底，且 $\dim V=3$。

以 $\{e^x,e^{2x},e^{3x}\}$ 為座標基底，$B'$ 中三個函數的座標分別為

核心觀念

對矩陣的欄向量依序使用 Gram–Schmidt 正交化，可得到正交單位向量 $\mathbf q_1,\mathbf q_2,\mathbf q_3$。令 $Q=[\mathbf q_1\ \mathbf q_2\ \mathbf q_3]$，則 $A=QR$，其中 $R=Q^TA$，且 $r_{ij}=\mathbf q_i^T\mathbf a_j$。

最小平方解則由 $A=QR$ 得到：先計算 $Q^T\mathbf b$，再解上三角系統 $R\mathbf x=Q^T\mathbf b$。

解題方法

設 $A$ 的三個欄向量為 $\mathbf a_1,\mathbf a_2,\mathbf a_3$。題目已給 $\mathbf q_1=\frac12(1,1,1,1)^T$ 與 $r_{11}=2$。

(a) 求 $\mathbf q_2,\mathbf q_3$ 與 $Q$

對第二欄向量，

$$r_{12}=\mathbf q_1^T\mathbf a_2 =\frac12(-3+1-3+1)=-2.$$

扣除 $\mathbf a_2$ 在 $\mathbf q_1$ 方向上的投影，得到

$$\mathbf u_2=\mathbf a_2-r_{12}\mathbf q_1 =\begin{bmatrix}-3\\1\\-3\\1\end{bmatrix} +2\begin{bmatrix}1/2\\1/2\\1/2\\1/2\end{bmatrix} =\begin{bmatrix}-2\\2\\-2\\2\end{bmatrix}.$$

因為 $\|\mathbf u_2\|=4$，所以

$$\mathbf q_2=\frac{\mathbf u_2}{\|\mathbf u_2\|} =\begin{bmatrix}-1/2\\1/2\\-1/2\\1/2\end{bmatrix}.$$

對第三欄向量，

$$r_{13}=\mathbf q_1^T\mathbf a_3 =\frac12(-5-2+1+4)=-1,$$ $$r_{23}=\mathbf q_2^T\mathbf a_3 =\frac12(5-2-1+4)=3.$$

扣除 $\mathbf a_3$ 在 $\mathbf q_1,\mathbf q_2$ 方向上的投影：

$$\mathbf u_3=\mathbf a_3-r_{13}\mathbf q_1-r_{23}\mathbf q_2 =\begin{bmatrix}-5\\-2\\1\\4\end{bmatrix} +\mathbf q_1-3\mathbf q_2 =\begin{bmatrix}-3\\-3\\3\\3\end{bmatrix}.$$

因為 $\|\mathbf u_3\|=6$，所以

$$\mathbf q_3=\frac{\mathbf u_3}{\|\mathbf u_3\|} =\begin{bmatrix}-1/2\\-1/2\\1/2\\1/2\end{bmatrix}.$$

核心觀念

矩陣序列 $C^n$ 是否收斂，可從矩陣的冪次結構判斷。若 $C$ 是冪等矩陣，也就是 $C^2=C$，則對所有正整數 $n$ 都有 $C^n=C$，因此其極限就是 $C$。

解題方法

直接計算 $C^2$，檢查矩陣是否冪等：

$$C^2= \begin{bmatrix} 3&-1&-2\\ 2&0&-2\\ 2&-1&-1 \end{bmatrix} \begin{bmatrix} 3&-1&-2\\ 2&0&-2\\ 2&-1&-1 \end{bmatrix} = \begin{bmatrix} 3&-1&-2\\ 2&0&-2\\ 2&-1&-1 \end{bmatrix} =C.$$

核心觀念

矩陣指數由冪級數定義：

$$e^C=I+C+\frac{C^2}{2!}+\frac{C^3}{3!}+\cdots.$$

若 $C^2=C$，則所有正次方都滿足 $C^k=C$（$k\ge 1$），因此

$$e^C=I+\left(\sum_{k=1}^{\infty}\frac{1}{k!}\right)C =I+(e-1)C.$$

解題方法

計算 $C^2$：

$$C^2= \begin{bmatrix} 3&-1&-2\\ 2&0&-2\\ 2&-1&-1 \end{bmatrix} \begin{bmatrix} 3&-1&-2\\ 2&0&-2\\ 2&-1&-1 \end{bmatrix} = \begin{bmatrix} 3&-1&-2\\ 2&0&-2\\ 2&-1&-1 \end{bmatrix} =C.$$

核心觀念

存在量詞 $\exists x\,Q(x)$ 表示「定義域中至少有一個整數 $x$，使 $Q(x)$ 為真」。要判定它為真，只需找出一個符合條件的整數作為例子。

解題方法

將 $Q(x)$ 的不等式化簡：

$$x+1>2x$$

兩邊減去 $x$，得到：

$$1>x$$

也就是 $x<1$。定義域是整數，取 $x=0$，符合 $0<1$；代回原式也有：

核心觀念

全稱命題 $\forall x\,Q(x)$ 表示：定義域中的每一個整數 $x$ 都必須使 $Q(x)$ 成立。只要找到一個整數反例，這個全稱命題就為假。

解題方法

將不等式 $x+1>2x$ 移項，兩邊同減 $x$：

$$1>x$$

因此，$Q(x)$ 只在整數 $x<1$ 時成立。取整數 $x=1$，原不等式變成：

$$1+1>2(1)$$

核心觀念

存在量詞 $\exists x$ 表示「至少存在一個符合條件的整數」。$\neg Q(x)$ 表示命題 $Q(x)$ 不成立。

解題方法

題目給定 $Q(x)$ 為 $x+1>2x$。先求出 $Q(x)$ 不成立的條件：

$$\neg Q(x):\quad x+1\le 2x$$

移項得：

$$1\le x$$

核心觀念

本題考查命題的否定與全稱量詞。由於題目定義的論域是整數，$\forall x\,\neg Q(x)$ 表示「每一個整數 $x$ 都不滿足 $Q(x)$」。

解題方法

先化簡 $Q(x)$：

$$x+1>2x \iff 1>x \iff x<1$$

核心觀念

條件命題 $A\to B$ 只有在 $A$ 為真、$B$ 為假時為假；其餘情況皆為真。因此，要判斷一個命題是否為重言式，只要檢查是否存在一組真值，使整個命題為假。

解題方法

本題的前件是 $p$，後件是 $\neg q\lor r$。要使整個條件命題為假，必須同時滿足：

• 前件 $p$ 為真。
• 後件 $\neg q\lor r$ 為假。

析取命題只有在兩部分都為假時才為假，因此 $\neg q$ 為假、$r$ 為假，也就是 $q$ 為真、$r$ 為假。

取真值設定

$$p=\text{真},\qquad q=\text{真},\qquad r=\text{假}.$$

核心觀念

條件命題 $A\to B$ 只有在 $A$ 為真、$B$ 為假時為假；其餘情況都為真。等價地，

$$A\to B\equiv \neg A\lor B$$

本題要判斷 $\neg p\to(q\to r)$ 是否對所有 $p,q,r$ 的真值組合都為真。

解題方法

先把內層條件命題改寫：

$$q\to r\equiv \neg q\lor r$$

再改寫外層條件命題：

$$\neg p\to(q\to r) \equiv \neg(\neg p)\lor(\neg q\lor r) \equiv p\lor\neg q\lor r$$

核心觀念

條件命題 $A\to B$ 等價於 $\neg A\lor B$。當前件為假時，條件命題為真；當前件為真時，命題的真假取決於後件。

若一個命題在所有真值指派下都為真，就稱為重言式。

解題方法

將兩個條件命題改寫成析取形式：

$$(p\to q)\lor(\neg p\to r) \equiv (\neg p\lor q)\lor(p\lor r)$$

利用析取運算的結合律與交換律整理：

$$(\neg p\lor p)\lor q\lor r$$

核心觀念

函數 $f:\mathbb{R}\to\mathbb{R}$ 是雙射，須同時滿足：

• 單射：若 $f(x_1)=f(x_2)$，則 $x_1=x_2$。
• 滿射：對每個 $y\in\mathbb{R}$，都存在 $x\in\mathbb{R}$ 使得 $f(x)=y$。

本題的函數是一次函數 $f(x)=ax+b$。當斜率 $a\ne 0$ 時，函數對實數具有唯一的反解，因此是雙射。

解題方法

先檢查單射。令 $x_1,x_2\in\mathbb{R}$，若

$$f(x_1)=f(x_2),$$

則

$$-3x_1+4=-3x_2+4 \quad\Longrightarrow\quad x_1=x_2.$$

核心觀念

函數 $f:\mathbb{R}\to\mathbb{R}$ 是雙射，必須同時滿足：

• 單射：若 $f(a)=f(b)$，則 $a=b$。
• 滿射：對每個 $y\in\mathbb{R}$，都存在 $x\in\mathbb{R}$ 使得 $f(x)=y$。

只要有一項不成立，函數就不是雙射。

解題方法

題目給定

$$f(x)=-3x^2+7.$$

先檢查單射。取兩個不同的實數 $1$ 與 $-1$：

$$f(1)=-3(1)^2+7=4,\qquad f(-1)=-3(-1)^2+7=4.$$

核心觀念

雙射必須同時滿足「單射」與「滿射」，而且題目指定的函數必須對定義域中的每個實數都有定義。判斷函數是否為從 $\mathbb{R}$ 到 $\mathbb{R}$ 的雙射時，須檢查定義域限制與值域是否涵蓋整個 $\mathbb{R}$。

解題方法

題目給定

$$f(x)=\frac{x+1}{x+2}.$$

分母在 $x=-2$ 時為 $0$，所以 $f(-2)$ 沒有定義。由於題目指定定義域為 $\mathbb{R}$，這個式子並未對每個實數都有定義，因此它不是一個從 $\mathbb{R}$ 到 $\mathbb{R}$ 的函數，當然也不是雙射。

也可檢查其值域。令

$$y=\frac{x+1}{x+2},$$

整理得

$$y(x+2)=x+1,$$ $$(y-1)x=1-2y.$$

核心觀念

函數 $f:\mathbb{R}\to\mathbb{R}$ 是雙射，必須同時滿足：

• 單射：若 $f(a)=f(b)$，則 $a=b$。
• 滿射：對每個 $y\in\mathbb{R}$，都存在 $x\in\mathbb{R}$ 使得 $f(x)=y$。

本題要檢查 $f(x)=x^5+1$ 是否同時符合這兩項條件。

解題方法

先證明單射。若 $f(a)=f(b)$，則

$$a^5+1=b^5+1$$

所以 $a^5=b^5$。實數上的五次方函數嚴格遞增，因此 $a=b$，故 $f$ 為單射。

再證明滿射。任取 $y\in\mathbb{R}$，令

$$x=\sqrt[5]{y-1}$$

核心觀念

題目中的圖是完全二分圖 $K_{m,n}$：每個紅球頂點都與每個藍球頂點相連，因此紅球頂點的度數是 $n$，藍球頂點的度數是 $m$。

最小邊割是指移除後能使圖不連通的最少邊數。要找 $|E'|$，需同時找出一組能斷開圖的邊，並證明任何邊割都不能更小。

解題方法

先看上界：任選一個藍球頂點，它與全部 $m$ 個紅球頂點相連。移除這 $m$ 條邊，就能隔離該藍球頂點，因此

$$|E'|\le m.$$

再證明下界。將頂點集合分成非空的兩側 $S$ 與 $V\setminus S$。設 $S$ 中有 $a$ 個紅球頂點、$b$ 個藍球頂點。跨越這個分割的邊數為

$$a(n-b)+(m-a)b.$$

分情況估計：

核心觀念

圖 $G$ 是完全二分圖 $K_{m,n}$：每個紅球頂點都與每個藍球頂點相連，因此共有 $mn$ 條邊。邊割是移除後會使圖不連通的一組邊；最小邊割的大小為完全二分圖的邊連通度：

$$\lambda(K_{m,n})=\min(m,n)=m$$

其中使用了題目給定的 $m<n$。

解題方法

先確認最小邊割 $E'$ 含有幾條邊。移除任一藍球頂點的所有 incident edges（相鄰邊），就會使該頂點孤立；因為每個藍球頂點的度數是 $m$，所以存在大小為 $m$ 的邊割。

也可由一般邊割的形式確認沒有更小的邊割。若將頂點分成兩側，其中一側含有 $a$ 個紅球頂點與 $b$ 個藍球頂點，兩側間的邊數為

$$a(n-b)+(m-a)b$$

核心觀念

零一矩陣的每一列、每一欄分別對應一個長度為 $n$ 的位元字串，因此矩陣共有 $2^n$ 列與 $2^n$ 欄。矩陣中的 $1$ 的總數，就是滿足 $a\preceq b$ 的有序對 $(a,b)$ 數量。

解題方法

固定一個字串 $a$。要找出與 $a$ 恰好在 $k$ 個位元位置不同的字串 $b$，只需從 $n$ 個位置中選出 $k$ 個位置翻轉；其餘位置維持不變。因此，對每個固定的 $a$，共有

核心觀念

計算「至少出現一次連續 GG」的序列數，可以用補集計數：先算全部長度為 $4$ 的 DNA 序列，再扣掉完全沒有連續 GG 的序列。

解題方法

每個位置有 $4$ 種分子，因此長度為 $4$ 的序列共有

$$4^4=256$$

令 $b_n$ 表示長度為 $n$ 且不含連續 GG 的序列數。對這類序列，若最後一個分子是 C、A 或 T，前 $n-1$ 個分子可為任一不含 GG 的序列；若最後一個分子是 G，倒數第二個分子不能是 G，前 $n-2$ 個分子可為任一不含 GG 的序列，而倒數第二個分子有 C、A、T 三種選擇。因此

核心觀念

以補集計數處理「包含連續兩個 G」的序列：先計算不含連續 GG 的序列數，再用全部序列數相減。字母共有 4 種，因此長度為 $n$ 的序列總數是 $4^n$。

令 $b_n$ 表示長度為 $n$ 且不含連續 GG 的序列數，則

$$a_n=4^n-b_n.$$

解題方法

依序列最後一個字母分類 $b_n$：

• 最後一個字母不是 G：前 $n-1$ 個字母可為任一不含 GG 的序列，最後一個字母有 3 種選擇，共 $3b_{n-1}$ 種。
• 最後一個字母是 G：倒數第二個字母不能是 G。前 $n-2$ 個字母可為任一不含 GG 的序列，倒數第二個字母有 3 種非 G 的選擇，共 $3b_{n-2}$ 種。

核心觀念

以「不含連續兩個 G」的序列數作為補集計數。長度為 $n$ 的 DNA 序列總數是 $4^n$，因此不含連續兩個 G 的序列數為 $4^n-a_n$。

解題方法

令 $b_n$ 表示長度為 $n$ 且不含連續兩個 G 的序列數。這類序列可依最後一個字母分類：

• 最後一個字母不是 G：有 $3b_{n-1}$ 種。
• 最後一個字母是 G：前一個字母必須不是 G。前 $n-2$ 個字母可任選不含連續 G 的序列，接著有 $3$ 種非 G 字母，因此有 $3b_{n-2}$ 種。

所以，對 $n\ge 2$，

$$b_n=3b_{n-1}+3b_{n-2}.$$