Cramer's Rule is an exact method for determining the solution to a system of simultaneous linear equations. Consider a system of 2 equations in 2 variables:
a11 x1 + a12 x2 = b1
a21 x1 + a22 x2 = b2
To solve this system of equations, we look for the solution for each variable. Suppose we solve for x1 first. Eliminate x2 by multiplying each equation with the coefficient (or product of the coefficients, in the case of n > 2) of the other equations.
| (a11 x1 + a12 x2 | = | b1) | a22 | |
|---|---|---|---|---|
| (a21 x1 + a22 x2 | = | b2) | – a12 | |
| a11 a22 x1 + a12 a22 x2 | = | a22 b1 | ||
| – a12 a21 x1 – a12 a22 x2 | = | – a12 b2 | ||
| (a11 a22 – a12 a21) x1 | = | a22 b1 – | a12 b2 | |
| x1 | = | (a22 b1 – | a12 b2) / (a11 a22 – a12 a21) | |
Doing the same thing for x2, we have
| (a11 x1 + a12 x2 | = | b1) | a21 | |
|---|---|---|---|---|
| (a21 x1 + a22 x2 | = | b2) | – a11 | |
| a11 a21 x1 + a12 a21 x2 | = | a21 b1 | ||
| – a11 a21 x1 – a11 a22 x2 | = | – a11 b2 | ||
| (a11 a22 – a12 a21) x2 | = | a11 b2 – | a21 b1 | |
| x2 | = | (a11 b2 – | a21 b1) / (a11 a22 – a12 a21) | |
Observe that
| x1 |
= |
a22 b1 – a12 b2 a11 a22 – a12 a21 |
= |
|A| |
||||
|---|---|---|---|---|---|---|---|---|
| x2 |
= |
a11 b2 – a21 b1 a11 a22 – a12 a21 |
= |
|A| |
||||
Cramer's Rule states that if
an x n x Xn x 1 = Bn x 1
is a system of simultaneous linear equations, then
| xk = | |B(k)| |
|---|
where B(k) is a matrix obtained from A by replacing the kth column of A with B for k = 1, 2, . . . , n.
EXAMPLE: Consider a system of simultaneous linear equations in 2 variables:
| 3 x | – | y | = | 7 | ||
|---|---|---|---|---|---|---|
| 2 x | – | 4y | = | – | 2 |
| æ è |
3 2 |
– 1 – 4 |
ö ø |
æ è |
x y |
ö ø |
= | æ è |
7 – 2 |
ö ø |
|---|
| |A| = | | | |
3 2 |
– 1 – 4 |
| | |
= – 12 + 2 | = – 10 |
|---|---|---|---|---|---|---|
| |B(1)| = | | | |
7 – 2 |
– 1 – 4 |
| | |
= – 28 – 2 | = – 30 |
| |B(2)| = | | | |
3 2 |
7 – 2 |
| | |
= – 6 – 14 | = – 20 |
| x1 = | |B(1)| |
= | – 30 – 10 |
= 3 |
|---|---|---|---|---|
| x2 = | |B(2)| |
= | – 20 – 10 |
= 2 |
EXAMPLE: Consider a system of simultaneous linear equations in 3 variables using the diagonal method to calculate determinants:
| 3x1 | + | x2 | – | x3 | = | 2 | |
|---|---|---|---|---|---|---|---|
| x1 | + | 2x2 | + | x3 | = | 3 | |
| – | x1 | + | x2 | + | 4x3 | = | 9 |
|
æ ç è |
3 1 – 1 |
1 2 1 |
– 1 1 4 |
ö ÷ ø |
æ ç è |
x1 x2 x3 |
ö ÷ ø |
= |
æ ç è |
2 3 9 |
ö ÷ ø |
|---|
| |A| = | | | | |
3 1 – 1 |
1 2 1 |
– 1 1 4 |
| | | |
3 1 – 1 |
1 2 1 |
= ( 24 – 1 – 1 ) – ( 2 + 3 + 4 ) | = 22 – 9 | = 13 |
|---|---|---|---|---|---|---|---|---|---|---|
| |B(1)| = | | | | |
2 3 9 |
1 2 1 |
– 1 1 4 |
| | | |
2 3 9 |
1 2 1 |
= ( 16 + 9 – 3 ) – ( – 18 + 2 + 12 ) | = 22 + 4 | = 26 |
| |B(2)| = | | | | |
3 1 – 1 |
2 3 9 |
– 1 1 4 |
| | | |
3 1 – 1 |
2 3 9 |
= ( 36 – 2 – 9 ) – ( 3 + 27 + 8 ) | = 25 – 38 | = – 13 |
| |B(3)| = | | | | |
3 1 – 1 |
1 2 1 |
2 3 9 |
| | | |
3 1 – 1 |
1 2 1 |
= ( 54 – 2 + 2 ) – ( – 4 + 9 + 9 ) | = 53 – 14 | = 39 |
| x1 = | |B(1)| |
= | 26 13 |
= 2 |
|---|---|---|---|---|
| x2 = | |B(2)| |
= | – 13 13 |
= – 1 |
| x3 = | |B(3)| |
= | 39 13 |
= 3 |
EXAMPLE: Consider the same system of simultaneous linear equations in 3 variables using the cofactors to calculate determinants:
| 3x1 | + | x2 | – | x3 | = | 2 | |
|---|---|---|---|---|---|---|---|
| x1 | + | 2x2 | + | x3 | = | 3 | |
| – | x1 | + | x2 | + | 4x3 | = | 9 |
|
æ ç è |
3 1 – 1 |
1 2 1 |
– 1 1 4 |
ö ÷ ø |
æ ç è |
x1 x2 x3 |
ö ÷ ø |
= |
æ ç è |
2 3 9 |
ö ÷ ø |
|---|
| |A| = | | | | |
3 1 – 1 |
1 2 1 |
– 1 1 4 |
| | | |
¬ i = 2 |
|---|---|---|---|---|---|---|
| |A| = | [ 1 (– 1)2+1 (4 + 1) ] + [ 2 (– 1)2+2 (12 – 1) ] + [ 1 (– 1)2+3 (3 + 1) ] | |||||
| |A| = | – 5 + 22 – 4 | |||||
| |A| = | 13 | |||||
| |B(1)| = | | | | |
2 3 9 |
1 2 1 |
– 1 1 4 |
| | | |
¬ i = 1 |
| |B(1)| = | [ 2 (–1)1+1 (8 –1) ] + [ 1 (–1)1+2 (12 – 9) ] + [ – 1 (–1)1+3 (3 – 18) ] | |||||
| |B(1)| = | 14 – 3 + 15 | |||||
| |B(1)| = | 26 | |||||
| |B(2)| = | | | | |
3 1 – 1 |
2 3 9 |
– 1 1 4 |
| | | |
¬ i = 2 |
| |B(2)| = | [ 1 (–1)2+1 (8 + 9) ] + [ 2 (–1)2+2 (12 – 1) ] + [ 1 (–1)2+3 (27 + 2) ] | |||||
| |B(2)| = | – 17 + 33 – 29 | |||||
| |B(2)| = | – 13 | |||||
| |B(3)| = | | | | |
3 1 – 1 |
1 2 1 |
2 3 9 |
| | | |
¬ i = 1 |
| |B(3)| = | [ 3 (–1)1+1 (18 – 3) ] + [ 1 (–1)1+2 (9 + 3) ] + [ 2 (–1)1+3 (1 + 2) ] | |||||
| |B(3)| = | 45 – 12 + 6 | |||||
| |B(3)| = | 39 | |||||
| x1 = | |B(1)| |
= | 26 13 |
= | 2 |
|---|---|---|---|---|---|
| x2 = | |B(2)| |
= | – 13 13 |
= | – 1 |
| x3 = | |B(3)| |
= | 39 13 |
= | 3 |
PROBLEM: Develop an algorithm, expressed as a NSD, that will find the exact solution to a system of simultaneous linear equations in n variables using matrices and the Cramer's Rule.