115 年 國立中山大學應用數學系碩士班乙組《線性代數（乙）》

核心觀念

題目要求將矩陣 $A$ 分解為

$$A=UL,$$

其中 $U$ 為上三角矩陣，$L$ 為對角線元素皆為 $1$ 的下三角矩陣。設

$$A= \begin{pmatrix} 1&1&0\\ 2&1&-1\\ 3&-1&-1 \end{pmatrix}.$$

令

$$U= \begin{pmatrix} u_{11}&u_{12}&u_{13}\\ 0&u_{22}&u_{23}\\ 0&0&u_{33} \end{pmatrix}, \qquad L= \begin{pmatrix} 1&0&0\\ \ell_{21}&1&0\\ \ell_{31}&\ell_{32}&1 \end{pmatrix}.$$

因為 $L$ 的對角線元素固定為 $1$，未知數為

$$u_{11},u_{12},u_{13},u_{22},u_{23},u_{33}, \ell_{21},\ell_{31},\ell_{32}.$$

---

解題方法

直接計算矩陣乘積 $UL$：

$$UL= \begin{pmatrix} u_{11}+u_{12}\ell_{21}+u_{13}\ell_{31} & u_{12}+u_{13}\ell_{32} & u_{13} \\[4pt] u_{22}\ell_{21}+u_{23}\ell_{31} & u_{22}+u_{23}\ell_{32} & u_{23} \\[4pt] u_{33}\ell_{31} & u_{33}\ell_{32} & u_{33} \end{pmatrix}.$$

令此矩陣等於 $A$，由右下方逐步求解未知數。

第一步：由第三欄求出 $U$ 的第三欄

由矩陣乘積的第三欄可直接得到

$$u_{13}=0,\qquad u_{23}=-1,\qquad u_{33}=-1.$$

因此

$$u_{13}=0,\quad u_{23}=-1,\quad u_{33}=-1.$$

第二步：由第三列求出 $L$ 的第三列

第三列第一個元素給出

$$u_{33}\ell_{31}=3.$$

代入 $u_{33}=-1$：

$$-\ell_{31}=3 \quad\Longrightarrow\quad \ell_{31}=-3.$$

第三列第二個元素給出

$$u_{33}\ell_{32}=-1.$$

因此

$$-\ell_{32}=-1 \quad\Longrightarrow\quad \ell_{32}=1.$$

第三步：求出 $u_{22}$

第二列第二個元素為

$$u_{22}+u_{23}\ell_{32}=1.$$

代入 $u_{23}=-1$ 與 $\ell_{32}=1$：

$$u_{22}-1=1,$$

故

$$u_{22}=2.$$

第四步：求出 $\ell_{21}$

第二列第一個元素為

$$u_{22}\ell_{21}+u_{23}\ell_{31}=2.$$

代入 $u_{22}=2$、$u_{23}=-1$、$\ell_{31}=-3$：

本題要求證明一個 n x n 的 Hermitian 正半定矩陣 $A$，存在唯一的 Hermitian 正半定矩陣 $B$ 滿足 $B^2 = A$。這涉及到矩陣的平方根問題，特別是對於正半定矩陣。

證明存在性：
由於 $A$ 是 Hermitian 且正半定的，根據譜定理 (Spectral Theorem)，存在一個酉矩陣 $P$ 和一個對角矩陣 $D$，使得 $A = P D P^{-1}$，其中 $D$ 的對角元素 $d_i$ 都是非負實數（因為 $A$ 是正半定的）。由於 $A$ 是 Hermitian 矩陣，我們可以選擇 $P$ 為么正矩陣，此時 $P^{-1} = P^*$, 所以 $A = P D P^*$。
$D = \text{diag}(d_1, d_2, \dots, d_n)$, 其中 $d_i \ge 0$ 對於所有 $i=1, \dots, n$。

我們構造一個矩陣 $B = P D^{1/2} P^*$，其中 $D^{1/2} = \text{diag}(\sqrt{d_1}, \sqrt{d_2}, \dots, \sqrt{d_n})$。
現在我們來驗證 $B$ 是否滿足題目要求：

1. $B$ 是 Hermitian 的嗎？
   $B^* = (P D^{1/2} P^*)^* = (P^*)^* (D^{1/2})^* P^* = P (D^{1/2})^* P^*$。
   由於 $D^{1/2}$ 是對角矩陣，且其對角元素 $\sqrt{d_i}$ 都是實數，所以 $(D^{1/2})^* = D^{1/2}$。
   因此，$B^* = P D^{1/2} P^* = B$。
   所以，$B$ 是 Hermitian 的。

2. $B$ 是正半定的嗎？
   對於任意的向量 $x \in \mathbb{C}^n$，我們計算 $x^* B x$。
   $x^* B x = x^* (P D^{1/2} P^*) x = (x^* P) D^{1/2} (P^* x)$。
   令 $y = P^* x$。則 $x^* B x = y^* D^{1/2} y$。
   $y^* D^{1/2} y = \begin{pmatrix} \bar{y}_1 & \bar{y}_2 & \dots & \bar{y}_n \end{pmatrix} \begin{pmatrix} \sqrt{d_1} & & \\ & \ddots & \\ & & \sqrt{d_n} \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}$
   $y^* D^{1/2} y = \sum_{i=1}^n \sqrt{d_i} |y_i|^2$。
   由於 $d_i \ge 0$ 且 $|y_i|^2 \ge 0$，所以 $\sum_{i=1}^n \sqrt{d_i} |y_i|^2 \ge 0$。
   因此，$x^* B x \ge 0$ 對於所有 $x \in \mathbb{C}^n$。
   所以，$B$ 是正半定的。

3. $B^2 = A$ 嗎？
   $B^2 = (P D^{1/2} P^*) (P D^{1/2} P^*)$。
   由於 $P$ 是么正矩陣， $P^* P = I$ (單位矩陣)。
   $B^2 = P D^{1/2} (P^* P) D^{1/2} P^* = P D^{1/2} I D^{1/2} P^* = P (D^{1/2} D^{1/2}) P^*$。
   $D^{1/2} D^{1/2} = (\text{diag}(\sqrt{d_1}, \dots, \sqrt{d_n}))^2 = \text{diag}((\sqrt{d_1})^2, \dots, (\sqrt{d_n})^2) = \text{diag}(d_1, \dots, d_n) = D$。
   所以，$B^2 = P D P^* = A$。

這樣我們證明了存在一個 Hermitian 正半定矩陣 $B$ 使得 $B^2 = A$。

證明唯一性：
假設存在兩個 Hermitian 正半定的矩陣 $B_1$ 和 $B_2$ 滿足 $B_1^2 = A$ 和 $B_2^2 = A$。
我們需要證明 $B_1 = B_2$。

考慮矩陣 $B_1$ 和 $B_2$。由於它們都是 Hermitian 且正半定的，它們也具有實數的非負對角元素的譜分解。
$A = P D P^*$，其中 $D = \text{diag}(d_1, \dots, d_n)$， $d_i \ge 0$。
$B_1$ 是 Hermitian 正半定的，所以 $B_1 = Q_1 D_1 Q_1^*$，其中 $D_1 = \text{diag}(e_1, \dots, e_n)$， $e_i \ge 0$。
$B_1^2 = Q_1 D_1^2 Q_1^* = A = P D P^*$。
由於 $A$ 的譜分解（在決定 $P$ 和 $D$ 的順序是唯一的情況下）是唯一的，我們可以假定 $Q_1 = P$ (通過調整 $P$ 的列順序和對應 $D$ 的對角元素順序，以及符號)。
那麼 $D_1^2 = D$。
$D_1^2 = \text{diag}(e_1^2, \dots, e_n^2)$。
$D = \text{diag}(d_1, \dots, d_n)$。
所以 $e_i^2 = d_i$ 對於所有 $i$。
由於 $e_i \ge 0$ (因為 $B_1$ 是正半定的) 且 $d_i \ge 0$，我們有 $e_i = \sqrt{d_i}$。
因此，$D_1 = \text{diag}(\sqrt{d_1}, \dots, \sqrt{d_n}) = D^{1/2}$。
所以 $B_1 = P D^{1/2} P^*$。

同理，假設 $B_2$ 是另一個 Hermitian 正半定矩陣，滿足 $B_2^2 = A$。
那麼 $B_2$ 也可以寫成 $B_2 = P D_2 P^*$，其中 $D_2 = \text{diag}(f_1, \dots, f_n)$， $f_i \ge 0$。
$B_2^2 = P D_2^2 P^* = A = P D P^*$。
因此 $D_2^2 = D$。
由於 $f_i \ge 0$ 且 $d_i \ge 0$，我們有 $f_i = \sqrt{d_i}$。
所以 $D_2 = \text{diag}(\sqrt{d_1}, \dots, \sqrt{d_n}) = D^{1/2}$。
因此 $B_2 = P D^{1/2} P^*$。

比較 $B_1$ 和 $B_2$，我們發現 $B_1 = B_2$。

這裡需要更嚴謹地處理譜分解的唯一性。
如果 $A$ 的特徵值是唯一的（即 $d_i$ 互不相同），那麼 $P$ 的列向量（特徵向量）的方向是唯一的，且 $D$ 的順序也是唯一的。此時 $B = P D^{1/2} P^*$ 是唯一的。

如果 $A$ 有重覆的特徵值，例如 $d_1 = d_2 > 0$，那麼 $A$ 的特徵空間是多維的。
$A = P D P^*$。
$B$ 是 Hermitian 正半定的，且 $B^2 = A$。
令 $A$ 的特徵值為 $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge 0$。
$A = \sum_{i=1}^n \lambda_i v_i v_i^*$，其中 $v_i$ 是標準正交特徵向量。
我們構造 $B = \sum_{i=1}^n \sqrt{\lambda_i} v_i v_i^*$。
$B$ 是 Hermitian 的，因為 $v_i v_i^*$ 是 Hermitian 的。
$B$ 是正半定的，因為 $\sqrt{\lambda_i} \ge 0$。
$B^2 = (\sum_{i=1}^n \sqrt{\lambda_i} v_i v_i^*) (\sum_{j=1}^n \sqrt{\lambda_j} v_j v_j^*) = \sum_{i,j} \sqrt{\lambda_i \lambda_j} v_i v_i^* v_j v_j^*$。
由於 $\{v_i\}$ 是標準正交基， $v_i^* v_j = \delta_{ij}$。
$B^2 = \sum_{i} \sqrt{\lambda_i^2} v_i v_i^* = \sum_{i} \lambda_i v_i v_i^* = A$。
這樣存在性證明了。

現在證明唯一性。
假設 $B_1$ 和 $B_2$ 都是 $A$ 的 Hermitian 正半定平方根。
則 $B_1^2 = B_2^2 = A$。
令 $x$ 為任意向量。
$B_1 A = B_1 B_1^2 = B_1^3$。
$A B_1 = B_1^2 B_1 = B_1^3$。
所以 $B_1 A = A B_1$。
同理 $B_2 A = A B_2$。
這意味著 $B_1$ 和 $B_2$ 與 $A$ 可交換。
由於 $A$ 是 Hermitian 正半定的，我們可以找到一個共同的酉對角化矩陣 $P$，使得 $A = P D P^*$ 且 $B_1 = P D_1 P^*$， $B_2 = P D_2 P^*$。
其中 $D = \text{diag}(\lambda_1, \dots, \lambda_n)$， $\lambda_i \ge 0$。
$D_1 = \text{diag}(e_1, \dots, e_n)$， $e_i \ge 0$。
$D_2 = \text{diag}(f_1, \dots, f_n)$， $f_i \ge 0$。
$B_1^2 = A \implies P D_1^2 P^* = P D P^* \implies D_1^2 = D \implies e_i^2 = \lambda_i$。
$B_2^2 = A \implies P D_2^2 P^* = P D P^* \implies D_2^2 = D \implies f_i^2 = \lambda_i$。
由於 $e_i, f_i, \lambda_i \ge 0$，我們有 $e_i = \sqrt{\lambda_i}$ 且 $f_i = \sqrt{\lambda_i}$。
因此 $D_1 = D_2 = \text{diag}(\sqrt{\lambda_1}, \dots, \sqrt{\lambda_n})$。
這就意味著 $B_1 = P D_1 P^* = P D_2 P^* = B_2$。

這證明了唯一性。

更進一步的思考：
如果 $A$ 是正定矩陣，那麼 $d_i > 0$，所以 $\sqrt{d_i} > 0$。此時 $B$ 也是正定矩陣，且 $B$ 的特徵值也是唯一的。
如果 $A$ 有零特徵值，例如 $\lambda_k = 0$，那麼對應的 $e_k = f_k = \sqrt{0} = 0$。

核心觀念

設線性轉換

$$L:\mathbb{F}^n\to\mathbb{F}^m$$

的矩陣表示為 $A\in\mathbb{F}^{m\times n}$，因此對任意向量 $x\in\mathbb{F}^n$，

$$L(x)=Ax.$$

本題使用以下觀念：

1. $L$ 一對一 $\Longleftrightarrow \ker L=\{0\}$。
2. $L$ onto $\Longleftrightarrow \operatorname{Im}L=\mathbb{F}^m$。
3. 矩陣乘法 $Ax$ 可表示為 $A$ 的欄向量線性組合。
4. 矩陣的列空間是其所有列向量的張成空間，且 $$\operatorname{rank}(A) =\text{欄空間維度} =\text{列空間維度}.$$

---

（1）證明 $L$ 是一對一，當且僅當 $A$ 的所有欄向量線性獨立

設 $A$ 的欄向量為

$$A=\begin{bmatrix} \,|&|&&|\,\\ a_1&a_2&\cdots&a_n\\ \,|&|&&|\, \end{bmatrix},$$

其中每個 $a_j\in\mathbb{F}^m$。

對任意

$$x= \begin{bmatrix} x_1\\x_2\\ \vdots\\x_n \end{bmatrix} \in\mathbb{F}^n,$$

有

$$Ax=x_1a_1+x_2a_2+\cdots+x_na_n.$$

證明 $L$ 一對一 $\Longrightarrow$ $A$ 的欄向量線性獨立

因為 $L$ 一對一，所以

$$L(x)=L(y)\Longrightarrow x=y.$$

要證明 $a_1,\ldots,a_n$ 線性獨立，考慮其線性組合等於零向量的情形：

$$c_1a_1+c_2a_2+\cdots+c_na_n=0.$$

令

$$c= \begin{bmatrix} c_1\\c_2\\ \vdots\\c_n \end{bmatrix}.$$

依照矩陣乘法，

$$Ac=c_1a_1+c_2a_2+\cdots+c_na_n=0.$$

由 $L(x)=Ax$ 可得

$$L(c)=Ac=0=L(0).$$

由於 $L$ 一對一，因此

$$c=0.$$

也就是

$$c_1=c_2=\cdots=c_n=0.$$

因此 $a_1,\ldots,a_n$ 線性獨立。

---

證明 $A$ 的欄向量線性獨立 $\Longrightarrow$ $L$ 一對一

假設 $A$ 的所有欄向量 $a_1,\ldots,a_n$ 線性獨立。

欲證明 $L$ 一對一，只需證明

$$L(x)=L(y)\Longrightarrow x=y.$$

若

$$L(x)=L(y),$$

則

$$Ax=Ay.$$

移項得

$$A(x-y)=0.$$

令

$$z=x-y= \begin{bmatrix} z_1\\z_2\\ \vdots\\z_n \end{bmatrix}.$$

則

$$Az=z_1a_1+z_2a_2+\cdots+z_na_n=0.$$

由於 $a_1,\ldots,a_n$ 線性獨立，只有所有係數皆為零時，線性組合才會等於零向量。因此

$$z_1=z_2=\cdots=z_n=0,$$

所以

$$z=0.$$

因此

$$x-y=0\Longrightarrow x=y.$$

故 $L$ 是一對一。

綜合兩方向，得到

$$\boxed{ L\text{ 是一對一} \Longleftrightarrow A\text{ 的所有欄向量線性獨立} }.$$

---

（2）證明 $L$ onto，當且僅當 $A$ 的所有列向量線性獨立

設 $A$ 的列向量為

$$r_1^T,r_2^T,\ldots,r_m^T,$$

其中每個 $r_i^T\in\mathbb{F}^{1\times n}$。

證明 $L$ onto $\Longrightarrow$ $A$ 的所有列向量線性獨立

本題要求證明，對於一個 $m \times n$ 的實數矩陣 $A$，其中 $m > n$，向量 $x$ 是最小平方解 (least squares solution) 的充要條件是 $Ax$ 是向量 $b$ 在 $A$ 的值域空間 (range space) 上的投影。

定義與核心概念：

• 最小平方解 (Least Squares Solution): 對於方程組 $Ax=b$，如果 $b$ 不在 $A$ 的值域空間 (即 $A$ 的列空間) 中，則方程組無精確解。最小平方解 $x^*$ 是指使得 $\|Ax - b\|$ 最小的向量 $x$。這個最小化問題等價於最小化 $\|Ax - b\|^2$。
• 值域空間 (Range Space): 矩陣 $A$ 的值域空間，記為 $\text{Range}(A)$ 或 $\text{Col}(A)$，是 $A$ 的所有列向量的線性組合所形成的向量空間。
• 投影 (Projection): 向量 $p$ 是向量 $b$ 在子空間 $S$ 上的投影，如果 $p \in S$ 且 $b-p$ 垂直於 $S$ (即 $b-p$ 在 $S$ 的正交補空間中)。

證明存在性與唯一性 (通常最小平方解存在且在某些條件下唯一，但這裡只要求證明等價性):
最小平方解 $x^*$ 滿足正規方程 (normal equations)：$A^T A x^* = A^T b$。
這裡 $A^T$ 是 $A$ 的轉置矩陣。由於 $A$ 是 $m \times n$ 的實矩陣， $A^T$ 是 $n \times m$ 的。矩陣 $A^T A$ 是 $n \times n$ 的。

證明等價性：

($\Rightarrow$) 證明：若 $x$ 是 $Ax=b$ 的最小平方解，則 $Ax$ 是 $b$ 在 $\text{Range}(A)$ 上的投影。
設 $x$ 是 $Ax=b$ 的一個最小平方解。這意味著 $\|Ax - b\|$ 被最小化。
令 $p = Ax$。根據投影的定義，我們需要證明：

1. $p \in \text{Range}(A)$。

2. $b - p$ 垂直於 $\text{Range}(A)$。

3. $p \in \text{Range}(A)$:
   由於 $p = Ax$，其中 $x$ 是一個 $n \times 1$ 的向量， $p$ 是 $A$ 的列向量的線性組合。因此，$p$ 必然在 $A$ 的值域空間 (列空間) $\text{Range}(A)$ 中。

4. $b - p$ 垂直於 $\text{Range}(A)$:
   $b - p = b - Ax$。
   向量 $b-p$ 垂直於 $\text{Range}(A)$，意味著 $b-p$ 與 $\text{Range}(A)$ 中的每一個向量都內積為零。由於 $\text{Range}(A)$ 由 $A$ 的列向量張成，這等價於 $b-p$ 與 $A$ 的每一個列向量都垂直。
   設 $A$ 的列向量為 $a_1, a_2, \dots, a_n$。則對於 $i=1, \dots, n$， $a_i^T (b - Ax) = 0$。
   這可以寫成矩陣形式：$A^T (b - Ax) = 0$。
   整理得到 $A^T b - A^T Ax = 0$，即 $A^T Ax = A^T b$。
   這正是最小平方解滿足的正規方程。
   因此，如果 $x$ 是最小平方解，則 $A^T (b - Ax) = 0$，這意味著 $b - Ax$ 與 $A$ 的所有列向量都垂直，進而 $b - Ax$ 垂直於 $\text{Range}(A)$。
   所以，$p = Ax$ 是 $b$ 在 $\text{Range}(A)$ 上的投影。

($\Leftarrow$) 證明：若 $Ax$ 是 $b$ 在 $\text{Range}(A)$ 上的投影，則 $x$ 是 $Ax=b$ 的最小平方解。
假設 $p = Ax$ 是 $b$ 在 $\text{Range}(A)$ 上的投影。
根據投影的定義，有兩個條件：

1. $p \in \text{Range}(A)$。

2. $b - p$ 垂直於 $\text{Range}(A)$。

3. $p = Ax$ 顯然屬於 $\text{Range}(A)$。

4. $b - p$ 垂直於 $\text{Range}(A)$。這意味著 $b - p$ 與 $\text{Range}(A)$ 中的所有向量都正交。由於 $\text{Range}(A)$ 由 $A$ 的列向量張成，這意味著 $b - p$ 與 $A$ 的每一個列向量都正交。
   即對於 $A$ 的每一個列向量 $a_i$，有 $a_i^T (b - p) = 0$。
   寫成矩陣形式，這就是 $A^T (b - p) = 0$。
   將 $p = Ax$ 代入，得到 $A^T (b - Ax) = 0$。
   展開即為 $A^T b - A^T Ax = 0$，或 $A^T Ax = A^T b$。
   這表示 $x$ 滿足正規方程。

   現在我們需要證明 $x$ 是最小平方解，即 $\|Ax - b\|$ 被最小化。
   對於任意的向量 $y$，我們考慮 $\|Ay - b\|^2$。
   $Ay$ 是 $b$ 在 $\text{Range}(A)$ 上的投影 $p$ 之外的另一個向量 (除非 $Ay=p$)。
   我們知道 $b - p$ 垂直於 $\text{Range}(A)$。
   由於 $Ay \in \text{Range}(A)$，我們可以將 $b-Ay$ 分解為：
   $b - Ay = (b - p) + (p - Ay)$。
   其中 $b-p$ 垂直於 $\text{Range}(A)$，而 $p-Ay$ 也屬於 $\text{Range}(A)$ (因為 $p$ 和 $Ay$ 都屬於 $\text{Range}(A)$)。
   根據畢氏定理 (Pythagorean theorem)， $\|b - Ay\|^2 = \|b - p\|^2 + \|p - Ay\|^2$。
   由於 $\|p - Ay\|^2 \ge 0$，我們有 $\|b - Ay\|^2 \ge \|b - p\|^2$。
   這個不等式對於任意的 $y$ 都成立。
   這意味著 $\|b - p\|^2$ 是 $\|Ay - b\|^2$ 的最小值，並且這個最小值在 $Ay = p$ 時達到。
   因此，使得 $\|Ay - b\|$ 最小的 $y$ 就是滿足 $Ay = p$ 的 $y$。
   由於 $p = Ax$ (由假設)，所以使得 $\|Ay - b\|$ 最小的 $y$ 就是滿足 $Ay = Ax$ 的 $y$。
   如果 $x$ 是唯一的最小平方解，那麼 $y=x$。
   更一般地，如果 $x$ 是滿足 $Ax=p$ 的一個解，那麼 $\|Ax - b\|$ 達到最小值。
   由於 $p = Ax$ 是 $b$ 在 $\text{Range}(A)$ 上的投影，所以 $x$ 滿足 $A^T Ax = A^T b$。
   這保證了 $x$ 是最小平方解。

關於 $m > n$ 的條件：
題目給定的條件是 $m > n$。

• 對於 $Ax=b$， $A$ 是 $m \times n$ 的矩陣，$x$ 是 $n \times 1$ 的向量，$b$ 是 $m \times 1$ 的向量。
• 由於 $m > n$，矩陣 $A$ 是「高瘦型」(tall and skinny)。
• 在此情況下，矩陣 $A^T A$ ($n \times n$) 是可逆的，因此最小平方解 $x$ 是唯一的。
  證明 $A^T A$ 可逆：若 $A^T A y = 0$ 對某個 $y \in \mathbb{R}^n$，則 $y^T A^T A y = 0$，即 $(Ay)^T (Ay) = 0$，所以 $\|Ay\|^2 = 0$，這意味著 $Ay = 0$。由於 $A$ 的列向量在 $\mathbb{R}^m$ 中，且 $m > n$，如果 $Ay=0$ 僅當 $y=0$，則 $A$ 的列向量是線性獨立的，此時 $\text{rank}(A)=n$。
  在 $m > n$ 的情況下，如果 $A$ 的列向量是線性獨立的，則 $A^T A$ 是可逆的。
  通常，如果 $A$ 的列向量是線性獨立的，則 $A^T A$ 是可逆的。

核心觀念

本題考查三個重點：

1. 將二階遞迴數列改寫成一階矩陣遞迴。
2. 利用特徵值與特徵向量對矩陣作對角化。
3. 透過矩陣冪次得到 Fibonacci 數列的通項公式。

令狀態向量為

$$v_n= \begin{pmatrix} y_n\\ y_{n-1} \end{pmatrix}.$$

題目要求將 $v_{n+1}$ 表示成 $A v_n$。

解題方法一：建立矩陣 $A$

由遞迴關係

$$y_{n+1}=y_n+y_{n-1},$$

以及第二個分量

$$y_n=1\cdot y_n+0\cdot y_{n-1},$$

可得

$$\begin{pmatrix} y_{n+1}\\ y_n \end{pmatrix} = \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} \begin{pmatrix} y_n\\ y_{n-1} \end{pmatrix}.$$

因此

$$\boxed{ A= \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} }.$$

初始條件為 $y_0=0$、$y_1=1$，所以

$$v_1= \begin{pmatrix} y_1\\ y_0 \end{pmatrix} = \begin{pmatrix} 1\\ 0 \end{pmatrix}.$$

由矩陣遞迴可得

$$v_n=A^{n-1}v_1.$$

矩陣 $A$ 的對角化

1. 求特徵值

特徵多項式為

$$\det(A-\lambda I) = \det \begin{pmatrix} 1-\lambda&1\\ 1&-\lambda \end{pmatrix}.$$

計算得

$$\det(A-\lambda I) =(1-\lambda)(-\lambda)-1 =\lambda^2-\lambda-1.$$

因此特徵值滿足

$$\lambda^2-\lambda-1=0.$$

由公式解得兩個相異特徵值

$$\lambda_1=\frac{1+\sqrt5}{2}, \qquad \lambda_2=\frac{1-\sqrt5}{2}.$$

記

$$\phi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}.$$

其中

$$\phi-\psi=\sqrt5.$$

2. 求特徵向量

對任一特徵值 $\lambda$，解

$$(A-\lambda I) \begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} 0\\ 0 \end{pmatrix}.$$

第一列給出

$$(1-\lambda)x+y=0,$$

所以

$$y=(\lambda-1)x.$$

由特徵方程 $\lambda^2-\lambda-1=0$ 可知

$$\lambda(\lambda-1)=1,$$

故可取特徵向量為

$$\begin{pmatrix} \lambda\\ 1 \end{pmatrix}.$$

因此對應於 $\phi,\psi$ 的特徵向量分別為

$$u_1= \begin{pmatrix} \phi\\ 1 \end{pmatrix}, \qquad u_2= \begin{pmatrix} \psi\\ 1 \end{pmatrix}.$$

組成矩陣

$$P= \begin{pmatrix} \phi&\psi\\ 1&1 \end{pmatrix}, \qquad D= \begin{pmatrix} \phi&0\\ 0&\psi \end{pmatrix}.$$

因為 $P$ 的兩個欄向量是 $A$ 的特徵向量，所以

$$AP=PD.$$

又因為 $\phi\neq\psi$，矩陣 $P$ 可逆，因此

$$\boxed{ A=PDP^{-1} }.$$

3. 計算 $P^{-1}$

由二階矩陣反矩陣公式，

$$P^{-1} = \frac{1}{\phi-\psi} \begin{pmatrix} 1&-\psi\\ -1&\phi \end{pmatrix}.$$

由 $\phi-\psi=\sqrt5$，得到

本題要求證明，對於給定的向量範數 $\| \cdot \|$ on $\mathbb{C}^n$，由公式定義的矩陣範數 $\||\cdot|\|$ 是一個有效的矩陣範數，並且它與向量範數 $\| \cdot \|$ 是相容的 (compatible)。

定義：

• 向量範數 (Vector Norm): 對於向量空間 $V$ 上的範數 $\| \cdot \|: V \to \mathbb{R}$，它必須滿足以下性質：
  1. 非負性：$\|x\| \ge 0$，且 $\|x\| = 0 \iff x = 0$。
  2. 絕對齊次性：$\|\alpha x\| = |\alpha| \|x\|$ 對於所有純量 $\alpha$ 和向量 $x \in V$。
  3. 三角不等式：$\|x+y\| \le \|x\| + \|y\|$ 對於所有向量 $x, y \in V$。
• 矩陣範數 (Matrix Norm): 對於 $n \times n$ 矩陣空間 $M_n(\mathbb{C})$ 上的範數 $\||\cdot|\|: M_n(\mathbb{C}) \to \mathbb{R}$，它必須滿足以下性質：
  1. 非負性：$\|\|A\|\| \ge 0$，且 $\|A\| = 0 \iff A = 0$。
  2. 絕對齊次性：$\|\| \alpha A \|\| = |\alpha| \|A\|$ 對於所有純量 $\alpha$ 和矩陣 $A$。
  3. 三角不等式：$\|\| A + B \|\| \le \|A\| + \|\|B\|\|$ 對於所有矩陣 $A, B$。
  4. 子乘性 (Submultiplicativity)：$\|\| AB \|\| \le \|A\| \|\|B\|\|$ 對於所有矩陣 $A, B$。
• 相容性 (Compatibility): 一個矩陣範數 $\||\cdot|\|$ 與一個向量範數 $\| \cdot \|$ 是相容的，如果對於所有矩陣 $A$ 和所有向量 $x$， $\|Ax\| \le \|A\| \|x\|$。

給定的矩陣範數定義為：
$\|A\| = \sup_{x \neq 0} \frac{\|Ax\|}{\|x\|}$
這個定義實際上是矩陣範數的一種常見定義方式，稱為誘導範數 (induced norm) 或算子範數 (operator norm)。

證明 $\|A\|$ 是一個矩陣範數：
我們需要驗證 $\|A\|$ 滿足矩陣範數的四個性質：非負性、絕對齊次性、三角不等式和子乘性。

1. 非負性 ($\|A\| \ge 0$ 且 $\|A\| = 0 \iff A = 0$)：

   • 由於 $\|Ax\| \ge 0$ 且 $\|x\| > 0$ (因為 $x \neq 0$)，所以 $\frac{\|Ax\|}{\|x\|} \ge 0$。
   • 因此，其上確界 $\|A\| = \sup_{x \neq 0} \frac{\|Ax\|}{\|x\|} \ge 0$。
   • 若 $\|A\| = 0$，則對於所有 $x \neq 0$， $\frac{\|Ax\|}{\|x\|} = 0$，這意味著 $\|Ax\| = 0$。
   • 由於 $\|Ax\| = 0 \iff Ax = 0$，所以 $\|A\| = 0$ 意味著對於所有 $x \neq 0$， $Ax = 0$。
   • 如果對於所有 $x \neq 0$，$Ax = 0$，則矩陣 $A$ 的所有列向量都必須是零向量 (考慮 $x$ 為標準基向量 $e_i$)。
   • 因此，$A$ 是零矩陣。
   • 反之，若 $A=0$，則對於所有 $x \neq 0$， $Ax = 0$，所以 $\|Ax\| = 0$。因此 $\|A\| = \sup_{x \neq 0} \frac{0}{\|x\|} = 0$。
   • 所以，$\|A\| = 0 \iff A = 0$。

2. 絕對齊次性 ($\|\| \alpha A \|\| = |\alpha| \|A\|$)：
   考慮 $\|\| \alpha A \|\|$：
   $\|\alpha A\| = \sup_{x \neq 0} \frac{\|(\alpha A)x\|}{\|x\|} = \sup_{x \neq 0} \frac{\|\alpha (Ax)\|}{\|x\|}$
   由於 $\| \cdot \|$ 是向量範數， $\|\alpha (Ax)\| = |\alpha| \|Ax\|$。
   $\|\alpha A\| = \sup_{x \neq 0} \frac{|\alpha| \|Ax\|}{\|x\|} = |\alpha| \sup_{x \neq 0} \frac{\|Ax\|}{\|x\|} = |\alpha| \|A\|$
   所以，絕對齊次性成立。

3. 三角不等式 ($\|\| A + B \|\| \le \|A\| + \|\|B\|\|$)：
   考慮 $\|\| A + B \|\|$：
   $\|A+B\| = \sup_{x \neq 0} \frac{\|(A+B)x\|}{\|x\|} = \sup_{x \neq 0} \frac{\|Ax + Bx\|}{\|x\|}$
   由於 $\| \cdot \|$ 是向量範數， $\|Ax + Bx\| \le \|Ax\| + \|Bx\|$。
   $\|A+B\| \le \sup_{x \neq 0} \frac{\|Ax\| + \|Bx\|}{\|x\|} = \sup_{x \neq 0} \left( \frac{\|Ax\|}{\|x\|} + \frac{\|Bx\|}{\|x\|} \right)$
   由於 $x \neq 0$，對於固定的 $x$， $\frac{\|Ax\|}{\|x\|} \le \|A\|$ 且 $\frac{\|Bx\|}{\|x\|} \le \|B\|$。
   但是，這裡我們不能直接將上確界的式子拆開。
   正確的思路是：
   $\|A+B\| = \sup_{x \neq 0} \frac{\|Ax + Bx\|}{\|x\|} \le \sup_{x \neq 0} \frac{\|Ax\| + \|Bx\|}{\|x\|}$
   對於任意 $\epsilon > 0$，存在 $x_0 \neq 0$ 使得 $\|A+B\| \le \frac{\|(A+B)x_0\|}{\|x_0\|} + \epsilon$.
   $\frac{\|(A+B)x_0\|}{\|x_0\|} = \frac{\|Ax_0 + Bx_0\|}{\|x_0\|} \le \frac{\|Ax_0\| + \|Bx_0\|}{\|x_0\|} = \frac{\|Ax_0\|}{\|x_0\|} + \frac{\|Bx_0\|}{\|x_0\|}$.
   由於 $\frac{\|Ax_0\|}{\|x_0\|} \le \|A\|$ 且 $\frac{\|Bx_0\|}{\|x_0\|} \le \|B\|$。
   所以 $\frac{\|(A+B)x_0\|}{\|x_0\|} \le \|A\| + \|B\|$.
   因此 $\|A+B\| \le \|A\| + \|B\|$.
   三角不等式成立。

4. 子乘性 ($\|\| AB \|\| \le \|A\| \|\|B\|\|$)：
   考慮 $\|\| AB \|\|$：
   $\|AB\| = \sup_{x \neq 0} \frac{\|ABx\|}{\|x\|}$
   令 $y = Bx$。則 $x \neq 0 \implies y$ 可能為零。
   $\|ABx\| = \|A(Bx)\|$
   我們知道 $\frac{\|Az\|}{\|z\|} \le \|A\|$ 對於所有 $z \neq 0$。
   令 $z = Bx$. 如果 $Bx \neq 0$，則 $\|A(Bx)\| \le \|A\| \|Bx\|$。