Linear Systems and Gauss's Method

Linear Systems

A linear equation in variables $x_1, x_2, \ldots, x_n$ has the form

$$a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b$$

where the coefficients $a_i$ and the right-hand side $b$ are constants. A linear system is a collection of $m$ such equations that must hold simultaneously.

Three outcomes are possible for any linear system:

• Unique solution — exactly one assignment of values satisfies all equations
• No solution — the equations are inconsistent (a contradictory equation appears during reduction)
• Infinitely many solutions — at least one variable is free to range over $\mathbb{R}$

No other outcome is possible. This trichotomy is a theorem, not an assumption.

Matrix Form

A linear system is compactly written as $A\vec{x} = \vec{b}$, where $A$ is the $m \times n$ coefficient matrix, $\vec{x}$ is the column vector of unknowns, and $\vec{b}$ is the column vector of right-hand sides.

The augmented matrix $[A \mid \vec{b}]$ packages the coefficient matrix and right-hand side together:

$$\left[\begin{array}{ccc|c} a_{11} & \cdots & a_{1n} & b_1 \\ \vdots & & \vdots & \vdots \\ a_{m1} & \cdots & a_{mn} & b_m \end{array}\right]$$

All row operations are performed on the augmented matrix — we never need to write the variable names explicitly during elimination.

Row Operations

Three elementary row operations transform a system without changing its solution set:

The swap and scale operations are preparatory. The workhorse is the row combination: adding a multiple of one row to another is what actually eliminates variables.

Gauss's Method (Row Reduction)

Gauss's method applies row combinations to produce a staircase pattern where each row's first nonzero entry — called the pivot or leading entry — is strictly to the right of the pivot in the row above. This form is called echelon form (or row echelon form).

Algorithm

1. Find the leftmost column with a nonzero entry. Swap rows if needed to place a nonzero entry at the top of that column.
2. Use row combinations to zero out all entries below the pivot.
3. Cover the top row and repeat on the remaining submatrix.
4. Stop when no rows remain or all remaining rows are zero.

Example

Solve the $3 \times 3$ system:

$$\begin{array}{rcrcrcl} x & + & y & + & z & = & 6 \\ 2x & + & y & - & z & = & 1 \\ x & - & y & + & 2z & = & 5 \end{array}$$

Augmented matrix and reduction:

$$\left[\begin{array}{rrr|r} 1 & 1 & 1 & 6 \\ 2 & 1 & -1 & 1 \\ 1 & -1 & 2 & 5 \end{array}\right] \xrightarrow{-2\rho_1 + \rho_2,\;-\rho_1 + \rho_3} \left[\begin{array}{rrr|r} 1 & 1 & 1 & 6 \\ 0 & -1 & -3 & -11 \\ 0 & -2 & 1 & -1 \end{array}\right]$$

$$\xrightarrow{-2\rho_2 + \rho_3} \left[\begin{array}{rrr|r} 1 & 1 & 1 & 6 \\ 0 & -1 & -3 & -11 \\ 0 & 0 & 7 & 21 \end{array}\right]$$

This is echelon form. Back-substitution:

• Row 3: $7z = 21 \Rightarrow z = 3$
• Row 2: $-y - 3(3) = -11 \Rightarrow y = 2$
• Row 1: $x + 2 + 3 = 6 \Rightarrow x = 1$

Solution: $(x, y, z) = (1, 2, 3)$.

Pivot Variables and Free Variables

After reduction to echelon form:

• A pivot variable (or leading variable) is one whose column contains a leading entry. It can be solved for in terms of the free variables.
• A free variable corresponds to a column with no leading entry. It can take any value, generating infinitely many solutions.

Decision rule:

• No free variables + no contradictory row → unique solution
• Any free variable + no contradictory row → infinitely many solutions
• Any row of the form $[0 \;\cdots\; 0 \mid c]$ with $c \neq 0$ → no solution

Reduced Echelon Form and Gauss-Jordan

Reduced row echelon form (RREF) adds two requirements to echelon form:

• Each pivot equals 1
• All entries above each pivot are also zero

Gauss-Jordan reduction achieves RREF by additionally eliminating upward (above each pivot) after the forward pass. The result directly reads off the solution without back-substitution. For large systems, Gauss-Jordan is less numerically preferred than plain Gaussian elimination followed by back-substitution — but it is conceptually clean and useful for computing matrix inverses.