Inverse Matrix

Definition of Inverse Matrix

행렬의 앞/뒤 어디에 곱하든 그 결과가 항등행렬 $I$가 되는 행렬

용어

• invertible, non-singular : 역행렬이 존재하는 행렬
• singular : 역행렬이 존재하지 않는 행렬

Properties of Inverse Matrix

1. Inverse Matrix는 유일하다. (1개이다)
   증명
   a. 만약 행렬 $A$가 역행렬 $B$와 $C$를 가진다고 가정하자.
   $AB = BA = I,\ \ AC=CA=I$
   b. $CA=I$의 양변에 $B$를 곱하면,
   $CAB = B$
   c. 이때, a에서 한 가정때문에 $AB=I$이다.
   $C = B$
   d. 역행렬 $B$와 $C$는 동일한 행렬일 수 밖에 없다. 따라서 Inverse Matrix는 유일하다.
2. $n\times n$ 행렬 $A$가 invertible하면 $A$는 $n$개의 pivot을 가진다.
   ↔️  $n\times n$ 행렬 $A$가 $n$개의 pivot을 가지면 $A$는 invertible matrix이다.
   증명
   a. $n\times n$ 행렬 $A$가 $n$개의 pivot을 가지면, Gauss Elimination을 이용하여 $A$를 row echelon form matrix으로 나타낼 수 있다.
   ex) $2\times2$ 행렬을 G.E하여 pivot $1, -4$ 2개를 가지는 row echelon form으로 변환했다.
   $\begin{bmatrix} 1 & 2 \\ 3 & 2 \end{bmatrix} \rightarrow^{G.E} \begin{bmatrix} \color{blue}1 & 2 \\ 0 & \color{blue}-4 \end{bmatrix}$
   b. 따라서 $Ax=b$는 무조건 해을 가지므로 해를 구하기 위해서 수식을 변형시키면 다음과 같다.
   $x = A^{-1}b$
   c. 따라서 행렬 $A$는 invertible matrix이다.

3. $L$: Low transform matrix(or $U$: Upper transform matrix)이 invertible matrix라면, 대각성분에 0이 존재하지 않는다.
   ↔  대각성분에 0이 없다면 $L$or$U$ 행렬은 invertible matrix이다.

   : pivot이 n개 존재하기 위해서는 0인 성분을 가져서는 안된다. (2번 성질과 동일한 의미)
   

4. Digonal Matrix: 대각행렬 $A$의 대각성분 중에서 0이 1개라도 존재한다면, $A$는 singular matrix이다.
   ↔️  singular matrix인 Digonal Matirx $A$의 대각성분에는 적어도 0이 1개 이상존재한다.

   : $0$인 원소를 대각성분에 가진다면 pivot은 0이 될 수 없기 때문에 $n\times n$ 행렬이 $n$개의 pivot을 가지지 않게 된다. (2번 성질과 동일한 의미)
   

5. $A$가 역행렬을 가지면 선형방정식 $Ax = b$는 $x = A^{-1}b$인 유일한 해를 가진다. (2번 성질과 동일한 의미)

6. 선형방정식 $Ax = 0$에서 $x$가 영벡터가 아니라면, $A$는 singular matrix이다.
   증명
   a. 일반적인 선형방정식을 풀 때처럼(3번)* 양변에 $A$의 inverse matrix를 곱한다.

   $x=A^{-1}0$

   b. $0$이 곱해졌기 떄문에 우변의 결과는 $0$이고, 따라서 좌변은 다음과 같다.

   $x=0$

   c. 따라서 $A$가 역행렬을 가지면(a) $Ax = 0$의 유일한 해는 $x=0$ (영벡터) 이다.
   ↔️  $x≠0$이면, $A$는 역행렬을 가지지 않는다.
   

7. (드모르간의 정리) $n\times n$ 행렬 $A$, $B$가 invertible matrix이면 다음의 식이 만족한다.

   $(AB)^{-1} = B^{-1}A^{-1}$

   증명
   a. 우변에 $AB$를 곱하여 정리한다.

   $AB(B^{-1}A^{-1})=AIA^{-1} = I$

   b. 정리한 결과가 항등행렬이므로, inverse matrix의 definition에 따라 성질이 참임을 보일 수 있다.

8. $2\times 2$ 행렬이 invertible이기 위한 조건 (필요충분)

   • 조건 : *행렬식**이 $0$이 아니다.
     $\text{if and only if}\ \ 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}$
   • 증명
     a. $a=0$ 이면, Gauss Elimination 과정에서 1행과 2행을 바꾸면서 $c$와 $b$가 pivot이 된다. pivot과 invertible의 관계에 의해 invertible 이려면 $c≠0, b≠0$
     $\begin{bmatrix} 0 & b \\ c & d \end{bmatrix} \rightarrow^{G.E} \begin{bmatrix} \color{blue}c & d \\ 0 & \color{blue}b\end{bmatrix}$
     $\text{if}\ a=0,\ \ c\neq0 \text{ and } b\neq 0$
     b. $a\neq0$ 이면, Gauss Elimination의 결과에 따라 $a$와 $d-{cb\over a}$가 pivot이 된다. pivot과 invertible의 관계에 의해 invertible이려면 $d-{cb\over a}\neq0 \rightarrow ad-cb \neq0$
     $\begin{bmatrix} a & b \\ c & d \end{bmatrix} \rightarrow^{G.E} \begin{bmatrix} \color{blue}a & b\\ 0 & \color{blue}{d-\frac{cb}{a}}\end{bmatrix}$
     $\text{if}\ a\neq0,\ \ ad-cb \neq0$

Gauss-Jordan Elimination

Gauss Elimination의 한계

Inverse matrix의 성질에 따라, $**n\times n$ 행렬이 $n$개의 pivot을 가지면 Invertible**하다는 것을 알 수 있다.

따라서 Gauss Elimination을 이용하여 행렬을 row echelon form으로 변환하고 pivot의 수를 세서 Invertible한지 아닌지를 알아낼 수 있다. 그러나 inverse matrix를 구하기 위해서 Gauss Elimination을 진행하기에는 계산량이 너무 과하다. $O(n^2)$

Gauss-Jordan elimination

Gauss-Jordan elimination은 일반적인 Gauss elimination과 크게 다르지 않지만, 행렬의 inverse matrix를 더 쉽게 구할 수 있도록 해준다.

행렬과 inverse matrix를 곱한 결과인 항등행렬 $I$의 각 열을 만드는 inverse matrix의 각 열 벡터를 계산하는 아이디어.

과정 (in $3\times 3$ matrix)

1. inverse matrix를 모르는 상태이므로 임의의 요소로 행렬을 만든다.

2. inverse matrix의 각 열을 하나의 열 벡터로 취급하여 표현한다.

   $A^{-1} = \begin{bmatrix} x_1 & y_1 & z_1 \\ x_2 & y_2 & z_2\\ x_3 & y_3 & z_3 \end{bmatrix} = \begin{bmatrix} \bold{x} & \bold{y} & \bold{z} \end{bmatrix}$

3. 이렇게 표현한 행렬을 이용하면, $AA^{-1}$을 다음과 같은 수식으로 표현할 수 있다.

   $AA^{-1} = \begin{bmatrix} A\bold{x} & A\bold{y} & A\bold{z} \end{bmatrix}=I$

4. 항등행렬의 각 열을 $\bold{e_1, e_2, e_3}$으로 두면, 다래와 같은 3개의 방정식을 만들어낼 수 있다.

   $I = \begin{bmatrix} 1 & 0 & 0 \\ 0& 1 & 0\\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} \bold{e_1} & \bold{e_2} & \bold{e_3} \end{bmatrix}$
   $A\bold{x} = \bold{e_1}\\ A\bold{y} = \bold{e_2}\\ A\bold{z} = \bold{e_3}\\$

5. 이는 연립방정식의 형태와 크게 다르지 않기에, 3개의 방정식을 한번에 표현하여 Gauss Elimintation을 진행하여 Digonal Matrix를 만든다.

   *일반적인 Gauss Elimination과 다른점은 위로도 행 소거연산이 가능하다.

   $\left[\begin{array}{c|ccc}A & \bold{e_1} & \bold{e_2} & \bold{e_3} \end{array}\right]$

6. elimination이 끝나면 $A$가 항등행렬로 표현될 수 있게 pivot이 1이 되도록 행마다 상수곱을 해준다.

   → 즉, Elimination을 끝낸 $A$행렬이 항등행렬이 된다.

7. $A\bold{x} = \bold{e_1}$가 $I\bold{x} = A^{-1}$의 첫번째 열이 된다.

   → 즉, Elimination을 끝낸 $\begin{bmatrix} \bold{e_1} & \bold{e_2} & \bold{e_3} \end{bmatrix}$ 행렬이 Inverse matrix가 된다.

   $[A|I] \rightarrow^{G-J} [I|A^{-1}]$

G-J 과정을 거쳐 $A$를 항등행렬로 표현하는 과정은, 역행렬 $A^{-1}$을 곱한 결과와 동일하기 때문에 $A$와 함께 표현된 항등행렬$I$에 $A^{-1}$이 곱해졌다고 생각하면 $A^{-1}$을 얻을 수 있다.

Gauss-Jordan elimination Example.

1. augmentend matrix form

   $\left[\begin{array}{ccc|ccc}2 & -1 & 0 & 1 & 0 & 0 \\ -1 & 2 & -1 & 0 & 1 & 0 \\ 0 & -1 & 2 & 0 & 0 & 1 \end{array}\right]$

2. Gauss-Jordan Elimination

   $\rightarrow^{G.E}\left[\begin{array}{ccc|ccc}2 & -1 & 0 & 1 & 0 & 0 \\ 0 & \frac{3}{2} & -1 & \frac{1}{2} & 1 & 0 \\ 0 & -1 & 2 & 0 & 0 & 1 \end{array}\right]\ \rightarrow^{G.E}\left[\begin{array}{ccc|ccc}2 & -1 & 0 & 1 & 0 & 0 \\ 0 & \frac{3}{2} & -1 & \frac{1}{2} & 1 & 0 \\ 0 & 0 & \frac{4}{3} & \frac{1}{3} & \frac{2}{3} & 1 \end{array}\right]$

   G.E upward***

   $\rightarrow^{G.E\ up}\left[\begin{array}{ccc|ccc}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{array}\right]\ \rightarrow^{G.E\ up}\left[\begin{array}{ccc|ccc}2 & 0 & 0 & \frac{2}{3} & 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{array}\right]$

3. Scaliling

   $\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]$

역행렬을 갖지 않는 행렬에 Gauss-Jordan elimination을 적용하면 breakdown이 일어나서 해가 존재하지 않는다.

→ 역행렬이 존재하지 않음을 알 수 있다.