Chapter 5. Systems of Linear Equations

A system of linear equations is a collection of linear equations imposed on the same unknowns. The purpose of solving the system is to find all assignments of the unknowns that satisfy every equation at once.

Systems are the first major computational object in linear algebra. They connect equations, matrices, geometry, algorithms, and abstract structure. The standard method is to write the system as an augmented matrix, use elementary row operations, reduce it to echelon form or reduced echelon form, and then read off the solutions. A system is inconsistent exactly when row reduction produces a contradictory row of the form $0=b$ , where $b\ne 0$ .

5.1 General Form

A system of $m$ linear equations in $n$ unknowns has the form

\begin{aligned} 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,\\ &\vdots\\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n &= b_m. \end{aligned}

The unknowns are

x_1,x_2,\ldots,x_n.

The coefficients are the scalars

a_{ij}.

The right-hand side entries are

b_1,b_2,\ldots,b_m.

The first index of $a_{ij}$ records the equation. The second index records the unknown. Thus $a_{23}$ is the coefficient of $x_3$ in the second equation.

5.2 Matrix Form

The same system can be written as

Ax=b,

where

A= \begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{m1}&a_{m2}&\cdots&a_{mn} \end{bmatrix}, \qquad x= \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix}, \qquad b= \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_m \end{bmatrix}.

This notation is compact, but it also carries meaning.

The matrix $A$ represents the coefficients. The vector $x$ represents the unknowns. The vector $b$ represents the required output. Solving $Ax=b$ means finding every vector $x$ that is mapped by $A$ to $b$ .

5.3 Augmented Matrix

The augmented matrix of the system $Ax=b$ is

[A\mid b].

Explicitly,

\left[ \begin{array}{cccc|c} a_{11}&a_{12}&\cdots&a_{1n}&b_1\\ a_{21}&a_{22}&\cdots&a_{2n}&b_2\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ a_{m1}&a_{m2}&\cdots&a_{mn}&b_m \end{array} \right].

The vertical bar separates the coefficient columns from the right-hand side column. Row operations are performed on the whole augmented matrix because each row represents one equation.

For example, the system

\begin{aligned} x+2y-z&=3,\\ 2x-y+4z&=1 \end{aligned}

has augmented matrix

\left[ \begin{array}{ccc|c} 1&2&-1&3\\ 2&-1&4&1 \end{array} \right].

5.4 Solutions of a System

A solution of a system is a vector $x$ that satisfies every equation.

For example, consider

\begin{aligned} x+y&=5,\\ 2x-y&=1. \end{aligned}

The vector

\begin{bmatrix} 2\\ 3 \end{bmatrix}

is a solution because

2+3=5

and

2(2)-3=1.

A vector that satisfies only one equation is not a solution of the system. A solution must satisfy all equations simultaneously.

The solution set of a system is

\{x\in F^n: Ax=b\}.

This set may be empty, contain exactly one vector, or contain infinitely many vectors.

5.5 Consistency

A system is consistent if it has at least one solution.

A system is inconsistent if it has no solution.

For example,

\begin{aligned} x+y&=1,\\ x+y&=3 \end{aligned}

is inconsistent, because no pair $(x,y)$ can make both equations true.

In augmented matrix form,

\left[ \begin{array}{cc|c} 1&1&1\\ 1&1&3 \end{array} \right].

Subtracting the first row from the second gives

\left[ \begin{array}{cc|c} 1&1&1\\ 0&0&2 \end{array} \right].

The second row represents

0x+0y=2,

or simply

0=2.

This contradiction proves that the system is inconsistent.

5.6 Equivalent Systems

Two systems are equivalent if they have the same solution set.

Elementary row operations produce equivalent systems. The three operations are:

Operation	Meaning
Row interchange	Swap two equations
Row scaling	Multiply one equation by a nonzero scalar
Row replacement	Add a multiple of one equation to another

These operations preserve the set of solutions. They do not change the constraints; they only rewrite them.

For example, from

\begin{aligned} x+y&=5,\\ 2x-y&=1 \end{aligned}

we may replace the second equation by the sum of both equations:

3x=6.

The system becomes

\begin{aligned} x+y&=5,\\ 3x&=6. \end{aligned}

The new system has the same solution as the old system.

5.7 Echelon Form

A matrix is in row echelon form when its nonzero rows appear above its zero rows, each leading entry is to the right of the leading entry in the row above it, and all entries below a leading entry are zero. These conditions are the usual structural conditions used in row reduction.

For example,

\left[ \begin{array}{ccc|c} 1&2&-1&3\\ 0&1&4&5\\ 0&0&2&6 \end{array} \right]

is in echelon form.

Its triangular shape allows the unknowns to be found by back substitution. The last equation determines the last leading unknown. The previous equation then determines the previous leading unknown, and so on.

5.8 Reduced Echelon Form

A matrix is in reduced row echelon form when it is in echelon form, each leading entry is $1$ , and each leading $1$ is the only nonzero entry in its column. In this form, the solution can be read directly from the augmented matrix.

For example,

\left[ \begin{array}{ccc|c} 1&0&2&3\\ 0&1&-1&4\\ 0&0&0&0 \end{array} \right]

is in reduced echelon form.

It corresponds to

x_1+2x_3=3,

x_2-x_3=4.

The variable $x_3$ is free. If $x_3=t$ , then

x_1=3-2t, \qquad x_2=4+t.

Thus

x= \begin{bmatrix} 3-2t\\ 4+t\\ t \end{bmatrix}.

5.9 Pivots

A pivot is a leading entry used to solve for a leading variable.

In an echelon form, each nonzero row has a pivot. The column containing a pivot is called a pivot column. A variable corresponding to a pivot column is a leading variable. A variable corresponding to a nonpivot column is a free variable.

For example,

\left[ \begin{array}{cccc|c} 1&0&3&0&2\\ 0&1&-1&0&5\\ 0&0&0&1&7 \end{array} \right]

has pivot columns $1$ , $2$ , and $4$ . Therefore $x_1$ , $x_2$ , and $x_4$ are leading variables. The variable $x_3$ is free.

Pivots are the algebraic markers of constraint. Free variables are the algebraic markers of freedom.

5.10 Gaussian Elimination

Gaussian elimination is the process of using elementary row operations to put an augmented matrix into echelon form, then solving by back substitution. Row reduction to echelon form followed by back substitution is the standard elimination method for solving systems.

Consider

\begin{aligned} x+y+z&=6,\\ 2x-y+z&=3,\\ x+2y-z&=2. \end{aligned}

The augmented matrix is

\left[ \begin{array}{ccc|c} 1&1&1&6\\ 2&-1&1&3\\ 1&2&-1&2 \end{array} \right].

Replace $R_2$ by $R_2-2R_1$ , and replace $R_3$ by $R_3-R_1$ :

\left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&-3&-1&-9\\ 0&1&-2&-4 \end{array} \right].

Interchange $R_2$ and $R_3$ :

\left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&1&-2&-4\\ 0&-3&-1&-9 \end{array} \right].

Replace $R_3$ by $R_3+3R_2$ :

\left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&1&-2&-4\\ 0&0&-7&-21 \end{array} \right].

The last row gives

-7z=-21,

z=3.

The second row gives

y-2z=-4,

y-6=-4,

and therefore

y=2.

The first row gives

x+y+z=6,

x+2+3=6,

and therefore

x=1.

The solution is

\begin{bmatrix} 1\\ 2\\ 3 \end{bmatrix}.

5.11 Gauss-Jordan Elimination

Gauss-Jordan elimination continues row reduction until the augmented matrix is in reduced row echelon form.

Using the previous echelon matrix,

\left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&1&-2&-4\\ 0&0&-7&-21 \end{array} \right],

scale the third row by $-1/7$ :

\left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&1&-2&-4\\ 0&0&1&3 \end{array} \right].

Eliminate the entries above the pivot in column $3$ :

\left[ \begin{array}{ccc|c} 1&1&0&3\\ 0&1&0&2\\ 0&0&1&3 \end{array} \right].

Eliminate the entry above the pivot in column $2$ :

\left[ \begin{array}{ccc|c} 1&0&0&1\\ 0&1&0&2\\ 0&0&1&3 \end{array} \right].

The solution is read directly:

x=1,\qquad y=2,\qquad z=3.

5.12 Free Variables

Free variables appear when some columns have no pivot.

Consider

\left[ \begin{array}{ccc|c} 1&2&-1&4\\ 0&0&1&3 \end{array} \right].

The pivot columns are $1$ and $3$ . The variable $x_2$ is free.

The equations are

x_1+2x_2-x_3=4,

x_3=3.

Let

x_2=t.

Then

x_3=3,

and

x_1+2t-3=4.

Thus

x_1=7-2t.

The solution set is

\left\{ \begin{bmatrix} 7-2t\\ t\\ 3 \end{bmatrix} :t\in\mathbb{R} \right\}.

A free variable produces infinitely many solutions whenever the system is consistent.

5.13 Homogeneous Systems

A homogeneous system has the form

Ax=0.

Every homogeneous system is consistent, because the zero vector always satisfies it:

A0=0.

This solution is called the trivial solution.

A homogeneous system has either exactly one solution or infinitely many solutions. It has exactly one solution when the trivial solution is the only solution. It has infinitely many solutions when there is at least one nonzero solution.

If a homogeneous system has $n$ unknowns and its reduced echelon form has $r$ nonzero rows, then it has $n-r$ free variables.

5.14 Nonhomogeneous Systems

A nonhomogeneous system has the form

Ax=b, \qquad b\ne 0.

Its solution set, when nonempty, is a translate of the solution set of the associated homogeneous system

Ax=0.

Suppose $p$ is one particular solution of

Ax=b.

Then any other solution $x$ satisfies

A(x-p)=Ax-Ap=b-b=0.

Therefore

x-p

belongs to the null space of $A$ . Hence every solution has the form

x=p+v, \qquad v\in\{z:Az=0\}.

This structure is one of the central facts of linear systems.

5.15 Three Possible Outcomes

A linear system has exactly one of three possible solution types:

Outcome	Algebraic condition	Geometric meaning
No solution	Contradictory row appears	Empty intersection
One solution	Pivot in every variable column and no contradiction	Single intersection point
Infinitely many solutions	At least one free variable and no contradiction	Affine line, plane, or higher-dimensional set

There is no fourth case. In particular, a linear system cannot have exactly two distinct solutions.

The reason is linearity. If two distinct solutions exist, their difference gives a nonzero solution of the associated homogeneous system. That nonzero direction can be scaled, giving infinitely many solutions.

5.16 Underdetermined and Overdetermined Systems

A system with fewer equations than unknowns is called underdetermined. Such a system often has free variables, though it may also be inconsistent.

A system with more equations than unknowns is called overdetermined. Such a system often has no solution, though it may be consistent if some equations are redundant or compatible.

For example,

x+y=1

is underdetermined in two unknowns and has infinitely many solutions.

The system

\begin{aligned} x+y&=1,\\ x-y&=0,\\ 2x+3y&=5 \end{aligned}

is overdetermined. It may or may not be consistent. The number of equations alone does not determine the solution type. The arrangement of the equations matters.

5.17 Geometry of Systems

Each equation in a system defines a geometric constraint.

In $\mathbb{R}^2$ , each nonzero linear equation defines a line. A system of two equations asks where two lines intersect. The possibilities are:

Geometry	Solution type
Intersecting lines	One solution
Parallel distinct lines	No solution
Same line	Infinitely many solutions

In $\mathbb{R}^3$ , each nonzero linear equation defines a plane. Several planes may intersect in a point, a line, a plane, or not at all.

In $\mathbb{R}^n$ , each equation defines a hyperplane. A system describes the intersection of hyperplanes.

5.18 Row Space View

Each row of $A$ is the coefficient vector of one equation.

The equation

a_i\cdot x=b_i

uses the $i$ -th row $a_i$ of $A$ . Thus a system can be viewed as a collection of dot product constraints:

a_1\cdot x=b_1,

a_2\cdot x=b_2,

\vdots

a_m\cdot x=b_m.

This view is useful because it connects systems with geometry. Each row vector is normal to a hyperplane.

5.19 Column Space View

The matrix equation

Ax=b

can also be read by columns.

A= \begin{bmatrix} |&|&&|\\ a_1&a_2&\cdots&a_n\\ |&|&&| \end{bmatrix},

then

Ax=x_1a_1+x_2a_2+\cdots+x_na_n.

Thus $Ax=b$ asks whether $b$ can be written as a linear combination of the columns of $A$ .

The system is consistent precisely when $b$ lies in the span of the columns of $A$ . In later chapters this span is called the column space of $A$ .

5.20 Example with Infinitely Many Solutions

Consider

\begin{aligned} x+y+z&=4,\\ 2x+2y+2z&=8. \end{aligned}

The second equation is twice the first, so it adds no new constraint.

The augmented matrix is

\left[ \begin{array}{ccc|c} 1&1&1&4\\ 2&2&2&8 \end{array} \right].

Replace $R_2$ by $R_2-2R_1$ :

\left[ \begin{array}{ccc|c} 1&1&1&4\\ 0&0&0&0 \end{array} \right].

The equation is

x+y+z=4.

Let

y=s, \qquad z=t.

Then

x=4-s-t.

The solution set is

\left\{ \begin{bmatrix} 4-s-t\\ s\\ t \end{bmatrix} :s,t\in\mathbb{R} \right\}.

This is a plane in $\mathbb{R}^3$ .

5.21 Example with No Solution

Consider

\begin{aligned} x+y+z&=4,\\ 2x+2y+2z&=9. \end{aligned}

The augmented matrix is

\left[ \begin{array}{ccc|c} 1&1&1&4\\ 2&2&2&9 \end{array} \right].

Replace $R_2$ by $R_2-2R_1$ :

\left[ \begin{array}{ccc|c} 1&1&1&4\\ 0&0&0&1 \end{array} \right].

The second row says

0=1.

Therefore the system has no solution.

Geometrically, the two equations describe parallel planes in $\mathbb{R}^3$ .

5.22 Example with One Solution

Consider

\begin{aligned} x+y+z&=6,\\ y+z&=5,\\ z&=3. \end{aligned}

This system is already triangular.

From the third equation,

z=3.

From the second equation,

y+3=5,

y=2.

From the first equation,

x+2+3=6,

x=1.

The unique solution is

\begin{bmatrix} 1\\ 2\\ 3 \end{bmatrix}.

The system has one pivot for each variable.

5.23 Algorithmic Summary

To solve a linear system:

Step	Action
1	Write the augmented matrix
2	Use elementary row operations
3	Obtain echelon form or reduced echelon form
4	Check for contradiction
5	Identify pivot variables and free variables
6	Write the solution set

If a contradictory row appears, the system is inconsistent. If no contradiction appears and every variable column has a pivot, the solution is unique. If no contradiction appears and at least one variable column has no pivot, there are infinitely many solutions.

5.24 Summary

A system of linear equations is a set of simultaneous linear constraints. It is represented compactly by

Ax=b.

The augmented matrix

[A\mid b]

contains all coefficients and right-hand side values. Elementary row operations replace the original system by equivalent systems. Row reduction exposes pivots, free variables, contradictions, and solution structure.

The essential classification is:

Row-reduction result	Solution type
Contradictory row	No solution
Pivot in every variable column, no contradiction	Unique solution
Free variable, no contradiction	Infinitely many solutions

This classification is the computational foundation for rank, nullity, invertibility, column space, and linear transformations.