Cramer's rule: Definition from Answers.com

Wikipedia: 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).

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

Elementary formulation

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

$Ax = c\,$

where the square matrix $A$ is invertible and the vector $x$ is the column vector of the variables: $(x i)$ .

The theorem then states that:

$x_i = { \det(A_i) \over \det(A)}$

$(1)\,$

where $A i$ is the matrix formed by replacing the ith column of $A$ by the column vector $c$ . For simplicity, sometimes a single symbol like $Δ$ is used to represent $det(A)$ and the notation $Δ i$ is used to represent $det(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

$\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.

Example

A good way to use Cramer's rule on a 2×2 matrix is to use this formula:

Given

Failed to parse (unknown function\color): ax + by = {\color{red}e}\,

and

Failed to parse (unknown function\color): cx + dy = {\color{red}f}\,

, which in matrix format is

Failed to parse (unknown function\color): \begin{bmatrix} a & b \\ c & d \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix}=\begin{bmatrix} {\color{red}e} \\ {\color{red}f} \end{bmatrix}

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

Failed to parse (unknown function\color): 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

Failed to parse (unknown function\color): 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

Failed to parse (unknown function\color): ax + by + cz = {\color{red}j}\,

Failed to parse (unknown function\color): dx + ey + fz = {\color{red}k}\,

and

Failed to parse (unknown function\color): gx + hy + iz = {\color{red}l}\,

, which in matrix format is

Failed to parse (unknown function\color): \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:

Failed to parse (unknown function\color): 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} }

, Failed to parse (unknown function\color): 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 Failed to parse (unknown function\color): 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:

$\frac{\partial x}{\partial u} = - \frac{\left(\frac{\partial\left(F, G\right)}{\partial\left(y, u\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.

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.

External links

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

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

Cramer's rule