선형대수(HYU) 18_고유값과 고유벡터 및 대각화

Chapter 5. Eigenvalues and Eigenvectors

5.1 Introduction

first half of linear algebra: $Ax=b$

second half: $Ax=\lambda x$

• 여전히 matrix를 simplify해서 해결
• matrix를 diagonal로 simplify
• no more row exchanges: elimination은 eigenvalue($\lambda$)를 바꾸기 때문
• determinant를 이용

Fundamental equation

$$Ax=\lambda x$$

• number $\lambda$: matrix $A$의 eigenvalue
• vector $x$: matrix $A$의 eigenvector

The Solution of $Ax=\lambda x$

---

$\lambda x$를 $\lambda Ix$로 생각하면 $Ax=\lambda x$를 다음과 같이 쓸 수 있다.

$$(A-\lambda I)x=0$$

위와 같은 문제의 key는 다음과 같다.

• vector $x$는 $A-\lambda x$의 nullspace이다.
  
• number $\lambda$는 $A-\lambda x$가 nullspace를 가질 수 있는 값으로 선택된다.

모든 matrix는 nullspace를 갖지만 목표는 nonzero eigenvector $x$를 구하는 것이다.

• $x=0$인 equation의 solution으로서 가치가 거의 없다.
• 관심이 있는 것은 nonzero eigenvector $x$를 만드는 특정한 값 $\lambda$이다.
• 즉, $A-\lambda I$가 singular이어야 한다.

number $\lambda$는 $A-\lambda I$가 singular일 때만 $A$의 eigenvalue이다.
$$det(A-\lambda I)=0$$
각 $\lambda$는 eigenvector $x$와 연관이 있다
$$(A-\lambda I)x=0orAx=\lambda x$$

Example

$$\begin{array}{rl}\text{Subtract }\lambda I& A=\left[\begin{array}{cc}4& -5\\ 2& -3\end{array}\right],A-\lambda I=\left[\begin{array}{cc}4-\lambda & -5\\ 2& -3-\lambda \end{array}\right]\\ \text{Determinant}& det(A-\lambda I)=(4-\lambda )(-3-\lambda )+10={\lambda }^2-\lambda -2\end{array}$$

위 polynomial의 근이 determinant를 0으로 만드는 eigenvalue 값이다.

$$\lambda =2or\lambda =-1$$

• Singular인 (i.e. determinant = 0) $A-\lambda I$의 nullspace 에는 nonzero vector $x$가 존재한다.

$$\begin{array}{rl}{\lambda }_1=-1:& (A-{\lambda }_{1}I)x=\left[\begin{array}{cc}5& -5\\ 2& -2\end{array}\right]\left[\begin{array}{c}y\\ z\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right],x_1=\left[\begin{array}{c}1\\ 1\end{array}\right]\\ {\lambda }_2=2:& (A-{\lambda }_{1}I)x=\left[\begin{array}{cc}5& -5\\ 2& -2\end{array}\right]\left[\begin{array}{c}y\\ z\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right],x_2=\left[\begin{array}{c}5\\ 2\end{array}\right]\end{array}$$

• $A-{\lambda }_{1}I$의 column은 $x_2$의 $A-{\lambda }_{2}I$의 columne은 $x_1$의 multiple이다.
  • 2 by 2 matrix에서 유용

$A-\lambda I$의 nullspace는 (i.e., eigenspace) 모두 $Ax=\lambda x$를 만족한다. 위의 예시에서 eigenspace는 $x_1=(1,1)$, $x_2=(5,2)$를 지나는 line이다.

Steps in solving $Ax=\lambda x$

1. Compute the determinant of $A-\lambda I$
   • diagonal을 따라서 $\lambda$을 뺀 matrix로 determinant는 $n$ degree polynomial이다.
2. Find the roots of this polynomial
   • $n$개의 근이 $A$의 eigenvalue
3. For each eigenvalue solve the equation $(A-\lambda I)x=0$
   • determinant가 zero이므로 nonzero $x$가 존재하며 이것이 eigenvector이다.

Example 3

$A$가 triangular인 경우
$A=\left[\begin{array}{ccc}1& 4& 5\\ 0& \frac{3}{4}& 6\\ 0& 0& \frac{1}{2}\end{array}\right]$

$A$가 triangular이면 eigenvalue는 main diagonal에 존재한다.

$$det(A=\lambda I)=\left|\begin{array}{ccc}1-\lambda & 4& 5\\ 0& \frac{3}{4}-\lambda & 6\\ 0& 0& \frac{1}{2}-\lambda \end{array}\right|=(1-\lambda )(\frac{3}{4}-\lambda )(\frac{1}{2}-\lambda )$$

determinant가 diagonal entry의 곱이므로 determinant를 0으로 만드는 $\lambda$값은

$$\lambda =1,\lambda =\frac{3}{4},or\lambda =\frac{1}{2}$$

위의 예시로부터 알 수 있는 한 가지 핵심은 $A$를 eigenvalue 변화'없이' diagonal이나 triangular matrix로 바꾸는 것이다.

다만, eigenvalue 자체를 구하기는 어렵고

• Gaussian elimination은 이 경우엔 소용이 없다.
• eigenvalue를 구할 수 있는 별도의 formula도 존재하지 않는다.

eigenvalue에 대한 몇 가지 간단한 정보를 얻을 수 있다: sum & product

n개의 eigenvalue의 합(sum) 은 n개의 diagonal entry의 합과 같다.
$$\text{Trace of}A={\lambda }_1+\cdots +{\lambda }_n=a_{11}+\cdots +a_{nn}$$
n개의 eigenvalue의 곱(product) 은 $A$의 determinant와 같다
$$\text{Determinant of}A={\lambda }_1\cdots {\lambda }_n=productofpivots$$

proof

$det(A-\lambda I)=0$이 n개의 근 ${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$을 갖는다고 가정하자.

$$\begin{array}{rl}det(A-\lambda I)& =({\lambda }_1-\lambda )({\lambda }_2-\lambda )\cdots ({\lambda }_n-\lambda )=0\\ & =(-\lambda {)}^n+({\lambda }_1+{\lambda }_r+\cdots +{\lambda }_n)(-\lambda {)}^{n-1}+\cdots +{\lambda }_1{\lambda }_2\cdots {\lambda }_n\\ & \cdots (1)\\ det(A-\lambda I)& =\left|\begin{array}{cccc}{a}_{11}-\lambda & a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}-\lambda & \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}-\lambda \end{array}\right|\end{array}$$

• (1)에서 $\lambda =0$일 경우 $det(A-\lambda I)=detA={\lambda }_1{\lambda }_2\cdots {\lambda }_n$

$det(A-\lambda I)$를 다음과 같이 나타낼 수도 있다.

$$det(A-\lambda I)=(a_{11}-\lambda )C_{11}+a_{12}{C}_{12}+\cdots +a_{1n}{C}_{1n}$$

여기서,

$$\begin{array}{rl}{C}_{11}& =(-1{)}^{1+1}\left|\begin{array}{cccc}{a}_{22}-\lambda & a_{23}& \cdots & a2n\\ a_{32}& a_{33}-\lambda & \cdots & a_{3n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n2}& a_{n3}& \cdots & a_{nn}-\lambda \end{array}\right|\\ & =(-\lambda {)}^{n-1}+(\cdots )(-\lambda {)}^{n-2}+\cdots \\ C_{12}& =(-1{)}^{1+2}\left|\begin{array}{cccc}{a}_{21}& a_{23}& \cdots & a2n\\ a_{31}& a_{33}-\lambda & \cdots & a_{3n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n3}& \cdots & a_{nn}-\lambda \end{array}\right|\\ & =a_{21}(-\lambda {)}^{n-2}+(\cdots )(-\lambda {)}^{n-3}+\cdots \end{array}$$

이므로 (1)의 $(-\lambda {)}^n$과 $(-\lambda {)}^{n-1}$ 항은 $(a_{11}-\lambda )C_{11}$에서만 발생한다.

정리하면,

$$\begin{array}{rl}det(A-\lambda I)& =(a_{11}-\lambda )(a_{22}-\lambda )\cdots (a_{n-1n-1}-\lambda )(a_{nn}-\lambda )+\cdots \\ & =(-\lambda {)}^n+(a_{11}+a_{22}+\cdots +a_{nn})(-\lambda {)}^{n-1}+\cdots \\ & \cdots (2)\end{array}$$

• (1) = (2)에서 모든 $(-\lambda {)}^1$, $(-\lambda {)}^2$, $\cdots$, $(-\lambda {)}^n$에 대해서
  $$\sum _{i=1}^n{\lambda }_i=\sum _{i=1}^n{a}_{ii}$$

Eigshow

---

강의에서 다루지 않음.

5.2 Diagonalization of a Matrix

---

• Another matrix decomposition method.
• The eigenvectors diagonalize a matrix.

n개의 linearly independent eigenvector ($e_i$) 를 갖는 n by n matrix $A$를 가정하자. (i.e., $A{e}_i=\lambda e_i$)

이 eigenvector를 column으로 하는 matrix $S$에 대해 $S^{-1}AS$ 는 diagonal matrix $\mathrm{\Lambda }$ 이다.

$$S=\left[\begin{array}{cccc}|& |& & |\\ e_1& e_2& \cdots & e_n\\ |& |& & |\end{array}\right],S^{-1}AS=\mathrm{\Lambda }=\left[\begin{array}{ccc}{\lambda }_1& & \\ & {\lambda }_2& \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right]$$

• $S$: eigenvector matrix
• $\mathrm{\Lambda }$: eigenvalue matirx

proof

$$\begin{array}{rl}AS=A\left[\begin{array}{cccc}|& |& & |\\ e_1& e_2& \cdots & e_n\\ |& |& & |\end{array}\right]& =\left[\begin{array}{cccc}|& |& & |\\ {\lambda }_1{e}_1& {\lambda }_2{e}_2& \cdots & {\lambda }_n{e}_n\\ |& |& & |\end{array}\right]\\ & =\left[\begin{array}{cccc}|& |& & |\\ e_1& e_2& \cdots & e_n\\ |& |& & |\end{array}\right]\left[\begin{array}{ccc}{\lambda }_1& & \\ & {\lambda }_2& \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right]\\ & =S\mathrm{\Lambda }\end{array}$$

$S$는 모든 column (eigenvector)이 independent 하다고 가정했으므로 invertible 하다.

$$AS=S\mathrm{\Lambda },or{S}^{-1}AS=\mathrm{\Lambda },orA=S\mathrm{\Lambda }{S}^{-1}$$

이를 만족하는 matrix $S$가 존재할 때 $A$는 diagonalizable 하다.

Remark 1

Matrix $A$의 eigenvalue가 모두 다르면 (${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$이 distinct), n개의 eigenvector은 모두 independent 하다.

proof

n개의 eigenvector $e_1,\cdots ,e_n$ 중, $e_1$이 linearly dependent 하다고 가정해보자.

$$e_1=c_2{e}_2+\cdots +c_n{e}_n\cdots (1)$$

(1)의 양변에 matrix $A$를 곱하면

$$\begin{array}{rl}A{e}_1& =A(c_2{e}_2+\cdots +c_n{e}_n)\\ {\lambda }_1{e}_1& =c_2{\lambda }_2{e}_2+\cdots +c_n{\lambda }_n{e}_n\\ & \cdots (2)\end{array}$$

(1)의 양변에 ${\lambda }_1$을 곱하면

$$\begin{array}{rl}{\lambda }_1{e}_1& ={\lambda }_1(c_2{e}_2+\cdots +c_n{e}_n)\\ & =c_2{\lambda }_1{e}_2+\cdots +c_n{\lambda }_1{e}_n\\ & \cdots (3)\end{array}$$

(2)와 (3)은 ${\lambda }_1{e}_1$으로 같으므로

$$c_2({\lambda }_1-{\lambda }_2)e_2+c_3({\lambda }_1-{\lambda }_3)e_3+\cdots +c_n({\lambda }_1-{\lambda }_n)e_n=0$$

For distinct ${\lambda }_i$, $c_2=c_3=\cdots =c_n=0$

$e_1$은 linearly independent 하다.

Remark 2

Diagonalizing matrix $S$는 unique 하지 않다. eigenvector $e$는 상수배 되어도 (multiplied by a constant) 계속 eigenvector이다.

Remark 3

$S$의 eigenvector와 $\mathrm{\Lambda }$의 eigenvalue의 순서는 같다.

$$\left[\begin{array}{cccc}|& |& & |\\ e_1& e_2& \cdots & e_n\\ |& |& & |\end{array}\right]\left[\begin{array}{ccc}{\lambda }_1& & \\ & {\lambda }_2& \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right]$$

위의 $e_i$와 $e_j$의 순서가 바뀌면 ${\lambda }_i$와 ${\lambda }_j$의 순서도 바뀐다.

Remark 4

모든 matrix가 n개의 linearly independent vector를 갖는 것이 아니므로, 모든 matrix가 diagonalizable 한 것은 아니다.

중복된 eigenvalue가 존재하면 diagonalizable 하지 않을 수 있다.

$$A=\left[\begin{array}{cc}0& 1\\ 0& 0\end{array}\right],det(A-\lambda I)={\lambda }^2=0,{\lambda }_1={\lambda }_2=0$$

이 경우 $A$의 eigenvalue는 (1,0)의 multiple이다.

$$x=\left[\begin{array}{c}c\\ 0\end{array}\right]$$

Independent eigenvector가 한 개밖에 존재하지 않기 때문에 $S$를 만들 수 없다.

유의해아 할 점은 diagonalization이 되지 않는 이유가 $\lambda =0$ 이기 때문이 아니라 ${\lambda }_1={\lambda }_2$ 이기 때문이라는 점이다.

$A$의 diagonalizability 는 enough eigenvector 에 의해 결정된다.

$A$의 invertibility 는 nonzero eigenvalue 에 의해 결정된다.

• Diagonalizability와 invertibility는 아무 관계가 없고
• Diagonalization은 중복된(repeated) eigenvalue가 존재 할 때만 불가능하다.
  • 이 경우에도 항상 불가능 한 것은 아니다.
  • e.g., $A=I$ 이면 eigenvalue는 모두 1로 반복되지만 $A$는 항상 diagonal 하다.

Examples of Diagonalization

---

Example 1

$$\text{for projection matrix }A=\left[\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}\end{array}\right]$$

$$\begin{array}{c}det(A-\lambda I)=0,\lambda =1or\lambda =0,\mathrm{\Lambda }=\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right]\\ S=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right],AS=S\mathrm{\Lambda }=\left[\begin{array}{cc}1& 0\\ 1& 0\end{array}\right],S^{-1}AS=\mathrm{\Lambda }\end{array}$$

Example 2

$$\text{for rotation matrix }K=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]$$

$$\begin{array}{c}det(K-\lambda I)={\lambda }^2+1=0\\ \lambda =ior\lambda =-i\\ S=\left[\begin{array}{cc}1& 1\\ -i& i\end{array}\right]and{S}^{-1}KS=\left[\begin{array}{cc}i& 0\\ 0& -i\end{array}\right]\end{array}$$

• Real matrix를 표현하기 위해 complex number가 필요할 수도 있다.
• Real space $R^n$에 존재하는 eigenvalue의 수가 적으면, $C^n$ space에서 생각해야한다.

Powers and Products: $A^k$ and $AB$

---

$A^2$의 eigenvalue는 ${\lambda }_1^2,{\lambda }_2^2,\cdots ,{\lambda }_n^2$ 이고, $A$의 eigenvector는 $A^2$의 eigenvector와 동일하다.

$Ax=\lambda x$에서 시작하면

$$A^{2}x=A\lambda x=\lambda Ax={\lambda }^{2}x$$

Diagonalization 과정이서도 동일한 결과를 얻을 수 있다.

$$(S^{-1}AS)(S^{-1}AS)=S^{-1}{A}^{2}S={\mathrm{\Lambda }}^2$$

정리하면,

• eigenvalues of $A^k$: ${\lambda }_i^k$
• eigenvector of $A^k$: $S$

$S$가 $A$를 diagonalize 하면 $A^k$ 역시 diagonalize 할 수 있다.

$${\mathrm{\Lambda }}^k=(S^{-1}AS)(S^{-1}AS)\cdots (S^{-1}AS)=S^{-1}{A}^{k}S$$

$A$가 invertible하면 inverse ($k=-1$)인 경우에도 성립한다.

• $A^{-1}$의 eigenvalue는 $1/{\lambda }_i$

$$ifAx=\lambda xthenx=\lambda A^{-1}xand\frac{1}{\lambda }x=A^{-1}x$$

optional

두 matrix의 product (e.g., $AB$)에 대해서는 성립하지 않는다.

$A$의 eigenvalue를 $\lambda$, $B$의 eigenvalue를 $\mu$라고 할 때 다음과 같이 $AB$의 eigenvalue가 $\lambda \mu$라고 잘못 생각할 수 있다.

$$\text{False Proof}ABx=A\mu x=\mu Ax=\mu \lambda x$$

$A$와 $B$가 동일한 eigenvector $x$를 공유하고 있다고 가정하고 있지만 실제로는 그렇지 않기 때문이다.

이는 역으로, $AB$의 eigenvalue가 $\lambda \mu$가 되려면 동일한 eigenvector $x$를 공유하고 있어야 한다는 것을 의미한다.

Diagonalizable matrix는 $AB=BA$일 때만 동일한 eigenvector matrix $S$를 공유한다.

Proof

동일한 matrix $S$가 $A=S{\mathrm{\Lambda }}_1{S}^{-1}$와 $B=S{\mathrm{\Lambda }}_2{S}^{-1}$를 diagonalize할 때,

$$\begin{array}{c}AB=S{\mathrm{\Lambda }}_1{S}^{-1}S{\mathrm{\Lambda }}_2{S}^{-1}=S{\mathrm{\Lambda }}_1{\mathrm{\Lambda }}_2{S}^{-1}\\ BA=S{\mathrm{\Lambda }}_2{S}^{-1}S{\mathrm{\Lambda }}_1{S}^{-1}=S{\mathrm{\Lambda }}_2{\mathrm{\Lambda }}_1{S}^{-1}\end{array}$$

Diagonal matrix는 항상 commute 하므로

$$\begin{gathered} {\mathrm{\Lambda }}_1{\mathrm{\Lambda }}_2={\mathrm{\Lambda }}_2{\mathrm{\Lambda }}_1 \\ AB=BA \end{gathered}$$

반대 방향으로는,

$$\begin{array}{c}Ax=\lambda x\\ (AB)x=(BA)x=B(Ax)=B\lambda x=\lambda Bx\\ A(Bx)=\lambda (Bx)\end{array}$$

$x$와 $Bx$ 모두 동일한 eigenvector $\lambda$ 를 공유하는 $A$의 eigenvector 이다.

편의를 위해서 $A$의 eigenvalue가 distinct 하다고 가정하면, $Ax=\lambda x$를 만족하는 각 eigenspace는 모두 one-dimensional* 이므로 $Bx$는 $x$의 multiple이어야 한다. (i.e., $Bx=\mu x$)

결과적으로, $x$는 $B$의 eigenvector다.

참고

---

• If the eigenvalues are distinct then the eigenspaces are all one dimensional*

\> 정리

• eigenvalue가 distinct 하면
• $A{x}_i={\lambda }_i{x}_i$를 만족하는 $x_i$는 모두 independent하고
• 특정 eigenvalue ${\lambda }_i$에 대응하는 eigenvector들은 하나의 vector $x_i$로만 이루어져야 한다.
  • $x_i$가 eigenvector이면 $k{x}_i$도 eigenvector 이므로 이들이 모여서 eigenspace를 이루는 것.
  • 특정 eigenvalue에 대한 eigenspace와 $A$의 diagonalization을 위한 eigenvector matrix를 헷갈리지 말아야 한다.
  • Matrix $A$의 eigenvector matrix $S$의 dimension이 n인 것이지 각 eigenvalue에 대한 eigenspace의 dimension은 1이고 이런 eigenspace가 n개 있는 것.
• 즉, 동일한 $\lambda$에 대한 $x$는 one dimensional이어야 하므로, $Ax=\lambda x$, $A(Bx)=\lambda (Bx)$에서 $Bx$는 $x$의 multiple이어야 하고
• 이를 식으로 나타내면 $Bx=\mu x$ ($\mu$는 상수) 이므로 $x$는 $B$의 eigenvector이다.
• 결과적으로, $A$와 $B$는 동일한 eigenvector $x$를 공유한다.

2020.09.27 16:32 작성.