NationMaster - Encyclopedia: Cramer's rule

Cramer's rule is a theorem in linear algebra, which gives the solution of a system of linear equations in terms of determinants. 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 Algebra (and probably knew of the method as early as 1729).^[1] Look up theorem in Wiktionary, the free dictionary. ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear maps (also called linear transformations), and systems of linear equations. ... In mathematics and linear algebra, a system of linear equations is a set of linear equations such as A standard problem is to decide if any assignment of values for the unknowns can satisfy all three equations simultaneously, and to find such an assignment if it exists. ... In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every nÃ—n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ... Gabriel Cramer Gabriel Cramer (July 31, 1704 - January 4, 1752) was a Swiss mathematician, born in Geneva. ... Colin Maclaurin Colin Maclaurin (February, 1698 - June 14, 1746) was a Scottish mathematician. ...

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. In numerical analysis, pivoting is a process performed on a matrix in order to improve numerical stability, particularly in Gaussian elimination. ... In linear algebra, Gaussian elimination is an algorithm that can be used to determine the solutions of a system of linear equations, to find the rank of a matrix, and to calculate the inverse of an invertible square matrix. ... -1...

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 Elementary formulation
2 Abstract formulation
3 Example
4 Applications to differential geometry
5 Applications to algebra
6 Applications to integer programming
7 References
8 External links

Image File history File links Wikibooks-logo-en. ... Wikibooks logo Wikibooks, previously called Wikimedia Free Textbook Project and Wikimedia-Textbooks, is a wiki for the creation of books. ...

Elementary formulation

The system of equations is represented in matrix multiplication form as:

$mathbf{Ax} = mathbf{c},$

where the square matrix $mathbf{A}$ is invertible and the vector $mathbf{x}$ is the column vector of the variables: $(x i)$ . For the square matrix section, see square matrix. ... In mathematics and especially linear algebra, an n-by-n matrix A is called invertible, non-singular or regular if there exists another n-by-n matrix B such that AB = BA = In, where In denotes the n-by-n identity matrix and the multiplication used is ordinary matrix multiplication. ...

The theorem then states that:

$x_i = { det(mathbf{A}_i) over det(mathbf{A})}$

$(1),$

where $mathbf{A}_i$ is the matrix formed by replacing the ith column of $mathbf{A}$ by the column vector $mathbf{c}$ . For simplicity, a single symbol like $Δ$ is sometimes used to represent $det(mathbf{A})$ and the notation $Δ i$ is used to represent $det(mathbf{A}_i)$ . Thus, Equation (1) can be compactly written as

$x_i = { Delta_i over Delta }.$

Abstract formulation

Let R be a commutative ring, A an n×n matrix with coefficients in R. Then In ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation obeys the commutative law. ...

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

where Adj(A) denotes the adjugate of A, det(A) is the determinant, and I is the identity matrix. In linear algebra, the adjugate or classical adjoint of a square matrix is a matrix which plays a role similar to the inverse of a matrix; it can however be defined for any square matrix without the need to perform any divisions. ... In linear algebra, the identity matrix of size n is the n-by-n square matrix with ones on the main diagonal and zeros elsewhere. ...

Example

Consider the linear system

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

$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},$ and

$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 like so:

$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} }$ , $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} }$ , 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} }$

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 $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: For the French Revolution faction, see Jacobin. ...

$frac{partial x}{partial u} = - frac{left(frac{partialleft(F, Gright)}{partialleft(y, uright)}right)}{left(frac{partialleft(F, Gright)}{partialleft(x, yright)}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. In linear algebra, the Cayley-Hamilton theorem (named after the mathematicians Arthur Cayley and William Hamilton) states that every square matrix over the real or complex field, satisfies its own characteristic equation. ... In mathematics, Nakayamas lemma is an important technical lemma in commutative algebra and algebraic geometry. ...

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. In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... In mathematics, a unimodular matrix is a square matrix with determinant +1 or -1. ...

References

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

External links

MIT Linear Algebra Lecture on Cramer's Rule at Google Video, from MIT OpenCourseWare

I HATE MATH

Categories: Linear algebra | Mathematical theorems | Determinants

Results from FactBites:

Cramer's Rule (744 words)
	Cramer's Rule is stated in terms of the determinant...
	Cramer's rule is a venerable but, except in special circumstances, mostly useless method for solving systems of equations.
	Cramer's rule states that the solutions for ax cy=e and bx dy=f are given by the determinant solutions...

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

Elementary formulation GA_googleFillSlot("encyclopedia_square");