TheoremComplete

Cramer's Rule

Cramer's Rule gives an explicit formula for the solution of a system of linear equations in terms of determinants. While computationally expensive for large systems, it is theoretically elegant and useful for symbolic and small-scale computations.


Statement

Theorem4.4Cramer's Rule

Let AMn×n(F)A \in M_{n \times n}(F) be invertible and bFnb \in F^n. The unique solution x=(x1,,xn)x = (x_1, \ldots, x_n) of the system Ax=bAx = b is given by

xi=det(Ai(b))det(A)x_i = \frac{\det(A_i(b))}{\det(A)}

for i=1,2,,ni = 1, 2, \ldots, n, where Ai(b)A_i(b) is the matrix obtained from AA by replacing the ii-th column with bb.

Proof

Since AA is invertible, x=A1bx = A^{-1}b. By the adjugate formula, A1=1det(A)adj(A)A^{-1} = \frac{1}{\det(A)}\text{adj}(A), so

xi=(A1b)i=1det(A)j=1n(adj(A))ijbj=1det(A)j=1nCjibj.x_i = (A^{-1}b)_i = \frac{1}{\det(A)} \sum_{j=1}^n (\text{adj}(A))_{ij} b_j = \frac{1}{\det(A)} \sum_{j=1}^n C_{ji} b_j.

Now j=1nbjCji\sum_{j=1}^n b_j C_{ji} is the cofactor expansion of det(Ai(b))\det(A_i(b)) along column ii (since the ii-th column of Ai(b)A_i(b) is bb, and the cofactors for column ii are computed from the other columns, which are the same as in AA).


Examples

Example2 x 2 system

Solve (2153)(xy)=(411)\begin{pmatrix} 2 & 1 \\ 5 & 3 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 4 \\ 11 \end{pmatrix}.

det(A)=65=1\det(A) = 6 - 5 = 1.

x=det(41113)det(A)=12111=1,y=det(24511)det(A)=22201=2.x = \frac{\det\begin{pmatrix} 4 & 1 \\ 11 & 3 \end{pmatrix}}{\det(A)} = \frac{12 - 11}{1} = 1, \quad y = \frac{\det\begin{pmatrix} 2 & 4 \\ 5 & 11 \end{pmatrix}}{\det(A)} = \frac{22 - 20}{1} = 2.

Solution: (x,y)=(1,2)(x, y) = (1, 2). Verify: 2(1)+1(2)=42(1) + 1(2) = 4 and 5(1)+3(2)=115(1) + 3(2) = 11.

Example3 x 3 system

Solve: x+2z=6x + 2z = 6, 3x+4y+6z=30-3x + 4y + 6z = 30, x2y+3z=8-x - 2y + 3z = 8.

A=(102346123),b=(6308).A = \begin{pmatrix} 1 & 0 & 2 \\ -3 & 4 & 6 \\ -1 & -2 & 3 \end{pmatrix}, \quad b = \begin{pmatrix} 6 \\ 30 \\ 8 \end{pmatrix}.

det(A)=1(12+12)0+2(6+4)=24+20=44\det(A) = 1(12+12) - 0 + 2(6+4) = 24 + 20 = 44.

x=det(6023046823)44=6(12+12)0+2(6032)44=14418444=4044=1011.x = \frac{\det\begin{pmatrix} 6 & 0 & 2 \\ 30 & 4 & 6 \\ 8 & -2 & 3 \end{pmatrix}}{44} = \frac{6(12+12) - 0 + 2(-60-32)}{44} = \frac{144 - 184}{44} = \frac{-40}{44} = -\frac{10}{11}.

Similarly one computes yy and zz.

ExampleSymbolic/parametric system

Solve ax+by=eax + by = e, cx+dy=fcx + dy = f with adbc0ad - bc \neq 0:

x=edbfadbc,y=afceadbc.x = \frac{ed - bf}{ad - bc}, \quad y = \frac{af - ce}{ad - bc}.

Cramer's Rule gives a closed-form solution that makes dependence on parameters transparent.

ExampleWhen Cramer's Rule fails

If det(A)=0\det(A) = 0, Cramer's Rule does not apply. The system Ax=bAx = b either has no solution or infinitely many solutions, depending on whether bC(A)b \in C(A).

(1224)(xy)=(36)\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 3 \\ 6 \end{pmatrix}: det=0\det = 0. Infinitely many solutions: x=32tx = 3 - 2t, y=ty = t.

(1224)(xy)=(37)\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 3 \\ 7 \end{pmatrix}: det=0\det = 0 and bC(A)b \notin C(A). No solution.

ExampleSolving for one variable

A key advantage of Cramer's Rule: to find just x3x_3 in a 5×55 \times 5 system, compute only two determinants (det(A)\det(A) and det(A3(b))\det(A_3(b))), rather than solving the full system. This can be more efficient than row reduction if only one variable is needed.

ExampleTheoretical applications

Cramer's Rule is rarely used for numerical computation (too expensive for large nn), but it is invaluable in theory:

  • It shows the solution of Ax=bAx = b depends rationally on the entries of AA and bb.
  • It proves that solutions vary smoothly (or algebraically) with parameters.
  • It is used in algebraic geometry to study families of linear systems.
ExampleInverse via Cramer's Rule

Setting b=ejb = e_j in Ax=ejAx = e_j gives the jj-th column of A1A^{-1}:

(A1)ij=det(Ai(ej))det(A)=Cjidet(A)=(adj(A))ijdet(A).(A^{-1})_{ij} = \frac{\det(A_i(e_j))}{\det(A)} = \frac{C_{ji}}{\det(A)} = \frac{(\text{adj}(A))_{ij}}{\det(A)}.

This recovers the adjugate formula A1=1det(A)adj(A)A^{-1} = \frac{1}{\det(A)}\text{adj}(A).

ExampleComplex system

Solve (1+i)z1+2z2=3(1+i)z_1 + 2z_2 = 3 and iz1+(1i)z2=1iz_1 + (1-i)z_2 = 1 over C\mathbb{C}:

det(A)=(1+i)(1i)2i=22i\det(A) = (1+i)(1-i) - 2i = 2 - 2i.

z1=3(1i)222i=13i22iz_1 = \frac{3(1-i) - 2}{2 - 2i} = \frac{1 - 3i}{2 - 2i}. Rationalize by multiplying by 22i=2+2i\overline{2-2i} = 2 + 2i:

z1=(13i)(2+2i)(22i)(2+2i)=2+2i6i6i28=84i8=1i2z_1 = \frac{(1-3i)(2+2i)}{(2-2i)(2+2i)} = \frac{2 + 2i - 6i - 6i^2}{8} = \frac{8 - 4i}{8} = 1 - \frac{i}{2}.

ExampleGeometric interpretation in R^2

For Ax=bAx = b in R2\mathbb{R}^2: x1=det(b,a2)det(a1,a2)x_1 = \frac{\det(b, a_2)}{\det(a_1, a_2)} where a1,a2a_1, a_2 are the columns of AA.

det(b,a2)\det(b, a_2) is the signed area of the parallelogram spanned by bb and a2a_2, and det(a1,a2)\det(a_1, a_2) is the signed area spanned by a1a_1 and a2a_2. The ratio gives the "proportion" of a1a_1 needed to reach bb from the a2a_2 direction.

ExampleMultilinear algebra viewpoint

Cramer's Rule is a consequence of the multilinear and alternating nature of the determinant. Replacing column ii by b=xjajb = \sum x_j a_j and using multilinearity:

det(a1,,b,,an)=jxjdet(a1,,aj,,an)=xidet(A)\det(a_1, \ldots, b, \ldots, a_n) = \sum_{j} x_j \det(a_1, \ldots, a_j, \ldots, a_n) = x_i \det(A)

since det\det vanishes when two columns are equal. This is the deepest way to understand Cramer's Rule.

ExampleComputational cost

Cramer's Rule requires computing n+1n + 1 determinants of n×nn \times n matrices. Using cofactor expansion, this is O(nn!)=O((n+1)!)O(n \cdot n!) = O((n+1)!). Even using LU decomposition for each determinant, it is O(nn3)=O(n4)O(n \cdot n^3) = O(n^4), compared to O(n3)O(n^3) for Gaussian elimination on the augmented matrix.

ExampleCramer's Rule over general rings

Over a commutative ring RR (not necessarily a field), Cramer's Rule still holds in the form: det(A)xi=det(Ai(b))\det(A) \cdot x_i = \det(A_i(b)). If det(A)\det(A) is a unit in RR, we can divide. If not, the formula still gives useful information (e.g., det(A)\det(A) annihilates the cokernel of the map defined by AA).


RemarkSummary

Cramer's Rule converts the problem of solving a linear system into the problem of computing determinants. While impractical for large numerical systems, it provides:

  1. An explicit, closed-form formula for solutions
  2. A proof that solutions depend rationally on the coefficients
  3. Geometric insight via the volume interpretation of determinants
  4. A theoretical tool in algebra and algebraic geometry