크라메르 법칙

수치해석 마지막 수정: 2026-08-16 04:51:36

1. 개요[편집]

크라메르 법칙 Cramer's rule
진술	x_i = det(A_i) / det(A)
A_i	A 의 i 열을 b 로 갈아끼운 행렬
명명	Gabriel Cramer (1750). 매클로린·라이프니츠가 선행
비용	라플라스 전개 O(n!) · LU 기반 O(n⁴)
대조군	가우스 소거법 (2/3)n³, 실무적으로 후진 안정
실제 용도	기호계산 · 정확 정수 산술 · 이론적 유도 · n ≤ 3

모든 선형대수 강의가 가르치고, 모든 수치해석 강의가 쓰지 말라고 하는 그 공식. 두 강의 다 옳다.

크라메르 법칙(Cramer’s rule)은 정칙행렬 $A$ 에 대한 선형계 $A\mathbf{x} = \mathbf{b}$ 의 해를 성분마다 행렬식의 비로 주는 닫힌 공식이다.

x_i = \frac{\det(A_i)}{\det(A)}, \qquad A_i = \bigl[\,\mathbf{a}_1,\ \dots,\ \mathbf{a}_{i-1},\ \mathbf{b},\ \mathbf{a}_{i+1},\ \dots,\ \mathbf{a}_n\,\bigr]

즉 $A$ 의 $i$ 번째 열만 우변 $\mathbf{b}$ 로 갈아끼운 행렬의 행렬식을 원래 행렬식으로 나눈다. 가브리엘 크라메르가 1750년 대수곡선 저서의 부록에서 일반 $n$ 에 대해 적으면서 이름이 붙었지만, 매클로린이 20년 앞서 2·3 미지수 경우를 써 두었고 라이프니츠는 1693년 편지에서 이미 행렬식 비슷한 것을 다뤘다.¹

이 문서의 결론을 먼저 말해 두면 이렇다. 크라메르 법칙은 알고리즘이 아니라 공식이다. 부동소수점으로 큰 계를 푸는 데 쓰면 느리고 불안정하다. 그럼에도 죽지 않는 이유는 이 공식이 해를 계수의 유리함수로 명시적으로 써 준다는 데 있고, 그게 필요한 자리는 생각보다 많다. 수반행렬 문서가 이 공식이 나오는 항등식 쪽을 다루므로, 여기서는 공식 자체와 그 쓸모·못 쓸모를 본다.

2. 두 줄 증명[편집]

수반행렬을 거치지 않는 가장 짧은 증명이 있다. 단위행렬의 $i$ 번째 열을 해 $\mathbf{x}$ 로 갈아끼운 행렬

X_i = \bigl[\,\mathbf{e}_1,\ \dots,\ \mathbf{e}_{i-1},\ \mathbf{x},\ \mathbf{e}_{i+1},\ \dots,\ \mathbf{e}_n\,\bigr]

를 잡는다. 이 행렬의 $i$ 번째 행은 $x_i$ 하나만 남으므로 그 행으로 전개하면 $\det(X_i) = x_i$ 다. 한편 $A$ 를 왼쪽에서 곱하면 $A\mathbf{e}_j = \mathbf{a}_j$ 이고 $A\mathbf{x} = \mathbf{b}$ 이므로 $A X_i = A_i$ 다. 행렬식의 곱셈성을 쓰면

\det(A)\,x_i = \det(A)\det(X_i) = \det(A X_i) = \det(A_i)

로 끝난다. 여인수 전개도, 수반행렬도 필요 없다.

물론 고전적 유도도 알아 둘 만하다. $A^{-1} = \operatorname{adj}(A)/\det(A)$ 에서 $\mathbf{x} = \operatorname{adj}(A)\mathbf{b}/\det(A)$ 이고, $(\operatorname{adj}(A)\mathbf{b})_i = \sum_j C_{ji}b_j$ 는 정확히 $A_i$ 를 $i$ 열로 여인수 전개한 것이다. 두 유도가 말해 주는 바가 다르다 — 앞의 것은 나눗셈이 한 번뿐임을, 뒤의 것은 이 공식이 임의의 가환환 위에서 성립함을 보여 준다.

3. 기하 — 부피비로 읽기[편집]

$\det(A)$ 는 열벡터들이 만드는 평행육면체의 부호 있는 부피다. 그러면 크라메르 법칙은 다음 문장이 된다.

$x_i$ 는 ” $i$ 번째 모서리를 $\mathbf{b}$ 로 갈아끼웠을 때 부피가 몇 배가 되는가”이다.

증명도 그림 그대로다. $\mathbf{b} = \sum_j x_j \mathbf{a}_j$ 를 $A_i$ 의 $i$ 열에 대입하고 행렬식의 다중선형성을 쓰면, $j \ne i$ 인 항은 같은 열이 두 번 들어가 전부 0이 되고 $x_i \det(A)$ 만 남는다. 2차원이면 “평행사변형 하나의 한 변을 갈아끼웠을 때 넓이 비”, 3차원이면 부피 비다.

이 관점은 실제로 쓸모가 있다. 삼각형·사면체의 무게중심 좌표(barycentric coordinate)가 정확히 이 부피비이고, 들로네 삼각분할의 외접원 판정이나 점의 포함 판정도 결국 작은 행렬식의 부호를 보는 일이다. 값이 아니라 부호만 필요하다면 상쇄 걱정이 크게 줄고, 필요하면 정확 산술로 부호를 확정하는 적응 정밀도 술어(predicate)를 쓴다. 기하 알고리즘이 크라메르식 표현과 잘 지내는 이유다.

4. 비용 — 왜 안 쓰는가 (1)[편집]

$n+1$ 개의 행렬식을 구해야 한다. 여기서 첫 번째 사망 선고가 나온다.

여인수(라플라스) 전개로 재귀 계산하면 행렬식 하나가 $O(n!)$ 이다. $n=20$ 이면 순열이 $2.4\times10^{18}$ 개라 논외.
LU 분해로 영리하게 해도 각 행렬식이 $O(n^3)$ 이고 $A_i$ 는 $A$ 와 열 하나가 다르므로 인수분해를 공유할 수 없다. 총 $O(n^4)$ .
가우스 소거법 한 번이면 $\tfrac23 n^3$ 에 끝난다.

즉 크라메르는 최선을 다해도 표준 방법보다 $n$ 배 비싸다. “행렬식 하나만 다시 계산하면 되지 않나”라는 절약 시도는 재밌게도 자기 자신으로 되돌아온다.²

덤으로 오버플로 문제도 있다. 원소가 $O(1)$ 인 $30\times30$ 행렬만 되어도 행렬식이 쉽게 $10^{20}$ 을 넘나든다. 두 개의 거대한 수를 나눠 $O(1)$ 크기의 답을 얻는 구조라, 지수 범위를 벗어나면 $\infty/\infty$ 가 나온다.

5. 안정성 — 왜 안 쓰는가 (2)[편집]

더 나쁜 문제는 정확도다. 크라메르 법칙은 후진 안정하지 않다. 계산된 해 $\hat{\mathbf{x}}$ 가 원래 문제를 조금 흔든 문제 $(A+\Delta A)\hat{\mathbf{x}} = \mathbf{b}+\Delta\mathbf{b}$ 의 정확한 해라고 말할 수 없다는 뜻이며, 하이엄의 Accuracy and Stability of Numerical Algorithms 는 이 사실을 $2\times2$ 예제 하나로 보여 준다. 잔차 $\lVert \mathbf{b} - A\hat{\mathbf{x}}\rVert$ 가 반올림 단위 수준으로 내려가지 않는 계수 조합이 존재한다.

원인은 구조적이다. $\det(A)$ 와 $\det(A_i)$ 는 각각 덧뺄셈으로 상쇄를 겪은 뒤 서로 나누어진다. 두 번의 상쇄가 독립적으로 유효숫자를 갉아먹는데, 나눗셈은 그 손실을 되돌려 주지 않는다. 반면 부분 피벗팅을 붙인 가우스 소거는 실무적으로 후진 안정하다 — 성장인자가 병적으로 커지는 인위적 반례를 빼면 잔차가 항상 작다.

여기서 정직하게 짚어야 할 것이 있다. 전진 오차, 즉 참해와의 차이는 같은 예제에서 꽤 작게 나온다. 그래서 “직접 돌려 봤는데 잘 맞던데요?”라는 반박이 영원히 재생산된다. 문제는 언제 맞고 언제 틀리는지 사전에 판별할 수 없다는 점이고, 수치해석에서 그건 그냥 틀린 것과 같다. 잔차를 못 믿으면 후진 오차 해석이라는 진단 도구 자체가 무력해지므로, 반복 개선(iterative refinement)이나 오차 추정 같은 후속 장치도 함께 죽는다.

단, $n$ 이 아주 작으면 이야기가 다르다. $2\times2$ · $3\times3$ 에서는 행렬식이 곱 몇 개의 합이라 상쇄가 일어날 기회 자체가 적고, 실무에서 관측되는 정확도가 충분하다. 그래픽스와 유한요소법 커널이 지금도 닫힌 형 $2\times2$ · $3\times3$ 풀이를 쓰는 이유가 이것이다 — 피벗 탐색 분기가 없어 파이프라인이 안 깨지고, 완전히 언롤되어 SIMD·GPU에 그대로 올라간다. 등매개변수 요소의 야코비안 처리가 대표 사례이며, 자세한 논의는 수반행렬 문서에 있다. 이건 크라메르의 복권이 아니라 ” $n$ 이 3이면 $n^4$ 과 $n^3$ 의 차이가 없다” 는 자명한 사실의 결과다.

6. 그래도 크라메르가 사는 곳[편집]

부동소수점 세계 밖으로 나가면 사정이 완전히 뒤집힌다. 반올림이 없으면 불안정성 논의가 통째로 사라지고, 남는 것은 비용뿐이기 때문이다.

기호계산. 컴퓨터 대수 시스템에서 계수가 수가 아니라 기호일 때, 해를 “행렬식 두 개의 비”로 표현하는 것 자체가 목적이 된다. 가우스 소거는 중간 식이 폭발적으로 커지지만 크라메르는 결과가 닫힌 유리식으로 나오고, 분모가 $\det(A)$ 하나라 특이해지는 조건( $\det A = 0$ )이 눈에 그대로 보인다.

정확 정수 산술. 정수 계수 계의 해를 유리수로 정확히 얻으려면 행렬식을 정수로 계산해야 한다. 순진하게 소거하면 분수가 생기고 분자·분모가 폭발하는데, 베어라이스(Bareiss) 분수 없는 소거는 실베스터 항등식을 이용해 매 단계 나눗셈이 항상 딱 떨어지도록 배치한다. 중간값이 모두 $A$ 의 소행렬식이라 정수로 남고, 크기는 아다마르 한계 $\lvert\det A\rvert \le \prod_j \lVert \mathbf{a}_j\rVert_2$ 로 억제된다. 연산 수는 $O(n^3)$ 이다. 정수 선형계를 정확히 풀 때의 표준 도구다.³

유한체와 암호. 유한체 위에서는 나눗셈이 정확하므로 상쇄도 반올림도 없다. 부호이론의 키 방정식처럼 차수가 작은 계에서는 행렬식으로 직접 푸는 서술이 표준이고, 비밀 분산이나 다항식 보간류 구성에서도 해를 행렬식 비로 적어 두는 것이 증명에 편하다.

이론적 유도와 민감도. 평형조건 $F(\mathbf{x},p)=0$ 을 파라미터로 미분하면 $J\,\partial\mathbf{x}/\partial p = -\partial F/\partial p$ 라는 선형계가 나오고, 크라메르로 풀면 각 민감도가 행렬식 비로 표현된다. 값을 몰라도 부호를 읽을 수 있는 경우가 많아 정성적 분석에 강하다. 민감도 해석·감도 함수에서 쓰는 논법이고, 회로 이론에서 절점 해석의 전달 임피던스가 “여인수 / 행렬식”으로 적히는 것(SPICE 가 내부에서 실제로 그렇게 풀지는 않는다), 상태공간 전달함수의 분모가 $\det(sI-A)$ 인 것도 같은 뿌리다.

매개변수 변화법. 2계 선형 미분방정식 $y'' + p y' + q y = g$ 의 특수해를 구할 때, 두 기본해 $y_1,y_2$ 에 대해

\begin{bmatrix} y_1 & y_2 \\ y_1' & y_2' \end{bmatrix} \begin{bmatrix} u_1' \\ u_2' \end{bmatrix} = \begin{bmatrix} 0 \\ g \end{bmatrix}

를 크라메르로 풀면 곧바로 $u_1' = -y_2 g/W$ , $u_2' = y_1 g/W$ 가 나온다. 분모의 $W$ 가 브론스키 행렬식이고, 그것이 0이 아니라는 조건이 곧 기본해계라는 조건이다. 교과서 공식의 그 이상한 부호 배치는 크라메르 법칙의 부호 그 자체다.

정수 최적화. 선형계획법의 기저해는 $\mathbf{x}_B = B^{-1}\mathbf{b}$ 이므로 성분마다 $\det(B_i)/\det(B)$ 다. 여기서 $A$ 가 전체 단모듈성을 가지면 모든 정칙 기저에서 $\det(B) = \pm 1$ 이고, $\mathbf{b}$ 가 정수면 모든 기저해가 자동으로 정수가 된다. 즉 완화 문제의 꼭짓점이 전부 정수점이라 정수계획법이 선형계획법으로 붕괴한다. 이 유명한 정리의 증명 한복판에 크라메르 법칙이 앉아 있다.

7. 정리[편집]

상황	크라메르를 쓰는가
$n \le 3$ , 부동소수점, 반복 호출	쓴다. 빠르고 충분히 정확하다
$n \gtrsim 4$ , 부동소수점	쓰지 않는다. 가우스 소거 또는 LU 분해
기호 계수	쓴다. 닫힌 유리식이 목적이다
정수·유한체 정확 산술	조건부. 베어라이스류 $O(n^3)$ 이 보통 더 낫다
이론적 표현·증명	쓴다. 이게 원래 용도다

한 줄로 줄이면 — 크라메르 법칙은 해가 계수에 어떻게 의존하는지 말해 주는 언어이지, 해를 구하는 절차가 아니다. 교과서가 이 공식을 3장에서 가르치는 것은 “역행렬이 존재한다”를 증명하기 위해서였지 “역행렬을 구하라”가 아니었다.

8. 관련 문서[편집]

크라메르 본인은 이 공식을 대수곡선이 주어진 점들을 지나도록 계수를 맞추는 문제, 즉 요즘 말로 보간과 근사 문제를 풀려고 썼다. 행렬 개념이 없던 시절이라 표기는 지금과 딴판이고, 부호 규칙을 말로 설명해 놓은 대목은 읽다 보면 인내심 테스트에 가깝다. 참고로 이름을 남긴 사람이 최초 발견자가 아니라는 것은 수학사에서 국룰이고, 이 현상 자체에 스티글러의 명명 법칙이라는 이름이 붙어 있다(물론 스티글러도 최초가 아니다). ↩
행렬식 보조정리로 $A_i = A + (\mathbf{b}-\mathbf{a}_i)\mathbf{e}_i^{\top}$ 를 계수 1 갱신으로 보면 $\det(A_i) = \det(A)\bigl(1 + \mathbf{e}_i^{\top}A^{-1}(\mathbf{b}-\mathbf{a}_i)\bigr) = \det(A)\,x_i$ 가 나온다. 즉 ” $A_i$ 의 행렬식만 싸게 갱신하자”는 아이디어는 계산해 보면 이미 $\mathbf{x}$ 를 알아야 성립하는 항등식으로 되돌아온다. 크라메르 법칙을 크라메르 법칙으로 가속하려는 시도의 최후. ↩
정수 행렬식의 역사에서 빼놓을 수 없는 물건이 도지슨 축약(Dodgson condensation)이다. 인접한 $2\times2$ 소행렬식을 반복해서 접어 나가는 방법인데, 만든 사람이 옥스퍼드의 수학 강사 찰스 도지슨 — 필명 루이스 캐럴이다. 내부 항목이 0이면 절차가 죽는다는 결함이 있어 실무용은 못 됐지만, 이상한 나라의 앨리스 저자가 행렬식 알고리즘도 남겼다는 사실은 꽤 자주 인용된다. ↩