In linear algebra, Cramer's rule is an explicit formula for the solution of a system of linear equations with as many equations as unknowns, valid whenever the system has a unique solution. It expresses the solution in terms of the determinants of the (square) coefficient matrix and of matrices obtained from it by replacing one column by the vector of right hand sides of the equations. It is named after Gabriel Cramer (1704–1752), who published the rule for an arbitrary number of unknowns in 1750, although Colin Maclaurin also published special cases of the rule in 1748 (and possibly knew of it as early as 1729).
Cramer's rule is computationally very inefficient for systems of more than two or thee equations; its asymptotic complexity is O(n·n!) compared to elmination methods that have polynomial time complexity. Cramer's rule is also numerically unstable even for 2×2 systems.
- 1 General case
- 2 Proof
- 3 Finding inverse matrix
- 4 Applications
- 5 Geometric interpretation
- 6 Other proofs
- 7 Systems of vector equations: Cramer’s Rule extended
- 8 Incompatible and indeterminate cases
- 9 Notes
- 10 External links
Consider a system of n linear equations for n unknowns, represented in matrix multiplication form as follows:
where the n × n matrix A has a nonzero determinant, and the vector is the column vector of the variables. Then the theorem states that in this case the system has a unique solution, whose individual values for the unknowns are given by:
where is the matrix formed by replacing the i-th column of A by the column vector b.
The rule holds for systems of equations with coefficients and unknowns in any field, not just in the real numbers. It has recently been shown that Cramer's rule can be implemented in O(n3) time, which is comparable to more common methods of solving systems of linear equations, such as Gaussian elimination (consistently requiring 2.5 times as many arithmetic operations for all matrix sizes, while exhibiting comparable numeric stability in most cases).
The proof for Cramer's rule uses just two properties of determinants: linearity with respect to any given column (taking for that column a linear combination of column vectors produces as determinant the corresponding linear combination of their determinants), and the fact that the determinant is zero whenever two columns are equal (which is implied by the basic property that the determinant is alternating in the columns).
Fix the index j of a column. Linearity means that if we consider only column j as variable (fixing the others arbitrarily), the resulting function Rn → R (assuming matrix entries are in R) can be given by a matrix, with one row and n columns, that acts on column j. In fact this is precisely what Laplace expansion does, writing det(A) = C1a1,j + ... + Cnan,j for certain coefficients C1, ..., Cn that depend on the columns of A other than column j (the precise expression for these cofactors is not important here). The value det(A) is then the result of applying the one-line matrix L(j) = (C1 C2 ... Cn) to column j of A. If L(j) is applied to any other column k of A, then the result is the determinant of the matrix obtained from A by replacing column j by a copy of column k, so the resulting determinant is 0 (the case of two equal columns).
Now consider a system of n linear equations in n unknowns , whose coefficient matrix is A, with det(A) assumed to be nonzero:
If one combines these equations by taking C1 times the first equation, plus C2 times the second, and so forth until Cn times the last, then the coefficient of xj will become C1a1, j + ... + Cnan,j = det(A), while the coefficients of all other unknowns become 0; the left hand side becomes simply det(A)xj. The right hand side is C1b1 + ... + Cnbn, which is L(j) applied to the column vector b of the right hand sides bi. In fact what has been done here is multiply the matrix equation Ax = b on the left by L(j). Dividing by the nonzero number det(A) one finds the following equation, necessary to satisfy the system:
But by construction the numerator is the determinant of the matrix obtained from A by replacing column j by b, so we get the expression of Cramer's rule as a necessary condition for a solution. The same procedure can be repeated for other values of j to find values for the other unknowns.
The only point that remains to prove is that these values for the unknowns, the only possible ones, do indeed together form a solution. But if the matrix A is invertible with inverse A−1, then x = A−1b will be a solution, thus showing its existence. To see that A is invertible when det(A) is nonzero, consider the n × n matrix M obtained by stacking the one-line matrices L(j) on top of each other for j = 1, ..., n (this gives the adjugate matrix for A). It was shown that L(j)A = (0 ... 0 det(A) 0 ... 0) where det(A) appears at the position j; from this it follows that MA = det(A)In. Therefore
completing the proof.
For other proofs, see below.
Finding inverse matrix
Let A be an n × n matrix. Then
If R is a field (such as the field of real numbers), then this gives a formula for the inverse of A, provided det(A) ≠ 0. In fact, this formula will work whenever R is a commutative ring, provided that det(A) is a unit. If det(A) is not a unit, then A is not invertible.
Explicit formulas for small systems
Consider the linear system
which in matrix format is
Assume a1b2 − b1a2 nonzero. Then, with help of determinants x and y can be found with Cramer's rule as
The rules for 3 × 3 matrices are similar. Given
which in matrix format is
Then the values of x, y and z can be found as follows:
Cramer's rule is also extremely useful for solving problems in differential geometry. Consider the two equations and . When u and v are independent variables, we can define and
Finding an equation for is a trivial application of Cramer's rule.
First, calculate the first derivatives of F, G, x, and y:
Substituting dx, dy into dF and dG, we have:
Since u, v are both independent, the coefficients of du, dv must be zero. So we can write out equations for the coefficients:
Now, by Cramer's rule, we see that:
This is now a formula in terms of two Jacobians:
Similar formulas can be derived for
Cramer's rule can be used to prove that an integer programming problem whose constraint matrix is totally unimodular and whose right-hand side is integer, has integer basic solutions. This makes the integer program substantially easier to solve.
Ordinary differential equations
Cramer's rule is used to derive the general solution to an inhomogeneous linear differential equation by the method of variation of parameters.
Cramer's rule has a geometric interpretation that can be considered also a proof or simply giving insight about its geometric nature. These geometric arguments work in general and not only in the case of two equations with two unknowns presented here.
Given the system of equations
it can be considered as an equation between vectors
The area of the parallelogram determined by and is given by the determinant of the system of equations:
In general, when there are more variables and equations, the determinant of n vectors of length n will give the volume of the parallelepiped determined by those vectors in the n-th dimensional Euclidean space.
Therefore the area of the parallelogram determined by and has to be times the area of the first one since one of the sides has been multiplied by this factor. Now, this last parallelogram, by Cavalieri's principle, has the same area as the parallelogram determined by and .
Equating the areas of this last and the second parallelogram gives the equation
from which Cramer's rule follows.
A short proof
A short proof of Cramer's rule  can be given by noticing that is the determinant of the matrix
On the other hand, assuming that our original matrix A is invertible, this matrix has columns , where is the k-th column of the matrix A. Recall that the matrix has columns . Hence we have
The proof for other is similar.
Proof using Clifford algebra
Consider the system of three scalar equations in three unknown scalars
and assign an orthonormal vector basis for as
Let the vectors
Adding the system of equations, it is seen that
Using the exterior product, each unknown scalar can be solved as
For n equations in n unknowns, the solution for the k-th unknown generalizes to
If ak are linearly independent, then the can be expressed in determinant form identical to Cramer’s Rule as
where (c)k denotes the substitution of vector ak with vector c in the k-th numerator position.
Systems of vector equations: Cramer’s Rule extended
Consider the system of n vector equations in n unknown vectors
where we want to solve for each unknown vector xk in terms of the given scalar constants and vector constants ck.
Solving for unknown vectors
Using the Clifford algebra (or geometric algebra) of Euclidean vectors, the vectors xk and ck are in a vector space having d dimensions spanned by a basis of d orthonormal base vectors . This d-dimensional space can be extended to be a subspace of a larger (d + n)-dimensional space spanned by .
Multiply the k-th equation by the th orthonormal base unit , using the exterior product on the right, as
The original system of equations in grade-1 vectors is now transformed into a system of equations in grade-2 vectors, and no parallel components have been deleted by the exterior products since they multiply on perpendicular extended base units.
Let the vectors
Adding the transformed system of equations gives
which is a 2-vector equation. These exterior (wedge) products are equal to Clifford products since the factors are perpendicular.
For , and are solved by multiplying , and , respectively, on the right with exterior products
In the solution of x1, and similarly for x2 and is a 4-blade having 3 of its 4 dimensions in the extended dimensions , and the remaining one dimension is in the solution space of the vectors xk and ck. The 3-blade is in the problem space, or the extended dimensions. The inner product reduces, or contracts, to a 1-vector in the d-dimensional solution space. The divisor , the square of a blade, is a scalar product that can be computed by a determinant. Since C is a 2-vector, it commutes with the vectors without sign change and is conveniently shifted into the vacant k-th spot. A sign change occurs in every even k-th solution x+, such as x2, due to commuting or shifting ak right an odd number of times, in the dividend blade , into its k-th spot.
In general we have:
where denotes replacing the k-th element ak with C. The factor accounts for shifting the k-th vector ak by places. The -blade is multiplied by inner product with the reversed n-blade , producing a 1-vector in the d-dimensional solution space.
Using this formula, for solving a system of n vector equations having n unknown vectors in a d-dimensional space, requires extending the space to dimensions. The extended n dimensions are essentially used to hold the system of n equations represented by the scalar constants 1-vectors ak and the vector constants 1-vectors ck. The n vector constants ck are grade-increased to 2-vectors or grade-2 vectors that are partly in the extended space. Notice the similarity of form to Cramer’s Rule for systems of scalar equations; a basis is added in both cases. The advantage of this formula is that it avoids scalar coordinates and the results are directly in terms of vectors.
The system of vector equations can also be solved in terms of coordinates, without using the geometric algebra formula above, by the usual process of expanding all the vectors in the system into their coordinate vector components. In each expanded equation, the parallel (like) components are summed into d groups that form d independent systems of n unknown coordinates in n equations. Each system solves for one dimension of coordinates. After solving the d systems, the solved vectors can be reassembled from the solved coordinates. It seems that few books explicitly discuss this process for systems of vector equations. This process is the application of the abstract concept of linear independence as it applies to linearly independent dimensions of vector components or unit vectors. The linear independence concept extends to multivectors in geometric algebra, where each unique unit blade is linearly independent of the others for the purpose of solving equations or systems of equations. An equation containing a sum of d linearly independent terms can be rewritten as d separate independent equations, each in the terms of one dimension.
Solving for unknown scalars
Note that, instead of solving for unknown vectors xk, the xk may be known vectors and the vectors ak may be unknown. The vectors a1, a2, a3 could be solved as
In general, vector ak may be solved as
and represents transforming or projecting the system, or each vector ck, onto the basis of vectors which need not be orthonormal. However solving for the vectors by this formula is unnecessary and unnecessarily requires n vectors at a time. Solving each equation is independent in this case. This has been shown to clarify the usage, as far as what not to do, unless one has an unusual need to solve a particular vector ak. Instead, the following can be done in the case of projecting vectors ck onto a new arbitrary basis xk.
Projecting a vector onto an arbitrary basis.
Projecting any vector c onto a new arbitrary basis as
where each xk is written in the form
is a system of n scalar equations in n unknown coordinates
and can be solved using the ordinary Cramer’s rule for systems of scalar equations, where the step of adding a basis can be considered as already done. For n = 3, the solutions for the scalars are
For n basis vectors (n equations in n unknowns), the solution for the k-th unknown scalar coordinate generalizes to
the formula for Cramer’s rule.
The remainder of this subsection outlines some additional concepts or applications that may be important to consider when using arbitrary bases, but otherwise you may skip ahead to the next subsection.
The reciprocal basis of the arbitrary basis is such that , while in general . The k-th reciprocal base is
where denotes that the k-th vector xk is removed from the blade. In mathematics literature, the reciprocal basis is usually written using superscript indices as which should not be confused as exponents or powers of the vectors. The reciprocal bases can be computed once and saved, and then any vector c can be projected onto the arbitrary basis as with implied summation over the range of .
and that for
therefore if the are the new arbitrary bases, then the xk are the reciprocal bases and we also have
with the summation convention over k.
If we abandon the old basis ek and old coordinates and of c and refer c only to the new basis xk and its reciprocal , then we can newly rename coordinates for c on the new bases as
This is a coordinates naming convention that is often used implicitly such that and are understood as identities. Using this coordinates naming convention we can derive the expression
Since for and for (or using Kronecker delta), this expression reduces to the identity
Since c is an arbitrary vector, we can choose any two vectors u, v and find the identities
In the language of tensors, m is called the metric tensor of the basis, δ is the Kronecker delta, an upper-indexed (superscripted) element is called contravariant, and a lower-indexed (subscripted) element is called covariant. Equating right-hand sides, we obtain the tensor contractions that are equivalent to the dot product
where in the first equation either or (index-lowering contractions), and in the second equation either or (index-raising contractions). The contraction that lowers the index on into expands to the sum
Contractions are a form of inner product. Contractions such as these
are called index renaming. Contractions involving m and have many relations such as
When viewed as n × n matrices, and are inverse matrices. The matrices m are symmetric, so the indices can be reversed. The contraction that computes the matrix product is
The Kronecker delta , viewed as a matrix, is the identity matrix. From this matrix product identity, the reciprocal bases can be computed as
The formula for the inner or dot product of vectors requires the terms to be products of covariant and contravariant component pairs. One of the vectors has to be expressed in terms of the reciprocal basis relative to the basis of the other vector. This requirement is satisfied when expressing vectors on an orthonormal basis that is self-reciprocal, but must be paid proper attention otherwise. The formula is often written
but this is valid only if the vectors are both expressed on the same orthonormal basis with .
The derivative operator ∇ called del is often written as
for a basis and reciprocal basis , and position vector written in the tensor forms. For example, the divergence of r can be computed several ways as
The derivative operator can be applied further in this way as a vector, where
in geometric calculus for vectors in any number of dimensions n, and
For n = 3, the product is known as divergence, and the product is known as curl. The value is the pseudoscalar of the Clifford algebra. Dividing the bivector by the pseudoscalar produces its spatial dual in the orthogonal vector space with the same magnitude, and oriented with sign in the expected direction for the curl vector. For a scalar field , the product is known as the gradient vector, which generalizes the scalar-valued derivative of a single-variable function to a vector-valued derivative of a multi-variable function .
In the rectilinear coordinates system (or affine or oblique coordinate system) that has been considered so far, the metric tensor m has been a constant matrix containing constant ratios that relate to the amount of shearing that occurs in transforming from one rectilinear system to another. In a curvilinear coordinates system, the metric tensor m may be variable and varies with the position vector r. The local frame or basis at r can be defined as
where the position vector . It can be assumed that is a standard basis. Each is a function of the variables , and each is at least an implicit function of the variables such that the transformation is invertible. The basis is a frame local to each position of r in space, and may vary with position. The covariant metric tensor is
and in terms of the Jacobian matrix is expressed as the matrix
The contravariant metric tensor is again the matrix inverse of the covariant metric tensor
and the contravariant or reciprocal basis is
Projecting a vector onto an orthogonal basis
Projections onto arbitrary bases xk, as solved using Cramer’s rule as just above, treats projections onto orthogonal bases as only a special case. Projections onto mutually orthogonal bases can be achieved using the ordinary projection operation
which is correct only if the xk are mutually orthogonal. If the bases are constrained to be mutually perpendicular (orthogonal), then the formula for Cramer’s rule becomes
where c has been written as a sum of vector components parallel and perpendicular to xk. For any two perpendicular vectors xj, xk, their exterior product equals their Clifford product. The vector component must be parallel to the other , therefore its outermorphism is zero. The result is Cramer’s rule reduced to orthogonal projection of vector c onto base such that .
In general, the bases are not necessarily mutually orthogonal and the projection to use is Cramer’s rule, generalized projection, not the dot product specific to orthogonal projection.
An orthonormal basis is identical to its reciprocal basis since
and with implied summation over the range of . For an orthogonal basis, each reciprocal base is already shown to be
which suggests the name reciprocal basis.
Solving a system of vector equations using SymPy
The free software SymPy, for symbolic mathematics using python, includes a Geometric Algebra Module and interactive calculator console
isympy console can be used to solve systems of vector equations using the formulas of this article. A simple example of console interaction follows to solve the system
$isympy >>> from sympy.galgebra.ga import * >>> (e1,e2,e3,e4,e5,e6) = MV.setup('e*1|2|3|4|5|6',metric='[1,1,1,1,1,1]') >>> (v1,v2,v3) = symbols('v1 v2 v3') >>> (c1,c2,c3,C) = symbols('c1 c2 c3 C') >>> (a1,a2,a3) = symbols('a1 a2 a3') >>> a1 = 3*e4 + 2*e5 + 9*e6 >>> a2 = 4*e4 + 3*e5 + 6*e6 >>> a3 = 5*e4 + 7*e5 + 9*e6 >>> c1 = 9*e1 + 2*e2 + 3*e3 >>> c2 = 6*e1 + 5*e2 + 8*e3 >>> c3 = 2*e1 + 4*e2 + 7*e3 >>> C = (c1^e4) + (c2^e5) + (c3^e6) >>> v1 = (C^a2^a3)|((-1)**(1-1)*MV.inv(a1^a2^a3)) >>> v2 = (a1^C^a3)|((-1)**(2-1)*MV.inv(a1^a2^a3)) >>> v3 = (a1^a2^C)|((-1)**(3-1)*MV.inv(a1^a2^a3)) >>> 3*v1 + 4*v2 + 5*v3 9*e_1 + 2*e_2 + 3*e_3 >>> 2*v1 + 3*v2 + 7*v3 6*e_1 + 5*e_2 + 8*e_3 >>> 9*v1 + 6*v2 + 9*v3 2*e_1 + 4*e_2 + 7*e_3
Incompatible and indeterminate cases
A system of equations is said to be incompatible or inconsistent when there are no solutions and it is called indeterminate when there is more than one solution. For linear equations, an indeterminate system will have infinitely many solutions (if it is over an infinite field), since the solutions can be expressed in terms of one or more parameters that can take arbitrary values.
Cramer's rule applies to the case where the coefficient determinant is nonzero. In the 2 × 2 case, if the coefficient determinant is zero, then the system is incompatible if the numerator determinants are nonzero, or indeterminate if the numerator determinants are zero.
For 3x3 or higher systems, the only thing one can say when the coefficient determinant equals zero is that if any of the numerator determinants are nonzero, then the system must be incompatible. However, having all determinants zero does not imply that the system is indeterminate. A simple example where all determinants vanish (equal zero) but the system is still incompatible is the 3x3 system x+y+z=1, x+y+z=2, x+y+z=3.
|This article needs additional citations for verification. (August 2008)|
- Cramer, Gabriel (1750). "Introduction à l'Analyse des lignes Courbes algébriques" (in French). Geneva: Europeana. pp. 656–659. Retrieved 2012-05-18.
- MacLaurin, Colin (1748). A Treatise of Algebra, in Three Parts.
- Boyer, Carl B. (1968). A History of Mathematics (2nd ed.). Wiley. p. 431.
- Katz, Victor (2004). A History of Mathematics (Brief ed.). Pearson Education. pp. 378–379.
- Hedman, Bruce A. (1999). "An Earlier Date for "Cramer's Rule"". Historia Mathematica. 4(26) (4): 365–368. doi:10.1006/hmat.1999.2247
- David Poole (2014). Linear Algebra: A Modern Introduction. Cengage Learning. p. 276. ISBN 978-1-285-98283-0.
- Joe D. Hoffman; Steven Frankel (2001). Numerical Methods for Engineers and Scientists, Second Edition,. CRC Press. p. 30. ISBN 978-0-8247-0443-8.
- Thomas S. Shores (2007). Applied Linear Algebra and Matrix Analysis. Springer Science & Business Media. p. 132. ISBN 978-0-387-48947-6.
- Nicholas J. Higham (2002). Accuracy and Stability of Numerical Algorithms: Second Edition. SIAM. p. 13. ISBN 978-0-89871-521-7.
- Ken Habgood, Itamar Arel (2012). "A condensation-based application of Cramerʼs rule for solving large-scale linear systems". Journal of Discrete Algorithms 10: 98–109. doi:10.1016/j.jda.2011.06.007.
- Robinson, Stephen M. (1970). "A Short Proof of Cramer's Rule". Mathematics Magazine 43: 94–95.
|Wikibooks has a book on the topic of: Linear Algebra/Cramer's Rule|
- Proof of Cramer's Rule
- WebApp descriptively solving systems of linear equations with Cramer's Rule
- Online Calculator of System of linear equations