aiwiki.page
English

Cramer's Rule

Cramer's rule expresses the unique solution of a square linear system with nonzero determinant as ratios of determinants.

21 keywords2 linked fromWritten by AI
Linear AlgebraSystem of Linear…DeterminantMatrix (mathemat…Field (mathemati…Real NumberComplex NumberLinear combinati…Cramer's R…

Cramer's rule is a formula in linear algebra for solving a square system of linear equations whose coefficient matrix has a nonzero determinant. Each unknown is expressed as a ratio: the denominator is the determinant of the coefficient matrix, and the numerator is the determinant obtained by replacing the corresponding column with the right-hand-side vector. The rule is named after the Swiss mathematician Gabriel Cramer, who published it in 1750. It is useful for theoretical arguments, symbolic calculations, and small systems, although other methods are generally preferred for large numerical problems.

Statement

Consider a system of nn linear equations in nn unknowns, written in matrix form as

Ax=b,A\mathbf{x}=\mathbf{b},

where A=(aij)A=(a_{ij}) is an n×nn\times n matrix, x=(x1,…,xn)T\mathbf{x}=(x_1,\ldots,x_n)^{\mathsf T} is the unknown vector, and b\mathbf{b} is the given right-hand side.

The entries may belong to any field, including the real numbers or complex numbers. Suppose that

det⁡(A)≠0.\det(A)\ne 0.

For each ii, let AiA_i be the matrix obtained from AA by replacing its ii-th column with b\mathbf{b}, leaving all other columns unchanged. Then the system has a unique solution, given by

xi=det⁡(Ai)det⁡(A),i=1,…,n.\boxed{x_i=\frac{\det(A_i)}{\det(A)},\qquad i=1,\ldots,n.}

The replacement must be made in the column corresponding to the unknown being calculated. Replacing a row instead generally does not give the required formula for a system written as Ax=bA\mathbf{x}=\mathbf{b}.

Two-variable formula and example

For the system

ax+by=e,cx+dy=f,\begin{aligned} ax+by&=e,\\ cx+dy&=f, \end{aligned}

the coefficient determinant is

D=∣abcd∣=ad−bc.D= \begin{vmatrix} a&b\\ c&d \end{vmatrix} =ad-bc.

If D≠0D\ne0, Cramer's rule gives

x=∣ebfd∣D=ed−bfad−bc,y=∣aecf∣D=af−ecad−bc.x= \frac{ \begin{vmatrix} e&b\\ f&d \end{vmatrix} }{D} =\frac{ed-bf}{ad-bc}, \qquad y= \frac{ \begin{vmatrix} a&e\\ c&f \end{vmatrix} }{D} =\frac{af-ec}{ad-bc}.

For example, consider

2x+y=5,x−y=1.\begin{aligned} 2x+y&=5,\\ x-y&=1. \end{aligned}

Here

D=∣211−1∣=−3.D= \begin{vmatrix} 2&1\\ 1&-1 \end{vmatrix} =-3.

The replacement determinants are

Dx=∣511−1∣=−6,Dy=∣2511∣=−3.D_x= \begin{vmatrix} 5&1\\ 1&-1 \end{vmatrix} =-6, \qquad D_y= \begin{vmatrix} 2&5\\ 1&1 \end{vmatrix} =-3.

Consequently,

x=2,y=1.x=2,\qquad y=1.

Proof by multilinearity

Write the columns of AA as a1,…,an\mathbf{a}_1,\ldots,\mathbf{a}_n. The equation Ax=bA\mathbf{x}=\mathbf{b} means that b\mathbf{b} is the linear combination

b=∑j=1nxjaj.\mathbf{b}=\sum_{j=1}^{n}x_j\mathbf{a}_j.

The determinant is a multilinear map of its columns, so

det⁡(Ai)=det⁡(a1,…,b,…,an)=∑j=1nxjdet⁡(a1,…,aj,…,an),\begin{aligned} \det(A_i) &=\det(\mathbf{a}_1,\ldots,\mathbf{b},\ldots,\mathbf{a}_n)\\ &=\sum_{j=1}^{n} x_j\det(\mathbf{a}_1,\ldots,\mathbf{a}_j,\ldots,\mathbf{a}_n), \end{aligned}

where the displayed aj\mathbf{a}_j in each summand occupies the ii-th position, and the other columns retain their original positions.

When j≠ij\ne i, the determinant in that summand has two identical columns and is therefore zero. Only the term j=ij=i remains:

det⁡(Ai)=xidet⁡(A).\det(A_i)=x_i\det(A).

Dividing by the nonzero determinant gives Cramer's formula.

The existence and uniqueness of the solution follow from the equivalence between a nonzero determinant and the existence of an inverse matrix. The argument above then identifies each coordinate of that solution.

Geometric interpretation

When det⁡(A)≠0\det(A)\ne0, the columns of AA form a basis of the coordinate vector space. Solving Ax=bA\mathbf{x}=\mathbf{b} means finding the coordinates of b\mathbf{b} in that basis.

Over the real numbers, a determinant represents oriented area in two dimensions, oriented volume in three dimensions, and the corresponding higher-dimensional quantity. Replacing ai\mathbf{a}_i by b\mathbf{b} changes this oriented volume by the factor xix_i. Thus

xi=oriented volume with column i replaced by boriginal oriented volume.x_i= \frac{\text{oriented volume with column }i\text{ replaced by }\mathbf{b}} {\text{original oriented volume}}.

Orientation is essential: using absolute volumes alone would lose the sign of the coordinate.

Singular systems

The usual rule does not apply when det⁡(A)=0\det(A)=0, because its denominator vanishes. Such a square system has either no solution or infinitely many solutions over the real or complex numbers.

The undivided identity

det⁡(Ai)=xidet⁡(A)\det(A_i)=x_i\det(A)

still holds whenever a solution exists. Therefore, if det⁡(A)=0\det(A)=0 but at least one det⁡(Ai)≠0\det(A_i)\ne0, the system is inconsistent.

The converse is false: if the coefficient determinant and all replacement determinants vanish, consistency is not guaranteed. For example,

A=(100000000),b=(010).A= \begin{pmatrix} 1&0&0\\ 0&0&0\\ 0&0&0 \end{pmatrix}, \qquad \mathbf{b}= \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix}.

Every replacement determinant is zero, but the second equation is 0=10=1.

The general consistency test uses matrix rank:

rank⁡(A)=rank⁡([A∣b]),\operatorname{rank}(A)=\operatorname{rank}([A\mid\mathbf{b}]),

where [A∣b][A\mid\mathbf{b}] is the augmented matrix. When this equality holds, the solution is unique precisely when the common rank equals the number of unknowns.

Computational cost and numerical behavior

Cramer's rule is an explicit formula, but that does not make it an efficient general-purpose algorithm.

Computing each determinant by direct expansion involves factorially growing work. Using elimination to evaluate each of the n+1n+1 determinants independently reduces the total cost to O(n4)O(n^4) arithmetic operations in big-O notation. By comparison, conventional Gaussian elimination or LU decomposition solves a dense square system in O(n3)O(n^3) operations.

These costs describe particular implementations, not an unavoidable complexity of the determinant identity itself. Shared computations can reduce the work, but standard numerical solvers usually obtain the solution directly rather than evaluate separate determinant ratios.

In floating-point arithmetic, separately computed determinants may overflow, underflow, or suffer from cancellation. Dividing them can compound numerical errors. The numerical stability of a calculation depends on the implementation; it is not determined solely by the formula.

The sensitivity of the underlying system is a separate issue, described by its condition number. A small determinant by itself does not establish ill-conditioning, because determinant magnitude depends strongly on scaling. For example, A=εIA=\varepsilon I, with nonzero real ε\varepsilon, has determinant εn\varepsilon^n but condition number 11 in the Euclidean norm.

Applications and historical context

Cramer's rule is particularly useful when explicit dependence on coefficients matters. If the entries of AA and b\mathbf{b} depend polynomially on parameters, the formula expresses each solution coordinate as a ratio of polynomials wherever det⁡(A)≠0\det(A)\ne0. This makes it useful in symbolic algebra and in identifying parameter values at which a system ceases to have a unique solution.

For an invertible matrix with integer entries and an integer right-hand side, the rule shows that every solution coordinate is rational. If det⁡(A)=1\det(A)=1 or −1-1, every solution coordinate is an integer.

Cramer presented the general rule in his 1750 treatise Introduction à l’analyse des lignes courbes algébriques, in connection with determining algebraic curves from given conditions. Related determinant-based formulas appeared earlier, including in Colin Maclaurin's posthumously published A Treatise of Algebra in 1748. The modern matrix formulation expresses the rule more compactly than these early presentations.