CAGD-banner.gif
On-Line Geometric Modeling Notes
CRAMER'S RULE


Overview

Cramer's Rule is a determinant-based procedure utilized to solve systems of equations. In these notes we first discuss Cramer's Rule for systems of three linear equations with three unknowns and then state the Cramer's rule for general systems of equations.


Cramer's Rule - Three Equations, Three Unknowns

Given a system of three linear equations, with three unknowns,

\begin{displaymath}\begin{aligned}d_1 & = a_1 x + b_1 y + c_1 z \\  d_2 & = a_2 x + b_2 y + c_2 z \\  d_3 & = a_3 x + b_3 y + c_3 z \end{aligned}\end{displaymath}

Cramer's Rule depends on the calculation of four determinants. If we define $ D$ to be the determinant defined by

$\displaystyle D \: = \:
\begin{vmatrix}
a_1 & a_2 & a_3 \\
b_1 & b_2 & b_3 \\
c_1 & c_2 & c_3
\end{vmatrix}$

and the determinants $ D_1$, $ D_2$ and $ D_3$, to be

$\displaystyle D_1 \: = \:
\begin{vmatrix}
d_1 & d_2 & d_3 \\
b_1 & b_2 & b_3 \\
c_1 & c_2 & c_3
\end{vmatrix}$

$\displaystyle D_2 \: = \:
\begin{vmatrix}
a_1 & a_2 & a_3 \\
d_1 & d_2 & d_3 \\
c_1 & c_2 & c_3
\end{vmatrix}$

$\displaystyle D_3 \: = \:
\begin{vmatrix}
a_1 & a_2 & a_3 \\
b_1 & b_2 & b_3 \\
d_1 & d_2 & d_3
\end{vmatrix}$

respectively, then Cramer's rule states that

\begin{displaymath}\begin{aligned}x & = \frac{D_1}{D} \\  y & = \frac{D_2}{D} \\  z & = \frac{D_3}{D} \end{aligned}\end{displaymath}

Note that the determinants are easily generated. The columns of $ D$ are just the coefficients of $ x$, $ y$ and $ z$ respectively in the linear equations and $ D_i$ is produced by replacing the $ i$th row by the row $ \left[ \begin{array}{ccc} d_1 & d_2 & d_3 \end{array} \right]$


Example

Suppose we are given a point $ {\bf P} $ in space and a frame $ {\cal F} = ( {\vec u} , {\vec v} , {\vec w} , {\bf O} )$. By the definition of a frame, the point $ {\bf P} $ can be written

$\displaystyle {\bf P} = u {\vec u} + v {\vec v} + w {\vec w} + {\bf O}
$

and suppose we wish to find the coefficients $ (u,v,w)$ so that this is true. Now, $ {\bf P} - {\bf O} $ is a vector, and so we can write down the equations

\begin{displaymath}\begin{aligned}x_{po} & = x_u u + x_v v + x_w w \\  y_{po} & ...
..._v v + y_w w \\  z_{po} & = z_u u + z_v v + z_w w \end{aligned}\end{displaymath}

where the $ <x_{po},y_{po},z_{po}>$ is the cartesian coordinate representation of $ {\bf P} - {\bf O} $, $ <x_u,y_u,z_u>$ is the representation of $ {\vec u} $, $ <x_v,y_v,z_v>$ is the representation of $ {\vec v} $ and $ <x_w,y_w,z_w>$ is the representation of $ {\vec w} $. By Cramer's Rule, we can solve this by defining the following four determinants

$\displaystyle D \: = \:
\begin{vmatrix}
x_u & y_u & z_u \\
x_v & y_v & z_v \\
x_w & y_w & z_w
\end{vmatrix}$

$\displaystyle D_1 \: = \:
\begin{vmatrix}
x_{po} & y_{po} & z_{po} \\
x_v & y_v & z_v \\
x_w & y_w & z_w
\end{vmatrix}$

$\displaystyle D_2 \: = \:
\begin{vmatrix}
x_u & y_u & z_u \\
x_{po} & y_{po} & z_{po} \\
x_w & y_w & z_w
\end{vmatrix}$

$\displaystyle D_3 \: = \:
\begin{vmatrix}
x_u & y_u & z_u \\
x_v & y_v & z_v \\
x_{po} & y_{po} & z_{po}
\end{vmatrix}$

and then

\begin{displaymath}\begin{aligned}u & = \frac{D_1}{D} \\  v & = \frac{D_2}{D} \\  w & = \frac{D_3}{D} \end{aligned}\end{displaymath}


The Homogeneous Case

Given a system of three linear equations, with three unknowns,

\begin{displaymath}\begin{aligned}d_1 & = a_1 x + b_1 y + c_1 z \\  d_2 & = a_2 x + b_2 y + c_2 z \\  d_3 & = a_3 x + b_3 y + c_3 z \end{aligned}\end{displaymath}

then the system is called homogeneous if $ d_1 = d_2 = d_3 = 0$. In this case, if $ D \not = 0$, then Cramer's rule above gives the solution $ x = y = z = 0$ - the trivial solution. However, if $ D = 0$, then the rank of the coefficient matrix is less than 3, and the system will have non-trivial solutions.


The Example without Determinants

If we look closely at the determinants in the above example, we can see that they can actually be expressed in terms of the vectors $ {\vec u} $, $ {\vec v} $, $ {\vec w} $, and $ {\bf P} - {\bf O} $. In particular,

\begin{displaymath}\begin{aligned}D & = {\vec u} \cdot ( {\vec v} \times {\vec w...
...dot ( {\vec v} \times ( {\bf P} - {\bf O} ) ) \\  \end{aligned}\end{displaymath}

Thus, in this case, we can eliminate the determinants and utilize dot and cross products.


If Everything is Nice

It is worth looking at the vector-based Cramer's rule one more time for the case when the frame $ {\cal F} =( {\vec u} , {\vec v} , {\vec w} , {\bf O} )$ is orthonormal. If the vectors are all mutually perpendicular and of unit length then the above equations simplify significantly . In particular, if we assume that

\begin{displaymath}\begin{aligned}{\vec u} & = {\vec v} \times {\vec w} \\  {\ve...
...\vec u} \\  {\vec w} & = {\vec u} \times {\vec v} \end{aligned}\end{displaymath}

which is the case in a right-handed orthonormal system, we have

\begin{displaymath}\begin{aligned}D & = {\vec u} \cdot ( {\vec v} \times {\vec w} ) \\  & = {\vec u} \cdot {\vec u} \\  & = 1 \end{aligned}\end{displaymath}

\begin{displaymath}\begin{aligned}D_1 & = ( {\bf P} - {\bf O} ) \cdot ( {\vec v}...
...w} ) \\  & = ( {\bf P} - {\bf O} ) \cdot {\vec u} \end{aligned}\end{displaymath}

\begin{displaymath}\begin{aligned}D_2 & = {\vec u} \cdot ( ( {\bf P} - {\bf O} )...
...O} ) \\  & = ( {\bf P} - {\bf O} ) \cdot {\vec v} \end{aligned}\end{displaymath}

\begin{displaymath}\begin{aligned}D_3 & = {\vec u} \cdot ( {\vec v} \times ( {\b...
...O} ) \\  & = ( {\bf P} - {\bf O} ) \cdot {\vec w} \end{aligned}\end{displaymath}

Summarizing this case, it is clear that we only need dot products to calculate the determinants.

\begin{displaymath}\begin{aligned}D & = 1 \\  D_1 & = ( {\bf P} - {\bf O} ) \cdo...
... D_3 & = ( {\bf P} - {\bf O} ) \cdot {\vec w} \\  \end{aligned}\end{displaymath}

No cross products are required.


The General Cramer's Rule

Given a system of $ n$ linear equations

\begin{displaymath}\begin{aligned}a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n ...
...1} x_1 + a_{n2} x_2 + \cdots + a_{nn} x_n & = b_n \end{aligned}\end{displaymath}

If the determinant $ D$ of the coefficient matrix is not zero then the system has precisely one solution. This solution is given by the formulas

\begin{displaymath}\begin{aligned}x_1 & = \frac{D_1}{D} \\  x_2 & = \frac{D_2}{D} \\  & \vdots \\  x_n & = \frac{D_n}{D} \end{aligned}\end{displaymath}

where $ D_k$ is the determinant obtained from $ D$ by replacing the $ k$th row of $ D$ by the row with the entries

$\displaystyle \left[
\left[ \begin{array}{cccc}
b_1 & b_2 & \vdots & b_n
\end{array} \right]
\right]
$

Also, if the system is homogeneous and $ D \not = 0$, then it has only the trivial solution $ x_1 = x_2 = \cdots = x_n = 0$. If $ D = 0$, the homogeneous system has nontrivial solutions.


Bibliography


\begin{singlespace}
\noindent
\footnotesize\bfseries All contents copyright (c) ...
...ment, University of California, Davis \\
All rights reserved.
\end{singlespace}


Ken Joy
2000-11-28