## Cramer’s Rule

We’re trying to invert a function which is continuously differentiable on some region . That is we know that if is a point where , then there is a ball around where is one-to-one onto some neighborhood around . Then if is a point in , we’ve got a system of equations

that we want to solve for all the .

We know how to handle this if is defined by a linear transformation, represented by a matrix :

In this case, the Jacobian transformation is just the function itself, and so the Jacobian determinant is nonzero if and only if the matrix is invertible. And so our solution depends on finding the inverse and solving

This is the approach we’d like to generalize. But to do so, we need a more specific method of finding the inverse.

This is where Cramer’s rule comes in, and it starts by analyzing the way we calculate the determinant of a matrix . This formula

involves a sum over all the permutations , and we want to consider the order in which we add up these terms. If we fix an index , we can factor out each matrix entry in the th column:

where the hat indicates that we omit the th term in the product. For a given value of , we can consider the restricted sum

which is times the determinant of the - “minor” of the matrix . That is, if we strike out the row and column of which contain and take the determinant of the remaining matrix, we multiply this by to get . These are the entries in the “adjugate” matrix .

What we’ve shown is that

(no summation on ). It’s not hard to show, however, that if we use a different row from the adjugate matrix we find

That is, the adjugate times the original matrix is the determinant of times the identity matrix. And so if we find

So what does this mean for our system of equations? We can write

But how does this sum differ from the one we used before (without summing on ) to calculate the determinant of ? We’ve replaced the th column of by the column vector , and so this is just another determinant, taken after performing this replacement!

Here’s an example. Let’s say we’ve got a system written in matrix form

The entry in the th row and th column of the adjugate matrix is calculated by striking out the th *column* and th *row* of our original matrix, taking the determinant of the remaining matrix, and multiplying by . We get

and thus we find

where we note that

In other words, our solution is given by ratios of determinants:

and similar formulae hold for larger systems of equations.

From computational viewpoint, Cramer’s rule is nice for very small matrices, but in practice one should use Gaussian elimination or QR factorization to calculate the determinant and inverse of a matrix, or to solve a linear system.

Comment by timur | November 17, 2009 |

Yes, but Gaussian elimination doesn’t tell you about the analytic properties of the inverse.

Comment by Qiaochu Yuan | November 17, 2009 |

Going ogg on a tangent, whilst you’re right about computational requirements, Cramer’s rule is also worth knowing if you’re trying to simplify a linear system whose coefficients are themselves some functions of some other variables, since determinants have nice algebraic properties and interpretations as hyper-volumes. (This isn’t so much solving the linear system as simplifying it, say for large scale finite element models with structure. This is “algebraic form”, distinct from the “analytic properties” John Armstrong is using in his next post.)

It’s a shame that most mathematical degrees tend to briefly introduce Cramer’s rule almost as a historical artifact and then immediately introduce Gaussian elimination.

Comment by davetweed | November 19, 2009 |

Related to this wedge product thread, and this post, is the nice way that one can achieve the result of cramer’s rule directly without cofactors, adjoints, or even determinants. Suppose you have

Now wedge both sides with one of the vectors, eliminating it. For example

If the system is can be solved for the bivectors on the left and right hand sides differ only by a constant, and one can solve by division.

I first saw this nicely illustrated in this online book by John Browne here:

http://sites.google.com/site/grassmannalgebra/

Since the wedge calculation can be reduced to a determinant, at its core this is no different than Cramer’s rule, but I think it provides a nice conceptual clarity. It is also no more efficient, and no less numerically unstable, so you probably really want SVD for computational work.

Comment by peeterjoot | November 17, 2009 |

Qiaochu is closest to the mark, as will become apparent later this week. I don’t just want the inverse, but I want to know something about the form of the inverse.

Comment by John Armstrong | November 18, 2009 |

Oh, and I actually wanted to introduce the adjugate matrix for a

completely unrelated(?) reason I’ll be getting to later. It’s something I only know a handful of people have thought about, and none very explicitly.Comment by John Armstrong | November 18, 2009 |

[…] system of equations, which has a unique solution since the determinant of its matrix is . We use Cramer’s rule to solve it, and get an expression for our difference quotient as a quotient of two determinants. […]

Pingback by The Inverse Function Theorem « The Unapologetic Mathematician | November 18, 2009 |

[…] of a product matrix as a (quadratic) polynomial in the entries of and . As for inversion, Cramer’s rule expresses the entries of the inverse matrix as the quotient of a (degree ) polynomial in the […]

Pingback by General Linear Groups are Lie Groups « The Unapologetic Mathematician | June 9, 2011 |