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 ajk (j,k = 1,2,3, ..., n) and the right-hand sides bk are assumed to be known and the problem to be solved by Cramer's rule is the computation of the n unknowns xk (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,

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 ajk, and the column vectors x and b are defined in the first equation. The matrix A consists of n columns a1, a2, ..., an.

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


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

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 am survives. By the linearity condition xm 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.

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.

Personal tools
Variants
Actions
Navigation
Community
Toolbox