소거법, 행 사다리꼴, 가우스 소거법: 선형대수 기초 2장

1장에서는 선형방정식 시스템의 개념과 행렬의 특이성, 행렬식을 배웠습니다. 이번 글에서는 실제로 방정식 시스템을 푸는 방법을 다룹니다. 소거법(Elimination)부터 시작해 행 사다리꼴, 가우스 소거법, 그리고 랭크(Rank)까지 이어집니다.

이 글은 DeepLearning.AI의 Mathematics for Machine Learning and Data Science 1주차 내용을 기반으로 정리했습니다.

이번 글에서 배우는 것#

• 소거법(Elimination) 으로 선형방정식 시스템 풀기
• 행 축소(Matrix Row Reduction) 로 행렬을 이용한 풀이
• 행 사다리꼴(Row Echelon Form, REF) 과 기약 행 사다리꼴(RREF) 계산
• 랭크(Rank) 를 구하고, 랭크로 해의 개수 판단하기

---

비특이 시스템 풀기 — 소거법#

소거법은 방정식들을 조합해 변수를 하나씩 제거하며 해를 구하는 방법입니다.

예시:

$\begin{cases} a + b = 11 \\ a - b = -5 \end{cases}$

두 방정식이 모두 참이면, 두 방정식을 더하거나 빼도 여전히 참입니다.

1단계 — 두 방정식을 더함:

$(a + b) + (a - b) = 11 + (-5)$

$2a = 6 \quad \Rightarrow \quad a = 3$

2단계 — $a = 3$ 대입:

$3 + b = 11 \quad \Rightarrow \quad b = 8$

검증: $3 + 8 = 11$ ✓, $3 - 8 = -5$ ✓

핵심 원리: 방정식이 참이면, 그 방정식의 합/차/스칼라배도 항상 참입니다. 이것이 소거법의 수학적 근거입니다.

---

특이 시스템 풀기#

자유도 1 — 무한히 많은 해#

$\begin{cases} a + b = 5 \\ 2a + 2b = 10 \end{cases}$

2번 방정식에서 1번 방정식의 2배를 빼면:

$(2a + 2b) - 2(a + b) = 10 - 10$

$0 = 0$

이 결과는 항등식(항상 참)입니다. 즉 두 방정식이 동일한 정보를 담고 있으므로, $a$ 는 어떤 값이든 될 수 있고 $b = 5 - a$ 로 따라갑니다.

이를 자유도 1(1 degree of freedom) 이라고 합니다. 자유롭게 선택할 수 있는 변수가 1개이기 때문입니다.

해 없음 — 모순 시스템#

$\begin{cases} a + b = 5 \\ 2a + 2b = 12 \end{cases}$

2번 방정식에서 1번 방정식의 2배를 빼면:

$0 = 2$

이는 불가능한 등식입니다. 이 시스템은 해가 없습니다(no solution).

---

더 많은 변수가 있는 시스템#

3변수 시스템도 같은 원리로 풀 수 있습니다.

$\begin{cases} x + y + z = 6 \\ 2x + y + z = 8 \\ x + 2y + z = 9 \end{cases}$

1단계 — 1행을 이용해 2행, 3행에서 $x$ 소거:

• $R_2 \leftarrow R_2 - 2R_1$: $\quad -y - z = -4$
• $R_3 \leftarrow R_3 - R_1$: $\quad y + 0z = 3$

2단계 — $y = 3$ 대입:

$-3 - z = -4 \Rightarrow z = 1$

3단계 — 역대입(back substitution):

$x + 3 + 1 = 6 \Rightarrow x = 2$

해: $x = 2,\ y = 3,\ z = 1$

---

행 축소 (Matrix Row Reduction)#

방정식 대신 행렬로 같은 과정을 표현할 수 있습니다.

$\begin{cases} a + b = 11 \\ 2a - b = 2 \end{cases} \quad \Rightarrow \quad \begin{bmatrix} 1 & 1 \\ 2 & -1 \end{bmatrix}$

행 연산 수행 ($R_2 \leftarrow R_2 - 2R_1$):

$\begin{bmatrix} 1 & 1 \\ 0 & -3 \end{bmatrix}$

이 형태가 행 사다리꼴(Row Echelon Form) 입니다. 여기서 $-3b = -24 \Rightarrow b = 8$, 이후 $a = 3$ 을 구할 수 있습니다.

기약 행 사다리꼴(Reduced Row Echelon Form, RREF) 은 완전히 해가 분리된 형태입니다:

$\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \quad \Rightarrow \quad a = 3,\ b = 8$

특이 시스템의 행 사다리꼴#

특이 시스템의 경우, 소거 후 행이 $[0\ \ 0]$ 이 됩니다.

$\begin{bmatrix} 1 & 1 \\ 2 & 2 \end{bmatrix} \xrightarrow{R_2 - 2R_1} \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}$

두 번째 행이 전부 0이므로 해가 무한히 많습니다(자유도 1).

---

행 사다리꼴의 3가지 규칙#

행 사다리꼴(REF)을 만족하려면 다음 조건이 필요합니다.

1. 대각 원소(pivot) 는 0 또는 1
2. 대각 아래쪽은 항상 0
3. 대각 위쪽은:
   • 대각 원소가 1이면 어떤 수도 가능
   • 대각 원소가 0이면 반드시 0

---

특이성을 보존하는 행 연산#

방정식에 적용하던 연산을 행렬의 행에도 동일하게 적용할 수 있습니다. 중요한 것은 이 연산들이 행렬의 특이성을 변경하지 않는다는 점입니다.

주의: 행의 모든 원소에 고정 상수를 더하는 것은 특이성을 바꿀 수 있으므로 허용되지 않습니다.

---

행렬의 랭크 (Rank)#

랭크(Rank) 는 행렬이 담고 있는 실질적인 정보의 양입니다.

• 행 사다리꼴로 변환했을 때, 0이 아닌 행의 수 = 랭크
• 선형 독립인 행의 최대 개수

$\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \xrightarrow{\text{REF}} \begin{bmatrix} 1 & 2 \\ 0 & -2 \end{bmatrix} \quad \Rightarrow \quad \text{rank} = 2 \quad \text{(비특이)}$

$\begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix} \xrightarrow{\text{REF}} \begin{bmatrix} 1 & 2 \\ 0 & 0 \end{bmatrix} \quad \Rightarrow \quad \text{rank} = 1 \quad \text{(특이)}$

랭크와 해의 관계#

$n \times n$ 행렬(n개 변수, n개 방정식)에서:

---

가우스 소거법 (Gaussian Elimination)#

가우스 소거법은 첨가 행렬(augmented matrix) — 계수 행렬과 상수 열을 합친 행렬 — 에 행 연산을 적용해 해를 구하는 체계적인 알고리즘입니다.

단계별 예시#

$\begin{cases} x + 2y + z = 7 \\ 2x + y + z = 8 \\ x + y + 2z = 8 \end{cases}$

첨가 행렬:

$\left[\begin{array}{ccc|c} 1 & 2 & 1 & 7 \\ 2 & 1 & 1 & 8 \\ 1 & 1 & 2 & 8 \end{array}\right]$

1단계 — $R_2 \leftarrow R_2 - 2R_1$, $R_3 \leftarrow R_3 - R_1$:

$\left[\begin{array}{ccc|c} 1 & 2 & 1 & 7 \\ 0 & -3 & -1 & -6 \\ 0 & -1 & 1 & 1 \end{array}\right]$

2단계 — $R_3 \leftarrow R_3 - \frac{1}{3}R_2$:

$\left[\begin{array}{ccc|c} 1 & 2 & 1 & 7 \\ 0 & -3 & -1 & -6 \\ 0 & 0 & \frac{4}{3} & 3 \end{array}\right]$

이제 행 사다리꼴(REF) 완성입니다.

3단계 — 역대입(Back Substitution):

$\frac{4}{3}z = 3 \Rightarrow z = \frac{9}{4}$

$-3y - \frac{9}{4} = -6 \Rightarrow y = \frac{5}{4}$

$x + 2 \cdot \frac{5}{4} + \frac{9}{4} = 7 \Rightarrow x = \frac{9}{4}$

알고리즘 요약: 전진 소거(Forward Elimination)로 REF를 만들고 → 역대입(Back Substitution)으로 해를 구한다.

---

핵심 정리#

---

퀴즈#

Q1. 다음 시스템을 소거법으로 푸세요.

$\begin{cases} 3x + 2y = 1 \\ x - y = 3 \end{cases}$

정답 보기

$R_1 \leftarrow R_1 - 3R_2$: $(3x + 2y) - 3(x - y) = 1 - 9$

$5y = -8 \Rightarrow y = -\frac{8}{5}$

$x = 3 + y = 3 - \frac{8}{5} = \frac{7}{5}$

해: $x = \dfrac{7}{5},\ y = -\dfrac{8}{5}$

---

Q2. 다음 행렬을 행 사다리꼴(REF)로 변환하고 랭크를 구하세요.

$\begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 0 & 1 & 1 \end{bmatrix}$

정답 보기

$R_2 \leftarrow R_2 - 2R_1$:

$\begin{bmatrix} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 1 & 1 \end{bmatrix}$

$R_2 \leftrightarrow R_3$ (행 교환):

$\begin{bmatrix} 1 & 2 & 3 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix}$

0이 아닌 행이 2개이므로 rank = 2 (특이 행렬).

---

Q3. 다음 중 행렬의 특이성을 보존하지 않는 연산은?

1. 두 행을 교환한다
2. 한 행에 다른 행을 더한다
3. 모든 원소에 5를 더한다
4. 한 행에 3을 곱한다

정답 보기

3번 — 행의 모든 원소에 고정 상수를 더하는 것은 방정식 연산에 해당하지 않으므로 특이성을 바꿀 수 있습니다.

1, 2, 4번은 모두 허용된 행 연산으로 특이성을 보존합니다.

---

Q4. 다음 시스템의 랭크와 해의 종류를 판단하세요.

$\begin{cases} x + y = 3 \\ 2x + 2y = 6 \\ 3x + 3y = 9 \end{cases}$

정답 보기

첨가 행렬:

$\left[\begin{array}{cc|c} 1 & 1 & 3 \\ 2 & 2 & 6 \\ 3 & 3 & 9 \end{array}\right]$

$R_2 \leftarrow R_2 - 2R_1$, $R_3 \leftarrow R_3 - 3R_1$ 적용 후:

$\left[\begin{array}{cc|c} 1 & 1 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right]$

rank = 1, 자유도 = 1 → 무한히 많은 해 (특이 시스템)

세 방정식이 모두 동일한 정보를 담고 있습니다.

---

다음 글에서는 벡터 연산(합, 차, 점곱, 노름), 선형 변환, 행렬 곱셈, 역행렬, 그리고 이것이 뉴럴 네트워크(퍼셉트론) 에서 어떻게 쓰이는지를 다룰 예정입니다.