Eigenvalue & Eigenvector
행렬의 고유값과 고유벡터
수학적 정의는 다음과 같다.
행렬 $A$를 선형변환으로 보았을 때, 선형변환 $A$에 의한 변환 결과가 자기 자신의 상수배가 되는 0이 아닌 벡터를 고유벡터, 그 상수배 값을 고유값이라고 한다. 이때, 이는 $A$가 정방행렬일 때만 정의된다.
\[Ax=\lambda x\]기하학적 의미는, 방향은 보존되고 스케일만 변화되는 방향 벡터를 의미하는 것이다.
이는 식을 다시 정리해보면 다음과 같이 쓸 수 있다.
\[(A-\lambda I)x=0\]이때, $x$가 존재하기 위해서는 $\det (A-\lambda I)=0$을 만족해야한다. (매우 자명)
그리고, $\det(A-\lambda I)=0$를 특성방정식이라고 부른다. 즉 특성방정식의 해가 존재해야 행렬의 고유값과 고유벡터가 존재하는 것이다.
행렬 대각화
고유값과 고유벡터를 활용하기 위한 하나의 방법이라고 볼 수 있으며, 다른 말로는 고유값 분해라고도 불린다. 행렬의 대각화를 통해 LU분해, QR분해와 같은 부분 행렬로 분해하는 방법을 적용할 수 있다.
일단 기본적으로 행렬곱, 선형변환의 의미는 벡터를 회전시키고 크기를 조절하는 것이다. 그리고 고윳값 분해는 회전, 크기 조절, 회전의 3개의 과정을 3개의 행렬로 분해하는 과정이다. 여기서 회전은 고유벡터를 열벡터로 만든 행렬로, 크기 조절은 고유값을 대각행렬로 만든 행렬로 처리한다.
좌좌좌 아무튼 행렬 $A$에 대해서 고유값과 고유벡터들을 $\lambda_i, v_i$라고 하자. 그러면 다음과 같이 적을 수 있을 것이다~!
\[Av_i=\lambda_i v_i\]그리고 적당히 벡터로 바꿔주면
\[A\begin{bmatrix}v_1 & \cdots &v_n\end{bmatrix}=\begin{bmatrix}\lambda_1v_1 & \cdots & \lambda_nv_n\end{bmatrix} = \begin{bmatrix} v_1 & \cdots & v_n\end{bmatrix}\begin{bmatrix}\lambda_1 & & 0 \\ & \lambda_2 & & \\ & & \ddots & \\\ 0 & & & \lambda_n\end{bmatrix}\]즉, 고유벡터들을 열벡터로 하는 행렬을 $P$, 교유값들을 대각원소로 하는 대각행렬을 $\Lambda$라고 하면 다음식이 성립한다.
\[AP=P\Lambda \\ A=P\lambda P^{-1}\]So what?
아니 그래서 대각화를 하면 어따 써먹는가?
- 행렬식 $\det(A)$를 쉽게 구할 수 있다.
- $A$의 거듭제곱, 역행렬, 대각합(tr), 최소 다항식등을 쉽게 구할 수 있다
이를 키르히호프 정리에 도입하면 그래프의 스패닝 트리의 개수를 $O(\lvert V \rvert\lvert E\rvert)$에 계산할 수 있다!