Introdunction to Linear Algebra-第6章-Eigenvalues and Eigenvectors

[TOC]
《Introdunction to Linear Algebra》的第 6 章: Eigenvalues and Eigenvectors.

6.1 Introduction to Eigenvalues

本节概要

1. An eigenvector $\boldsymbol{x}$ lies along the same line as $A \boldsymbol{x}: A \boldsymbol{x}=\lambda \boldsymbol{x}$ . The eigenvalue is $\boldsymbol{\lambda}$.
2. If $A \boldsymbol{x}=\lambda \boldsymbol{x}$ then $A^{2} \boldsymbol{x}=\lambda^{2} \boldsymbol{x}$ and $A^{-1} \boldsymbol{x}=\lambda^{-1} \boldsymbol{x}$ and $(A+c I) \boldsymbol{x}=(\lambda+c) \boldsymbol{x}$: the same $\boldsymbol{x}$.
3. If $A \boldsymbol{x}=\lambda \boldsymbol{x}$ then $(A-\lambda I) \boldsymbol{x}=0$ and $A-\lambda I$ is singular and $\operatorname{det}(A-\lambda I)=0$.
4. Check $\lambda$ ‘s by $\text{det} A=\left(\lambda_{1}\right)\left(\lambda_{2}\right) \cdots\left(\lambda_{n}\right)$ and diagonal sum $a_{11}+a_{22}+\cdots+a_{n n}$= sum of $\lambda$’s.
5. Projections have $\lambda=1$ and $0$. Reflections have $1$ and $-1$. Rotations have $e^{i \theta}$ and $e^{-i \theta}$: complex!

本征值与本征向量的引入

从本章开始拓展研究对象, 静态的 $A \boldsymbol{x} = \boldsymbol{b}$ 到动态的(随时间变化的) $d \boldsymbol{u}/dt = \boldsymbol{u}$ 或者 $\boldsymbol{u}_{k+1}=A\boldsymbol{u}_k$. 这时不能再使用消元法了. 为了简化复杂度, 我们希望找到一个向量 $\boldsymbol{x}$, 对于 $A$, 与之相乘也不会改变其方向, 这样我们就可以只算固定方向上的标量集 $\lambda$.

一般向量乘以 $A$, 其方向都会变化, 但是 Certain exceptional vectors $\boldsymbol{x}$ are in the same direction as $A \boldsymbol{x}$. Those are the eigenvectors. Multiply an eigenvector by $A$, and the vector $A \boldsymbol{x}$ is a number $\lambda$ times the original $\boldsymbol{x}$. The basic equation is $A \boldsymbol{x}= \lambda \boldsymbol{x}$. The number $\lambda$ is an eigenvalue of $A$.

The eigenvalue $\lambda$ tells whether the special vector $\boldsymbol{x}$ is stretched or shrunk or reversed or left unchanged, when it is multiplied by $A$.

$A \boldsymbol{x} = 0 \boldsymbol{x}$ means that this eigenvector $\boldsymbol{x}$ is in the nullspace.
如果 $A=I$, 则 $A \boldsymbol{x}= \boldsymbol{x}$.

如何求解?

思路:

Eigenvalues: The number $\lambda$ is an eigenvalue of $A$ if and only if $A-\lambda I$ is singular.
Equation for the eigenvalues: $\operatorname{det}(A-\lambda I)=0 .$

具体步骤:

1. Compute the determinant of $A-\lambda I$. With $\lambda$ subtracted along the diagonal, this determinant starts with $\lambda^{n}$ or $-\lambda^{n}$. It is a polynomial in $\lambda$ of degree $n$.
2. Find the roots of this polynomial, by solving $\operatorname{det}(A-\lambda I)=0$. The $n$ roots are the $n$ eigenvalues of $A$. They make $A-\lambda I$ singular.
3. For each eigenvalue $\lambda$, solve $(A-\lambda I) \boldsymbol{x}=0$ to find an eigenvector $\boldsymbol{x}$.

例子:

$$ A=\left[\begin{array}{ll} .8 & .3 \\\\ .2 & .7 \end{array}\right] \quad \operatorname{det}\left[\begin{array}{ll} .8-\lambda & .3 \\\\ .2 & .7-\lambda \end{array}\right]=\lambda^{2}-\frac{3}{2} \lambda+\frac{1}{2}=(\lambda-1)\left(\lambda-\frac{1}{2}\right) $$ $(A-I) \boldsymbol{x}_{1}=0$ is $A \boldsymbol{x}_{1}=\boldsymbol{x}_{1}$ and the first eigenvector is $(. 6, . 4)$. $\left(A-\frac{1}{2} I\right) \boldsymbol{\boldsymbol{x}}_{2}=0$ is $A \boldsymbol{x}_{2}=\frac{1}{2} \boldsymbol{x}_{2}$ and the second eigenvector is $ (1,1)$ : $\boldsymbol{x}_{1}=\left[\begin{array}{l}.6 \\\\ .4\end{array}\right] \quad$ and $\quad A \boldsymbol{x}_{1}=\left[\begin{array}{ll}.8 & .3 \\\\ .2 & .7\end{array}\right]\left[\begin{array}{l}.6 \\\\ .4\end{array}\right]=\boldsymbol{x}_{1} \quad\left(A \boldsymbol{x}=\boldsymbol{x}\right.$ means that $\left.\lambda_{1}=1\right)$ $\boldsymbol{x}_{2}=\left[\begin{array}{r}1 \\\\ -1\end{array}\right]$ and $A \boldsymbol{x}_{2}=\left[\begin{array}{ll}.8 & .3 \\\\ .2 & .7\end{array}\right]\left[\begin{array}{r}1 \\\\ -1\end{array}\right]=\left[\begin{array}{r}.5 \\\\ -.5\end{array}\right]$ (this is $\frac{1}{2} \boldsymbol{x}_{2}$ so $\lambda_{2}=\frac{1}{2}$ ).

基础性质:

1. 本征值为 0, 并没有什么特殊意义, 只在于常规的零空间解释. If $A$ is singular, the eigenvectors for $\lambda = 0$ fill the nullspace: $A \boldsymbol{x} = 0 \boldsymbol{x} = 0$. If $A$ is invertible, zero is not an eigenvalue.

2. 本征值可以重复, 导致本征向量也可以重复.

Markov matrix

When $A$ is squared, the eigenvectors stay the same. The eigenvalues are squared. $$ A^{99}\left[\begin{array}{l} .8 \\\\ .2 \end{array}\right] \quad \rightarrow \quad \boldsymbol{x}_{1}+(.2)\left(\frac{1}{2}\right)^{99} \boldsymbol{x}_{2}=\left[\begin{array}{l} .6 \\\\ .4 \end{array}\right]+\left[\begin{array}{c} \text { very } \\\\ \text { small } \\\\ \text { vector } \end{array}\right] $$

The eigenvector $\boldsymbol{x}_1$ is a steady state that doesn’t change (because $\lambda_1 = 1$). The eigenvector $\boldsymbol{x}_2$ is a decaying mode that virtually disappears (because $\lambda_2 = .5$).
$A$ 被称为 Markov matrix, $\boldsymbol{x}_1 = (.6,.4)$ is the steady state.

对于投影矩阵

For projection matrices $P$, we can see when $P \boldsymbol{x}$ is parallel to $\boldsymbol{x}$. The eigenvectors for $\lambda = 1$ and $A = 0$ fill the column space and nullspace. The column space doesn’t move($P \boldsymbol{x} = \boldsymbol{x}$). The nullspace goes to zero ($P \boldsymbol{x} = 0 \boldsymbol{x}$).

例子: The projection matrix $P=\left[\begin{array}{cc}
.5 & .5 \\
.5 & .5
\end{array}\right] \text { has eigenvalues } \lambda=1 \text { and } \lambda=0$

其性质如下:

1. Markov matrix: Each column of $P$ adds to 1, so $\lambda= 1$ is an eigenvalue.
2. $P$ is singular, so $\lambda = 0$ is an eigenvalue.
3. $P$ is symmetric, so its eigenvectors $( 1, 1)$ and $( 1, -1)$ are perpendicular.

对于反射矩阵

例子:The reflection matrix $R=\left[\begin{array}{ll}
0 & 1 \\
1 & 0
\end{array}\right] \text { has eigenvalues } \mathbf{1} \text { and }-\mathbf{1}$

反射与投影之间的关系:
$$
\boldsymbol{R}=2 \boldsymbol{P}-\boldsymbol{I} \quad\left[\begin{array}{ll}
0 & 1 \\
1 & 0
\end{array}\right]=2\left[\begin{array}{ll}
.5 & .5 \\
.5 & .5
\end{array}\right]-\left[\begin{array}{ll}
1 & 0 \\
0 & 1
\end{array}\right]
$$

图解:

Determinant and Trace

对矩阵的行操作会导致某个单个本征值的变化(Elimination does not preserve the $\lambda$’s), 但是整体有不变的地方: 通过迹与秩反映(分解为 triangular matrix 后).

The product of the $n$ eigenvalues equals the determinant.
The sum of the $n$ eigenvalues equals the sum of the $n$ diagonal entries.

$A$ 的迹:

$$
\lambda_{1}+\lambda_{2}+\cdots+\lambda_{n}=\text { trace }=a_{11}+a_{22}+\cdots+a_{n n}
$$

Why do the eigenvalues of a triangular matrix lie along its diagonal? 后面会解答.

Imaginary Eigenvalues

本征值可能为复数, 例如旋转矩阵:

The $90^{\circ}$ rotation $Q=\left[\begin{array}{cc}0 & -1 \\ 1 & 0\end{array}\right]$ has no real eigenvectors. Its eigenvalues are $\lambda_{1}=i$ and $\lambda_{2}=-i$. Then $\lambda_{1}+\lambda_{2}=$ trace $=0$ and $\lambda_{1} \lambda_{2}=$ determinant $=1$.

复数 $i^2=-1$ 的意义: 旋转矩阵自乘 2 次会旋转 $180^。$ .

一些特殊矩阵可类比为实数与复数:
A symmetric matrix ( $S^T = S$) can be compared to a real number. A skew-symmetric matrix ($A^T = -A$) can be compared to an imaginary number. An orthogonal matrix ($Q^T Q = I$) corresponds to a complex number with $|\lambda| = 1$.

Eigenvalues of $AB$ and $A+ B$

$A$ and $B$ share the same $n$ independent eigenvectors if and only if $AB = BA$.

然后可以得到矩阵和的本征值为各自本征值的和, 矩阵乘积的本征值为各自本征值的乘积.
$A B \boldsymbol{x} =\lambda \beta \boldsymbol{x}, B A \boldsymbol{x} = \beta \lambda \boldsymbol{x}$.

6.2 Diagonalizing a Matrix

本节概要

1. The columns of $A X=X \Lambda$ are $A \boldsymbol{x}_{k}=\lambda_{k} \boldsymbol{x}_{k}$.The eigenvalue matrix $\Lambda$ is diagonal.
2. $n$ independent eigenvectors in $X$ diagonalize $A$: $A = X \Lambda X^{-1}$ and $\Lambda = X^{-1} A X$.
3. The eigenvector matrix $X$ also diagonalizes all powers $A^{k}$: $A^{k} = X \Lambda^k X^{-1}$.
4. Solve $\boldsymbol{u}_{k+1}=A \boldsymbol{u}_{k}$ by $\boldsymbol{u}_{k}=A^{k} \boldsymbol{u}_{0}=X \Lambda^{k} X^{-1} \boldsymbol{u}_{0}=c_{\mathbf{1}}\left(\lambda_{\mathbf{1}}\right)^{\boldsymbol{k}} \boldsymbol{x}_{\mathbf{1}}+\cdots+c_{n}\left(\lambda_{n}\right)^{\boldsymbol{k}} \boldsymbol{x}_{n}$​
5. No equal eigenvalues $\Rightarrow X$ is invertible and $A$ can be diagonalized.
6. Equal eigenvalues $\Rightarrow A$ might have too few independent eigenvectors. Then $X^{-1}$ fails.
7. Every matrix $C=B^{-1} A B$ has the same eigenvalues as $A$. These $C$’s are “similar“ to $A$.

对角化的意义: 方便一些运算, 例如对 $A$​ 进行高次幂运算, 对角矩阵的计算会非常简单.

Diagonalization Suppose the $n \times n$ matrix $A$ has $n$ linearly independent eigenvectors $\boldsymbol{x}{1}, \ldots, \boldsymbol{x}{n}$. Put them into the columns of an eigenvector matrix $X$. Then $X^{-1} A X$ is the eigenvalue matrix $\Lambda$​ :

$$
\begin{array}{l}\text { Eigenvector matrix } X \\ \text { Eigenvalue matrix } \Lambda \\ \end{array} \quad X^{-1} A X =\Lambda=\left[\begin{array}{lll}\lambda_{1} & & \\ & \ddots & \\ & & \lambda_{n}\end{array}\right]
$$

$A^2$ has the same eigenvectors in $X$ and squared eigenvalues in $\Lambda^2$.

推导过程如下:

$A$ times $X$ :
$$
A X=A\Bigg[\begin{array}{ccc}x_{1} & \cdots & x_{n}\end{array}\Bigg]=\Bigg[\begin{array}{lll}\lambda_{1} x_{1} & \cdots & \lambda_{n} x_{n}\end{array}\Bigg] .
$$

The trick is to split this matrix $A X$ into $X$ times $\Lambda$ , $X$ times $\Lambda$:

$$ \Bigg[\begin{array}{lll}\lambda_{1} \boldsymbol{x}_{1} & \cdots & \lambda_{n} \boldsymbol{x}_{n}\end{array}\Bigg]=\Bigg[\begin{array}{lll} \boldsymbol{x}_{1} & \cdots & \boldsymbol{x}_{n} \end{array}\Bigg]\left[\begin{array}{lll}\lambda_{1} & & \\\\ & \ddots & \\\\ & & \lambda_{n}\end{array}\right]=X \Lambda . $$

因此:
$$
A X=X \Lambda \text { is } X^{-1} A X=\Lambda \quad \text { or } \quad A=X \Lambda X^{-1}
$$

高次幂运算:
$$
A^{k}=\left(X \Lambda X^{-1}\right)\left(X \Lambda X^{-1}\right) \ldots\left(X \Lambda X^{-1}\right)=X \Lambda^{k} X^{-1}
$$
Question: When does $A^{k} \rightarrow$ zero matrix?
Answer :All $|\lambda|<1$.

结论 1
Suppose the eigenvalues $A_1, . . . , A_n$ are all different. Then it is automatic that the eigenvectors $\boldsymbol{x}_1, . . ., \boldsymbol{x}_n$ are independent. The eigenvector matrix $X$ will be invertible. Any matrix that has no repeated eigenvalues can be diagonalized.

结论 2
We can multiply eigenvectors by any nonzero constants. $A(c \boldsymbol{x}) = \lambda( c \boldsymbol{x})$ is still true.

结论 3
The eigenvectors in $X$ come in the same order as the eigenvalues in $\Lambda$.

结论 4
Some matrices have too few eigenvectors. Those matrices cannot be diagonalized.

There is no connection between invertibility and diagonalizability.
Invertibility is concerned with the eigenvalues ( $\lambda
= 0$ or $\lambda \ne 0$). 有没有零项.
Diagonalizability is concerned with the eigenvectors (too few or enough for $X$). 有没有重复项.

可对角化定理:

Independent $\boldsymbol{x}$ from different $\lambda$ :

Eigenvectors $\boldsymbol{x}_{1}, \ldots, \boldsymbol{x}_{j}$ that correspond to distinct (all different) eigenvalues are linearly independent. An $n \times n$ matrix that has $n$ different eigenvalues (no repeated $\lambda$ 's) must be diagonalizable.

Similar Matrices: Same Eigenvalues

定义
All the matrices $A = BCB^{-1}$ are “similar.” They all share the eigenvalues of $C$.

相似的形式:

• eigenvector matrix: $A=X \Lambda X^{-1}$, 更换 $X$ 中的列的顺序可以得到一系列的 $\Lambda$.
• 对于非 eigenvector matrix 的可逆矩阵 $B$(might not be diagonal, and the columns of $B$ might not be eigenvectors).
• 单位矩阵 $I$, $BI B^{- 1} = I$, with all eigenvalues $\lambda = 1$.
• 最简单的形式: Jordan form: All the similar $A$’s have two parameters $r$ and $s$, not both zero: always determinant= 1 and trace= 2.

$$
C=\left[\begin{array}{ll}
\mathbf{1} & \mathbf{1} \\
0 & \mathbf{1}
\end{array}\right]=\text { Jordan form gives } A=B C B^{-1}=\left[\begin{array}{cc}
1-r s & r^{2} \\
-s^{2} & 1+r s
\end{array}\right]
$$

Fibonacci Numbers

本征值求解的应用: 快速求解 Fibonacci 数列. 如何求解第 100 项的元素 $F_{100}$?
常规解法: 利用公式 $F_{k+ 2} = F_{k+ 1} + F_k$, 迭代.
线性代数解法:

1. 构造公式 $\boldsymbol{u}_{k+i} = A \boldsymbol{u}_k$​

$$ \text { Let } \boldsymbol{u}_{k}=\left[\begin{array}{c} F_{k+1} \\\\ F_{k} \end{array}\right] . \text { The rule } \begin{array}{l} F_{k+2}=F_{k+1}+F_{k} \\\\ F_{k+1}=F_{k+1} \end{array} \text { is } \boldsymbol{u}_{k+1}=\left[\begin{array}{ll} 1 & 1 \\\\ 1 & 0 \end{array}\right] \boldsymbol{u}_{k} $$

2. 求解 $A$​ 的本征值

$$
A-\lambda I=\left[\begin{array}{cc}
1-\lambda & 1 \\
1 & -\lambda
\end{array}\right] \quad \text { leads to } \quad \operatorname{det}(A-\lambda I)=\lambda^{2}-\lambda-1
$$

本征值解如下:
$$
\lambda_{1}=\frac{1+\sqrt{5}}{2} \approx 1.618
\text{ and }
\lambda_{2}=\frac{1-\sqrt{5}}{2} \approx-.618
$$

3. 对 $A$​ 进行幂运算

eigenvectors $\boldsymbol{x}_1=\left(\lambda_1, 1\right)$ and $\boldsymbol{x}_2=\left(\lambda_2, 1\right)$. Step 2 finds the combination of those eigenvectors that gives $\boldsymbol{u}_0=(1,0)$ :

$$
\left[\begin{array}{l}
1 \
0
\end{array}\right]=\frac{1}{\lambda_1-\lambda_2}\left(\left[\begin{array}{c}
\lambda_1 \
1
\end{array}\right]-\left[\begin{array}{c}
\lambda_2 \
1
\end{array}\right]\right) \quad \text { or } \quad \boldsymbol{u}_0=\frac{x_1-x_2}{\lambda_1-\lambda_2}
$$

100 steps from $\boldsymbol{u}_{0}$ $$ \boldsymbol{u}_{100}=\frac{\left(\lambda_{1}\right)^{100} x_{1}-\left(\lambda_{2}\right)^{100} x_{2}}{\lambda_{1}-\lambda_{2}} $$

4. We want $F_{100} =$ second component of $\boldsymbol{u}_{100}$. The second components of $\boldsymbol{x}_1$ and $\boldsymbol{x}_2$​ are 1.

$\text { 100th Fibonacci number }=\frac{\lambda_{1}^{100}-\lambda_{2}^{100}}{\lambda_{1}-\lambda_{2}}=\text { nearest integer to } \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{100}$.

$F_{101} /F_{100}$ must be very close to the limiting ratio $(1 + \sqrt{5})/2$. 也就是黄金比例: 1.618.

Matrix Powers $A^k$

总结上面的应用:
本征值分解 is perfectly suited to computing powers.
Powers of $A$:

$$ A^{k} \boldsymbol{u}_{0}=\left(X \Lambda X^{-1}\right) \cdots\left(X \Lambda X^{-1}\right) \boldsymbol{u}_{0}=X \Lambda^{k} X^{-1} \boldsymbol{u}_{0} $$

具体步骤总结如下:

1. Write $\boldsymbol{u}_{0}$ as a combination $c_{1} \boldsymbol{x}_{1}+\cdots+c_{n} \boldsymbol{x}_{n}$ of the eigenvectors. Then $\boldsymbol{c}=X^{-1} \boldsymbol{u}_{0}$. 2. Multiply each eigenvector $\boldsymbol{x}_{i}$ by $\left(\lambda_{i}\right)^{k}$. Now we have $\Lambda^{k} X^{-1} \boldsymbol{u}_{0}$. 3. Add up the pieces $c_{i}\left(\lambda_{i}\right)^{k} \boldsymbol{x}_{i}$ to find the solution $\boldsymbol{u}_{k}=A^{k} \boldsymbol{u}_{0}$. This is $X \Lambda^{k} X^{-1} \boldsymbol{u}_{0}$. Solution for $\boldsymbol{u}_{k+1}=A \boldsymbol{u}_{k} \quad \boldsymbol{u}_{k}=A^{k} \boldsymbol{u}_{0}=c_{1}\left(\lambda_{1}\right)^{k} \boldsymbol{x}_{1}+\cdots+c_{n}\left(\lambda_{n}\right)^{k} \boldsymbol{x}_{n}$. 即: $$ A^{k} \boldsymbol{u}_{0}=X \Lambda^{k} X^{-1} \boldsymbol{u}_{0}= X \Lambda^{k} \boldsymbol{c} = \left[\begin{array}{ccc} \boldsymbol{x}_{1} & \ldots & \boldsymbol{x}_{n} \end{array}\right]\left[\begin{array}{ccc} \left(\lambda_{1}\right)^{k} & & \\\\ & \ddots & \\\\ & & \left(\lambda_{n}\right)^{k} \end{array}\right]\left[\begin{array}{c} c_{1} \\\\ \vdots \\\\ c_{n} \end{array}\right] $$

Follow the eigenvectors, this is crucial link from linear algebra to differential equations($\lambda^k$ will become $e^{\lambda k}$).

Nondiagonalizable Matrices

multiplicity 的概念.
两个概念:

1. (Geometric Multiplicity = GM): Count the independent eigenvectors for $\lambda$. Then GM is the dimension of the nullspace of $A - \lambda I$.

2. (Algebraic Multiplicity = AM): Count the repetitions of $\lambda$ among the eigenvalues. Look at then roots of $\text{det}(A - \lambda I) = 0$.
   总会有 $GM \leq AM$.

multiplicity = AM - GM.

multiplicity > 0 $\Rightarrow$ undiagonalizable.

6.3 Systems of Differential Equations

本节概要

1. If $A \boldsymbol{x}=\lambda \boldsymbol{x}$ then $\boldsymbol{u}(t)=e^{\lambda t} \boldsymbol{x}$ will solve $\frac{d \boldsymbol{u}}{d t}=A \boldsymbol{u}$. Each $\lambda$ and $\boldsymbol{x}$ give a solution $e^{\lambda t} \boldsymbol{x}$.
2. If $A=X \Lambda X^{-1}$ then $\boldsymbol{u}(t)=e^{A t} \boldsymbol{u}(0)=X e^{\Lambda t} X^{-1} \boldsymbol{u}(0) = c_{1} e^{\lambda_{1} t} x_{1}+\cdots+c_{n} e^{\lambda_{n} t} x_{n}$.
3. $A$ is stable and $\boldsymbol{u}(t) \rightarrow \mathbf{0}$ and $e^{A t} \rightarrow 0$ when all eigenvalues of $A$ have real part $<0$.
4. Matrix exponential $e^{A t}=I+A t+\cdots+(A t)^{n} / n !+\cdots=X e^{\Lambda t} X^{-1}$ if $A$ is diagonalizable.
5. Second/First order equation $u^{\prime \prime}+B u^{\prime}+C u=0$ is equivalent to $\left[\begin{array}{l}u \\ u^{\prime}\end{array}\right]^{\prime}=\left[\begin{array}{c}0 \\ -C-B\end{array}\right]\left[\begin{array}{c}u \\ u^{\prime}\end{array}\right]$.

本节主要目的: To convert constant-coefficient differential equations into linear algebra.

本节研究对象: 线性时不变系统. 一般性的微分方程组系统表述如下:

$$
\begin{array}{l}
\text { System of } \\
\boldsymbol{n} \text { equations }
\end{array} \quad \frac{d \boldsymbol{u}}{d t}=A \boldsymbol{u} \quad \text { starting from the vector } \boldsymbol{u}(0)=\left[\begin{array}{c}
u_{1}(0) \\
\cdots \\
u_{n}(0)
\end{array}\right] \text { at } t=0
$$

细分为:
线性时变: $A$ changes as $t$ changes.
非线性:: $A$ changes as $\boldsymbol{u}$ changes.

求解的主题思想:
Solve linear constant coefficient equations by exponentials $e^{\lambda t}\boldsymbol{x}$, when $A \boldsymbol{x} = \lambda x$ .

Solution of $du/dt = Au$

求解思路:
$$
\begin{array}{l}
\text { Choose } \boldsymbol{u}=e^{\lambda t} \boldsymbol{x} \\
\text { when } \boldsymbol{A} \boldsymbol{x}=\lambda \boldsymbol{x}
\end{array} \quad \frac{d \boldsymbol{u}}{d t}=\lambda e^{\lambda t} \boldsymbol{x} \quad \text { agrees with } \quad A \boldsymbol{u}=A e^{\lambda t} \boldsymbol{x}
$$

得到的解为: $\boldsymbol{u} = e^{\lambda t}$ .
根据 $\lambda$ 分为3种情况:

1. $\lambda > 0$: grow
2. $\lambda < 0$: decay
3. imaginary part $\omega$ gives oscillation $e^{i \omega t}$ like a sine wave.

具体步骤如下:

1. Write $\boldsymbol{u}(0)$ as a combination $c_{1} \boldsymbol{x}_{1}+\cdots+c_{n} \boldsymbol{x}_{n}$ of the eigenvectors of $\boldsymbol{A}$.
2. Multiply each eigenvector $\boldsymbol{x}_{i}$ by its growth factor $e^{\boldsymbol{\lambda}_{i} t}$.
3. The solution is the same combination of those pure solutions $e^{\lambda t} \boldsymbol{x}$: $$ \frac{d \boldsymbol{u}}{d t}=A \boldsymbol{u} \quad u(t)=c_{1} e^{\lambda_{1} t} \boldsymbol{x}_{1}+\cdots+c_{n} e^{\lambda_{n} t} \boldsymbol{x}_{n} $$

注意上述解法:

1. Not included: If two $\lambda$’s are equal, with only one eigenvector, another solution is needed.(It will be $t e^{\lambda} \boldsymbol{x}$.)
2. Step 1 needs to diagonalize $A = X \Lambda X^{- 1}$: a basis of $n$ eigenvectors.

例子如下:
Solve $d \boldsymbol{u} / d t=A \boldsymbol{u}$ knowing the eigenvalues $\lambda=1,2,3$ of $A$:

$$
\begin{array}{l}\text { Typical example } \\ \text { Equation for } \boldsymbol{u} \\ \text { Initial condition } \boldsymbol{u}(0)\end{array} \quad \frac{d \boldsymbol{u}}{d t}=\left[\begin{array}{lll}1 & 1 & 1 \\ 0 & 2 & 1 \\ 0 & 0 & 3\end{array}\right] \boldsymbol{u} \quad \text { starting from } \quad \boldsymbol{u}(0)=\left[\begin{array}{l}9 \\ 7 \\ 4\end{array}\right]
$$.

The eigenvectors are $\boldsymbol{x}_{1}=(1,0,0)$ and $\boldsymbol{x}_{2}=(1,1,0)$ and $\boldsymbol{x}_{3}=(1,1,1)$. Step 1. The vector $\boldsymbol{u}(0)=(9,7,4)$ is $2 \boldsymbol{x}_{1}+3 \boldsymbol{x}_{2}+4 \boldsymbol{x}_{3}$. Thus $\left(c_{1}, c_{2}, c_{3}\right)=(2, 3, 4)$. Step 2. The factors $e^{\lambda t}$ give exponential solutions $e^{t} \boldsymbol{x}_{1}$ and $e^{2 t} \boldsymbol{x}_{2}$ and $e^{3 t} \boldsymbol{x}_{3}$. Step 3. The combination that starts from $\boldsymbol{u}(0)$ is $\boldsymbol{u}(t)=2 e^{t} \boldsymbol{x}_{1}+3 e^{2 t} \boldsymbol{x}_{2}+4 e^{3 t} \boldsymbol{x}_{3}$.

Second Order Equations

The most important equation in mechanics is $my^{\prime \prime} +by^{\prime}+ ky = 0$, 其中 $m,b,k$ 分别为质量, damping, elastic coefficient.

求解思路:

$$
m \frac{d^{2} y}{d t^{2}}+b \frac{d y}{d t}+k y=0 \quad \text { becomes } \quad\left(m \lambda^{2}+b \lambda+k\right) e^{\lambda t}=0
$$

构造矩阵:

$$
\begin{array}{l}
d y / d t=y^{\prime} \\
d y^{\prime} / d t=-k y-b y^{\prime}
\end{array} \quad \text { converts to } \quad \frac{d}{d t}\left[\begin{array}{c}
y \\
y^{\prime}
\end{array}\right]=\left[\begin{array}{rr}
0 & 1 \\
-k & -b
\end{array}\right]\left[\begin{array}{c}
y \\
y^{\prime}
\end{array}\right]=A \boldsymbol{u}
$$

$$
A-\lambda I=\left[\begin{array}{cc}
-\lambda & 1 \\
-k & -b-\lambda
\end{array}\right] \quad \text { has determinant } \quad \lambda^{2}+b \lambda+k=0
$$

$$ \boldsymbol{x}_{1}=\left[\begin{array}{c} 1 \\\\ \lambda_{1} \end{array}\right] \quad \boldsymbol{x}_{2}=\left[\begin{array}{c} 1 \\\\ \lambda_{2} \end{array}\right] \quad \boldsymbol{u}(t)=c_{1} e^{\lambda_{1} t}\left[\begin{array}{c} 1 \\\\ \lambda_{1} \end{array}\right]+c_{2} e^{\lambda_{2} t}\left[\begin{array}{c} 1 \\\\ \lambda_{2} \end{array}\right] $$

The $2 \times 2$ matrix $A$ is called a companion matrix -a companion to the second order equation with $y^{\prime \prime}$.

例子:
Motion around a circle with $y^{\prime \prime} + y = 0$ and $y = cos t$.

$$
\text{Use } y^{\prime \prime}=-y \frac{d \boldsymbol{u}}{d t}=\frac{d}{d t}\left[\begin{array}{c}y \\ y^{\prime}\end{array}\right]=\left[\begin{array}{rr}0 & 1 \\ -1 & 0\end{array}\right]\left[\begin{array}{c}y \\ y^{\prime}\end{array}\right]=A \boldsymbol{u}
$$

$$
\boldsymbol{u}(t)=\frac{1}{2} e^{i t}\left[\begin{array}{l}
1 \\
i
\end{array}\right]+\frac{1}{2} e^{-i t}\left[\begin{array}{r}
1 \\
-i
\end{array}\right]=\left[\begin{array}{r}
\cos t \\
-\sin t
\end{array}\right] . \quad \text { This is }\left[\begin{array}{c}
y(t) \\
y^{\prime}(t)
\end{array}\right]
$$

最终为一个半径为 1 的圆.

Difference Equations

replace $y^{\prime \prime} = -y$ by a difference equation. Here are three choices using $Y(t + \Delta t) - 2Y(t) + Y(t - \Delta t)$. Divide by $(\Delta t)^2$ to approximate $y^{\prime \prime}$.

$$
\begin{array}{lllll}
\mathbf{F} & \text { Forward from } n-1 & \frac{Y_{n + 1} - 2 Y_{n} + Y_{n - 1}}{(\Delta t)^{2}}= & -Y_{n - 1} \\
\mathbf{C} & \text { Centered at time } n & \frac{Y_{n + 1} - 2 Y_{n} + Y_{n - 1}}{(\Delta t)^{2}}= & -Y_{n} \\
\mathbf{B} & \text { Backward from } n + 1 & \frac{Y_{n + 1} - 2 Y_{n} + Y_{n - 1}}{(\Delta t)^{2}}= & -Y_{n + 1}
\end{array}
$$

形成的效果:

$$
\text { Forward }|\lambda|>1 \text { (spiral out) } \quad \text { Centered }|\lambda|=1 \text { (best) } \quad \text { Backward }|\lambda|<1 \text { (spiral in) }
$$

化成连续两帧之间的关系: $U_{n + 1} = A U_n$. 设 $U_n = (Y_n , Z_n )$.

1. Forward

$$ \begin{array}{l} Y_{n+1}=Y_{n}+\Delta t Z_{n} \\\\ Z_{n+1}=Z_{n}-\Delta t Y_{n} \end{array} \text { becomes } U_{n+1}=\left[\begin{array}{cc} 1 & \Delta t \\\\ -\Delta t & 1 \end{array}\right]\left[\begin{array}{l} Y_{n} \\\\ Z_{n} \end{array}\right]=A U_{n} $$ $$ \text { Eigenvalues of } A \quad \lambda=1 \pm i \Delta t \quad \text { Then }|\lambda|>1 \text { and }\left(Y_{n}, Z_{n}\right) \text { spirals out } $$

图解如下:

2. Backward

$$
\begin{array}{l}
Y_{n+1}=Y_{n}+\Delta t Z_{n+1} \\
Z_{n+1}=Z_{n}-\Delta t Y_NaN
\end{array} \text { is }\left[\begin{array}{cc}
1 & -\Delta t \\
\Delta t & 1
\end{array}\right]\left[\begin{array}{l}
Y_{n+1} \\
Z_{n+1}
\end{array}\right]=\left[\begin{array}{l}
Y_{n} \\
Z_{n}
\end{array}\right]= A U_{n}
$$

3. Centered

leapfrog method

Stability of $2 \times 2$ Matrices

Stability depends on the eigenvalues of $A$. 将本征值分解: $\lambda = r + is$,$e^{\lambda t} = e^{rt} e^{ist}$. Factor $e^{ist}$ has absolute value fixed at 1:

$$
e^{i s t}=\cos s t+i \sin s t \quad \text { has } \quad\left|e^{i s t}\right|^{2}=\cos ^{2} s t+\sin ^{2} s t=1
$$

实数部分决定 grow($r>0$) 或者 decay($r<0$).
The question is: Which matrices have negative eigenvalues? More accurately, when are the real parts of the $\lambda$’s all negative?

Stability $A$ is stable and $\boldsymbol{u}(t) \rightarrow 0$ when all eigenvalues $\lambda$ have negative real parts The $2 \times 2$ matrix $A=\left[\begin{array}{ll}a & b \\ c & d\end{array}\right]$ must pass two tests:

$$
\begin{aligned}
&\lambda_{1}+\lambda_{2}<0 \quad \text{ The trace } \quad T=a+d \text{ must be negative}. \\
&\lambda_{1} \lambda_{2}>0 \quad \text{ The determinant } \quad D=a d-b c \quad \text{ must be positive}.
\end{aligned}
$$

The Exponential of a Matrix

引入它的原因是当出现多重本征值时, 如何求解的问题.
We want to write the solution $\boldsymbol{u}(t)$ in a new form $e^{At}\boldsymbol{u}(0)$.
$e^{At}$ 的定义如下:

$$
\begin{aligned}
& \text{ Matrix exponential } e^{A t} & e^{A t} = I+A t + & \frac{1}{2}(A t)^{2}+\frac{1}{6}(A t)^{3}+\cdots \\
& \text{ Its } t \text{ derivative is } A e^{A t} & A+A^{2} t+\frac{1}{2} A^{3} t^{2}+\cdots & = A e^{A t} \\
& \text{ Its eigenvalues are } e^{\lambda t} \quad & \left(I+A t+\frac{1}{2}(A t)^{2}+\cdots\right) \boldsymbol{x} & = \left(1+\lambda t+\frac{1}{2}(\lambda t)^{2}+\cdots\right) \boldsymbol{x}
\end{aligned}
$$

Therefore $e^{At}u(0)$ solves the differential equation with one quick formula-even if there is a shortage of eigenvectors.

先从不存在多重的理想情况下开始考虑:

$$
\begin{aligned}
& \text{ Use the series } \quad & e^{A t} & = I+X \Lambda X^{-1} t+\frac{1}{2}\left(X \Lambda X^{-1} t\right)\left(X \Lambda X^{-1} t\right)+\cdots \\
& \text{ Factor out } X \text{ and } X^{-1} & & = X\left[I+\Lambda t+\frac{1}{2}(\Lambda t)^{2}+\cdots\right] X^{-1} \\
& e^{A t} \text{ is diagonalized! } &
e^{A t} & = X e^{\Lambda t} X^{-1}
\end{aligned}
$$

由此可见, $e^{At} \boldsymbol{u}(0)$ has the same eigenvector matrix $\boldsymbol{x}$ as $A$. Then $\Lambda$ is a diagonal matrix and so is $e^{\Lambda t}$.

$$ \begin{aligned} e^{A t} \boldsymbol{u}(0) & = X e^{\Lambda t} X^{-1} \boldsymbol{u}(0) & = \left[\begin{array}{lll} & & \\\\ \boldsymbol{x}_{1} & \cdots & \boldsymbol{x}_{n} \\\\ & & \end{array}\right]\left[\begin{array}{lll} e^{\lambda_{1} t} & & \\\\ & \ddots & \\\\ & & e^{\lambda_{n} t} \end{array}\right]\left[\begin{array}{c} c_{1} \\\\ \vdots \\\\ c_{n} \end{array}\right] \end{aligned} $$

出现多重本征值时:
例如: $y’’ - 2y’ + y = 0$, 本征值为 $\lambda = 1 , 1$. Diagonalization is not possible.
$u =(y, y’)$ 时:

$$
\frac{d}{d t}\left[\begin{array}{c}
y \\
y^{\prime}
\end{array}\right]=\left[\begin{array}{c}
y^{\prime} \\
2 y^{\prime}-y
\end{array}\right] \quad \text { is } \quad \frac{d \boldsymbol{u}}{d t}=A \boldsymbol{u}=\left[\begin{array}{rr}
0 & 1 \\
-1 & 2
\end{array}\right] \boldsymbol{u}
$$

做一阶泰勒展开:

$$
e^{A t}=e^{I t} e^{(A-I) t}=e^{t}[I+(A-I) t]
$$

The first component of $e^{At} \boldsymbol{u}(0)$ is our answer $y(t)$.

$$
\left[\begin{array}{l}
y \\
y^{\prime}
\end{array}\right]=e^{t}\left[I+\left[\begin{array}{ll}
-1 & 1 \\
-1 & 1
\end{array}\right] t\right]\left[\begin{array}{r}
y(0) \\
y^{\prime}(0)
\end{array}\right] \quad y(t)=e^{t} y(0)-t e^{t} y(0)+t e^{t} y^{\prime}(0)
$$

对于反对称矩阵:
$A$ is an antisymmetric matrix ($A^T = -A$). Its exponential $e^{At}$ is an orthogonal matrix.
The eigenvalues of $A$ are $i$ and $-i$. The eigenvalues of $e^{At}$ are $e^{it}$ and $e^{- it}$.

4 rules:

1. $e^{At}$ always has the inverse $e^{-At}$.
2. The eigenvalues of $e^{At}$ are always $e^{\lambda t}$.
3. When $A$ is antisymmetric, $e^{At}$ is orthogonal. Inverse= transpose= $e^{-At}$.
4. Their absolute value is 1: neutral stability, pure oscillation, energy is conserved. So $||\boldsymbol{u}(t)|| = ||\boldsymbol{u}(0)||$.

例子:

$$
\begin{aligned}
& A=\left[\begin{array}{rr}
0 & 1 \\
-1 & 0
\end{array}\right] \\
& e^{A t}=I+A t+\frac{1}{2}(A t)^{2}+\frac{1}{6}(A t)^{3}+\cdots=\left[\begin{array}{cc}
1-\frac{1}{2} t^{2}+\cdots & t-\frac{1}{6} t^{3}+\cdots \\
-t+\frac{1}{6} t^{3}-\cdots & 1-\frac{1}{2} t^{2}+\cdots
\end{array}\right] \\
& e^{A t}=\left[\begin{array}{rr}
\cos t & \sin t \\
-\sin t & \cos t
\end{array}\right]
\end{aligned}
$$

对于三角矩阵:
triangular matrix $A$. Then the eigenvector matrix $X$ is triangular. So are $X^{- 1}$ and $e^{At}$.

6.4 Symmetric Matrices

本节概要

1. A symmetric matrix $S$ has $n$ real eigenvalues $\lambda_{i}$ and $n$ orthonormal eigenvectors $\boldsymbol{q}{1}, \ldots, \boldsymbol{q}{n}$.
2. Every real symmetric $S$ can be diagonalized : $S = Q \Lambda Q^{-1}=Q \Lambda Q^{\mathrm{T}}$.
3. The number of positive eigenvalues of $S$ equals the number of positive pivots.
4. Antisymmetric matrices $A=-A^{\mathrm{T}}$ have imaginary $\lambda$’s and orthonormal (complex) $q’s$.
5. Section 9.2 explains why the test $S = S^{\mathrm{T}}$ becomes $\boldsymbol{S}=\overline{\boldsymbol{S}}^{\mathbf{T}}$ for complex matrices.
   $S=\left[\begin{array}{rr}0 & i \\ -i & 0\end{array}\right]=\bar{S}^{\mathrm{T}} \text{ has real } \lambda=1,-1 . \quad A=\left[\begin{array}{cc}0 & i \\ i & 0\end{array}\right]=-\bar{A}^{\mathrm{T}} \text{ has } \lambda=i,-i$.

symmetric matrices are the most important matrices in the world.

问题:
What is special about $S \boldsymbol{x} = S \boldsymbol{x}$ when $S$ is symmetric?

回答:

1. A symmetric matrix has only real eigenvalues.
2. The eigenvectors can be chosen orthonormal.

Every symmetric matrix can be diagonalized. Its eigenvector matrix $X$ becomes an orthogonal matrix $Q$.

Why do we use the word “choose”? Because the eigenvectors do not have to be unit vectors. Their lengths are at our disposal.

Spectral Theorem 谱定理

Spectral Theorem: Every symmetric matrix has the factorization $S = Q \Lambda Q^{\mathrm{T}}$ with real eigenvalues in $\Lambda$ and orthonormal eigenvectors in the columns of $Q$:
Symmetric diagonalization:
$$
S = Q \Lambda Q^{-1}=Q \Lambda Q^{\mathrm{T}} \quad \text{ with } \quad Q^{-1}=Q^{\mathrm{T}}
$$.

This is the “spectral theorem” in mathematics and the “principal axis theorem” in geometry and physics.

Symmetric matrices $S$ have orthogonal eigenvector matrices $Q$. Look at this again:
Symmetry $S = X \Lambda X^{-1}$ becomes $S = Q \Lambda Q^{\mathrm{T}}$ with $Q^{\mathrm{T}} Q=I$.
This says that every $2 \times 2$ symmetric matrix is (rotation)(stretch)(rotate back)

$$ S=Q \Lambda Q^{\mathrm{T}}=\left[\begin{array}{ll} \boldsymbol{q}_{1} & \boldsymbol{q}_{2} \end{array}\right]\left[\begin{array}{ll} \lambda_{1} & \\\\ & \lambda_{2} \end{array}\right]\left[\begin{array}{l} \boldsymbol{q}_{1}^{\mathrm{T}} \\\\ \boldsymbol{q}_{2}^{\mathrm{T}} \end{array}\right] $$ Columns $\boldsymbol{q}_{1}$ and $\boldsymbol{q}_{2}$ multiply rows $\lambda_{1} \boldsymbol{q}_{1}^{\mathrm{T}}$ and $\lambda_{2} \boldsymbol{q}_{2}^{\mathrm{T}}$ to produce $S = \lambda_{1} \boldsymbol{q}_{1} \boldsymbol{q}_{1}^{\mathrm{T}}+\lambda_{2} \boldsymbol{q}_{2} \boldsymbol{q}_{2}^{\mathrm{T}}$.

Complex Eigenvalues of Real Matrices

For real matrices, complex $\lambda$’s and $x$’s come in “conjugate pairs.”

$$
\begin{aligned}
& \begin{array}{l}
\lambda=a+i b \\
\bar{\lambda}=a-i b
\end{array} \\
& \text{ if } A \boldsymbol{x} = \lambda x \text{ then } A \bar{\boldsymbol{x}} = \bar{\lambda} \bar{\boldsymbol{x}}
\end{aligned}
$$

即便 $A$ 全是实数也有可能出现复数的本征值.

第 9 章会详细讲复数矩阵.

Eigenvalues versus Pivots

The eigenvalues of $A$ are very different from the pivots. For eigenvalues, we solve $\text{det}(A - AI) = 0$. For pivots, we use elimination. The only connection:

1. product of pivots = determinant = product of eigenvalues.

2. For symmetric matrices the pivots and the eigenvalues have the same signs:
   The number of positive eigenvalues of $S = S^T$ equals the number of positive pivots.

positive definite matrices
Special case: $S$ has all $\lambda_i > 0$ if and only if all pivots are positive.

All Symmetric Matrices are Diagonalizable

证明使用 Schur’s Theorem:
Every square $A$ factors into $QTQ^{- 1}$ where $T$ is upper triangular and $Q^{-T}= Q^{- 1}$. If $A$ has real eigenvalues then $Q$ and $T$ can be chosen real: $Q^T Q = I$.

Schur’s $S = Q T Q^{-1}$ means that $T=Q^{\mathrm{T}} S Q$. The transpose is again $Q^{\mathrm{T}} S Q$.
The triangular $T$ is symmetric when $S^{\mathrm{T}}=S$. Then $T$ must be diagonal and $T=\Lambda$.
This proves that $S = Q \Lambda Q^{-1}$. The symmetric $S$ has $n$ orthonormal eigenvectors in $Q$.

6.5 Positive Definite Matrices

本节概要

1. Symmetric $S$ : all eigenvalues $>0 \Leftrightarrow$ all pivots $>0 \Leftrightarrow$ all upper left determinants $>0$.
2. The matrix $S$ is then positive definite. The energy test is $\boldsymbol{x}^{\mathrm{T}} S \boldsymbol{x}>0$ for all vectors $\boldsymbol{x} \neq \mathbf{0}$.
3. One more test for positive definiteness: $S = A^{\mathrm{T}} A$ with independent columns in $A$.
4. Positive semidefinite $S$ allows $\lambda=0 , \text{pivot} = 0 , \text{determinant} = 0 , \text{ energy } \boldsymbol{x}^{\mathrm{T}} S \boldsymbol{x} = 0$.
5. The equation $\boldsymbol{x}^{\mathrm{T}} S \boldsymbol{x}=1$ gives an ellipse in $\mathbf{R}^{n}$ when $S$ is symmetric positive definite.

本节的两个目的:

• To find quick tests on a symmetric matrix that guarantee positive eigenvalues.
• To explain important applications of positive definiteness.

从简单的 $2 \times 2$ 矩阵开始
问题:

$
\text { When does } S=\left[\begin{array}{ll}
a & b \\
b & c
\end{array}\right] \text { have } \lambda_{1}>0 \text { and } \lambda_{2}>0 ?
$

The eigenvalues of $S$ are positive if and only if $a > 0$ and $ac - b^2 > 0$.
证明思路如下:
$$
\left[\begin{array}{ll}
a & b \\
b & c
\end{array}\right] \quad \begin{array}{c}
\text { The first pivot is } a \\
{\longrightarrow} \\
\text { The multiplier is } b / a
\end{array} \quad\left[\begin{array}{cc}
a & b \\
0 & c-\frac{b}{a} b
\end{array}\right] \quad \begin{array}{c}
\text { The second pivot is } \\
c-\frac{b^{2}}{a}=\frac{a c-b^{2}}{a}
\end{array}
$$

Energy-based Definition

引入:
From $S \boldsymbol{x} = A \boldsymbol{x}$, multiply by $\boldsymbol{x}^T$ to get $\boldsymbol{x}^T S \boldsymbol{x} = \lambda \boldsymbol{x}^T \boldsymbol{x}$. $\boldsymbol{x}^T S \boldsymbol{x}$ is positive for all nonzero vectors $\boldsymbol{x}$.

$\boldsymbol{x}^T S \boldsymbol{x}$ (or $\frac{1}{2}\boldsymbol{x}^T S \boldsymbol{x}$) is the energy in the system.

The requirement of positive energy gives another definition of a positive definite matrix.

Definition $S$ is positive definite if $\boldsymbol{x}^{\mathrm{T}} S \boldsymbol{x}>0$ for every nonzero vector $\boldsymbol{x}$:
$$
2 \times 2 : \quad \boldsymbol{x}^{\mathrm{T}} S \boldsymbol{x}=\left[\begin{array}{ll}x & y\end{array}\right]\left[\begin{array}{ll}a & b \\ b & c\end{array}\right]\left[\begin{array}{l}x \\ y\end{array}\right]=a x^{2}+2 b x y+c y^{2}>0
$$

If $S$ and $T$ are symmetric positive definite, so is $S + T$.

推论
If the columns of $A$ are independent, then $S = A^T A$ is positive definite.

$\boldsymbol{x}^T S \boldsymbol{x}=\boldsymbol{x}^T A^T A \boldsymbol{x}= (A \boldsymbol{x})^T (A \boldsymbol{x}) = ||A \boldsymbol{x}||^2 \geq 0$,只有当 $A$ 中出现了线性相关的列才会等于0. 这也验证了正定矩阵的能量非负性质.

5 equivalent statements of positive definite­ness. You will see how that key idea connects the whole subject of linear algebra: pivots, determinants, eigenvalues, and least squares (from $A^T A$).

When a symmetric matrix $S$ has one of these five properties, it has them all :

1. All $n$ pivots of $S$ are positive.
2. All $n$ upper left determinants are positive.
3. All $n$ eigenvalues of $S$ are positive.
4. $\boldsymbol{x}^T S \boldsymbol{x}$ is positive except at $\boldsymbol{x} = 0$. This is the energy-based definition.
5. $S$ equals $A^T A$ for a matrix $A$ with independent columns.

The “upper left determinants” are 1 by 1, 2 by 2, … , $n$ by $n$.

Cholesky factor

类比于 LU 分解, 我们对正定矩阵进行分解: $S=LDL^T= (L\sqrt{D})(L\sqrt{D})^T=A^TA$, $A$ 即为 Cholesky factor.

也可以对正定矩阵进行本征值分解:

$S=A^TA, ; A=Q\sqrt{\Lambda}Q^T$
当 $S$ 为 $\left[\begin{array}{rrr}
2 & -1 & 0 \\
-1 & 2 & -1 \\
0 & -1 & 2
\end{array}\right]$

可以得到其诸多分解例子如下:

$$ \begin{aligned} & \boldsymbol{x}^{\mathrm{T}} S \boldsymbol{x}=2 \boldsymbol{x}_{1}^{2}-2 \boldsymbol{x}_{1} \boldsymbol{x}_{2}+2 \boldsymbol{x}_{2}^{2}-2 \boldsymbol{x}_{2} \boldsymbol{x}_{3}+2 \boldsymbol{x}_{3}^{2} \quad & \text{ Rewrite with squares } \\\\ & \left\|A_{1} \boldsymbol{x}\right\|^{2}=\boldsymbol{x}_{1}^{2}+\left(\boldsymbol{x}_{2}-\boldsymbol{x}_{1}\right)^{2}+\left(\boldsymbol{x}_{3}-\boldsymbol{x}_{2}\right)^{2}+\boldsymbol{x}_{3}^{2} \quad & \text{ Using differences in } \\\\ & A_1 \left\|A_{2} \boldsymbol{x}\right\|^{2}=2\left(\boldsymbol{x}_{1}-\frac{1}{2} \boldsymbol{x}_{2}\right)^{2}+\frac{3}{2}\left(\boldsymbol{x}_{2}-\frac{2}{3} \boldsymbol{x}_{3}\right)^{2}+\frac{4}{3} \boldsymbol{x}_{3}^{2} \quad & \text{ Using } S=L D L^{\mathrm{T}} \\\\ & \left\|A_{3} \boldsymbol{x}\right\|^{2}=\lambda_{1}\left(\boldsymbol{q}_{1}^{\mathrm{T}} \boldsymbol{x}\right)^{2}+\lambda_{2}\left(\boldsymbol{q}_{2}^{\mathrm{T}} \boldsymbol{x}\right)^{2}+\lambda_{3}\left(\boldsymbol{q}_{3}^{\mathrm{T}} \boldsymbol{x}\right)^{2} \quad & \text{ Using } S=Q \Lambda Q^{\mathbf{T}} \end{aligned} $$

Positive Semidefinite Matrices

The smallest eigenvalue is zero. The energy in its eigenvector is $\boldsymbol{x}^T S \boldsymbol{x} = \boldsymbol{x}^T \boldsymbol{0} \boldsymbol{x} = 0$.

Positive semidefinite matrices have all $\lambda > 0$ and all $\boldsymbol{x}^T S \boldsymbol{x} > 0$. Those weak inequalities( $\geq$ instead of $>$ ) include positive definite $S$ and also the singular matrices at the edge.

接下来是应用

The Ellipse $ax^2 + 2bxy + cy^2 = 1$

principal axis theorem
对正定矩阵进行本征分解可以使找到图形的主轴.
例子: tilted ellipse $5x^2 + 8xy + 5y^2 = 1$.
分解得正定矩阵 $S$:

The equation is

$$
\left[\begin{array}{ll}x & y\end{array}\right]\left[\begin{array}{ll}5 & 4 \\ 4 & 5\end{array}\right]\left[\begin{array}{l}x \\ y\end{array}\right]=1
\text{ The matrix is }
S=\left[\begin{array}{ll}5 & 4 \\ 4 & 5\end{array}\right]
$$

本征分解: $S = QAQ^T$: Eigenvectors in $Q$, Eigenvalues 9 and 1

$$
\left[\begin{array}{ll}5 & 4 \\ 4 & 5\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{rr}1 & 1 \\ 1 & -1\end{array}\right]\left[\begin{array}{ll} 9 & 0 \\ 0 & 1\end{array}\right] \frac{1}{\sqrt{2}}\left[\begin{array}{rr}1 & 1 \\ 1 & -1\end{array}\right]
$$

$\boldsymbol{x}^T S \boldsymbol{x} = (\boldsymbol{x}^T Q)\Lambda (Q^T \boldsymbol{x})$:

$$
\boldsymbol{x}^T S \boldsymbol{x}=\text { sum of squares } 5 x^{2}+8 x y+5 y^{2}=9\left(\frac{x+y}{\sqrt{2}}\right)^{2}+1\left(\frac{x-y}{\sqrt{2}}\right)^{2}
$$

使用 $X,Y$ 即主轴表示:

$$
\text { Lined up } \quad \frac{x+y}{\sqrt{2}}=X \quad \text { and } \quad \frac{x-y}{\sqrt{2}}=Y \quad \text { and } \quad 9 X^2 +Y^{2} = 1
$$

最终的图解:

总结:

$S=Q \Lambda Q^{\mathrm{T}}$ is positive definite when all $\lambda_{i}>0$. The graph of $\boldsymbol{x}^{\mathrm{T}} S \boldsymbol{x}=1$ is an ellipse:

$$
\left[\begin{array}{ll}x & y\end{array}\right] Q \Lambda Q^{\mathrm{T}}\left[\begin{array}{l}x \\ y\end{array}\right]=\left[\begin{array}{ll}X & Y\end{array}\right] \Lambda\left[\begin{array}{l}X \\ Y\end{array}\right]=\lambda_1 X^{2}+\lambda_{2} Y^{2}=1
$$

The axes point along eigenvectors of $S$. The half-lengths are $1 / \sqrt{\lambda_{1}}$ and $1 / \sqrt{\lambda_{2}}$.

Important Application: Test for a Minimum

对于双变量函数 $F(x,y)$, positive $d^2 f / dx^2$ changes to positive definite $S$:

$$
S=\left[\begin{array}{ll}
\partial^{2} F / \partial x^{2} & \partial^{2} F / \partial x \partial y \\
\partial^{2} F / \partial y \partial x & \partial^{2} F / \partial y^{2}
\end{array}\right]
$$

图解:

$$
F(x, y) \text { has a minimum if } \partial F / \partial x=\partial F / \partial y=0 \text { and } S \text { is positive definite. }
$$

各类矩阵及其本征值

$$ \begin{array}{lll} \textbf { Symmetric: } S^{\mathrm{T}}=S=Q \Lambda Q^{\mathrm{T}} & \text { real eigenvalues } & \text { orthogonal } \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}=0 \\\\ \textbf { Orthogonal: } Q^{\mathrm{T}}=Q^{-1} & \text { all }|\lambda|=1 & \text { orthogonal } \overline{\boldsymbol{x}}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}=0 \\\\ \textbf { Skew-symmetric: } A^{\mathrm{T}}=-A & \text { imaginary } \lambda \text { 's } & \text { orthogonal } \overline{\boldsymbol{x}}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}=0 \\\\ \textbf { Complex Hermitian: } \bar{S}^{\mathrm{T}}=S & \text { real } \lambda \text { 's } & \text { orthogonal } \overline{\boldsymbol{x}}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}=0 \\\\ \textbf { Positive Definite: } \boldsymbol{x}^{\mathrm{T}} S \boldsymbol{x}>0 & \text { all } \lambda>0 & \text { orthogonal since } S^{\mathrm{T}}=S \\\\ \textbf { Markov: } m_{i j}>0, \sum_{i=1}^{n} m_{i j}=1 & \lambda_{\text {max }}=1 & \text { steady state } \boldsymbol{x}>0 \\\\ \textbf { Similar: } A=B C B^{-1} & \lambda(A)=\lambda(C) & B \text { times eigenvector of } C \\\\ \textbf { Projection: } P=P^{2}=P^{\mathrm{T}} & \lambda=1 ; 0 & \text { column space; nullspace } \\\\ \textbf { Plane Rotation }: \operatorname{cosine-sine} & e^{i \theta} \text { and } e^{-i \theta} & \boldsymbol{x}=(1, i) \text { and }(1,-i) \\\\ \textbf { Reflection: } I-2 \boldsymbol{u} \boldsymbol{u}^{\mathrm{T}} & \lambda=-1 ; 1, . ., 1 & \boldsymbol{u} ; \text { whole plane } \boldsymbol{u}^{\perp} \\\\ \textbf { Rank One: } \boldsymbol{u} \boldsymbol{v}^{\mathrm{T}} & \lambda=\boldsymbol{v}^{\mathrm{T}} \boldsymbol{u} ; 0, . ., 0 & \boldsymbol{u} ; \text { whole plane } \boldsymbol{v}^{\perp} \\\\ \textbf { Inverse: } A^{-1} & 1 / \lambda(A) & \text { keep eigenvectors of } A \\\\ \textbf { Shift: } A+c I & \lambda(A)+c & \text { keep eigenvectors of } A \\\\ \textbf { Stable Powers: } A^{n} \rightarrow 0 & \text { all }|\lambda|<1 & \text { any eigenvectors } \\\\ \textbf { Stable Exponential: } e^{A t} \rightarrow 0 & \text { all Re } \lambda<0 & \text { any eigenvectors } \\\\ \textbf { Cyclic Permutation: } P_{i, i+1}=1, P_{n 1}=1 & \lambda_{k}=e^{2 \pi i k / n}=\text { roots of } 1 & \boldsymbol{x}_{k}=\left(1, \lambda_{k}, \ldots, \lambda_{k}^{n-1}\right) \\\\ \textbf { Circulant: } c_{0} I+c_{1} P+\cdots & \lambda_{k}=c_{0}+c_{1} e^{2 \pi i k / n}+\cdots & \boldsymbol{x}_{k}=\left(1, \lambda_{k}, \ldots, \lambda_{k}^{n-1}\right) \\\\ \textbf { Tridiagonal: }-1,2,-1 \text { on diagonals } & \lambda_{k}=2-2 \cos \frac{k \pi}{n+1} & \boldsymbol{x}_{k}=\left(\text { sin } \frac{k \pi}{n+1}, \sin \frac{2 k \pi}{n+1}, \ldots\right) \\\\ \textbf { Diagonalizable: } A=X \Lambda X^{-1} & \text { diagonal of } \Lambda & \text { columns of } X \text { are independent } \\\\ \textbf { Schur: } A=Q T Q^{-1} & \text { diagonal of triangular } T & \text { columns of } Q \text { if } A^{\mathrm{T}} A=A A^{\mathrm{T}} \\\\ \textbf { Jordan: } A=B J B^{-1} & \text { diagonal of } J & \text { block gives } 1 \text { eigenvector } \\\\ \textbf { SVD: } A=U \Sigma V^{\mathrm{T}} & r \text { singular values in } \Sigma & \text { eigenvectors of } A^{\mathrm{T}} A, A A^{\mathrm{T}} \text { in } V, U \end{array} $$