薛爾上三角化

# 薛爾上三角化 Schur triangulation ![Creative Commons License](https://i.creativecommons.org/l/by/4.0/88x31.png) 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}} \newcommand{\mult}{\operatorname{mult}} \newcommand{\iner}{\operatorname{iner}}$ ```python 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 is 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 with all eigenvalues real. Then there is 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 is 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_k = 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 執行以下程式碼。  Run the code below.  ```python ### 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) ``` By running the code above with `seed = 0`, we obtain that $Q_2^{-1} A_2 Q_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$。  Let $\hat{Q}_2 = 1 \oplus Q_2$. Find $\hat{Q}_2^{-1} A\hat{Q}_2$.  ##### **Answer:** $\hat{Q}_2=\begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & -2 & 1 & 0\\ 0 & -3 & 0 & 1\end{bmatrix},$ and $\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} -4 & 21 & -4 & -3 \\ 0 & 3 & 42 & -22 \\ 0 & 0 & 25 & -10 \\ 0 & 0 & 60 & -25\end{bmatrix}.$ --- ##### Exercise 1(b) 求 $A$ 的所有特徵值。  Find the spectrum of $A$.  ##### **Answer:** $A_3=\begin{bmatrix} 25 & -10\\ 60 & -25\end{bmatrix}, \spec(A_3)=\{5, -5\},$ and $\lambda_3=5.$ And $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}.$ Let $\hat{Q}_3=I_2\oplus Q_3,$ $\hat{Q}_2=I_1\oplus Q_2.$ And $Q=\hat{Q}_2\hat{Q}_3.$ Then rewrite $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}.$ Since it is an upper triangular matrix, the eigenvalues of $A$ is the value of diagonal. So $\spec(A)=\{-4, 3, 5, -5\}.$ --- :::info What do the experiments try to tell you? (open answer) ##### **Answer:** Tell us how to use the above process to get the upper triangular matrix, and get the eigenvalue by its values of diagonal. ... ::: --- ## Exercises ##### Exercise 2 令 $$ A = \begin{bmatrix} -1 & -4 & 2 \\ 2 & 4 & -1 \\ 0 & -2 & 3 \end{bmatrix}. $$ 求一個實垂直矩陣 $Q$ 使得 $Q\trans AQ$ 為一上三角矩陣。  Let $$ A = \begin{bmatrix} -1 & -4 & 2 \\ 2 & 4 & -1 \\ 0 & -2 & 3 \end{bmatrix}. $$ Find a real orthogonal matrix $Q$ such that $Q\trans AQ$ is an upper triangular matrix.  ##### **Answer:** $\spec(A)=\{1, 2, 3\}.$ Let $\lambda_1=1,$ and $\ker(A-I)=\operatorname{span}\{\begin{bmatrix}1\\-1\\-1\end{bmatrix}\}.$ Let $V_1=\begin{bmatrix}1\\-1\\-1\end{bmatrix}.$ And expand it to basis $\begin{bmatrix} 1 & 1 & 2\\ -1 & 1 & 1\\ -1 & 0 & 1\end{bmatrix}.$ Since it need to be a orthogonal matrix, it should be $Q=\begin{bmatrix} \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{2}{\sqrt{6}}\\ \frac{-1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}}\\ \frac{-1}{\sqrt{3}} & 0 & \frac{1}{\sqrt{6}}\end{bmatrix}.$ Then $Q^TAQ=\begin{bmatrix} \frac{7}{\sqrt{3}} & \frac{1}{\sqrt{3}} & 0 \\ 0 & 6 & 0 \\ 0 & 0 & \frac{3}{2} \end{bmatrix}.$ Thus it is a upper triangular matrix. --- ##### Exercise 3 令 $A$ 為一方陣、 $Q$ 為一可逆矩陣、而 $D$ 為一上三角矩陣。已知 $Q^{-1}AQ = D$，證明 $\spec(A) = \spec(D)$ 且它們就是 $D$ 的對角線元素所成的集合。  Let $A$ be a square matrix, $Q$ an invertible matrix, and $D$ an upper triangular matrix. It is known that $Q^{-1}AQ = D$. Show that $\spec(A) = \spec(D)$ and they equal the set of diagonal entries of $D$.  ##### **Answer:** 1. **Claim: $\spec(A) = \spec(D)$** By the equation $Q^{-1}AQ = D$, we know that $A$ and $D$ are similar (see 506). Therefore, $p_A(x) = p_D(x)$ and $\spec(A) = \spec(D)$. 2. **Claim: $\spec(D)$ is the set of diagonal entries of $D$.** $D$ is an upper triangular matrix with the form of $$ D = \begin{bmatrix} \lambda_1 & ~ & * \\ ~ & \ddots & ~ \\ O & ~ & \lambda_n \end{bmatrix}. $$ Since $$ D-xI = \begin{bmatrix} \lambda_1-x & ~ & * \\ ~ & \ddots & ~ \\ O & ~ & \lambda_n-x \end{bmatrix}, $$ we get $$p_D(x)=\det(D-xI)=(\lambda_1-x)(\lambda_2-x)...(\lambda_n-x).$$ We can see that $\spec(D)=\{ \lambda_1, \lambda_2, ..., \lambda_n \}$, which is the set of diagonal entries of $D$. ##### Exercise 4 若 $P$ 和 $Q$ 為大小相同的么正矩陣，證明 $PQ$ 和 $QP$ 都是么正矩陣。若 $P$ 和 $Q$ 為大小相同的實垂直矩陣，證明 $PQ$ 和 $QP$ 都是實垂直矩陣。  If $P$ and $Q$ are unitary matrices of the same order, show that $PQ$ and $QP$ are both unitary. If $P$ and $Q$ are real orthogonal matrices of the same order, show that $PQ$ and $QP$ are both real orthogonal.  ##### **Answer:** (1)Because $P$ and $Q$ are unitary matrices of the same order,we know $P\times P^* = I_n$ and $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$. So $PQ$ and $QP$ are both unitary. (2)Because $P$ and $Q$ are real orthogonal matrices of the same order,we know $P\trans = P^{-1}$ and $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}$. So $PQ$ and $QP$ are both real orthogonal. ##### 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$.  Prove the Schur triangulation theorem. ##### 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$.  **Solution:** Let $\lambda_1$ be a element of $\spec(A)$, and $\bv_1$ be a unit vector and eigenvector that corresponds to $\lambda_1$. Assume $Q_1$ is a unitary matrix made up by the $\bv_1$. Then we can use $Q_1$ to triangular part of A, that is $$ Q_1^*AQ_1 = \begin{bmatrix} \lambda_1 & ? \\ O & A_2 \end{bmatrix}. $$ And we let $\lambda_2$ be a element of $\spec(A_2)$, use the same method to get the unitary matrix $Q_2$. We expand $Q_2$ to $Q^{\prime}_2$, and $$ Q_2' = \begin{bmatrix} I & O \\ O & Q_2 \end{bmatrix}. $$ Repeat operation above until we triangular $A$. Then $Q=Q_1Q^{\prime}_2...Q^{\prime}_n$ is a unitary matrix. ##### 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$.  Prove the Schur triangulation theorem for real matrices with real eigenvalues. ##### 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$.  ##### 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$.  Prove the Schur triangulation theorem for real matrices. ##### 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$.  :::info collaboration: 1 4 problems: 4 - 2, 3, 4, 5 :warning: Missing one problem from Ken. :tired_face: I finished. by Ken moderator: 0 :sob: qc: 1 :::

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.