109 年 國立中正大學通訊工程學系碩士班通訊乙組《線性代數與資料結構》

核心觀念

本題考查以下線性代數概念：

1. Gaussian–Jordan elimination：將矩陣化為 reduced row echelon form（RREF）。
2. Column space 的基底：原矩陣中對應於 RREF 主元欄的欄向量，構成 $\operatorname{Col}(A)$ 的一組基底。
3. Row space 的線性組合：向量若能表示成 $A$ 的列向量線性組合，必須屬於 $\operatorname{Row}(A)$。
4. 座標向量：若 $C$ 是 $\operatorname{Col}(A)$ 的基底，則 $(v)_C$ 僅在 $v\in\operatorname{Col}(A)$ 時有定義。

---

解題方法

（a）求 $A$ 的 reduced row echelon form

原矩陣為

$$A= \begin{bmatrix} 1&2&3&4\\ 4&3&2&1\\ 1&3&5&3\\ 7&5&3&1 \end{bmatrix}.$$

先以第一列消去第一欄：

$$R_2\leftarrow R_2-4R_1,\qquad R_3\leftarrow R_3-R_1,\qquad R_4\leftarrow R_4-7R_1.$$

得到

$$\begin{bmatrix} 1&2&3&4\\ 0&-5&-10&-15\\ 0&1&2&-1\\ 0&-9&-18&-27 \end{bmatrix}.$$

交換第二列與第三列：

$$R_2\leftrightarrow R_3,$$

並以第二列消去第二欄：

$$\begin{bmatrix} 1&2&3&4\\ 0&1&2&-1\\ 0&-5&-10&-15\\ 0&-9&-18&-27 \end{bmatrix} \longrightarrow \begin{bmatrix} 1&2&3&4\\ 0&1&2&-1\\ 0&0&0&-20\\ 0&0&0&-36 \end{bmatrix}.$$

將第三列除以 $-20$：

$$R_3\leftarrow-\frac{1}{20}R_3,$$

再消去第四欄：

$$\begin{bmatrix} 1&2&3&4\\ 0&1&2&-1\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}.$$

最後消去第一列與第二列的第二欄、第四欄：

$$R_1\leftarrow R_1-4R_3,\qquad R_2\leftarrow R_2+R_3,\qquad R_1\leftarrow R_1-2R_2.$$

因此

$$\operatorname{rref}(A)= \begin{bmatrix} 1&0&-1&0\\ 0&1&2&0\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}.$$

主元欄為第 $1、2、4$ 欄，故

$$\operatorname{rank}(A)=3.$$

---

（b）求 column space 的基底 $C$

基底必須取自原矩陣 $A$ 的主元欄，不能直接取 RREF 的欄向量。

原矩陣的第 $1、2、4$ 欄分別為

$$\mathbf a_1= \begin{bmatrix} 1\\4\\1\\7 \end{bmatrix}, \qquad \mathbf a_2= \begin{bmatrix} 2\\3\\3\\5 \end{bmatrix}, \qquad \mathbf a_4= \begin{bmatrix} 4\\1\\3\\1 \end{bmatrix}.$$

所以

$$C= \left\{ \begin{bmatrix} 1\\4\\1\\7 \end{bmatrix}, \begin{bmatrix} 2\\3\\3\\5 \end{bmatrix}, \begin{bmatrix} 4\\1\\3\\1 \end{bmatrix} \right\}.$$

因此

核心觀念

本題考查：

• 齊次線性方程組 $B\mathbf{x}=\mathbf{0}$ 的解集合，即矩陣 $B$ 的零空間。
• 零空間的維度，也就是 nullity。
• 特徵值與特徵向量的定義：

$$B\mathbf{x}=\lambda\mathbf{x}$$

等價於

$$(B-\lambda I)\mathbf{x}=\mathbf{0}$$

因此特徵值必須滿足：

$$\det(B-\lambda I)=0$$

---

a. 零空間與其維度

令

$$\mathbf{x}= \begin{bmatrix} x\\y\\z \end{bmatrix}$$

要求 $B\mathbf{x}=\mathbf{0}$：

$$\begin{bmatrix} 1&0&3\\ 0&5&0\\ 7&0&9 \end{bmatrix} \begin{bmatrix} x\\y\\z \end{bmatrix} = \begin{bmatrix} 0\\0\\0 \end{bmatrix}$$

得到方程組：

$$\begin{cases} x+3z=0,\\ 5y=0,\\ 7x+9z=0. \end{cases}$$

由第二式可得：

$$y=0$$

由第一式可得：

$$x=-3z$$

代入第三式：

$$7(-3z)+9z=0$$ $$-21z+9z=0$$ $$-12z=0$$

因此：

$$z=0,\qquad x=0,\qquad y=0$$

所以只有零向量：

$$N(B)=\left\{ \begin{bmatrix} 0\\0\\0 \end{bmatrix} \right\}$$

因此零空間為平凡零空間，其維度為：

$$\dim N(B)=0$$

也可由行列式判斷：

$$\det(B) =5 \begin{vmatrix} 1&3\\ 7&9 \end{vmatrix} =5(9-21) =-60\neq 0$$

故 $B$ 可逆，nullity 為 $0$。

---

b. 特徵值與特徵向量

求特徵值

計算特徵方程：

$$\det(B-\lambda I)=0$$

其中

$$B-\lambda I= \begin{bmatrix} 1-\lambda&0&3\\ 0&5-\lambda&0\\ 7&0&9-\lambda \end{bmatrix}$$

沿著第二列或第二行展開：

$$\det(B-\lambda I) =(5-\lambda) \begin{vmatrix} 1-\lambda&3\\ 7&9-\lambda \end{vmatrix}$$

因此：

$$\det(B-\lambda I) =(5-\lambda)\left[(1-\lambda)(9-\lambda)-21\right]$$

展開括號內的部分：

$$(1-\lambda)(9-\lambda)-21 =9-10\lambda+\lambda^2-21$$ $$=\lambda^2-10\lambda-12$$

所以特徵方程為：

$$(5-\lambda)(\lambda^2-10\lambda-12)=0$$

先由第一因子得到：

$$\lambda_1=5$$

再解二次方程：

$$\lambda^2-10\lambda-12=0$$ $$\lambda=\frac{10\pm\sqrt{100+48}}{2}$$ $$=\frac{10\pm\sqrt{148}}{2} =5\pm\sqrt{37}$$

故三個特徵值為：

$$\boxed{\lambda=5,\quad 5+\sqrt{37},\quad 5-\sqrt{37}}$$

---

求 $\lambda=5$ 的特徵向量

代入 $(B-5I)\mathbf{x}=\mathbf{0}$：

$$B-5I= \begin{bmatrix} -4&0&3\\ 0&0&0\\ 7&0&4 \end{bmatrix}$$

因此：

核心觀念

二元搜尋樹（BST）的每個節點都必須符合：

• 左子樹的所有鍵值都小於該節點的鍵值。
• 右子樹的所有鍵值都大於該節點的鍵值。
• 左、右子樹本身也都必須是 BST。

判斷時要檢查整個子樹的值域限制，不能只比較父節點與直接子節點。

解題方法

(a) 判斷 Fig. 1 是否為 BST

圖中的根節點為 $18$。左子樹的節點為 $12、8、14$，都小於 $18$；右子樹的節點為 $20、19、24$，都大於 $18$。

以 $12$ 為根的左子樹中，$8 < 12 < 14$；以 $20$ 為根的右子樹中，$19 < 20 < 24$。各節點都符合 BST 的大小限制，因此 Fig. 1 是 BST。

也可用中序走訪快速驗證。BST 的中序走訪結果應為遞增序列；此圖的結果為：

$$8,\ 12,\ 14,\ 18,\ 19,\ 20,\ 24$$

(b) BST 節點結構

每個節點包含鍵值、左子節點指標與右子節點指標：

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
} Node;

(c) 中序走訪

中序走訪的順序是「左子樹、根節點、右子樹」。對 BST 執行中序走訪時，會依鍵值由小到大輸出。

void inorder(Node *root) {
    if (root == NULL)
        return;

    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
}

(d) 插入節點

核心觀念

這題考無向加權圖的最小生成樹（Minimum Spanning Tree, MST）、加權鄰接矩陣，以及用程式找出 MST。

生成樹必須連接圖中的所有頂點，且不能有環；若圖有 $V$ 個頂點，生成樹恰有 $V-1$ 條邊。最小生成樹是在所有生成樹中，總邊權重最小者。

本題採用 Kruskal 演算法：將邊依權重由小到大排序，逐一加入；若加入某邊會形成環，就略過。使用並查集判斷兩端頂點是否已連通。

(a) 最小生成樹

由圖可讀出頂點為 $0,1,2,3,4,5$，各邊及權重如下：

邊	權重
$(1,2)$	2
$(3,4)$	2
$(0,2)$	3
$(2,3)$	3
$(3,5)$	3
$(1,3)$	5
$(2,4)$	5
$(1,0)$	6
$(4,5)$	9

依權重由小到大檢查：

1. 加入 $(1,2)$，權重 $2$。
2. 加入 $(3,4)$，權重 $2$。
3. 加入 $(0,2)$，權重 $3$，連接頂點 $0$ 與 $\{1,2\}$。
4. 加入 $(2,3)$，權重 $3$，連接 $\{0,1,2\}$ 與 $\{3,4\}$。
5. 加入 $(3,5)$，權重 $3$，將頂點 $5$ 接入。此時已選滿 $V-1=5$ 條邊。

所得最小生成樹可表示為：

1 --(2)-- 2 --(3)-- 0
           |
          (3)
           |
           3
          / \
       (2)   (3)
        /     \
       4       5

總權重為：

$$2+2+3+3+3=13$$

(b) 加權鄰接矩陣

以下依頂點順序 $0,1,2,3,4,5$ 排列。矩陣元素表示兩頂點間的邊權重；沒有邊時以 $0$ 表示。由於本圖所有邊權重皆為正數，$0$ 不會與有效邊權重混淆。

$$\begin{bmatrix} 0 & 6 & 3 & 0 & 0 & 0 \\ 6 & 0 & 2 & 5 & 0 & 0 \\ 3 & 2 & 0 & 3 & 5 & 0 \\ 0 & 5 & 3 & 0 & 2 & 3 \\ 0 & 0 & 5 & 2 & 0 & 9 \\ 0 & 0 & 0 & 3 & 9 & 0 \end{bmatrix}$$

(c) 以 Kruskal 演算法取得最小生成樹

先從矩陣取出所有無向邊，只讀取 $i<j$ 的位置，避免重複記錄同一條邊。排序後，用並查集檢查每條邊的兩端是否已在同一集合；若不在同一集合，就加入 MST 並合併集合。