역행렬

1. 정방행렬 $A$가 가역 행렬일 경우 $A^{-1}A=I$, $AA^{-1}=I$가 성립한다.
2. 행렬의 가역성을 테스트 하는 알고리즘은 elimination이며, $A$(row echelon form)는 반드시 0이 아닌 $n$개의 pivot을 지녀야 한다.
3. 행렬대수 관점에서 가역성을 확인할 때, 가역 행렬은 행렬식 $\det(A) \neq 0$을 만족해야 한다.
4. 방정식 $Ax=0$ 관점에서 가역성을 확인할 때, 가역 행렬은 오직 $x=0$ 만이 유일한 해로 존재해야 한다.
5. 행렬 $A$, $B$가 같은 shape이고, 가역이라면 $AB$ 에 대해 다음이 성립한다: $(AB)^{-1}=B^{-1}A^{-1}$

• 역행렬은 elimination 이 n개의 pivot을 생성할 때만 역행렬이 존재한다.

• 행렬 $A$ 는 두 개 이상의 다른 역행렬을 가질 수 없다. $BA=I, \ AC=I$ 가 성립할 경우 반드시 $B=C$ 이다.

• $A$ 가 가역일 경우, $Ax=b$ 의 유일한 해는 $x=A^{-1}x$ 이다.

  • $A^{-1}Ax=A^{-1}b \to x=A^{-1}b$

• $Ax=0$ 에 0이 아닌 해 $x$ 가 존재할 경우, $A$ 는 비가역이다. 어떤 행렬도 0을 $x$로 되돌릴 수 없다.

• shape=(2,2) 행렬에서 가역성을 지니려면 행렬식 $\det(A)$ 에 대해 $ad-bc \neq 0$ 이 성립해야 한다.

  • $\begin{bmatrix}a & b \\ c & d\end{bmatrix}^{-1}=\frac{1}{ad-bc}=\begin{bmatrix}d & -b \\ -c & a\end{bmatrix}$

• 대각행렬의 대각 요소 $d_1~d_n$에 대해 0이 존재해서는 안된다.

  • 대각행렬의 역은 각 대각 요소의 역이다.

• 제거 행렬의 역행렬:

  • $E=\begin{bmatrix}1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}, \ \ E^{-1}=\begin{bmatrix}1 & 0 & 0 \\ 5 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}$ 제거를 수행할 때 계산 순서의 중요성: 제거 E 이후 제거 F를 적용하는 경우
  • $E: b_2 \leftarrow b_2-5b_1$
  • $F: b_3 \leftarrow b_3-4b_2$ $F=\begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -4 & 1\end{bmatrix}, \ \ F=\begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 4 & 1\end{bmatrix}$ $E \to F$ 순서로 제거를 수행할 경우, row3 이 row1의 영향을 받는다. 즉, 행렬 적용 결과로 복잡한 상호작용항 20 FE(3,1)이 추가된다. $FE=\begin{bmatrix}1 & 0 & 0 \\ -5 & 1 & 0 \\ 20 & -4 & 1\end{bmatrix}$ $FE: R_3 \leftarrow R_3-4(R_2-5R_1) = R_3-4R_2+20R_1$ 그래서 $(FE)^{-1}=E^{-1}F^{-1}$을 적용함
  • $F^{-1}: R_3 \leftarrow R_3+3R_2$ : 3행 연산이 종료됨
  • $E^{-1}: R_2 \leftarrow R_2 + 3R_1$ ; 2행 연산이 종료됨 즉, 연산이 분리되게 됨. $E^{-1}F^{-1}=\begin{bmatrix}1 & 0 & 0 \\ 5 & 1 & 0 \\ 0 & 4 & 1\end{bmatrix} = L$

  이는 $A=LU$를 이용하는 이유임

  • 행렬 $A$를 소거해서 위삼각행렬 $U$를 만드는 연산: $U=FEA$
  • $U$에서 다시 $A$로 복구하는 연산: $A=E^{-1}F^{-1}U$ ($A^{-1}A=I$ 에 의해)
    • 이때 $A=LU$ 라면, $L=E^{-1}F^{-1}$
  • 소거 과정의 기록(=곱해준 행연산들)을 전부 포함한 하나의 행렬 $L$을 얻을 수 있음.

Gauss-Jordan 소거법: $A^{-1}$ 계산

$AA^{-1}=I$ 에서, $A^{-1}$의 각 행을 ${x_1, x_2, x_3}$로 봄
즉, $A[x_1, x_2, x_3]=[e_1, e_2, e_3]=I$

핵심 접근법: $[A \ \ I]$ 에 $A^{-1}$ 을 곱함: $A^{-1}[A \ \ I] \to [I \ \ A^{-1}]$ 을 도출, 역행렬을 계산함

가우스 소거(위삼각행렬) -> 조단(pivot 위아래를 모두 0으로: dens matrix), -> 이후 첨가행렬의 모든 행을 dense matrix의 각 diagonal entris로 나눔

가우스-조단 소거법은 $n$개의 방정식을 모두 해결(solving) 함.
예를 들어, 아래 세개의 방정식을 해결해야 함. $Ax_1=(1,0,0), Ax_2=(0,1,0),Ax_3=(0,0,1)$

이를 위해 첨가행렬 $[A \ \ b]$ 를 구성하여 역행렬을 구함.

예시로 행렬 $K$ 와 $I$로 첨가행렬 $[K \ e_1 \ e_2 \ e_3]$ 를 구성하여 가우스-조단 소거

$$\begin{align} [K \ e_1 \ e_2 \ e_3]=\begin{bmatrix}2 & -1 & 0 & 1 & 0 & 0 \\ -1 & 2 & -1 & 0 & 1 & 0 \\ 0 &-1 & 2 & 0 & 0 & 1\end{bmatrix} \\ \to \begin{bmatrix}2 & -1 & 0 & 1 & 0 & 0 \\ 0 & \frac{2}{3} & -1 & \frac{1}{2} & 1 & 0 \\ 0 &-1 & 2 & 0 & 0 & 1\end{bmatrix} \ \ (\frac{1}{2}\text{row } 1+\text{row } 2) \\ \to \begin{bmatrix}2 & -1 & 0 & 1 & 0 & 0 \\ 0 & \frac{2}{3} & -1 & \frac{1}{2} & 1 & 0 \\ 0 &-1 & 2 & 0 & 0 & 1\end{bmatrix} \ \ (\frac{1}{2}\text{row } 1+\text{row } 2) \\ \to \begin{bmatrix}2 & -1 & 0 & 1 & 0 & 0 \\ 0 & \frac{2}{3} & -1 & \frac{1}{2} & 1 & 0 \\ 0 &0 & \frac{4}{3} & \frac{1}{3} & \frac{2}{3} & 1\end{bmatrix} \ \ (\frac{2}{3}\text{row } 2 + \text{row } 3) \end{align}$$

마지막 행렬의 첫 3열은 $U$ 이며, 피봇 $2, \frac{2}{3}, \frac{4}{3}$ 이 대각에 위치해있다.
가우스 소거법은 여기서 back substitution을 적용하지만, 조단 소거법은 (Reduced Echelon Form) $R=I$를 만든다.
[[행 사다리꼴]], [[기약행 사다리꼴]] 피봇 위의 행들을 0으로 만든다.

$$\begin{align} \text{(Zero above third pivot)} \quad \to \quad \begin{bmatrix} 2 & -1 & 0 & 1 & 0 & 0 \\ 0 & \frac{3}{2} & 0 & \frac{3}{4} & \frac{3}{2} & \frac{3}{4} \\ 0 & 0 & \frac{4}{3} & \frac{1}{3} & \frac{2}{3} & 1 \end{bmatrix} \quad (\frac{3}{4} \text{row } 3 + \text{row } 2) \\ \text{(Zero above second pivot)} \quad \to \quad \begin{bmatrix} 2 & 0 & 0 & \frac{3}{2} & 1 & \frac{1}{2} \\ 0 & \frac{3}{2} & 0 & \frac{3}{4} & \frac{3}{2} & \frac{3}{4} \\ 0 & 0 & \frac{4}{3} & \frac{1}{3} & \frac{2}{3} & 1 \end{bmatrix} \quad (\frac{2}{3} \text{row } 2 + \text{row } 1) \end{align}$$

즉, 가우스 소거 -> 조단: 피봇 위를 0으로 만들고 -> 모든 row들을 대각 피봇으로 나눔.

$$\begin{align} \begin{matrix} \text{(divide by 2)} \\ \text{(divide by } \frac{3}{2}\text{)} \\ \text{(divide by } \frac{4}{3}\text{)} \end{matrix} \quad \left[ \begin{array}{ccc|ccc} 1 & 0 & 0 & \frac{3}{4} & \frac{1}{2} & \frac{1}{4} \\ 0 & 1 & 0 & \frac{1}{2} & 1 & \frac{1}{2} \\ 0 & 0 & 1 & \frac{1}{4} & \frac{1}{2} & \frac{3}{4} \end{array} \right] = \begin{bmatrix} I & x_1 & x_2 & x_3 \end{bmatrix} = \begin{bmatrix} I & K^{-1} \end{bmatrix} \end{align}$$

1. $K$는 주대각 대칭, $K^{-1}$도 대칭
2. $K$는 삼중 대각 행렬(tridiagonal, 주대각 + 주대각 위아래, 나머진 0), 그러나 $K^{-1}$은 밀집 행렬(dense matrix)
3. 피봇의 곱은 $2(\frac{3}{2})(\frac{4}{3})=4$, 4는 행렬식 $det(K)=4$ $K^{-1}$은 $\det K$ 로 나누는 것을 포함하고, 따라서 행렬식이 0이면 역행렬이 존재할 수 없음. $K^{-1}=\frac{1}{4}=\begin{bmatrix}3 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 3\end{bmatrix}$ 가우스 소거 과정에서 행 교환이 없었을 경우, 가우스 소거 이후 $U$의 피봇들의 곱은 행렬식이다.

Gauss-Jordan 의 원리

$A^{-1}[A \ \ I] = [I \ \ A^{-1}]$

$[A \ | \ I ]\to [U\ |\ L^{-1}]$

1. $EA=U$
2. 양변에 $E^{-1}$을 곱함. $L$은 소거의 역연산
   • $E^{-1}EA=E^{-1}U$
   • $A=E^{-1}U$
   • $A=LU, \ L=E^{-1}$

삼각 행렬의 경우 대각 요소들이 0이 아닐경우 가역이다.

대각 우세 행렬(Diagonal dominant matricx)는 가역이다. (삼각 부등식($|a+b|\le|a|+|b|$)과 절댓값 성질($|ab|=|a||b|$) 이용)