Row Reduction

$$\begin{alignat*}{4} 15 x_{1}&+&2 x_{2}&-&5 x_{3}& = & 11 \\ 5 x_{1}&&&-&7 x_{3}& = & 12 \\ 7 x_{1}&+&7 x_{2}&-&5 x_{3}& = & 0 \\ \end{alignat*}$$

Gaussian Elimination

A system of linear equations may be solved (or shown to have no solutions) by the method of Gaussian elimination. The basic steps are elementary row operations: (i) Add a multiple of one equation to another, (ii) multiply an equation by a non-zero scalar, or (iii) exchange a pair of equations.

The goal is recursively to solve for some variables in terms of the remaining variables. For example, suppose the variable $x_{1}$ appears in some equation. If necessary, exchange a pair of equations so that $x_{1}$ appears in the first equation. Now divide the first equation by the coefficient of $x_{1}$, and add multiples of the first equation to the other equations, eliminating $x_{1}$ from each. Mentally crossing out the first equation yields a system with one fewer equations and one fewer variables than the original. Repeat this process until as many variables as possible have been eliminated.

The program randomly generates a system of $m$ equations in $n$ variables (up to ten of each). If the number of variables is at least as large as the number of equations, then “most of the time” the resulting system has a solution. (The elimination algorithm can be carried out to completion whether or not a solution exists.)

The coefficients of the initial system are integers, so row operations can be expressed in terms of rational numbers (fractions). Multipliers may be input as fractions or decimals, e.g., -45/113 or 3.875.