Ch.2 §2.3 — Elimination Using Matrices

1 왜 행 연산을 행렬로 표현하는가

§2.2에서 소거법을 절차적 언어로 기술했다 — “2행에서 1행의 3배를 뺀다”, “3행과 2행을 교환한다”. 이 절은 그 절차적 기술을 행렬 언어로 바꾼다.

노트

핵심 전환: 행 연산 → 행렬 곱셈

소거법의 각 단계는 소거 행렬 \(E_{ij}\) 를 왼쪽에서 곱하는 것과 동일하다.

\[\text{"$i$ 행에서 $j$ 행의 $\ell$ 배를 뺀다"} \iff E_{ij} \cdot (\text{현재 행렬})\]

• 전체 소거 과정: \(A \xrightarrow{E_{21}} \xrightarrow{E_{31}} \xrightarrow{E_{32}} U\)
• 행렬 언어: \((E_{32} E_{31} E_{21}) A = U\)

이 추상화가 중요한 이유:

1. 기록: 소거 과정 전체를 행렬 곱 \(E_{32}E_{31}E_{21}\) 로 간결하게 기록한다.
2. 역연산: 역행렬 \(E^{-1}\) 이 소거를 되돌린다 → \(A = LU\) 분해의 기초.
3. 이론: 행 연산 = 행렬 곱이라는 사실로 선형대수의 구조를 분석할 수 있다.

---

2 \(Ax\) 복습: 행 방법과 열 방법

소거 행렬을 이해하기 전에 행렬-벡터 곱 \(Ax\) 의 두 방법을 다시 확인한다.

2.1 행 방법: 각 행과 \(x\) 의 내적

\(Ax\) 의 \(i\) 번째 성분은 \(A\) 의 \(i\) 번째 행과 \(x\) 의 내적이다.

\[(Ax)_i = \sum_{j=1}^{n} a_{ij} x_j = a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n\]

직관: 각 방정식(행)을 독립적으로 계산한다. \(i\) 번째 방정식에서 각 미지수에 계수를 곱하고 더한다.

2.2 열 방법: 열벡터들의 선형 결합

\(Ax\) 는 \(A\) 의 열들을 \(x\) 의 성분으로 결합한 것이다.

\[Ax = x_1(\text{col}_1) + x_2(\text{col}_2) + \cdots + x_n(\text{col}_n)\]

직관: \(x\) 의 각 성분이 대응하는 열벡터에 곱하는 “가중치”이다.

3×3 예시로 두 방법이 같은 결과를 주는지 확인한다:

\[ A = \begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix},\quad x = \begin{bmatrix} -1 \\ 2 \\ 2 \end{bmatrix} \]

행 방법: \((Ax)_1 = 2(-1) + 4(2) + (-2)(2) = -2 + 8 - 4 = 2\)

열 방법: \((-1)\begin{bmatrix}2\\4\\-2\end{bmatrix} + 2\begin{bmatrix}4\\9\\-3\end{bmatrix} + 2\begin{bmatrix}-2\\-3\\7\end{bmatrix} = \begin{bmatrix}-2+8-4\\-4+18-6\\2-6+14\end{bmatrix} = \begin{bmatrix}2\\8\\10\end{bmatrix}\)

두 방법 모두 \(Ax = b = (2, 8, 10)^\top\) 를 준다.

---

3 소거 행렬 \(E_{ij}\) — 한 단계 소거를 하나의 행렬로

3.1 \(E_{ij}\) 의 정의와 구성법

소거 행렬 \(E_{ij}\)는 “\(i\) 행에서 \(j\) 행의 \(\ell\) 배를 뺀다”는 한 가지 소거 연산을 행렬로 표현한 것이다.

구성 방법:

단위 행렬 \(I\) 에서 \((i, j)\) 위치의 0을 \(-\ell\) 로 바꾼다.

\[ E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ \boxed{-\ell_{21}} & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \quad \text{(2행 1열 위치에 } -\ell_{21} \text{)} \]

나머지 행들은 단위 행렬 \(I\) 의 행 그대로이다 — 해당 행에 아무것도 하지 않는다.

3.2 왜 단위 행렬 \(I\) 에서 출발하는가?

직관 1 — \(I\) 의 각 행은 “그대로 출력하라”는 지시이다

\(I\) 를 \(v\) 에 곱하면 \(Iv = v\) 이다. 왜인가? \(I\) 의 \(i\) 번째 행은 \(e_i^\top = [0, \ldots, 1, \ldots, 0]\) (i번째 위치만 1)이다.

\[ (Iv)_i = e_i^\top v = v_i \]

\(i\) 번째 행이 “\(v\) 의 \(i\) 번째 성분을 그대로 가져오라”고 지시한다. 모든 행이 이런 식이므로 \(Iv = v\) 이다.

직관 2 — \(E_{ij}\) 의 각 행은 “행 연산 지시문”이다

\(E_{21}\) 의 세 행을 읽으면:

• 1행 \([1, 0, 0]\): “1번째 성분을 그대로 출력하라” → 1행 변환 없음
• 2행 \([-\ell, 1, 0]\): “\(-\ell \times\)(1번째 성분) \(+\) 1 \(\times\)(2번째 성분)을 출력하라” → 2행에서 1행의 \(\ell\) 배를 뺀다
• 3행 \([0, 0, 1]\): “3번째 성분을 그대로 출력하라” → 3행 변환 없음

\(E_{ij}\) 는 \(I\) 에서 딱 하나의 원소만 바꾼 행렬이다. 그 결과로 “딱 하나의 행만 바뀌고, 나머지는 그대로인” 변환이 만들어진다.

3.3 왜 \(-\ell\) 인가? — 부호의 직관

소거 연산은 “빼기”이다: \((\text{새 }i\text{행}) \leftarrow (\text{기존 }i\text{행}) - \ell \times (j\text{행})\).

\(E_{21}\) 을 벡터 \(v\) 에 곱하면 어떻게 되는지 직접 계산한다.

\[ E_{21} v = \begin{bmatrix} 1 & 0 & 0 \\ -\ell & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \\ v_3 \end{bmatrix} = \begin{bmatrix} 1 \cdot v_1 + 0 + 0 \\ (-\ell) \cdot v_1 + 1 \cdot v_2 + 0 \\ 0 + 0 + 1 \cdot v_3 \end{bmatrix} = \begin{bmatrix} v_1 \\ v_2 - \ell v_1 \\ v_3 \end{bmatrix} \]

• 1행: \(v_1\) 그대로.
• 2행: \(v_2 - \ell v_1\) — 정확히 “\(v_1\) 의 \(\ell\) 배를 뺀다”는 소거 연산이다.
• 3행: \(v_3\) 그대로.

\(-\ell\) 을 넣는 이유: 행렬-벡터 곱에서 2행은 \((-\ell) \cdot v_1 + 1 \cdot v_2\) 이 되어야 하므로.

3.4 구체적 예시: \(E_{21}\) 으로 3×3 소거 1단계

이전 §2.2의 3×3 예시를 계속 사용한다.

\[ A = \begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix},\quad b = \begin{bmatrix} 2 \\ 8 \\ 10 \end{bmatrix} \]

첫 번째 소거: 2행에서 1행의 \(\ell_{21} = 4/2 = 2\) 배를 뺀다.

\[ E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \]

\(E_{21} A\) 계산 — 각 행이 어떻게 바뀌는지 전개한다:

\[ E_{21} A = \begin{bmatrix} 1\cdot(2,4,-2) + 0 + 0 \\ (-2)\cdot(2,4,-2) + 1\cdot(4,9,-3) + 0 \\ 0 + 0 + 1\cdot(-2,-3,7) \end{bmatrix} = \begin{bmatrix} 2 & 4 & -2 \\ -4+4 & -8+9 & 4-3 \\ -2 & -3 & 7 \end{bmatrix} = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ -2 & -3 & 7 \end{bmatrix} \]

\(E_{21} b\) 계산:

\[ E_{21} b = \begin{bmatrix} 2 \\ -2(2)+8 \\ 10 \end{bmatrix} = \begin{bmatrix} 2 \\ 4 \\ 10 \end{bmatrix} \]

새 시스템 \(E_{21}A \cdot x = E_{21}b\) 는 \(Ax = b\) 와 같은 해를 갖는다. 소거가 행렬 곱으로 표현됐다.

---

4 행렬 곱셈의 의미와 법칙

4.1 행렬이 “작용한다(acts)”

\(E_{21}\) 이 \(A\) 에 곱해질 때, \(E_{21}\) 은 \(A\) 를 변환한다. 행렬은 수동적인 수 배열이 아니라 능동적인 변환이다.

행렬 곱셈 \(AB\) 를 이해하는 세 가지 관점:

관점	해석
\((AB)_{ij} = (\text{row}_i \text{ of } A) \cdot (\text{col}_j \text{ of } B)\)	각 원소를 내적으로 계산
\(AB\) 의 각 열 \(= A \times (B\text{의 해당 열})\)	\(B\) 의 각 열에 \(A\) 를 독립적으로 작용
\(AB\) 의 각 행 = \(A\) 의 해당 행 \(\times B\)	\(A\) 의 각 행이 \(B\) 의 행들의 결합을 지시

4.2 결합 법칙 (Associative Law) — 성립한다

\[A(BC) = (AB)C\]

직관: 세 변환을 순서대로 적용할 때, 어떻게 묶어서 계산해도 최종 결과가 같다.

소거에서의 활용: \(E_{32}(E_{31}(E_{21}A)) = (E_{32}E_{31}E_{21})A\)

이 성질 덕분에 전체 소거 과정을 하나의 행렬 \(E = E_{32}E_{31}E_{21}\) 로 압축할 수 있다.

왜 결합 법칙이 성립하는가?

핵심 아이디어는 “행렬 곱셈이 함수 합성(function composition)이다”는 것이다. 함수 \(f\), \(g\), \(h\) 에 대해

\[(f \circ g \circ h)(x) = f(g(h(x)))\]

어떻게 괄호를 치든 \(h\) 먼저, \(g\) 다음, \(f\) 마지막 순으로 적용된다. 행렬 곱도 마찬가지다.

\[A(BC)v = A\bigl(B(Cv)\bigr), \quad (AB)Cv = A(B(Cv))\]

\(v\) 에 \(C\) 먼저, 그다음 \(B\), 마지막으로 \(A\) 를 적용하는 순서는 괄호 위치와 관계없이 고정된다. 따라서 \(A(BC) = (AB)C\) 이다.

힌트

결합 법칙은 “어떤 순서로 곱해도 된다”는 뜻이 아니다. \(A, B, C\) 의 순서는 고정된다. 결합 법칙은 그 순서를 유지한 채로 어디서 먼저 계산할지 (괄호 위치)만 자유롭다는 뜻이다. 교환 법칙(순서 바꾸기)과 혼동하지 않는다.

4.3 교환 법칙 (Commutative Law) — 일반적으로 성립하지 않는다

\[AB \neq BA \quad (\text{일반적})\]

왜 성립하지 않는가? 행렬은 방향이 있는 변환이다. “\(A\) 먼저, \(B\) 나중”과 “\(B\) 먼저, \(A\) 나중”은 다른 변환이다.

구체적 반례:

\[ E_{21} = \begin{bmatrix} 1 & 0 \\ -2 & 1 \end{bmatrix},\quad E_{12} = \begin{bmatrix} 1 & -3 \\ 0 & 1 \end{bmatrix} \]

\[ E_{21} E_{12} = \begin{bmatrix} 1 & -3 \\ -2 & 7 \end{bmatrix} \quad \neq \quad E_{12} E_{21} = \begin{bmatrix} 7 & -3 \\ -2 & 1 \end{bmatrix} \]

왜 결과가 다른가? — 단계별 직관

\(E_{21}\): “2행에서 1행의 2배를 뺀다”. \(E_{12}\): “1행에서 2행의 3배를 뺀다”.

\(v = (v_1, v_2)^\top\) 에 두 순서를 적용해 보자.

순서 A: \(E_{12}\) 를 먼저, 그다음 \(E_{21}\)

\[ v = \begin{bmatrix} v_1 \\ v_2 \end{bmatrix} \xrightarrow{E_{12}} \begin{bmatrix} v_1 - 3v_2 \\ v_2 \end{bmatrix} \xrightarrow{E_{21}} \begin{bmatrix} v_1 - 3v_2 \\ v_2 - 2(v_1 - 3v_2) \end{bmatrix} = \begin{bmatrix} v_1 - 3v_2 \\ -2v_1 + 7v_2 \end{bmatrix} \]

\(E_{21}\) 이 \(E_{12}\) 로 이미 수정된 1행에 작용한다. 따라서 2행에서 \(v_1 - 3v_2\) 의 2배를 빼게 된다.

순서 B: \(E_{21}\) 을 먼저, 그다음 \(E_{12}\)

\[ v = \begin{bmatrix} v_1 \\ v_2 \end{bmatrix} \xrightarrow{E_{21}} \begin{bmatrix} v_1 \\ v_2 - 2v_1 \end{bmatrix} \xrightarrow{E_{12}} \begin{bmatrix} v_1 - 3(v_2 - 2v_1) \\ v_2 - 2v_1 \end{bmatrix} = \begin{bmatrix} 7v_1 - 3v_2 \\ -2v_1 + v_2 \end{bmatrix} \]

\(E_{12}\) 가 \(E_{21}\) 로 이미 수정된 2행에 작용한다. 1행에서 \(v_2 - 2v_1\) 의 3배를 빼게 된다.

핵심: 먼저 적용된 변환이 중간 값을 바꾸어 놓기 때문에 나중 변환의 실질적 계산이 달라진다. 순서를 바꾸면 “어떤 버전의 행”에 작용하는지가 달라진다.

노트

소거 행렬들이 서로 다른 행을 건드리는 경우 (예: \(E_{31}\) 과 \(E_{32}\)) 순서를 바꾸어도 결과가 같다. 두 연산이 서로 다른 행을 변형하기 때문이다. 반면 \(E_{21}\) 과 \(E_{12}\) 는 1행과 2행을 서로 참조하기 때문에 순서가 중요하다.

실용적 결론: 소거 행렬들의 순서가 중요하다. \(E_{21}\) 다음 \(E_{32}\) 와, \(E_{32}\) 다음 \(E_{21}\) 은 다른 결과를 낸다.

4.4 왼쪽 곱과 오른쪽 곱의 차이

\(E\) 를 \(A\) 의 왼쪽에서 곱하면 \(A\) 의 행에 작용한다.

\[EA: \quad \text{$E$ 의 각 행이 "$A$ 의 행들 중 어떤 것을 얼마만큼 합칠지" 지시}\]

\(E\) 를 \(A\) 의 오른쪽에서 곱하면 \(A\) 의 열에 작용한다.

\[AE: \quad \text{$E$ 의 각 열이 "$A$ 의 열들 중 어떤 것을 얼마만큼 합칠지" 지시}\]

소거법은 행 연산이므로 항상 왼쪽에서 곱한다.

예: \(E_{21}\) 을 오른쪽에서 곱하면 “1열의 4배를 2열에서 뺀다”는 열 연산이 된다.

4.5 열 단위 행렬 곱셈

\(A\) 와 \(B = [b_1 \; b_2 \; b_3]\) 의 곱은 각 열에 독립적으로 \(A\) 를 작용한 것이다.

\[AB = A[b_1 \; b_2 \; b_3] = [Ab_1 \; Ab_2 \; Ab_3]\]

직관: \(B\) 의 각 열이 독립적인 \(Ax = b\) 문제의 우변이라고 볼 수 있다.

예시:

\[ E_{21} \begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix} = \Bigl[ E_{21}\!\begin{pmatrix}2\\4\\-2\end{pmatrix} \;\Big|\; E_{21}\!\begin{pmatrix}4\\9\\-3\end{pmatrix} \;\Big|\; E_{21}\!\begin{pmatrix}-2\\-3\\7\end{pmatrix} \Bigr] = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ -2 & -3 & 7 \end{bmatrix} \]

---

5 전체 소거 과정: \(E_{32}E_{31}E_{21}A = U\)

§2.2의 3×3 예시 전체를 행렬 언어로 기술한다.

5.1 Step 1: \(E_{21}A\) — 2행에서 1행의 2배를 뺀다

\[ E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \implies E_{21} A = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ -2 & -3 & 7 \end{bmatrix} \]

5.2 Step 2: \(E_{31}(E_{21}A)\) — 3행에서 1행의 \((-1)\) 배를 뺀다 (= 1행을 더한다)

\(\ell_{31} = -2/2 = -1\) 이므로 \(E_{31}\) 의 \((3,1)\) 위치에 \(-\ell_{31} = 1\) 이 들어간다.

\[ E_{31} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \implies E_{31}(E_{21}A) = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 1 & 5 \end{bmatrix} \]

확인: 새 3행 = 기존 3행 \((-2, -3, 7)\) + 1행 \((2, 4, -2)\) = \((0, 1, 5)\).

5.3 Step 3: \(E_{32}(E_{31}E_{21}A)\) — 3행에서 2행의 1배를 뺀다

\[ E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix} \implies U = E_{32}(E_{31}E_{21}A) = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 0 & 4 \end{bmatrix} \]

5.4 전체를 하나의 식으로

\[ (E_{32} E_{31} E_{21}) A = U \]

---

6 소거 행렬의 역행렬 — 빼기의 역은 더하기

\(E_{ij}\) 의 역행렬 \(E_{ij}^{-1}\) 은 소거를 되돌리는 행렬이다.

직관: \(E_{21}\) 이 “2행에서 1행의 \(\ell\) 배를 뺐으면”, \(E_{21}^{-1}\) 은 “2행에 1행의 \(\ell\) 배를 더한다”.

\[ E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -\ell & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \implies E_{21}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ +\ell & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \]

부호만 반전하면 된다. 검증:

\[ E_{21}^{-1} E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ \ell & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -\ell & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ \ell - \ell & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = I \checkmark \]

2행 1열: \(\ell \cdot 1 + 1 \cdot (-\ell) = 0\). 더하기와 빼기가 정확히 상쇄된다.

6.1 \(A = LU\) 연결

\[ E_{32}E_{31}E_{21}A = U \implies A = \underbrace{E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}}_{= L}U = LU \]

\(L\) 의 원소들이 소거의 승수 \(\ell_{ij}\) 들과 같은 이유: 역행렬들을 순서대로 곱할 때, 서로 다른 열의 승수들이 간섭하지 않고 각자의 자리에 들어간다.

왜 승수들이 그대로 \(L\) 에 들어가는가?

세 역행렬을 명시적으로 곱해 보자.

\[ E_{21}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix},\quad E_{31}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix},\quad E_{32}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \]

먼저 \(E_{21}^{-1} E_{31}^{-1}\):

\[ \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix} \]

\(E_{21}^{-1}\) 의 \((2,1)\) 위치의 2는 \(E_{31}^{-1}\) 의 1열과 내적할 때 \((1, 0, 0)\) 의 1열 → \(2 \cdot 1 + 1 \cdot 0 = 2\), 변하지 않는다. \(E_{31}^{-1}\) 의 \((3,1)\) 위치의 \(-1\) 도 \(E_{21}^{-1}\) 의 영향을 받지 않고 그대로 들어간다.

다음으로 \((E_{21}^{-1} E_{31}^{-1}) E_{32}^{-1}\):

\[ \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 1 & 1 \end{bmatrix} \]

\(E_{32}^{-1}\) 의 \((3,2)\) 위치의 1이 \(L\) 의 \((3,2)\) 위치에 그대로 들어간다.

비밀: 각 역행렬 \(E_{ij}^{-1}\) 은 오직 하나의 원소 \((\ell_{ij}\))만 \(I\) 에서 다르다. 이 원소가 이미 계산된 중간 행렬의 다른 열과 상호작용하지 않도록, 소거 순서(\(E_{21} \to E_{31} \to E_{32}\), 즉 왼쪽 열부터)가 설계되어 있다. 역순(\(E_{21}^{-1} \to E_{31}^{-1} \to E_{32}^{-1}\))으로 곱하면 각 승수가 “자신의 자리”에 간섭 없이 들어간다. 이것이 \(L\) 이 승수들의 행렬인 이유다.

\[ L = \begin{bmatrix} 1 & 0 & 0 \\ \ell_{21} & 1 & 0 \\ \ell_{31} & \ell_{32} & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 1 & 1 \end{bmatrix} \]

---

7 치환 행렬 \(P_{ij}\) — 행 교환을 행렬로

7.1 치환 행렬의 구성과 의미

피벗 위치에 0이 나타나면 행 교환이 필요하다. 행 교환도 행렬로 표현한다.

치환 행렬 \(P_{ij}\): 단위 행렬 \(I\) 에서 \(i\) 행과 \(j\) 행을 서로 바꾼 행렬.

\[ P_{23} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \]

\(P_{23}\) 이 \(I\) 에서 2행과 3행을 교환한 것임을 확인한다: 2행이 \([0,0,1]\) (원래 \(I\) 의 3행), 3행이 \([0,1,0]\) (원래 \(I\) 의 2행).

\(P_{23}\) 을 벡터에 곱하면:

\[ P_{23} \begin{bmatrix} v_1 \\ v_2 \\ v_3 \end{bmatrix} = \begin{bmatrix} v_1 \\ v_3 \\ v_2 \end{bmatrix} \quad \text{(2번째와 3번째 성분이 교환된다)} \]

직관: \(P_{23}\) 의 2행 \([0,0,1]\) 은 “\(v\) 의 3번째 성분을 출력하라”는 지시이다. 3행 \([0,1,0]\) 은 “2번째 성분을 출력하라”는 지시이다. 이처럼 치환 행렬의 각 행은 원본의 어떤 성분을 가져올지 지정한다.

\(P_{23}\) 을 행렬에 곱하면:

\[ P_{23} \begin{bmatrix} 2 & 4 & 1 \\ 0 & 0 & 3 \\ 0 & 6 & 5 \end{bmatrix} = \begin{bmatrix} 2 & 4 & 1 \\ 0 & 6 & 5 \\ 0 & 0 & 3 \end{bmatrix} \]

2행(피벗 0)과 3행(피벗 6)이 교환되어 소거를 계속할 수 있다.

7.2 치환 행렬의 핵심 성질

\[P_{ij}^{-1} = P_{ij}^\top = P_{ij}\]

왜 \(P_{ij}^2 = I\) 인가? — “두 번 교환 = 원상복구”

\(P_{23}\) 을 두 번 적용하면:

\[ \begin{bmatrix} v_1 \\ v_2 \\ v_3 \end{bmatrix} \xrightarrow{P_{23}} \begin{bmatrix} v_1 \\ v_3 \\ v_2 \end{bmatrix} \xrightarrow{P_{23}} \begin{bmatrix} v_1 \\ v_2 \\ v_3 \end{bmatrix} \]

2행과 3행을 교환하고, 다시 교환하면 원래로 돌아온다. 따라서 \(P_{23} P_{23} = I\), 즉 \(P_{23}^{-1} = P_{23}\) 이다.

왜 \(P_{ij}^\top = P_{ij}^{-1}\) 인가? — 직교 행렬의 특성

\(P_{23}\) 의 전치를 계산한다:

\[ P_{23} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \implies P_{23}^\top = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} = P_{23} \]

\(P_{23}\) 이 대칭 행렬(\(P_{23}^\top = P_{23}\))이므로 \(P_{23}^\top = P_{23} = P_{23}^{-1}\).

일반적으로 치환 행렬의 행들은 단위 벡터 \(e_i\) 들의 순열이다. 이 행들은 서로 직교하고 각 노름이 1이다 — 즉 치환 행렬은 직교 행렬(orthogonal matrix)이다. 직교 행렬은 \(Q^\top Q = I\) 를 만족하므로 \(Q^{-1} = Q^\top\).

행 교환을 두 번 하면 원래로 돌아온다: \(P_{ij} P_{ij} = I\).

---

8 확장 행렬 (Augmented Matrix) — 좌우를 동시에 처리

8.1 확장 행렬의 아이디어

소거는 \(A\) 의 행과 \(b\) 의 성분에 동시에 같은 연산을 적용한다. 이 두 가지를 하나로 합쳐 확장 행렬 \([A \mid b]\) 를 만들면 효율적이다.

\[ [A \mid b] = \left[\begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 4 & 9 & -3 & 8 \\ -2 & -3 & 7 & 10 \end{array}\right] \]

소거 행렬 \(E\) 가 \([A \mid b]\) 에 작용하면 좌우 양쪽이 동시에 변환된다:

\[ E_{21} [A \mid b] = [E_{21}A \mid E_{21}b] \]

왜 확장 행렬이 해를 보존하는가? — 등가 변환의 원리

\(Ax = b\) 의 해 \(x^*\) 가 존재한다고 하자. \(E_{21}A\) 를 계수 행렬로 갖는 새 시스템 \(E_{21}Ax = E_{21}b\) 에 \(x^*\) 를 대입하면:

\[ E_{21}A x^* = E_{21}(Ax^*) = E_{21}b \checkmark \]

\(x^*\) 는 새 시스템도 만족한다. 역방향: \(E_{21}\) 은 가역이므로, \(E_{21}Ax = E_{21}b\) 를 만족하는 \(x\) 는 양변에 \(E_{21}^{-1}\) 을 곱해 \(Ax = b\) 로 복원된다. 따라서 두 시스템의 해집합이 일치한다.

\[ Ax = b \iff E_{21}Ax = E_{21}b \]

이것이 소거가 해를 바꾸지 않는 이유이다. 소거 행렬 \(E_{ij}\) 는 항상 가역이므로(역행렬 = 부호 반전) 이 등가성이 보장된다.

직관: \([A \mid b]\) 를 \(n \times (n+1)\) 행렬로 보고 \(E\) 를 왼쪽에서 곱한다. \(A\) 부분의 소거와 \(b\) 부분의 변환이 동시에 일어난다.

8.2 3×3 예시: 확장 행렬로 전체 소거 추적

초기:

\[ \left[\begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 4 & 9 & -3 & 8 \\ -2 & -3 & 7 & 10 \end{array}\right] \]

\(E_{21}\) 적용 (\(R_2 - 2R_1\)):

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

\(E_{31}\) 적용 (\(R_3 + R_1\)):

\[ \left[\begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 4 \\ 0 & 1 & 5 & 12 \end{array}\right] \]

\(E_{32}\) 적용 (\(R_3 - R_2\)):

\[ \left[\begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 4 & 8 \end{array}\right] = [U \mid c] \]

\(Ux = c\): 후방 대입으로 \(z = 2\), \(y = 2\), \(x = -1\).

8.3 여러 우변을 동시에 처리

\[ [A \mid b_1 \mid b_2] \xrightarrow{\text{소거}} [U \mid c_1 \mid c_2] \]

\(LU\) 분해를 한 번 계산하고 여러 \(b\) 에 재사용하는 것과 동일하다.

---

9 Worked Examples

9.1 예시 1: \(E_{21}\) 의 오른쪽 곱 — 열 연산이 된다

\(E_{21}\) (\(\ell = 4\))을 오른쪽에서 곱하면:

\[ A E_{21} = A \begin{bmatrix} 1 & 0 & 0 \\ -4 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \]

\(AE_{21}\) 의 각 열은 \(A\) 의 열들의 선형 결합이다: 새 1열 \(= A\) 의 1열 \(- 4 \times\) 2열, 새 2열 = 2열, 새 3열 = 3열.

이것은 행 연산이 아니라 열 연산이다. 소거에서는 쓰지 않지만, 열 연산이 필요할 때 오른쪽 곱을 사용한다.

9.2 예시 2: \(P_{32}E_{21}\) — 두 연산을 하나의 행렬로

다음 시스템을 소거한다.

\[ \begin{cases} x + 2y + 2z = 1 \\ 4x + 8y + 9z = 3 \\ 3y + 2z = 1 \end{cases} \implies [A \mid b] = \left[\begin{array}{ccc|c} 1 & 2 & 2 & 1 \\ 4 & 8 & 9 & 3 \\ 0 & 3 & 2 & 1 \end{array}\right] \]

Step 1 — \(E_{21}\) 적용 (\(\ell_{21} = 4\)):

\[ E_{21}[A \mid b] = \left[\begin{array}{ccc|c} 1 & 2 & 2 & 1 \\ 0 & 0 & 1 & -1 \\ 0 & 3 & 2 & 1 \end{array}\right] \]

2열 피벗 위치가 0. 행 교환 필요.

Step 2 — \(P_{32}\) 적용 (\(R_2 \leftrightarrow R_3\)):

\[ P_{32}E_{21}[A \mid b] = \left[\begin{array}{ccc|c} 1 & 2 & 2 & 1 \\ 0 & 3 & 2 & 1 \\ 0 & 0 & 1 & -1 \end{array}\right] = [U \mid c] \]

이미 상삼각. 후방 대입: \(z = -1\), \(y = 1\), \(x = 1\).

합성 행렬 \(M = P_{32}E_{21}\):

\[ M = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -4 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ -4 & 1 & 0 \end{bmatrix} \]

9.3 예시 3: 행렬 곱셈의 두 가지 방법

\[ AB = \begin{bmatrix} 3 & 4 \\ 1 & 5 \\ 2 & 0 \end{bmatrix} \begin{bmatrix} 2 & 4 \\ 1 & 1 \end{bmatrix} \]

방법 1 — 내적 (행×열):

\((AB)_{11} = [3,4] \cdot [2,1]^\top = 10\), \((AB)_{12} = [3,4] \cdot [4,1]^\top = 16\), … 총 6번 내적.

방법 2 — 열×행 (외적 합, Outer Product Sum):

\[ AB = \underbrace{\begin{bmatrix} 3 \\ 1 \\ 2 \end{bmatrix}}_{A\text{의 열 1}} \underbrace{[2 \;\; 4]}_{B\text{의 행 1}} + \underbrace{\begin{bmatrix} 4 \\ 5 \\ 0 \end{bmatrix}}_{A\text{의 열 2}} \underbrace{[1 \;\; 1]}_{B\text{의 행 2}} = \begin{bmatrix} 6 & 12 \\ 2 & 4 \\ 4 & 8 \end{bmatrix} + \begin{bmatrix} 4 & 4 \\ 5 & 5 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 10 & 16 \\ 7 & 9 \\ 4 & 8 \end{bmatrix} \]

열×행 방법의 의미: 각 항이 랭크 1 행렬(Rank-1 Matrix)이다. \(AB\) 는 이런 랭크 1 행렬들의 합이다. 이 관점은 SVD에서 핵심이 된다.

---

10 ML/DL에서의 연결

10.1 배치 처리와 확장 행렬

딥러닝의 배치(Batch) 처리는 여러 샘플을 한 번에 처리한다:

\[ Y = AX, \quad X = [x_1 \mid x_2 \mid \cdots \mid x_B] \]

\(A\) 를 한 번만 계산하고 \(B\) 개의 \(x\) 에 동시에 적용하는 것은, 확장 행렬에 \(A\) 를 곱하는 것과 같은 논리이다.

10.2 역전파에서의 비가환성

신경망에서 레이어를 거꾸로 통과하는 역전파(Backpropagation)는 자코비안 행렬들의 곱이다.

\[\frac{\partial \mathcal{L}}{\partial x} = W_1^\top W_2^\top \cdots \frac{\partial \mathcal{L}}{\partial y}\]

행렬 곱의 비가환성 때문에 순서를 바꾸면 안 된다. \(AB \neq BA\) 라는 사실이 역전파 구현에서 핵심이다.

---

11 코드로 확인하기

11.1 Step 1 — 소거 행렬 \(E_{ij}\) 직접 구성

import numpy as np

def make_E(n, i, j, ell):
    """
    n×n 소거 행렬 E_ij 생성.
    i행에서 j행의 ell배를 뺀다.
    (i,j) 위치에 -ell, 나머지는 단위 행렬.
    (0-indexed)
    """
    E = np.eye(n)
    E[i, j] = -ell
    return E

def make_P(n, i, j):
    """n×n 치환 행렬 P_ij 생성 (i, j 행 교환). 0-indexed."""
    P = np.eye(n)
    P[[i, j]] = P[[j, i]]   # 행 교환
    return P

A = np.array([[2, 4, -2], [4, 9, -3], [-2, -3, 7]], dtype=float)
b = np.array([2, 8, 10], dtype=float)

# Step 1: E21 (2행에서 1행의 2배 뺌, 0-indexed: i=1, j=0, ell=2)
E21 = make_E(3, 1, 0, 2)
print("E21:\n", E21)

# Step 2: E31 (3행에서 1행의 -1배 뺌, 0-indexed: i=2, j=0, ell=-1)
E31 = make_E(3, 2, 0, -1)
print("E31:\n", E31)

# Step 3: E32 (3행에서 2행의 1배 뺌, 0-indexed: i=2, j=1, ell=1)
E32 = make_E(3, 2, 1, 1)
print("E32:\n", E32)

# 전체 소거
U = E32 @ E31 @ E21 @ A
c = E32 @ E31 @ E21 @ b
print("U:\n", U)
print("c:", c)   # [2. 4. 8.]

# L 계산 (역행렬들의 곱)
L = np.linalg.inv(E21) @ np.linalg.inv(E31) @ np.linalg.inv(E32)
print("L:\n", L)
# [[1.  0.  0.]
#  [2.  1.  0.]
#  [-1. 1.  1.]]  ← 승수들이 그대로!

print("LU = A?", np.allclose(L @ U, A))  # True

11.2 Step 2 — 확장 행렬로 소거 (실용 구현)

import numpy as np

def gaussian_elimination_augmented(A, b):
    """
    확장 행렬 [A|b]로 소거 수행.
    소거 행렬 E들과 L을 함께 추적한다.
    """
    n = len(b)
    Ab = np.hstack([A.copy().astype(float), b.reshape(-1, 1).astype(float)])
    L = np.eye(n)

    print("초기 [A|b]:\n", Ab)

    for j in range(n - 1):          # 피벗 열
        pivot = Ab[j, j]
        if abs(pivot) < 1e-12:
            raise ValueError(f"피벗 = 0: {j}열, 행 교환 필요")

        for i in range(j + 1, n):   # 피벗 아래 행들
            ell = Ab[i, j] / pivot
            Ab[i, :] -= ell * Ab[j, :]
            L[i, j] = ell            # L에 승수 기록

        print(f"Step {j+1} 후 [A|b]:\n", Ab)

    U = Ab[:, :-1]
    c = Ab[:, -1]

    # 후방 대입
    x = np.zeros(n)
    for i in range(n - 1, -1, -1):
        x[i] = (c[i] - U[i, i+1:] @ x[i+1:]) / U[i, i]

    return x, L, U

A = np.array([[2, 4, -2], [4, 9, -3], [-2, -3, 7]], dtype=float)
b = np.array([2, 8, 10], dtype=float)

x, L, U = gaussian_elimination_augmented(A, b)
print("\n해:", x)              # [-1.  2.  2.]
print("L:\n", L)               # 승수들이 대각선 아래에
print("U:\n", U)               # 피벗들이 대각선에
print("LU = A?", np.allclose(L @ U, A))   # True

11.3 Step 3 — 교환 법칙 검증

import numpy as np

# AB ≠ BA 확인
A = np.array([[1, 2], [0, 1]], dtype=float)
B = np.array([[1, 0], [3, 1]], dtype=float)

print("AB:\n", A @ B)
print("BA:\n", B @ A)
print("AB == BA?", np.allclose(A @ B, B @ A))   # False

# E_ij들의 순서 차이
E21 = np.array([[1., 0., 0.], [-2., 1., 0.], [0., 0., 1.]])
E32 = np.array([[1., 0., 0.], [0., 1., 0.], [0., -1., 1.]])

print("\nE32 @ E21:\n", E32 @ E21)
print("E21 @ E32:\n", E21 @ E32)
print("같은가?", np.allclose(E32 @ E21, E21 @ E32))   # False

---

12 핵심 요약

개념	수식 / 의미
소거 행렬 \(E_{ij}\)	\(I\) 에서 \((i,j)\) 위치에 \(-\ell\) — \(i\) 행에서 \(j\) 행의 \(\ell\) 배를 뺀다
\(E_{ij}v\) 효과	\(v_i \to v_i - \ell v_j\), 나머지 불변
\(E_{ij}A\) 효과	\(A\) 의 \(i\) 행 \(\to\) \(i\) 행 \(- \ell \times j\) 행 (왼쪽 곱 = 행 연산)
왼쪽 곱 vs 오른쪽 곱	왼쪽 = 행 연산, 오른쪽 = 열 연산
역행렬 \(E_{ij}^{-1}\)	\((i,j)\) 위치를 \(+\ell\) 로 — 빼기의 역은 더하기
치환 행렬 \(P_{ij}\)	\(I\) 에서 \(i\) 행과 \(j\) 행 교환, \(P_{ij}^2 = I\)
결합 법칙	\(A(BC) = (AB)C\) — 성립
교환 법칙	\(AB \neq BA\) — 일반적으로 불성립
확장 행렬	\([A \mid b]\) 로 좌우를 동시에 소거
전체 소거	\(E_{32}E_{31}E_{21}A = U\), \(A = LU\)

---

13 관련 주제

선행 지식

• Ch.2 §2.2 — The Idea of Elimination — 피벗·승수·전방 소거

이 챕터 다음

관련 심화