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 column 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 implemented in a naïve way is computationally inefficient for systems of more than two or three equations. In the case of n equations in n unknowns, it requires computation of n + 1 determinants, while Gaussian elimination produces the result with the same computational complexity as the computation of a single determinant.Cramer’s rule can also be numerically unstable even for 2×2 systems. However, 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.
General case
Consider a system of n linear equations for n unknowns, represented in matrix multiplication form as follows:
- {\displaystyle Ax=b}
where the n × n matrix A has a nonzero determinant, and the vector {\displaystyle x=(x_{1},\ldots ,x_{n})^{\mathrm {T} }} 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.
A more general version of Cramer’s rule considers the matrix equation
where the n × n matrix A has a nonzero determinant, and X, B are n × m matrices. Given sequences and, let be the k × k submatrix of X with rows in and columns in. Let be the n × n matrix formed by replacing the column of A by the column of B, for all . Then
In the case , this reduces to the normal Cramer’s rule.
The rule holds for systems of equations with coefficients and unknowns in any field, not just in the real numbers.
Cramer’s Rule is a method for solving multivariate simultaneous linear equations.
a11 x1 + a12x2 + … a1n xn = b1
an1 x1 + an2 x2 + … annxn = bn
where xi is the ith variable, aij is the constant coefficient on *y in the rth equation, and bi is the constant on the right-hand side of the rth equation.
This can be written in matrix notation as:
AX = b,
where A is the matrix containing the elements aij b is the vector containing the elements bi ; X is the vector of values of the variables xi The value of xk which satisfies. the set of simultaneous equations is found by Cramer’s rule by replacing the kth column of the matrix A by the vector b, forming a new matrix Ak.
The value of Xk is then the determinant of Ak divided by the determinant of A, that is
Xk = |Ak| / |A|; k=1,…,n
Geometric interpretation
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.
Other proofs
A proof by abstract linear algebra
This is a restatement of the proof above in abstract language.
Consider the map where is the matrix with substituted in the th column, as in Cramer’s rule. Because of linearity of determinant in every column, this map is linear. Observe that it sends the th column of to theth basis vector (with 1 in theth place), because determinant of a matrix with a repeated column is 0. So we have a linear map which agrees with the inverse of on the column space; hence it agrees with on the span of the column space. Since is invertible, the column vectors span all of , so our map really is the inverse of . 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 n-th column of the matrix A. Recall that the matrix has columns , and therefore. Hence, by using that the determinant of the product of two matrices is the product of the determinants, 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
- \mathbf {a} _{2}\wedge \mathbf {a} _{3}}}\end{aligned}}}
For n equations in n unknowns, the solution for the k-th unknown {\displaystyle x_{k}} 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.
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 3×3 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 3×3 system x+y+z=1, x+y+z=2, x+y+z=3.
SOURCE:
K A FOX AND T K KAUL, INTERMEDIATE ECONOMIC STATISTICS (MELBOURNE, FLA, 1980)
I was very pleased to search out this web-site.I needed to thanks for your time for this excellent read!! I definitely having fun with each little bit of it and I have you bookmarked to check out new stuff you weblog post.
Well I definitely enjoyed studying it. This tip procured by you is very practical for accurate planning.
It’s nearly impossible to find knowledgeable people for this topic, but you sound like you know what you’re talking about! Thanks