Summary

가우스 소거법(Gaussian Elimination)은 연립일차방정식 $A x = b$ 를 푸는 가장 기본적인 방법이다. 변수를 하나씩 차근차근 없애서(소거) 식을 “계단 모양(사다리꼴)“으로 정리한 다음, 아래에서부터 거꾸로 값을 대입해 답을 구한다. 역행렬, 랭크, 부분공간 계산까지 결국 이 한 가지 기계를 돌려서 한다.

용어 설명

system of linear equations (연립일차방정식): 여러 개의 일차방정식을 동시에 만족시키는 해를 찾는 문제. 행렬로는 $A x = b$ .

augmented matrix (첨가행렬): 계수 행렬 $A$ 오른쪽에 $b$ 를 붙인 $[A ∣ b]$ . 계산할 때 식 대신 이걸 가지고 논다.

row operations (행연산): 첨가행렬의 행을 바꾸는 3가지 허용된 조작. 해는 그대로 보존된다.

pivot (피벗): 각 행에서 맨 왼쪽에 처음 나오는 0이 아닌 원소. 소거의 “기준점”.

echelon form (행사다리꼴): 피벗들이 계단처럼 오른쪽 아래로 내려가고, 피벗 아래가 모두 0인 모양.

back-substitution (후진대입): 사다리꼴이 된 뒤 맨 아래 식부터 거꾸로 값을 대입해 풀어 올라가는 단계.

RREF (기약행사다리꼴, Reduced Row Echelon Form): 피벗 위까지 모두 0으로 만들고 피벗을 1로 만든 가장 깔끔한 형태. 여기까지 하면 Gauss-Jordan 소거법.

free variable (자유변수): 피벗이 없는 변수. 아무 값이나 넣어도 되므로 해가 무수히 많아지는 원인.

inconsistent (해 없음): $0 = (0 이 아닌 수)$ 같은 모순 행이 생긴 경우.

Gaussian Elimination

1. 직관 (변수를 하나씩 소거해 위삼각꼴로)

연립방정식을 푼다는 건, 사실 중학교 때부터 하던 “가감법”이다. 한 식에서 $x$ 를 없애려고 다른 식을 적당히 곱해서 빼던 그것.

가우스 소거법은 이걸 위에서 아래로 순서대로, 기계처럼 하는 것이다. 비유하자면:

책상 위에 식 3개가 어지럽게 놓여 있다.
제일 위 식으로 아래 식들의 $x$ 를 싹 지운다. (이제 아래 두 식엔 $x$ 가 없다)
두 번째 식으로 그 아래 식의 $y$ 를 지운다. (맨 아래 식엔 $z$ 만 남는다)
결국 식들이 계단(사다리꼴) 모양이 된다. 맨 아래 식은 변수 하나짜리라 바로 풀린다.

이렇게 변수가 점점 줄어드는 “위삼각형(upper triangular)” 모양을 만드는 게 핵심이다.

2. 절차 (3가지 행연산 → 사다리꼴 → 후진대입)

식을 직접 쓰지 말고 숫자만 모아 첨가행렬 $[A ∣ b]$ 로 다룬다. 허용되는 행연산(row operations) 은 딱 3가지이고, 무엇을 해도 해집합은 변하지 않는다.

두 행을 교환한다. (식 순서 바꾸기)
한 행에 0이 아닌 상수를 곱한다.
한 행에 다른 행의 배수를 더한다. ← 실제 소거가 일어나는 핵심 연산

진행 순서:

전진 소거(forward elimination): 맨 위 왼쪽부터 피벗을 잡고, 그 아래를 모두 0으로 만든다. 다음 행으로 내려가며 반복 → 행사다리꼴(echelon form).
후진대입(back-substitution): 맨 아래 식부터 거꾸로 값을 구해 위로 대입해 올라간다.

Tip

한 단계 더 나아가 피벗 위쪽까지 0으로 만들고 피벗을 1로 맞추면 RREF(기약행사다리꼴) 가 된다. 이것이 Gauss-Jordan 소거법이며, 이때는 후진대입이 거의 필요 없이 답이 바로 읽힌다.

3. 해의 종류 (유일해 / 무수히 많음 / 없음 — 피벗으로 판별)

사다리꼴까지 만들면 피벗 개수만 보고 해의 종류를 알 수 있다.

상황	판별	해
피벗 수 = 변수 수	자유변수 없음	유일해 (unique)
피벗 수 < 변수 수	자유변수 존재	무수히 많음 (infinitely many)
$0 = (0 이 아닌 수)$ 행 발생	모순	해 없음 (inconsistent)

Warning

피벗 자리에 0이 나오면 그 행으로는 아래를 소거할 수 없다. 이때는 아래의 0이 아닌 행과 교환(행연산 1번) 한 뒤 진행해야 한다. 무작정 0으로 나누면 안 된다.

4. 예시 (구체 3변수 풀이)

⎩ ⎨ ⎧ x + y + z = 6 2 x + 3 y + z = 11 x - y + 2 z = 7

첨가행렬:

121 13 - 1 1126117

1행을 피벗으로 아래 소거 ( $R_{2} \to R_{2} - 2 R_{1}$ , $R_{3} \to R_{3} - R_{1}$ ):

100 11 - 2 1 - 1 1 6 - 1 1

2행을 피벗으로 아래 소거 ( $R_{3} \to R_{3} + 2 R_{2}$ ):

100110 1 - 1 - 1 6 - 1 - 1

이제 사다리꼴 완성. 피벗이 3개(변수 3개)이므로 유일해.

후진대입(back-substitution):

맨 아래 행: $- z = - 1 \Rightarrow z = 1$
둘째 행: $y - z = - 1 \Rightarrow y = - 1 + 1 = 0$
첫째 행: $x + y + z = 6 \Rightarrow x = 6 - 0 - 1 = 5$

따라서 $(x, y, z) = (5, 0, 1)$ . (원래 식들에 넣어보면 모두 맞는다.)

5. 어디에 쓰나 / 흔한 함정

쓰임:

연립방정식 풀이는 기본이고, 역행렬(matrix inverse) 계산( $[A ∣ I] \to [I ∣ A^{- 1}]$ ), 랭크(rank) 구하기(= 피벗 개수), 영공간/열공간 등 부분공간 계산까지 전부 이 소거 엔진을 돌려서 한다. 선형대수의 “공용 엔진”.

함정:

0 피벗: 위 [!warning]처럼 행교환 필요.
부동소수점 오차(floating-point error): 컴퓨터로 풀 때 아주 작은 피벗으로 나누면 오차가 커진다. 실무에서는 절댓값이 큰 원소를 피벗으로 고르는 부분 피벗팅(partial pivoting) 을 쓴다.
부호 실수: $R_{i} \to R_{i} - k R_{j}$ 에서 부호를 헷갈리는 게 가장 흔한 손계산 실수.

Tip

교과서 참고: Gilbert Strang, Introduction to Linear Algebra, Ch 1–2.

6. 30초 요약 (bullets)

목적: $A x = b$ 를 첨가행렬 $[A ∣ b]$ 로 만들어 푼다.
행연산 3가지(교환 / 상수배 / 다른 행의 배수 더하기) → 해 불변.
전진 소거로 사다리꼴(echelon form) → 후진대입으로 해 구함.
더 밀어붙이면 RREF(Gauss-Jordan): 피벗=1, 피벗 위아래 모두 0.
해 판별: 피벗 수 = 변수 수 → 유일해 / 자유변수 있으면 → 무수히 많음 / 모순 행 → 해 없음.
0 피벗은 행교환, 컴퓨터 계산은 피벗팅으로 오차 관리.

Gaussian Elimination

Gaussian Elimination

1. 직관 (변수를 하나씩 소거해 위삼각꼴로)

2. 절차 (3가지 행연산 → 사다리꼴 → 후진대입)

3. 해의 종류 (유일해 / 무수히 많음 / 없음 — 피벗으로 판별)

4. 예시 (구체 3변수 풀이)

5. 어디에 쓰나 / 흔한 함정

6. 30초 요약 (bullets)

관련 노트