역행렬과 연립일차방정식

두 입력 x,y가 두 출력에 섞여 있을 때 출력에서 입력을 되돌릴 수 있을까요? 행렬 곱·선형 독립·행렬식·여인수를 사용해 가역성과 해의 개수를 이해합니다. 이 절은 선택 심화이며 기본 그래프 학습의 필수 선수는 아닙니다. 2×2 예를 먼저 읽고, 3×3의 두 계산법과 선택 Python 실행으로 이어갑니다.

역행렬은 양쪽 곱이 I

정사각행렬 A에 대해 $AA^{-1}=A^{-1}A=I$인 행렬이 역행렬입니다. 2×2에서 ad−bc≠0이면

대각선을 맞바꾸고 나머지 두 원소의 부호를 바꾼 후 행렬식으로 나눕니다. 각 자리의 역수를 취하는 계산이 아닙니다. $A=\begin{pmatrix}2&1\\1&1\end{pmatrix}$는 행렬식 1이므로 $A^{-1}=\begin{pmatrix}1&-1\\-1&2\end{pmatrix}$입니다. 직접 양쪽으로 곱하면 대각선이 1, 나머지가 0이라 검산할 수 있습니다.

Ax=b의 해와 소거

2x+y=7, x+y=4는 $A\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}7\\4\end{pmatrix}$입니다. 역행렬을 왼쪽에서 곱하면 x=7−4=3, y=−7+8=1입니다. 원래 두 식에 대입해 7과 4를 얻는지 확인합니다.

계수와 우변을 옆에 붙인 증강행렬에서 한 행은 식 하나입니다. 기본행연산은 다음 세 가지이며 우변에도 같은 연산을 합니다.

첫 단계는 두 행 교환, 다음은 $R_2\leftarrow R_2-2R_1$입니다. 둘째 행에서 y=1, 첫째 행에서 x=3입니다. 다음 열을 소거할 때 기준으로 쓰는 0이 아닌 원소를 피벗이라고 합니다. 이 계산은 첫 열의 1, 둘째 열의 −1을 피벗으로 썼습니다. 기준자리가 0이면 나누기 전에 아래 행에서 같은 열의 0이 아닌 원소를 찾아 행 전체를 교환합니다.

여인수행렬은 전치한 뒤 나눈다

앞 절의 $C=\begin{pmatrix}1&2&0\\0&1&3\\2&0&1\end{pmatrix}$는 det C=13입니다. 아홉 자리에서 행·열을 지우고 $(-1)^{i+j}$까지 곱해 여인수행렬 K를 만듭니다.

수반행렬 adj(C)는 여인수행렬의 전치입니다. N의 (2,1)이 K의 (1,2)=6이라는 식으로 위치를 확인합니다. 일반 실수 n×n 행렬에도 $A\operatorname{adj}(A)=\operatorname{adj}(A)A=(\det A)I$이며, det A≠0일 때만 $A^{-1}=\operatorname{adj}(A)/\det A$로 나눌 수 있습니다.

전치가 필요한 이유도 곱의 한 자리로 읽을 수 있습니다. $(A\operatorname{adj}(A))_{ij}=\sum_k a_{ik}K_{jk}$입니다. i=j이면 i행의 여인수 전개라 det A입니다. i≠j이면 j행을 i행으로 바꾼 행렬의 j행 전개이고, 같은 행이 둘이라 0입니다. 반대 곱은 같은 생각을 열 전개에 적용합니다. 이 설명은 앞 절의 행·열 전개와 같은 행이 두 개면 행렬식이 0이라는 성질을 사용합니다. 작은 예의 검산을 모든 행렬식 성질의 일반 증명과 혼동하지 않습니다.

이 C에서는 두 곱을 모두 계산해

를 얻습니다. 예를 들어 (CN)₁₃=1·6+2·(−3)+0·1=0, (NC)₂₁=6·1+1·0+(−3)·2=0입니다. 13으로 나누면 두 곱 모두 I입니다. K를 전치하지 않고 그대로 나누면 일반적으로 이 검산에 실패합니다.

같은 3×3을 [C와 I]의 소거로 끝까지 구한다

이번에는 여인수를 사용하지 않고 [C와 I]를 붙여 6열 모두에 같은 행연산을 합니다. 왼쪽이 I가 될 때 오른쪽을 읽습니다. 행연산들을 합친 변환을 E라 하면 [C와 I]는 [EC와 EI]가 됩니다. EC=I이면 오른쪽 EI=E가 C를 되돌리는 역행렬입니다. 각 기본행연산을 복원할 수 있어 E도 가역입니다.

시작:

1. 첫 열: $R_3\leftarrow R_3-2R_1$. 오른쪽 첫 자리도 0−2·1=−2로 바뀝니다.

2. 둘째 열 위: $R_1\leftarrow R_1-2R_2$.

3. 둘째 열 아래: $R_3\leftarrow R_3+4R_2$. 셋째 자리의 1+4·3=13이 새 피벗입니다.

4. 셋째 피벗을 1로: $R_3\leftarrow R_3/13$.

5. 셋째 열의 첫 행: $R_1\leftarrow R_1+6R_3$. 오른쪽은 $1-12/13=1/13$, $-2+24/13=-2/13$, $6/13$입니다.

6. 셋째 열의 둘째 행: $R_2\leftarrow R_2-3R_3$.

오른쪽 결과는 위 N/13과 같습니다. 두 방법으로 구한 역행렬이 일치하며 $CC^{-1}=C^{-1}C=I$를 검산할 수 있습니다.

기준 자리의 0과 역행렬 없음을 구별한다

첫 기준 자리가 0인 $P=\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}$는 $R_1\leftrightarrow R_2$로 왼쪽이 I가 됩니다. 같은 행 교환으로 오른쪽도 P가 되어 $P^{-1}=P$, $P^2=I$입니다. 0을 보고 바로 '역행렬 없음'으로 판단하지 않습니다.

반면 $S=\begin{pmatrix}1&2&3\\2&4&6\\0&1&1\end{pmatrix}$는 $R_2\leftarrow R_2-2R_1$로 왼쪽에 영행이 생깁니다. 다른 0이 아닌 행과 교환해도 독립된 행이 늘지 않아 왼쪽을 I로 만들 수 없습니다. det S=0이고 역행렬이 없습니다. 앞 열의 소거를 끝낸 뒤, 현재 행과 아래 행의 같은 열에 0이 아닌 값이 하나도 없으면 그 열에 새 피벗을 놓을 수 없습니다.

역행렬이 없어도 해가 있을 수 있다

x+y=2와 2x+2y=5를 소거하면 0=1이라 해가 없습니다. 둘째 식의 우변이 4이면 0=0이 되어 새 조건이 없습니다. y=t를 자유롭게 잡으면 x=2−t로 무한히 많은 해입니다. 계수행렬의 행렬식이 0이라는 사실만으로 해 없음과 무한해 중 하나를 정할 수는 없습니다. 우변까지 봐야 합니다. 위 소거 실패는 역행렬 없음이며, 모든 Ax=b에 해가 없다는 뜻이 아닙니다.

선택 실행: 분수로 같은 단계 재현하기

아래 전체 코드를 inverse_fraction.py에 저장하고 python inverse_fraction.py로 실행합니다. Python이 처음이면 목차의 실행 안내를 먼저 읽고, 코드를 건너뛰어 손 계산을 먼저 해도 됩니다. 외부 패키지는 필요 없습니다. Fraction은 정수와 "1/3" 같은 유리수 문자열을 정확한 분수로 계산합니다. 부동소수 입력은 이 실습에서 거절합니다.

코드는 0부터 시작하는 행·열 번호를 쓰므로 col=0이 수학의 첫 열입니다. work의 앞 n열은 계수, 뒤 n열은 I로 시작한 부분입니다. zip은 같은 자리끼리 묶고, row[:]는 각 단계를 복사해 다음 연산 뒤에도 이전 기록이 남게 합니다. 반복문은 열마다 0이 아닌 피벗 찾기→필요한 행 교환→피벗을 1로 만들기→다른 행의 같은 열을 0으로 만들기를 수행합니다.

"""Exact Gauss-Jordan example for discrete-math ch7-2. Standard library only."""
from fractions import Fraction
import sys


def inverse_fraction(matrix):
    n = len(matrix)
    if n == 0 or any(len(row) != n for row in matrix):
        raise ValueError("non-empty square matrix required")
    # Integers or rational strings such as "1/3"; reject binary float inputs.
    if any(isinstance(value, float) for row in matrix for value in row):
        raise TypeError("use integers or rational strings, not float")
    work = [[Fraction(value) for value in row] +
            [Fraction(int(i == j)) for j in range(n)]
            for i, row in enumerate(matrix)]
    trace = [("start", [row[:] for row in work])]

    def record(label):
        trace.append((label, [row[:] for row in work]))

    for col in range(n):
        # Search the current row AND lower rows before declaring failure.
        pivot_row = next((row for row in range(col, n)
                          if work[row][col] != 0), None)
        if pivot_row is None:
            raise ValueError(f"no nonzero pivot in column {col + 1}; singular")
        if pivot_row != col:
            work[col], work[pivot_row] = work[pivot_row], work[col]
            record(f"R{col + 1} <-> R{pivot_row + 1}")
        pivot = work[col][col]
        if pivot != 1:
            work[col] = [value / pivot for value in work[col]]
            record(f"R{col + 1} <- R{col + 1} / {pivot}")
        for row in range(n):
            if row == col:
                continue
            factor = work[row][col]
            if factor != 0:
                work[row] = [x - factor * y
                             for x, y in zip(work[row], work[col])]
                record(f"R{row + 1} <- R{row + 1} - ({factor}) R{col + 1}")
    return [row[n:] for row in work], trace


def multiply(left, right):
    return [[sum(x * y for x, y in zip(row, column))
             for column in zip(*right)] for row in left]


def show(matrix):
    for row in matrix:
        print(" ".join(str(value) for value in row))


if __name__ == "__main__":
    cases = {
        "regular": [[1, 2, 0], [0, 1, 3], [2, 0, 1]],
        "swap": [[0, 1, 0], [1, 0, 0], [0, 0, 1]],
        "singular": [[1, 2, 3], [2, 4, 6], [0, 1, 1]],
        "nonsquare": [[1, 2, 3], [4, 5, 6]],
    }
    name = sys.argv[1] if len(sys.argv) > 1 else "regular"
    if name not in cases:
        print("choose regular, swap, singular, or nonsquare")
        raise SystemExit(2)
    source = cases[name]
    try:
        inverse, trace = inverse_fraction(source)
    except (ValueError, TypeError) as error:
        print("failure:", error)
        raise SystemExit(2)
    for step, augmented in trace:
        print(step)
        show(augmented)
    print("inverse")
    show(inverse)
    identity = [[int(i == j) for j in range(len(source))]
                for i in range(len(source))]
    print("A * inverse == I:", multiply(source, inverse) == identity)
    print("inverse * A == I:", multiply(inverse, source) == identity)

기본 실행은 위 시작 표와 6개 행연산을 출력하며 마지막 역행렬은 N/13, 두 검산 줄은 모두 True여야 합니다. python inverse_fraction.py swap은 첫 두 행 교환 뒤 P를 역행렬로 얻고 역시 두 검산이 True입니다. python inverse_fraction.py singular은 failure: no nonzero pivot in column 3; singular을 출력하고 종료 코드 2로 끝납니다. python inverse_fraction.py nonsquare은 정사각형 입력이 아니라는 실패를 출력합니다. 실패 입력에서 0으로 나누거나 결과를 억지로 만들지 않습니다.

실습 파일은 저장소의 docs/cs-textbooks/discrete-math-examples/inverse_fraction.py에도 둡니다. 입력 행렬은 복사해서 사용하므로 함수 호출이 원본 리스트를 바꾸지 않습니다. 큰 행렬에서도 같은 알고리즘을 사용할 수 있지만 여인수 재귀 계산이나 여러 입력의 실행 성공을 일반 정리의 증명으로 세지 않습니다.

스스로 풀어보기

문제 1. x+2y=5, 3x+4y=11을 소거로 풀고 검산하세요.

풀이: 둘째 식에서 첫째의 3배를 빼면 −2y=−4라 y=2입니다. 첫째에 넣으면 x=1입니다. 대입 결과는 1+4=5, 3+8=11입니다. 해가 (1,2)이므로 좌표의 순서도 유지합니다.

문제 2. x−y=1, 2x−2y=2의 해 개수를 구하고 전체 해를 적으세요.

힌트: 두 식이 독립된 조건인지 확인합니다.

풀이: 둘째는 첫째의 2배라 한 조건뿐입니다. y=t를 임의의 실수로 잡아 x=t+1이라 하면 모든 식을 만족합니다. 무한해이며 'x=1,y=0' 하나만 적으면 전체 해집합을 다루지 못합니다.

복습은 피벗 계산보다 먼저 어떤 행연산을 사용했는지 적는 것부터 시작합니다. OpenStax의 역행렬 설명에서 정의와 증강행렬 방법, MIT Strang 강의의 여인수 공식에서 전치가 있는 일반식을 추가 확인할 수 있습니다.