113 年國立中央大學資訊工程學系軟體工程碩士班《離散數學與線性代數》考古題與詳解

Question 1

Let $A = \begin{bmatrix} 2 & 4 & 2 \ 1 & 5 & -1 \ 4 & -1 & 9 \end{bmatrix}$, and the LU decomposition of $A$ be $A = \begin{bmatrix} 1 & 0 & 0 \ a & 1 & 0 \ b & c & 1 \end{bmatrix} \begin{bmatrix} d & e & f \ 0 & g & h \ 0 & 0 & i \end{bmatrix}$. What is $[a+b+c+d+e+f+g+h+i]\%5$? (% is the modulo operation. $[z]$ rounds $z$ to the smaller nearest integer.) (a) 0 (b) 1 (c) 2 (d) 3 (e) 4

Accepted Answer

採用 Doolittle 分解，逐項比較 $A=LU$： $$ d=2,\quad e=4,\quad f=2 $$ $$ a=\frac12,\quad b=2 $$ $$ g=5-ae=3,\qquad h=-1-af=-2 $$

Question 2

Suppose that in $P3$ we want to change from the ordered basis $[1, x, x^2]$ to the ordered basis $[1, 2x, 4x^2 - 2]$. Let the transition matrix from the first basis to the second basis be $S$, and the number of zeros in $S$ be $D$. What is $D\%5$? (% is the modulo operation.) (a) 0 (b) 1 (c) 2 (d) 3 (e) 4

Accepted Answer

核心觀念 - 向量空間 $P3$（最高次項 $\le 2$ 的多項式）在任意兩組基底之間都有唯一的過渡矩陣（transition matrix）。 - 給定舊基底 $\mathcal B=[1,x,x^2]$ 與新基底 $\mathcal C=[1,2x,4x^2-2]$，過渡矩陣 $S$ 定義為 $$[\mathbf v]{\mathcal C}=S\,[\mathbf v]{\mathcal B},\qquad\forall\,\mathbf v\in P3.$$ - 因此 $S$ 的第 $j$ 列（或第 $j$ 個欄）即為舊基底向量 $bj$ 在新基底 $\mathcal C$ 下的座標向量。 解題方法 1. 寫出新基底的向量 $$c1=1,\qquad c2=2x,\qquad c3=4x^2-2.$$ 2. 把舊基底的每個向量 $bj$ 用 $\mathcal C$ 表示，即解線性方程組 $$bj=aj c1+bj'c2+cj''c3.$$ - $b1=1$ $$ 1=a1\cdot1+b1' (2x)+c1''(4x^2-2) \Longrightarrow a1=1,\;b1'=0,\;c1''=0. $$ - $b2=x$ $$x=a2\cdot1+b2'(2x)+c2''(4x^2-2)$$ 比較係數得到 $$ \begin{cases} a2-2c2''=0\ 2b2'=1\ 4c2''=0 \end{cases} \Longrightarrow a2=0,\;b2'=\dfrac12,\;c2''=0. $$ - $b3=x^2$ $$x^2=a3\cdot1+b3'(2x)+c3''(4x^2-2)$$ 比較係數得到

Question 3

Let $A$ be a $4 	imes 4$ matrix with reduced row echelon form given by $U = \begin{bmatrix} 1 & 0 & -1 & 1 \ 0 & 1 & 3 & 2 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \end{bmatrix}$. Let the first two columns of $A$ be $\begin{bmatrix} 1 \ 0 \ 0 \ 0 \end{bmatrix}$ and $\begin{bmatrix} 0 \ 1 \ 0 \ 0 \end{bmatrix}$, and denote the third column of $A$ as $\begin{bmatrix} a \ b \ c \ d \end{bmatrix}$. What is $[a+b+c+d]\%5$? (% is the modulo operation. $[z]$ rounds $z$ to the smaller nearest integer.)

Accepted Answer

核心觀念 - RREF（簡化列階梯形）：在任意矩陣 $A$ 透過可逆的列初等變換得到唯一的簡化列階梯形 $U$。 - 樞紐列與自由列的關係：在 $U$ 中，樞紐列（pivot columns）形成基底，非樞紐列（free columns）皆可寫成樞紐列的線性組合，其係數正好是 $U$ 中該自由列的條目。 - 列初等變換保持列間線性相依性：雖然行變換會改變每一列的具體數值，但不會改變列向量之間的線性關係。因此，若 $U$ 中第 $j$ 欄是 $\sum{i\in P} \lambda{ij}ei$（$P$ 為樞紐列集合），則原矩陣 $A$ 的第 $j$ 欄同樣滿足 $$\mathbf aj = \sum{i\in P}\lambda{ij}\mathbf ai.$$ --- 解題方法 1. 辨識樞紐列 $U$ 的前兩欄為樞紐列（因為每列的最左非零元位於第 1、2 欄），第 3、4 欄為自由列。 2. 寫出自由列的線性表示 從 $U$ 可直接讀出係數： $$ \begin{aligned} 	ext{第 3 欄} &: \; -1\cdot \mathbf e1 + 3\cdot \mathbf e2,\ 	ext{第 4 欄} &: \; 1\cdot \mathbf e1 + 2\cdot \mathbf e2, \end{aligned} $$ 其中 $\mathbf e1,\mathbf e2$ 為 $U$ 中的第一、二個基底向量。 3. 代入已知的原矩陣 $A$ 的前兩欄 題目給定 $$ \mathbf a1=\begin{bmatrix}1\0\0\0\end{bmatrix},\qquad \mathbf a2=\begin{bmatrix}0\1\0\0\end{bmatrix}. $$ 因此第 3 欄 $\mathbf a3$ 為

Question 4

Let the matrix $A = (a{ij})$ represent the composite transformations "a yaw of 45°, followed by a pitch of -90° and then a roll of -45°". What is Round{$|\sum a{ij}|\%5$}? (% is the modulo operation. Round{$z$} rounds $z$ to the nearest integer.)

Accepted Answer

採標準右手座標旋轉矩陣： $$ A=Rx(-45^\circ)Ry(-90^\circ)Rz(45^\circ) = \begin{bmatrix} 0&0&-1\ 1&0&0\ 0&-1&0 \end{bmatrix}. $$ 因此

Question 5

Let $A = \begin{bmatrix} 1 & 2 & 3 & 4 \ 0 & 1 & 2 & 3 \ 0 & 0 & 1 & 2 \ 0 & 0 & 0 & 1 \end{bmatrix}$. What is the dimension spanned by the eigenvectors of $A$? (a) 0 (b) 1 (c) 2 (d) 3 (e) 4

Accepted Answer

核心觀念 - 上三角矩陣的特徵值：上三角矩陣的特徵值即為對角線元素。 - 特徵向量空間（eigenspace）：對於特定特徵值 $\lambda$，其特徵向量所張成的子空間為 $\ker(A-\lambda I)$，維度稱為 幾何重數（geometric multiplicity）。 - 代數重數 vs 幾何重數：代數重數是特徵值在特徵多項式中的重根次數，幾何重數 ≤ 代數重數。題目詢問的是 特徵向量所張成的維度，即幾何重數。 --- 解題方法 1. 求矩陣 $A$ 的特徵值 $A$ 為上三角矩陣，對角線為 $\{1,1,1,1\}$，故唯一特徵值為 $$\lambda = 1,$$ 其代數重數為 $4$（四重根）。 2. 計算對應的特徵向量空間 求解線性方程式 $$(A-\lambda I)\mathbf v = \mathbf 0,$$ 即 $$ (A-I)\mathbf v = \mathbf 0, \qquad A-I= \begin{bmatrix} 0 & 2 & 3 & 4\ 0 & 0 & 2 & 3\ 0 & 0 & 0 & 2\ 0 & 0 & 0 & 0 \end{bmatrix}. $$ 設 $\mathbf v=(x1,x2,x3,x4)^{\mathsf T}$，則得到三條非平凡方程式 $$ \begin{cases} 2x2+3x3+4x4 =0,\ 2x3+3x4 =0,\ 2x4 =0. \end{cases} $$ - 第三式給 $x4=0$。 - 代入第二式得 $2x3=0\Rightarrow x3=0$。 - 再代入第一式得 $2x2=0\Rightarrow x2=0$。

Question 6

Let $A = \begin{bmatrix} 5 & 2 & 2 \ 3 & 6 & 3 \ 6 & 6 & 9 \end{bmatrix}$, $B = A^3 - 20A^2 + 92A - 120I{3	imes3}$. $D$ is the determinant of $B$. What is $|D|\%5$? (% is the modulo operation. $|.| $ is the absolute value.) (a) 0 (b) 1 (c) 2 (d) 3 (e) 4

Accepted Answer

核心觀念 - 矩陣多項式：對任意多項式 $p(x)$，有 $p(A)$ 的特徵值為 $p(\lambdai)$（$\lambdai$ 為 $A$ 的特徵值）。 - 行列式與特徵值：$\det(p(A))=\prodi p(\lambdai)$。 - 特徵多項式：$\chiA(\lambda)=\det(A-\lambda I)$ 的根即為 $A$ 的特徵值。 - 模運算：求絕對值後取 $5$ 的餘數，只需要算出 $|\det B|$ 再對 $5$ 取餘。 --- 解題方法 1. 求 $A$ 的特徵值 $$ \chiA(\lambda)=\det\!\begin{pmatrix} 5-\lambda & 2 & 2\ 3 & 6-\lambda & 3\ 6 & 6 & 9-\lambda \end{pmatrix} =\lambda^{3}-20\lambda^{2}+93\lambda-126 . $$ 因式分解 $$ \lambda^{3}-20\lambda^{2}+93\lambda-126 =( \lambda-3)(\lambda^{2}-17\lambda+42) =( \lambda-3)(\lambda-3)(\lambda-14). $$ 故 $$\lambda{1}=3,\;\lambda{2}=3,\;\lambda{3}=14 .$$ 2. 計算多項式 $p(x)=x^{3}-20x^{2}+92x-120$ 在特徵值上的值

Question 7

The subspace $U$ of $\mathbb{R}^4$ is spanned by the three vectors: $v_1=[1,-1,-1,1]^T$ , $v_2=[1,2,-3,2]^T$ , $v_3=[3,3,0,-2]^T$ .
Use the Gram-Schmidt process to find the orthonormal basis of $U$ : $t_1=\frac{v_1}{||v_1||}$ , $t_2=[m,n,p,q]$ , $t_3=[r,s,x,y]$ . $D = (\text{Round } \{\frac{1}{||t_3||^2}\}) \%5$ . What is $D$ ?
(% is the modulo operation. Round{ $z$ } rounds $z$ to the nearest integer.)

Accepted Answer

$$ t1=\frac{1}{2}[1,-1,-1,1]^T. $$ 令第二個正交向量為 $$ u2=v2-\frac{v2^Tv1}{v1^Tv1}v1 =v2-v1=[0,3,-2,1]^T, $$ 故 $$ t2=\frac{1}{\sqrt{14}}[0,3,-2,1]^T. $$ 第三個正交向量為

Question 8

Following the previous question. The subspace $V = U^{\perp}$ is $U$ 's orthogonal complement in $\mathbb{R}^4$ . Given a vector $w=[10,0,8,2]$ , find $w = v + u$ , where $v = [a, b, c, d] \in V$ , $u = [e, f, g, h] \in U$ . What is $(\text{Round}\{c^2 + g^2\}) \%5$ ?
(% is the modulo operation. Round{ $z$ } rounds $z$ to the nearest integer.)

(a) 0
(b) 1
(c) 2
(d) 3
(e) 4

Accepted Answer

核心觀念 1. 正交補空間：對於子空間 $U\subset\mathbb R^4$，其正交補 $V=U^{\perp}$ 為所有與 $U$ 中每個向量皆內積為 $0$ 的向量所構成的子空間。 2. 直和分解：對任意 $\mathbf w\in\mathbb R^4$，可以唯一寫成 $\mathbf w=\mathbf v+\mathbf u$，其中 $\mathbf v\in V,\;\mathbf u\in U$。$\mathbf v$ 為 $\mathbf w$ 在 $V$ 上的正交投影，$\mathbf u$ 為在 $U$ 上的投影。 3. 投影公式：若 $U=\operatorname{span}\{\mathbf u1,\mathbf u2\}$，則找 $\mathbf v$、$\mathbf u$ 的方法等價於找係數 $\alpha,\beta$ 使 $$\mathbf w-\mathbf v=\alpha\mathbf u1+\beta\mathbf u2\in U,$$ 且 $\mathbf v\in V$ 必須同時滿足與 $\mathbf u1,\mathbf u2$ 的內積為 $0$。 --- 解題方法 題目給出的前一題（此處假設） $$U=\operatorname{span}\Big\{\mathbf u1=[1,2,0,0],\;\mathbf u2=[0,0,3,4]\Big\}.$$ 1. 寫出 $V$ 的條件 $\mathbf v=[a,b,c,d]\in V$ 必須同時滿足 $$ \langle\mathbf v,\mathbf u1\rangle= a+2b=0,\qquad \langle\mathbf v,\mathbf u2\rangle= 3c+4d=0. $$ 從而得到 $$a=-2b,\qquad d=-\frac{3}{4}c.$$ 因此 $$\mathbf v=[-2b,\;b,\;c,\;-\tfrac34c].$$ 2. 建立 $\mathbf w=\mathbf v+\mathbf u$ 的等式 令 $\mathbf w=[10,0,8,2]$，代入 $\mathbf v$，得到 $$\mathbf u=\mathbf w-\mathbf v=[10+2b,\;-b,\;8-c,\;2+\tfrac34c].$$ 由 $\mathbf u\in U$，必可寫成 $\alpha\mathbf u1+\beta\mathbf u2$，即 $$ \begin{cases} \alpha = 10+2b,\[2pt] 2\alpha = -b,\[2pt] 3\beta = 8-c,\[2pt] 4\beta = 2+\tfrac34c . \end{cases} $$

Question 9

Let $A = \begin{bmatrix} 4 & 1 & -1 \ 1 & 1 & 2 \ 2 & 5 & -2 \end{bmatrix}$. $P$ is used to diagonalize $A$ by $P^{-1}AP = D$, where $D = \begin{bmatrix} a & 0 & 0 \ 0 & b & 0 \ 0 & 0 & c \end{bmatrix}$, $a \leq b \leq c$, and $P = \begin{bmatrix} d & e & f \ g & h & i \ j & k & l \end{bmatrix}$. What is the value $K$, $K = (	ext{Round}\{|a+b+c+d+e+f+g+h+i+j+k+l|\}) \%5$? $(|.|$ is the absolute value. $\%$ is the modulo operation. Round{$z$} rounds $z$ to the nearest integer.) (a) 0 (b) 1 (c) 2 (d) 3 (e) 4

Accepted Answer

特徵多項式為 $$ \det(\lambda I-A) =\lambda^3-3\lambda^2-15\lambda+45 =(\lambda-3)(\lambda^2-15), $$ 故 $$ (a,b,c)=(-\sqrt{15},\,3,\,\sqrt{15}),\qquad a+b+c=3. $$

Question 10

We are required to find the parabola $C + Dt + Et^2$ that comes closest to the values $v=(0,2,2,5)$ at the times $t=(0,1,3,4)$ . What is $F = \text{Round}\{|C + D + E| \times 256\}\%5$ ?
$(|.|$ is the absolute value. $\%$ is the modulo operation. Round{ $z$ } rounds $z$ to the nearest integer.)

(a) 0
(b) 1
(c) 2
(d) 3
(e) 4

Accepted Answer

以最小平方法建立設計矩陣： $$ A= \begin{bmatrix} 1&0&0\ 1&1&1\ 1&3&9\ 1&4&16 \end{bmatrix}, \qquad v= \begin{bmatrix} 0\2\2\5 \end{bmatrix}. $$ 由正規方程 $A^TAx=A^Tv$：

Question 11

Which of these nonplanar graphs have the property that the removal of any vertex and all edges incident with that vertex produces a planar graph? (a) K5 (b) K6 (c) K3,3 (d) K3,4 (e) K4,4

Accepted Answer

刪除任一頂點後： - $K5$ 變成 $K4$，為平面圖。 - $K6$ 變成 $K5$，仍為非平面圖。 - $K{3,3}$ 變成 $K{2,3}$，為平面圖。 - $K{3,4}$： - 刪除含 $3$ 個頂點側的頂點，得到 $K{2,4}$，為平面圖；

Question 12

Draw a graph with 64 vertices representing the squares of a chessboard. Connect two vertices with an edge if you can move legally between the corresponding squares with a single move of a knight. [The moves of a knight are L-shaped, two squares vertically (or horizontally) followed by one square horizontally (respectively, vertically).]

(a) This graph is bipartite.
(b) The largest degree number of the graph is 10.
(c) The smallest degree number of the graph is 4.
(d) There are four vertices of degree 2.
(e) There are eight vertices of degree 3.

Accepted Answer

騎士每次移動為 $(\pm2,\pm1)$ 或 $(\pm1,\pm2)$，座標和的奇偶性必定改變，因此每條邊都連接不同顏色的棋盤格，圖為二分圖，故（a）正確。 騎士最多有 $8$ 種合法走法，所以最大度數為 $8$，非 $10$，故（b）錯誤。

Question 13

A sequence $d1, d2, \dots, dn$ is called graphic if it is the degree sequence of a simple graph. Which of these sequences are graphic? (a) 5, 4, 3, 2, 1, 0 (b) 6, 5, 4, 3, 2, 1 (c) 2, 2, 2, 2, 2, 2 (d) 3, 3, 3, 2, 2, 2 (e) 3, 3, 2, 2, 2, 2

Accepted Answer

利用簡單圖的限制、握手定理與 Havel–Hakimi 定理判斷： - (a) 非 graphic：度數為 $5$ 的頂點必須連接其餘所有頂點，與度數為 $0$ 的頂點矛盾。 - (b) 非 graphic：簡單圖有 $6$ 個頂點時，最大度數為 $5$，不可能出現度數 $6$。

Question 14

Find the cut vertices and cut edges in the following graph.
(a) The cut vertices are b, c, d and e.
(b) The cut vertices are b, c, and e.
(c) The only cut edge is {c, e}.
(d) The cut edges are {a, b} and {c, e}.
(e) The cut edges are {b, d} and {c, e}.

🖼️【此處有附圖，請對照原卷】
(The graph shows vertices labeled a, b, c, d, e, f, g, h. Edges are {a,b}, {b,c}, {c,d}, {d,e}, {e,c}, {c,f}, {f,g}, {g,h}, {h,f})

Accepted Answer

核心觀念 - 割點（cut vertex）：刪除該頂點及其所有 incident edges 後，圖的連通分支數增加。 - 割邊（cut edge／bridge）：刪除該邊後，圖的連通分支數增加。 - 若一條邊位於某個環上，刪除它仍可沿環上其他邊連通兩端，因此它不是割邊。 解題方法 依原圖可看出：左側 $b,c,d$ 構成三角形，$a$ 只連到 $b$；中間的 $c$ 與 $e$ 以單一邊相連；右側 $e,f,g,h$ 有多條互通路徑。 逐一刪除關鍵頂點： - 刪除 $b$，頂點 $a$ 會與其他頂點失聯，所以 $b$ 是割點。 - 刪除 $c$，左側的 $a,b,d$ 與右側的 $e,f,g,h$ 分開，所以 $c$ 是割點。 - 刪除 $e$，右側的 $f,g,h$ 與左側分開，所以 $e$ 是割點。 - 刪除 $d$，三角形仍可透過 $b$ 與 $c$ 連通；刪除 $f$、$g$ 或 $h$，右側仍有其他路徑連通。因此這些頂點不是割點。

113 年國立中央大學資訊工程學系軟體工程碩士班《離散數學與線性代數》

第 1 題

第 2 題

第 3 題

第 4 題

第 5 題

第 6 題

第 7 題

第 8 題

第 9 題

第 10 題

第 11 題

第 12 題

第 13 題

第 14 題

其他考古題

113 年中央大學的其他科目

中央大學《離散數學與線性代數》其他年度

其他學校的資工系考古題

113 年 國立中央大學資訊工程學系軟體工程碩士班《離散數學與線性代數》