Advanced Eigendecomposition 2

<Advanced Eigendecomposition 2>

    1. Advanced Eigendecomposition 2

---

Advanced Eigendecomposition 2

 

orthogonally diagonalizable

• Symmetric Matrix A를 decomposition 했을 때,
• orthogonal 한 Matrix P와 (with P^{-1} = P^T)                                                     
• diagonal Matrix D를 가지면,
• A는 orthogonally diagonalizable 하다.

• 

 

Geometric Multiplicity

• Algebraic Multiplicity: Characteristic Equation에서 각 λ의 개수
• Geometric Multiplicity: Characteristic Equation의 각 λ의 eigenspace의 dimension (= 각 λ의 eigenspace에서 basis vector의 개수)
• 1 <= Geometric Multiplicity <= Algebraic Multiplicity                                                                                                                 → x가 non-zero vector가 아니기 때문에 (= det(A - λI)가 역행렬이 존재하지 않기 때문에)

 

 

ex) Characteristic Equation: (λ - 1)^2(λ + 5) = 0

λ	1	-5	total
Algebraic Multiplicity	2	1	3
Geometric Multiplicity	(1 <=) 1 or 2 (<= 2)	(1 <=) 1 (<= 1)	2, 3 (<= Algebraic Multiplicity)

 

 

 

Spectral Decomposition

• Symmetric Matrix의 eigendecomposition
• Matrix P가 A의 orthonormal eigenvector이고,
• diagonal Matrix D가 eigenvalue들을 가지고,
• Matrix A가 Symmetric Matrix 일 시,
• P^{-1} = P^T 이기 때문에,

A = PDP^T = [u1, u2, ... , un][[λ1 ...  0], [0, λ2, ..., 0], [0, ..., λn]](u1T, ..., unT)

   = [λ1u1, ..., λn*un](u1T, ..., unT)

   = λ1*u1*u1T + λ2*u2*u2T + ... + λn*un*unT

      (각각의 요소들은 A의 spectrum들)

 

 

 

The Spectral Theorem for Symmetric Matrix

• A는 n개의 real eigenvalues를 가진다. (λ는 허근이 아닌 모두 실근)

    proof)

    ex) Ax = λx → λ와 x를 복소수로 갖는 vector 일 시,

 

      (복소수 x는 complex(x)라고 표현)

    complex(complex(x)^T * A * x)

     = xT * complex(A) * complex(x)

     = xT * A * complex(x)

     = (xT * A * complex(x))^T             # 결과값이 1x1 scalar 값이기 때문에 transpose 취해도 동일

     = complex(x)^T * A * x                # A^T= A

 

    → complex(complex(x)^T * A * x) = complex(x)^T * A * x

    → x는 실수                               # scalar 값은 복소수 취해도 동일한 값 출력

 

 

    이를 complex(x)^T * λ * x = λ * complex(x)^T * x 에 적용시키면

     = (λ 값) * (complex(x)^T * A * x 값)

 

    → 위에서 (complex(x)^T * A * x 값)는 실수 값이라고 했으므로

∴ λ는 실수 (복소수가 될 수 없다.)

 

• 각 λ의 eigenspace의 dimension(= Geometric Multiplicity)는 각 λ의 Algebraic Multiplicity와 같다.

    → Geometric Multiplicity가 항상 각 λ에서 최대값(= Algebraic Multiplicity)을 가진다.

 

• eigenspace들은 서로 orthogonal하다. (각 eigenspace의 λ들은 다른 λ들과 orthogonal하다.)

 

• A는 orthogonally diagonalizable하다.

 

 

 

n이 매우 큰 수일 때,

1. V^{-1}*A*V 에서 A가 diagonal matrix라면

characteristic equation: (A - λI)는 diagonal entry들의 곱으로 바로 계산 가능.

 ex) (A - λI) = [[8 - λ, 0], [0, -3 - λ]]일 시, 바로 대각선 entry들의 곱인 (8 - λ)(-3 - λ) = 0으로 계산 가능

 

 

2. V^{-1}*A*V = D 양변에 계속해서 M, M^{-1}을 곱해서 A를 diagonal matrix로 근사

 

V^{-1}*A*V = M*V^{-1}*A*V*M^{-1}

→ V^{-1}(M*A*M^{-1})*V = M^{-1}*D*M

→ V^{-1}*A´*V = D´

→ Matrix A의 diagnonal entry 값들은 커지고, 그 외 entry들은 점점 작아져서 diagonal matrix로 근사