112 年 國立中正大學資訊工程學系碩士班乙組《數學》

核心觀念

$A$ 是 $3\times 4$ 矩陣，零空間維度（nullity）由秩–零度定理決定：

$$\operatorname{rank}(A)+\operatorname{nullity}(A)=4\ (\text{行數，即未知數個數}).$$

而 $A\mathbf{x}=\mathbf{b}$ 是否對所有 $\mathbf{b}\in\mathbb{R}^3$ 都有解，取決於 $\operatorname{rank}(A)$ 是否等於 $3$（列數）。

解題方法

先做列運算求秩：

$$\begin{bmatrix} 1 & 4 & 0 & 1 \\ 1 & 4 & -3 & -3 \\ 0 & 0 & 3 & 4 \end{bmatrix} \xrightarrow{R_2-R_1} \begin{bmatrix} 1 & 4 & 0 & 1 \\ 0 & 0 & -3 & -4 \\ 0 & 0 & 3 & 4 \end{bmatrix} \xrightarrow{R_3+R_2} \begin{bmatrix} 1 & 4 & 0 & 1 \\ 0 & 0 & -3 & -4 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

只剩兩個非零列，所以 $\operatorname{rank}(A)=2$，

本題考查向量空間的子空間判別。一個非空子集 $W$ 若是向量空間 $V$ 的子空間，則必須滿足以下三個條件：

1. 零向量屬於 $W$。
2. 對於 $W$ 中的任意向量 $u, v$，其和 $u+v$ 也屬於 $W$（加法封閉性）。
3. 對於 $W$ 中的任意向量 $u$ 和任意純量 $c$，其純量積 $cu$ 也屬於 $W$（純量乘法封閉性）。

令 $V$ 為所有 $2 \times 2$ 實數矩陣的集合，這是一個向量空間。我們逐一檢驗選項。

(1) 所有 $2 \times 2$ 反對稱矩陣，即 $A^T = -A$。
令 $W_1 = \{A \in M_{2\times2}(\mathbb{R}) \mid A^T = -A\}$。

• 零向量：零矩陣 $\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}$ 滿足 $\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}^T = \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} = -\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}$。所以零向量屬於 $W_1$。
• 加法封閉性：設 $A, B \in W_1$。則 $A^T = -A$ 且 $B^T = -B$。
  $(A+B)^T = A^T + B^T = (-A) + (-B) = -(A+B)$。
  所以 $A+B \in W_1$。
• 純量乘法封閉性：設 $A \in W_1$ 且 $c$ 為實數。則 $A^T = -A$。
  $(cA)^T = cA^T = c(-A) = -(cA)$。
  所以 $cA \in W_1$。
  因此，$W_1$ 是 $V$ 的一個子空間。

(2) 所有 $2 \times 2$ 可逆矩陣。
令 $W_2 = \{A \in M_{2\times2}(\mathbb{R}) \mid \det(A) \neq 0\}$。

• 零向量：零矩陣 $\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}$ 的行列式為 0，所以它不是可逆矩陣，不屬於 $W_2$。
  因此，$W_2$ 不是子空間。

(3) 所有 $2 \times 2$ singular matrices（不可逆矩陣）。
令 $W_3 = \{A \in M_{2\times2}(\mathbb{R}) \mid \det(A) = 0\}$。

• 零向量：零矩陣是 singular matrix，屬於 $W_3$。

本題考查可逆矩陣的性質。一個 $n \times n$ 矩陣 $A$ 是可逆的（invertible）等價於以下性質：

• $\det(A) \neq 0$。
• $Ax=0$ 只有零向量解。
• $Ax=b$ 對於任意 $b \in \mathbb{R}^n$ 都有唯一解。
• $A$ 的列向量（或行向量）線性獨立。
• $A$ 的秩為 $n$。
• $A$ 可以表示為若干個基本矩陣（elementary matrices）的乘積。
• $A^T$ 也是可逆的。
• $A^{-1}$ 存在。

現在我們逐一檢驗選項：

(1) $A = E_1E_2 \cdots E_k$ where each $E_i$ is a $4 \times 4$ elementary matrix.
根據基本矩陣定理（Elementary Matrix Theorem），一個 $n \times n$ 矩陣 $A$ 是可逆的，當且僅當它可以表示為基本矩陣的乘積。這個敘述是正確的。

(2) $\det(A) = 0$.
如果矩陣 $A$ 是可逆的，那麼它的行列式 $\det(A)$ 必定不等於 0。因此，這個敘述是錯誤的。

本題考查矩陣的特徵值（eigenvalues）與相關性質，包含可逆性、對角化性、跡（trace）和行列式（determinant）。

給定一個 $3 \times 3$ 矩陣 $A$ 的特徵值為 $\lambda_1 = -1$, $\lambda_2 = 2$, $\lambda_3 = 4$。

我們逐一分析選項：

(1) A is invertible.
一個矩陣是可逆的（invertible），當且僅當它的所有特徵值都不為零。
在此例中，特徵值為 $-1, 2, 4$，它們都非零。因此，$A$ 是可逆的。此敘述正確。

(2) A is diagonalizable.
一個 $n \times n$ 矩陣 $A$ 如果有 $n$ 個不同的特徵值，則它一定是可對角化的（diagonalizable）。

核心觀念

所有 $2\times 2$ 對稱矩陣都能寫成

$$\begin{bmatrix} a & b \\ b & c \end{bmatrix} = a\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} + b\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} + c\begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix},$$

所以這個空間的維度是 $3$。把每個對稱矩陣對應到座標向量 $(a,b,c)$，三個矩陣構成基底 $\iff$ 三個座標向量線性獨立 $\iff$ 以它們為列的 $3\times 3$ 行列式不為 $0$。

選項分析

(1) 座標為 $(1,0,0),(0,1,0),(0,0,1)$，就是標準基底，行列式 $=1\neq 0$，是基底。

(2) 座標為 $(3,3,3),(0,1,0),(1,1,0)$：

$$\det\begin{bmatrix} 3 & 3 & 3 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{bmatrix} =3(0-0)-3(0-0)+3(0-1)=-3\neq 0,$$

是基底。

本題考查矩陣的秩（rank）、零度（nullity）以及列空間（column space）的維度。

給定一個 $4 \times 7$ 的矩陣 $A$。

• 秩（rank）的定義是矩陣的列空間（或行空間）的維度。
• 零度（nullity）的定義是矩陣的零空間（null space）的維度。
• 秩-零度定理（Rank-Nullity Theorem）指出：對於一個 $m \times n$ 的矩陣 $A$，$\text{rank}(A) + \text{nullity}(A) = n$（$n$ 是矩陣的列數）。
• 矩陣的秩有上限：$\text{rank}(A) \le \min(m, n)$。

對於一個 $4 \times 7$ 的矩陣 $A$：

• $m=4$, $n=7$。
• $\text{rank}(A) \le \min(4, 7) = 4$。
• $\text{rank}(A) + \text{nullity}(A) = 7$。

現在我們逐一分析選項：

(1) The maximum possible value of rank(A) is 4.

核心觀念

下三角矩陣 $L=(\ell_{ij})$ 的定義為：

$$\ell_{ij}=0\quad\text{當 }i<j，$$

也就是主對角線右上方的元素全部為 $0$。

本題考查下三角矩陣的基本性質：

• 下三角矩陣的行列式等於對角線元素乘積。
• 下三角矩陣的乘積仍為下三角矩陣。
• 可逆下三角矩陣的逆矩陣仍為下三角矩陣。
• 下三角矩陣轉置後成為上三角矩陣。

---

解題方法

逐一檢查四個敘述是否符合三角矩陣的定義與性質。其中第 $(1)$ 項可利用一個可逆下三角矩陣的反例判斷。

---

選項分析

(1) If $L$ is invertible, then $L^{-1}$ is an upper triangular matrix.

此敘述錯誤。

若 $L$ 是可逆的下三角矩陣，則 $L^{-1}$ 仍然是下三角矩陣，而不是一般所稱的上三角矩陣。

例如：

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

其逆矩陣為：

$$L^{-1} = \begin{bmatrix} 1&0\\ -2&1 \end{bmatrix},$$

仍是下三角矩陣，並非上三角矩陣。

一般而言，$L^{-1}$ 可由方程式

$$LX=I$$

逐欄解出。由於 $L$ 的右上方為零，解出的 $X$ 也會具有右上方為零的結構，因此 $X=L^{-1}$ 仍為下三角矩陣。

---

(2) $\det(L)$ is the product of diagonal elements in $L$.

此敘述正確。

下三角矩陣的行列式等於主對角線元素的乘積：

$$\det(L)=\ell_{11}\ell_{22}\cdots \ell_{nn}.$$

例如：

$$L= \begin{bmatrix} a&0&0\\ b&c&0\\ d&e&f \end{bmatrix},$$

則

$$\det(L)=acf.$$

這是三角矩陣行列式的基本性質。

---

核心觀念

若 $A\mathbf{v}=\lambda\mathbf{v}$（$\mathbf{v}\neq\mathbf{0}$），則同一個特徵向量 $\mathbf{v}$ 也是下列矩陣的特徵向量：

• $A^{-1}\mathbf{v}=\dfrac{1}{\lambda}\mathbf{v}$（需 $\lambda\neq 0$）
• $A^{k}\mathbf{v}=\lambda^{k}\mathbf{v}$
• $(A+cI)\mathbf{v}=(\lambda+c)\mathbf{v}$

另外 $A^T$ 與 $A$ 有相同的特徵多項式，因為

本題考查函數空間上的內積（inner product）和正交性（orthogonality）。
兩個函數 $f$ 和 $g$ 在給定的內積下是正交的，若且唯若 $\langle f,g \rangle = 0$。
內積定義為 $\langle f,g \rangle = \int_{-1}^{1} f(x)g(x)dx$。

我們逐一檢驗選項：

(1) $1, e^x$ is orthogonal.
計算 $\langle 1, e^x \rangle = \int_{-1}^{1} 1 \cdot e^x dx = [e^x]_{-1}^{1} = e^1 - e^{-1} = e - \frac{1}{e} \neq 0$。
所以 $1$ 和 $e^x$ 不正交。

(2) $1, x^2$ is orthogonal.

本題考查最小平方解（least squares solution）的性質。對於一個線性方程組 $Ax=b$，如果它沒有精確解，我們尋找一個向量 $\hat{x}$ 使得 $\|Ax - b\|$ 最小，這個 $\hat{x}$ 就是最小平方解。

最小平方解滿足正規方程（normal equations）：$A^T A \hat{x} = A^T b$。

我們逐一檢驗選項：

(1) If b is in column space of A, then the least square solution to $Ax = b$ is also a solution to $Ax = b$.
如果 $b$ 在 $A$ 的列空間中，則表示方程組 $Ax=b$ 有精確解。
此時，最小平方問題 $\|Ax - b\|$ 的最小值是 0，由精確解 $\hat{x}$ 達成，即 $A\hat{x} = b$。
因此，最小平方解就是方程組的精確解。此敘述正確。

(2) The normal system $A^T Ax = A^T b$ is always consistent.
正規方程 $A^T A \hat{x} = A^T b$ 總是存在解。
這是因為 $A^T A$ 是一個半正定（positive semi-definite）矩陣。

譜分解 (Spectral Decomposition)

譜分解是將一個矩陣分解為其特徵值（eigenvalues）和特徵向量（eigenvectors）的組合。它主要適用於可對角化矩陣（diagonalizable matrices），特別是正規矩陣（normal matrices）或對稱矩陣（symmetric matrices）。

核心概念：

1. 矩陣性質 (Matrix Property): 譜分解揭示了矩陣的內在結構，即矩陣如何變換向量。它將這種變換分解為沿著特徵向量方向的伸縮（由特徵值決定）和投影。

2. 特徵值 (Eigenvalues): 特徵值是描述矩陣對應線性變換在特定方向上的伸縮因子。對於一個 $n \times n$ 矩陣 $A$，它有 $n$ 個特徵值（可能重複）。

3. 特徵向量 (Eigenvectors): 特徵向量是線性變換下方向不變的非零向量。當矩陣作用於其特徵向量時，結果只是該特徵向量的純量倍數，這個純量就是對應的特徵值。

4. 對角化 (Diagonalization): 一個矩陣 $A$ 是可對角化的，如果存在一個可逆矩陣 $P$ 和一個對角矩陣 $D$，使得 $A = PDP^{-1}$。這裡，$D$ 的對角線元素是 $A$ 的特徵值，而 $P$ 的列是 $A$ 對應的特徵向量。

   • 對於一個具有 $n$ 個線性獨立特徵向量的 $n \times n$ 矩陣 $A$，我們可以寫成 $A = P D P^{-1}$。
   • $P = [\mathbf{v}_1 \ \mathbf{v}_2 \ \cdots \ \mathbf{v}_n]$，其中 $\mathbf{v}_i$ 是對應於特徵值 $\lambda_i$ 的特徵向量。
   • $D = \text{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$。

譜分解的定義和形式：

奇異值分解 (Singular Value Decomposition, SVD)

奇異值分解（SVD）是一種將任意矩陣（不論是否為方陣，是否可逆）分解為三個特定矩陣乘積的強大工具。它與譜分解（Spectral Decomposition）有相似之處，但更具普遍性。

核心概念：

1. 矩陣性質 (Matrix Property): SVD 揭示了矩陣的內在幾何結構。對於任意一個 $m \times n$ 的實數矩陣 $A$，SVD 將矩陣 $A$ 的作用分解為三個基本操作：一個旋轉（或反射）、一個尺度變換（沿著正交軸）和另一個旋轉（或反射）。

2. 奇異值 (Singular Values): 奇異值是矩陣 $A$ 的奇異值分解中的尺度因子。它們是實數，非負，且通常按降序排列。對於一個 $m \times n$ 的矩陣 $A$，最多有 $\min(m, n)$ 個非零奇異值。奇異值是矩陣 $A^T A$（或 $AA^T$）的特徵值的平方根。

3. 對角化 (Diagonalization): 雖然 SVD 本身不是直接的矩陣對角化（因為 $A$ 不一定是方陣），但它與對角化緊密相關。SVD 的核心是將矩陣 $A$ 的作用分解到一組互相正交的向量基底上。具體來說，矩陣 $A^T A$ 和 $AA^T$ 是對稱的（或埃爾米特矩陣），因此它們都可以被對角化，並且其特徵向量可以構成標準正交基。

4. 標準正交矩陣 (Orthonormal Matrices): SVD 的分解涉及到兩個標準正交矩陣 $U$ 和 $V$。標準正交矩陣的列向量構成一個標準正交基，並且其逆等於其轉置（對於實數矩陣，$U^T = U^{-1}$ 且 $V^T = V^{-1}$）。

奇異值分解的定義和形式：

對於任意一個 $m \times n$ 的實數矩陣 $A$，其奇異值分解可以表示為：
$A = U \Sigma V^T$
其中：

• $U$ 是一個 $m \times m$ 的標準正交矩陣。 $U$ 的列向量被稱為 $A$ 的左奇異向量（left singular vectors）。
• $\Sigma$ 是一個 $m \times n$ 的對角矩陣。其對角線上的元素 $\sigma_1, \sigma_2, \ldots, \sigma_r$ 是 $A$ 的奇異值（singular values），其中 $r = \text{rank}(A)$。這些奇異值是非負的，通常按降序排列 ($\sigma_1 \ge \sigma_2 \ge \ldots \ge \sigma_r > 0$)。矩陣 $\Sigma$ 的其他元素均為零。

本題要求給出矩陣 $A$ 的行空間（row space）的一個標準正交基（orthonormal basis）。

首先，我們需要理解行空間的定義。矩陣的行空間是由其行向量張成的向量空間。通過高斯消去法將矩陣化為行階梯形（row echelon form）或行簡約階梯形（row-reduced echelon form, RREF），並不改變其行空間。然而，行階梯形矩陣的非零行向量是行空間的一個基底，但它們通常不是標準正交基。

題目給出了矩陣 $A$ 的行簡約階梯形 $R$。
$A = \begin{bmatrix} 1 & 2 & 1 & -7 \\ 2 & 4 & 1 & -5 \\ 1 & 2 & 2 & -16 \end{bmatrix}$
$R = \begin{bmatrix} 1 & 2 & 0 & 2 \\ 0 & 0 & 1 & 9 \\ 0 & 0 & 0 & 0 \end{bmatrix}$

$R$ 的非零行向量是 $\mathbf{r}_1 = [1, 2, 0, 2]$ 和 $\mathbf{r}_2 = [0, 0, 1, 9]$。
這兩個向量是行空間的一個基底。它們是線性獨立的，並且張成了行空間。
但是，這組基底不是標準正交基，因為向量的模長（norm）不為 1，且它們之間不一定正交（在本例中，它們是正交的，因為 $\mathbf{r}_1 \cdot \mathbf{r}_2 = 1(0) + 2(0) + 0(1) + 2(9) = 18 \neq 0$。實際上，它們不是正交的）。

重要概念：
高斯消去法（行化簡）會改變行向量，但不會改變行空間。也就是說，原始矩陣 $A$ 的行空間與其行階梯形矩陣 $R$ 的行空間是相同的。
因此，$R$ 的非零行向量構成了 $A$ 的行空間的一個基底。

問題點：
題目要求的是「標準正交基」。
然而，行空間的基底是通過對原始矩陣 $A$ 的行向量進行線性組合得到的，或者直接由 $R$ 的非零行向量構成。
一個常見的誤解是，認為 $R$ 的非零行向量就是 $A$ 的行空間的基底，並且直接對它們進行 Gram-Schmidt 正交化。
事實上，行空間的基底應該是原始矩陣 $A$ 的某幾個行向量的線性組合。

更正與澄清：
行空間是由矩陣的行向量張成的空間。
高斯消去法對行進行的操作（例如 $R_i \leftarrow R_i + c R_j$）會改變行向量本身，但不會改變由這些行向量張成的空間。
因此，$R$ 的非零行向量 $\mathbf{r}_1 = [1, 2, 0, 2]$ 和 $\mathbf{r}_2 = [0, 0, 1, 9]$ 是行空間的一個基底。
然而，它們不一定是 $A$ 的行空間的基底（因為行操作改變了向量）。
正確的說法是：$R$ 的非零行向量構成了 $R$ 的行空間的基底，而 $R$ 的行空間等於 $A$ 的行空間。

尋找標準正交基：
我們可以使用 Gram-Schmidt 正交化過程來將基底 $\{\mathbf{r}_1, \mathbf{r}_2\}$ 轉換為標準正交基。
令 $u_1 = \mathbf{r}_1 = [1, 2, 0, 2]$。
令 $u_2 = \mathbf{r}_2 = [0, 0, 1, 9]$。

Gram-Schmidt 過程：

1. 第一個向量：
   $v_1 = u_1 = [1, 2, 0, 2]$。
   計算其模長：$\|v_1\| = \sqrt{1^2 + 2^2 + 0^2 + 2^2} = \sqrt{1 + 4 + 0 + 4} = \sqrt{9} = 3$。
   標準化向量：$e_1 = \frac{v_1}{\|v_1\|} = \frac{1}{3}[1, 2, 0, 2] = [\frac{1}{3}, \frac{2}{3}, 0, \frac{2}{3}]$。

2. 第二個向量：
   首先，計算 $u_2$ 在 $v_1$ 上的投影：
   $\text{proj}_{v_1} u_2 = \frac{\langle u_2, v_1 \rangle}{\|v_1\|^2} v_1 = \frac{\langle [0, 0, 1, 9], [1, 2, 0, 2] \rangle}{3^2} [1, 2, 0, 2]$
   $\langle u_2, v_1 \rangle = 0(1) + 0(2) + 1(0) + 9(2) = 18$。

題意說明

原卷寫「$T(\mathbf{v}_1)=(1,-2)^T$ and $T(\mathbf{v}_1)=(-4,1)^T$」，同一個向量不可能對應兩個不同的像，第二個顯然是 $T(\mathbf{v}_2)$ 的筆誤。以下以

$$T(\mathbf{v}_1)=\begin{bmatrix}1\\-2\end{bmatrix},\qquad T(\mathbf{v}_2)=\begin{bmatrix}-4\\1\end{bmatrix}$$

作答。

核心觀念

線性變換由它在一組基底上的像完全決定：把任意向量寫成基底的線性組合，再利用線性性質

$$T(c_1\mathbf{v}_1+c_2\mathbf{v}_2)=c_1T(\mathbf{v}_1)+c_2T(\mathbf{v}_2).$$

(a) 計算 $T(5,-3)$

先把 $(5,-3)$ 用 $\mathbf{v}_1=(1,1)$、$\mathbf{v}_2=(1,0)$ 表示：

核心觀念

先把命題化簡：

$$Q(x,y):\ x+y=x-y \iff 2y=0 \iff y=0 .$$

所以 $Q(x,y)$ 為真只看 $y$ 是不是 $0$，與 $x$ 無關。接下來每一題都只要問「$y$ 能不能（或是否一定）等於 $0$」。

逐題判斷（論域：所有整數）

小題	敘述	判斷理由	真假
(a)	$Q(1,1)$	$y=1\neq 0$	F
(b)	$Q(2,0)$	$y=0$	T
(c)	$\forall y\,Q(1,y)$	取 $y=1$ 即為反例	F
(d)	$\exists x\,Q(x,2)$	$y=2$ 固定不為 $0$，不論 $x$ 取什麼都不成立	F
(e)	$\exists x\exists y\,Q(x,y)$	取 $x=0,\ y=0$	T

核心觀念

鴿籠原理：先把 $1$ 到 $12$ 依「和為 $13$」配對，再找出「最多能選幾個數而仍未湊滿三對」，答案就是那個數再加一。

解題方法

和為 $13$ 的配對恰好把 $1\sim12$ 分成 $6$ 組（每個數只出現在一組）：

$$\{1,12\},\ \{2,11\},\ \{3,10\},\ \{4,9\},\ \{5,8\},\ \{6,7\}.$$

要讓選出的數「最多只有兩對」，最大的選法是：

核心觀念

令 $a_n$ 為長度 $n$、含有連續兩個 $0$（"00"）的二元字串個數。依照字串開頭的寫法分類，每一類都會化成較短的同類問題。

(a) 遞迴關係

依第一、二個字元分成三類：

1. 以 $1$ 開頭：剩下的 $n-1$ 位必須自己含有 "00"，共 $a_{n-1}$ 種。
2. 以 $01$ 開頭：開頭的 $0$ 後面接 $1$，無法和後面組成 "00"，剩下 $n-2$ 位必須自己含有 "00"，共 $a_{n-2}$ 種。
3. 以 $00$ 開頭：已經含有 "00"，剩下 $n-2$ 位任意，共 $2^{n-2}$ 種。

三類互斥且涵蓋所有情形，所以

$$a_n=a_{n-1}+a_{n-2}+2^{n-2},\qquad n\ge 2 .$$

(b) 初始條件

長度 $0$、$1$ 的字串不可能含有 "00"：

$$a_0=0,\qquad a_1=0 .$$

（若從 $n\ge 3$ 開始用遞迴，也可寫成 $a_1=0,\ a_2=1$；兩種寫法一致，因為 $a_2=0+0+2^0=1$，就是 "00" 本身。）

核心觀念

三小題都用同兩個工具：

• 握手定理：所有頂點的度數總和等於邊數的兩倍，$\sum \deg(v)=2|E|$。
• 補圖：$G$ 與 $\overline{G}$ 的邊合起來恰好是 $n$ 個頂點的完全圖 $K_n$，所以

$$|E(G)|+|E(\overline{G})|=\binom{n}{2}=\frac{n(n-1)}{2}.$$

(a)

$6$-正則圖的每個頂點度數都是 $6$，設有 $n$ 個頂點：