# Chapter 5. Systems of Linear Equations

# 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,
$$

so

$$
z=3.
$$

The second row gives

$$
y-2z=-4,
$$

so

$$
y-6=-4,
$$

and therefore

$$
y=2.
$$

The first row gives

$$
x+y+z=6,
$$

so

$$
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.

If

$$
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,
$$

so

$$
y=2.
$$

From the first equation,

$$
x+2+3=6,
$$

so

$$
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.