[선형대수학] 가우스-요르단 소거법으로 n차 정방행렬의 역행렬 구하기

2차 정방행렬(정사각형행렬)의 역행렬을 구하는 법은 고등학교 수학과정을 배운 사람이라면 모두 다 알 것이다. 다음과 같은 2차 정방행렬이 있다.

 

$A = \begin{bmatrix} 1 & 2\\  3 & 4 \end{bmatrix}$

 

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

 

$A^{-1} = -\frac{1}{2}\begin{bmatrix} 4 & -2\\  -3 & 1 \end{bmatrix}$

 

방금 나는 아래 공식에 따라 역행렬을 구했다. 아마 익숙한 공식일 것이다. 

 

2차 정방행렬의 역행렬 구하는 공식

그런데 이 공식은 2차 정방행렬에만 적용될 수 있다. 만약 정방행렬의 차수가 3차, 4차,..., n차라면 역행렬을 어떤 방식으로 구할 수 있을까? 오늘은 바로 그에 대한 해결책에 대해 살펴보려고 한다. 

 

가우스-요르단 소거법으로 n차 정방행렬의 역행렬 구하기

가역(invertible)인 n차 정방행렬의 역행렬은 가우스-요르단 소거법으로 구할 수 있다. 가역이라는 것은 역행렬이 존재한다는 뜻이다. 가우스-요르단 소거법의 기본적인 아이디어는 다음과 같다.

 

"AX = I(항등행렬)라면 X는 A의 역행렬일 것이다. AX의 좌변을 IX로 바꿔주기 위해 기본행연산(elementary row operation)을 해주면, 그에 따라 우변도 바뀌게 될 것이고, 그 우변의 값이 바로 A의 역행렬을 의미하게 된다."

 

자, 이 말이 무슨 뜻인지 천천히 하나하나 살펴보자. 일단 기본행연산은 연립방정식의 해를 바꾸지 않으면서 행렬을 변형하는 방법들로 다음과 같은 것들을 포함한다.

 

1) 행렬의 한 행을 상수배한다.

2) 행렬의 두 행을 맞바꾼다.

3) 한 행을 상수배하여 다른 행에 더한다. 

 

여기서 행렬의 각 행은 각 일차방정식을 의미한다. 우리가 연립일차방정식의 해를 구할 때를 생각해보자. 해를 구하기 위해 어떤 일차방정식에는 상수배를 해주기도 하고, 또 상수배를 곱한 일차방정식을 또다른 일차방정식에서 더해주거나 빼주기도 한다. 그리고 각 일차방정식의 나열 순서는 계산 편의에 따라 바꿔주기도 한다. 이런 과정들을 해준다고 그 연립일차방정식의 해가 바뀌었던가? 그렇지 않았다. 해는 결국 동일했다. 

 

이러한 기본행연산을 행렬로 나타낸 것을 기본 행렬(elementary matrix)이라고 한다. 보통 E라고 표기한다.

 

우리는 $AX = I$의 좌변에 여러 개의 기본행렬을 곱해줘서 $AX$가 $IX$로 변하게 하고 싶다. 이것을 행렬의 곱으로 나타내면 다음과 같이 나타낼 수 있다.

 

$E_rE_{r-1}...E_2E_1AX = E_rE_{r-1}...E_2E_1I$

 

$IX = E_rE_{r-1}...E_2E_1I$

 

어떤 행렬에 항등행렬을 곱해주면 행렬 그 자신이 나오므로, 

 

$X = E_rE_{r-1}...E_2E_1$ 

 

이다. 따라서 A의 역행렬 $A^{-1}$은 $E_rE_{r-1}...E_2E_1$이다. X가 A의 역행렬이라고 위에서 언급했었다. 

 

가우스-요르단 소거법으로 3차 정방행렬의 역행렬 구하기 예제

아마 위 증명 과정이 막연하게 느껴지실 수도 있을 것 같다. 예제를 통해서 가우스-요르단 소거법을 좀 더 확실히 이해해보자. 다음과 같은 3차 정방행렬이 있다. 

 

$A = \begin{bmatrix} 2 & 1 & 1\\  4 & -6 & 0\\  -2 & 7 & 2 \end{bmatrix}$ 

 

가우스-요르단 소거법을 이용해서 A의 역행렬을 구해보자.

 

$AX = I$라면 X는 A의 역행렬일 것이다. 여기서 X와 I는 모두 3차 정방행렬이다. 기본행렬을 좌변과 우변의 왼쪽에 곱해주어 좌변의 A를 I로 바꿔줄 것이다. 그 결과 우리는 X, 즉 A의 역행렬을 알게 된다. 자, 이제 시작해보자. 

 

$AX = I$

 

$\begin{bmatrix} 2 & 1 & 1\\  4 & -6 & 0\\  -2 & 7 & 2 \end{bmatrix}X = \begin{bmatrix} 1 & 0 & 0\\  0 & 1 & 0\\  0 & 0 & 1 \end{bmatrix}$ 

 

먼저 A가 대각 성분 아래쪽이 모두 0인 상삼각행렬(upper triangular matrix)이 되도록 기본행연산을 해줄 것이다. 이를 위해 두번째 행과 세번째 행에서 첫번째 행의 상수배를 각각 빼준다.  

 

$\begin{bmatrix} 2 & 1 & 1\\  0 & -8 & -2\\  0 & 8 & 3 \end{bmatrix}X = \begin{bmatrix} 1 & 0 & 0\\  -2 & 1 & 0\\  1 & 0 & 1 \end{bmatrix}$

 

두번째 행에서는 첫번째 행을 2배한 것을 빼줬고, 세번째 행에서는 첫번째 행을 1배한 것을 더해줬다(-1배한 것을 빼줬다). 이번에는 세번째 행에서 두번째 행의 상수배를 빼준다. 

 

$\begin{bmatrix} 2 & 1 & 1\\  0 & -8 & -2\\  0 & 0 & 1 \end{bmatrix}X = \begin{bmatrix} 1 & 0 & 0\\  -2 & 1 & 0\\  -1 & 1 & 1 \end{bmatrix}$

 

세번째 행에서 두번째 행을 1배한 것을 더해줬다(-1배한 것을 빼줬다). A가 상삼각행렬로 변형되었다. pivot은 2, -8, 1인 것을 알 수 있다. 이제 상삼각행렬이 대각행렬(diagonal matrix)이 되도록 기본행연산을 해줄 것이다. 대각행렬이란 대각성분을 제외하고는 모든 성분이 0인 행렬을 의미한다. 첫번째 행과 두번째 행에서 세번째 행의 상수배를 빼서 각 행의 세번째 성분이 0이 되게 하자.  

 

$\begin{bmatrix} 2 & 1 & 0\\  0 & -8 & 0\\  0 & 0 & 1 \end{bmatrix}X = \begin{bmatrix} 2 & -1 & -1\\  -4 & 3 & 2\\  -1 & 1 & 1 \end{bmatrix}$

 

첫번째 행에서는 세번째 행을 1배한 것을 빼줬고, 두번째 행에서는 세번째 행을 2배한 것을 더해줬다(-2배한 것을 빼줬다). 이번에는 첫번째 행의 두번째 성분이 0이 되게 하기 위해서 첫번째 행에서 두번째 행의 상수배를 빼주자.

 

$\begin{bmatrix} 2 & 0 & 0\\  0 & -8 & 0\\  0 & 0 & 1 \end{bmatrix}X = \begin{bmatrix} \frac{3}{2} & -\frac{5}{8} & -\frac{3}{4}\\  -4 & 3 & 2\\  -1 & 1 & 1 \end{bmatrix}$

 

첫번째 행에서 두번째 행을 1/8배 해준 것을 더해줬다(-1/8배 해준 것을 빼줬다). 그 결과 A가 대각행렬이 되었다. 이제 각 대각요소를 1로 만들어주자. 각 행을 적당한 상수를 곱해주면 된다. 첫번째 행은 1/2을 곱해주고, 두번째 행은 -1/8을 곱해주고, 세번째 행은 그대로 둔다(1로 곱해준다).

 

$\begin{bmatrix} 1 & 0 & 0\\  0 & 1 & 0\\  0 & 0 & 1 \end{bmatrix}X = \begin{bmatrix} \frac{3}{4} & -\frac{5}{16} & -\frac{3}{8}\\  \frac{1}{2} & -\frac{3}{8} & -\frac{1}{4}\\  -1 & 1 & 1 \end{bmatrix}$  

 

여기서 X의 왼쪽이 항등행렬 $I$이므로, 

 

$X = \begin{bmatrix} \frac{3}{4} & -\frac{5}{16} & -\frac{3}{8}\\  \frac{1}{2} & -\frac{3}{8} & -\frac{1}{4}\\  -1 & 1 & 1 \end{bmatrix}$

 

이다. 이 X가 바로 A의 역행렬이다. 

 

이 예제에서 우리는 3차 정방행렬의 역행렬을 구해봤는데, 4차, 5차,..., 100차 정방행렬의 역행렬도 동일한 방식으로 구할 수 있다. 이런 알고리즘을 개발해냈다는 것이 참 놀랍다.

 

 

<참고자료>

[1] 박부성 지음, "8일간의 선형대수학", 경문사

[2] Gilbert Strang 지음, "Linear algebra and its applications (제4판)", BROOKS/COLE CENGAGE Learning