# 薛爾上三角化

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}$

from lingeo import random_int_list, random_good_matrix

## Main idea

Recall that an $n\times n$ matrix $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ is called upper triangular if $a_{ij} = 0$ for all $i > j$.

##### Schur triangulation theorem

Let $A$ be a square complex matrix.
Then there are a unitary matrix $Q$ such that $Q^*AQ = T$ is a upper triangular matrix.

Necessarily, the diagonal entries of $T$ are the eigenvalues of $A$.

Note that if $A$ is a real matrix with complex eigenvalues, then the Schur triangulation theorem still work since $A$ can be viewed as a complex matrix.
However, the decomposition will enforce $Q$ and $T$ to have non-real entries.

##### Schur triangulation theorem (real matrix with real eigenvalues)

Let $A$ be a square real matrix.
Then there are a real orthogonal matrix $Q$ such that $Q\trans AQ = T$ is a upper triangular matrix.

Necessarily, the diagonal entries of $T$ are the eigenvalues of $A$.

##### Schur triangulation theorem (real matrix)

Let $A$ be a square real matrix.
Then there are a real invertible matrix $Q$ such that $Q^{-1}AQ = T$ has the form

$$
T = \begin{bmatrix}
B_1 & ~ & * \\
~ & \ddots & ~ \\
O & ~ & B_t
\end{bmatrix},
$$

such that $B_k = \begin{bmatrix} \lambda_k \end{bmatrix}$ if $\lambda_k\in\mathbb{R}$
and $B_k = \begin{bmatrix} a & b \\ -b & a \end{bmatrix}$ if $\lambda = a + bi$ with $b \neq 0$.

Necessarily, the diagonal blocks of $T$ determine the eigenvalues of $A$.

## Side stories

- cases of real matrices
- properties of unitary/orthogonal matrices

## Experiments

##### Exercise 1

執行以下程式碼。

### code
set_random_seed(0)
print_ans = False

n = 4
eigs = random_int_list(n)
Q = random_good_matrix(n - 1, n - 1, n - 1, 3)
A2 = Q * diagonal_matrix(eigs[1:]) * Q.inverse()
Q2 = identity_matrix(n - 1)
Q2[:,0] = Q[:,0]
T2 = Q2.inverse() * A2 * Q2
A = zero_matrix(n, n)
A[0,0] = eigs[0]
A[0,1:] = vector(random_int_list(n - 1)) 
A[1:,1:] = A2

pretty_print(LatexExpr("Q_2^{-1} A_2 Q_2 ="), Q2.inverse(), A2, Q2, LatexExpr("="), T2)
pretty_print(LatexExpr("A ="), A)

if print_ans:
    Qhat2 = block_diagonal_matrix(matrix([[1]]), Q2)
    T = Qhat2.inverse() * A * Qhat2
    pretty_print(LatexExpr(r"\hat{Q}_2^{-1} A_2 \hat{Q}_2 ="), Qhat2.inverse(), A, Qhat2, LatexExpr("="), T)
    print("eigenvalues of A:", eigs)

當 `seed = 0` 時
$Q_2^{-1}A_2Q_2=\begin{bmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
3 & 0 & 1
\end{bmatrix}\begin{bmatrix}
21 & 42 & -22 \\
-22 & -59 & 34 \\
-18 & -66 & 41
\end{bmatrix}\begin{bmatrix}
1 & 0 & 0 \\
-2 & 1 & 0 \\
-3 & 0 & 1
\end{bmatrix}=\begin{bmatrix}
3 & 42 & -22 \\
0 & 25 & -10 \\
0 & 60& -25 \\
\end{bmatrix}$
$A=\begin{bmatrix}
-4 & -4 & -4 & -3 \\
0 & 21 & 42 &-22 \\
0 & -22 & -59 & 34 \\
0 & -18 & -66 & 41
\end{bmatrix}$

##### Exercise 1(a)

令 $\hat{Q}_2 = 1 \oplus Q_2$。
求 $\hat{Q}_2^{-1} A\hat{Q}_2$。

:::warning

- [x] $\hat{Q}_2$ 和 $\hat{Q}_2^{-1}$ 中間要有標點
:::

$Ans$
得 $\hat{Q}_2 =\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & -2 & 1 & 0 \\
0 & -3 & 0 & 1
\end{bmatrix}，$ $\hat{Q}_2^{-1} =\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 2 & 1 & 0 \\
0 & 3 & 0 & 1
\end{bmatrix}$，
$\hat{Q}_2^{-1} A\hat{Q}_2=\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 2 & 1 & 0 \\
0 & 3 & 0 & 1
\end{bmatrix}\begin{bmatrix}
-4 & 4 & -4 & -3 \\
0 & 21 & 42 & -22 \\
0 & -22 & -59 & 34 \\
0 & -18 & -66 & 41
\end{bmatrix}\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & -2 & 1 & 0 \\
0 & -3 & 0 & 1
\end{bmatrix}=\begin{bmatrix}
-4 & 21 & -4 & -3 \\
0 & 3 & 42 & -22 \\
0 & 0 & 25 & -10 \\
0 & 0 & 60& -25 \\
\end{bmatrix}$。

##### Exercise 1(b)

求 $A$ 的所有特徵值。

:::warning

- [x] 令 $\hat{Q}_3 = 2 \oplus Q_3$，$\hat{Q}_2 = 1 \oplus Q_2$ --> 令 $\hat{Q}_3 = I_2 \oplus Q_3$，$\hat{Q}_2 = I_1 \oplus Q_2$
- [x] 中英數數之間空格
:::

$Ans$
$A_3=\begin{bmatrix}
25 & -10 \\
60 & -25 \\
\end{bmatrix}$，經計算可得 $\spec(A_3)=\{5,-5\}$，取 $\lambda_3=5$
得到 $Q_3^{-1}A_3Q_3=\begin{bmatrix}
1 & 0 \\
-2 & 1
\end{bmatrix}\begin{bmatrix}
25 & -10 \\
60 & -25 \\
\end{bmatrix}\begin{bmatrix}
1 & 0 \\
2 & 1
\end{bmatrix}=\begin{bmatrix}
5 & -10 \\
0 & -5 \\
\end{bmatrix}$。
令 $\hat{Q}_3 = I_2 \oplus Q_3$，$\hat{Q}_2 = I_1 \oplus Q_2$
$Q=\hat{Q}_2\hat{Q}_3$ ，則 $Q^{-1}AQ=\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & -2 & 1
\end{bmatrix}\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 2 & 1 & 0 \\
0 & 3 & 0 & 1
\end{bmatrix}\begin{bmatrix}
-4 & 4 & -4 & -3 \\
0 & 21 & 42 & -22 \\
0 & -22 & -59 & 34 \\
0 & -18 & -66 & 41
\end{bmatrix}\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & -2 & 1 & 0 \\
0 & -3 & 0 & 1
\end{bmatrix}\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 2 & 1
\end{bmatrix}=\begin{bmatrix}
-4 & 21 & -10 & 3 \\
0 & 3 & -2 & -22 \\
0 & 0 & 5 & -10 \\
0 & 0 & 0 & -5 \\
\end{bmatrix}$，
$A$ 的所有特徵值為矩陣$\begin{bmatrix}
-4 & 21 & -10 & 3 \\
0 & 3 & -2 & -22 \\
0 & 0 & 5 & -10 \\
0 & 0 & 0 & -5 \\
\end{bmatrix}$ 對角線的數值，得$\ -4 ,3 ,5 ,-5$。

## Exercises

##### Exercise 2

令

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

求一個實垂直矩陣 $Q$ 使得 $Q\trans AQ$ 為一上三角矩陣。

**[由林柏仰同學提供]**
經計算得知， $\spec(A) = \{1,2,3\}$ 。
取 $\lambda_1 = 1$ ， $\ker(A-I) = \operatorname{span}\left\{\begin{bmatrix} 1 \\ -1 \\ -1 \end{bmatrix}\right\}$ 。
取 $\bv_1 = (1,-1,-1)$ ，將其擴充並正交化後得到矩陣
$$
Q_1 = \begin{bmatrix}
\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{6}} \\
\frac{-1}{\sqrt{3}} & 0 & \frac{-2}{\sqrt{6}} \\
\frac{-1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}}
\end{bmatrix}, \\
{Q_1}^{-1}AQ_1 = \begin{bmatrix}
1 & -\frac{\sqrt{3}}{\sqrt{2}} & \frac{5}{\sqrt{2}} \\
0 & 2 & \frac{3}{\sqrt{3}} \\
0 & 0 & 3
\end{bmatrix}.
$$

運氣很好，此時 ${Q_1}^{-1}AQ_1$ 已是上三角矩陣。
則取
$$
Q = \begin{bmatrix}
\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{6}} \\
\frac{-1}{\sqrt{3}} & 0 & \frac{-2}{\sqrt{6}} \\
\frac{-1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}}
\end{bmatrix}.
$$
可將 $A$ 上三角化。

##### Exercise 3

令 $A$ 為一方陣、
$Q$ 為一可逆矩陣、
而 $T$ 為一上三角矩陣。

已知 $Q^{-1}AQ = T$，
證明 $\spec(A) = \spec(T)$ 且它們就是 $T$ 的對角線元素所成的集合。

:::warning

- [x] 題目已經說 $Q^{-1}AQ = T$ 了所以前兩行是多餘的
- [x] 這裡解釋了 $T$ 的對角線元素就是 $\spec(T)$，可是沒有解釋為什麼 $\spec(A) = \spec(T)$
:::

$Ans:$

由上可知，$T$ 為 $A$ 的基底轉換，所以 $\spec(A) = \spec(T)$ 。

因為 $T$ 為上三角矩陣，所以 $p_T(x)=(x-\lambda_1)\dots(x-\lambda_1)$，也就是 $p_A(x)$ 的因式分解。

因此 $T$ 的對角線元素所成的集合等於 $\spec(T) = \spec(A)$。

##### Exercise 4

若 $P$ 和 $Q$ 為大小相同的么正矩陣，證明 $PQ$ 和 $QP$ 都是么正矩陣。
若 $P$ 和 $Q$ 為大小相同的實垂直矩陣，證明 $PQ$ 和 $QP$ 都是實垂直矩陣。

:::warning

- [x] $^T$ --> $\trans$
:::

$Ans:$

(1)
設 $P$ 和 $Q$ 皆為 $n\times n$ 的方陣，而且因為 $P$ 和 $Q$ 皆為么正矩陣，所以可以得到:
$P\times P^* = I_n$ 和 $Q\times Q^* = I_n$.
$PQ\times (PQ)^* = PQQ^*P^* = P\times I_n\times P^* = PP^* = I_n$.
$QP\times (QP)^* = QPP^*Q^* = Q\times I_n\times Q^* = QQ^* = I_n$.
故 $PQ$ 和 $QP$ 都是么正矩陣。

(2)
設 $P$ 和 $Q$ 皆為 $n\times n$ 的方陣，而且因為 $P$ 和 $Q$ 皆為實垂直矩陣，所以可以得到:
$P\trans = P^{-1}$ 和 $Q\trans = Q^{-1}$.
$(PQ)\trans = Q\trans(P\trans) = Q^{-1}P^{-1} = (PQ)^{-1}$.
$(QP)\trans = P\trans(Q\trans) = P^{-1}Q^{-1} = (QP)^{-1}$.
故 $PQ$ 和 $QP$ 都是實垂直矩陣。

##### Exercise 5

證明一般版本的薛爾上三角化定理：

##### Schur triangulation theorem

Let $A$ be a square complex matrix.
Then there are a unitary matrix $Q$ such that $Q^*AQ = T$ is a upper triangular matrix.

Necessarily, the diagonal entries of $T$ are the eigenvalues of $A$.

**[由林柏仰同學提供]**
令 $\lambda_1$ 為 $\spec(A)$ 中的一個元素，且 $\bv_1$ 為一長度為 $1$ 的對應到 $\lambda_1$ 的特徵向量。
令 $Q_1$ 為用 $\bv_1$ 擴張出來的么正矩陣。
則 $Q_1$ 可以對 $A$ 做到一部分的三角化，即
$$
Q_1^*AQ_1 = \begin{bmatrix}
\lambda_1 & ? \\
O & A_2
\end{bmatrix}.
$$

若再令 $\lambda_2$ 為 $\spec(A_2)$ 中的一個元素。
並以同樣方法得出么正矩陣 $Q_2$ ，將 $Q_2$ 擴張成 $Q_2'$ ，且
$$
Q_2' = \begin{bmatrix}
I & O \\
O & Q_2
\end{bmatrix}.
$$
則 $Q_2'$ 會滿足

1. $Q_2'^* = Q_2'$ ，$Q_2'$ 為一么正矩陣。
2. $Q_2'$ 不會影響到 $Q_1^*AQ_1$ 中已被三角化的部分，且可對其未被三角化的部分進行一部份的三角化。

則可重複上述動作，直到將 $A$ 三角化。
且 $Q = Q_1Q_2'...Q_n'$ 為一么正矩陣。

##### Exercise 6

證明所有特徵值皆為實數的實矩陣版本的薛爾上三角化定理：

##### Schur triangulation theorem (real matrix with real eigenvalues)

Let $A$ be a square real matrix.
Then there are a real orthogonal matrix $Q$ such that $Q\trans AQ = T$ is a upper triangular matrix.

Necessarily, the diagonal entries of $T$ are the eigenvalues of $A$.

:::warning

- [x] 向量用粗體
- [x] $Q_2$ 左上角是 $1$ 不是 $\lambda_1$
- [x] 標點
- [x] 中英數之間空格
:::

$Ans:$
令 $A$ 的第一個特徵值為 $\lambda_1$，則至少存在一個對應的單位特徵向量 $\bx_1$，$\Vert$$\bx_1$$\Vert$$=1$，將 $n$ 維向量 $\bx_1$ 置於矩陣 $Q_1$ 的第一行，再將 $\bx_1$ 擴充成 $\mathbb{R}^{n}$ 的基底並正交化後得到么正矩陣 $Q_1$ 的另外 $(n-1)$ 個單位向量。
$$
Q_1= \begin{bmatrix}
| & |&~ & | \\
{\bf x}_1 & *&\cdots & * \\
| & |&~ & |
\end{bmatrix}
$$
由特徵方程式 $A \bx_1=\lambda_1 \bx_1$ 可知
$AQ_1=A \begin{bmatrix}
| & |&~ & | \\
{\bf x}_1 & *&\cdots & * \\
| & |&~ & |
\end{bmatrix}
= \begin{bmatrix}
| & |&~ & | \\
{\lambda_1\bf x}_1 & *&\cdots & * \\
| & |&~ & |
\end{bmatrix}
=Q_1 \begin{bmatrix}
\lambda_1 & ?&\dots & ? \\
0 & *&\cdots & * \\
\vdots & |&~ & |
\end{bmatrix}$
或寫為
$Q_1^{-1}AQ_1= \begin{bmatrix}
\lambda_1 & ?&\dots & ? \\
0 & *&\dots & * \\
\vdots & |&~ & |
\end{bmatrix}=T_1.$
第二個步驟僅需考慮 $T_1$ 矩陣右下標為 $*$ 的 $(n-1)×(n-1)$ 階分塊，令此分塊的一個特徵值為 $\lambda_2$，正規化後的 $(n-1)$ 維特徵向量以 $\bx_2$ 表示， $\Vert$$\bx_2$$\Vert$$=1$ 。
如前一步驟做法，將 $(n-1)$ 維向量 $\bx_2$ 置於矩陣 $Q_2$ 的第一行，其餘的 $(n-2)$ 行由 $\bx_2$ 擴充並正交化後確定 。
$$
Q_2= \begin{bmatrix}
1 & 0&\dots & 0 \\
0 & | & * & * \\
\vdots & x_2 & |\ & | \\
0 & | & * & *
\end{bmatrix}
$$
由特徵方程式 $T_1Q_2 =
Q_2 \begin{bmatrix}
\lambda_1 & ?&~&\cdots & ? \\
0 & \lambda_2&?&\cdots & ? \\
\vdots &0 &*&\cdots & * \\
0 & \vdots &*&\cdots & * \\
\end{bmatrix}$

或寫為 $Q_2^{-1}T_1Q_2=\begin{bmatrix}
\lambda_1 & ?&~&\cdots & ? \\
0 & \lambda_2&?&\cdots & ? \\
\vdots &0 &*&\cdots & * \\
0 & \vdots &*&\cdots & * \\
\end{bmatrix}$
以此類推，經過 $n$ 次步驟後，可以得到一個上三角矩陣 $T$ ，整個計算式為
$Q_n^{-1}Q_{n-1}^{-1}Q_{n-2}^{-1}\cdots Q_1^{-1}AQ_1
\cdots Q_{n-2}Q_{n-1}Q_n=T$ 。

其中么正矩陣乘積 $Q=Q_1\cdots Q_n$ 仍然是么正矩陣，
因為 $(Q_1\cdots Q_n)^{-1}=Q_n^{-1}\cdots Q_1^{-1}=Q_n^{\trans}\cdots Q_1^{\trans}=(Q_1\cdots Q_n)^{\trans}$
得證 $Q^{\trans}AQ=T$。

:::success
除了細節和格式外都很棒 :thumbsup:
:::

##### Exercise 7

證明一般實矩陣版本的薛爾上三角化定理：

##### Schur triangulation theorem (real matrix)

Let $A$ be a square real matrix.
Then there are a real invertible matrix $Q$ such that $Q^{-1}AQ = T$ has the form

$$
T = \begin{bmatrix}
B_1 & ~ & * \\
~ & \ddots & ~ \\
O & ~ & B_t
\end{bmatrix},
$$

such that $B_k = \begin{bmatrix} \lambda_k \end{bmatrix}$ if $\lambda_k\in\mathbb{R}$
and $B_k = \begin{bmatrix} a & b \\ -b & a \end{bmatrix}$ if $\lambda = a + bi$ with $b \neq 0$.

Necessarily, the diagonal blocks of $T$ determine the eigenvalues of $A$.

**[由林柏仰同學提供]**
假設 $\spec(A)$ 為一複數集合。
觀察 $\spec(A)$ 中的元素 $\lambda_1$ 為實數的情況。
令向量 $\bv_1$ 滿足 $A\bv_1 = \lambda_1\bv_1$ 。
則可用 $\bv_1$ 擴張出可逆矩陣 $Q_1$ ，使得
$$
{Q_1}^{-1}AQ_1 = \begin{bmatrix}
\lambda & ? \\
O & A_2
\end{bmatrix}.
$$

觀察 $\spec(A)$ 中的元素 $\lambda_1$ 為複數的情況。
令 $\lambda_1 = a + bi$ ， $a,\ b$ 為實數。
再令向量 $\bv_1 = \bx + \by i$ 滿足 $A\bv_1 = \lambda_1\bv_1$ ，且 $\bx,\ \by$ 為實數向量。
則 $A\bx + A\by i = (a\bx + b\by) + (b\bx + a\by)i$ 。
則可知
$$
\left\{
\begin{array}{}
A\bx = a\bx - b\by,\\
A\by = b\bx - a\by.
\end{array}
\right.
$$
令
$$
Q_1 = \begin{bmatrix}
| & | & ~ \\
\bx & \by & \ldots \\
| & | & ~
\end{bmatrix}.
$$
且 $Q_1$ 為一可逆矩陣。
則
$$
{Q_1}^{-1}AQ_1 = \begin{bmatrix}
a & b & ? \\
-b & a & ? \\
O & O & A_2
\end{bmatrix}.
$$

此時可知，無論 $\lambda$ 為實數或複數，皆可以做到一部分的三角化。

再觀察 $A_2$ 。
可重複上述動作得到一可逆矩陣 $Q_2$ ，且 $Q_2$ 可對 $A_2$ 做到一部分的三角化。
將 $Q_2$ 擴張成 $n\times n$ 矩陣 ${Q_2}'$ ，且
$$
{Q_2}' = \begin{bmatrix}
I & O \\
O & Q_2
\end{bmatrix}.
$$
觀察 ${{Q_2}'}^{-1}\ {Q_1}^{-1}AQ_1\ {Q_2}'$ 。
可以發現 ${Q_2}'$ 不會影響到已被三角化的部分，且對於未被三角化的部分也可以做到一部份的三角化。
換句話說，我們可以重複以上動作直到得出一個三角矩陣 $T$ 。

:::info
分數 = 6
:::