Cramer's Rule and Gaussian Elimination

The two main practical methods for solving systems of linear equations are Cramer's rule (via determinants) and Gaussian elimination (successively eliminating unknowns). Cramer's rule applies only to square, nonsingular systems; Gaussian elimination is universal.

For illustration, take the same system throughout:

⎩ ⎨ ⎧ x + y + z = 6 2 x - y + z = 3 x + 2 y - z = 2 A = 121 1 - 1 2 11 - 1, B = 632 .

Cramer's Rule

Theorem (Cramer). If the determinant of a square system $A X = B$ is nonzero, $Δ = det A \neq = 0$ , then the system is determinate (has a unique solution), and

x_{i} = \frac{Δ _{i}}{Δ}, i = \overline{1, n},

where $Δ_{i}$ is the determinant obtained from $Δ$ by replacing the $i$ -th column with the column of constant terms $B$ .

Proof. When $det A \neq = 0$ , the inverse matrix exists, and $X = A^{- 1} B = \frac{1}{Δ} A B$ . Expanding the product of the adjugate matrix $A$ with $B$ row by row, the $i$ -th coordinate is

x_{i} = \frac{A _{1 i} b _{1} + A _{2 i} b _{2} + \dots + A _{ni} b _{n}}{Δ},

and the numerator is exactly the expansion of the determinant $Δ_{i}$ along its $i$ -th column (the column of $b_{1}, \dots, b_{n}$ ).

Example. For our system,

Δ = 121 1 - 1 2 11 - 1 = 7.

Replacing the columns in turn with $B = (6, 3, 2)^{T}$ :

Δ_{1} = 632 1 - 1 2 11 - 1 = 7, Δ_{2} = 121632 11 - 1 = 14, Δ_{3} = 121 1 - 1 2 632 = 21.

Hence

x = \frac{Δ _{1}}{Δ} = 1, y = \frac{Δ _{2}}{Δ} = 2, z = \frac{Δ _{3}}{Δ} = 3.

Limitations. Cramer's rule works only for a square system with $det A \neq = 0$ , and requires computing $n + 1$ determinants of order $n$ — expensive for large $n$ . In practice, Gaussian elimination is used more often.

Gaussian Elimination

The idea: use elementary row transformations on the augmented matrix $\overline{A} = (A ∣ B)$ to bring the system to row-echelon (triangular) form — the forward pass — and then successively find the unknowns from the bottom up — the back substitution. Elementary transformations do not change the solution set.

Example (the same system). Forward pass:

121 1 - 1 2 11 - 1 632 R_{2} - 2 R_{1} R_{3} - R_{1} 100 1 - 3 1 1 - 1 - 2 6 - 9 - 4 R_{2} \leftrightarrow R_{3} R_{3} + 3 R_{2} 100110 1 - 2 - 7 6 - 4 - 21 .

Back substitution:

- 7 z = - 21 \Rightarrow z = 3; y - 2 z = - 4 \Rightarrow y = 2; x + y + z = 6 \Rightarrow x = 1.

We get the same solution $x = 1, y = 2, z = 3$ .

The Gauss–Jordan method. If we continue the transformations and also zero out the entries above the leading ones, reducing the left-hand side to the identity matrix (reduced row-echelon form), the solution can be read off directly — no back substitution needed.

The general case. Gaussian elimination works for any $m \times n$ system. As the transformations proceed, the rank and type of the system become apparent immediately (cf. the Kronecker–Capelli theorem):

a row $(0 \dots 0 ∣ β)$ with $β \neq = 0$ — the system is inconsistent;
after discarding zero rows, $r$ rows remain: if $r = n$ the solution is unique; if $r < n$ , we express $r$ basic unknowns through $n - r$ free ones and obtain the general solution (infinitely many solutions).

Comparing the Methods

	Cramer's Rule	Gaussian Elimination
Applicability	only square, $det A \neq = 0$	any $m \times n$
What it gives	a unique solution by formula	full analysis + all solutions
Cost	$n + 1$ determinants of order $n$ (expensive)	$\sim n^{3}$ operations (efficient)

Cramer's Rule

Gaussian Elimination

Comparing the Methods

Related works