Linear systems and the Gauss-Jordan method

Summary

This lesson studies systems of linear equations with any number of equations and of unknowns. It writes each system as a matrix equation $AX = B$ and represents it by its augmented matrix; it proves that the three elementary row operations transform a system into another with the same solutions, and that every matrix can be brought by means of them to a reduced row echelon form, from which the solutions can be read off directly: this is Gauss-Jordan elimination. It then proves that this form is unique, whatever operations are used, and defines with it the rank of a matrix; it proves the Rouché-Capelli theorem (known in the Spanish-speaking world as the Rouché-Frobenius theorem), which decides whether a system has a solution and how many free parameters its solutions have, and applies it to homogeneous systems. This completes the study of systems begun in the unit on number systems.

Learning objectives

Write a linear system in matrix form, form its augmented matrix and justify why elementary row operations preserve its solutions.
Reduce a matrix to its reduced row echelon form by Gauss-Jordan elimination, prove that this form is unique and read the solutions of the system from it.
Compute the rank of a matrix and apply the Rouché-Capelli theorem to classify a system, also when its coefficients depend on a parameter.
Set up as linear systems problems of interpolation, of chemical balance, of network flow and of magic squares, and describe their solutions with free parameters.

The matrix form of a system

In the lesson of the course Algebra and Geometry I on first-degree equations and linear systems, systems of two and of three equations were solved by substitution, elimination and comparison, and those of two equations in two unknowns were classified by means of their determinant. The general case was left pending there, and its classification was admitted without proof. This lesson settles it with the tools of the lesson on matrices and matrix operations.

A system of $m$ linear equations in $n$ unknowns $x_1, x_2, \ldots, x_n$ is a set of $m$ equations of the form shown below, which must hold simultaneously; the number $a_{ij}$ is the coefficient of the unknown $x_j$ in equation $i$ , and $b_i$ is the constant term of that equation.

\begin{cases} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 \\ \cdots \\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n = b_m \end{cases}

A solution of the system is an ordered list of $n$ numbers $(s_1, s_2, \ldots, s_n)$ which, put in place of the unknowns, satisfy the $m$ equations. Let $A$ be the coefficient matrix, with $m$ rows and $n$ columns, whose entry in row $i$ and column $j$ is $a_{ij}$ ; let $X$ be the column of the unknowns and $B$ that of the constant terms. As was already observed in that lesson, by the definition of the matrix product the entry $i$ of the column $AX$ is precisely the left-hand side of equation $i$ . Hence the whole system is written as a single equality between column matrices, $AX = B$ . For example, the system that will be solved further on is written as follows:

\begin{cases} 2y + z = 0 \\ x + y + z = 2 \\ 2x + 3y - z = -3 \end{cases} \qquad \begin{pmatrix} 0 & 2 & 1 \\ 1 & 1 & 1 \\ 2 & 3 & -1 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 0 \\ 2 \\ -3 \end{pmatrix}

To solve the system it suffices to know the numbers $a_{ij}$ and $b_i$ : the names of the unknowns play no role in the computations. The augmented matrix of the system is the matrix $M$ , with $m$ rows and $n + 1$ columns, obtained by appending to $A$ the column $B$ as its last column; we shall write it $M = \left( A, B \right)$ . Each row of $M$ summarizes an equation: its first $n$ entries are the coefficients, and the last one is the constant term. In the example:

M = \begin{pmatrix} 0 & 2 & 1 & 0 \\ 1 & 1 & 1 & 2 \\ 2 & 3 & -1 & -3 \end{pmatrix}

A system is consistent if it has at least one solution, and inconsistent if it has none; a consistent system is determinate if it has exactly one, and indeterminate if it has more than one. Two systems in the same unknowns are equivalent when they have the same solution set. The Course I lesson showed that a system of two equations in two unknowns has no solution, one, or infinitely many; by the end of this lesson we shall know that the same happens with every linear system, and we shall have a criterion for deciding which of the cases occurs.