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

核心觀念

二次函數若可寫成

$$f(\mathbf{x})=-\mathbf{x}^{T}B\mathbf{x}+\mathbf{c}^{T}\mathbf{x}+d,$$

且對稱矩陣 $B$ 正定，則 $f$ 嚴格凹，存在唯一的全域最大值。最大值位置可由梯度為零求得：

$$\nabla f(\mathbf{x})=-2B\mathbf{x}+\mathbf{c}=\mathbf{0}.$$

解題方法

令 $\mathbf{x}=(x,y,z)^T$，將題目的二次項整理為矩陣形式：

$$f(\mathbf{x})=-\mathbf{x}^{T}B\mathbf{x}+\mathbf{c}^{T}\mathbf{x}-5,$$

其中

$$B= \begin{bmatrix} 1&1&0\\ 1&5&1\\ 0&1&4 \end{bmatrix}, \qquad \mathbf{c}= \begin{bmatrix} -2\\ 0\\ -4 \end{bmatrix}.$$

先確認 $B$ 正定。其順序主子式為

$$1>0,\qquad \begin{vmatrix} 1&1\\ 1&5 \end{vmatrix}=4>0,\qquad \det(B)=15>0.$$

依 Sylvester 判別法，$B$ 正定，因此 $f$ 嚴格凹，臨界點就是唯一的全域最大值位置。

令梯度為零：

$$-2B\mathbf{x}+\mathbf{c}=\mathbf{0} \quad\Longleftrightarrow\quad B\mathbf{x}=\frac{\mathbf{c}}{2} = \begin{bmatrix} -1\\ 0\\ -2 \end{bmatrix}.$$

展開成聯立方程：

$$\begin{cases} x+y=-1,\\ x+5y+z=0,\\ y+4z=-2. \end{cases}$$

【核心觀念】

實矩陣 $Q$ 為正交矩陣的定義是

$$Q^TQ=I_n.$$

向量長度平方可寫成內積：$\|x\|^2=x^Tx$。因此，若 $Q$ 保持所有向量的長度，就能進一步證明它保持內積。

【解題方法】

使用極化恆等式，從長度保持推出內積保持，再由內積保持證明 $Q^TQ=I_n$。

【證明】

對任意 $x,y\in\mathbb R^n$，有

$$2(Qx)^T(Qy)=\|Q(x+y)\|^2-\|Qx\|^2-\|Qy\|^2.$$

依題設，$\|Qz\|=\|z\|$ 對所有 $z\in\mathbb R^n$ 成立，因此

核心觀念

要在 $\operatorname{span}\{(1,1,1,1)^T\}$ 中找出與 $c$ 距離最短的向量，就是將 $c$ 正交投影到這個子空間。正交投影的誤差向量會與子空間垂直。

令 $u=(1,1,1,1)^T$，則子空間中的向量皆可寫成 $w=\alpha u$。

解題方法

使 $\|w-c\|$ 最小的向量為 $c$ 在 $u$ 上的正交投影：

$$w=\operatorname{proj}_{u}c =\frac{u^Tc}{u^Tu}u$$

計算分子與分母：

$$u^Tc=1+8+9+6=24,\qquad u^Tu=1+1+1+1=4$$

因此

核心觀念

條件 $S^T=-S$ 表示 $S$ 是實數反對稱矩陣。反對稱矩陣的二次型恆為零：對任意實向量 $x$，

$$x^T Sx=(x^T Sx)^T=x^T S^T x=-x^T Sx,$$

因此 $x^T Sx=0$。

解題方法

用核空間判斷 $S-I$ 是否可逆。假設 $(S-I)x=0$，則 $Sx=x$。左乘 $x^T$ 得

$$x^T Sx=x^T x.$$

核心觀念

本題考查 Gram–Schmidt 正交化與薄型 QR 分解。對 $A=[a_1\ a_2\ a_3]$，依序計算

$$r_{ij}=q_i^Ta_j,\qquad u_j=a_j-\sum_{i=1}^{j-1}r_{ij}q_i,\qquad r_{jj}=\|u_j\|,\qquad q_j=\frac{u_j}{r_{jj}}.$$

如此得到 $A=QR$，其中 $Q$ 的欄向量彼此正交且長度為 $1$，$R$ 為上三角矩陣。最小平方解則由 $R\hat{x}=Q^Tb$ 求得。

解題方法與推導

令 $a_1,a_2,a_3$ 分別為 $A$ 的三個欄向量。題目已給

$$q_1=\frac{1}{\sqrt{2}} \begin{bmatrix}1\\0\\1\\0\end{bmatrix}, \qquad r_{11}=\sqrt{2}.$$

對第二欄，

$$r_{12}=q_1^Ta_2=\sqrt{2}, \qquad u_2=a_2-r_{12}q_1 =\begin{bmatrix}-1\\1\\1\\1\end{bmatrix}.$$

因此

$$r_{22}=\|u_2\|=2, \qquad q_2=\frac{u_2}{r_{22}} =\frac12\begin{bmatrix}-1\\1\\1\\1\end{bmatrix}.$$

對第三欄，

$$r_{13}=q_1^Ta_3=\frac{1}{\sqrt{2}}, \qquad r_{23}=q_2^Ta_3=0.$$

移除在 $q_1,q_2$ 方向上的投影後，

$$u_3=a_3-r_{13}q_1-r_{23}q_2 =\begin{bmatrix}\frac12\\1\\-\frac12\\0\end{bmatrix}.$$

所以

$$r_{33}=\|u_3\|=\frac{\sqrt{6}}{2}, \qquad q_3=\frac{u_3}{r_{33}} =\frac{1}{\sqrt{6}}\begin{bmatrix}1\\2\\-1\\0\end{bmatrix}.$$

(a) 正交單位向量與 $Q$

$$Q= \begin{bmatrix} \frac{1}{\sqrt{2}}&-\frac12&\frac{1}{\sqrt{6}}\\ 0&\frac12&\frac{2}{\sqrt{6}}\\ \frac{1}{\sqrt{2}}&\frac12&-\frac{1}{\sqrt{6}}\\ 0&\frac12&0 \end{bmatrix}.$$

核心觀念

若矩陣滿足 $C^2=C$，稱為冪等矩陣。此時對所有正整數 $n$，都有 $C^n=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$，則對所有正整數 $n$ 都有 $C^n=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.$$

所以 $C^n=C$（$n\ge 1$）。代入矩陣指數的冪級數：

核心觀念

使用二項式定理：

$$(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k$$

因為 $0.01>0$，展開後各項皆為正，因此只取前幾項，就能得到原式的下界。

解題方法

將 $1.01$ 寫成 $1+0.01$，展開前幾項：

$$1.01^{100}=(1+0.01)^{100}$$

核心觀念

若正整數 $x$ 的冪 $x^x$ 是 $2$ 的冪，則 $x$ 本身也只能含有質因數 $2$，因此 $x$ 必須是 $2$ 的冪。接著利用同底數相等時指數相等，將原式化成整數方程。

解題方法

題目右側大於 $1$，所以 $x>1$。由於 $x^x=2^{2048}$，$x^x$ 的質因數只有 $2$，故 $x$ 也只能有質因數 $2$。設

$$x=2^k,\qquad k\in\mathbb{Z}_{>0}.$$

代回原式：

$$(2^k)^{2^k}=2^{2048},$$

因此

$$k2^k=2048=2^{11}.$$

核心觀念

「自然數有無限多個」表示自然數集合沒有最大元素：對每一個自然數，都能找到一個更大的自然數。這裡使用自然數的通常大小關係 $>$。

解題方法

先以 $x$ 表示任意自然數，再要求存在自然數 $y$ 大於 $x$。由於題目指定用 $x\in N$ 表示「$x$ 是自然數」，可寫成：

$$\forall x\bigl(x\in N \rightarrow \exists y\,(y\in N \land y>x)\bigr)$$

核心觀念

利用平方根的整數部分分組。對正整數 $j$，只要

$$j^2 \le k < (j+1)^2,$$

就有 $\lfloor\sqrt{k}\rfloor=j$。因此，每個整數 $j$ 對應一段連續的 $k$ 值。

解題方法

假設 $n$ 為正整數。對 $j=1,2,\ldots,n-1$，滿足 $\lfloor\sqrt{k}\rfloor=j$ 的整數 $k$ 為

$$j^2,\ j^2+1,\ \ldots,\ (j+1)^2-1,$$

共有

$$(j+1)^2-j^2=2j+1$$

個，每個的值都是 $j$，所以這一組的總和是 $j(2j+1)$。

最後一組 $j=n$ 只包含 $k=n^2$，貢獻為 $n$。因此

$$\sum_{k=1}^{n^2}\lfloor\sqrt{k}\rfloor =\sum_{j=1}^{n-1}j(2j+1)+n.$$

核心觀念

本題考查集合的可數性與康托對角線法。若一個集合的元素能列成序列 $f_1,f_2,f_3,\ldots$，就稱它至多可數；若無法列成這樣的序列，便是不可數。

每個函數 $f:N\to\{0,a\}$ 都能用來表示 $N$ 的一個子集：取所有滿足 $f(n)=a$ 的 $n$。反過來，每個 $N$ 的子集也對應到一個這樣的函數。因此，$F$ 和 $N$ 的冪集合一樣大。由康托定理，無限集合 $N$ 的冪集合不可數。

解題方法

也可以直接用對角線法證明。假設 $F$ 可數，則所有函數都能排成一列：

$$f_1,f_2,f_3,\ldots$$

定義一個新函數 $g:N\to\{0,a\}$，讓它在第 $n$ 個輸入值上，取與 $f_n(n)$ 不同的值：

核心觀念

普通生成函數 $G(x)=\sum_{n=0}^{\infty}a_nx^n$ 中，$x^n$ 的係數 $a_n$ 就是序列的第 $n$ 項。因此，只要將 $G(x)$ 展開並讀出各次方的係數，即可得到所生成的序列。

解題方法

利用平方差公式 $x^6-1=(x-1)(x^5+x^4+x^3+x^2+x+1)$，可得

$$G(x)=\frac{x^6-1}{x-1} =x^5+x^4+x^3+x^2+x+1 =1+x+x^2+x^3+x^4+x^5.$$

核心觀念

由分割 $P_1$ 對應的等價關係，定義為：兩個元素屬於同一個分割區塊時，兩者便形成一組有序對。

因此，等價關係中的有序對數量，等於各區塊大小的平方總和。此題的區塊大小為 $1$ 與 $3$，所以有序對總數為

$$1^2+3^2=10$$

解題方法

區塊 $\{a\}$ 只有一個元素，產生的有序對為 $(a,a)$。

區塊 $\{b,c,d\}$ 中，每個元素都能和同一區塊內的每個元素配對，包含元素與自身的配對，因此產生 $3\times 3=9$ 組：

核心觀念

連通平面圖可使用歐拉公式：

$$V-E+F=2$$

其中 $V$ 是頂點數、$E$ 是邊數，$F$ 是平面嵌入後的區域數，包含外部區域。

握手定理指出，所有頂點的度數總和等於邊數的兩倍：

$$\sum_{v\in V}\deg(v)=2E$$

解題方法

題目有 $10$ 個頂點，每個頂點的度數都是 $14$，所以度數總和為

$$\sum_{v\in V}\deg(v)=10\times14=140$$

核心觀念

生成樹是包含原圖所有頂點、連通且沒有環的子圖。本題用到兩個觀念：

• 橋邊必選：刪除後會使圖不連通的邊稱為橋邊；每棵生成樹都必須包含它。
• Cayley 公式：具有 $k$ 個相異頂點的完全圖 $K_k$，其生成樹數為 $$\tau(K_k)=k^{k-2},\qquad k\ge 2.$$

解題方法

附上的頁圖印刷內容為第 2-1、2-2 題的矩陣問題，未包含第 9-2 題的啞鈴圖。以下依本題文字所定義的結構作答：兩個頂點集合互不重疊的完全圖 $K_n$、$K_m$，以唯一一條邊相連，且 $n,m\ge 2$。

設連接兩個完全圖的邊為 $e$。

第一步：連接邊 $e$ 必須納入生成樹。

兩側之間只有 $e$ 相連，刪除 $e$ 就會使整張圖分成兩個連通分量。因此 $e$ 是橋邊，每棵生成樹都必須包含它，這一步沒有額外的選擇數。

第二步：每一側都必須選出自己的生成樹。