크라메르 공식

선형대수학 Linear Algebra
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	<colbgcolor=#006ab8> 기본 대상		일차함수 · 벡터 · 행렬 · 선형 변환
대수적 구조		가군(모듈) · 벡터 공간 · 내적 공간 · 노름 공간
선형 연산자	<colbgcolor=#006ab8> 기본 개념	연립방정식( 1차 · 2차) · 행렬곱 · 단위행렬 · 역행렬과 크라메르 공식 · 가역행렬 · 전치행렬 · 행렬식( 라플라스 전개) · 주대각합
	선형 시스템	기본행연산과 기본행렬 · 가우스-조르당 소거법 · 행사다리꼴 · 행렬표현 · 라그랑주 보간법
	주요 정리	선형대수학의 기본정리 · 차원 정리 · 가역행렬의 기본정리 · 스펙트럼 정리
	기타	제곱근행렬 · 멱등행렬 · 멱영행렬 · 에르미트 행렬 · 야코비 행렬 · 방데르몽드 행렬 · 아다마르 행렬 변환 · 노름(수학)
벡터공간의 분해		상사 · 고유치 문제 · 케일리-해밀턴 정리 · 대각화( 대각행렬) · 삼각화 · 조르당 분해
벡터의 연산		노름 · 거리함수 · 내적 · 외적( 신발끈 공식) · 다중선형형식 · ∇ · 크로네커 델타
내적공간		그람-슈미트 과정 · 수반 연산자( 에르미트 내적)
다중선형대수		텐서 · 텐서곱 · 레비치비타 기호	}}}}}}}}}

1. 개요2. 응용

2.1. 역행렬 구하기

2.1.1. 개념 일반화2.1.2. 문제점

2.2. 예제

Règle de Cramer

1. 개요

행렬식을 이용하여 연립방정식의 해를 구하는 공식이다. 가브리엘 크라메르(Gabriel Cramer,1704-1752)가 출판한 《대수 곡선 해석 개론》(Introduction à l'Analyse des lignes Courbes algébriques, 1750)에서 소개가 되어 그의 이름이 붙었으나, 방정식의 개수가 2, 3개일 경우에 대한 공식을 콜린 매클로린(Colin Maclaurin)이 2년 먼저 발표한 바 있으며, 칼 보이어(Carl B. Boyer), 브루스 헤드먼(Bruce A. Hedman) 등에 의하면 그가 크라메르보다 30년 정도 먼저 발견했다고도 알려져 있다. 사실 매클로린도 방정식의 개수가 4개 이상일 경우에 대한 일반화를 시도하기도 했으나 결정적으로 부호를 정하는 방법을 찾지 못해 공식 도출 단계에 이르지는 못했다.

[math(n\times n)] 행렬 [math(A)]와 [math(n)]차원 열벡터 [math(\mathbf b=\begin{pmatrix} b_1 \\ \vdots \\ \vdots \\ b_n \end{pmatrix})]가 있다고 하자. 이때 [math(n)]차원 열벡터 [math(\mathbf x = \begin{pmatrix} x_1 \\ \vdots \\ \vdots \\ x_n \end{pmatrix})]가 다음과 같은 연립방정식

[math(A\mathbf x = \mathbf b)]

의 해라면

[math(x_i \det A = \det A_i)]

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

[math(x_i = \dfrac{\det A_i}{\det A})]

이다.

2. 응용

2.1. 역행렬 구하기

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

[math(A_{i=\mathbf e_j} = \begin{pmatrix}
a_{11} & \cdots & 0 & \cdots & a_{1n} \\
a_{21} & \cdots & 0 & \cdots & a_{2n} \\
\vdots & \ddots & \vdots & & \vdots \\
a_{j1} & \cdots & 1 & \cdots & a_{jn} \\
\vdots & & \vdots & \ddots & \vdots \\
a_{n1} & \cdots & 0 & \cdots & a_{nn}
\end{pmatrix})]

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

[math(\alpha_{ij} \det A = C_{ji})]

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

2.1.1. 개념 일반화

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

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

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

역행렬

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

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

2.1.2. 문제점

행렬식의 값이 작으면 부동 소수점 연산의 정확도 한계와 나누기 연산 때문에 오차가 매우 커지고, 결과적으로 수치적 안정성(numerical stability)이 쓰레기인 알고리즘이라 제대로 된 소프트웨어라면 이 방식을 사용하지 않는다.

... 크라머 공식[1]이 유용해 보이지만 실제로는 그렇지 않다. [math(n)]개의 미지수와 [math(n)]개의 일차방정식으로 이루어진 연립일차방정식을 풀기 위해, [math(n×n)] 행렬의 행렬식을 [math(n+1)]번 계산해야 하기 때문이다. 3.4절에서 다룬 가우스 소거법과 비교하면 크라머 공식은 계산의 양이 너무 많아서 결코 효과적이지 않다. 실제로 크라머 공식은 계산에 도움이 되지 않지만, 이론적이고 심미적인 가치를 지닌 공식이다.

프리드버그 외 2인 지음, 한빛수학교재연구소 번역, 프리드버그 선형대수학 5판(최초 번역판), 한빛아카데미, p. 251

크라메르 공식은 수학적으론 우아하지만 방정식을 수치적으로 계산하는 측면에서는 아무 짝에도 쓸모 없는 알고리즘이란 평가를 받는다. 손으로 알고리즘을 적용하는 것은 일일이 행렬식을 반복적으로 구해줘야 하기 때문에 계산량이 많아 부적절하고, 그렇다고 컴퓨터로 돌리기에는 정확도가 개판이기 때문이다. 이 때문에 선형대수학 교재의 저자로 유명한 MIT 교수 길버트 스트랭은 "크라메르 공식으로 방정식을 푸는 것은 미친 짓이다."라고 평하기도 했다. 역행렬은 첨가행렬 [math([A | I])]을 만든 뒤 기본행연산을 이용해 [math([I | A^{-1}])]로 계산하면 편리하다.

2.2. 예제

삼차정사각행렬 [math(A)]가

[math(A = \begin{bmatrix} 1 & 2 & 0 \\ 3 & 2 & 1 \\ 2 & 1 & 0 \end{bmatrix})]

일 때, [math(A)]의 역행렬 [math(A^{-1})]을 구하시오.

[math(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})]

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

[math(\displaystyle \det A = \sum_{i=1}^n a_{ij}C_{ij})]

로 계산할 수 있으며 마침 위에 여인수들이 계산되어있으므로 아무 열이나 골라서 사용하면 된다. 0이 최대한 많은 열을 고르는 게 계산하기 좋다. 여기선 간단히 세번째 열([math(j=3)])을 골랐다.

[math(\det A = a_{13}C_{13} + a_{23}C_{23} + a_{33}C_{33} = 0\cdot\left(-1\right) + 1\cdot3 + 0\cdot\left(-4\right) = 3)]

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

[math(A^{-1} = \dfrac13 \begin{bmatrix} -1 & 0 & \ \;\ 2 \\ \ \;\ 2 & 0 & -1 \\ -1 & 3 & -4 \end{bmatrix})]

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

[math(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)]

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

[1] 출처에 이렇게 적혀 있다.

크라메르 공식

1. 개요

2. 응용

2.1. 역행렬 구하기

2.1.1. 개념 일반화

2.1.2. 문제점

2.2. 예제

분류