M4AI) 기타 등등의 decomposition: LU / PLU / LDU

이건 뭔가.. additional topic 느낌이 강해서 대강만 짚고 넘어가겠음

 

LU

low, upper의 약자인거 같은데, upper triangular matrix와 lower triangular matrix 두 개의 곱으로 나타내어 주는 거 같습니당

가우스 조던 소거법 적용해주듯이 하면 된대요.

말로 하면 잘 안 와닿으니까 예제 한 번 봅시다.. 사실 안 중요한 거 같은데 그냥 이해나 할라고

$$\begin{bmatrix} 2 &1 &-1 \\ -3 & -1 & 2 \\ -2 &1&2\end{bmatrix} \Rightarrow \begin{bmatrix} 2 &1 &-1 \\ 0 & \frac{1}{2} & \frac{1}{2} \\ -2 &1&2\end{bmatrix}$$

첫 번째 행에 $\frac{3}{2}$을 곱해주고 두 번째 행에서 빼준 결과인데요, 이건 가만히 생각해보면 요래 표현할 수 있습니다.

$$\begin{align}\mathbf{A} & = \begin{bmatrix} 2 &1 &-1 \\ -3 & -1 & 2 \\ -2 &1&2\end{bmatrix} \\ & = \begin{bmatrix} 1 &0 &0 \\ \frac{3}{2} & 1 & 0 \\ 0 &0&1\end{bmatrix} \begin{bmatrix} 2 &1 &-1 \\ 0 & \frac{1}{2} & \frac{1}{2} \\ -2 &1&2\end{bmatrix}\\&=\begin{bmatrix} 1 &0 &0 \\ \frac{3}{2} & 1 & 0 \\ 0 &0&1\end{bmatrix}\begin{bmatrix}\mathbf{a}_1^\top\\\mathbf{a}_2^\top\\\mathbf{a}_3^\top\end{bmatrix} \\ &= \cdots \\ &= \mathbf{L}\mathbf{U} \end{align}$$  
여기서 전치 표시는 그냥 행 벡터를 표기할 때 쓰는 노테이션일 뿐임

 

암튼 이걸 계산하는 게 결국 가우스-조던 소거법이랑 똑같은 거 아니겠어요~ 이런 아이디어로 upper/lower triangular 구하는 거임

 

혁펜하임: 어따 쓰냐?

A: $\mathbf{A}\mathbf{x}=\mathbf{b} \Rightarrow (1)\: \mathbf{L}\mathbf{y}=\mathbf{b}\quad (2)\: \mathbf{U}\mathbf{x}=\mathbf{y}$ 로 구하면 쉬워진대

PLU

가끔 LU 분해가 안되는 일이 있대요 가령 $a_{11}=1$일 때.. 그럼 행의 순서를 바꿔주면 풀리는데 (연립방정식 푸는 상황에서는 행의 순서 자체가 중요하진 않아서) 그때 Permutation matrix라는 말을 쓰는데, 별건 아니고

$$\begin{gather}\mathbf{P} = \begin{bmatrix} 0 &1 &0 \\ 1 & 0 & 0 \\ 0 &0&1\end{bmatrix}, \\ \Rightarrow \quad \mathbf{P}\mathbf{A}=\mathbf{L}\mathbf{U}\end{gather}$$

이게 다임

LDU

D는 diagonal matrix를 의미하는데요, 원래 LU 분해에서 L은 diagonal term이 모두 1인데 U는 꼭 그렇진 않거든요. 그래서 U도 그렇게 만들어주고자 D를 설정했다고 해요.

 

 

Similar Matrix

서울대 인공지능 면접질문이람서? similar matrix끼리는 eigenvalue가 같냐?

$\text{Definition:}$ $m\times n$ 행렬 $\mathbf{A}$에 대해, $\mathbf{B} = \mathbf{P}\mathbf{A}^{-1}\mathbf{P}$를 만족하는 $\mathbf{P}$ (위의 permutation 아님..) 가 존재하면 A, B는 서로 similar하다고 하고, 아래의 성질을 만족합니다.

1. A는 스스로 similar 하다.
2. B가 A와 similar하면 A도 B와 similar하다
3. A, B가 similar하고 B, C가 similar하면, A, C도 similar하다.
4. A와 B의 rank가 같다.
5. Trace가 같다! (A, B), (B,C), (C, A) => circular!
6. $\det$가 같다! 
7. eigenvalue도 같다! eigenvector는 다를 수 있어요 (P만큼 돌아가 있다는데 '회전된 만큼'이라는 게 뭔소린진 잘 모르겠,,)

ㅋㅋ 나 면접 볼 수 있는 걸까