크라메르 공식(Cramer's Rule) 혹은 크래머의 공식/법칙은 유일한 해를 가진 연립 일차방정식 [math]\displaystyle{ A\mathbf{x}=\mathbf{b} }[/math]의 해를 행렬식의 비를 이용해서 구하는 공식이다. 스위스 제네바 출신 수학자 가브리엘 크라메르(Gabriel Cramer, 1704-1752)의 이름을 딴 공식이다.
설명[편집 | 원본 편집]
n개의 미지수를 가진 n개의 일차연립방정식 [math]\displaystyle{ Ax=b }[/math]가 있다고 하자. 이 때 [math]\displaystyle{ x=(x_1,\cdots ,x_n)^T }[/math]라 두자. 이제 [math]\displaystyle{ B_k }[/math]를 A에서 k번째 열벡터를 b로 바꾼 행렬이라고 두면,
- [math]\displaystyle{ x_k \det(A) = \det{B_k} }[/math]
가 성립하는데, 이를 크래머의 법칙이라 부른다. 여기서 특히 A가 가역행렬이면, 위 식은
- [math]\displaystyle{ x_k= \frac{\det{B_k}}{\det{A}} }[/math]
로 나타난다. 따라서 크래머의 법칙은 연립방정식의 해가 어떻게 나오는지 명시적으로 알려준다. 허나 행렬식 계산이 무지 어렵기 때문에 별 쓸모는 없다.
크래머의 법칙을 쓰면 역행렬의 성분이 어떻게 나타나는지도 정확히 알 수 있다. 가령, A의 역행렬의 (i,j)번째 성분 [math]\displaystyle{ c_{i,j} }[/math]를 알고 싶다고 하자. 그러면 아래 연립방정식
- [math]\displaystyle{ A\begin{bmatrix} c_{1,j} \\ \vdots \\ c_{n,j} \end{bmatrix} = \mathbf{e}_j }[/math]
를 풀면 된다. 그런데 크래머의 법칙에 따르면 이 방정식의 해는
- [math]\displaystyle{ c_{i,j} \det{A}= \det \begin{pmatrix} a_{1,1} & \cdots & 0 & \cdots & a_{1,n} \\ \vdots & \ddots & \vdots & \ddots & \vdots\\ a_{j,1} & \cdots & 1 & \cdots & a_{j,n} \\ \vdots & \ddots & \vdots & \ddots & \vdots\\ a_{n,1} & \cdots & 0 & \cdots & a_{n,n} \\ \end{pmatrix} }[/math]
가 되는데, 위 행렬식은 계산해보면 [math]\displaystyle{ (-1)^{i+j}\det(A(j,i)) }[/math]가 된다! 따라서
- [math]\displaystyle{ c_{i,j} =\frac{(-1)^{i+j}\det(A(j,i))}{\det{A}} }[/math]
를 얻는다.
효율성[편집 | 원본 편집]
A가 n×n행렬일 때 [math]\displaystyle{ A\mathbf{x}=\mathbf{b} }[/math]에 대해서 곱셈 횟수는 대략 [math]\displaystyle{ \mathcal{O}(n^3) }[/math] A의 행렬식을 구하기 위해서는 A를 사다리꼴 행렬(Row Echelon Form)으로 만드는 과정이 가장 효율적이다. 사다리꼴 행렬로 만들 때 1행부터 n행까지 각각 상수 [math]\displaystyle{ a_1, \cdots, a_n }[/math]만큼 곱해서 0이 아닌 모든 A의 1열의 숫자를 모두 1로 맞추어준다. 이 때 위한 상수를 곱하는 횟수는 최대 행렬 A의 전체의 원소의 개수인 n2이다. 한편 A의 각 행에 곱해준 상수 [math]\displaystyle{ a_1, \cdots, a_n }[/math]의 역수들을 곱해서 새로운 상수 [math]\displaystyle{ b_1 }[/math]을 구한다. 그 다음에 각 행에서 1행의 숫자를 빼주어서 1행 1열을 제외한 다른 숫자는 모두 0으로 맞추어줘도 행렬식은 변하지 않으니 1행 1열을 제외한 나머지 1열의 원소가 모두 0이면서 행렬식이 [math]\displaystyle{ |A'|=a_1 \cdots a_n \cdot |A| }[/math]안 행렬 A'을 만들 수 있다. 이제 이 변형된 행렬 A'에 대해서 2X2 부터 nXn까지 원소부분 (n-1)X(n-1) 행렬에 대해서도 반복적으로 해준다. A에서 A'을 만들 때 숫자를 n2+n만큼 곱한 것을 확인할 수 있고, 마찬가지로 상대각행렬(upper triangluar matrix)로 만들 때 최대 [math]\displaystyle{ \sum_i=1^n (i^2 + i) = \frac{n(n+1)(n+2)}{3} }[/math]만큼의 숫자를 곱해야 하는 것을 확인할 수 있다.
예시 : 3X3 행렬에서 역행렬 구하기
[math]\displaystyle{ \mathrm{det}A=\begin{vmatrix}{1} & {2} & 3 \\ 2& 3& 5 \\ -1&0&2 \end{vmatrix} = 1\cdot 2\cdot (-1) \begin{vmatrix}1& 2& 3 \\ 1& 3/2& 5/2 \\ 1& 0& -2 \end{vmatrix} }[/math]
[math]\displaystyle{ 1\cdot 2\cdot (-1) \begin{vmatrix}1& 2& 3 \\ 0& -1/2& 1/2 \\ 0& -2& -5 \end{vmatrix}=(-2)\cdot (-1/2)\cdot 1\cdot 2\cdot (-1) \begin{vmatrix}1& 2& 3 \\ 0& 1& 1 \\ 0& 1& 5/2 \end{vmatrix} }[/math]
[math]\displaystyle{ = (-2)\cdot (-1/2)\cdot 1\cdot 2\cdot (-1) \begin{vmatrix}1& 2& 3 \\ 0& 1& 1 \\ 0& 0& 3/2 \end{vmatrix} = (3/2)\cdot(-2)\cdot(-1/2) \cdot 1 \cdot 2 \cdot (-1) =-3 }[/math]
크라메르 공식은 A와 i행(i=1,...n)을 b로 대체한 행렬 Ai의 행렬식을 구해야 하기 때문에 거기에 (n+1)을 곱한 횟수. 다시 말해 [math]\displaystyle{ \frac{n^4}{3} + \mathcal{O}(n^3) }[/math]만큼의 곱셈을 해주어야 한다.
반면에 가우스 소거법은 첨가행렬(augmented matrix) [math]\displaystyle{ [A|\mathbf{b}] }[/math]에 대해 사다리꼴 행렬로 만든 뒤 뒤쪽부터 치환(Back Substitution)하면서 해를 구하는 방식이다. 치환하면서 해를 구할 때는 대략 [math]\displaystyle{ \mathcal{O}(n^2) }[/math]만큼의 곱셈만 소모되므로 첨가행렬의 사다리꼴로 만드는데 들어가는 숫자 곱셈횟수인 대략 [math]\displaystyle{ \frac{n^3}{3} + \mathcal{O}(n^2) }[/math] 만큼의 연산만 하면 된다. 즉 가우스 소거법에 비해 효율이 좋지 않다.