Gauss-Jordan Elimination(가우스-조던 소거법) & RREF

 

오늘은 이전 게시물에서 다루었던 부분공간들을 발견할 수 있는, 그리고 이후 문제 해결에서 도움이 되는 가우스-조던 소거법과, rref(기약 행사다리꼴)에 대해서 알아보도록 하겠습니다.

 

---

 

Gauss-Jordan Elimination(가우스-조던 소거법)

 

이전 게시물에서 가우스 소거법(Gaussian Elimination)을 다룬 적이 있습니다. 이번에는 가우스 소거법이 아니라 한층 더 나아간, 가우스-조던 소거법에 대해서 다뤄볼 것입니다. 

 

우리는 이전에 가우스 소거법을 이용하여 주어진 행렬 ((A))를 ref, row echelon form의 형태로 만들어주었습니다.

https://jaehoonstudy.tistory.com/12

Solving ((A))((x)) ((=)) ((b)) (When ((n)) x ((n))) - part 2

 

RREF(Reduced Row echelon form)을 만들어주기 위해서는 ref의 pivot들을 1로 만들어주고, 그 1들 위나 아래를 모두 0으로 만들어주면 됩니다. pivot은 행의 first non-zero, 그러니까 왼쪽에서부터 숫자를 읽었을 때 가장 먼저 나오는 0이 아닌 숫자들 pivot이라고 합니다.

 

항상 그렇듯이 예시를 같이 보면서 직접 가우스-조던 소거법을 이용해 rref를 만들어보겠습니다.

 

 

<현재 pivot = 1행의 1>

 

우선 2행의 3을 없애고 싶으니 1행 x 3 을 해서 2행에서 빼줍니다.

현재 pivot이 1이고 밑이 전부 0이니 pivot을 2행으로 넘겨줍니다.

그러면 아래와 같이 나옵니다.

 

((\begin{bmatrix}
1 & 2 & 4\\ 
0 & 2 & 2\\ 
0 & 4 & 4
\end{bmatrix}))

 

<현재 pivot = 2행의 2>

 

그다음 현재 pivot 밑에 있는 4를 없애주고 싶으니 2행 x 2 를 해서 3행에서 빼줍니다.

그러면 위와 같이 3행이 0이 되고, 우리가 아는 row echelon form(ref)가 나옵니다.

 

여기서 rref의 조건이 들어갑니다. pivot 위의 숫자가 0이어야 하고, pivot 값이 1이어야 합니다. 2행의 2 위에 1행의 2가 있습니다. 그대로 빼주면 0이 될 것이므로 2행 x 1을 해서 1행에서 빼줍니다. 그렇게하면 아래와 같이 나옵니다.

 

((\begin{bmatrix}
1 & 0 & 2\\ 
0 & 2 & 2\\ 
0 & 0 & 0
\end{bmatrix}))

 

그리고 마지막으로 2행 자체를 2로 나눠줌으로써 pivot 값을 1로 만들어주겠습니다. 그렇게 한다면 위의 결과물인 rref가 나오는 것입니다.

 

가우스-조던 소거법의 3가지 연산

1. 어떤 행에 숫자를 곱하여 다른 행에서 빼준다.
2. 어떤 행에 0이 아닌 숫자를 곱한다(pivot을 1로 만들기 위해).
3. 행들의 위치를 바꾼다(행의 숫자가 모두 0인 애들을 맨 밑으로 몰아넣기 위해)

여기서 중요한 것은, 이 3가지 연산 모두 Linear combination에 해당한다는 것입니다. 그냥 벡터들을 조합한 것일 뿐이므로, 이러한 연산들을 해도 행렬의 Row space는 달라지지 않는 것이 핵심 포인트입니다. 새로운 기저벡터가 생기거나 이런 것이 아니라, 기존 것들만을 활용하는 것이기 때문에 공간이 달라질 일이 없다는 것이죠.

 

---

 

Reduced Row echelon form(rref)

 

 

 

이 rref에 대해서 조금 더 알아보도록 하겠습니다. 먼저 rref는 이런 모양으로 생겼습니다. 

 

여기서 ((R))은 Row echelon form입니다. R 밑에 0이 있는 형태이죠. 아까도 언급했듯이 이렇게 행렬에 변화를 가한다고 해서 기존 행렬인 ((A))와 row space가 달라지지 않습니다. 그래서 훨씬 더 간단한 형태를 하고 있으면서도 ((m)) - ((r)) 개의 성분이 모두 0인 행을 밑에 가지고 있습니다.

 

우리는 CR factorization을 통해서 ((r))개의 independent column들을 찾아낸 바가 있습니다. 그리고 4개의 부분공간들을 살펴보면서 left nullspace, 그러니까 nullspace의 row 버전 공간의 차원이 ((m)) - ((r))이라는 것을 본 적이 있습니다.

https://jaehoonstudy.tistory.com/8

CR Factorization

https://jaehoonstudy.tistory.com/16

Four Fundamental Subspaces(4개의 주요 부분공간)

 

 

이것도 마찬가지로 행렬에 ((m)) - ((r))개의 dependent한 row가 있다는 것을 알려주는 셈입니다. 마지막 행이 싹 다 0이므로 마지막 행이 dependent한 행일 것입니다. 진짜 그런지 한 번 볼까요?

 

원래 우리 A는 이거였습니다.

 

1행 x 6을 하면, 6 12 24 가 나옵니다.

2행 x 2를 하면, 6 16 28 이 나옵니다.

이거 두 개 빼면, 0 4 4 가 나옵니다.

 

정확히 위의 2개 행들로 3행을 만들 수 있으므로, 3행은 이들 두 행에 dependent한 것입니다.

 

 

RREF와 4개의 부분공간과의 연관

 

우리가 마지막으로 만든 rref는 기존 행렬인 ((A))의 row space와 column space, 그리고 null space를 알려줍니다. 

 

여기서 다루려고 부분공간 게시물에서는 다루지 않았는데, 어떤 부분공간을 표현할 때에는 그 공간의 basis를 이용해서 표현합니다. 공간에 벡터는 무한히 많아 어떤 벡터를 특정하며 공간을 표현해야하는데, 그 적임자가 바로 얘네들의 linear combination으로 공간의 모든 벡터들을 만들어낼 수 있는 basis들 인 것이죠. 그래서 basis들 간의 linear combination 형태로 어떤 벡터공간을 표현합니다. 

 

그러면, row space와 column space, null space를 표현하려면 이들의 basis를 알면 될 것입니다.

 

우리의 rref는 바로 이 basis들을 주는 것입니다. 

 

이렇게 말이죠.

 

 

우리의 rref가 이렇게 생겼을 때, ((R))의 행들은 모두 독립적인 행들이고, 이들이 바로 Row space의 basis가 되는 것입니다.

 

또한, 

 

앞의 2개의 column이 소거법 결과 identity matrix의 형태로 나왔습니다. CR factorization에서처럼 이들은 independent한 column들의 위치를 알려주는 것이므로, 원래 행렬인 ((A))의 column 1과 column 2가 Column space의 basis가 되는 것입니다.

 

Nullspace의 정의에 따르면, ((A))((x)) ((=)) ((0))을 만족하는 모든 ((x))들 입니다. 이 ((x))를 구하려면 ((R₀))((x)) ((=)) ((0))을 풀면 됩니다. 그러면 우리의 ((x))를 위의 그림처럼 ((\begin{bmatrix}
-2\\ 
-1\\ 
1
\end{bmatrix})) 로 구할 수 있습니다.

 

---

 

RREF를 구할 때 일어날 수 있는 경우들

 

선형대수학에서는 여러가지 경우들이 있는데, 이를 머리속에 잘 담아두면 전체적인 그림을 그릴 때 좋은 것 같습니다. 특히 지금 막 rref고 가우스-조던 소거법이고 여러가지가 나와서 정신이 없는데, 이들이 언제 어디서 쓰이는지를 중점으로 정리해두면 좋을 것 같습니다. 제가 이전에 ((A))((x)) = ((b)) 문제를 풀어야하는데 ((A))가 ((n)) x ((n)) 상황일 때 가우스 소거법을 이용해 LU 분해를 하여 문제를 쉽게 푼다 라고 정리한 것처럼 말이죠. 다음 게시물에서도 가우스-조던 소거법이 쓰이는 문제 상황을 다룰 것입니다.

 

어쨌든, 우리가 rref를 구할 때 일어날 수 있는 경우들이 무엇이 있는지 살펴보도록 하겠습니다. 

 

결론부터 말하면,

 

((A))가 invertible한 경우,

((A))가 dependent row를 가질 경우,

((A))의 independent column이 뒤에 있을 때,

 

이렇게 3가지 입니다. 

 

 

 

((A))가 invertible한 경우

 

선형대수에서는 동일한 개념인데 이를 지칭하는 말이 여러 개 있는 경우가 많습니다.

 

((A))가 invertible 하다는 것은 ((A))가 역행렬이 있다는 뜻이고,

 

선형변환을 해도 다시 역으로 돌려놓을 수 있는 선형변환이기에 변환 시 차원이 무너지지 않는(찌그러지지 않는) 변환이라는 것입니다.

즉, 3차원에서 2차원으로 가는 변환이라던지 말이죠.

 

이를 위해서는 일단 당연히 ((n)) x ((n)) 형태의 행렬이어야 합니다(차원이 보존되어야하니까). 그리고 ((n)) x ((n)) 행렬 안에서도 dependent한 column이 없이 모두 독립적으로 basis가 되어야하는 것입니다(dependent column이 있으면 차원이 무너지기 때문입니다).

 

'차원이 찌그러진다' 라는 뜻은 제 이전 게시물 중 행렬식에 대한 게시물을 보면 좋습니다. ((A))가 invertible 하다는 것은 determinant가 0이 아니라는 뜻도 되겠네요. https://jaehoonstudy.tistory.com/9

행렬식(Determinant)

 

어쨋든, 가장 간단한 경우인 ((A))가 invertible할 경우를 보겠습니다.

 

((A))가 invertible한 경우에는 dependent한 게 없기 때문에 맨 처음 예시와 같이 행렬 맨 밑에 모두 0인 행이 없습니다. 이렇게 identity matrix가 나와버리죠. rref는 많은 것을 알려주는데, 벌써 우리는 행렬을 rref로 만들어주기만 해도 이 행렬이 역행렬이 있는지 없는지를 알아낼 수 있는 것입니다.  

 

 

((A))가 dependent row들이 있는 경우

 

맨 위의 예시와 같은 경우입니다.

 

밑에 성분이 모두 0인 행이 나옵니다. 그리고 맨 오른쪽에 있는 표기는, 우리의 rref 속 형태가 ((I)), ((F)), 그리고 밑에 0인 행으로 생겼다는 뜻입니다.

 

((I))는 identity matrix이고, ((F))는 아마 free variable이라서 알파벳 ((F))를 사용하였을 겁니다. 얘는 independent column을 어떻게 조합해야 그 자리의 column이 나오는지를 알려주는 애 입니다. 실제로 col 1에 col 2 x 2를 해서 더하면 col 3이 나옴을 볼 수 있습니다.

((I))는 ((A))의 ((r))개의 independent column들을 찾아주고, 하단에 ((m)) - ((r)) 개의 0인 행들을 만듭니다. 여기서 ((m))은 행렬 ((A))가 ((m)) x ((n)) 모양(행 개수 x 열 개수)으로 생겼다는 데에서 가져온 ((m))입니다.

 

 

Independent column이 뒤에 있을 때

 

우리는 rref 속 내용물이 ((\begin{bmatrix}
I & F\\ 
0 & 0
\end{bmatrix})) 처럼 모양을 가지게 정리하고 싶습니다. 그래야 보기가 편하기 때문이죠. 이를 위해서는 Permutation matrix를 사용하는데, 이는 LU 분해를 할 때와 같습니다. 이전 게시물에서의 "가우스 소거법이 통하지 않을 때" 의 경우입니다.

https://jaehoonstudy.tistory.com/12

Solving ((A))((x)) ((=)) ((b)) (When ((n)) x ((n))) - part 2

 

바로 Permutation matrix ((P))를 곱해주는 건데요, ((P))가 곱해지는 원리와 계산은 위의 링크를 타고 이전 게시물에서 아주 자세하게 확인하실 수 있습니다. 그럼 Permutation matrix를 확인하셨다고 가정하고, 우리가 원하는 rref 모양을 permutation matrix를 이용해서 나타내면 다음과 같이 됩니다.

 

일단 앞에 거를 ((\begin{bmatrix}
I & F\\ 
0 & 0
\end{bmatrix})) 이렇게 만들어놓고, 뒤의 Permutation matrix를 이용해서 column들을 원래 행렬 ((A))와 같은 자리로 만들어주는 것입니다. 

 

이렇게 되겠네요.

 

아직 잘 머리로 안 와닿을 수 있으니, 예시로 또 보겠습니다.

 

((A))가 이렇게 있으면, 일단 아무것도 할 수가 없으니 3행과 1행의 자리를 바꿔줍니다.

 

그다음에 첫 번째 pivot인 1행의 1은 밑에도 0이고, pivot 값도 1이니 됐고, 두 번째 pivot을 건드려야합니다.

 

두 번째 pivot은 그 다음 행의 가장 먼저 나오는 non-zero 성분입니다. 2행 맨 끝에 1이 있으니 그게 pivot이 되고, pivot 위를 0으로 만들어주기 위해 2행에 x 2를 해서 1행에서 빼줍니다.

 

그러면 rref 꼴이 되는데, 우리가 원하는 ((\begin{bmatrix}
I & F\\ 
0 & 0
\end{bmatrix})) 로 만들기 위해 뒤에 Permutation matrix를 곱해주어 3번째 column이 두 번째로 가게 만든 것입니다. 왜 위에 LU분해에서는 ((P))가 왼쪽에 곱해졌었는데 지금은 오른쪽에 곱해져있냐면, LU분해에서는 행들의 위치를 옮겨주는 것이고, 얘는 반대로 열의 위치를 옮겨준 것이기 때문입니다.