Introduction to Linear Algebra
Gilbert Strang
- Chapter 6 Eilgenvalues and Eigenvectors
This chapter enters a new part of linear algebra, based on $Ax = AX.$
Certain exceptional vectors x are in the same direction as Ax. Those are the "eigenvectors". Multiply an eigenvector by A, and the vector Ax is a number A times the original x.
+ 선형변환 A에 의한 변환 결과가 자기 자신의 상수배가 되는 0이 아닌 벡터
The basic equation is $Ax = Ax$. The number $A$ is an eigenvalue of $A$.
- 고유값 $\lambda$는 A의 고유값이며, 0이 될 수 있다.
- $Ax=0x$는 이 고유벡터 x가 nullspace 안에 있다는 것을 의미한다.
- A가 identity matrix라면 모든 벡터는 Ax=x를 가지고 있음.
- 모든 벡터들이 I의 고유벡터이고, 모든 고유값 lambda는 1임
$A= \begin{bmatrix}{.8}&{.3}\\{.2}&{.7} \end{bmatrix} det\begin{bmatrix}{.8-\lambda}&{.3}\\{.2}&{.7-\lambda} \end{bmatrix} = \lambda^{2}-\frac{3}{2} \lambda + \frac{1}{2} = (\lambda-1)(\lambda-\frac{1}{2})$
nullspace에 있는
- $(A-I)x_1=0, Ax_1=x_1$, 고유벡터$(.6,.4) \rightarrow Ax_1=\begin{bmatrix}{.8}&{.3}\\{.2}&{.7}\end{bmatrix}\begin{bmatrix}{.6}\\{.4} \end{bmatrix}=x_1$
- $(A-\frac{1}{2}I)x_2=0, Ax_2=x_2$, 고유벡터$(1,-1) \rightarrow Ax_2=\begin{bmatrix}{.8}&{.3}\\{1}&{-1}\end{bmatrix}\begin{bmatrix}{.5}\\{-.5} \end{bmatrix}=x_2$
When A is squared, the eigenvectors stay the same. The eigenvalues are squared.
- 여기서 고유벡터들이 절대 섞이지 않고 자신의 방향에 머물기 때문에 패턴이 유지된다.
Other vectors do change direction. But all other vectors are combinations of the two eigenvectors.
- 방향이 변하는 다른 벡터들의 경우.
- A의 첫번째 열은 $x_1+(.2)x_2$ 임.
- 예제에서는 $\begin{bmatrix}{.8}\\{-.2} \end{bmatrix}=x_1+(.2)x_2=\begin{bmatrix}{.6}\\{-.4} \end{bmatrix}+\begin{bmatrix}{.2}\\{-.2} \end{bmatrix}$
- A에 곱해질때 각 고유벡터는 고유값에 곱해짐
- At every step $x_1$ is unchanged and $x_2$ is multiplied by ($\frac{1}{2}$), so we have ($\frac{1}{2})^{99}$
- $x^{99}\begin{bmatrix}{.8}\\{-.2} \end{bmatrix} isreally_1+(.2)\frac{1}{2}^{99}x_2=\begin{bmatrix}{.6}\\{-.4} \end{bmatrix}+\begin{bmatrix}{very}\\{small}\\{vector} \end{bmatrix}$
- This is the first column of A 100. $\rightarrow$ 여기서(.8,.2)를 의미함
A is a Markov matrix(각 열 벡터들을 더하면 1이 되는 행렬).
- Its eigenvector $x_l = (.6,.4)$ is the steady state-which all columns of Ak will approach.
The projection matrix $P=\begin{bmatrix}{.5}&{.5}\\{.5}&{.5} \end{bmatrix}$ has eigencalues $\lambda=1$ and $\lambda=0$
위 예는 markov matrices, singular matrices, 그리고 symmetric matrices를 설명한다.
- All have special A's and x 's:
- $P=\begin{bmatrix}{.5}&{.5}\\{.5}&{.5} \end{bmatrix}$의 각 열은 1을 추가해서 람다=1이 고유값
- P는 singular여서 람다=0이 고유값
- P는 대칭이어서 고유벡터(1,1)과 (1,-1)이 직각
- 영공간nullspace는 0에 투영되어있음
- 열 공간은 그 스스로를 투영함
- Project each aprt $v=\begin{bmatrix}{1}&{-1}\\{2}&{2} \end{bmatrix}$ projects onto $P_v=\begin{bmatrix}{0}&{0}\\{2}&{2} \end{bmatrix}$
- Projections have $\lambda = 0$ and $1$. Permutations have all $|A| = 1$.
The reflection matrix $R=\begin{bmatrix}{0}&{1}\\{1}&{0} \end{bmatrix}$ has eigenvalues 1 snd -1
- 고유벡터(1,1)은 R에 의해 변하지 않음!
- $reflection = 2(projection)-I$ 때문에 R에서 고유벡터은 P에서와 같다.
- $R=2P-I, \begin{bmatrix}{0}&{1}\\{1}&{0} \end{bmatrix}=2\begin{bmatrix}{.5}&{.5}\\{.5}&{.5} \end{bmatrix}-\begin{bmatrix}{1}&{0}\\{0}&{1} \end{bmatrix}.\dots (2)$
- $2Px=2\lambda x$처럼 행렬이 두 배가 되면 고유값이 2배가 된다.
- 그 결과가 $(2p-i)X=(2\lambda-1)x$!!
- 행렬이 I에 의해 변하면 각 $\lambda$는 1에 의해 바뀐다. 고유벡터 내에서는 변화 없음!!
Key idea: The eigenvalues of Rand P are related exactly as the matrices are related:
- The eigenvalues of $R = 2P - I$ are 2(1) - 1 = 1 and 2(0) - 1 = -1.
- The eigenvalues of $R^2$ are $\lambda^2$. In this case $R^2 = I$. Check $(I)^2$ = 1 and $(-1)^2$ = 1.
The Equation for the Eigenvalues: $P x = x, P x = 0, Rx = -x$ is the key caculation almost every application starts by solving $Ax = \lambda x$.
- 일단 $\lambda x$를 왼쪽으로 넘기면 $(A-\lambda I)x=0$을 쓸 수 있고
- 행렬 $(A-\lambda I)$매를 한 고유벡터 x는 0 벡터임.
- The eigenvectors make up the nullspace of $A - \lambda I$
- 고유값 람다를 알때, $(A-\lambda I)x=0$을 풀어서 고유벡터를 찾을 수 있음
If $(A - \lambda I)X = 0$ has a nonzero solution, $A - \lambda I$ is not invertible. The determinant of $A -\lambda I$ must be zero.
- 고유값 람다 알아내는 법
- The number $\lambda$ is an eignvalue of A if and only if $A-\lambda I$ is singular:
- Equtation for the eigenvalues $\rightarrow det(A-\lambda I)=0$
- $det(A-\lambda I)=0$ 여기에는 x가 아닌 람다만 들어있음
- A가 N $\times$ N 행렬일때 $det(A-\lambda I)=0$는 degree N을 가지게 됨
For each elgenvalue $\lambda$ solve $(A - \lambda I)x = 0$ or $A_x=\lambda x$ to find an eigenvector x.
$A=\begin{bmatrix}{1}&{2}\\{2}&{4} \end{bmatrix}$ is already singular (zero determinant). Find its $\lambda$'s and $x$'s
- A가 singular일때 $\lambda=0$은 고유값들 중 하나이다.
- $Ax=0x$가 solution을 가짐! 이는 $\lambda=0$에 대한 고유 벡터임
- 하지만 $det(A-\lambda I)=0$은 모든 람다들과 x들을 찾는 방법임
- Subtract $\lambda$ from the diagonal to find $a-\lambda i =\begin{bmatrix}{1-\lambda}&{2}\\{2}&{4-\lambda} \end{bmatrix}$
Take the determinant "ad - bc" of this 2 by 2 matrix.
- $det\begin{bmatrix}{1-\lambda}&{2}\\{2}&{4-\lambda} \end{bmatrix}=(1-\lambda)(4-\lambda)-(2)(2)=\lambda^{2}-5\lambda$
- $\lambda^{2}-5\lambda$를 0으로 놓으면 근은 람다가 0 또는 5
- One solution is $\lambda = 0$ (as expected, since A is singular). Factoring into $\lambda$ times $\lambda - 5$, the other root is $\lambda = 5$.:
- $det(A-\lambda I)=\lambda^2-5\lambda =0$ yields the eigenvalues $\lambda_1=0$ and $\lambda_2=5$
- 고유벡터를 찾아보자
- $(A-0I)x=\begin{bmatrix}{1}&{2}\\{2}&{4} \end{bmatrix}\begin{bmatrix}{y}\\{z} \end{bmatrix}=\begin{bmatrix}{0}\\{0} \end{bmatrix}$ yields the eigenvector $\begin{bmatrix}{y}\\{z} \end{bmatrix}=\begin{bmatrix}{2}\\{-1} \end{bmatrix}$ for $\lambda_1=0$
- $(A-5I)x=\begin{bmatrix}{-4}&{2}\\{2}&{-1} \end{bmatrix}\begin{bmatrix}{y}\\{z} \end{bmatrix}=\begin{bmatrix}{0}\\{0} \end{bmatrix}$ yields the eigenvector $\begin{bmatrix}{y}\\{z} \end{bmatrix}=\begin{bmatrix}{1}\\{2} \end{bmatrix}$ for $\lambda_2=5$.
- 0과 5가 고유값이기 때문에 $A-0I$, $A-5I$는 singular이다.
- 고유벡터 (2,-1)과 (1,2)은 영공간nullspace에 있다.: $(A-\lambda I)x=0$ is $Ax=\lambda x$
summary: n matrix에 의한 고유값 문제를 해결하기 위해 밟을 step!
- Compute the determinant of $A-\lambda I$.
- Find the roots of this polynomial
- solve $(A-\lambda I)x=0$ to find an eigenvector $x$
Bad news: A 행에 또다른 열을 추가하거나 행을 바꾼다면 고유값들은 항상 변할 것임!
- Elimination does not preserve the A'S. The triangular U has its eigenvalues sitting along the diagonal-they are the pivots. But they are not the eigenvalues of A!
Good news: The product $\lambda_1$ times $\lambda_2$ and the sum $\lambda_1$ + $\lambda_2$ can be found quickly from the matrix.
The product of the n eigenvalues equals the determinant. The sum of the n eigenvalues equals the sum of the n diagonal entries.
- The sum of the entries on the main diagonal is called the trace of A:
- $\lambda_1+\lambda_2+\dots+\lambda_n=trace=a_{11}+a_{22}+\dots+a_{nn}$
- 계산을 잘못했는지 알 수 있음! 잘못되었다면? go back to $det(A-\lambda I)=0$
- The determinant test makes the product of the A'S equal to the product of the pivots (assuming no row exchanges). But the sum of the A'S is not the sum of the pivots-as the example showed. The individual A's have almost nothing to do with the pivots. In this new part of linear algebra, the key equation is really nonlinear: A multiplies x.
The eigenvalues might not be real numbers.?!?!
The $90^o$ rotation $Q=\begin{bmatrix}{0}&{-1}\\{1}&{0} \end{bmatrix}$ has no real eigenvectors. Its eigenvalues are $\lambda=i$ and $\lambda=-i$. Sum of $\lambda$'s= trace=0, Product=determinany=1.
- rotation 후 $Q_x$ 어느 벡터도 x와 같은 방향에 있지 않음 x=0일때 빼고.
- 그러면 고유벡터가 될 수 없는데 그래도 우리는 허수imaginary numbers로 보겠다.
- $-I$인 $Q^2$을 봐봐. 만약 Q가 90도 회전하면 $Q^2$은 180도 회전하겠지? 그건 고유값들이 -1과 -1이라는 거고.(확실히 $-IX=-1X$인 건 아니까.) $Q^2$이니까 각 $\lambda ^2$이 될거고. 우리는 $\lambda ^2=-1$을 얻게될거야. 그러면 근은 $i,-i$가 나오겠지. 우리는 허수 i가 고유벡터에 있다는 것을 알 수 있어.
- $\begin{matrix} complex \\ eigenvectors \end{matrix}$ $\begin{bmatrix}{0}&{-1}\\{1}&{0} \end{bmatrix}\begin{bmatrix}{1}\\{i} \end{bmatrix}=-i\begin{bmatrix}{1}\\{i} \end{bmatrix}$ and $\begin{bmatrix}{0}&{-1}\\{1}&{0} \end{bmatrix}\begin{bmatrix}{i}\\{1} \end{bmatrix}=i\begin{bmatrix}{i}\\{1} \end{bmatrix}$
- 여기서 복소수벡터complex vector $x_1=(1,i),x_2=(i,1)$는 회전한 방향을 유지하지.
- 이 예제들은 실제 행렬이 복소수 고유치들과 고유값들을 쉽게 가질 수 있는 모든 중요한 포인트를 만들지.
- 특히 고유치 i와 -i는 Q의 two special properties을 말해.
- Q is an otrhogonal matrix so the absolute value of each $\lambda$ is $|\lambda|=1$
- Q is a skew-wymmetric matrix so each $\lambda$ is pure imaginary.
- A symmetric matrix $(^AT=A)$ can be compared to a real number. A skew-symmetric matrix $(A^T = -A)$ can be compared to an imaginary number. An orthogonal matrix $(A^T A = 1)$ can be compared to a complex number with $|\lambda| = 1$.
- The eigenvectors for all these special matrices are perpendicular. Somehow (i, I) and (1, i) are perpendicular
The eigenvalue A is the length of $Ax$ , when the unit eigenvector x lines up. The built-in choices for A illustrate three possibilities: 0,1, or 2 directions where $A_x$ crosses x.
- 0: 실제 고유벡터가 없음. $Ax$가 x의 뒤 혹은 앞에 있음. 이건 고유값과 고유벡터들이 rotation Q에서 복소수라는 것을 의미함.
- 1: 고유벡터들의 오직 한 line만이 존재. Ax와 x는 움직이는 방향에서 만나긴 하는데 교차하진 않음.(2$\times$2행렬에서)
- 2: 두 독립적인 방향의 고유벡터가 있음. This is typica! Ax는 x와 첫번째 고유벡터 $x_1$에서 교차하고, 두번째 고유벡터 $x_2$에서 다시 돌아옴(cross back). 그러면 Ax와 x는 $-x_1$과 $-x_2$에서 다시 교차함.
REVIEW OF THE KEY IDEAS
- $Ax = \lambda x$ says that eigenvectors x keep the same direction when multiplied by A.
- $Ax = \lambda x$ also says that $det(A - \lambda I) = 0$. This determines n eigenvalues.
- The eigenvalues of $A^2$ and $A^{-1}$ are $\lambda^2$ and $\lambda^{-1}$, with the same eigenvectors.
- The sum of the A'S equals the sum down the main diagonal of A (the trace). The product of the A'S equals the determinant.
- Projections $P$, reflections $R$, $90^o$ rotations $Q$ have special eigenvalues $1,0, -1, i, -i$. Singular matrices have $\lambda = O$. Triangular matrices have A'S on their diagonal.
WORKED EXAMPLES
6.1.A 다 끝내고 시간 나면 할 것,,
Does the matrix A turn into a diagonal matrix A when we use the eigenvectors properly?
Diagonalization: Suppose the n by n matrix A has n linearly independent eigervectors $x_1,\dots,x_n$. Put them into the columns of an eigenvectors matrix S. Then $S^{-1}AS$ is tje eigenvalue matrix $\Lambda$
- Eigenvector matrix S, Eigenvalue matrix $\Lambda$, $S^{-1}AS=\Lambda=\begin{bmatrix}{\lambda_1}&{}&{}\\{}&{\ddots}&{}\\{}&{}&{\lambda_n}\end{bmatrix}$
- i.e. $AS=S\Lambda$ is $S^{-1}AS=\Lambda$ or $A=SAS^{-1}$
- 행렬 S는 역을 취할 수 있기 때문에 그 열들은 선형적으로 독립이 될 수 있다. n개의 독립적인 고유벡터 없이 대각선화 할 수 없다.
- $A$와 $\Lambda$는 같은 고유값 $\lambda_1,\dots\lambda_n$을 가지고 있다.
- 이 고유 벡터들은 다르다.
$$\text{Eigenvectors }\begin{bmatrix}{1}\\{0}\end{bmatrix}\begin{bmatrix}{1}\\{1}\end{bmatrix} \begin{matrix}\begin{bmatrix}{1}&{-1}\\{0}&{1}\end{bmatrix}\\S^{-1}\end{matrix}\begin{matrix}\begin{bmatrix}{1}&{5}\\{0}&{6}\end{bmatrix}\\A\end{matrix}\begin{matrix}\begin{bmatrix}{1}&{1}\\{0}&{1}\end{bmatrix}\\S\end{matrix}$ = $\begin{matrix}\begin{bmatrix}{1}&{0}\\{0}&{6}\end{bmatrix}\\ \Lambda\end{matrix}$$
$A=S\Lambda S^{-1} \rightarrow A^2=S \Lambda S^{-1}S \Lambda S^{-1} \rightarrow \text{ remove } S^{-1}S=I \rightarrow S \Lambda^2S^{-1}$
- The $k^{th}$ power will be $A^k = S \Lambda^k S^{-1}$
Remark
- 고유값 $\lambda_1,\dots\lambda_n$는 다 달라서 자동으로 고유벡터 $x_1,\dots,x_n$도 독립적이다. 반복죄지 않는 고유값을 가진 어느 행렬도 대각성화 할 수 없다. 2.어느 nonzero constats를 고유벡터에 곱할 수 있다.$Ax=\lambda x$는 true로 남아있다.
- S에서 고유벡터는 $\Lambda$의 고유값에 따라 같은 정렬에 있다.(The eigenvectors in $S$ come in the same order as the eigenvalues in $\Lambda$) 4.어떤 행렬이 너무 적은 고유벡터를 가지고 있으면 그 행렬은 대각선화할 수 없다.
n개의 람다들에 대해 고유벡터들은 독립적이다. 그러면 우리는 A를 대각화할 수 있다.
Independent $x$ from differentt $\lambda$
- 구별되는 고유값들에 관련된 고유벡터 $x_1,\dots,x_n$는 선형적으로 독립이다.
- n개의 다른 고유값들을(반복되지 않은 람다들) 가진 n by n 행렬은 대각화되어야만 한다.
Powers of A
- A가 Markov matrix이면?
- $A=S\Lambda S^{-1}$에서 구한 고유벡터들은 $S$의 열 안에 있고, $A^2$의 고유벡터이기도 함.
- $A^2$은 $S$와 같고, $A^2$ 고유벡터 행렬은 $\Lambda^2$임을 보여보자.
- SAME $S$ for $A^2$
- $A^2 = S\Lambda S^{-1}S\Lambda S^{-1} = S\Lambda^2 S^{-1}$
- Powers of A
- $A^k = S\Lambda^k S^{-1}$
- Limit $k \rightarrow \infty$
- $A^{100}=S\Lambda S^{-1}$
- SAME $S$ for $A^2$
Every new Fibonacci number is the sum of the two previous F's:
- The sequence 0,1,1,2,3,5,8,13,... comes from $F_{k+2}=F_{k+1}+F_{k}$
step 1: 일단 matrix equation $u_{k+1}=Au_k$으로 시작!
- Let $u_k=\begin{bmatrix}{F_{k+1}}\\{F_k}\end{bmatrix} $. The rule $\begin{matrix}{F_{k+2}=F_{k+1}+F_k}\\{F_{k+1}=F_{k+1}}\end{matrix}$ is $u_{k+1} = \begin{bmatrix}{1}&{1}\\{1}&{0}\end{bmatrix}u_k$
Every step multiples by $A= \begin{bmatrix}{1}&{1}\\{1}&{0}\end{bmatrix}$.
- 100번하면 $u_{100}=A^{100}u_k$가 된다.
- Subtract $\lambda$ from the diagonal of A:
- $A-\lambda I = \begin{bmatrix}{1-\lambda}&{1}\\{1}&{-\lambda}\end{bmatrix}$ leads to $det(A-\lambda I)=\lambda^2 - \lambda - 1$
- $-b\pm sqrt(b^2-4ac)/2a$ 으로 해를 구할 수 있지
- Eigenvalues $\lambda_1=\frac{1+\sqrt{5}}{2} \approx 1.618$ and $\lambda_2=\frac{1-\sqrt{5}}{2} \approx -.618$
- Eigenvalues로 Eigenvectors를 구해보자. $x_1=(\lambda_1,1)$ and $x_2=(\lambda_2,1)$
step 2: Find the combination of those eigenvectors that gives $u_0=(1,0)$
- $\begin{bmatrix} {1}\\{0} \end{bmatrix} = \frac{1}{\lambda_1-\lambda_2} \bigg( \begin{bmatrix}{\lambda_1}\\{1} \end{bmatrix} - \begin{bmatrix}{\lambda_2}\\{1} \end{bmatrix} \bigg)$ or $u_0=\frac{x_1-x_2}{\lambda_1-\lambda_2}$
step 3: multiplies $u_0$ by $A^{100}$ to find $u_{100}$
- 100 steps from $u_0$ $u_{100}=\frac{(\lambda_1)^{100}x_1-(\lambda_2)^{100}x_2}{\lambda_1-\lambda_2}$
- 우리는 $F_{100}= \text{ second componets of } u_{100}$ 를 원해
- $x_1$과 $x_2$의 second component는 1이야
- ${\lambda_1-\lambda_2}$은 $\sqrt{5}$
- 결국 $F_{100}=\frac{1}{\sqrt{5}}\bigg[\bigg(\frac{1+\sqrt{5}}{2} \bigg)^{100} - \bigg(\frac{1-\sqrt{5}}{2} \bigg)^{100}\bigg] \approx 3.54\cdot10^{20}$
- The fractions and square roots must disappear, because Fibonacci's rule $F_{k+2} = F_{k+l} + F_k$ stays with integers
- k번째 피보나치 수=$\frac{\lambda_{1}^{k}-\lambda_{2}^{k}}{\lambda_1-\lambda_2}$ = 가장 가까운 상수는 $\frac{1}{\sqrt{5}}\bigg(\frac{1+\sqrt{5}}{2} \bigg)^{k}$
The ratio FlOd F100 must be very close to the limiting ratio (I + 0) /2. The Greeks called this number the "golden mean".
Power of A: $A^KU_0 = (S\Lambda S^{-1})\dots(S\Lambda S^{-1})u_0=S\Lambda^k S^{-1}u_0$
- Write $u_0$ as a combination $c_1x_1+\dots+c_nx_n$ of the eigenvectors.
- Multuply eaxh eigenvector $x_i$ by $(\lambda_i)^k$
- Add up the pieces $c_i(\lambda_i)^kx_i$ to find the solution $u_k=A^ku_0$
- Solution for $u_{k+1}=Au_k$ $u_k=A^ku_0=c_1(\lambda_1)^kx_1+\dots+c_n(\lambda_n)^kx_n$
the eigenvectors in S lead to the c's in the combination $u_0=c_1x_1+\dots+c_nx_n$
step 1
- $u_0= \begin{bmatrix}{}\\ {x_1} & {\dots} & {x_n}\\{} \end{bmatrix}\begin{bmatrix}{c_1}\\{\vdots}\\{c_n} \end{bmatrix}$. This says that $u_0=Sc$
- 상관계수는 $c=S^{-1}U_0$
step 2
- Multiply by $\Lambda^k$
step 3
- the final result $u_k=\sum c_i(\lambda_i)^kx_i$is the product of S and $\Lambda^k$ and $S^{-1}u_0$
- $A^ku_0 = S\Lambda^kS^{-1}u_0 = S\Lambda^kc = \begin{bmatrix}{}&{}&{}\\{x_1} & {\dots}&{x_n}\\{}&{}&{}\end{bmatrix} \begin{bmatrix}{(\lambda_1)^k}&{}&{}\\{}&{\ddots}&{}\\{}&{}&{(\lambda_n)^k}\end{bmatrix} \begin{bmatrix}{c_1}\\{\vdots}\\{c_n}\end{bmatrix}$
고유벡터와 고유값을 가진 S와 람다집합일때, $A^Ku_0$를 계산해보자.
- $u_0=(1,0)$
- $A=\begin{bmatrix}{1}&{2}\\{1}&{0}\end{bmatrix} \text{ has } \lambda_1=2 \text{ and } x_1=\begin{bmatrix}{2}\\{1}\end{bmatrix}$
- $\lambda_2=-1 \text{ and } x_2=\begin{bmatrix}{1}\\{-1}\end{bmatrix}$
Solution in three steps: $u_0=c_1x_1+c_2x_2$를 찾고 $u_k=c_1(\lambda_1)^kx_1+c_2(\lambda_2)^kx_2$도 찾자
- step 1 $u_0=\begin{bmatrix}{1}\\{0}\end{bmatrix} = \frac{1}{3}\begin{bmatrix}{2}\\{1}\end{bmatrix} + \frac{1}{3}\begin{bmatrix}{1}\\{-1}\end{bmatrix} \text{ so } c_1 = c_2=\frac{1}{3}$
- step 2 Multiply the two parts by $(\lambda_1)^k=2^k \text{ and } (\lambda_2)^k=(-1)^k$
-
step 3 Combine eigenvectors $c_1(\lambda_1)^kx_1 \text{ and }c_2(\lambda_2)^kx_2 \text{ into } u_k $
- $u_k=A^ku_0$ $u_k=\frac{1}{3}2^k\begin{bmatrix}{2}\\{1}\end{bmatrix}+\frac{1}{3}(-1)^k\begin{bmatrix}{1}\\{-1}\end{bmatrix}$
람다가 A의 고유값일때 우리는 두가지를 알아냈지
- 기하학적으로 고유벡터; 0이 아닌nonzero 해결책은 $Ax=\lambda x$
- 대수로 고유값; $A-\lambda I $의 determinant는 0이야.
For exceptional matrices, an eigenvalue can be repeated. Then there are two different ways to count its multiplicity. Always OM < AM for each A: 고유값들이 반복되는 예외적인 경우에 중복도(?)를 세는 두가지 다른 방법이 있다.
- 기하학적 중복도 Geomatric Multiplicity=GM
- $\lambda$에서 독립적인 고유벡터를 센다.이건 $A-\lambda I$의 nullspace의 차원이다.
- 대수적 중복도 Algebraic Multiplicity=AM
- 고유값을 사용한 $\lambda$의 반복을 센다. $det(A-\lambda I)=0$의 n개의 근을 본다.
$\lambda=4,4,4$이면 GM은 3이고 AM은 1 또는 2 또는 3임!!
- When repeats = [1 1. .. 1] we know that the n eigenvalues are all different and A is diagonalizable.
- The sum of all components in "repeats" is always n, because every nth degree equation $det(A - \lambda I) = 0$ has n roots (counting repetitions). The sum of all components in "repeats" is always $n$, because every $n^{th}$ degree equation $det(A - \lambda I) = 0$ has $n$ roots (counting repetitions).
- The total number of independent eigenvectors might be less than n. Then A is not diagonalizable.
An eigenvalue $\lambda$ of A times an eigenvalue $\beta$ of B usually does not give an eigenvalue of AB:
False proof: $ABx = A\beta x = \beta A x = \beta \lambda x$.
- 이건 베타를 곱한 람다가 고유값처럼 보인다.
- x가 A,B의 고유벡터일때 이는 옳은 증명이다.
- 하지만 항상 그렇지는 않지!
- A의 고유벡터들은 일반적으로 B의 고유벡터들이 아니다.
- 1이 AB의 고유값일때, A,B는 모두 0 고유값을 가질 수 있다.
- 이 때문에 A+B의 고유값은 일반적으로 $\lambda+\beta$가 아니다.
- 이 잘못된 증명은 위 사실을 보인다.
- x가 진짜 A,B 모두의 고유벡터라면, $ABx=\lambda \beta x$와 $BAx= \beta \lambda x$가 나와야 한다.
- n개의 고유벡터가 공유된다면 고유값들을 곱할 수 있다.
REVIEW OF THE KEY IDEAS
- If $A$ has $n$ independent eigenvectors $x_1 \dots x_n$, they go into the columns of $S$.
- $A$ is diagonalized by $S$ $S^{-1}AS = \Lambda$ and $A = S\Lambda S^{-1}$.
- The powers of $A$ are $A^k = S\Lambda^kS^{-1}$. The eigenvectors in $S$ are unchanged.
- The eigenvalues of $A^k$ are $(\lambda_1)^k, ... , (\lambda_n)^k$ in the matrix $\Lambda^k$.
- The solution to $u_{k+l} = Au_k$ starting from $u_0$ is $u_k = A^ku_0 = S\Lambda^kS^{-1}u_0$:
- $u_k=c_1(\lambda_1)^kx_1+\dots+c_n(\lambda_n)^kx_n$ provided $u_0 = c_1x_1 + c_nx_n$
- That shows Steps 1,2,3 ($c$'s from $S^{-1} u_O , \lambda^k$ from $\Lambda^k$, and $x$'s from $S$)
- A is diagonalizable if every eigenvalue has enough eigenvectors (GM = AM).
WORKED EXAMPLES
Problem Set 6.2
The whole point of the section is this: To convert constant-coefficient differential equations into linear algebra.
One equation $\frac{du}{dt}=\lambda u$ has the solutions $u(t) = Ce^{\lambda t}$.
- Linear algebra moves to n by n. The unknown is a vector u (now boldface).
- 우리는 n exponentials $e^{\lambda t}x$ in $u(t)$를 expect하지.
n equations $\frac{du}{dt}=Au$ starting from the vector $u(0)$ at t=0
- These differential equations are linear. If u(t) and vet) are solutions, so is $C u(t) + Dv(t)$.
- 우리가 가장 먼저 할 일: "pure exponential solutions" $Ax=\lambda x$를 사용하여 $u=e^{\lambda t}x$ 를찾는 것
- Notice that A is a constant matrix.
- $\frac{du}{dt} = Au$ is "linear with constant coefficients"
The main point will be:Solve linear constant coefficient equations by exponentials $e^{\lambda t}x$, when $Ax = \lambda X$.
Use $u=e^{\lambda t}x$ when $Ax=\lambda x$ $\frac{du}{dt}=\lambda e^{\lambda t}x$ agrees with $Au=Ae^{\lambda t}x$
- All components of this special solution $u = e^{\lambda t}x$ share the same $e^{\lambda t}$. The solution grows when $\lambda > O$. It decays when $\lambda < O$. If $\lambda$ is a complex number, its real part decides growth or decay. The imaginary part $w$ gives oscillation ei wt like a sine wave.
Solve $\frac{du}{dt}=Au=\begin{bmatrix}{0}&{1}\\{1}&{0}\end{bmatrix}u$ starting from $u(0)=\begin{bmatrix}{4}\\{2}\end{bmatrix}$
- u에 대한 벡터방정식
- y,z라는 스칼라를 포함
$\frac{du}{dt}=Au$, $frac{d}{dt}\begin{bmatrix}{y}\\{z}\end{bmatrix} = \begin{bmatrix}{1}&{1}\\{1}&{0}\end{bmatrix} \begin{bmatrix}{y}\\{z}\end{bmatrix}$ means that $\frac{dy}{dt}=z$ and $\frac{dz}{dt}=y$
- This matrix A has eigenvalues 1 and -1. The eigenvectors are (1, 1) and (1, -1).
- $u_1(t)=e^{\lambda_1 t}x_1=e^t \begin{bmatrix} {1}\\{1}\end{bmatrix}$ and $u_2(t)=e^{\lambda_2 t}x_2=e^{-t} \begin{bmatrix} {1}\\{-1}\end{bmatrix}$
To find all other solutions, multiply those special solutions by any C and D and add:
- Complete solution
- $u(t) = Ce^t\begin{bmatrix}{1}\\{1}\end{bmatrix}+De^{-t}\begin{bmatrix}{1}\\{-1}\end{bmatrix} = \begin{bmatrix}{4}\\{2}\end{bmatrix}$ yields $C=3$ and $D=1$
The same three steps that solved Uk+l = AUk now solve $\frac{du}{dt} = Au:$
- Write $u (0)$ as a combination $c_1 x_1 + ... + c_n x_n$ of the eigenvectors of $A$.
- Multiply each eigenvector $x_i$ by $e^{\lambda_i t}$ .
- The solution is the combination of pure solutions $e^{\lambda t}x$:
- $u(t)=c_1e^{\lambda_1 t}x_1+\dots+c_ne^{\lambda_n t}x_n$
Solve $\frac{du}{dt}=Au$ knowing tjhe eigenvalues $\lambda=1,2,3$ of A
$$\frac{du}{dt}=\begin{bmatrix}{1}&{1}&{1}\\{0}&{2}&{2}\\{0}&{0}&{3} \end{bmatrix}u \text{ starting from } u(0)=\begin{bmatrix}{9}\\{7}\\{4} \end{bmatrix}$$
The eigenvectors are $x_1 = (1,0,0)$ and $x_2 = (1,1,0)$ and $x_3 = (1,1,1)$.
- Step 1 The vector $u(0) = (9,7,4)$ is $2x_1 + 3x_2 + 4x_3$. Thus ($c_1, c_2, c_3) = (2,3,4)$.
- Step 2 The pure exponential solutions are $e^t x_1$ and $e^{2t} x_2$ and $e^{3t} x_3$.
- Step 3 The combination that starts from $u(0)$ is $u(t) = 2e^{t}x_1 + 3e^{2t} x_2 + 4e^{3t} x_3$.
The coefficients 2, 3, 4 came from solving the linear equation $c_1x_1 + c_2x_2 + c_3x_3 = u(0)$:
$$\begin{bmatrix}{}&{}&{}\\{x_1}&{x_2}&{x_3}\\{}&{}&{} \end{bmatrix}\begin{bmatrix}{c_1}\\{c_2}\\{c_3} \end{bmatrix}=\begin{bmatrix}{1}&{1}&{1}\\{0}&{1}&{1}\\{0}&{0}{1} \end{bmatrix}\begin{bmatrix}{2}\\{3}\\{4} \end{bmatrix}=\begin{bmatrix}{9}\\{7}\\{4} \end{bmatrix} \text{ which is } Sc=u(0)$$
The most important equation in mechanics is $my" +by' +ky = 0$.
?
$$m\frac{d^2 y}{dt^2}+b\frac{dy}{dt} + ky = 0 \text{ becomes } (m\lambda^2 + b\lambda + k) e^{\lambda t}=0$$
Everything depends on $m\lambda^2 + b\lambda + k = 0$. This equation for $\lambda$ has two roots $\lambda_1$ and $\lambda_2$. Then the equation for $y$ has two pure solutions $y_1 = e^{\lambda_1 t}$ and $y_2 = e^{\lambda_2 t}$ . Their combinations $c_1 y_1 + c_2y_2$ give the complete solution unless $\lambda_1 = \lambda_2$.
$$u(t)=c_1e^{\lambda_1 t}\begin{bmatrix}{1}\\{\lambda_1} \end{bmatrix}+c_we^{\lambda_2 t}\begin{bmatrix}{1}\\{\lambda_2} \end{bmatrix}$$
Motion around a circle with $y" + y = 0$ and $y = cos t$
$$\begin{matrix}{\text{Forward from }n-1}\\{\text{ Centeren at }n}\\{\text{ Backward from }n+1} \end{matrix}\frac{Y_{n+1}-2Y_n +Y_{n-1}}{(\Delta t)^2}=\begin{matrix}{-Y_{n-1}}\\{-Y_n}\\{-Y_{n+1}} \end{matrix}$$
- 이 세가지 방법은 완전한 원을 구성하진 않아, $\Delta t = \frac{2\pi}{32}$ 길이의 32단계에서
$$\text{Foward }|\lambda|>1\text{ (spiral out) Centered} |\lambda|=1\text{(best) Backward } |\lambda|<1 \text{ (spiral in)}$$
$$\text{Forward }\begin{matrix}{Y_{n+1}=Y_n+\Delta tZ_n}\\{Z_{n+1}=Z_n-\Delta tY_n}\end{matrix}\text{ becomes } U_{n+1}=\begin{bmatrix}{1}&{\Delta t}\\{-\Delta t}&{1} \end{bmatrix}\begin{bmatrix}{Y_n}\\{A_n} \end{bmatrix}=AU_n$$
$$\text{Eigenvalues of A } \lambda = 1 \pm i\Delta t \text{ } |\lambda | >1 \text{ and } (Y_n, Z_n) \text{ spirals out}$$
$$\text{Backward }\begin{matrix} {Y_{n+1}=Y_n+\Delta t Z_{n+1}}\\{Z_{n+1}=Z_n-\Delta t T_{n+1}}\end{matrix} \text{ is } \begin{bmatrix}{1} &{-\Delta t}\\{\Delta}&{1}\end{bmatrix}\begin{bmatrix}{Y_{n+1}\\{Z_{n+1}}}\end{bmatrix}=\begin{bmatrix}{Y_n}\\{Z_n}\end{bmatrix}=U_n$$
- complete solution $u(t)$ 는 $e^{\lambda t}$로 만들어짐!
- 만약 고유값 람다가 있다면, $e^{\lambda t}$가 0에 가까워지면 그땐 정확하게 람다가 음수여야 한다는 것을 알지.
- 만약 고유값이 복소수 $\lambda = r+is$라면 실제 부분 r은 음수여야 하지.
$$e^{ist} =\cos st + i \sin st \text{ has }|e^{ist}|^2=\cos ^2 st+\sin ^2 st =1 $$
Which matrices have negative eigenvalues? More accurately, when are the real parts of the $\lambda$'s all negative?
$$\text{Stability; a is stable and } u(t)\rightarrow 0 \text{ when all eigenvalues have negative real parts.}$$
$$\text{The 2 by 2 matrix } A=\begin{bmatrix}{a}&{b}\\{c}&{d}\end{bmatrix} \text{must pass two tests:}$$
$$\begin{matrix}{\lambda_1+\lambda_2<0}\\{\lambda_1\lambda_2 >0}\end{matrix} \begin{matrix}{\text{The trace } T=a+d \text{must be negative}}\\{\text{The determinant } D=ad-bc \text{ must be positive}}\end{matrix}$$
- 람다들이 음수로 존재하면 합은 음수일테니까, 그 합이 trace T이고. 그럼 곱은 양수가 되겠지. 이게 determinant D야.
- 람다들이 복소수라면 $r\pm is$로부터 얻을 수 있겠지, 그렇지 않으면 T,D는 얻을 수 없어
We want to write the solution $u(t)$ in a new form $e^{At} u(0)$.
$$\text{Matrix exponentil }e^{At} \text{ } e^{At} = I At +\frac{1}{2}(At)^2 + \frac{1}{6}(At)^3+\dots$$
$$\text{Its derivative is } Ae^{At} \text{ }A+A^2+\frac{1}{2}A^3t^2+\dots = Ae^{At}$$
$$\text{Its eigenvalues are } e^{\lambda r}\text{ }(I+At +\frac{1}{2}(At)^2)x=(1+\lambda t +\frac{1}{2}(\lambda t)^2+\dots)x$$
This chapter emphasizes how to find$ u(t) = e^{At} u(0)$ by diagonalization. Assume A does have $n$ independent eigenvectors, so it is diagonalizable. Substitute $A = S\Lambda S^{-1}$ into the series for $e^{At}$. Whenever $\Lambda S^{-1} S\Lambda S^{-1}$ appears, cancel $S^{-1} S$ in the middle:
$$\text{Use the series } e^{At}=I+S\Lambda S^{-1}t +\frac{1}{2}(S\Lambda S^{-1}t)(S\Lambda S^{-1}t)+\dots$$
$$\text{Factor out } S \text{ and } S^{-1} \text{ } = S[I+\Lambda t +\frac{1}{2}(\Lambda t)^2+\dots]S^{-1}$$
$$\text{Diagonalize } e^{At} \text{ } = Se^{\Lambda t}S^{-1}$$
$$e^{At}u(0) = Se^{\Lambda t}S^{-1}u(0)=\begin{bmatrix}{}\\{x_1}&{\dots}&{x_n}\\{}\end{bmatrix}\begin{bmatrix}{e^{\lambda_1t}}&{}&{}\\{}&{\ddots}&{}\\{}&{}&{e^{\lambda)n t}}\end{bmatrix}\begin{bmatrix}{c_1}\\{\vdots}\\{c_n}\end{bmatrix}$$
$e^{At}u(0)$의 solution
- $u(0)=c_1x_1+\dots+c_nx_n$을 쓰자, n개의 독립적인 고유벡터가 필요하다.
- $e^{\lambda_i t}$에 각 $x_i$를 곱하자
- $e^{At}u(0)$의 best form은 $u(t)=c_1e^{\lambda_1 t}x_1+\dots+c_ne^{\lambda_n t}x_n$
When you substitute $y = e^{\lambda t}$ into $y" - 2y' + y = 0$, you get an equation with repeated roots: $\lambda^2 - 2\lambda + 1 = 0 = (\lambda-1)$.
$$\text{Short series }e^{At}=e^{It}e^P-I{t=e^t[I+(A-I)t}$$
$$u(t)=e^t\begin{bmatrix}I+\begin{bmatrix}{-1}&{1}\\{-1}&{1}\end{bmatrix} t \end{bmatrix}u(0)$$
$$y(t) = e^ty(0) -te^ty(0) +te^t y[0]$$
Use the infinite series to find $e^{At}$ for $A=\begin{bmatrix}{0}&{1}\\{-1}&{1}\end{bmatrix}$. Notice that $A^4=I$
$$A=\begin{bmatrix}{0}&{1}\\{-1}&{1}\end{bmatrix}$$
$$e^{At}=\begin{bmatrix}{\cos t}&{\sin t}\\{\sin t}&{\cos t}\end{bmatrix}$$
The eigenvalues of eAt are e it and e-it . Three rules:
- $e^{At}$ always has the inverse $e^{-A}$t .
- The eigenvalues of $e^{At}$ are always $e^{\lambda t}$.
- When A is skew-symmetric, $e^{At}$ is orthogonal. Inverse = transpose = $e^{-At}.
Solve
$\frac{du}{dt}=Au=\begin{bmatrix}{1}&{1}\\{0}&{2}\end{bmatrix}u$ starting from $u(0)=\begin{bmatrix}{2}\\{1}\end{bmatrix}$ at t=0
Solution
$u(t)=e^t\begin{bmatrix}{1}\\{0}\end{bmatrix}+e^{2t}\begin{bmatrix}{1}\\{1}\end{bmatrix}$
REVIEW OF THE KEY IDEAS
WORKED EXAMPLES
Problem Set 6.3
I have to write "can be chosen" because the two in the plane are not automatically perpendicular.
This section makes that best possible choice for symmetric matrices: The eigenvectors of $P = P^T$ are perpendicular unit vectors.
What is special about $A x = \lambda x$ when A is symmetric?
- A와 trsnspose한 A가 같을 때 고유값 람다와 고유벡터 엑스의 특징을 볼거야
diagonalization $A=S\Lambda S^{-1}$는 A의 대칭을 반영할걸, $A^T=(S^{-1})^T \Lambda S^{T}$에서 힌트를 얻어볼까!
- A와 trsnpose A가 같다 했으니까.
- $S = S^{-1}$ 겠네?
- That makes each eigenvector in S orthogonal to the other eigenvectors.
- S의 각 고유 벡터를 다르 고유벡터와 직교하게 만듦!
key fact
- Asymmetric matrix has only real eigenvalues.
- The eigenvectors can be chosen orthonormal.
Its eigenvector matrix $S$ becomes an orthogonal matrix $Q$. Orthogonal matrices have $Q^{-l} = Q^T$
Why do we use the word "choose"? Because the eigenvectors do not have to be unit vectors.
Their lengths are at our disposal. We will choose unit vectors-eigenvectors of length one, which are orthnormal and not just orthogonal.
Then $S\Lambda S^{-1}$ is in its special and particular form $Q\Lambda Q^T$ for symmetric matrices:
(Special Theorem) 모든 대칭 행렬은 람다 행렬의 고유값들과 $S=Q$ 인 직교 고유벡터와 같이 factorization $A=Q\Lambda Q^T$을 가지고 있음
$$\text{Symmetric diagonalixation } A=Q\Lambda Q^{-1}=Q\Lambda Q^T \text{ with } Q^{-1} = Q^T$$
This is the "spectral theorem" in mathematics and the "principal axis theorem" in geometry and physics.
- By an example, showing real $\Lambda$'s in A and orthonormal $x$'s in $Q$.
- By a proof of those facts when no eigenvalues are repeated.
- By a proof that allows repeated eigenvalues (at the end of this section).
Find the $\lambda$'s and $x$'s when $A=\begin{bmatrix}{1}&{2}\\{2}&{4}\end{bmatrix}$ and $A-\lambda I = \begin{bmatrix}{1-\lambda}&{2}\\{2}&{4-\lambda}\end{bmatrix}$
Solution
- determinant of $A-\lambda I$인 $\lambda^2-5\lambda$로 고유값 0,5를 찾을 수 있지
- 두 고유 벡터는 (2,-1),(1,2)야.(orthogonal but not yet orthonormal.)
- 람다가 0일때 고유벡터는 A의 nullspace안에 있어.
- 람다가 5일때 고유벡터는 열공간column space 안에 있어.
- why are the nullspace and column space perpendicular?
- The Fundamental Theorem says that the nullspace is perpendicular to the row space-not the column space.
- 하지만 우리가 보는 행령은 대칭이잖아!
- 그래서 행과 열 공간은 같지.
These eigenvectors have length $\sqrt{5}$. Divide them by $\sqrt{5}$ to get unit vectors.
Put those into the columns of $S$ (which is $Q$). Then $Q^{-1} AQ$ is $\Lambda$ and $Q^{-1} = Q^T$:
$$Q^{-1}AQ = \frac{1}{\sqrt{5}}\begin{bmatrix}{2}&{-1}\\{1}&{2}\end{bmatrix} \begin{bmatrix} {1}&{2}\\{2}&{4} \end{bmatrix} \frac{1}{\sqrt{5}} \begin{bmatrix} {2}&{1}\\{-1}&{2} \end{bmatrix}=\begin{bmatrix}{0}&{0}\\{0}&{5}\end{bmatrix}=\Lambda$$
Now comes the $n$ by $n$ case. The $\lambda$'s are real when $A = A^T$ and $Ax = \lambda x$ .
Real Eigenvalues; All the eigen values of a real symmetric matrix are real
Orthogonal Eigenvectors; Eigenvectors of a real symmetic matrix (when they correspond to different $\lambda|'s)are always perpendeicular.
$$(\lambda_1x)^Ty = (Ax)^Ty=x^TA^Ty = x^TAy=x^T\lambda_2y$$
The eigenvectors of a 2 by 2 symmetric matrix have a special form:
Not widely known $A=\begin{bmatrix}{a}&{b}\\{b}&{c}\end{bmatrix}$ has $x_1=\begin{bmatrix}{b}\\{\lambda_1-a}\end{bmatrix}$ and $x_2=\begin{bmatrix}{\lambda_2-c}\\{b}\end{bmatrix}$
$$x_{1}^{T}x_2=b(\lambda_2-c)+(\lambda_1-a)b=b(\lambda_1+\lambda_2-a-c)=0$$
- $\lambda_1+\lambda_2$가 trace a+c와 같기 떄문에 0이다~
- $x_{1}^{T}x_2=0$이 되겠지?
- $x_1=x_2=0$일때, a=c,b=0
- 이 경우 A=I에서 고유값이 반복됨
This example shows the main goal of this section-to diagonalize symmetric matrices A by orthogonal eigenvector matrices $S = Q$. Look again at the result: $$\text{Symmetry } A=S\Lambda S^{-1} \text{ becomes } A=Q\Lambda Q^T \text{ with } Q^TQ=I$$
이는 모든 2 by 2 행렬이 이렇게 생겼다는 것을 의미 $$A=Q\Lambda Q^T = \begin{bmatrix}{}\\{x_1}&{x_2}\\{}\end{bmatrix} \begin{bmatrix} {\lambda_1}&{}\\{}&{\lambda_2}\end{bmatrix} \begin{bmatrix}{}&{x^{T}_{1}}&{}\\{}&{x_{2}^{T}}&{} \end{bmatrix}$$
$$\text{Sum of ranl-one matrics }A=\lambda_1x_1x_{1}^{T}+\lambda_2x_2x_{2}^{T}$$
- $x_ix_{i}^{T}$를 n번 곱하면 projection matrices임.
- Including the A's, the spectral theorem A = QAQT for symmetric matrices says that A is a combination of projection matrices: $$A=\lambda_1P_1+\dots+\lambda_nP_n \text{ } \lambda_i=\text{ eigenvalue, } P_i=\text{projection onto eigenspace}$$
For real matrices, complex $\lambda$'s and $x$'s come in "conjugate pairs." $$\text{If }Ax=\lambda x \text{ then } A\bar{x}=\bar{\lambda}\bar{x}$$
$$A=\begin{bmatrix}{\cos \theta} &{-\sin \theta}\\{\sin \theta} &{\cos \theta} \end{bmatrix} \text{ has } \lambda_1=\cos \theta + i \sin \theta \text{ and } \lambda_2 \cos \theta -i\sin \theta$$
$$\text{This is } \lambda x \text{ } Ax=\begin{bmatrix} {\cos \theta}&{-\sin \theta}\\{\sin \theta}&{\cos \theta}\end{bmatrix}\begin{bmatrix}{1}\\{-i}\end{bmatrix}=(\cos \theta + i \sin \theta) \begin{bmatrix}{1}\\{-i}\end{bmatrix})$$
$$\text{This is } \bar{\lambda}\bar{x} \text{ } A\bar{x}=\begin{bmatrix} {\cos \theta}&{-\sin \theta}\\{\sin \theta}&{\cos \theta}\end{bmatrix}\begin{bmatrix}{1}\\{i}\end{bmatrix}=(\cos \theta - i \sin \theta) \begin{bmatrix}{1}\\{i}\end{bmatrix})$$
For this rotation matrix the absolute value is $|\lambda|=1$, because $|cos^2 \theta + \sin^2 \theta = 1$. This fact $|\lambda| = 1$ holds for the eigenvalues of every orthogonal matrix.
$$product of pivots = determinant = product of eigenvalues.$$
We are assuming a full set of pivots d 1, ... , dn. There are n real eigenvalues AI, ... , An. The d's and A'S are not the same, but they come from the same matrix. This paragraph is about a hidden relation. For symmetric matrices the pivots and the eigenvalues have the same signs:
- The number of positive eigenvalues of $A = A^T$ equals the number of positive pivots. Special case: $A$ has all $\lambda_i > 0$ if and only if all pivots are positive.
The signs of the pivots match the signs of the eigenvalues, one plus and one minus. This could be false when the matrix is not symmetric.
- 대칭 행렬에서 pivot이 둘 중 한 개만 양수라면 고유값도 둘 중 한 개만 양수
- 비대칭행렬에서는 pivot이 둘 다 양수여도 고유값은 아닐 수 있으니 주의!
- the pivots and eigenvalues have matching signs,
- But to change sign, a real eigenvalue would have to cross zero.
- The matrix would at that moment be singular
- 어느 A의 고유값도 반복되지 않을 때, 고유벡터는 독립이 확실하다.
- 그러면 A는 대각화될 수 있다.
- 하지만 반복된 고유값은 고유벡터의 단점을 가질 수 있음
- 이건 비대칭 행렬에대해 일어나곤 함.
- 대칭 행렬에서는 절대 안 일어나는 일
- There are always enough eigenvectors to diagonalize $A = A^T$.
Here is one idea for a proof. Change A slightly by a diagonal matrix $diag( c , 2c, ... , n c)$. If c is very small, the new symmetric matrix will have no repeated eigenvalues. Then we know it has a full set of orthonormal eigenvectors. As $c \rightarrow 0$ we obtain n orthonormal eigenvectors of the original A-even if some eigenvalues of that A are repeated.
Schur's Theorem
- Every square matrixfactors into $A=QTQ^{-1}$ where $T$ is upper triangular and $\bar{Q}^{T} =Q-^{l.}$ If A has real eigenvalues then $Q$ and $T$ can be chosen real: $Q^T Q = I$
- 임의의 복소수 정사각 행렬을 상삼각 행렬로 나타내는 행렬 분해
- ?
REVIEW OF THE KEY IDEAS
WORKED EXAMPLES
Problem Set 6.4
Challenge Problems
This section concentrates on symmetric matrices that have positive eigenvalues.
Symmetric matrices with positive eigenvalues are at the center of all kinds of applications. They are called positive definite.
Here are two goals of this section:
- To find quick tests on a symmetric matrix that guarantee positive eigenvalues.
- To explain important applications of positive definiteness.
$$\text{Start with 2 by 2 When does } A=\begin{bmatrix}{a}&{b}\\{b}&{c}\end{bmatrix} \text{ have } \lambda_1>0 \text{ and } \lambda_2>0?$$
$$\text{The eigenvalues of A are positive if and only if } a>0 \text{ and } ac-b^2>0$$
Proof that the 2 by itest is passed when $\lambda_l > 0$ and $|lambda_2 > O$. Their product $\lambda_1 \lambda_2$ is the determinant so $ac - b^2 > O$. Their sum is the trace so $a + c > O$. Then $a$ and $c$ are both positive (if one of them is not positive, $ac - b^2 > 0$ will fail).
$$\text{The eigenvalues of } A = A^T \text{ are positive if and only if the pivots are positive: } a>0 \text{ and } \frac{ac-b^2}{a}>0$$
- $a > 0$은 위 두 test에서 모두 요구하는 조건!!
- 그래서 $ac>b^2$도 요구됨!
$$\begin{bmatrix}{1}&{b}\\{b}&{c}\end{bmatrix} \begin{matrix}{\text{The first pivot is a}}\\{\longrightarrow}\\{\text{The multiplier is b/a}}\end{matrix}\begin{bmatrix}{a}&{b}\\{0}&{c-\frac{b}{a}b}\end{bmatrix}\begin{matrix}{\text{The second pivot is}}\\{c-\frac{b^2}{a}=\frac{ac-b^2}{a}}\end{matrix}$$
Positive eigenvalues mean positive pivots and vice versa. 양수인 고유겂은 양수인 피벗을 의미하고 그 반대도 마찬가지!
The new idea is that $x^T A x$ is positive for all nonzero vectors x, not just the eigenvectors. In many applications this number $x^T Ax (or \frac{1}{2}x^TAx)$ is the energy in the system. The requirement of positive energy gives another definition of a positive definite matrix. I think this energy-based definition is the fundamental one.
Definition; A is positive definite if $x^TAx>0$ for every nonzero vector x $$x^TAx = \begin{bmatrix}{x}&{y}\end{bmatrix}\begin{bmatrix}{a}&{b}\\{b}&{c}\end{bmatrix}\begin{bmatrix}{x}&{y}\end{bmatrix}=ax^2 + 2bxy + cy^2 >0$$
This energy-based definition leads to a basic fact: If A and B are symmetric positive definite, so is A + B
- Reason: The pivots and eigenvalues are not easy to follow when matrices are added, but the energies just add
If the columns of R are independent, then $A = R^T R$ is positive definite.
- 여기서 $A = R^T R$은 square 이고 symmetric임
The number $x^T Ax$ is the same as $x^T R^T Rx$. That is exactly $(Rx)^T(Rx)$-another important proof by parenthesis! That vector $Rx$ is not zero when $x \neq 0$ (this is the meaning of independent columns). Then $x^TAx$ is the positive number $||Rx||^2$ and the matrix A is positive definite.
When a symmetric matrix has one of these five properties, it has them all:
- All n pivots are positive.
- All n upper left determinants are positive
- 1 by 1, w by 2,... , n by n
- All n eigenvalues are positive.
- $x^TAx$ is positive except at x = 0 This is the energy-based definition.
- A equals $R^TR$ for a matrix R with independent columns.
A,B가 positive definiteness일때, $$A=\begin{bmatrix}{2}&{-1}&{0}\\{-1}&{2}&{-1}\\{0}&{-1}&{2}\end{bmatrix} and, B=\begin{bmatrix}{2}&{-1}&{b}\\{-1}&{2}&{-1}\\{b}&{-1}&{2}\end{bmatrix}$$
- A의 pivot은 2, 3/2, 4/3 임! 모두 양수!
- 이것의 upper left determinants는 2,3,4이고 모두 양수!
- A 고유값은 $2-\sqrt{2},2,2+\sqrt{2}$로 모두 양수!
- $x^T Ax$도 양수! $$x^T Ax=2(x_{1}^{2}-x_1x_2+x_{2}^{2}-x_2x_3+x_{3}^{2}=2(x_1-\frac{1}{2}x_2)^2+\frac{3}{2}(x_2-\frac{2}{3}x_3)^2+\frac{4}{3}(x_3)^2$$
-
I have two candidates to suggest for $R$. Either one will show that $A = R^T$ R is positive definite. $R$ can be a rectangular first difference matrix, 4 by 3, to produce those second differences -1,2, -1 in $A$
- 여기서 R의 세 개 열은 모두 독립이고, A는 positive definite이다.
-
Another $R$ comes from $A = LDL^T$ (the symmetric version of $A = LU$). Elimination gives the pivots 2, 3/2, 4/3 in $D$ and the multipliers -1/2, 0, -2/3 in L. Just put $\sqrt(D)$ with $L$. $$LDL^T=(L\sqrt{D})(L\sqrt{D})^2=R^TR$$
- 여기서 R은 Cholesky factor!!
- 콜레스키 분해는 MATLAB에서 $R=chol(A)$로 계산된다.
- 정사각 R은 어떻게 A웅 만드는 방법이고, 이 콜레스키 R은 우리가 분해하는 방법이다.In applications, the rectangular R is how we build A and this Cholesky R is how we break it apart.
고유값은 대칭이 $R=Q\sqrt{\Lambda}Q^T$를 선택하게 한다. 또한 $R^TR=Q\Lambda Q^T$도 성공적!
Now tum to B, where the (1,3) and (3,1) entries move away from 0 to b.
- b는 너무 크면 안 된다.
- The determinant test은 가장 쉽다.
- 1 by 1 determinant 은 2이고, 2 by 2 determinant은 여전히 3이다. 3 by 3 determinant는 0을 포함한다.
- $det B = 4+2b-2b^2 = (1 +b)(4-2b)$must be positive.
- Often we are at the edge of positive definiteness.
- The determinant is zero.
- The smallest eigenvalue is zero.
- The energy in its eigenvector is $x^T Ax = x^TOX = O$.
- These matrices on the edge are called positive semidefinite.
- Positive semidefinite matrices have all $\lambda > 0$ and all $x^T Ax > O$.
- Those weak inequalities (> instead of > ) include positive definite matrices and the singular matrices at the edge.
$A = Q\Lambda Q^{-l} = Q\Lambda Q^T$:
- The tilted ellipse is associated with A. Its equation is $x^T Ax = 1$.
- The lined-up ellipse is associated with $\Lambda$. Its equation is $X^T \Lambda X = 1$.
- The rotation matrix that lines up the ellipse is the eigenvector matrix $Q$.
Find the axes of this tilted ellipse $5x^2 + 8xy + 5y^2 = 1$.
Solution
- Start with the positive definite matrix that matches this equation:
- 방정식은 $\begin{bmatrix} {x}&{y} \end{bmatrix} \begin{bmatrix} {5}&{4}\\{4}&{5} \end{bmatrix} \begin{bmatrix} {x}\\{y} \end{bmatrix} = 1$
- 행렬은 $A=\begin{bmatrix}{5}&{4}\\{4}&{5}\end{bmatrix}$
- 고유값은 9과 1
- 고유벡터는 $\begin{bmatrix}{1}\\{1}\end{bmatrix}$랑 $\begin{bmatrix}{1}\\{-1}\end{bmatrix}$
- 단위 벡터에 대해 $\sqrt{2}$로 나누면 $A=Q\Lambda Q^T$
- $x^TAx = 5x^2 + 8xy + 5y^2 = 9 \big( \frac{x+y}{\sqrt{2}} \big)^2 + 1 \big( \frac{x-y}{\sqrt{2}} \big)^2$
- 상관계수는 9와 1임(pivot 5와 9/5가 아니라)
The axes of the tilted ellipse point along the eigenvectors.
- This explains why $A = Q\Lambda Q^T$ is called the "principal axis theorem"-it displays the axes.
- Not only the axis directions (from the eigenvectors) but also the axis lengths (from the eigenvalues).
- To see it all, use capital letters for the new coordinates that line up the ellipse:
- $\frac{x+y}{\sqrt{2}}=X$ and $\frac{x-y}{\sqrt{2}}=Y$ and $9X^2+Y^2=1$
- The bigger eigenvalue $\lambda_1$ gives the shorter axis, of half-length $1 /\sqrt{\lambda_1}$ = 1/3.
- The smaller eigenvalue $\lambda_2 = 1$ gives the greater length $1/\sqrt{\lambda_1} = 1.$
- In the xy system, the axes are along the eigenvectors of A.
- In the XY system, the axes are along the eigenvectors of A-the coordinate axes
- All comes from $A = Q\Lambda Q^T$.
REVIEW OF THE KEY IDEAS
WORKED EXAMPLES
Problem Set 6.5
Challenge Problems
The key step in this chapter is to diagonalize a matrix by using its eigenvectors.
- $S$는 고유벡터 행렬
- $S^{-1}AS$는 $\Lambda$(고유값 행렬)
- 하지만 대각화는 모든 A에 대해 가능하진 않음
- 어떤 행렬은 고유벡터가 너무 작게 가지고 있기도 함
- 고유벡터 행렬 S는 위의 상황을 해결하기 위한 best choice이지만 지금 우리는 어느 역행렬 M이든 허용함(?) In this new section, the eigenvector matrix S remains the best choice when we can find it, but now we allow any invertible matrix M
- 어떤 M을 선택하든지간에 고유값은 같음!
$$\text{DEFINITION; Let M be all y invertible.matrlx. Then }B = M^{- 1} AM \text{ is similar to }A.$$
If $B = M^{ -1} A M$ then immediately $A = M B M^{ -1}$. That means: If $B$ is similar to $A$ then $A$ is similar to $B$.
대각화할 수 있는 행렬음 $\Lambda$와 유사함. In that special case M is S.
We have $A = S\Lambda ^{S-1}$ and $\Lambda = S^{-1} AS$. They certainly have the same eigenvalues!
$M^{-1}AM$은 differential equation에서 변수에 변화를 줄 떄 나타난다.
- $u=Mv$라고 하면,
- $\frac{du}{dt}=Au$ 는 $M\frac{dv}{dt}=AMv$가 되고, 그건 $\frac{dv}{dy}=M^{-1}amV$임
- 원래 상관계수 행렬은 A였는데 새로운 상관계수 행렬은 $M^{-1}AM$임
- u가 v로 변하는 것은 유사한 행렬으로 이끄는 것과 같음
- 할상 u로 돌아갈 수 있기 때문에,
- 유사한 행렬은 같기 growth되거나 decay 해야한다. 더 자세하게 말하자면,A와 B의 고유값은 같다.
(No .change in $\Lambda$'s) Similar matrices A and $M^{-1}$ have the same eigenvalues. If x is an eigenvector of A, $M^{-1}x$ is an eigenvector of $=M^{-1}AM$.
- The proof is quick, since $B = M^{-1} AM$ gives $A = MBM^{- 1}$. Suppose $Ax = \lambda X$:
- $MBM^{-1}x=\lambda x$ means that $B(M^{-1}x)=\lambda(M^{-1}x)$
The eigenvalue of $B$ is the same $\lambda$.
The eigenvector has changed to $M^{-1}x$.
Two matrices can have the same repeated $\lambda$, and fail to be similar-as we will see
These matrices $M^{-1}AM$ all have the same eigenvalues 1 and 0. $$\text{The projection } A = \begin{bmatrix}{.5}&{.5}\\{.5}&{.5}\end{bmatrix} \text{ is similar to }\Lambda = S^{-1}AS = \begin{bmatrix}{1}&{0}\\{0}&{0}\end{bmatrix}$$ $$\text{Now choose } M = \begin{bmatrix}{1}&{0}\\{1}&{2}\end{bmatrix} \text{. The similar matrix } M^{-1}AM \text{ is } \begin{bmatrix}{1}&{1}\\{0}&{0}\end{bmatrix}$$ $$\text{Also choose } M = \begin{bmatrix}{0}&{-1}\\{1}&{0}\end{bmatrix} \text{. The similar matrix } M^{-1}AM \text{ is } \begin{bmatrix}{.5}&{-.5}\\{-.5}&{.5}\end{bmatrix}$$
- 고유값 1,0을 가진 모든 2 * 2 행렬은 서로 유사하다.
- 고유 벡터는 M에 의해 변하고, 고유값은 변하지 않는다.
The zero matrix shares those eigenvalues, but it is similar only to itself: $M^{-1}0M = 0$.
A family of similar matrices with A = 0, 0 (repeated eigenvalue) $$A=\begin{bmatrix}{0}&{-1}\\{0}&{0}\end{bmatrix} \text{ is similar to }\begin{bmatrix}{1}&{-1}\\{1}&{-1}\end{bmatrix}\text{ and all }B=\begin{bmatrix}{cd}&{d^2}\\{-c^2}&{-cd}\end{bmatrix} \text{ except } \begin{bmatrix}{0}&{0}\\{0}&{0}\end{bmatrix}$$
- 이 매트릭스 B는 모두 0 determinant(A와 같은)를 가지고 있다.
- 모두 A와 같이 rank one을 가지고 있다.
- 한 고유값은 0이고, trace는 cd-dc=0이어서 다른 고유값도 0이어야 한다,
$$M=\begin{bmatrix}{a}&{b}\\{c}&{d}\end{bmatrix}\text{ with } ad-bc=1,\text{, and }B=M^{-1}AM$$
- 행렬 B는 대각화할 수 없다.
- A는 가능한한 대각화에 가깝게 해야한다.
- 이건 행렬 B의 family에 대한 조르단 형식Jordan form이다.
- 오직 한 고유벡터만 있을때, Jordan form J=A는 이 행렬을 대각화할만큼 근접하다.
- $A$에서 $B=M^{-1}AM$에 가는동안 어떤 것은 변하고 어떤 것은 변하지 않는다.
- 변하는 것: Eigenvectors, Nullspace , Column space , Row space , Left nullspace , Singular values
- 변하지 않는 것: Eigenvalues , Trace and determinant , Rank , Number of independent eigenvectors , Jordan form
- 고유값과 고유벡터는 유사한 메트릭스에서 변하지 않는다.
- trace는 변하지 않는 고유값들의 합이다.
- determinanat는 같은 고유값들의 곱이다.
- nullspace는 고유값이 0인게 하나라도 존재하는 고유벡터로 구성되어 있어서 변할 수 있다.
- 이 차원은 n-r이고, 변하지 않는다!
- 벡터들이 스스로 $M^{-1}$에 곱해지는 동안 고유벡터는 각 고유값에서 같다.
- singular 값은 $A^TA$에 의존하고, 명확하게 변한다.
We lead up to it with one more example of similar matrices: triple eigenvalue, one eigenvector.
This Jordan matrix $J$ has $\lambda = 5,5,5$ on its diagonal. Its only eigenvectors are multiples of $x = (1,0,0)$. Algebraic mUltiplicity is 3, geometric multiplicity is 1: $$\text{If }J=\begin{bmatrix}{5}&{1}&{0}\\{0}&{5}&{1}\\{0}&{0}&{5}\end{bmatrix} \text{ then } J-5I=\begin{bmatrix}{0}&{1}&{0}\\{0}&{0}&{1}\\{0}&{0}&{0}\end{bmatrix} \text{ has rank 2}$$
- 모든 유사한 행렬 $B=M^{-1}JM$ 은 같은 세 고유값 5,5,5를 가지고 있다.
- 또한, $B-5I$는 같은 rank 2를 가져야만 한다.
- nullspace는 차원1을 가지고 있다.
- Jordan block인 J와 규사한 모든 B는 유일한 하나의 독립적인 고유벡터 $M^{-1}x$를 가지고 있다.
Jordan's theorem에서는 $J^t$가 $J$와 유사하다고 말한다. 유사함을 제공하는 행렬 M은 reverse identity가 된다. $$J^T=M^{-1}JM\text{ is } \begin{bmatrix}{5}&{0}&{0}\\{1}&{5}&{0}\\{0}&{1}&{5}\end{bmatrix} = \begin{bmatrix}{}&{}&{1}\\{}&{1}&{}\\{1}&{}&{}\end{bmatrix} \begin{bmatrix}{5}&{1}&{0}\\{0}&{5}&{1}\\{0}&{0}&{5}\end{bmatrix} \begin{bmatrix}{}&{}&{1}\\{}&{1}&{}\\{1}&{}&{}\end{bmatrix}$$
- 모든 빈 entries는 0이다.
- $J^T$의 고유백터는 $M^{-1}(1,0,0)=(0,0,1)$이다.
- J에서 고유벡터 one line $(x_1,0,0)$과 $J^T$에서 another line $(0,0,x_3)$이 있다.
The key fact is that this matrix $J$ is similar to every matrix $A$ with eigenvalues 5,5,5 and one line of eigenvectors.
There is an $M$ with $^{-1}AM = J$.
Since $J$ is as close to diagonal as we can get, the equation $\frac{du}{dt} = J u$ cannot be simplified by changing variables. We must solve it as it stands: $$\frac{du}{dt}=Ju=\begin{bmatrix}{5}&{1}&{0}\\{0}&{5}&{1}\\{0}&{0}&{5}\end{bmatrix}\begin{bmatrix}{x}\\{y}\\{z}\end{bmatrix} \text{ is } \begin{matrix}{dx/dt=5x+y}\\{dy/dt=5y+z}\\{dz/dt=5z}\end{matrix}$$
- system은 triangular이다. $$\text{Last equation }\frac{dz}{dt}=5z \text{yields } z=z(0)e^{5t}$$ $$\text{Notice }te^{5t}\text{ }\frac{dy}{dt}=5y+z \text{yields } y=(y(0)+tz(0))e^{5t}$$ $$\text{Notice }t^2e^{5t}\text{ }\frac{dx}{dt}=5x+y \text{yields } x=(x(0)+ty(0)+\frac{1}{2}t^2z(0))e^{5t}$$
- The two missing eigenvectors are responsible for the teSt and t 2eSt terms in y and x.
- The factors t and t 2 enter because A = 5 is a triple eigenvalue with one eigenvector.
- 모든 A에 대해 우리는 M을 선택해서 $M^{-1}AM$이 가능한한 대각화에 근접하기를 원한다.
- A가 n개 고유벡터들의 전체 집합일때, M의 열들이 고유벡터가 된다.(When A has a full set of n eigenvectQrs, they go. into. the cQlumns Qf M. )
- 그러면 M=S가 된다.
- 행렬 $S^{-1}AS$는 대각화되어 있다.
- 행렬 $\Lambda$는 A의 조르단 형식이다.(A가 대각화될 수 있다면.)
- 일반적으로 고유벡터는 결측이고, 고유값 집합은 얻을 수 없다(In the general case, eigenvectors are missing and A can't be reached. ).
(Jordan form) If A has s independent elegevectors, it is similar to a matrix $J$ that has s Jordan blocks on its diagonal: Some matrix M plus A into Jordan form: $$\text{Jordan form }M^{-1}AM=\begin{bmatrix}{J_1}&{}&{}\\{}&{\ddots}&{}\\{}&{}&{J_s}\end{bmatrix}=J$$
- J에서 각 block은 하나의 고유값 람다, 고유벡터, 그리고 위 대ㅏㄱ에서 1들을 가지고 있다. $$\text{Jordan block }J_i=\begin{bmatrix}{\lambda_i}&{1}{}&{}\\{}&{\cdot}&{\cdot}&{}\\{}&{}&{\cdot}&{1}\\{}&{}&{}&{\lambda_i}\end{bmatrix}$$
- 만일 같은 jordan form J를 가지고 있다면, A는 B와 유사하다.
- Jordam form J는 결측 고유벡터에 대해 off-diagonal 1을 가지고 있다.
- 이는 행렬 유사성에 대한 big theotem이다.
- 유사한 행렬의 모든 family에서 J라고 불리는 특정 member를 선택한다,
- 그건 대각화와 근사하다.
- J에 대해 du/dt=Ju를 ex4에서 풀 수 있었다.
- family에서 모두 다른 행렬은 form $A=MJM^{-1}$을 가지고 있다.
- M을 통한 연결은 du/dt=Au를 해결한다.
- $MJM^{-1}MJM^{-1}=MJ^2M^{-1}$
REVIEW OF THE KEY IDEAS
WORKED EXAMPLES
Problem Set 6.6
Challenge ProblemsS
A is any m by n matrix, square or rectangular. Its rank is r. We will diagonalize this $A$, but not by $S^{-1} AS$.
- 특이값 분해
- 고유벡터 s는 3가지 큰 문제가 있다.
- 항상 직교가 아니며
- 항상 충분한 고유벡터를 가지고 있지 않으며,
- $Ax=\lambda x$는 A가 squre이기를 원한다.
The $u$'s are eigenvectors of $AA^T$ and the $v$'s are eigenvectors of $A^T A$.
- 행렬이 둘 다 대칭이기 때문에 이 고유벡터들은 직교로 선택될 수 있다.
- In equation (13) below, the simple fact that $A$ times $A^T A$ is the same as $AA^T$ will lead to a remarkable property of these u's and v's: $$\text{"A is diagonalized" } Av_1=\sigma_1u_1\text{ } Av_2=\sigma_2u_2\text{ }\dots Av_r=\sigma_r u_r$$
- The singular vectors $v_1, ... , v_r$ are in the row space of $A$.
- The outputs $u_1 , ... , u_r$ are in the column space of $A$.
- The singular values $\sigma_1\dots \sigma_r$ are all positice numbers
- When the v'S and u's go into the columns of V and U, orthogonality gives $V^T V = I$ and $U^T U = I$.
- The $\sigma$'s go into a diagonal matrix $\sum$
$Ax_i=\lambda_i x_i$가 대각 $AS=A\Lambda$로 이끌기 떄문에, 방정식 $Av_i=\sigma_i u_i$는 $AV=U \Sigma$에서 column by column이라 말한다. $$\begin{matrix} { \text{(m by n)(n by r)}} \\{\text{equals}}\\{\text{(m by r)(r by r)}}\end{matrix} A\begin{bmatrix}{}\\{v_1,\dots v_r}\\{}\end{bmatrix}= \begin{bmatrix}{}\\{u_1\dots u_r}\\{}\end{bmatrix} \begin{bmatrix}{\sigma_1}&{}&{}\\{}&{\ddots}&{}\\{}&{}&{\sigma_r}\end{bmatrix}$$
- v와 u는 A의 행과 열 공간을 차지하기도 함
- nullspace N(A)와 왼쪽 nullspace$N(A^T)$로부터 더 많은 v를 위해 n-r이 필요하고, u를 위해 m-r이 필요하다.
- 두 공간이 직교가 된다면 자동적으로 v들과 u들은 직교가 된다.
- 그래서 행렬은 sqaure가 되고, $AV=U\Sigma$을 얻게 된다. $$\begin{matrix} { \text{(m by n)(n by n)}} \\{\text{equals}}\\{\text{(m by m)(m by n)}}\end{matrix} A\begin{bmatrix}{}\\{v_1,\dots v_r \dots v_n}\\{}\end{bmatrix}= \begin{bmatrix}{}\\{u_1\dots u_r \dots u_m}\\{}\end{bmatrix} \begin{bmatrix}{\sigma_1}&{}&{}&{}\\{}&{\ddots}&{}&{}\\{}&{}&{\sigma_r}&{}\\{}&{}&{}&{}\end{bmatrix}$$
- 새로운 $\Sigma$은 m by n 행렬
- m-r개의 새로운 0행과 n-r개의 새로운 0 행을 가진 기존의 r * r 행렬이다.
- $V^TV=I$dhk $U^TU=I$는 유지되고,크기는 n과 m이다.
- V는 이제 $V^{-1}=V^T$인 직각 직교 행렬이다.
- $AV=U\Sigma$은 $A=U\Sigma V^T$가 될 수 있다.
Singular Value Decomposition: $$\text{SVD } A=U\Sigma V^T = u_1\sigma_1 v^{T}_{1}+\dots+u_r\sigma_r v^{T}_{r}$$
This reduced SVD gives the same splitting of A into a sum of r matrices, each of rank one.
We will see that $\sigma^{2}_{i}$ is an eigenvalue of $A^T A$ and also $AA^T$. When we put the singular values in descending order, $\sigma_1 > \sigma_2 > ... \sigma_r > 0$, the splitting in equation (4) gives the r rank -one pieces of A in order of importance.
When is $U\Sigma V^T$ (singular values) the same as $\Lambda AS^{-1}$ (eigenvalues)?
solution
- S=U에서 직교 고유벡터가 필요하다. $\Lambda= \Sigma$에서 음수가 아닌 고유값들이 필요하다.
- A는 positive semidefinite (or definite) symmetric matrix $Q\Lambda Q^T$여야 한다.
If $A = xy^T$ with unit vectors $x$ and $y$, what is the SVD of A?
solution
- 기존 $\Sigma$있는 식에서 감소한 SVD는 rank=1을 가진 $xy^T$이지.
- 이건 $u_1=x$, $v_1=y$, $\sigma_1=1$를 가져.
- 전체 SVD에서 $u_1=x$를 u의 직교 basis에서 complete하고, v의 직교 basis에서 $v_1=y$로 coplete해.(For the full SVD, complete $u_l = x$ to an orthonormal basis of u's, and complete $v_1 = y$ to an orthonormal basis of v's. No new O"s. )
What is compression?
- We want to replace those 217 matrix entries by a smaller number, without losing picture quality
try an SVD approach: Replace the 256 by 512 pixel matrix by a matrix of rank one: a column times a row. If this is successful, the storage requirement becomes 256 + 512 (add instead of multiply). The compression ratio (256)(512)/(256 + 512) is better than 170 to 1. This is more than we hope for. We may actually use five matrices of rank one (so a matrix approximation of rank 5). The compression is still 34 : 1 and the crucial question is the picture quality.
Where does the SVD come in? The best rank one approximation to A is the matrix $\sigma_1 u_1 v_{1}^{T}$. It uses the largest singular value $\sigma_1$. The best rank 5 approximation includes also $\sigma_2 u_2 v_{2}^{T} + ... + \sigma_5 u_5 v_{5}^{T}$, The SVD puts the pieces of A in descending order.
- Start with a 2 by 2 matrix. Let its rank be r = 2, so A is invertible.
- We want $v_1$ and $v_2$ to be perpendicular unit vectors.
- We also want $Av_1$ and $Av_2$ to be perpendicular.
- Then the unit vectors $U_l = Av_1/||Av_1||$ and $u_2 = Av_2/||Av_2||$ will be orthonormal. $$\text{Unsysmmetric matrix }A=\begin{bmatrix}{2}&{2}\\{-1}&{1}\end{bmatrix}$$
- No orthogonal matrix $Q$ will make $Q^{-l} AQ$ diagonal.
- We need $U^{-1} AV$.
- The two bases will be different-one basis cannot do it.
- The output is $Av_1 = \sigma_1 u_1$ when the input is $v_1$.
- The "singular values" $\sigma_1$ and $\sigma_2$ are the lengths $||Av_1||$ and $||Av_2||$. $$\begin{matrix}{AV=U\Sigma}\\{A=U\Sigma V^T}\end{matrix}\text{ } A\begin{bmatrix}{v_1} &{v_2}\end{bmatrix}=\begin{bmatrix}{\sigma_1u_1}&{\sigma_2u_2}\end{bmatrix}=\begin{bmatrix}{u_1}&{u_2}\end{bmatrix}\begin{bmatrix}{\sigma_1}&{}\\{}&{\sigma_2}\end{bmatrix}$$
$$A^T A=(U\Sigma V^T)^T (U\Sigma V^T)=V\Sigma {}^T\Sigma {V}^T$$
- $U^T U$ disappears because it equals I.
- uT U disappears because it equals I.
- Multiplying those diagonal $\Sigma{}^T$ and $\Sigma$ gives $\sigma_{1}^{2}$ and $\sigma_{2}^{2}$.
- That leaves an ordinary diagonalization of the crucial symmetric matrix $A^T A$, whose eigenvalues are $\sigma_{1}^{2}$ and $\sigma_{2}^{2}$: $$\begin{matrix}{\text{Eigenvalues }\sigma_{1}^{2}, \sigma_{2}^{2}}\\{\text{Eigenvectors }v_1, v_2}\end{matrix} \text{ }A^T A=V\begin{bmatrix}{\sigma_{1}^{2}}&{0}\\{0}&{\sigma_{2}^{2}}\end{bmatrix}V^T$$
- 이건 $A=Q\Lambda Q^T$와 같아
- 하지만 대칭 행렬은 A itself가 아니지
- 이제 대칭 행렬은 $A^T A$야
- 그리고 V의 열들은 $A^TA$의 고유벡터이고. Last is $U$...
Find the singular value decomposition of that matrix $A=\begin{bmatrix}{2}&{2}\\{-1}&{1}\end{bmatrix}$
Solution
- $A^TA$와 그 고유벡터를 계산하자
- 그러면 unit vector가 나와 $$A^TA=\begin{bmatrix}{5}&{3}\\{3}&{5}\end{bmatrix}\text{ has unit eigenvectors }v_1=\begin{bmatrix}{1/\sqrt{2}}\\{1/\sqrt{2}}\end{bmatrix} \text{ and } v_2=\begin{bmatrix}{-1/\sqrt{2}}\\{1/\sqrt{2}}\end{bmatrix}$$
- $A^TA$의 고유값들은 8하고 2임
- v들은 직교야. 왜냐하면 모든 대칭 행렬의 고유 벡터는 직교이기 떄문이지!
- 그리고 $A^TA$는 자동적으로 대칭이 돼 $$Av_1=\begin{bmatrix}{2}&{2}\\{-1}&{1}\end{bmatrix}\begin{bmatrix}{1/\sqrt{2}}\\{1/\sqrt{2}}\end{bmatrix}=\begin{bmatrix}{2\sqrt{2}}\\{0}\end{bmatrix}\text{. The unit vector is } u_1=\begin{bmatrix}{1}\\{0}\end{bmatrix} $$
- $Av_1$은 $2\sqrt{2} u_1$과 같지
- 처음 특이값singular value는 $\sigma_1 = 2\sqrt{2}$임. 그러면 $\sigma_{1}^{2}=8$이 돼. $$Av_2=\begin{bmatrix}{2}&{2}\\{-1}&{1}\end{bmatrix}\begin{bmatrix}{-1/\sqrt{2}}\\{1/\sqrt{2}}\end{bmatrix}=\begin{bmatrix}{0}\\{\sqrt{2}}\end{bmatrix}\text{. The unit vector is } u_2=\begin{bmatrix}{0}\\{1}\end{bmatrix} $$
- $Av_2$는 $\sqrt{2}u_2$이고 $]sigma_2=\sqrt{2}$임.
- 그러면 $\sigma_{2}^{2}$는 $A^T A$의 다른 고유값 2에 agree 하지... $$A=U\Sigma V^T \text{ is }\begin{bmatrix}{2}&{2}\\{-1}&{1}\end{bmatrix}=\begin{bmatrix}{1}&{0}\\{0}&{1}\end{bmatrix}\begin{bmatrix}{2\sqrt{2}}&{}\\{}&{\sqrt{2}}\end{bmatrix}\begin{bmatrix}{1/\sqrt{2}}&{1/\sqrt{2}}\\{-1/\sqrt{2}}&{1/\sqrt{2}}\end{bmatrix}$$
- 이 행렬과 모든 역을 취할 수 있는 2 * 2 행렬은 단위 원을 타원으로 변환한다!
We found the u's from the v's. Could we find the u's directly? Yes, by multiplying $AA^T$ instead of $A^T A$: $$\text{Diagonal in this example } A A^T = \begin{bmatrix}{2}&{2}\\{-1}&{1}\end{bmatrix}\begin{bmatrix}{2}&{-1}\\{2}&{1}\end{bmatrix}= \begin{bmatrix}{8}&{0}\\{0}&{2}\end{bmatrix}$$
- 이 고유벡터 (1,0)과 (0,1)은 $u_1,u_2$를 빨리 찾을 수 있게 하지!
- 왜 처음 고유벡터가 (-1,0)이나(0,1) 대신에 (1,0)이 될까?
- 우리는 $Av_1$를 따라야 하기 때문이지!
- $AA^T$는 $A^TA$와 같은 고유값 8,2를 가져
- 그 특이값은 $\sqrt{8},\sqrt{2}$야
Find the SVD of the singular matrix $A = \begin{bmatrix}{2}&{2}\\{1}&{1}\end{bmatrix}$. The rank is r = 1.
Solution
- 행 공간은 오직 한 basis 벡터 $v_1=(1,1)/\sqrt{2}$를 가지고 있지.
- 그 열 공간은 오직 한 basis 벡터 $u_1=(2,1)/\sqrt{5}$를 가지고 있고.
- 그러면 $Av_1=(4,2)/\sqrt{2}$는 $\sigma_1 u_1$과 같아야 해.
- 그러면 $\sigma_1=\sqrt{10}$
행렬 U와 V는 모든 4개의 준공간에서 직교 기반을 포함한다.
- V의 열에서 첫 r 은 A의 행 공간
- V의 열에서 마지막 n-r은 A의 영공간
- U의 열에서 첫 r은 A의 열공간
- U의 열에서 마지막 n-r은 $A^T$의 영공간
The first columns $v_1, ... ,v_r$ and $u_1, ... ,u_r$ are eigenvectors of $A^T A$ and $AA^T$. We now explain why AVi falls in the direction of $u_i$. The last v's and u's (in the nullspaces) are easier. As long as those are orthonormal, the SVD will be correct.
Section 6.1 described the MATLAB demo called eigshow.
Search engines are link-based more than content-based.
REVIEW OF THE KEY IDEAS
WORKED EXAMPLES
Problem Set 6.7
Challenge Problems