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

核心觀念

對 $n\times n$ 方陣 $A$，**非奇異（nonsingular）**的定義是 $A$ 可逆，也就是存在矩陣 $A^{-1}$ 使得

$$AA^{-1}=A^{-1}A=I.$$

若矩陣元素取自一個域，例如實數或複數，以下條件彼此等價：

• $A$ 可逆；
• 存在矩陣 $B$ 使 $AB=BA=I$；
• $\det(A)\ne 0$；
• 齊次方程 $Ax=0$ 的唯一解是 $x=0$。

解題方法與選項分析

逐一比對題目敘述與非奇異矩陣的定義及等價條件，並用反例否定不成立的敘述。

(1) 若 $A$ 不可逆，則 $A$ 是非奇異矩陣。

錯誤。 非奇異的定義就是可逆，因此不可逆的矩陣是奇異矩陣。以 $A=0$ 為例，零矩陣不可逆，所以不是非奇異矩陣。

(2) 若存在矩陣 $B$ 使得 $AB=BA=I$。

核心觀念

初等矩陣是對單位矩陣 $I_n$ 施行一次初等列運算後得到的矩陣。初等列運算只有三種：

1. 交換兩列。
2. 將一列乘上非零常數。
3. 將某列的倍數加到另一列。

初等矩陣左乘矩陣 $A$，會對 $A$ 施行對應的列運算。因此，判斷定義時要看它是否來自上述其中一種單次列運算。

解題方法

逐項比對題目描述與三種初等列運算。前三項正好各對應一種列運算；第 (4) 項描述的是欄的重排，不能作為一般的初等矩陣定義。

選項分析

(1) 正確。 將 $I_n$ 的兩列互換，是一次交換兩列的初等列運算，因此所得矩陣是初等矩陣。

核心觀念

本題考查行列式的基本性質：

• 相同的行列式值不代表矩陣相同。
• 行列式對矩陣相加不具線性；對矩陣乘上純量則滿足 $\det(rA)=r^n\det(A)$。
• 轉置不改變行列式，且 $\det(AB)=\det(A)\det(B)$。
• 初等列運算對行列式的影響不同：交換兩列會變號，某列乘上 $c$ 會使行列式乘上 $c$，某列加上另一列的倍數則不改變行列式。

解題方法

逐項檢查是否符合行列式的定理。判斷全稱敘述是否錯誤時，可用簡單矩陣舉反例；若要判斷乘積或轉置，則直接套用行列式的基本公式。

選項分析

(1) 錯誤。 行列式只是一個數值，不能唯一決定矩陣。取

$$A=\begin{pmatrix}1&0\\0&0\end{pmatrix}, \qquad B=\begin{pmatrix}2&0\\0&0\end{pmatrix}.$$

兩者都滿足 $\det(A)=\det(B)=0$，但 $A\ne B$。

核心觀念

令 $A=[a_1\ a_2\ \cdots\ a_n]$，其中 $A$ 是 $n\times n$ 方陣。題目考查方陣的可逆性、齊次方程組 $Ax=0$、秩與零度，以及矩陣轉置的秩。

幾個重要定理如下：

• $a_1,\ldots,a_n$ 線性獨立，若且唯若 $A$ 可逆，也就是 $A$ 非奇異。
• $Ax=0$ 只有平凡解 $x=0$，若且唯若 $A$ 可逆。
• 秩零度定理：$\operatorname{rank}(A)+\operatorname{nullity}(A)=n$。
• 矩陣與其轉置的秩相等：$\operatorname{rank}(A)=\operatorname{rank}(A^T)$。

解題方法

逐項對照上述定理。要特別留意「奇異」代表不可逆；方陣的欄向量線性獨立時，矩陣應是非奇異，而非奇異。另兩項涉及 $Ax=0$ 的解與秩零度定理，可直接由基本線性代數定理判斷。

選項分析

(1) 錯誤。
$n$ 個欄向量線性獨立，若且唯若 $A$ 非奇異。題目將條件寫成「$A$ 是奇異矩陣」，方向相反。

例如，若 $A=I_n$，其欄向量線性獨立，但 $A$ 非奇異；若 $A$ 是零矩陣，欄向量線性相依且 $A$ 奇異。

核心觀念

設

$$A=\begin{pmatrix}a&b\\c&d\end{pmatrix}, \qquad a,b,c,d\in\mathbb R.$$

本題要找出使 $A^2=-I$ 的所有實數矩陣。關鍵是將矩陣平方後逐項比較，並利用實數平方非負的性質排除 $b=c=0$ 的情形。

解題方法

直接計算：

$$A^2= \begin{pmatrix} a^2+bc & b(a+d)\\ c(a+d) & d^2+bc \end{pmatrix}.$$

令 $A^2=-I$，比較矩陣各元素，得到

$$a^2+bc=-1,\qquad b(a+d)=0,\qquad c(a+d)=0,\qquad d^2+bc=-1.$$

若 $b=c=0$，第一式會變成 $a^2=-1$，這與 $a$ 為實數矛盾。因此 $b,c$ 不可能同時為零，故至少一個非零。由 $b(a+d)=0$ 或 $c(a+d)=0$ 可得

$$a+d=0,$$

也就是 $d=-a$。代入第一式，得到

$$a^2+bc=-1 \quad\Longleftrightarrow\quad bc=-(1+a^2).$$

因此所有符合條件的矩陣恰為

核心觀念

本題考行列式的餘因子展開。若沿第 $j$ 欄展開，則

$$\det A=\sum_{i=1}^{n}(-1)^{i+j}a_{ij}\det A_{ij},$$

其中 $A_{ij}$ 是刪除第 $i$ 列與第 $j$ 欄後得到的子矩陣。若某一列或某一欄只有少數非零元素，沿該列或該欄展開能大幅減少計算量。

解題方法

原矩陣的第 $4$ 欄只有 $a_{34}=8$ 非零，因此沿第 $4$ 欄展開。其餘子矩陣的行列式符號為 $(-1)^{3+4}=-1$：

$$\det A =-8 \begin{vmatrix} 1&0&2&0&4\\ 30&1&5&0&9\\ 2&0&8&0&7\\ 7&0&4&6&0\\ 0&0&1&2&0 \end{vmatrix}.$$

這個 $5\times5$ 子矩陣的第 $2$ 欄只有一個非零元素 $1$，位於第 $2$ 列。沿該欄展開，符號為 $(-1)^{2+2}=1$：

$$\det A =-8 \begin{vmatrix} 1&2&0&4\\ 2&8&0&7\\ 7&4&6&0\\ 0&1&2&0 \end{vmatrix}.$$

接著沿 $4\times4$ 矩陣的第 $4$ 欄展開。該欄只有前兩列非零，故

核心觀念

奇異值分解（SVD）將矩陣寫成

$$A=U\Sigma V^{T},$$

其中 $U$、$V$ 的欄向量皆為正交單位向量，$\Sigma$ 的對角線元素為非負奇異值。對本題的 $3\times 2$ 矩陣，可先求 $A^{T}A$ 的特徵值與正交單位特徵向量：

• 特徵值的平方根是奇異值。
• $A^{T}A$ 的正交單位特徵向量組成 $V$。
• 對應的左奇異向量由 $u_i=\dfrac{Av_i}{\sigma_i}$ 求得。

解題方法

先計算

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

其特徵值為 $10$ 與 $8$，對應的正交單位特徵向量分別為

$$v_1=\frac{1}{\sqrt{2}} \begin{bmatrix} 1\\-1 \end{bmatrix}, \qquad v_2=\frac{1}{\sqrt{2}} \begin{bmatrix} 1\\1 \end{bmatrix}.$$

因此奇異值為

$$\sigma_1=\sqrt{10}, \qquad \sigma_2=\sqrt{8}=2\sqrt{2}.$$

依序求左奇異向量：

$$u_1=\frac{Av_1}{\sigma_1} =\frac{1}{\sqrt{5}} \begin{bmatrix} 2\\0\\1 \end{bmatrix}, \qquad u_2=\frac{Av_2}{\sigma_2} = \begin{bmatrix} 0\\1\\0 \end{bmatrix}.$$

將 $u_1,u_2$ 作為 $U$ 的欄向量，並將 $v_1,v_2$ 作為 $V$ 的欄向量，得到一組奇異值分解：

核心觀念

在 $\lVert x\rVert=1$ 的限制下，求 $Ax=0$ 的最小平方解，就是在所有單位向量中，找出使殘差平方 $\lVert Ax\rVert^2$ 最小的 $x$。由於

$$\lVert Ax\rVert^2=x^{\mathsf T}A^{\mathsf T}Ax,$$

此問題等價於求矩陣 $A^{\mathsf T}A$ 的最小特徵值所對應的單位特徵向量，也就是 $A$ 的最小右奇異向量。

解題方法與證明

設 $A^{\mathsf T}A$ 的特徵值為 $\lambda_1,\ldots,\lambda_n$，並依大小排列為

$$0\leq \lambda_1\leq\lambda_2\leq\cdots\leq\lambda_n.$$

因為 $A^{\mathsf T}A$ 是對稱半正定矩陣，存在一組正交標準特徵向量 $v_1,\ldots,v_n$。將任意滿足 $\lVert x\rVert=1$ 的向量展開為

$$x=\sum_{i=1}^{n}c_i v_i, \qquad \sum_{i=1}^{n}c_i^2=1.$$

因此

核心觀念

本題考查命題的分類：若一個命題在所有情況下都為真，稱為重言式；在所有情況下都為假，稱為矛盾式；有時真、有時假，則為兩者皆非。

關鍵是全稱量詞 $\forall b$ 涵蓋所有對象，因此也涵蓋被存在量詞選出的 $a$。

解題方法

假設存在某個 $a$，使得對所有 $b$ 都有

$$b\in a\leftrightarrow b\notin b。$$

令 $b=a$，得到

$$a\in a\leftrightarrow a\notin a。$$

核心觀念

左側是等比級數，首項為 $2^{x-2}$，公比為 $\frac12$。等比級數首項為 $a$、公比為 $q$ 且 $|q|<1$ 時，其和為 $\frac{a}{1-q}$。本題假設級數收斂，因此可使用此公式。

解題方法

將左側級數化簡：

$$\sum_{r=2}^{\infty}2^{x-r} =2^{x-2}+2^{x-3}+2^{x-4}+\cdots =\frac{2^{x-2}}{1-\frac12} =2^{x-1}$$

原式因此成為：

$$2^{x-1}=\sqrt{1+3\cdot 2^{x-2}}$$

核心觀念

「整數部分」是小於或等於該數的最大整數。設

$$S=\sqrt5+\sqrt6+\sqrt7+\sqrt8+\sqrt9+\sqrt{10}+\sqrt{11}+\sqrt{12}+\sqrt{13},$$

只要證明 $26<S<27$，即可確定 $S$ 的整數部分為 $26$。

比較平方根與正有理數時，可利用：若 $a,b>0$，則 $a^2<b^2$ 蘊含 $a<b$。

解題方法

先用容易平方驗算的數給各項建立下界：

$$\begin{aligned} \sqrt5&>\frac{11}{5},& \sqrt6&>\frac{12}{5},& \sqrt7&>\frac52,& \sqrt8&>\frac{14}{5},\\ \sqrt9&=3,& \sqrt{10}&>3,& \sqrt{11}&>\frac{33}{10},& \sqrt{12}&>\frac{17}{5},& \sqrt{13}&>\frac72. \end{aligned}$$

例如，$\left(\frac{11}{5}\right)^2=\frac{121}{25}<5$，因此 $\sqrt5>\frac{11}{5}$；其餘不等式也可由兩邊平方驗證。相加得

核心觀念

把 $n$ 個連續數字 $1$ 組成的數記為 $R_n$，則它是等比級數：

$$R_n=1+10+10^2+\cdots+10^{n-1} =\frac{10^n-1}{9}.$$

本題要判斷 $R_{243}$ 是否能被 $243=3^5$ 整除。只知道它能被 $9$ 整除還不夠，必須再檢查因數 $3$ 的次方是否達到 $5$。

解題方法

利用 $10=1+9$，將 $R_{243}$ 改寫並套用二項式定理：

$$R_{243} =\frac{(1+9)^{243}-1}{9} =\sum_{j=1}^{243}\binom{243}{j}9^{j-1}.$$

逐項檢查：

• $j=1$ 時，該項為 $\binom{243}{1}=243$，可被 $243$ 整除。
• $j=2$ 時，該項為 $$\binom{243}{2}9=\frac{243\cdot242}{2}\cdot9,$$ 含有因數 $243$，因此可被 $243$ 整除。
• $j=3$ 時，該項為 $81\binom{243}{3}$。其中

核心觀念

利用嚴格遞增性與函數方程 $f(f(x))=2x+1$，先判斷 $f(x)$ 必定大於 $x$，再逐步求出所需的函數值。

以下依台灣考試常用約定，令 $\mathbb{N}=\{1,2,3,\ldots\}$。

解題方法

先證明對任意正整數 $x$，都有 $f(x)>x$。若 $f(x)\le x$，由 $f$ 嚴格遞增可得 $f(f(x))\le f(x)\le x$，但題目給出 $f(f(x))=2x+1>x$，矛盾。因此 $f(x)>x$。

依序代入：

• $x=1$ 時，$f(f(1))=3$。由 $f(1)>1$，且 $f(f(1))>f(1)$，得 $1<f(1)<3$，所以 $f(1)=2$，進而 $f(2)=3$。
• $x=2$ 時，$f(f(2))=5$。因為 $f(2)=3$，所以 $f(3)=5$。

核心觀念

本題先把三個數列相加，利用遞迴式建立總和 $u_n$ 的關係；再運用 $u_n$ 的結果消去 $x_{n-1}$ 和 $z_{n-1}$，得到 $y_n$ 的遞迴式，最後解出 $y_n$ 的閉合公式。

(a) 用數學歸納法證明 $u_n=2^n$

由定義，

$$\begin{aligned} u_n &=x_n+y_n+z_n\\ &=(x_{n-1}+y_{n-1}+z_{n-1}) +(x_{n-1}+z_{n-1})+y_{n-1}\\ &=2(x_{n-1}+y_{n-1}+z_{n-1})\\ &=2u_{n-1}. \end{aligned}$$

基底： 當 $n=0$ 時，

$$u_0=x_0+y_0+z_0=1+0+0=1=2^0.$$

歸納步驟： 假設對某個 $n\geq 1$，$u_{n-1}=2^{n-1}$。由 $u_n=2u_{n-1}$，

$$u_n=2\cdot 2^{n-1}=2^n.$$

因此依數學歸納法，對所有 $n\geq 0$，皆有 $u_n=2^n$。

(b) 推導 $y_n$ 的遞迴式

由題目給定的 $y_n$ 遞迴式，

$$y_n=x_{n-1}+z_{n-1}.$$

而

$$u_{n-1}=x_{n-1}+y_{n-1}+z_{n-1}=2^{n-1}.$$

因此

$$x_{n-1}+z_{n-1}=u_{n-1}-y_{n-1},$$

代回可得

$$\boxed{y_n=2^{n-1}-y_{n-1}},\qquad n\geq 1.$$

核心觀念

關係 $R\cap S$ 的定義是：$x(R\cap S)y$ 當且僅當 $xRy$ 且 $xSy$。本題要檢查它是否同時具備自反性、對稱性、遞移性。

由題意，

$$x(R\cap S)y \iff 7\mid(x-y)\ \text{且}\ 13\mid(x-y).$$

因為 $7$ 與 $13$ 互質，這等價於 $91\mid(x-y)$，也就是 $x\equiv y\pmod{91}$。

解題方法與證明

直接依等價關係的三項定義驗證：

• **自反性：**任取 $x\in\mathbb N$，有 $x-x=0$，而 $7$ 和 $13$ 都整除 $0$。因此 $xRx$ 且 $xSx$，故 $x(R\cap S)x$。
• **對稱性：**若 $x(R\cap S)y$，則 $7\mid(x-y)$ 且 $13\mid(x-y)$。

核心觀念

等價關係必須同時具備自反性、對稱性、遞移性。此題的關係 $R\cup S$ 表示：$x$ 與 $y$ 至少符合以下一項，即 $x\equiv y\pmod 7$ 或 $x\equiv y\pmod{13}$。

解題方法

先檢查三項性質。對任意 $x\in\mathbb N$，有 $x\equiv x\pmod 7$，所以 $(x,x)\in R\subseteq R\cup S$，故 $R\cup S$ 具有自反性。

若 $(x,y)\in R\cup S$，則 $x\equiv y\pmod 7$ 或 $x\equiv y\pmod{13}$。同餘關係具有對稱性，因此 $y\equiv x$ 也成立於相同模數，故 $(y,x)\in R\cup S$。所以 $R\cup S$ 具有對稱性。

核心觀念

令 $F$ 表示剩餘頂點之間的失效連線。若剩下 $m$ 個頂點，題目條件會化為：$F$ 至多有 $m-3$ 條邊。以下證明只要從 $K_m$ 刪除至多 $m-3$ 條邊，剩餘圖便有 Hamiltonian cycle。

歸納時，選一個在 $F$ 中至少有一條、但失效邊數不超過一半的頂點 $v$。刪除 $v$ 後可套用歸納假設；再把 $v$ 插入較小圖的 Hamiltonian cycle。

引理

若 $m\ge5$，且簡單圖 $F$ 至多有 $m-3$ 條邊，則 $F$ 有一個非孤立頂點 $v$，使得

$$1\le d_F(v)\le \left\lfloor\frac{m-2}{2}\right\rfloor.$$

**證明引理：**取 $F$ 中一個含邊的連通分量，令其最小度數為 $\delta$。此分量至少有 $\delta+1$ 個頂點，因此邊數至少為

$$\frac{\delta(\delta+1)}{2}.$$

若 $\delta>\lfloor(m-2)/2\rfloor$，則 $\delta\ge\lfloor(m-2)/2\rfloor+1$，這會使該分量的邊數大於 $m-3$，與 $|E(F)|\le m-3$ 矛盾。因此該分量中存在度數介於 $1$ 與 $\lfloor(m-2)/2\rfloor$ 之間的頂點。引理得證。

解題方法：對頂點數歸納

設 $G=K_m-F$，且 $|E(F)|\le m-3$。

基礎情形

• $m=3$ 時，$|E(F)|\le0$，故 $G=K_3$，有 Hamiltonian cycle。
• $m=4$ 時，$|E(F)|\le1$。若有一條失效邊 $ab$，令其餘兩點為 $c,d$，則 $a-c-b-d-a$ 是 Hamiltonian cycle；