Systems of linear equations

Write the equilibrium equations at every joint of a bridge truss and you get a system of linear equations. So do Kirchhoff's laws for a circuit, mass balances around a chemical plant, the stiffness equations of a finite-element model and the least-squares fit of a calibration curve. Large engineering models routinely produce systems with thousands or millions of unknowns, and solving them is one of the most heavily used computations in the world.

This chapter teaches the method behind nearly all of those solvers: Gaussian elimination. You will learn to set up a system as an augmented matrix, reduce it with row operations, read off the solution, and recognize when a system has no solution or infinitely many. You will also see why a computer can give a badly wrong answer to a system that looks harmless.

Linear equations and what a solution means

A linear equation in the unknowns \(x_1, x_2, \dots, x_n\) has the form \(a_1x_1 + a_2x_2 + \dots + a_nx_n = b\), where the coefficients \(a_i\) and the right-hand side \(b\) are constants. The unknowns appear only to the first power, never multiplied together, never inside a sine or a square root. \(3x - 2y + z = 7\) is linear; \(xy = 4\) and \(x^2 + y = 1\) are not.

A system is a set of such equations that must hold at the same time. A solution is a set of values that satisfies every equation. The key fact about linear systems is that there are only three possibilities:

• exactly one solution;
• no solution (the system is inconsistent);
• infinitely many solutions.

There is never exactly two or exactly five. With two unknowns you can see why: each equation is a straight line, and two lines either cross once, are parallel, or are the same line.

In three unknowns each equation is a plane. Three planes usually meet at a single point, but they can also share a whole line, coincide, or have no common point at all. The algebra below sorts out which case you are in without any need to picture it.

The augmented matrix

Writing \(x\), \(y\), \(z\) and the plus signs again at every step is wasteful. Since only the numbers change, we record the coefficients and right-hand sides in a rectangular table called the augmented matrix. The system

Each row is one equation, each column to the left of the bar belongs to one unknown, and the last column holds the right-hand sides. The left part alone is the coefficient matrix \(A\). In matrix notation (Lesson 3) the system is written \(A\mathbf{x} = \mathbf{b}\).

Row operations

Three operations change a system into an equivalent one, meaning it has exactly the same solutions:

• Swap two rows (write the equations in a different order).
• Multiply a row by a non-zero constant.
• Add a multiple of one row to another row.

None of these can create or destroy a solution, and each can be undone. The third is the workhorse: we use it to eliminate unknowns. Notation: \(R_2 \to R_2 - 2R_1\) means "replace row 2 with row 2 minus twice row 1".

Gaussian elimination

The goal is row echelon form: a staircase shape in which each row's first non-zero entry (its pivot) lies to the right of the pivot above it, and everything below each pivot is zero. Then the last equation has one unknown, the one above it has two, and so on, and you can solve from the bottom up by back substitution.

The procedure, column by column:

• Choose a pivot: a non-zero entry in the current column, at or below the current row. Swap it into place if needed.
• Use it to make every entry below it zero, with operations of the form \(R_i \to R_i - m R_{\text{pivot}}\), where the multiplier \(m\) is the entry divided by the pivot.
• Move one row down and one column right, and repeat.

Reduced row echelon form

If you keep going, scaling each pivot to 1 and clearing the entries above the pivots as well as below, you reach reduced row echelon form (RREF). This is Gauss–Jordan elimination. In RREF the solution can be read directly with no back substitution. For the example above, the RREF is

By hand, plain elimination with back substitution takes fewer operations. Gauss–Jordan becomes the method of choice when you want a matrix inverse (Lesson 3), and the RREF is the clearest way to see the structure of systems with many or no solutions.

Systems with no solution or many solutions

Elimination detects the other two cases automatically.

If a row reduces to \(\left[\,0 \;\; 0 \;\; \cdots \;\; 0 \mid c\,\right]\) with \(c \ne 0\), it says \(0 = c\). That is impossible, so the system has no solution. The equations contradict each other.

If there is no contradiction but some column has no pivot, the unknown for that column is a free variable. It can take any value, and the pivot variables are expressed in terms of it. Every value of the free variable gives a solution, so there are infinitely many.

Rank and counting solutions

The number of pivots is the rank of the matrix. For a system with \(n\) unknowns:

• If the augmented matrix has a pivot in its last column, there is no solution.
• Otherwise, if the rank equals \(n\), there is exactly one solution.
• Otherwise there are \(n - \text{rank}\) free variables and infinitely many solutions.

A homogeneous system, where every right-hand side is zero (\(A\mathbf{x} = \mathbf{0}\)), always has at least the solution \(\mathbf{x} = \mathbf{0}\). It has other solutions exactly when there are free variables. Homogeneous systems turn up in balancing chemical equations and, in Lesson 5, in finding eigenvectors.

Engineering applications

Two problems show how systems arise in practice. In both, the physics gives one equation per unknown, and the equations are linear because the underlying laws (equilibrium, Ohm's law) are linear.

Forces at a joint

A real truss has one pair of equations like this at every joint. A bridge with 40 joints gives 80 equations, and the computer solves them by exactly the elimination you just did.

Currents in a circuit

Notice that the coefficient matrix \(\begin{pmatrix} 6 & -4 \\ -4 & 10 \end{pmatrix}\) is symmetric. Resistor networks and spring networks always give symmetric matrices, and solvers exploit that to halve the work.

When computers struggle: pivoting and ill-conditioning

Elimination is exact in theory, but computers round every number to about 16 significant digits. Two practical issues follow.

First, partial pivoting. If a pivot is very small, the multipliers become huge and rounding errors are magnified. Software therefore swaps rows so that the largest available entry in the column becomes the pivot. When you work by hand you only need to swap when a pivot is exactly zero, but knowing why programs swap will help you read their documentation.

Second, some systems are ill-conditioned: tiny changes in the data cause huge changes in the solution. Geometrically, the lines (or planes) are nearly parallel, so their crossing point is poorly defined.

If your data come from measurements, an ill-conditioned model means the measurement error can swamp the answer. The cure is usually in the engineering, not the arithmetic: choose better-separated sensor positions, or reformulate the model. Numerical-methods courses quantify this with the condition number of a matrix.