Cramer's rule

From Knowino

Jump to: navigation, search

In mathematics, Cramer's rule gives a closed formula for the solution of a set of simultaneous linear equations. That is, Cramer's rule gives the solution in algebraic (as opposed to numeric) form of the following set of n equations with n unknowns:

$\begin{alignat}{3} a_{11} x_1& + a_{12} x_2 + a_{13} x_3 + \cdots &+ a_{1n}x_n &= b_1 \\ a_{21} x_1& + a_{22} x_2 + a_{23} x_3 + \cdots &+ a_{2n}x_n &= b_2 \\ a_{31} x_1& + a_{32} x_2 +\cdots \qquad \cdots&+ a_{3n}x_n &= b_3 \\ \cdots & \cdots & \\ a_{n1} x_1& + a_{n2} x_2 + a_{n3} x_3 + \cdots &+ a_{nn}x_n &= b_n \\ \end{alignat}$

Here the coefficients a_jk (j,k = 1,2,3, ..., n) and the right-hand sides b_k are assumed to be known and the problem to be solved by Cramer's rule is the computation of the n unknowns x_k (k = 1,2,3, ..., n). Very often all numbers involved are real, but the method works equally well for complex numbers.

Coupled linear equations appear in numerical engineering and physics, in statistics, economy, etc. The method of the Swiss mathematician Gabriel Cramer (1704 – 1752) is based on determinants and is therefore computationally not very convenient. The rule plays mainly a role in mathematical theories where an explicit expression for the solution of linear equations is required.

In practical numerical calculations, either by hand or by computer, the method of Gaussian elimination is to be preferred,

[edit] The rule and its derivation

The equations are most conveniently rewritten in matrix-vector notation:

$\mathbf{A}\; \mathbf{x} = \mathbf{b} \quad \Longleftrightarrow \quad x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2+ \cdots + x_n \mathbf{a}_n = \mathbf{b}\quad \Longleftrightarrow \quad \mathbf{b} = \sum_{k=1}^n x_k\; \mathbf{a}_k,$

where the matrix A, containing the elements a_jk, and the column vectors x and b are defined in the first equation. The matrix A consists of n columns a₁, a₂, ..., a_n.

Cramer's rule is based on the following two properties of determinants:

Linearity

$\begin{align} \vert \mathbf{a}_1\; \cdots \mathbf{a}_{k-1}\; (c\; \mathbf{d} + c'\mathbf{d'})\; \mathbf{a}_{k+1}\; \cdots \;\mathbf{a}_n\;\vert = c\; \vert \mathbf{a}_1\; \cdots \mathbf{a}_{k-1}\; \mathbf{d}\; \mathbf{a}_{k+1}\; \cdots \;\mathbf{a}_n\;\vert + c'\;\vert \mathbf{a}_1\; \cdots \mathbf{a}_{k-1}\; \mathbf{d'}\; \mathbf{a}_{k+1}\; \cdots \;\mathbf{a}_n\;\vert \end{align}$

where c and c′ are (real or complex) numbers, and d and d′ are arbitrary column vectors of n elements.

Vanishing: When two (or more) columns of a determinant are identical, the determinant vanishes.

Consider the determinant of A and replace column m by the right-hand side vector b:

$D_m:= \vert \mathbf{a}_1\; \cdots \mathbf{a}_{m-1}\; \mathbf{b} \; \mathbf{a}_{m+1}\; \cdots \;\mathbf{a}_n\;\vert = \vert \mathbf{a}_1\; \cdots \mathbf{a}_{m-1}\; \Big(x_1\mathbf{a}_1 + \cdots + x_n\mathbf{a}_n\Big)\; \mathbf{a}_{m+1}\; \cdots \;\mathbf{a}_n\;\vert$

From the vanishing condition it follows that out of all the terms between the parentheses only the column a_m survives. By the linearity condition x_m may be moved in front of the determinant:

$D_m = x_m \vert \mathbf{a}_1\; \cdots \mathbf{a}_{m-1}\; \mathbf{a}_m \; \mathbf{a}_{m+1}\; \cdots \mathbf{a}_n \vert = x_m \det(\mathbf{A}).$

Hence Cramer's rule

$x_m = \frac{D_m}{\det(\mathbf{A}) } = \frac{ \vert \mathbf{a}_1\; \cdots \mathbf{a}_{m-1}\; \mathbf{b} \; \mathbf{a}_{m+1}\; \cdots \;\mathbf{a}_n\;\vert } {\vert \mathbf{a}_1\; \cdots \mathbf{a}_{m-1}\; \mathbf{a}_m \; \mathbf{a}_{m+1}\; \cdots \;\mathbf{a}_n\;\vert }, \qquad m=1,2,\ldots, n.$

Clearly, the solution exists and is unique if and only if det(A) ≠ 0.

[edit] Example

Consider the following equations (n = 3):

$\begin{align} x + y + 2z &= 0 \\ 3x +y + 2z &= 2 \\ 2x - 2y + z &= -6 \\ \end{align}$

Compute the determinant of A:

$\det(\mathbf{A}) = \begin{vmatrix} 1 & \;\;1 & 2 \\ 3 & \;\;1 & 2 \\ 2 & -2 & 1 \\ \end{vmatrix} = \begin{vmatrix} \;\;1 & 2 \\ -2 & 1 \\ \end{vmatrix} - \begin{vmatrix} 3 & 2 \\ 2 & 1 \\ \end{vmatrix} +2 \begin{vmatrix} 3 & \;\;1 \\ 2 & -2 \\ \end{vmatrix} = 5 +1 -16 = -10$

Determine first x:

$-10 x = \begin{vmatrix} \;\;0 & \;\;1 & 2 \\ \;\;2 & \;\;1 & 2 \\ -6 & -2 & 1 \\ \end{vmatrix} = -\begin{vmatrix} \;\;2 & 2 \\ -6 & 1 \\ \end{vmatrix} + 2 \begin{vmatrix} \;\;2 & \;\;1 \\ -6 & -2 \\ \end{vmatrix} = -14 +4 = -10 \Longrightarrow x = \frac{-10}{-10} = 1$

Next y

$-10 y = \begin{vmatrix} 1 & \;\;0 & 2 \\ 3 & \;\;2 & 2 \\ 2 & -6 & 1 \\ \end{vmatrix} = \begin{vmatrix} \;\;2 & 2 \\ -6 & 1 \\ \end{vmatrix} + 2 \begin{vmatrix} 3 & \;\;2 \\ 2 & -6 \\ \end{vmatrix} = 14 -44 =-30 \Longrightarrow y = \frac{-30}{-10} = 3$

Finally z:

$-10 z = \begin{vmatrix} 1 & \;\;1 & \;\;0 \\ 3 & \;\;1 & \;\;2 \\ 2 & -2 & -6 \\ \end{vmatrix} = \begin{vmatrix} \;\;1 &\;\; 2 \\ -2 & -6 \\ \end{vmatrix} - \begin{vmatrix} 3 & \;\;2 \\ 2 & -6 \\ \end{vmatrix} = -2 +22 =20 \Longrightarrow z = \frac{20}{-10} = -2$

Final solution

$\begin{pmatrix} x \\ y\\ z \end{pmatrix} = \begin{pmatrix} \;\;1 \\\;\; 3\\ -2 \end{pmatrix}$

See Gaussian elimination for the solution of the very same equations.

Cramer's rule

[edit] The rule and its derivation

[edit] Example

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Community

Toolbox