크라메르 공식

Règle de Cramer

1. 개요

---

행렬식을 이용하여 연립방정식의 해를 구하는 공식이다. 가브리엘 크라메르가 출판한 《대수 곡선 해석 개론》(Introduction à l'Analyse des lignes Courbes algébriques, 1750)에서 소개가 되어 그의 이름이 붙었으나, 방정식의 개수가 2, 3개일 경우에 대한 공식을 콜린 매클로린이 2년 먼저 발표한 바 있으며, 칼 보이어(Carl B. Boyer), 브루스 헤드먼(Bruce A. Hedman) 등에 의하면 그가 크라메르보다 30년 정도 먼저 발견했다고도 알려져 있다. 사실 매클로린도 방정식의 개수가 4개 이상일 경우에 대한 일반화를 시도하기도 했으나 결정적으로 부호를 정하는 방법을 찾지 못해 공식 도출 단계에 이르지는 못했다.
$$n\times n$$ 행렬 $$A$$와 $$n$$차원 열벡터 $$\mathbf b=\begin{pmatrix} b_1 \\ \vdots \\ \vdots \\ b_n \end{pmatrix}$$가 있다고 하자. 이때 $$n$$차원 열벡터 $$\mathbf x = \begin{pmatrix} x_1 \\ \vdots \\ \vdots \\ x_n \end{pmatrix}$$가 다음과 같은 연립방정식

$$A\mathbf x = \mathbf b$$

의 해라면

$$x_i \det A = \det A_i$$

가 성립한다. 여기서 $$A_i$$는 $$A$$의 $$i$$번째 열을 $$\mathbf b$$로 교체한 행렬이다. $$\det A \ne 0$$이라면

$$x_i = \dfrac{\det A_i}{\det A}$$

이다.

2. 응용

---

2.1. 역행렬 구하기

---

$$\mathbf b$$가 단위행렬의 $$j$$번째 열벡터 $$\mathbf e_j$$이고 $$\mathbf x = \boldsymbol\alpha_j$$라 놓으면
$$A\boldsymbol\alpha_j = \mathbf e_j$$
이며 $$\boldsymbol\alpha_j$$는 곧 $$A$$의 역행렬 $$A^{-1}$$의 $$j$$번째 열벡터임을 알 수 있다. 크라메르의 공식에 따라 $$A$$의 $$i$$번째 열을 $$\mathbf e_j$$로 교체하면서 계산해주면 $$\boldsymbol\alpha_j$$의 $$i$$번째 행의 성분, 즉 $$\alpha_{ij}$$가 얻어지는데, $$\det A_i$$를 계산할 때 $$i$$번째 열에 주목해서 라플라스 전개(여인수 전개)를 적용하면 소행렬식과 여인수를 이용하여 역행렬을 구하는 방법이 도출된다. 즉

$$A_{i=\mathbf e_j} = \begin{pmatrix} a_{11} & \cdots\cdots & 0 & \cdots\cdots & a_{1n} \\ a_{21} & \cdots\cdots & 0 & \cdots\cdots & a_{2n} \\ \vdots & \ddots\qquad\,\ & \vdots & & \vdots \\ \vdots & \qquad\,\ \ddots & \vdots & & \vdots \\ a_{j1} & \cdots\cdots & 1 & \cdots\cdots & a_{jn} \\ \vdots & & \vdots & \ddots\qquad\,\ & \vdots \\ \vdots & & \vdots & \qquad\,\ \ddots & \vdots \\ a_{n1} & \cdots\cdots & 0 & \cdots\cdots & a_{nn} \end{pmatrix}$$

에서 $$\mathbf e_j$$로 치환된 $$i$$번째 열벡터에 주목하여 라플라스 전개를 적용하면 $$j$$행 $$i$$열을 제거한 $$(n-1)$$차 소행렬식 $$M_{ji}$$에 $$\left(-1\right)^{j+i}$$를 곱한 여인수 $$C_{ji}$$가 얻어지고 이 값은 $$A^{-1}$$의 $$j$$번째 열벡터의 $$i$$행 성분 $$\alpha_{ij}$$에 $$\det A$$를 곱한 값

$$\alpha_{ij} \det A = C_{ji}$$

이다. 행렬의 '''열'''을 하나씩 교체하면서 행렬식을 구해준 결과가 역행렬 열벡터의 '''행''' 성분에 대응되기 때문에 후술할 전치행렬이 필요한 이유가 여기서 나온다.

2.1.1. 개념 일반화

---

• 소행렬식

$$n$$차 정사각행렬 $$A$$에서 $$i$$행 $$j$$열을 제거하여 얻어진 $$(n-1)$$차 정사각행렬의 행렬식을 $$(i,\ j)$$ 소행렬식(minor)이라고 하며 $$M_{ij}$$로 나타낸다. 행렬이랑 비슷한 표기 방식을 쓰기에 행렬로 오인할 수 있으나 $$M_{ij}$$는 엄연히 '행렬식'의 값이다.

• 여인수

$$M_{ij}$$에 $$\left(-1\right)^{i+j}$$를 곱한 값 $$\left(-1\right)^{i+j}M_{ij}$$를 $$(i,\ j)$$ 여인수(cofactor)라고 하며 $$C_{ij}$$로 나타낸다. $$C_{ij}$$를 성분으로 갖는 행렬을 여인수 행렬이라고 하며 $$C$$로 나타낸다.

• 수반행렬

여인수 행렬에 전치행렬을 적용한 $$C^{\mathrm T}$$를 수반행렬(adjugate matrix)이라고 하며 $$\mathrm{adj}\left(A\right)$$로 나타내기도 한다.
한편 $$A^* \,{\sf or}\, A^{\dag}$$로 표기되는 에르미트 수반행렬(Hermitian adjoint)을 짧게 수반행렬 혹은 수반 연산자라고 부르기 때문에 혼동을 피하기 위해 본 용어를 고전적 수반행렬(classical adjoint)이라 나타내기도 하며, 교재에 따라 딸림행렬로 번역되기도 한다. 대한수학회 용어집에서는 '수반행렬', '딸림행렬' 둘 다 공식 용어로 채택하고 있다.

• 역행렬

$$A^{-1} = \dfrac1{\det A}C^{\mathrm T} = \dfrac1{\det A}\mathrm{adj}\left(A\right)$$ (단, $$A$$는 정사각행렬이며 $$\det A \ne 0$$)

즉 수반행렬을 행렬식으로 나누면 된다. 자세한 건 역행렬 문서 참조.

2.1.2. 문제점

---

행렬식의 값이 작으면 부동 소수점 연산의 정확도 한계와 나누기 연산 때문에 오차가 매우 커지고, 결과적으로 수치적 안정성(numerical stability)이 쓰레기인 알고리즘이라 제대로 된 소프트웨어라면 이 방식을 사용하지 않는다.
크라메르 공식은 수학적으론 우아하지만 방정식을 수치적으로 계산하는 측면에서는 아무 짝에도 쓸모 없는 알고리즘이란 평가를 받는다. 손으로 알고리즘을 적용하는 것은 일일이 행렬식을 반복적으로 구해줘야 하기 때문에 계산량이 많아 부적절하고, 그렇다고 컴퓨터로 돌리기에는 정확도가 개판이기 때문이다. 이 때문에 선형대수학 교재의 저자로 유명한 MIT 교수 길버트 스트랭은 "크라메르 공식으로 방정식을 푸는 것은 미친짓이다."라고 평하기도 했다. 역행렬은 elementary row operation으로 계산하면 편리하다.

2.2. 예제

---

삼차정사각행렬 $$A$$가 $$A = \begin{bmatrix} 1 & 2 & 0 \\ 3 & 2 & 1 \\ 2 & 1 & 0 \end{bmatrix}$$ 일 때, $$A$$의 역행렬 $$A^{-1}$$을 구하시오.

$$A^{-1}$$을 구하기 위해서는 여인수 행렬을 알아야 한다.

[math(C_{11} = \left(-1\right)^{1+1}M_{11} = \:\ \:\ \begin{vmatrix} 2 & 1 \\ 1 & 0 \end{vmatrix} = 2\cdot0 - 1\cdot1 = -1 \\ C_{12} = \left(-1\right)^{1+2}M_{12} = -\begin{vmatrix} 3 & 1 \\ 2 & 0 \end{vmatrix} = -\left(3\cdot0 - 1\cdot2\right) = 2 \\ C_{13} = \left(-1\right)^{1+3}M_{13} = \:\ \:\ \begin{vmatrix} 3 & 2 \\ 2 & 1 \end{vmatrix} = 3\cdot1 - 2\cdot2 = -1 \\ \ \\ C_{21} = \left(-1\right)^{2+1}M_{21} = -\begin{vmatrix} 2 & 0 \\ 1 & 0 \end{vmatrix} = -\left(2\cdot0 - 0\cdot1\right) = 0 \\ C_{22} = \left(-1\right)^{2+2}M_{22} = \:\ \:\ \begin{vmatrix} 1 & 0 \\ 2 & 0 \end{vmatrix} = 1\cdot0 - 0\cdot2 = 0 \\ C_{23} = \left(-1\right)^{2+3}M_{23} = -\begin{vmatrix} 1 & 2 \\ 2 & 1 \end{vmatrix} = -\left(1\cdot1 - 2\cdot2\right) = 3 \\ \ \\ C_{31} = \left(-1\right)^{3+1}M_{31} = \:\ \:\ \begin{vmatrix} 2 & 0 \\ 2 & 1 \end{vmatrix} = 2\cdot1 - 0\cdot2 = 2 \\ C_{32} = \left(-1\right)^{3+2}M_{32} = -\begin{vmatrix} 1 & 0 \\ 3 & 1 \end{vmatrix} = -\left(1\cdot1 - 0\cdot3\right) = -1 \\ C_{33} = \left(-1\right)^{3+3}M_{33} = \:\ \:\ \begin{vmatrix} 1 & 2 \\ 3 & 2 \end{vmatrix} = 1\cdot2 - 2\cdot3 = -4 \\ \ \\ \therefore C = \begin{bmatrix} -1 & \ \;\ 2 & -1 \\ \ \;\ 0 & \ \;\ 0 & \ \;\ 3 \\ \ \;\ 2 & -1 & -4 \end{bmatrix})]

행렬식은 라플라스 전개를 이용해서

$$\displaystyle \det A = \sum_{i=1}^n a_{ij}C_{ij}$$

로 계산할 수 있으며 마침 위에 여인수들이 계산되어있으므로 아무 열이나 골라서 사용하면 된다. 여기선 간단히 첫번째 열($$j=1$$)을 골랐다.

$$\det A = a_{11}C_{11} + a_{21}C_{21} + a_{31}C_{31} = 1\cdot\left(-1\right) + 3\cdot0 + 2\cdot2 = 3$$

여인수 행렬을 전치하고 행렬식으로 나누면 계산 끝.

$$A^{-1} = \dfrac13 \begin{bmatrix} -1 & 0 & \ \;\ 2 \\ \ \;\ 2 & 0 & -1 \\ -1 & 3 & -4 \end{bmatrix}$$

원래 행렬과 곱해서 단위행렬이 나오는지 확인도 해보자.

$$A^{-1}A = \dfrac13 \begin{bmatrix} -1 & 0 & \ \;\ 2 \\ \ \;\ 2 & 0 & -1 \\ -1 & 3 & -4 \end{bmatrix} \begin{bmatrix} 1 & 2 & 0 \\ 3 & 2 & 1 \\ 2 & 1 & 0 \end{bmatrix} = \dfrac13 \begin{bmatrix} 3 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 3 \end{bmatrix} = I_3$$

여기선 $$3$$차 정사각행렬이라 여인수 행렬의 각 성분을 비교적 쉽게 계산했지만, 차수가 커지면 행렬식 계산량이 겉잡을 수 없이 불어나게 된다. 어쨌든 아무리 차수가 커도 계산이 가능한 것은 사실이다.
내용 자체는 어려운 편이 아니라 프로그래밍하기는 쉽다. 보통 $$n=5$$ 이상은 프로그램을 만드는 게 더 빠를 수 있으나 상술한대로 수치에 따라서는 정확도가 떨어지고 시간이 오래 걸릴 수 있다.