Linear Algebra/Cramer's Rule

From Wikibooks, open books for an open world
< Linear Algebra
Jump to: navigation, search

Cramer's Rule[edit]

Let's try to solve the systems of linear equations:
a11x1+a12x2+a13x3+...+a1nxn=b1
a21x1+a22x2+a23x3+...+a2nxn=b2
a31x1+a32x2+a33x3+...+a3nxn=b3
...
an1x1+an2x2+an3x3+...+annxn=bn

Which is the special case when the number of equations and the number of variables are the same.

Consider the matrix

\begin{bmatrix}
a_{11} & a_{12} & a_{13} & \ldots & a_{1n} \\
a_{21} & a_{22} & a_{23} & \ldots & a_{2n} \\
a_{31} & a_{32} & a_{33} & \ldots & a_{3n} \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
a_{n1} & a_{n2} & a_{n3} & \ldots & a_{nn} \\
\end{bmatrix}

to be denoted D.

First, we multiply the nth equation by the cofactor Co(anj) for the jth column, and add it all up. This gets us

Co(a1j)a11x1+Co(a1j)a12x2+Co(a1j)a13x3+...+Co(a1j)a1nxn+
Co(a2j)a21x1+Co(a2j)a22x2+Co(a2j)a23x3+...+Co(a2j)a2nxn+
Co(a3j)a31x1+Co(a3j)a32x2+Co(a3j)a33x3+...+Co(a3j)a3nxn+
+...+
Co(anj)an1x1+Co(anj)an2x2+Co(anj)an3x3+...+Co(anj)annxn
=
Co(a1j)b1+Co(a2j)b2+Co(a3j)b3+...+Co(anj)bn.

The left side cancels out except for Co(a1j)a1jxj+Co(a2j)a2jxj+Co(a3j)a3jxj+...+Co(anj)anjxj

which is equal to x_j \begin{bmatrix}
a_{11} & a_{12} & a_{13} & \ldots & a_{1n} \\
a_{21} & a_{22} & a_{23} & \ldots & a_{2n} \\
a_{31} & a_{32} & a_{33} & \ldots & a_{3n} \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
a_{n1} & a_{n2} & a_{n3} & \ldots & a_{nn} \\
\end{bmatrix}=D

and the right side is equal to

\begin{bmatrix}
a_{11} & a_{12} & a_{13} & \ldots & b_1 & \ldots & a_{1n} \\
a_{21} & a_{22} & a_{23} & \ldots & b_2 & \ldots & a_{2n} \\
a_{31} & a_{32} & a_{33} & \ldots & b_3 & \ldots & a_{3n} \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
a_{n1} & a_{n2} & a_{n3} & \ldots & b_n & \ldots & a_{nn} \\
\end{bmatrix}, to be denoted D(j), which is the same thing as D but with the jth column replaced by bk.

Dividing by D gets xj=\frac{D_j}{D}.

This formula is called Cramer's Rule, and this solution exists when D is not equal to 0.

In particular, in the process of finding the solution, we also find that this is the only solution, so this solution is unique.

Example[edit]

Consider the system of linear equations below.
3x_1 + 2x_2 - 5x_3 = 15
5x_1 + x_3 = 23
x_2 + x_3 = 12

If we only want the solution for, say, x_2, we can apply Cramer's Rule to find that its solution is \frac {D_2}{D}, and since we know
D_2=\begin{bmatrix} 3 & 15 & -5 \\ 5 & 23 & 1 \\ 0 & 12 & 1\end{bmatrix},
x_{2} = \frac{\det\begin{bmatrix} 3 & 15 & -5 \\ 5 & 23 & 1 \\ 0 & 12 & 1\end{bmatrix}}{\det\begin{bmatrix} 3 & 2 & -5 \\ 5 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}} = 9.