Cramer's Rule

Cramer's Rule

Theorem 1. (Cramer's Rule) Let $Ax = b$ be a system of $n$ linear equations in $n$ unknowns, where $x = (x_1, ..., x_n)^t$.
If $\det(A) \neq 0$, then this system has a unique solution, and $$x_k = \frac{\det(M_k)}{\det(A)}, \forall k \in \{1, ..., n\},$$ where $M_k \in M_{n \times n}(F)$ obtained from $A$ by replacing column $k$ of $A$ by $b$.

Proof. Let $y \in F^n$, and let denote $y_k = \frac{\det(M_k)}{\det(A)}, \forall k \in \{1, ..., n\}$.
Note that $$y_k = \frac{\det(M_k)}{\det(A)} = \det(M_k) \cdot \det(A^{-1}) = \det(A^{-1}M_k) \\ = \sum_{j=1}^n (-1)^{k+j} (A^{-1}M_k)_{kj} \det(\widetilde{(A^{-1}M_k)_{kj}}) = (A^{-1}M_k)_{kk} \det(\widetilde{(A^{-1}M_k)_{kk}}) \\ = (A^{-1}b)_k \det(I_{n-1}) = (A^{-1}b)_k,$$ because $$(A^{-1}M_k)_{ij} = \begin{cases} (I_n)_{ij} & \text{if } j \neq k \\ (A^{-1}b)_i & \text{if } j = k \end{cases}.$$
Since $x = A^{-1}b$ is a unique solution of $Ax = b$, $x_k = (A^{-1}b)_k = y_k, \forall k \in \{1, ..., n\} \Longrightarrow x = y$. Thus $x_k = \frac{\det(M_k)}{\det(A)}$. $\blacksquare$

    크라메르 공식은 주어진 선형연립방정식의 해를 수학적으로 깔끔하게 제시한다는 점에서 의미가 있지만, 실제로 방정식의 해를 수치적으로 계산하고자 할 때는 별 볼일 없는 정리이다. coefficient matrix가 $n \times n$ 행렬일 때, 그 해를 구하려면 행렬식을 총 $n+1$번 계산해야 하기 때문에 연산량이 꽤 많은 편이다.