27. 크래머(Cramer) 공식, 가우스-조던 소거법 (Gauss-Jordan Elimination)

27.1. Cramer's Rule.

 변수와 방정식의 개수가 같은 다음과 같은 연립방정식이 있다고 합시다.

$\begin {cases} a_{11} x_1+a_{12} x_2+\cdots+a_{1n} x_n = b_1\\a_{21} x_1 + a_{22} x_2 +\cdots+a_{2n} x_n = b_2\\\qquad\qquad\qquad\quad\vdots\\a_{n1} x_1 + a_{n2} x_2 + \cdots + a_{nn} x_n = b_n\end {cases}\cdots(1)$

 (1)을 Matrix 형태로 바꾸면 다음과 같아집니다.

$\begin {bmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&\ddots&\vdots\\a_{n1}&a_{n2}&\cdots&a_{nn}\end {bmatrix}\begin {bmatrix} x_1\\x_2\\\vdots\\x_n\end {bmatrix}=\begin {bmatrix} b_1\\b_2\\\vdots\\b_n\end {bmatrix}\cdots(2)$

 (2)를 $\mathbf {Ax}=\mathbf {b}$의 형태가 되었습니다. 이때 $\mathbf {A}$의 크기는 $n \times n$인 Matrix이고, $\det{\mathbf{A}}\neq0$이라고 합시다. 그렇다면 $\mathbf{A}$의 Rank $r$은 $r=n$이므로 $\mathbf {x}$는 유일한 해를 가집니다. Cramer' rule은 이 유일한 해를 다음과 같다고 제시합니다.

 $x_1 = \frac {D_1}{D},\ x_2=\frac {D_2}{D},\ \cdots,\ x_n=\frac {D_n}{D}\ \cdots\ (3)$

 이때 $D_k$는 $D$의 $k$ 번째 column을 $\mathbf {b}$의 원소로 치환한 Determinant 값입니다. 예제를 풀어보면서 공식을 적용해 봅시다.

 

 Ex) 1. $\begin {cases} 3x-2y+z=13\\-2x+y+4z=11\\x+4y-5z=-31\end {cases}$

 주어진 예제를 Matrix 형태로 바꾸면 다음과 같습니다.

$\begin {bmatrix} 3&-5&1\\-2&1&4\\1&4&-5\end {bmatrix}\begin {bmatrix} x\\y\\z\end {bmatrix}=\begin {bmatrix}13\\11\\-31\end {bmatrix}$

 $D = \det {\mathbf {A}}$를 구해봅시다.

$D = \det{\mathbf{A}} = \begin {vmatrix} 3&-5&1\\-2&1&4\\1&4&-5\end {vmatrix}= 3\begin {vmatrix}1&4\\4&-5\end {vmatrix} -(-5)\begin {vmatrix}-2&4\\1&-5\end {vmatrix} + 1\begin {vmatrix} -2&1\\1&4\end {vmatrix} = -60\cdots(4)$

 $D_x$, $D_y$, $D_z$를 구해봅시다. 각 변수의 column을 $\mathbf {b}$의 원소로 치환하고, Determinant를 계산해 봅시다.

$\det {D_x} = \begin {vmatrix} 13&-2&1\\11&1&4\\-31&4&-5\end {vmatrix} = -60\cdots(5)$

$\det {D_y} = \begin {vmatrix} 3&13&1\\-2&11&4\\1&-31&-5\end {vmatrix} = 180\cdots(6)$

$\det {D_z} = \begin {vmatrix} 3&-2&13\\-2&1&11\\1&4&-31\end {vmatrix} = -240\cdots(7)$

 (4)~(7)의 결과를 이용하여 Camer's rule을 적용합니다.

$x = \frac {D_x}{D} = \frac {-60}{60} = -1$

$y = \frac {D_y}{D} = \frac {180}{60} = 3$

$z = \frac {D_z}{D} = \frac {-240}{60} = -4$

 

 sol) $x = -1$, $y = 3$, $z = -4$

 

 만일 $\mathbf {b}$가 zero vector이고, $D \neq 0$이면, 주어진 연립방정식을 만족시키는 Matrix $\mathbf {x}$는 오로지 자명한 해인 $\mathbf{x} = \begin {bmatrix}0\\0\\\vdots\\0\end {bmatrix}$만을 가집니다. 하지만 $D = 0$이라면 비자 명해를 가집니다.

 

 27.2. Inverse Matrix, Gauss-Jordan Elimination.

 크기가 $n \times n$인 matrix $\mathbf {A} = [a_jk]$의 Inverse matrix를 $\mathbf {A^{-1}}$라고 씁니다. Inverse matrix는 다음을 만족합니다.

 $\mathbf {AA^{-1}} = \mathbf {A^{-1} A} = \mathbf {I}\cdots(8)$

 (8)의 $\mathbf {I}$는 크기가 $n \times n$인 Unit matrix입니다.

 $\mathbf {A}$의 Inverse matrix가 $\mathbf {B}$, $\mathbf{C}$라고 합시다. Matrix 곱의 성질로 다음을 만족함을 보일 수 있습니다.

 $\mathbf{B} = \mathbf {IB} = \mathbf{(CA) B} = \mathbf {C(AB)} = \mathbf {CI} = \mathbf {C}\cdots(9)$

 (9)에서 $\mathbf {B} = \mathbf {C}$임을 알았습니다. 이는 Inverse matrix는 유일하다는 사실을 알 수 있습니다.

 이번에는 어떤 경우에 Inverse matrix가 존재하는지 알아봅시다. $\mathbf {A}$가 크기가 $n\times n$ matrix이고 다음과 같은 linear system이 제시되었다고 합시다.

 $\mathbf {Ax} = \mathbf {b}\cdots(10)$

 만일 $\mathbf {A^{-1}}$이 존재한다고 가정하고, 양변의 왼쪽에 $\mathbf {A^{-1}}$을 곱합니다. 그렇다면 (11)과 같이 쓸 수 있습니다.

 $\mathbf {A^{-1} Ax} = \mathbf {x} = \mathbf {A^{-1} b}\cdots(11)$

 앞선 포스팅에서 $r = n$일 때 유일한 해를 갖고, $r < n$일 때 해를 갖지 않거나 무한한 해를 가짐을 알았습니다. 앞선 단락에서 Inverse matrix는 유일하다는 것을 알았습니다. 즉, 크기가 $n \times n$ matrix $\mathbf {A}$의 Inverse matrix는 $\mathbf{A}$의 rank $r$이 $r = n$을 만족할 때, Inverse matrix가 존재한다는 것을 알 수 있습니다.

 

 이제 이 Inverse matrix가 존재하고, 이를 구하기 위해 어떤 방법을 써야 하는지 알아봅시다. 이 방법을 Gauss-Jordan Elimination이라고 하는데, 아이디어는 Gauss Elimination과 크게 다르지 않습니다. $\mathbf {A}$에 Unit matrix를 추가하여 $n \times 2n$ augmented matrix로 만듭니다.

 $[\mathbf {A}|\mathbf {I}]\cdots(12)$

 (12)의 $\mathbf {A}$부분을 Gauss Eliminantion 하여 Unit matrix로 만들어봅시다. 그렇다면 다음과 같은 형태가 되겠습니다.

 $[\mathbf {I}|\mathbf {B}]\cdots(13)$

 (13)의 $\mathbf {B}$가 $\mathbf {A}$의 Inverse matrix입니다. 예제를 풀어봅시다.

 

 Ex) 2. $\mathbf{A} = \begin {bmatrix} -1&1&2\\3&-1&1\\-1&3&4\end {bmatrix}$

   Unit matrix를 추가하여 $n \times 2n$ augment matrix를 만들어봅시다.

  $\begin {bmatrix} -1&1&2&|&1&0&0\\3&-1&1&|&0&1&0\\-1&3&4&|&0&0&1\end {bmatrix}\cdots(13)$

   (13)을 Gauss Elimination 해봅시다. 먼저 row 1에 3을 곱한 뒤 row 2에 더하고, row 1을 row 3에 더하면 되겠습니다.

  $\begin {bmatrix} -1&1&2&|&1&0&0\\0&2&7&|&3&1&0\\0&2&2&|&-1&0&1\end {bmatrix}\cdots(14)$

  $\begin {bmatrix} -1&1&2&|&1&0&0\\0&2&7&|&3&1&0\\0&0&-5&|&-4&-1&1\end {bmatrix}\cdots(15)$

   (15)의 주대각 원소를 1로 만들어줍시다. row 1에 -1, row 2에 0.5, row 3에 -0.2를 곱합니다.

  $\begin {bmatrix} 1&-1&-2&|&-1&0&0\\0&1&3.5&|&1.5&0.5&0\\0&0&1&|&0.8&0.2&-0.2\end {bmatrix}\cdots(16)$

   이제 반대방향으로 Gauss Elimination을 진행해 봅시다. (16)의 row 3에 -3.5를 곱한 뒤 row 2에 더하고, row 3에 2를 곱하여 row 1에 더합니다.

  $\begin {bmatrix} 1&-1&0&|&0.6&0.4&-0.4\\0&1&0&|&-1.3&-0.2&0.7\\0&0&1&|&0.8&0.2&-0.2\end {bmatrix}\cdots(17)$

   (17)의 row 2를 row 1에 더하면 좌측 matrix가 Unit matrix가 완성됩니다. 이때 우측 Matrix가 Inverse matrix임을 알 수 있습니다.

  $\begin {bmatrix} 1&0&0&|&-0.7&0.2&0.3\\0&1&0&|&-1.3&-0.2&0.7\\0&0&1&|&0.8&0.2&-0.2\end {bmatrix}\cdots(18)$

 

   sol) $\mathbf {A^{-1}} = \begin {bmatrix} -0.7&0.2&0.3\\-1.3&-0.2&0.7\\0.8&0.2&-0.2\end {bmatrix}$

 

 이번 포스팅은 여기서 마치겠습니다. 다음 포스팅에서 Eigenvalue Problem에 대하여 작성할 예정입니다.