2.5. Inverse Matrices

선형대수학 글 목록

연결 강의: MIT 18.06 Linear Algebra - Lecture 3: Multiplication and inverse matrices

1. 역행렬의 정의

정사각행렬 AA에 대해 어떤 행렬 A−1A^{-1}이 존재해서 다음을 만족하면, AA를 invertible matrix라고 한다.

A−1A=IA^{-1}A=I

그리고 동시에 다음도 성립한다.

AA−1=IAA^{-1}=I

이때 A−1A^{-1}을 AA의 inverse matrix, 즉 역행렬이라고 한다.

역행렬은 행렬에서 나눗셈과 비슷한 역할을 한다. 하지만 행렬에서는 일반적인 숫자처럼 단순히 나누는 연산이 없기 때문에, 곱했을 때 항등행렬을 만드는 행렬을 따로 정의한다.

2. 가역성을 확인하는 여러 관점

행렬 AA가 가역인지 확인하는 관점은 여러 가지가 있다.

2.1 Elimination 관점

가역성을 확인하는 가장 계산적인 방법은 elimination이다.

n×nn \times n 행렬 AA가 가역이려면 elimination 과정에서 반드시 nn개의 pivot이 나와야 한다.

즉, 어떤 단계에서도 pivot이 0이 되어 소거가 멈추면 안 된다.

모든 pivot이 존재하면 AA는 invertible matrix이다.

2.2 Determinant 관점

행렬대수 관점에서는 determinant로 가역성을 확인할 수 있다.

det⁡(A)≠0⟺A is invertible\det(A)\neq 0 \quad \Longleftrightarrow \quad A \text{ is invertible}

반대로,

det⁡(A)=0⟺A is singular\det(A)=0 \quad \Longleftrightarrow \quad A \text{ is singular}

이다.

2.3 Nullspace 관점

방정식 관점에서는 다음 homogeneous equation을 본다.

Ax=0Ax=0

AA가 가역이려면 이 방정식의 해가 오직 zero solution이어야 한다.

x=0x=0

만약 0이 아닌 해가 존재한다면 AA는 가역이 아니다.

왜냐하면 Ax=0Ax=0에서 서로 다른 xx가 같은 출력 0으로 가기 때문이다. 이런 경우에는 어떤 행렬도 0을 원래의 xx로 되돌릴 수 없다.

3. 역행렬의 기본 성질

역행렬과 관련해 기억해야 할 기본 성질들이 있다.

3.1 역행렬은 유일하다

행렬 AA는 두 개 이상의 다른 역행렬을 가질 수 없다.

예를 들어 BA=IBA=I이고 AC=IAC=I라고 하자.

그러면 다음과 같이 정리할 수 있다.

B=BIB = BI

그리고 AC=IAC=I이므로,

B=B(AC)B = B(AC)

결합법칙을 적용하면,

B=(BA)CB = (BA)C

BA=IBA=I이므로,

B=IC=CB = IC = C

따라서 B=CB=C이다.

즉, left inverse와 right inverse가 모두 존재한다면 둘은 반드시 같은 행렬이다.

3.2 Ax=bAx=b의 해

AA가 가역이면 Ax=bAx=b의 해는 유일하다.

양변에 A−1A^{-1}을 곱하면 된다.

Ax=bAx=b A−1Ax=A−1bA^{-1}Ax=A^{-1}b

따라서,

x=A−1bx=A^{-1}b

이다.

3.3 곱의 역행렬

두 행렬 AA, BB가 같은 크기의 정사각행렬이고 둘 다 가역이면, ABAB도 가역이다.

이때 다음이 성립한다.

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

순서가 반대로 뒤집히는 점이 중요하다.

확인하면 다음과 같다.

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

즉, ABAB를 되돌리려면 먼저 BB를 되돌리고, 그 다음 AA를 되돌려야 한다.

4. 간단한 역행렬 예시

4.1 2×22 \times 2 행렬

2×22 \times 2 행렬

A=[abcd]A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}

가 가역이려면 determinant가 0이 아니어야 한다.

ad−bc≠0ad-bc \neq 0

이때 역행렬은 다음과 같다.

A−1=1ad−bc[d−b−ca]A^{-1} = \frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}

여기서 분모 ad−bcad-bc가 0이면 역행렬은 존재할 수 없다.

4.2 대각행렬

대각행렬은 역행렬을 구하기 쉽다.

D=[d10⋯00d2⋯0⋮⋮⋱⋮00⋯dn]D = \begin{bmatrix} d_1 & 0 & \cdots & 0 \\ 0 & d_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_n \end{bmatrix}

이 행렬이 가역이려면 모든 대각성분이 0이 아니어야 한다.

di≠0(i=1,…,n)d_i \neq 0 \quad (i=1,\dots,n)

그러면 역행렬은 각 대각성분을 역수로 바꾼 행렬이다.

D−1=[1d10⋯001d2⋯0⋮⋮⋱⋮00⋯1dn]D^{-1} = \begin{bmatrix} \frac{1}{d_1} & 0 & \cdots & 0 \\ 0 & \frac{1}{d_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \frac{1}{d_n} \end{bmatrix}

5. Elimination matrix의 역행렬

소거행렬도 역행렬을 가진다.

예를 들어 다음 행렬 EE를 보자.

E=[100−510001]E = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}

이 행렬은 다음 행 연산을 수행한다.

R2←R2−5R1R_2 \leftarrow R_2 - 5R_1

이 연산을 되돌리려면 반대로 5R15R_1을 더하면 된다.

따라서 역행렬은 다음과 같다.

E−1=[100510001]E^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 5 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}

즉, elimination matrix의 역행렬은 같은 위치의 multiplier 부호를 반대로 바꾼 형태이다.

6. 여러 elimination의 순서

이번에는 두 개의 elimination을 연속으로 적용한다고 하자.

첫 번째 연산은 다음이다.

E:R2←R2−5R1E: \quad R_2 \leftarrow R_2 - 5R_1

두 번째 연산은 다음이다.

F:R3←R3−4R2F: \quad R_3 \leftarrow R_3 - 4R_2

각 elimination matrix는 다음과 같다.

E=[100−510001],F=[1000100−41]E = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad F = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -4 & 1 \end{bmatrix}

두 연산을 EE 다음 FF 순서로 적용하면 전체 행렬은 FEFE이다.

FE=[100−51020−41]FE = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 20 & -4 & 1 \end{bmatrix}

여기서 (3,1)(3,1) 위치에 2020이 생긴다.

왜냐하면 FF가 적용될 때의 두 번째 행은 이미 EE에 의해 바뀐 상태이기 때문이다.

실제로 세 번째 행 연산은 다음처럼 해석된다.

R3←R3−4(R2−5R1)R_3 \leftarrow R_3 - 4(R_2 - 5R_1)

따라서,

R3←R3−4R2+20R1R_3 \leftarrow R_3 - 4R_2 + 20R_1

이다.

즉, 행렬곱에서는 이전 elimination의 영향이 뒤쪽 elimination에 반영된다.

7. 전체 elimination을 되돌리는 순서

EE 다음 FF를 적용한 행렬은 FEFE이다.

따라서 이를 되돌리는 역행렬은 다음이다.

(FE)−1=E−1F−1(FE)^{-1}=E^{-1}F^{-1}

순서가 반대로 바뀌는 것이 핵심이다.

각 역행렬은 다음과 같다.

E−1=[100510001],F−1=[100010041]E^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 5 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad F^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 4 & 1 \end{bmatrix}

따라서,

E−1F−1=[100510041]E^{-1}F^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 5 & 1 & 0 \\ 0 & 4 & 1 \end{bmatrix}

이 행렬은 LL로 볼 수 있다.

즉, 소거를 수행하는 행렬들이 EE, FF라면,

U=FEAU=FEA

이고, 다시 UU에서 AA로 돌아가면 다음과 같다.

A=E−1F−1UA=E^{-1}F^{-1}U

따라서,

A=LUA=LU

이며,

L=E−1F−1L=E^{-1}F^{-1}

이다.

즉, LL은 elimination을 되돌리는 행렬들을 모아둔 것이다.

8. Gauss-Jordan 소거법의 목적

Gauss-Jordan 소거법은 역행렬을 직접 계산하는 방법이다.

기본 아이디어는 다음 식에서 출발한다.

AA−1=IAA^{-1}=I

A−1A^{-1}의 column들을 x1,x2,…,xnx_1,x_2,\dots,x_n이라고 하면,

A[x1 x2 ⋯ xn]=[e1 e2 ⋯ en]=IA[x_1 \ x_2 \ \cdots \ x_n] = [e_1 \ e_2 \ \cdots \ e_n] = I

즉, 역행렬을 구하는 것은 다음 nn개의 방정식을 동시에 푸는 것과 같다.

Ax1=e1,Ax2=e2,…,Axn=enAx_1=e_1, \quad Ax_2=e_2, \quad \dots, \quad Ax_n=e_n

이를 한 번에 처리하기 위해 augmented matrix를 만든다.

[A  I][A \ \ I]

그리고 행 연산을 통해 왼쪽의 AA를 II로 만들면, 오른쪽에는 A−1A^{-1}이 남는다.

[A  I]⟶[I  A−1][A \ \ I] \longrightarrow [I \ \ A^{-1}]

이것이 Gauss-Jordan 소거법의 핵심이다.

9. Gauss-Jordan 소거 과정

Gauss-Jordan 소거는 크게 세 단계로 볼 수 있다.

  1. Gaussian elimination으로 아래쪽을 0으로 만들어 upper triangular matrix UU를 만든다.
  2. Jordan step으로 pivot 위쪽도 0으로 만든다.
  3. 각 row를 pivot으로 나누어 왼쪽을 identity matrix로 만든다.

Gaussian elimination은 보통 UU를 만든 뒤 back substitution을 한다.

반면 Gauss-Jordan은 back substitution을 행렬 연산으로 끝까지 밀어붙여서 왼쪽을 II로 만든다.

10. 예시 행렬 KK

다음 행렬을 생각하자.

K=[2−10−12−10−12]K = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}

역행렬을 구하기 위해 augmented matrix [K  I][K \ \ I]를 만든다.

[2−10100−12−10100−12001]\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]

먼저 첫 번째 pivot 22를 사용해서 두 번째 행의 첫 번째 성분을 제거한다.

R2←R2+12R1R_2 \leftarrow R_2+\frac{1}{2}R_1

그러면 다음이 된다.

[2−10100032−112100−12001]\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]

다음으로 두 번째 pivot 32\frac{3}{2}를 사용해서 세 번째 행의 두 번째 성분을 제거한다.

R3←R3+23R2R_3 \leftarrow R_3+\frac{2}{3}R_2

그러면 다음 upper triangular form을 얻는다.

[2−10100032−11210004313231]\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]

왼쪽 첫 3열은 UU이고, pivot은 다음과 같다.

2,32,432,\quad \frac{3}{2},\quad \frac{4}{3}

11. Pivot 위쪽까지 제거하기

Gaussian elimination은 여기서 back substitution으로 해를 구한다.

Gauss-Jordan은 한 단계 더 진행해서 pivot 위쪽까지 0으로 만든다.

먼저 세 번째 pivot 위의 −1-1을 제거한다.

R2←R2+34R3R_2 \leftarrow R_2+\frac{3}{4}R_3

그러면 다음과 같다.

[2−101000320343234004313231]\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]

이제 두 번째 pivot 위의 −1-1을 제거한다.

R1←R1+23R2R_1 \leftarrow R_1+\frac{2}{3}R_2

그러면 다음과 같다.

[200321120320343234004313231]\left[ \begin{array}{ccc|ccc} 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{array} \right]

마지막으로 각 row를 자신의 pivot으로 나눈다.

[10034121401012112001141234]\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]

따라서 오른쪽 블록이 K−1K^{-1}이다.

K−1=[34121412112141234]K^{-1} = \begin{bmatrix} \frac{3}{4} & \frac{1}{2} & \frac{1}{4} \\ \frac{1}{2} & 1 & \frac{1}{2} \\ \frac{1}{4} & \frac{1}{2} & \frac{3}{4} \end{bmatrix}

또는 다음처럼 쓸 수 있다.

K−1=14[321242123]K^{-1} = \frac{1}{4} \begin{bmatrix} 3 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 3 \end{bmatrix}

12. 예시에서 볼 수 있는 점

위 예시에서 몇 가지 중요한 사실을 확인할 수 있다.

12.1 대칭행렬의 역행렬

KK는 symmetric matrix이다.

KT=KK^T=K

계산 결과 K−1K^{-1}도 대칭행렬이다.

(K−1)T=K−1(K^{-1})^T=K^{-1}

대칭인 가역행렬의 역행렬도 대칭이 된다는 사실을 이 예시에서 볼 수 있다.

12.2 Sparse matrix의 inverse는 dense할 수 있다

KK는 tridiagonal matrix이다.

즉, 주대각선과 그 위아래 대각선에만 값이 있고 나머지는 0이다.

하지만 K−1K^{-1}은 거의 모든 entry가 0이 아닌 dense matrix이다.

즉, 원래 행렬이 sparse하다고 해서 역행렬도 sparse하다는 보장은 없다.

12.3 Pivot의 곱과 determinant

소거 과정에서 나온 pivot은 다음과 같다.

2,32,432,\quad \frac{3}{2},\quad \frac{4}{3}

행 교환이 없었으므로 determinant는 pivot들의 곱이다.

det⁡K=2⋅32⋅43=4\det K = 2\cdot \frac{3}{2}\cdot \frac{4}{3} = 4

역행렬 공식에 determinant가 분모로 등장한다는 점도 여기서 확인할 수 있다.

K−1=14[321242123]K^{-1} = \frac{1}{4} \begin{bmatrix} 3 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 3 \end{bmatrix}

det⁡K=0\det K=0이었다면 이 나눗셈은 불가능하고, 역행렬도 존재하지 않는다.

13. Gauss-Jordan과 LU 분해의 연결

Gauss-Jordan의 기본 원리는 다음 한 줄로 요약할 수 있다.

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

실제로는 A−1A^{-1}을 모르기 때문에 행 연산으로 [A  I][A \ \ I]를 [I  A−1][I \ \ A^{-1}]로 바꾼다.

소거행렬들을 모두 곱한 행렬을 EE라고 하면,

EA=UEA=U

이다.

이때 EE는 AA를 UU로 만드는 모든 elimination을 담고 있다.

양변에 E−1E^{-1}을 곱하면,

A=E−1UA=E^{-1}U

여기서 E−1E^{-1}이 바로 LL이다.

A=LUA=LU

즉, LL은 elimination을 되돌리는 행렬이고, UU는 elimination을 통해 얻은 upper triangular matrix이다.

14. 삼각행렬과 대각우세행렬

삼각행렬은 가역성 판별이 쉽다.

삼각행렬이 가역이려면 대각성분이 모두 0이 아니어야 한다.

예를 들어 upper triangular matrix

U=[d1∗∗0d2∗00d3]U = \begin{bmatrix} d_1 & * & * \\ 0 & d_2 & * \\ 0 & 0 & d_3 \end{bmatrix}

에서 다음이 성립하면 UU는 가역이다.

d1d2d3≠0d_1d_2d_3 \neq 0

일반적으로도 삼각행렬의 determinant는 대각성분의 곱이다.

det⁡U=d1d2⋯dn\det U = d_1d_2\cdots d_n

따라서 대각성분 중 하나라도 0이면 역행렬이 존재하지 않는다.

또 하나 중요한 경우는 strict diagonal dominance이다.

각 행에서 대각성분의 절댓값이 나머지 성분들의 절댓값 합보다 크면, 그 행렬은 가역이다.

즉, 모든 ii에 대해 다음이 성립하면 된다.

∣aii∣>∑j≠i∣aij∣|a_{ii}| > \sum_{j\neq i}|a_{ij}|

이 조건은 삼각부등식과 절댓값 성질을 이용해 증명할 수 있다.

직관적으로는 대각성분이 각 행에서 충분히 강하면, 어떤 column이나 row가 다른 것들의 조합으로 완전히 무너질 수 없다는 뜻이다.

15. 정리

이번 내용의 핵심은 역행렬이 언제 존재하고, 어떻게 계산되는지이다.

  1. AA가 가역이면 A−1A=IA^{-1}A=I이고 AA−1=IAA^{-1}=I이다.
  2. AA가 가역이려면 elimination에서 nn개의 pivot이 필요하다.
  3. Ax=0Ax=0이 0이 아닌 해를 가지면 AA는 singular matrix이다.
  4. Ax=bAx=b의 해는 AA가 가역일 때 x=A−1bx=A^{-1}b이다.
  5. 곱의 역행렬은 순서가 뒤집힌다.
(AB)−1=B−1A−1(AB)^{-1}=B^{-1}A^{-1}
  1. Elimination matrix의 역행렬은 해당 row operation을 되돌리는 행렬이다.
  2. Gauss-Jordan 소거법은 [A  I][A \ \ I]를 [I  A−1][I \ \ A^{-1}]로 바꾸어 역행렬을 구한다.
  3. A=LUA=LU에서 LL은 elimination의 inverse들을 모은 행렬이고, UU는 elimination 결과이다.
  4. 삼각행렬은 대각성분이 모두 0이 아닐 때 가역이다.
  5. Strictly diagonally dominant matrix는 가역이다.