Cramer's rule: Definition from Answers.com

Cramer's rule is a theorem in linear algebra, which gives an expression for the solution of a system of linear equations with as many equations as unknowns, valid in those cases where there is unique solution; this solution is then expressed 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 in his 1750 Introduction à l'analyse des lignes courbes algébriques, although Colin Maclaurin also published the method in his 1748 Treatise of Geometry (and probably knew of the method as early as 1729).^[1]

Computationally, it is inefficient for large matrices and thus not used in practical applications which may involve many equations. However, as no pivoting is needed, it is more efficient than Gaussian elimination for small matrices, particularly when SIMD operations are used.

Cramer's rule is of theoretical importance in that it gives an explicit expression for the solution of the system.

Wikibooks has a book on the topic of

Linear Algebra/Cramer's Rule

1 Explicit formulas for small systems
2 Finding solution of a system of linear equations in the general case
3 Finding inverse matrix
4 Abstract formulation
5 Applications to differential geometry
6 Applications to algebra
7 Relevance to eigenvalues
8 Applications to integer programming
9 See also
10 Notes
11 External links

Explicit formulas for small systems

Consider the linear system

$ax + by = {\color{red}e}\,$

$cx + dy = {\color{red}f}\,$

which in matrix format is

$\begin{bmatrix} a & b \\ c & d \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix}=\begin{bmatrix} {\color{red}e} \\ {\color{red}f} \end{bmatrix}.$

Then, x and y can be found with Cramer's rule as:

$x = \frac { \begin{vmatrix} \color{red}{e} & b \\ \color{red}{f} & d \end{vmatrix} } { \begin{vmatrix} a & b \\ c & d \end{vmatrix} } = { {\color{red}e}d - b{\color{red}f} \over ad - bc}$

and

$y = \frac { \begin{vmatrix} a & \color{red}{e} \\ c & \color{red}{f} \end{vmatrix} } { \begin{vmatrix} a & b \\ c & d \end{vmatrix} } = { a{\color{red}f} - {\color{red}e}c \over ad - bc}.$

The rules for 3×3 are similar. Given:

$ax + by + cz = {\color{red}j},\,$

$dx + ey + fz = {\color{red}k},\,$

$gx + hy + iz = {\color{red}l},\,$

which in matrix format is

$\begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}\begin{bmatrix} x \\ y \\ z \end{bmatrix}=\begin{bmatrix} {\color{red}j} \\ {\color{red}k} \\ {\color{red}l} \end{bmatrix}$

x, y and z can be found as follows:

$x = \frac { \begin{vmatrix} {\color{red}j} & b & c \\ {\color{red}k} & e & f \\ {\color{red}l} & h & i \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} }, \quad y = \frac { \begin{vmatrix} a & {\color{red}j} & c \\ d & {\color{red}k} & f \\ g & {\color{red}l} & i \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} },\text{ and }z = \frac { \begin{vmatrix} a & b & {\color{red}j} \\ d & e & {\color{red}k} \\ g & h & {\color{red}l} \end{vmatrix} } { \begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i \end{vmatrix} }.$

Finding solution of a system of linear equations in the general case

Consider a system of linear equations represented in matrix multiplication form as

$Ax = b\,$

$(1)\,$

where the square matrix $A$ is invertible and the vector $x = (x_1, \ldots, x_n)^\top$ is the column vector of the variables.

Then the theorem states that:

$x_i = \frac{\det(A_i)}{\det(A)} \qquad i = 1, \ldots, n \,$

where $A i$ is the matrix formed by replacing the ith column of $A$ by the column vector $b$ .

This formula is, however, of limited practical value for larger matrices, as there are other more efficient ways of solving systems of linear equations, such as by Gauss elimination or, even better, LU decomposition.

Finding inverse matrix

Let A be an n×n matrix. Then

$\mathrm{Adj}(A)A = \mathrm{det}(A)I\,$

where Adj(A) denotes the adjugate matrix of A, det(A) is the determinant, and I is the identity matrix. If det(A) is invertible in R, then the inverse matrix of A is

$A^{-1} = \frac{1}{\operatorname{det}(A)} \operatorname{Adj}(A).$

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. The formula is, however, of limited practical value for large matrices, as there are other more efficient ways of generating the inverse matrix, such as by Gauss–Jordan elimination.

Abstract formulation

The rule holds for systems of equations with coefficients and unknowns in any field, not just in the real numbers.

Applications to differential geometry

Cramer's rule is also extremely useful for solving problems in differential geometry. Consider the two equations $F(x, y, u, v) = 0\,$ and $G(x, y, u, v) = 0\,$ . When u and v are independent variables, we can define $x = X(u, v)\,$ and $y = Y(u, v).\,$

Finding an equation for $\dfrac{\partial x}{\partial u}$ is a trivial application of Cramer's rule.

First, calculate the first derivatives of F, G, x, and y:

$dF = \frac{\partial F}{\partial x} dx + \frac{\partial F}{\partial y} dy +\frac{\partial F}{\partial u} du +\frac{\partial F}{\partial v} dv = 0$

$dG = \frac{\partial G}{\partial x} dx + \frac{\partial G}{\partial y} dy +\frac{\partial G}{\partial u} du +\frac{\partial G}{\partial v} dv = 0$

$dx = \frac{\partial X}{\partial u} du + \frac{\partial X}{\partial v} dv$

$dy = \frac{\partial Y}{\partial u} du + \frac{\partial Y}{\partial v} dv.$

Substituting dx, dy into dF and dG, we have:

$dF = \left(\frac{\partial F}{\partial x} \frac{\partial x}{\partial u} +\frac{\partial F}{\partial y} \frac{\partial y}{\partial u} +\frac{\partial F}{\partial u} \right) du + \left(\frac{\partial F}{\partial x} \frac{\partial x}{\partial v} +\frac{\partial F}{\partial y} \frac{\partial y}{\partial v} +\frac{\partial F}{\partial v} \right) dv = 0$

$dG = \left(\frac{\partial G}{\partial x} \frac{\partial x}{\partial u} +\frac{\partial G}{\partial y} \frac{\partial y}{\partial u} +\frac{\partial G}{\partial u} \right) du + \left(\frac{\partial G}{\partial x} \frac{\partial x}{\partial v} +\frac{\partial G}{\partial y} \frac{\partial y}{\partial v} +\frac{\partial G}{\partial v} \right) dv = 0.$

Since u, v are both independent, the coefficients of du, dv must be zero. So we can write out equations for the coefficients:

$\frac{\partial F}{\partial x} \frac{\partial x}{\partial u} +\frac{\partial F}{\partial y} \frac{\partial y}{\partial u} = -\frac{\partial F}{\partial u}$

$\frac{\partial G}{\partial x} \frac{\partial x}{\partial u} +\frac{\partial G}{\partial y} \frac{\partial y}{\partial u} = -\frac{\partial G}{\partial u}$

$\frac{\partial F}{\partial x} \frac{\partial x}{\partial v} +\frac{\partial F}{\partial y} \frac{\partial y}{\partial v} = -\frac{\partial F}{\partial v}$

$\frac{\partial G}{\partial x} \frac{\partial x}{\partial v} +\frac{\partial G}{\partial y} \frac{\partial y}{\partial v} = -\frac{\partial G}{\partial v}.$

Now, by Cramer's rule, we see that:

$\frac{\partial x}{\partial u} = \frac{\begin{vmatrix} -\frac{\partial F}{\partial u} & \frac{\partial F}{\partial y} \\ -\frac{\partial G}{\partial u} & \frac{\partial G}{\partial y}\end{vmatrix}}{\begin{vmatrix}\frac{\partial F}{\partial x} & \frac{\partial F}{\partial y} \\ \frac{\partial G}{\partial x} & \frac{\partial G}{\partial y}\end{vmatrix}}.$

This is now a formula in terms of two Jacobians:

$\frac{\partial x}{\partial u} = - \frac{\left(\frac{\partial\left(F, G\right)}{\partial\left(u, y\right)}\right)}{\left(\frac{\partial\left(F, G\right)}{\partial\left(x, y\right)}\right)}.$

Similar formulae can be derived for $\frac{\partial x}{\partial v}$ , $\frac{\partial y}{\partial u}$ , $\frac{\partial y}{\partial v}.$

Applications to algebra

Cramer's rule can be used to prove the Cayley–Hamilton theorem of linear algebra, as well as Nakayama's lemma, which is fundamental in commutative ring theory.

Relevance to eigenvalues

Cramer's rule can be used to formulate the characteristic equation in eigenvalue problems. An eigenvector x is often expressed as

$(\lambda I - A) \mathbf{x} = 0.$

This can be viewed as a linear system of equations in which the coefficient matrix is the expression in the parentheses, the matrix of the unknowns is x, and the right hand side matrix is zero. According to Cramer's rule, solutions to x are expressed as a quotient. The numerator will always be zero, since here $b = 0\,$ (see Eq. 1). Hence to find the non-trivial solutions (not all zeros), the denominator must also equal zero; that is, the determinant of the coefficient matrix must be zero. Then the solutions of the equation are given by:

$\det( \lambda I - A) = 0 \,$

which is the familiar characteristic equation

Applications to integer programming

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 all integer has integer basic solutions. This makes the integer program substantially easier to solve.

Notes

This article needs additional citations for verification.
Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (August 2008)

^ Carl B. Boyer, A History of Mathematics, 2nd edition (Wiley, 1968), p. 431.

External links

Proof of Cramer's Rule

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	Year 1750 (in Science & Technology)
	Year 1748 (in Science & Technology)
	Gabriel Cramer

	How to solve linear Equations in 3 variables using Cramer's Rule? Read answer...
	What happens when Cramer's rule is applied to dependent or inconsistent systems? Read answer...
	What is Jim Cramer's net worth? Read answer...

	How is Cramers Rule used in life?
	What are some examples of Cramer's rule when its applied to dependent or inconsistent systems?
	C program for exponential curve fitting using cramer's rule?

		Sci-Tech Dictionary. McGraw-Hill Dictionary of Scientific and Technical Terms. Copyright © 2003, 1994, 1989, 1984, 1978, 1976, 1974 by McGraw-Hill Companies, Inc. All rights reserved. Read more
		Wikipedia. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article "Cramer's rule". Read more

Cramer's rule

Contents