Diagonalization
- We want to change a given square matrix $A \in \mathbb{R}^{n \times n}$ into a diagonal matrix $D$ via the following form: $D = V^{-1}AV$, where $V \in \mathbb{R}^{n \times n}$ is an invertible matrix and $D \in \mathbb{R}^{n \times n}$ is a diagonal matrix. This process is called the diagonalization of $A$
- Finding V and D: How can we find $V$ and $D$? From $D = V^{-1}AV$, we get $VD = AV$. Let $V = [v_1, v_2, \dots, v_n]$ (where $v_i$ are column vectors) and $D$ be a diagonal matrix with diagonal entries $\lambda_1, \dots, \lambda_n$.
- Expanding $VD = AV$ yields $[\lambda_1 v_1, \dots, \lambda_n v_n] = [A v_1, \dots, A v_n]$. This implies $A v_i = \lambda_i v_i$. Therefore, the columns of $V$ must be the eigenvectors of $A$, and the diagonal entries of $D$ must be the corresponding eigenvalues
| 대각화(diagonalization): 어떤 정방행렬 $A$를 역행렬이 존재하는 행렬 $V$와 대각행렬(Diagonal matrix) $D$를 이용해 $D = V^{-1}AV$ 꼴로 만드는 것 이 수식을 풀어보면 $Av_i = \lambda_i v_i$라는 결과가 나오는데, 이는 곧 행렬 $V$를 구성하는 열벡터들이 $A$의 고유벡터임 -> 이는 대각행렬 $D$를 채우는 값들이 '고유값'임을 증명 |
Linear Transformation via Eigendecomposition
- Eigendecomposition : By rearranging the diagonalization formula, we get $A = VDV^{-1}$. This specific factorization is called eigendecomposition
- We can rewrite a linear transformation $T(x) = Ax$ as a sequence of three simpler transformations: $$T(x) = Ax = V(D(V^{-1}x))$$
- Step-by-Step Breakdown:
- $V^{-1}x$ : Transforms the input vector $x$ from the standard basis into the coordinate system defined by the eigenvectors of $A$
- $D(\dots)$ : In this new coordinate system, the transformation acts simply as a scaling along each eigenvector axis by its corresponding eigenvalue $\lambda$
- $V(\dots)$ : Transforms the scaled vector back into the standard coordinate system
왼쪽 그림(변환 전의 평범한 공간) : 반지름이 1인 평범한 원(unit circle)과 그 안의 두 벡터 -> 아무런 힘도 가해지지 않은 기본 상태
오른쪽 그림 (선형 변환 후 찌그러진 공간) : 어떤 행렬을 곱해서 원이 있던 공간 전체를 잡아당기고 회전시킨 결과로 타원이 됨, 이것이 선형 변환
*이 그림에서 고유벡터 : 공간이 타원형으로 찌그러지는 와중에도, 오른쪽 타원의 장축과 단축을 가리키는 검은색 화살표들을 보면 공간이 변형되기 전과 비교했을 때 방향이 꺾이지 않고 그대로 유지됨
**이 그림에서 고유값 : 방향은 안 변했지만, 길이는 늘어나거나 줄어듦
| 고유값 분해(eigendecomposition) : 행렬 $A$를 $A = VDV^{-1}$ 형태로 분해하는 것 이를 선형변환 $T(x) = Ax$에 적용해 보면, 복잡한 회전이나 찌그러짐 없이 3단계 기하학적 흐름으로 변환을 이해할 수 있음 ① $V^{-1}$ : 원래 축에 있던 데이터를 고유벡터를 축으로 하는 새로운 곳으로 보냄 ② $D$ : 새로운 곳에서는 모든 변환이 단순히 각 축 방향으로 고유값만큼 쭉쭉 늘리거나 줄이는 단순 곱셈으로 바뀜 ③ $V$ : 크기 변환이 끝난 데이터를 다시 원래의 표준 축으로 데려옴 |
실습 III
내용: 딥러닝이나 마르코프 체인 모델 등에서 어떤 벡터에 행렬 $A$를 $k$번 반복해서 곱하는 $A^k x$ 연산은 자주 등장함. 거대한 행렬을 계속 곱하는 것은 엄청난 연산량이 필요하지만, 고유값 분해($A = VDV^{-1}$)를 이용하면 쉽기 때문.
실제 $A^k$를 나열해보면 중간에 있는 $V^{-1}$과 $V$가 서로 만나 단위행렬이 되어 상쇄되므로, 결국 $VD^k V^{-1}$만 남게 됨 -> 대각행렬 $D$의 거듭제곱($D^k$)은 단순히 대각선에 있는 고유값들을 $k$제곱하는 것만으로 끝나기 때문에, 연산 복잡도가 극단적으로 줄어든다는 점에서 이점이 있다./]
Further Study: Conditions for Diagonalizability
- Is it always possible?: It is not always possible to diagonalize a matrix $A$
- Determining whether a matrix $A \in \mathbb{R}^{n \times n}$ is diagonalizable requires that its geometric multiplicity should be equal to its algebraic multiplicity for all eigenvalues
- As a special case, if an $n \times n$ matrix $A$ has $n$ distinct eigenvalues, then $A$ is guaranteed to be diagonalizable
| 그렇다면 언제 대각화가 가능할까? 모든 정방행렬이 무조건 대각화 가능한 것은 아님 대각화 가능 여부를 판단하려면, 행렬이 가진 대수적 중복도(특성방정식 해의 중복 개수)와 기하학적 중복도(고유공간의 차원)가 일치해야 함 but. 예외 존재 : $n \times n$ 크기의 행렬이 만약 서로 다른 $n$개의 고유값을 가진다면, 그 행렬은 무조건 대각화가 가능 |