1.1 Systems of Linear Equations

Theory: Systems of Linear Equations

Linear Equations and Linear Systems (Lay §1.1)

A linear equation in the variables $x_1, x_2, \dots, x_n$ is an equation that can be written in the form

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

• $a_1, a_2, \dots, a_n$ are the coefficients (real or complex numbers, usually known in advance),
• $x_1, x_2, \dots, x_n$ are the variables, and $b$ is a constant.

For example $2x_1 - 3x_2 = 5$ is linear. Equations such as $x_1 x_2 = 4$, $\sqrt{x_1} + x_2 = 3$ or $4x_1 - 5x_2 = x_1 x_2$ are not linear (products of variables, roots, powers, etc. are not allowed).

A system of linear equations (a linear system) is a collection of one or more linear equations involving the same variables, e.g.

$$\begin{aligned} 2x_1 - 3x_2 &= 5 \\ 5x_1 + 2x_2 &= 10 \end{aligned}$$

• A solution of the system is a list $(s_1, s_2, \dots, s_n)$ of numbers that makes every equation true when substituted for $x_1, \dots, x_n$.
• The solution set is the set of all possible solutions.
• Two systems are equivalent if they have the same solution set.

The Three Possible Cases — the Picture with Lines

With two variables, each linear equation describes a line in the $x_1x_2$-plane: the solutions of that one equation are exactly the points on its line. A solution of the system must lie on all the lines at once, so the solution set is the intersection of the lines.

Two lines in the plane can only meet in three ways:

Picture	Solutions	Name
Lines are parallel (never meet)	no solution	inconsistent
Lines cross at exactly one point	exactly one (unique) solution	consistent
Lines coincide (the same line)	infinitely many solutions	consistent

Fact (Lay §1.1): Every system of linear equations has either

1. no solution, or
2. exactly one solution, or
3. infinitely many solutions.

A system is consistent if it has at least one solution (case 2 or 3), and inconsistent if it has none (case 1).

There is no linear system with “exactly 2” or “exactly 5” solutions. As soon as there are two different solutions, there are infinitely many (every point on the line through them works). The same three cases hold for three variables, where each equation is a plane in $\mathbb{R}^3$.

Coefficient Matrix, Augmented Matrix, Matrix and Vector Forms

The essential information of a system is stored in a rectangular array called a matrix. For the system $2x_1 - 3x_2 = 5$, $5x_1 + 2x_2 = 10$:

$$\underbrace{A = \begin{bmatrix} 2 & -3 \\ 5 & 2 \end{bmatrix}}_{\text{coefficient matrix}}, \qquad \mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} 5 \\ 10 \end{bmatrix}$$

The augmented matrix $[A \mid \mathbf{b}]$ is the coefficient matrix with the column of constants added on the right (the augmented column):

$$[A \mid \mathbf{b}] = \left[\begin{array}{cc|c} 2 & -3 & 5 \\ 5 & 2 & 10 \end{array}\right]$$

The size of a matrix is written $m \times n$: $m$ rows first, then $n$ columns. Here $A$ is $2 \times 2$ and $[A \mid \mathbf{b}]$ is $2 \times 3$. A column with $n$ entries, like $\mathbf{x}$, is a vector in $\mathbb{R}^n$.

The same system can be written in three equivalent ways:

Form	For our example
System of equations	$2x_1 - 3x_2 = 5,\ \ 5x_1 + 2x_2 = 10$
Matrix equation $A\mathbf{x} = \mathbf{b}$	$\begin{bmatrix} 2 & -3 \\ 5 & 2 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 5 \\ 10 \end{bmatrix}$
Vector equation	$x_1\begin{bmatrix} 2 \\ 5 \end{bmatrix} + x_2\begin{bmatrix} -3 \\ 2 \end{bmatrix} = \begin{bmatrix} 5 \\ 10 \end{bmatrix}$

All three have the same solution set and are all solved by row reducing the same augmented matrix $[A \mid \mathbf{b}]$.

The vector equation reads ”$\mathbf{b}$ is a linear combination of the columns of $A$ with weights $x_1, x_2$”. Lay develops the vector form in §1.3 and the product $A\mathbf{x} = x_1\mathbf{a}_1 + \cdots + x_n\mathbf{a}_n$ in §1.4 — but it is worth seeing now that they are just new notation for the same system.

Elementary Row Operations and Row Equivalence

Solving a system means replacing it with an equivalent system that is easier to solve. On the augmented matrix this is done with three elementary row operations:

1. Switch (interchange): swap two rows, e.g. $R_1 \leftrightarrow R_2$.
2. Scale: multiply all entries of a row by a nonzero constant, e.g. $R_2 \leftarrow \tfrac{1}{2}R_2$.
3. Replace (replacement): add to one row a multiple of another row, e.g. $R_3 \leftarrow R_3 + 4R_1$.

Two matrices are row equivalent (written $A \sim B$) if one can be turned into the other by a sequence of elementary row operations. Every row operation is reversible (swap back, scale by $1/c$, subtract the multiple again).

Fact (Lay §1.1): If the augmented matrices of two linear systems are row equivalent, then the two systems have the same solution set.

Mini-example: elimination (Lay §1.1, Example 1)

Solve $x_1 - 2x_2 + x_3 = 0$, $\ 2x_2 - 8x_3 = 8$, $\ -4x_1 + 5x_2 + 9x_3 = -9$.

$$\left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ -4 & 5 & 9 & -9 \end{array}\right] \xrightarrow{R_3 + 4R_1} \left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & -3 & 13 & -9 \end{array}\right] \xrightarrow{\tfrac12 R_2} \left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & -3 & 13 & -9 \end{array}\right] \xrightarrow{R_3 + 3R_2} \left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & 0 & 1 & 3 \end{array}\right]$$

Back-substitute: $x_3 = 3$, $x_2 = 4 + 4(3) = 16$, $x_1 = 2(16) - 3 = 29$. Check in the original third equation: $-4(29) + 5(16) + 9(3) = -116 + 80 + 27 = -9$ ✓. Unique solution $(29, 16, 3)$.

Spotting an Inconsistent System

If row reduction produces a row of the form

$$\left[\begin{array}{ccc|c} 0 & \cdots & 0 & b \end{array}\right] \quad \text{with } b \ne 0,$$

that row means $0x_1 + \cdots + 0x_n = b$, i.e. $0 = b$ — impossible. The system is inconsistent. In the language of §1.2: the augmented column has a pivot.

A row of all zeros $[0 \ \cdots \ 0 \mid 0]$ is harmless ($0 = 0$); it just means one equation was redundant. Only $[0 \ \cdots \ 0 \mid b]$ with $b \ne 0$ signals “no solution”.

---

Solved Examples (Textbook Questions)

Exercise 1

(Adapted from Lay §1.1, Exercise 1)

Solve the system using elementary row operations on the augmented matrix:

$$\begin{aligned} x_1 + 5x_2 &= 7 \\ -2x_1 - 7x_2 &= -5 \end{aligned}$$

Show solution ↓Hide solution ↑

Solution

$$\left[\begin{array}{cc|c} 1 & 5 & 7 \\ -2 & -7 & -5 \end{array}\right] \xrightarrow{R_2 + 2R_1} \left[\begin{array}{cc|c} 1 & 5 & 7 \\ 0 & 3 & 9 \end{array}\right] \xrightarrow{\tfrac13 R_2} \left[\begin{array}{cc|c} 1 & 5 & 7 \\ 0 & 1 & 3 \end{array}\right] \xrightarrow{R_1 - 5R_2} \left[\begin{array}{cc|c} 1 & 0 & -8 \\ 0 & 1 & 3 \end{array}\right]$$

So $x_1 = -8$, $x_2 = 3$: the unique solution is $(-8, 3)$.

Check: $-8 + 5(3) = 7$ ✓ and $-2(-8) - 7(3) = 16 - 21 = -5$ ✓.

Geometrically, the two lines cross at exactly one point, $(-8, 3)$.

Exercise 2

(Adapted from Lay §1.1, Exercise 11)

Solve the system:

$$\begin{aligned} x_2 + 4x_3 &= -5 \\ x_1 + 3x_2 + 5x_3 &= -2 \\ 3x_1 + 7x_2 + 7x_3 &= 6 \end{aligned}$$

Show solution ↓Hide solution ↑

Solution

The top-left entry is 0, so first swap $R_1 \leftrightarrow R_2$:

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

$R_3 \leftarrow R_3 - 3R_1$: row 3 becomes $[0, -2, -8 \mid 12]$. Then $R_3 \leftarrow R_3 + 2R_2$:

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

The last row says $0x_1 + 0x_2 + 0x_3 = 2$, i.e. $0 = 2$. The augmented column has a pivot, so the system is inconsistent — it has no solution.

Exercise 3

(Adapted from Lay §1.1, Exercise 19)

Determine the value(s) of $h$ such that the matrix is the augmented matrix of a consistent linear system:

$$\left[\begin{array}{cc|c} 1 & h & 4 \\ 3 & 6 & 8 \end{array}\right]$$

Show solution ↓Hide solution ↑

Solution

$R_2 \leftarrow R_2 - 3R_1$:

$$\left[\begin{array}{cc|c} 1 & h & 4 \\ 3 & 6 & 8 \end{array}\right] \sim \left[\begin{array}{cc|c} 1 & h & 4 \\ 0 & 6 - 3h & -4 \end{array}\right]$$

• If $6 - 3h = 0$, i.e. $h = 2$, row 2 reads $0 = -4$: inconsistent.
• If $h \ne 2$, the entry $6 - 3h$ is a pivot, the augmented column is not a pivot column, and the system is consistent (with a unique solution).

Answer: the system is consistent exactly when $h \ne 2$.

(Geometric view: when $h = 2$ the lines $x_1 + 2x_2 = 4$ and $3x_1 + 6x_2 = 8$ are parallel.)