[bskyvision의 선형대수학, 제6강] 행렬을 이용한 소거법

지난 강의

[bskyvision의 선형대수학, 제0강] 동기부여: 선형대수학 F 받았던 학생이 선형대수학을 이용해서 SCI 논문을 쓰다

[bskyvision의 선형대수학, 제1강] 벡터와 선형결합  

[bskyvision의 선형대수학, 제2강] 점곱과 길이  

[bskyvision의 선형대수학, 제3강] 행렬    

[bskyvision의 선형대수학, 제4강] row picture와 column picture  

[bskyvision의 선형대수학, 제5강] 소거법 (elimination)  

 

 

오늘은 지난 시간에 배운 소거법을 행렬(matrix)을 이용해서 구현해보도록 하겠습니다. 행렬을 이용해서 소거해야 할 대상들을 하나씩 소거할 것이고, 또한 행렬을 이용해서 row exchange도 진행할 것입니다. 소거법에 행렬을 이용할 수 있게 되면, 컴퓨터에게 이 과정을 대신해달라고 부탁하기가 한결 쉬워집니다. 제6강 이제 시작하겠습니다.

 

 

소거행렬 (elimination matrix)

다음과 같이 3개의 미지수를 가진 3개의 방정식이 있다고 가정하겠습니다. 

 

 

이것을 우리는 행렬과 벡터를 이용해서 표현할 수 있습니다. 

 

 

지난 시간에 배운 소거법을 기억한다면, 먼저 해야 할 것은 두번째 방정식의 x1을 없애는 것입니다. 그렇게 하려면, 두번째 방정식에서 첫번째 방정식에 2를 곱한 것을 빼줘야 합니다. 그런데 이것을 행렬로 해주려면 어떻게 해야할까요?

 

Ax와 b의 왼쪽에 각각 소거 행렬(elimination matrix)을 곱해줘야 합니다. 이 소거 행렬의 목적은 행렬 A의 두번째 행에서 첫번째 행에 2를 곱한 것을 빼주는 것입니다. 또한 벡터 b의 두번째 성분에서 첫번째 성분에 2를 곱한 것을 빼주는 것입니다. 

 

어떤 행렬을 곱해줘야 그것이 가능할까요? 우선 행렬 A의 첫번째 행과 세번째 행에는 변동이 있어서는 안 됩니다. 또한 벡터 b의 첫번째 성분과 세번째 성분도 바뀌어선 안 됩니다. 행렬 A의 두번째 행과 벡터 b의 두번째 성분만 변화가 생겨야 합니다. 

 

그 전에 항등 행렬(identity matrix)이라는 것을 잠시 다루고 가겠습니다.

 

 

항등 행렬은 n x n 정방 행렬이고, 대각 요소는 모두 1이고 나머지 요소는 모두 0인 행렬입니다. 이 행렬을 어떤 행렬이나 벡터에 곱했을 때는 그들 자신이 나옵니다. 곱하기에서 1과 같은 역할을 하는 친구입니다.

 

 

이러한 항등 행렬에서 딱 하나의 0만 바꿔주면 두번째 행에서 첫번째 행에 어떤 수를 곱해준 것을 뺄 수 있는 능력을 가진 소거 행렬이 됩니다. 바로 항등 행렬에서 두번째 행, 첫번째 열 요소를 -2로 바꿔줘야 합니다. 그것을 행렬 A의 왼쪽에 곱하면 다음과 같이 계산됩니다. 

 

참고로 행렬과 행렬을 곱할 때는 앞 행렬에 뒤 행렬의 각 열(column)을 곱한 것이 결과 행렬의 각 열이 됩니다. 

 

 

또한 위 소거행렬 E_21을 벡터 b의 왼쪽에 곱해주면 다음과 같은 결과가 나옵니다. 

 

 

이 소거행렬 덕분에 우리는 두번째 방정식에서 x1을 소거할 수 있었던 것입니다. 

 

 

세번째 방정식의 x1도 소거해줘야겠죠? 이번에도 소거 행렬을 통해서 제거해보겠습니다. 이번에는 세번째 행에서 첫번째 행을 더해줘야 함으로, 다음과 같은 소거 행렬이 필요합니다. 

 

 

이 소거행렬 E_31 덕분에 우리는 세번째 방정식에서도 x1을 소거할 수 있었습니다.  

 

 

이제 마지막으로 세번째 방정식에서 두번째 방정식을 빼줌으로 세번째 행에 있는 x2를 소거해야 합니다. 이때 필요한 소거 행렬은 다음과 같습니다. 

 

 

드디어 상삼각행렬 U가 되었습니다. 전진 소거(forward elimination)가 아무 탈 없이 완료되었습니다. 소거행렬 E_32 덕분에 삼각시스템으로 변환되었습니다. 

 

 

지금까지 여러 소거행렬들을 통해서 소거법을 구현한 과정을 정리하자면 다음과 같습니다.

 

 

보기에는 복잡해보이지만, 실제로 그다지 어려울 것은 없으니 겁 먹지 마세요.^^;  중요한 것은 행렬과 벡터를 이용해서 소거 과정을 구현해냈다는 것에 있습니다. 이 핵심을 놓치시면 안 됩니다. 

 

치환행렬 (permutation matrix)

위의 예제는 row exchange의 필요없이 소거가 잘 진행되었지만, 만약 막힌다면 row exchange가 필요합니다. 곱했을 때 row exchange를 해주는 행렬을 치환행렬(permutation matrix)이라고 부릅니다. 

 

첫번째 행과 두번째 행의 위치를 서로 바꿔주려면 어떤 행렬을 곱해줘야 할까요? 이번에도 역시 항등행렬에서 시작해야 합니다. 항등행렬의 첫번째, 두번째 행의 위치를 교환해준 것을 어떤 행렬의 왼쪽에 곱하면, 그 행렬의 첫번째 두번째 행이 서로 바뀝니다. 

 

 

 

두번째, 세번째 행의 위치를 서로 바꿔주는 치환행렬 P_23을 곱해주면 다음과 같이 두번째, 세번째 행이 서로 치환됩니다. 

 

 

 

소거행렬을 곱해가면서 소거법을 진행해가다가, row exchange가 필요해진 경우에는 이와 같은 치환행렬들을 곱해가며 계속 진행하면 되는 것입니다. 

 

첨가행렬 (augmented matrix)

Ax = b에 소거법을 진행할 때 실제적으로 영향을 받는 것들은 행렬 A와 벡터 b 안의 값들입니다. 따라서, 이것들만 하나로 모아서 행렬을 만들어 주면 훨씬 편리하게 소거 과정을 추적할 수 있습니다. 

 

 

이러한 행렬을 첨가행렬(augmented matrix)이라고 부릅니다. 첨가행렬을 이용해서 소거법을 진행하면, 원래는 Ax=b 양변에 소거행렬과 치환행렬을 곱해가며 진행해야했던 것을 첨가행렬의 왼쪽에 한번만 곱하면 되기 때문에 훨씬 간결해집니다. 

 

 

제6강 끝

오늘은 소거법을 행렬을 이용해서 진행하는 법에 대해서 살펴봤습니다. 그 과정에서 항등행렬, 소거행렬, 치환행렬이라는 것도 배웠고, 행렬과 행렬을 곱하는 방법에 대해서도 다뤘습니다. 또 행렬 A와 벡터 b를 붙여서 만든 첨가행렬이라는 것도 알게 되었습니다. 소거법의 목적은 결국 상삼각행렬을 도출해내는 것입니다. 가능하다면 말이죠. 상삼각행렬이 도출된다면, 유일한 해를 가지는 것이고, row exchange를 해줬는데도 영구적으로 막히게 되면 해가 없거나 무수히 많은 해를 갖는 것입니다. 다음 시간에 또 찾아뵙겠습니다! 부족한 글 끝까지 읽어주셔서 감사합니다.