線性代數筆記

Linear Algebra

Contents

• TASHOUN（她笑）
• Spectral Decomposition
• Equivalent Conditions of an Invertible Matrix
• Consistency of Ax=b
• A Motivation of Adjoint Operators
• A Motivation of Normal Operators
• Transpose, Trace, Determinant, Rank, Inverse
• A Geometric Interpretation of Determinant
• Properties of the Determinant
• 遞迴方程式的線性代數觀點recurrence relation (linear algebra aspect)
• Diamond
• The Importance of Strang's Big Picture
• Jordan Canonical Form

---

TASHOUN（她笑）

		real	complex
		transpose $A^t$	adjoint $A^*$
orthogonally diagonalizable	spectral theorem $\Leftrightarrow$	symmetric $A^t=A$	Hermitian (self-adjoint) $A^*=A$	$\Rightarrow$	unitarily diagonalizable	spectral theorem $\Leftrightarrow$	normal
		orthogonal $A^tA=I$	unitary $A^* A=I$

注意到上面這張圖，美中不足的地方在於Hermitian並不是unitarily diagonalizable的等價條件，讓這張圖並沒有呈現完美的對稱。

Spectral Decomposition

Let $$\begin{array}{lll} A &=& PDP^t \\ &=& (\mathbf{u}_1|\mathbf{u}_2|\cdots |\mathbf{u}_n)\begin{pmatrix}\lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{pmatrix}\begin{pmatrix}\mathbf{u}_1^t \\ \mathbf{u}_2^t \\ \vdots \\ \mathbf{u}_n^t \end{pmatrix} \\ &=& \lambda_1 \mathbf{u}_1 \mathbf{u}_1^t+\lambda_2 \mathbf{u}_2\mathbf{u}_2^t+\cdots +\lambda_n \mathbf{u}_n \mathbf{u}_n^t \\ \end{array}$$ be the orthogonal diagonalization of $A$. For any $\mathbf{v}$, $$\begin{array}{lll} \mathbf{u}_i\mathbf{u}_i^t\mathbf{v} &=& (\mathbf{u}_i^t \mathbf{v})\mathbf{u}_i \\ &=& \langle \mathbf{u}_i, \mathbf{v}\rangle \mathbf{u}_i \\ &=& \langle \mathbf{v}, \mathbf{u}_i\rangle \mathbf{u}_i \\ &=& \frac{\langle \mathbf{v}, \mathbf{u}_i\rangle}{||\mathbf{u}_i||^2}\mathbf{u}_i \\ &=& \text{proj}_{\text{span}(\mathbf{u}_i)}\mathbf{v} \\ &=& \text{the orthogonal projection of }\mathbf{v}\text{ on the subspace }\text{span}(\mathbf{u}_i)\leq E_{\lambda_i} \end{array}$$

Equivalent Conditions of an Invertible Matrix

See Anton's Theorem 6.4.5 in Elementary Linear Algebra.

If $A$ is an $n\times n$ matrix, then the following statements are equivalent.

1. $A$ is invertible.
2. $A\mathbf{x}=\mathbf{0}$ has only the trivial solution.
3. The reduced row echelon form of $A$ is $I_n$.
4. $A$ is expressible as a product of elementary matrices.
5. $A\mathbf{x}=\mathbf{b}$ is consistent for every $n\times 1$ matrix $\mathbf{b}$.
6. $A\mathbf{x}=\mathbf{b}$ has exactly one solution for every $n\times 1$ matrix $\mathbf{b}$.
7. $\det{(A)}\neq 0$.
8. The column vectors of $A$ are linearly independent .
9. The row vectors of $A$ are linearly indenpendent.
10. The column vectors of $A$ span $\mathbb{R}^n$.
11. The row vectors of $A$ span $\mathbb{R}^n$.
12. The column vectors of $A$ form a basis for $\mathbb{R}^n$.
13. The row vectors of $A$ form a basis for $\mathbb{R}^n$.
14. $A$ has rank $n$.
15. $A$ has nullity $0$.
16. The orthogonal complement of the null space of $A$ is $\mathbb{R}^n$.
17. The orthogonal complement of the row space of $A$ is $\{\mathbf{0}\}$.
18. The kernel of $T_A$ is $\{\mathbf{0}\}$.
19. The range of $T_A$ is $\mathbb{R}^n$.
20. $T_A$ is one-to-one.
21. $\lambda=0$ is not an eigenvalue of $A$.
22. $A^T A$ is invertible.

上面這個列表不太好用，因為一般來說不一定有 $m=n$，所以我個人比較喜歡用下面的等價關係。下面 $A$ 為一 $m\times n$ 的矩陣。點擊箭頭可以看到證理由。

線性變換的觀點		向量空間的觀點				維度的觀點		向量的觀點
								columns are linearly independent
							⇗rank = the number of linearly independent columns ⇙rank = the number of linearly independent columns
$A:F^n\to F^m$ is one-to-one	⇔Theorem 8.2.1	kernel A = 0	⇔Definition	nullity A= 0	⇔Dimension Theorem	rank A = n
							⇘rank A^T = n <=> A^T columns span F^n ⇖rank A^T = n <=> A^T columns span F^n
								rows span F^n
								rows are linearly independent
							⇗rank = the number of linearly independent rows ⇙rank = the number of linearly independent rows
$A:F^n\to F^m$ is onto	⇔Definition	image A = F^m		⇔rank = dimension of image		rank A = m
							⇘column space = image A ⇖column space = image A
								columns span F^m

Consistency of $A\mathbf{x}=\mathbf{b}$

• $\text{rank}(A)\neq \text{rank}(A|\mathbf{b})\Leftrightarrow A\mathbf{x}=\mathbf{b}$ has no solutions
• $\text{rank}(A)=\text{rank}(A|\mathbf{b})=n\Leftrightarrow A\mathbf{x}=\mathbf{b}$ has exactly one solution
• $\text{rank}(A)=\text{rank}(A|\mathbf{b})< n\Leftrightarrow A\mathbf{x}=\mathbf{b}$ has infinitely many solutions

上面這三個敘述可以利用上面的one-to-one及onto的等價敘述得到。另外，$A\mathbf{x}=\mathbf{b}$ 的解只有三種可能，無解、恰有一組解、無線多組解。證明如下：假設 $\mathbf{x}_1, \mathbf{x}_2$ 為相異兩組解，則 $\mathbf{x}_1+c(\mathbf{x}_1-\mathbf{x}_2)$ 皆為解，其中 $c$ 為任意實數。

注意到，例如空間中的三個平面，既使判斷方程式是無解、無限多組解還是唯一解之後，仍然要再更進一步探討（可以利用法向量）三個平面的相交情況。（平面相交的圖形來自於Anton的書）

A Motivation of Adjoint Operators

Click Me!

A Motivation of Normal Operators

Click Me!

Transpose, Trace, Determinant, Rank, Inverse

	transpose	trace	det	rank	inverse
$cA$	$(cA)^t=cA^t$ by def.	$\text{tr }cA=c\cdot \text{tr }A$ by def.	$\det{cA}=c^n \det{A}$ by def.	$\text{rank }cA=\text{rank }A$, $c\neq 0$	$(cA)^{-1}=c^{-1}A^{-1}$, $c\neq 0$ by def.
$A+B$	$(A+B)^t=A^t+B^t$ by def.	$\text{tr }(A+B)=\text{tr }A+\text{tr }B$ by def.		$\text{rank }(A+B)\leq \text{rank }A+\text{rank }B$
$AB$	$(AB)^t=B^t A^t$ by def.	$\text{tr }AB=\color{red}{\text{tr }BA}$ by def.	$\det{AB}=\det{A}\cdot \det{B}$ difficult	$\text{rank }AB\leq \min{\{\text{rank }A, \text{rank }B\}}$	$(AB)^{-1}=B^{-1}A^{-1}$ by def.
$A^t$	$(A^t)^t=A$ by def.	$\text{tr }A^t=\text{tr }A$ by def.	$\det{A^t}=\det{A}$ by def.	$\text{rank }A^t=\text{rank }A$ difficult	$(A^t)^{-1}=(A^{-1})^t$

A Geometric Interpretation of Determinant

參考這裡，動畫版參考這裡。另一個比較常見的證法是這個，還有一個比較少見的證法，不過我覺得後面兩個都比不上第一個簡單。

Properties of the Determinant

See Friedberg's Linear Algebra

1. If $B$ is a matrix obtained by interchanging any two rows or interchanging any two columns of an $n\times n$ matrix $A$, then $\det{B} = −\det{A}$. (Proof: By the definition.)
2. If $B$ is a matrix obtained by multiplying each entry of some row or column of an $n\times n$ matrix $A$ by a scalar $k$, then $\det{B} = k\cdot \det{A}$. (Proof: By the definition.)
3. If $B$ is a matrix obtained from an $n\times n$ matrix $A$ by adding a multiple of row $i$ to row $j$ or a multiple of column $i$ to column $j$ for $i\neq j$, then $\det{B} = \det{A}$. (Proof: Waiting for proving.)
4. The determinant of an upper triangular matrix is the product of its diagonal entries. In particular, $\det{I} = 1$. (Proof: By the definition.)
5. If two rows (or columns) of a matrix are identical, then the determinant of the matrix is zero. (Proof: By 3 and 10.)
6. For any $n\times n$ matrices $A$ and $B$, $\det{AB}=\det{A}\cdot \det{B}$. (Proof: It is difficult to prove.)
7. An $n\times n$ matrix $A$ is invertible if and only if $\det{A}\neq 0$. Furthermore, if $A$ is invertible, then $\det{A^{-1}}=\frac{1}{\det{A}}$. (Proof: By 4 and 6.)
8. For any $n\times n$ matrix $A$, the determinants of $A$ and $A^t$ are equal. (Proof: By the definition.)
9. If $A$ and $B$ are similar matrices, then $\det{A}=\det{B}$. (Proof: By 6 and 7.)
10. If $A$ has a $0$ row or a $0$ column, then $\det{A}=0$. (Proof: By the definition.)
11. If $i$th row equals a multiple of $j$th row, then $\det{A}=0$. (Proof: 3 and 10.)
12. $\det{A}$ is row linear. (Proof: Waiting for proving.)

遞迴方程式的線性代數觀點recurrence relation (linear algebra aspect)

Click Me!

我們大學時（甚至是高中），即學過遞迴方程式（recurrence relation），例如 $a_{n+2}=5a_{n+1}-6a_n$，其中 $n$ 為大於等於 $1$ 的正整數，一般書上教我們的解法是，先求出此遞迴方程式的特徵方程式（characteristic equation） $r^2=5r-6$，並求出此特徵方程式的根為 $r=2$ 或是 $r=3$，則此遞迴方程式的解為 $a_n=c_1\cdot 2^n+c_2\cdot 3^n.$

又例如遞迴方程式 $a_{n+2}=4a_{n+1}-4a_n.$，此遞迴方程式的特徵方程式為 $r^2=4r-4$，有重根 $r=2$，這時候我們要調整遞迴方程式的解為 $a_n=c_1\cdot 2^n+c_2\cdot n\cdot 2^n$，學生到這裡可能會有三個問題。

1. 特徵方程式是我們在線性代數中學習到的觀念，遞迴方程式是否跟向量空間(vector space)、線性變換（linear transformation）有關係，為何在解遞迴方程式時會用到特徵方程式？
2. 我們何以知道當特徵方程式有重根時，其遞迴方程式的解要做如此的調整？
3. 一般書上都是給出遞迴方程式的解，然後用代入驗證的方法證明，然而，相信數學家們不是一開始研究遞迴方程式時就知道其解的形式，數學家們當初是如何知道遞迴方程式的解的形式呢？

本文的目的在回答這三個問題。

Diamond

		Singular Value Decomposition	→	Pseudoinverse
	↗				↘
↗						↘
Gram-Schmidt Process	←	←	Orthogonal Projection	→	→	Least Square Problem
↘			↓			↗
		↘	Householder Reflection	↗
		↘	↓	↗
			QR-decomposition

The Importance of Strang's Big Picture

Click Me!

Jordan Canonical Form

我個人偏好的Jordan Form的證明。