선형대수학 — 첨가행렬과 가우스 소거법으로 연립방정식 풀기

 

첨가행렬과 가우스 소거법 대표 이미지

연립방정식을 풀 때마다 변수 x₁, x₂, x₃를 매번 다시 쓰고 +랑 =을 다 그리는 게 시간 낭비라는 생각이 들었다. 행렬로 옮기면 숫자만 다루면 되고, 행 연산 몇 번이면 답이 나온다. 가우스 소거법이 이 작업의 표준 절차이고, 선형대수 1단원 전체가 결국 이걸 변주한 거라는 걸 이번 학기에 정리하면서 알게 됐다.

같은 학기에 시스템 프로그래밍도 같이 듣고 있는데, 컴파일러가 코드를 토큰화하는 거랑 연립방정식을 행렬로 옮기는 게 사실 같은 발상이라는 게 재밌었다. 둘 다 "기호를 잘 정리하면 계산이 쉬워진다"는 얘기를 하고 있었다.

첨가행렬이 뭔가

연립방정식에서 변수랑 등호를 다 떼고 숫자만 표로 정리한 게 첨가행렬이다. 왼쪽은 계수, 오른쪽은 우변 상수, 그 사이를 세로선으로 구분한다.

 x₁ +  x₂ + 5x₃ =  0
       x₂ + 9x₃ =  0
            7x₃ = -7

이 시스템을 첨가행렬로 옮기면 이렇게 된다.

[ 1  1  5 |  0 ]
[ 0  1  9 |  0 ]
[ 0  0  7 | -7 ]

왼쪽 부분만 떼면 계수 행렬이고, 우변 상수까지 붙은 전체가 첨가행렬이다. 세로선은 사실 안 그어도 행렬이 성립하는데, "여기부터 오른쪽이 우변이다"라고 시각적으로 표시해두는 용도다.

기본 행 연산

첨가행렬을 풀기 좋은 모양으로 바꿀 때 쓰는 작업이 세 가지 있고, 이 셋은 해를 바꾸지 않는다는 게 보장된다. 두 행을 교환하는 것, 한 행에 0이 아닌 상수를 곱하는 것, 한 행에 다른 행의 배수를 더하는 것. 연립방정식에서 "두 식을 빼서 변수 하나를 소거"하던 걸 그대로 행렬 위에서 하는 셈이다.

사다리꼴과 피벗

행 연산으로 도달하려는 목표는 행 사다리꼴(row echelon form)이다. 정의는 두 가지다. 모든 0행은 맨 아래에 있어야 하고, 각 0이 아닌 행의 leading entry(왼쪽에서 첫 번째로 0이 아닌 수)가 위 행의 leading entry보다 오른쪽에 있어야 한다. 이 leading entry가 피벗이다. 사다리꼴은 대략 이런 모양이다(■가 피벗, *는 아무 값).

[ ■ * * * | * ]
[ 0 ■ * * | * ]
[ 0 0 ■ * | * ]
[ 0 0 0 0 | 0 ]

여기서 한 단계 더 나아간 게 기약 행 사다리꼴(RREF)인데, 조건이 두 개 더 붙는다. 각 피벗 위치의 값이 정확히 1이어야 하고, 피벗이 있는 열에서 피벗 외 다른 값은 전부 0이어야 한다. RREF까지 만들면 답이 사실상 그냥 보인다.

절차를 정리하면, 가장 왼쪽의 0이 아닌 열(피벗 열)을 찾고, 필요하면 행 교환으로 그 열의 피벗을 위로 끌어올리고, 그 아래 행들을 전부 0으로 만든 다음 다음 행·다음 열로 내려가며 반복한다. 사다리꼴이 되면 RREF로 가기 위해 위쪽도 0으로 만들고 피벗을 1로 정규화한다. 가우스 소거법은 사다리꼴까지, 가우스-조던 소거법은 RREF까지다.

실제로 풀어보면

학교 과제에 있던 문제를 하나 가져왔다. 다음 연립방정식은 우변이 전부 0이라 동차(homogeneous) 시스템이다.

 x +  y + 3z =  0
 x + 4y - 8z =  0
-3x - 7y + 9z =  0

첨가행렬로 옮기면:

[  1   3  -5 | 0 ]
[  1   4  -8 | 0 ]
[ -3  -7   9 | 0 ]

R₂ → R₂ - R₁, R₃ → R₃ + 3R₁을 적용하면 1열이 정리된다.

[  1   3  -5 | 0 ]
[  0   1  -3 | 0 ]
[  0   2  -6 | 0 ]

R₃ → R₃ - 2R₂로 2열까지 정리하면:

[  1   3  -5 | 0 ]
[  0   1  -3 | 0 ]
[  0   0   0 | 0 ]

여기까지가 사다리꼴이다. 마지막 줄이 0 = 0으로 의미 없는 식이 됐는데, 이건 자유 변수가 있다는 뜻이다. R₁ → R₁ - 3R₂로 한 단계 더 가면 RREF가 된다.

[  1   0   4 | 0 ]
[  0   1  -3 | 0 ]
[  0   0   0 | 0 ]

피벗이 있는 1열(x)과 2열(y)이 기본 변수, 피벗이 없는 3열(z)이 자유 변수다. 여기서 x + 4z = 0이니 x = -4z, y - 3z = 0이니 y = 3z, z는 자유롭게 움직인다. 매개변수 벡터로 정리하면:

[x]       [-4]
[y] = z · [ 3]
[z]       [ 1]

해 집합은 (-4, 3, 1) 방향으로 뻗어나가는, 원점을 지나는 직선이다.

헷갈렸던 부분들

첨가행렬 [A | b]의 가장 오른쪽 열, 즉 b 자리에 피벗이 생긴다는 게 무슨 뜻인지 처음엔 감이 안 왔다. [0 0 ... 0 | nonzero] 같은 행이 만들어졌다는 의미인데, 식으로 풀면 0 = 5 같은 모순이 된다. 이건 시스템이 불능(inconsistent)이라 해가 존재하지 않는다는 뜻이다. 반대로 계수 행렬 A의 모든 행에 피벗이 박혀 있으면 우변 b가 어떤 값이든 마지막 열까지 피벗이 밀려날 일이 없어서 항상 해가 존재한다.

사다리꼴까지만 만들고 back-substitution으로 푸는 게 가우스 소거법, RREF까지 끝까지 정리해서 답을 바로 보이게 하는 게 가우스-조던 소거법이다. 시험에서는 보통 RREF까지 요구하는 편인데 풀이 과정이 깔끔하게 남기 때문인 것 같다.

피벗이 있는 열의 변수가 기본 변수, 없는 열의 변수가 자유 변수다. 자유 변수는 아무 값이나 넣어도 되고 기본 변수는 자유 변수에 대한 식으로 표현되는데, 자유 변수가 하나라도 있으면 해가 무수히 많아진다.

우변이 전부 0이면 동차, 아니면 비동차인데 동차 시스템은 항상 자명해(x=0)를 가져서 절대 불능이 될 수 없다. 자유 변수가 있느냐 없느냐로 "자명해만 있느냐, 무수히 많느냐"가 갈린다.

참고한 자료는 David C. Lay의 Linear Algebra and Its Applications(학교 교재 1.1~1.3절), 위키피디아의 Gaussian elimination 항목(역사와 알고리즘 의사코드), Mathematics LibreTexts의 Gaussian Elimination 챕터다.

행 연산에서 끝내지 않고 해의 상태까지 보기

첨가행렬을 기약 행 사다리꼴로 만드는 건 목적이 아니라 해의 구조를 읽기 위한 과정이다. 피벗 열과 자유변수를 표시하고, [0 0 ... 0 | c]에서 c≠0인 행이 생기는지 확인하면 유일해·무수히 많은 해·해 없음이 구분된다.

MIT OpenCourseWare 18.06 Linear Algebra

LibreTexts Row Reduction 학습 문서

NumPy linalg.solve 공식 문서

Wolfram MathWorld Gaussian Elimination

계산 검산에 NumPy를 쓸 수는 있지만 linalg.solve는 정사각·full-rank 계수를 전제로 한다. 수업 문제에서는 먼저 손으로 피벗과 모순 행을 판정하고, 수치 계산은 그 뒤 검산용으로 두는 게 좋았다.

참고 자료

• MIT OCW 18.06
• numpy.linalg.solve
• Gaussian Elimination