5.3 Diagonalization

Jaehyun_onelion·2023년 3월 17일
Linear Algebra선형대수학
0

선형대수학

목록 보기
28/42

이번 포스트에서는 diagonalization에 대해서 알아보겠습니다.


1) Diagonalization


(1) Efficiency of diagonal matrix


Diagonal matrix는 계산상의 이점을 가지고 있습니다.


example

D=[2003]D = \begin{bmatrix}2 & 0 \\ 0 & 3\end{bmatrix}

일 때,

D2=[220032],   D3=[230033],   Dk=[2k003k]D^2 = \begin{bmatrix}2^2 & 0 \\ 0 & 3^2\end{bmatrix}, \ \ \ D^3 = \begin{bmatrix}2^3 & 0 \\ 0 & 3^3\end{bmatrix}, \ \ \ D^k = \begin{bmatrix}2^k & 0 \\ 0 & 3^k\end{bmatrix}

임을 알 수 있습니다.


example

D=[200030001]D =\begin{bmatrix}2 & 0 & 0\\ 0 & 3 & 0 \\ 0 & 0 & 1\end{bmatrix}

일 때,

D−1=[12000130001]D^{-1} =\begin{bmatrix}\frac{1}{2} & 0 & 0\\ 0 & \frac{1}{3} & 0 \\ 0 & 0 & 1\end{bmatrix}

인 것을 알 수 있습니다.


example

A=[72−41],  P=[11−1−2],  D=[5003]A = \begin{bmatrix}7 & 2 \\ -4 & 1\end{bmatrix}, \ \ P = \begin{bmatrix}1 & 1 \\ -1 & -2\end{bmatrix}, \ \ D= \begin{bmatrix}5 & 0 \\ 0 & 3\end{bmatrix}

AA와 DD는 similar합니다. 즉,

A=PDP−1A = PDP^{-1}

입니다. 여기서

A2=PDP−1PDP−1=PD2P−1,A3=PD2P−1PDP−1=PD3P−1,⋮Ak=PDkP−1=[11−1−2][5k003k][11−1−2]=[2⋅5k−3k5k−3k2⋅3k−2⋅5k2⋅3k−5k]A^2 = PDP^{-1}PDP^{-1}=PD^2P^{-1}, \\ A^3 = PD^2P^{-1}PDP^{-1}=PD^3P^{-1}, \\ \vdots\\ A^k=PD^kP^{-1} = \begin{bmatrix}1 & 1 \\ -1 & -2\end{bmatrix} \begin{bmatrix}5^k & 0 \\ 0 & 3^k\end{bmatrix}\begin{bmatrix}1 & 1 \\ -1 & -2\end{bmatrix} = \begin{bmatrix} 2\cdot 5^k -3^k & 5^k -3^k \\ 2\cdot 3^k - 2\cdot 5^k & 2\cdot 3^k - 5^k\end{bmatrix}

인 것을 알 수 있습니다.

위 예시들과 같이 diagonal matrix가 가지는 계산상의 이점이 많습니다. 따라서 AA에 대해 설명할 때 AA 대신 AA와 similar한 diagonal matrix DD를 이용하여 설명하는 경우가 많습니다. AA를 PDP−1PDP^{-1}로 바꾸는 과정을 diagonaization이라고 합니다.


(2) Diagonalization


Definition : Diagonalization

A square matrix AA is diagonalizable if AA is similar to a diagonal matrix

A=PDP−1A=PDP^{-1} for some invertible matrix PP and some diagonal matrix DD

어떤 matrix가 diagonalizable하다는 것은 AA와 diagonal matrix DD가 similar하다는 것을 뜻합니다.

어떤 matrix가 diagonalizable 여부를 확인할 수 있는 정리는 다음과 같습니다.


Theorem : The Diagonalization Theorem

An n×nn \times n matrix AA is diagonalizable if and only if AA has nn linearly independent eigenvectors. In fact, A=PDP−1A=PDP^{-1} with DD a diagonal matrix, columns of PP are nn linearly independent eigenvectors of AA, and diagonal entries of DD are eigenvalues of AA that correspond, respectively, to the eigenvectors in PP.

In other words, AA is diagonalizable if and only if there are enough eigenvectors to form a basis of Rn\mathbb R^n - eigenvector basis for Rn\mathbb R^n

n×nn \times n matrix AA와 DD가 similar하기 위한 조건은 linearly independent한 eigenvector가 nn개가 되면 됩니다. 이 때, P,DP, D를 특정할 수 있는데, DD의 diagonal entry는 AA의 eigenvalue가, PP의 각 column은 DD의 diagonal entry의 같은 index 위치의 eigenvalue에 해당하는 eigenvector가 됩니다.


example

A=[133−3−5−3331]A=\begin{bmatrix} 1 & 3 & 3 \\ -3 & -5 & -3 \\ 3 & 3 & 1 \end{bmatrix}

AA의 diagonalizable 여부를 확인하기 위해서 먼저 AA의 eigenvalue와 eigenvector를 구해야 합니다.

det⁡(A−λI)=∣1−λ33−3−5−λ−3331−λ∣\det(A-\lambda I) = \begin{vmatrix}1-\lambda & 3 & 3 \\ -3 & -5-\lambda & -3 \\ 3 & 3 & 1-\lambda\end{vmatrix}

위 matrix의 determinant를 계산하기가 어렵기 때문에, row operation을 통해 계산을 쉽도록 변형 후 determinant를 구하면

∣1−λ33−3−5−λ−3331−λ∣=∣1−λ33−3−5−λ−30−2−λ−2−λ∣\begin{vmatrix}1-\lambda & 3 & 3 \\ -3 & -5-\lambda & -3 \\ 3 & 3 & 1-\lambda\end{vmatrix} = \begin{vmatrix}1-\lambda & 3 & 3 \\ -3 & -5-\lambda & -3 \\ 0 & -2-\lambda & -2-\lambda\end{vmatrix}
=(−1)2(1−λ)∣−5−λ−3−2−λ−2−λ∣+(−1)3(−3)∣33−2−λ−2−λ∣=(1−λ)((−5−λ)(−2−λ)+3(−2−λ))+3(3(−2−λ)−3(−2−λ))=(1−λ)(λ+2)(λ+2)=0= (-1)^{2}(1-\lambda)\begin{vmatrix}-5-\lambda & -3 \\ -2-\lambda & -2-\lambda \end{vmatrix} + (-1)^{3}(-3)\begin{vmatrix}3 & 3 \\ -2-\lambda & -2-\lambda\end{vmatrix} \\ =(1-\lambda)((-5-\lambda)(-2-\lambda)+3(-2-\lambda)) +3(3(-2-\lambda)-3(-2-\lambda)) \\ =(1-\lambda)(\lambda+2)(\lambda+2) = 0
λ=−2,1\lambda = -2 , 1

임을 알 수 있고, λ=−2\lambda=-2의 multiplicity는 2입니다.

이제 eigenvalue를 계산하였으니 각각의 eigenvalue에 대한 eigenvector를 구해보면

λ=1\lambda=1인 경우

A−I=[033−3−6−3330]A-I =\begin{bmatrix} 0 & 3 & 3 \\ -3 & -6 & -3 \\ 3 & 3 & 0 \end{bmatrix}

이 되어 (A−I)x=0(A-I)\boldsymbol x=0의 solution을 augmented matrix를 통해 구하면

[1330−3−5−303310]∼[10−1001100000]\begin{bmatrix} 1 & 3 & 3 & 0 \\ -3 & -5 & -3 & 0 \\ 3 & 3 & 1 & 0 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & -1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}

이 되어

x=x3[1−11],   x3  is  free\boldsymbol{x} = x_3\begin{bmatrix}1 \\ -1 \\ 1 \end{bmatrix}, \ \ \ x_3 \ \ is \ \ free

가 됩니다.

λ=−2\lambda = -2인 경우

A+2I=[333−3−3−3333]A+2I =\begin{bmatrix} 3 & 3 & 3 \\ -3 & -3 & -3 \\ 3 & 3 & 3 \end{bmatrix}

이 되어 (A+2I)x=0(A+2I)\boldsymbol{x} = 0의 solution은

[3330−3−3−303330]∼[111000000000]\begin{bmatrix} 3 & 3 & 3 & 0 \\ -3 & -3 & -3 & 0 \\ 3 & 3 & 3 & 0 \end{bmatrix} \sim \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}

이 되어

x=x2[−110]+x3[−101]   x2,x3  is  free\boldsymbol{x} = x_2\begin{bmatrix}-1 \\ 1 \\ 0 \end{bmatrix} +x_3\begin{bmatrix}-1 \\ 0 \\ 1 \end{bmatrix} \ \ \ x_2, x_3 \ \ is \ \ free

가 됩니다.

λ=1\lambda=1일 때에 대응하는 eigenspace의 basis 원소의 개수가 하나, λ=−2\lambda=-2일 때 대응하는 eigenspace의 basis 원소의 개수가 2개입니다. 이 때 서로 다른 eigenvalue에 해당하는 eigenvector는 linearly independent하므로, 위 matrix는 diagonalizable하고, P,DP, D는 다음과 같습니다.

P=[1−1−1−110101],  D=[100020002]P = \begin{bmatrix}1 & -1 & -1 \\ -1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}, \ \ D=\begin{bmatrix}1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{bmatrix}

example

A=[243−4−6−3331]A=\begin{bmatrix} 2 & 4 & 3 \\ -4 & -6 & -3 \\ 3 & 3 & 1 \end{bmatrix}

다음 matrix가 diagonalizable 여부를 확인하기 위해 먼저 eigenvalue를 구해보면

det⁡(A−λI)=∣2−λ43−4−6−λ−3331−λ∣\det(A-\lambda I) = \begin{vmatrix}2-\lambda & 4 & 3 \\ -4 & -6-\lambda & -3 \\ 3 & 3 & 1-\lambda\end{vmatrix}
∣2−λ43−4−6−λ−3331−λ∣=∣2−λ43−2−λ−2−λ0331−λ∣\begin{vmatrix}2-\lambda & 4 & 3 \\ -4 & -6-\lambda & -3 \\ 3 & 3 & 1-\lambda\end{vmatrix} = \begin{vmatrix}2-\lambda & 4 & 3 \\ -2-\lambda & -2-\lambda & 0 \\ 3 & 3 & 1-\lambda\end{vmatrix}
=3∣−2−λ−2−λ33∣+(1−λ)∣2−λ4−2−λ−2−λ∣ =(1−λ)(λ+2)2=0\\= 3\begin{vmatrix}-2-\lambda & -2-\lambda \\ 3 & 3 \end{vmatrix} + (1-\lambda) \begin{vmatrix} 2-\lambda & 4 \\-2-\lambda & -2-\lambda \end{vmatrix} \\ \ \\ = (1-\lambda)(\lambda+2)^2=0

이 되어

λ=1,−2\lambda = 1, -2

이고, λ=−2\lambda=-2의 multiplicity는 2입니다.

이 때, λ=−2\lambda=-2일 때의 eigenvector를 구해보면

A+2I=[443−4−4−3333]A+2I=\begin{bmatrix} 4 & 4 & 3 \\ -4 & -4 & -3 \\ 3 & 3 & 3 \end{bmatrix}

이 되어 (A+2I)x=0(A+2I)\boldsymbol{x}=0의 solution은

[4430−4−4−303330]∼[110000100000]\begin{bmatrix} 4 & 4 & 3 & 0 \\ -4 & -4 & -3 & 0 \\ 3 & 3 & 3 & 0 \end{bmatrix} \sim \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}

이 되어

x=x3[−110],x3  is  free\boldsymbol{x} = x_3\begin{bmatrix} -1 \\ 1 \\ 0 \end{bmatrix}, x_3 \ \ is \ \ free

가 되고,

λ=1\lambda=1일 때의 eigenvector를 구하면

A−I=[143−4−7−3330]A-I =\begin{bmatrix} 1 & 4 & 3 \\ -4 & -7 & -3 \\ 3 & 3 & 0 \end{bmatrix}

가 되어,

[1430−4−7−303300]∼[10−1001100000]\begin{bmatrix} 1 & 4 & 3 & 0 \\ -4 & -7 & -3 & 0 \\ 3 & 3 & 0 & 0 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & -1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}
x=x3[1−11],x3  is  free\boldsymbol{x} = x_3\begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix}, x_3 \ \ is \ \ free

가 됩니다. 지금 각각의 eigenvalue에 해당하는 eigenspace의 dimension이 1이므로, 총 합이 3이 되지 않아, 해당 matrix는 diagonalizable하지 않습니다.

이를 통해 모든 matrix가 diagonalizable하지 않다는 것을 알 수 있습니다.

다음 정리는 matrix의 diagonalizable 여부를 확인할 수 있는 정리입니다.


Theorem

An n×nn \times n matrix with nn distinct eigenvalues is diagonalizable

nn개의 서로 다른 eigenvalue를 가진 n×nn \times n matrix는 diagonalizable합니다. 이는 서로 다른 eigenvalue에 해당하는 eigenvector는 linearly independent한 것을 이용하면 쉽게 확인할 수 있습니다.


Theorem

Let AA be an n×nn \times n matrix whose distinct eigenvalues are λ1,λ2,...,λp\lambda_1, \lambda_2, ... , \lambda_p

  1. For 1≤k≤p1\leq k \leq p, the dimension of the eigenspace for λk\lambda_k is less than or equal to the multiplicity of the eigenvalue λk\lambda_k
  2. The matrix AA is diagonaliable if and only if the sume of the dimensions of the eigenspaces equals nn. This happens if and only if
    1. The characteristic polynomial factors completely into linear factors
    2. The dimension of the eigenspace for each λk\lambda_k equals the multiplicity of λk\lambda_k
  3. If AA is diagonalizable and BkB_k is a basis for the eigenspace corresponding to λk\lambda_k for each kk , then the total collection of vectors in the sets B1,...,BpB_1, ..., B_p forms an eigenvector basis for Rn\mathbb R^n

이 정리에서는 eigenvalue의 multiplicity에 따라 diagonalizable 여부를 확인할 수 있는 정리입니다.

만약 특정 eigenvalue의 multiplicity가 kk인 경우, 해당 eigenvalue의 eigenspace의 dimension이 kk를 만족할 때, 또한 이러한 조건을 모든 eigenvalue에 대해 성립할 때, 해당 matrix는 diagonalizable하게 됩니다. 만약 특정 eigenvalue의 multiplicity가 eigenspace의 dimension보다 클 때, 해당 matrix는 diagonalizable하지 않습니다.

위의 예시를 다시보면, 첫 번째의 예시는 λ=1\lambda=1일 때 eigenspace dimension이 1이었고, λ=−2\lambda=-2일 때 eigenspace dimension이 2로 각각의 multiplicity와 같았기 때문에 diagonalizable하였고, 두 번째 예시는 λ=−2\lambda=-2일 때의 multiplicity는 2였으나 eigenspace의 dimension이 1이었기 때문에 diagonalization이 불가능하였습니다.


example

A=[5000050014−30−1−20−3]A = \begin{bmatrix} 5 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 \\ 1 & 4 & -3 & 0 \\ -1 & -2 & 0 & -3 \end{bmatrix}

해당 matrix가 diagonalizable 여부를 확인하기 위해 eigenvalue를 구하면 위 matrix는 triangular matrix이므로

λ=5,−3\lambda =5, -3

이 되고, 각각의 multiplicity가 2가 됩니다.

λ=5\lambda=5일 때의 eigenvector를 구하기 위해 (A−5I)x=0(A-5I)\boldsymbol x = 0을 풀면

[500000500014−300−1−20−30]∼[10816001−4−400000000000]\begin{bmatrix} 5 & 0 & 0 & 0 & 0\\ 0 & 5 & 0 & 0 & 0 \\ 1 & 4 & -3 & 0 & 0 \\ -1 & -2 & 0 & -3 & 0 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & 8 & 16 & 0\\ 0 & 1 & -4 & -4 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}

이 되어

x=x3[−8410]+x4[−16401],  x3,x4  is  free\boldsymbol{x} = x_3 \begin{bmatrix}-8 \\ 4 \\ 1 \\ 0 \end{bmatrix} + x_4 \begin{bmatrix} -16 \\ 4 \\ 0 \\ 1\end{bmatrix}, \ \ x_3, x_4 \ \ is \ \ free

λ=−3\lambda=-3일 때의 eigenvector를 구하기 위해 (A+3I)x=0(A+3I)\boldsymbol{x} =0을 풀면

[800000800014000−1−2000]∼[10000010000000000000]\begin{bmatrix} 8 & 0 & 0 & 0 & 0\\ 0 & 8 & 0 & 0 & 0 \\ 1 & 4 & 0 & 0 & 0 \\ -1 & -2 & 0 & 0 & 0 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}

이 되어

x=x3[0010]+x4[0001],  x3,x4  is  free\boldsymbol{x} = x_3 \begin{bmatrix}0 \\ 0 \\ 1 \\ 0 \end{bmatrix} + x_4 \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1\end{bmatrix}, \ \ x_3, x_4 \ \ is \ \ free

이 됩니다. 이 때 각 eigenvalue의 multiplicity와 eigenspace의 dimension이 2로 같기 때문에 해당 matrix는 diagonalizable하고

A=PDP−1, P=[−8−1600440010100101],D=[5000050000−30000−3]A=PDP^{-1}, \\ \ \\ P = \begin{bmatrix} -8 & -16 & 0 & 0 \\ 4 & 4 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{bmatrix}, D=\begin{bmatrix} 5 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 \\ 0 & 0 & -3 & 0 \\ 0 & 0 & 0 & -3 \end{bmatrix}

가 됩니다.


지금까지 diagonalization에 대해서 알아보았습니다. 다음 포스트에서는 complex eigenvalue에 대해서 알아보겠습니다. 질문이나 오류 있으면 댓글 남겨주세요! 감사합니다!


Appendix : Proof of Theorem


Theorem : The Diagonalization Theorem

An n×nn \times n matrix AA is diagonalizable if and only if AA has nn linearly independent eigenvectors. In fact, A=PDP−1A=PDP^{-1} with DD a diagonal matrix, columns of PP are nn linearly independent eigenvectors of AA, and diagonal entries of DD are eigenvalues of AA that correspond, respectively, to the eigenvectors in PP.

In other words, AA is diagonalizable if and only if there are enough eigenvectors to form a basis of Rn\mathbb R^n - eigenvector basis for Rn\mathbb R^n


  • Proof

⇒\Rightarrow

A=PDP−1  ⟺  AP=PDA=PDP^{-1} \iff AP=PD

임을 밝히면 됩니다.

PP : n×nn\times n matrix with column : v1,...,vn\boldsymbol{v_1}, ..., \boldsymbol{v_n}, DD : diagonal matrix with λ1,...,λn\lambda_1, ..., \lambda_n이라고 합시다.

이 경우

AP=A[v1...vn]=[Av1...Avn]AP = A\begin{bmatrix} \boldsymbol{v_1} & ... & \boldsymbol{v_n} \end{bmatrix} = \begin{bmatrix} A\boldsymbol{v_1} & ... & A\boldsymbol{v_n} \end{bmatrix}

가 되고

PD=[v1...vn][λ1...0⋮⋱⋮0⋯λn]=[λ1v1...λnvn]PD = \begin{bmatrix} \boldsymbol{v_1} & ... & \boldsymbol{v_n} \end{bmatrix}\begin{bmatrix} \lambda_1 & ... & 0 \\ \vdots & \ddots & \vdots \\0 & \cdots & \lambda_n \end{bmatrix} = \begin{bmatrix} \lambda_1\boldsymbol{v_1} & ... & \lambda_n\boldsymbol{v_n} \end{bmatrix}

이 됩니다.

AP=PD[Av1...Avn]=[λ1v1...λnvn]AP=PD \\ \begin{bmatrix} A\boldsymbol{v_1} & ... & A\boldsymbol{v_n} \end{bmatrix} = \begin{bmatrix} \lambda_1\boldsymbol{v_1} & ... & \lambda_n\boldsymbol{v_n} \end{bmatrix}

이 되고, 이는

Avj=λjvjA\boldsymbol{v_j} = \lambda_j\boldsymbol {v_j}

이므로, DD의 diagonal entry는 eigenvalue, PP의 column은 해당 위치의 eigenvalue에 해당하는 eigenvector가 됩니다. ㅇ

⇐\Leftarrow

{v1,...,vn}\{\boldsymbol{v_1}, ..., \boldsymbol{v_n}\}이 linearly independent한 eigenvectors고, 각각의 eigenvector에 해당하는 eigenvalue를 λ1,...,λn\lambda_1, ..., \lambda_n라 하면

P=[v1...vn],  D=[λ1...0⋮⋱⋮0⋯λn]P =\begin{bmatrix} \boldsymbol{v_1} & ... & \boldsymbol{v_n} \end{bmatrix}, \ \ D=\begin{bmatrix} \lambda_1 & ... & 0 \\ \vdots & \ddots & \vdots \\0 & \cdots & \lambda_n \end{bmatrix}

으로 P,DP, D를 정의하면

PD=[λ1v1...λnvn]=[Av1...Avn]=APPD = \begin{bmatrix} \lambda_1\boldsymbol{v_1} & ... & \lambda_n\boldsymbol{v_n} \end{bmatrix} = \begin{bmatrix} A\boldsymbol{v_1} & ... & A\boldsymbol{v_n} \end{bmatrix} = AP

가 되어

PD=APA=PDP−1PD = AP \\ A = PDP^{-1}

가 성립하여 diagonalizable합니다.


Theorem

An n×nn \times n matrix with nn distinct eigenvalues is diagonalizable


  • Proof

nn개의 서로 다른 eigenvalue에 해당하는 eigenvector는 linearly independent합니다. 따라서 nn개의 linearly independent한 eigenvector를 가지고 있기 때문에, diagonalizable합니다.

profile
Jaehyun_onelion
데이터 분석가 새싹
이전 포스트

5.2 Characteristic Equation

다음 포스트

5.4 Complex Eigenvalue

0개의 댓글