Notes on Cramer's rule

Tags Math

Cramer's rule is a clever solution to the classical system of linear equations Ax=b:

\[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}b_1 \\ b_2 \\ b_3\end{bmatrix}\]

Using determinants (and assuming det(A)\neq 0).

We start by constructing a special matrix: the identity matrix whose first column is replaced by the column vector x, and then multiplying A by it [1]:

\[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \begin{bmatrix} x_{1} & 0 & 0 \\ x_{2} & 1 & 0 \\ x_{3} & 0 & 1 \\ \end{bmatrix} = \begin{bmatrix} b_1 & a_{12} & a_{13} \\ b_2 & a_{22} & a_{23} \\ b_3 & a_{32} & a_{33} \\ \end{bmatrix}\]

If we call our special matrix C_1 and the result B_1, then:

\[A \cdot C_1 = B_1\]

One of the fundamental properties of determinants is the product property:

\[det(A)\cdot det(C_1)=det(B_1)\]

But what is det(C_1)? It's easy to check that it's just x_1. Therefore:

\[det(a)\cdot x_1 = det(B_1)\]

Or:

\[x_1 = \frac{det(B_1)}{det(A)}\]

We can proceed similarly with C_2:

\[$$ \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \begin{bmatrix} 1 & x_{1} & 0 \\ 0 & x_{2} & 0 \\ 0 & x_{3} & 1 \\ \end{bmatrix} = \begin{bmatrix} a_{11} & b_1 & a_{13} \\ a_{21} & b_2 & a_{23} \\ a_{31} & b_3 & a_{33} \\ \end{bmatrix} $$\]

And from this:

\[x_2=\frac{det(B_2)}{det(A)}\]

So we get Cramer's rule:

For the n-by-n system of equations Ax=b, the solutions can be determined with:

\[x_i = \frac{\det(B_i)}{\det(A)} \qquad i = 1, \ldots, n\]

Where B_i is the matrix formed by replacing the i-th column of A by the column vector b.

While the construction detailed above should provide good motivation for why Cramer's rule works, it's not a rigorous proof; Wikipedia has a nice one.

Uses for matrix inversion

Given a matrix A, we'd like to find A^{-1} such that:

\[A\cdot A^{-1} = I\]

We can do this by repeated application of Cramer's rule, using the columns of A^{-1} as unknowns. Let's represent our matrices symbolically as:

\[A=\begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \qquad A^{-1}=\begin{bmatrix} x & y \\ v & w \\ \end{bmatrix}\]

Multiplying A by the first column of A^{-1}, we get the first column of the identity matrix [2]:

\[\begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \begin{bmatrix} x \\ v \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\]

We can use Cramer's rule to find the values of x and v from this. First, we need matrices B_1 and B_2:

\[B_1=\begin{bmatrix} 1 & b \\ 0 & d \\ \end{bmatrix} \qquad B_2=\begin{bmatrix} a & 1 \\ c & 0 \\ \end{bmatrix}\]

Then, compute the determinants:

\[\begin{align*} det(A)&=ad-bc\\ det(B_1)&=d\\ det(B_2)&=-c \end{align*}\]

And applying Cramer's rule:

\[\begin{align*} x&=\frac{det(B_1)}{det(A)}=\frac{d}{ad-bc}\\ v&=\frac{det(B_2)}{det(A)}=\frac{-c}{ad-bc} \end{align*}\]

Similarly, multiplying A by the second column of A^{-1}, we have:

\[\begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \begin{bmatrix} y \\ w \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}\]

And after applying Cramer's rule for this, we'll find that:

\[\begin{align*} y&=\frac{-b}{ad-bc}\\ w&=\frac{a}{ad-bc} \end{align*}\]

Overall, we get the nice formula:

\[A^{-1}=\frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c & a \\ \end{bmatrix}\]

Which you may be familiar with; it works whenever det(A)\neq 0 (meaning that the matrix A is actually invertible).

Inverting larger matrices

We've seen how to derive the well-known symbolic form of A^{-1} for 2-by-2 matrices. The same method works for any size. Let's take 3-by-3:

\[A=\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \qquad A^{-1}=\begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \\ \end{bmatrix}\]

To obtain the first column of A^{-1}, we multiply by it to get the first column of I:

\[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \begin{bmatrix} x_{11} \\ x_{21} \\ x_{31} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ \end{bmatrix}\]

To solve this using Cramer's rule, we'll need three B matrices:

\[B_1=\begin{bmatrix} 1 & a_{12} & a_{13} \\ 0 & a_{22} & a_{23} \\ 0 & a_{32} & a_{33} \\ \end{bmatrix} \quad B_2=\begin{bmatrix} a_{11} & 1 & a_{13} \\ a_{21} & 0 & a_{23} \\ a_{31} & 0 & a_{33} \\ \end{bmatrix} \quad B_3=\begin{bmatrix} a_{11} & a_{12} & 1 \\ a_{21} & a_{22} & 0 \\ a_{31} & a_{32} & 0 \\ \end{bmatrix}\]

And calculate their determinants. Because of the column borrowed from I, the determinants of these B matrices are the cofactors of A, meaning they are determinants of 2-by-2 matrices. To get all elements of A^{-1}, we'll need to find a total of nine determinants of 2-by-2 matrices. This extends to larger matrices as well: for an n-by-n matrix, we'll need to calculate n determinants of (n-1)-by-(n-1) matrices. Overall the time it takes to invert a matrix using this approach is O(n!), which is clearly infeasible for any reasonable size.

Thankfully, more efficient methods of inverting matrices exist - like the simple Gauss-Jordan elimination (O(n^3)).

Therefore, Cramer's rule is rarely used to invert matrices (or solve systems of equations) in practice. It's mostly useful for very small sizes, and also good for generating symbolic formulas for the simplest cases like the 2-by-2 inverse matrix formula shown above.

[1]This is just straightforward matrix multiplication, and using the fact that a_{11}x_1+a_{12}x_2+a_{13}x_3=b_1 etc.
[2]Feel free to check this on paper by performing the full multiplication between A and A^{-1} in their symbolic form and noticing that you only need the first column of A^{-1} to obtain the first column of the result.

For comments, please send me an email.