1.8 General Linear Systems

1Reading¶

Material related to this page, as well as additional exercises, can be found in ALA Ch. 1.8.

2Learning Objectives¶

By the end of this page, you should know:

how to put a matrix in to row echelon form
compute the rank of a matrix
how to solve general linear systems using row echelon form

3Row Echelon Form¶

So far we have discussed techniques for solving “nice” linear systems defined by nonsingular coefficient matrices: these are “nice” since they always have a unique solution. Now, we move towards more general systems that have $m$ equations and $n$ unknowns, including non-square ( $m \neq n$ ) and singular coefficient matrices.

The good news is that we already have the tools that we need to solve the general case, but we need to make some small tweaks to accomodate this more general setting. We first define a generalization of upper triangular matrices that take a “stair case form”, called the row echelon form of a matrix.

An example of a matrix in row echelon form is

\begin{bmatrix} \textbf{2} & 0 & 1 & -5 & 6 \\ 0 & 0 & \textbf{1} & 1 & 7 \\ 0 & 0 & 0 & \textbf{-3} & 1\\ 0 & 0 & 0 & 0 & 0 \end{bmatrix},

(1)

where $r=3, m=4$ and the pivots 3, -1, and 2 are in $\textbf{bold}$ .

If $A$ is an $m \times n$ matrix, then we can find an $m \times m$ permutation matrix $P$ and an $m \times m$ lower triangular matrix $L$ such that

PA = LU,

(3)

where $U$ is an $m \times n$ matrix in row echelon form. This fact follows from an analogous development of the LU-factorization using Gaussian Elimination, with some slight modifications for dealing with columns that do not have a pivot. We illustrate the procedure with an example which makes clear when things deviate from our previous approach.

Consider the linear system with the augmented matrix

\left[ \begin{array}{ccccc|c} 1 & 3 & 2 & -1 & 0 & a \\ 2 & 6 & 1 & 4 & 3 & b \\ -1 & -3 & -3 & 3 & 1 & c \\ 3 & 9 & 8 & -7 & 2 & d\end{array}\right],

(4)

where $\textbf{b} = \begin{bmatrix} a \\ b \\ c \\ d\end{bmatrix}$ is a generic right hand side vector that we use to get a better understanding of the solution properties of this linear system. The $(1,1)$ entry is a pivot. We use elementary row operations to make the entries below the pivot to be zero.

\left[ \begin{array}{ccccc|c} 1 & 3 & 2 & -1 & 0 & a \\ 0 & 0 & -3 & 6 & 3 & b-2a \\ 0 & 0 & -1 & 2 & 1 & c+a \\ 0 & 0 & 2 & 4 & 2 & d-3a\end{array}\right],

(5)

In (5), the second column has no suitable nonzero entry to use as the second pivot, because the 3 in the (1,2) position is already in a row with a pivot, so we move to the 3rd column. The $(2, 3)$ entry is nonzero, and becomes our second pivot (associated with the second row), which we use to zero out entries below it:

\left[ \begin{array}{ccccc|c} 1 & 3 & 2 & -1 & 0 & a \\ 0 & 0 & -3 & 6 & 3 & b-2a \\ 0 & 0 & 0 & 0 & 0 & c-\frac{b}{3}+\frac{5}{3}a \\ 0 & 0 & 0 & 0 & 4 & d + \frac{2}{3}b-\frac{13}{3}a\end{array}\right].

(6)

No suitable pivots are available in column 4 (since rows 1 and 2 already have pivots associated with them), and so the final pivot is the 4 in the fifth column. We want to put our matrix into row echelon form, so we swap rows 3 and 4 to get

\left[ \begin{array}{ccccc|c} 1 & 3 & 2 & -1 & 0 & a \\ 0 & 0 & -3 & 6 & 3 & b-2a \\ 0 & 0 & 0 & 0 & 4 & d + \frac{2}{3}b-\frac{13}{3}a \\ 0 & 0 & 0 & 0 & 0 & c-\frac{b}{3}+\frac{5}{3}a \end{array}\right].

(7)

The three pivots are 1, -3, and 4 at $(1,1)$ , $(2, 3)$ , and $(3, 4)$ .

4Rank of a Matrix¶

We can now define the rank of a matrix. For now, this will seem like a strange thing to give a name to, but we’ll see later in the class that in addition to the algebraic properties we outline next, it also says a lot about the geometry of subspaces defined by the columns of $A$ .

Rank plays a central role in our study of linear algebra, but right now we will explore the connections between rank and the solution set of a linear system.

Properties 1-3 are straightforward consequences of the definition of rank. Property 4 is not as obvious, but we’ll come back to it later in the class once we’ve developed more tools.

Exercise 1 (Ranks of matrices)

For each of the given matrices, find their rank.

a. $\bm 1 &0& 2& 3 \\ 0& 0 &1 &4 \\ 0& 0& 2 &2 \em$

b. $\bm 0& 2& 3 \\ 4&2&2 \\ 1&0&1 \\ 3&4&5\em$

Solution to Exercise 1

To find their rank, we put the given matrices in row echelon form and count the number of pivots.

a. We use the pivot in position $(2, 3)$ to eliminate below it, getting the matrix

\begin{align*} \bm \mathbf 1 &0& 2& 3 \\ 0& 0 & \mathbf 1 &4 \\ 0& 0& 0 & \mathbf {-6} \em \end{align*}

(8)

which is in row echelon form. The pivots (1, 1, and -6) are bolded. We see there are 3 pivots, meaning the rank of the matrx in part (a) is 3.

b. First, we swap Row 1 and Row 3 so that the first pivot is nonzero, getting the matrix

\begin{align*} \bm 1&0&1 \\ 4&2&2 \\ 0& 2& 3 \\ 3&4&5\em \end{align*}

(9)

Then we use the entry in position $(1, 1)$ to eliminate below it, getting the matrix

\begin{align*} \bm 1&0&1 \\ 0&2&-2 \\ 0& 2& 3 \\ 0&1&2\em \end{align*}

(10)

Then, we use the entry in position $(2, 2)$ to eliminate below it, getting the matrix

\begin{align*} \bm 1&0&1 \\ 0&2&-2 \\ 0& 0& 5 \\ 0&0&3\em \end{align*}

(11)

Finally, we use the entry in postion $(3, 3)$ to eliminate below it, getting the matrix

\begin{align*} \bm \mathbf 1&0&1 \\ 0&\mathbf 2&-2 \\ 0& 0& \mathbf 5 \\ 0&0&0\em \end{align*}

(12)

which is in row echelon form. The pivots (1, 2, and 5) are bolded. We see there are 3 pivots, meaning the rank of the matrx in part (b) is 3.

Python Break!¶

SymPy is a Python library for performing symbolic mathematics. We use it below to compute (reduced) row echelon forms of a matrix and see that it allows us to identify the rank of a matrix. In practice, numerical algebra routines based on the singular value decomposition, which we will see in the last third of the class, are used to compute the rank of a matrix: this is implemented by the numpy function np.linalg.matrix_rank.

## Row echelon form
import sympy
import numpy as np

# find the reduced row echelon form
A = sympy.Matrix([[1, 3, 2, -1, 0], [2, 6 ,1, 4, 3], [-1, -3, -3, 3, 1], [3, 9, 8, 7, 2]])
A_re = A.rref()

# find the rank of matrix
print("Row echelon form of the matrix:\n", A_re)

# find the rank of matrix
print("\nRank of the matrix: ", A.rank())

# Rank of a matrix using numpy
A_n = np.array([[1, 3, 2, -1, 0], [2, 6 ,1, 4, 3], [-1, -3, -3, 3, 1], [3, 9, 8, 7, 2]])
print("\nRank of the matrix using numpy: ", np.linalg.matrix_rank(A_n))

Row echelon form of the matrix:
 (Matrix([
[1, 3, 0, 0,  8/7],
[0, 0, 1, 0, -3/7],
[0, 0, 0, 1,  2/7],
[0, 0, 0, 0,    0]]), (0, 2, 3))

Rank of the matrix:  3

Rank of the matrix using numpy:  3

5Solving Linear Systems in Row Echelon Form¶

Suppose we have reduced the system to row echelon form $[U | \textbf{c}]$ , corresponding to the linear system $U\vv x = \vv c$ . We will now discuss how to solve such a system, and the types of solution sets that are possible.

5.1No Solution¶

First, we check for inconsistent equations. For example, if the $i^{th}$ row of $U$ is all zeros, but the corresponding entry $c_i \neq 0$ , then this would represent $0 = c_i \neq 0$ . This case corresponds to when $A \textbf{x} = \textbf{b}$ has no solution, also called incompatible. For example, in our previous example (7) the last row is all zeros, and therefore the system (4) has no solution if $c-\frac{b}{3}+\frac{5}{3}a \neq 0$ . If there are no such inconsistencies, the linear system is compatible, and has one or more solutions. Let’s see how to solve such compatible linear systems.

5.2Compatible Linear Systems¶

To find the solutions to compatible linear systems, we first split the variables into two separate classes.

As before, we use back substitution to solve $U \textbf{x} = \textbf{c}$ , but our goal is now to express the basic variables as a function of the free variables. We use our previous example to illustrate this procedure. Let’s fix a right hand side by setting $a = 0, b = 3, c=1, d=1$ :

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

(13)

Let us denote the variables as $(x, y, z, u, v)$ . Following (13), $\color{red}{(x, z, v)}$ are basic variables, while $\color{green}{(y, u)}$ are free variables. We first need to solve the reduced system

\begin{align*} \color{red}{x}+\color{green}{3y}+\color{red}{2z}-\color{green}{u} &= 0, \\ -\color{red}{3z} + \color{green}{6u} + \color{red}{3v} &= 3, \\ \color{red}{4v} &= 3 \\ 0 &= 0, \end{align*}

(14)

for the basic variables $\color{red}{(x, z, v)}$ in terms of the free variables $\color{green}{(y, u)}$ . Back Substitution combined with a bit of algebra gives us the following general solution

v=\frac{3}{4}, \ z = -1 + 2u + v = -\frac{1}{4} + 2u, \ x = -3y - 2z + u = \frac{1}{2}-3y-3u.

(15)

As the name suggests, we are free to chose any values for the free variables $\color{green}{(y, u)}$ : any resulting solution will satisfy (15). One possible solution for (4) is obtained by setting $y=y=0$ so that $x = \frac{1}{2},\, y=0,\, z=-\frac{1}{4},\, u =0,\, v = \frac{3}{4}$ .

5.3General Properties¶

In general, for an $m \times n$ system ( $m$ equations and $n$ unknowns) of rank $r$ , there are $r$ basic variables and $m - r$ free variables.
There are $m - r$ all zero rows in the row echelon form of the linear system. The system is compatible if and only if the corresponding right-hand vector entries $c_i$ are zero.

Our discussion is summarized in the following theorem.

Exercise 2 (Solving linear systems in row echelon form)

Given an augmented matrix in row echelon form,

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

(16)

find the set of all values $w, x, y, z$ which solve the corresponding linear system.

Solution to Exercise 2

Let’s reduce even further, using the pivots to eliminate the entries above them.

Using the pivot in position (3, 4) to eliminate above it, we get the equivalent system

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

(17)

Using the pivot in position (2, 2) to eliminate above it, we get the equivalent system

\begin{align*} \left[ \begin{array}{cccc|c} 2 & 0 & -16 & 0 & -4\\ 0 & 1 & 5 & 0 & 1\\ 0 & 0 & 0 & 1 & 2 \end{array}\right] \end{align*}

(18)

The reduced system is hence given as

\begin{align*} 2w - 16 y &= -4\\ x + 5y &= 1\\ z &= 2 \end{align*}

(19)

Therefore our solution set is the set of all $(w, x, y, z)$ such that

\begin{align*} w &= 8y - 4\\ x &= -5y + 1\\ z &= 2 \end{align*}

(20)

Note that this is an infinite set!

Exercise 3 (An inconsistent system)

Show that the system with augmented matrix

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

(21)

is inconsistent.

Solution to Exercise 3

Let’s put the augmented matrix in row echelon form to look for an inconsistencies.

Using the entry in position (1, 1) to eliminate the entries below it, we get the equivalent system

\begin{align*} \left[ \begin{array}{ccc|c} 1 & 2 & -1 & 4\\ 0 & 7 & -1 & 8\\ 0 & 0 & 0 & 1 \end{array}\right] \end{align*}

(22)

We are immediately done, as we have the row $\left[ \begin{array}{ccc|c} 0 & 0 & 0 & 1 \end{array}\right]$ , which corresponds to the equation $0x + 0y + 0z = 1$ . This is clearly impossible!

Therefore our system is inconsistent, and has zero solutions.

6A Geometric perspective¶

Suppose we have $m$ equations in three unknowns of the form

a_{i1}x_1 + a_{i2}x_2 + a_{i3}x_3 = b_i,

(23)

where $i = 1,2,\ldots,m$ . The solution set to each equation (23) defines a plane $P_i$ in three dimensional space. Therefore, when solving $A \textbf{x} = \textbf{b}$ , we are looking for a point $(x_1, x_2, x_3)$ that lies in all of the planes $P_i$ defined by the $m$ equations of the form (23).

Geometrically, we are looking for a point $\textbf{x}$ that lies in the intersection $P_1 \cap P_2 \cap \ldots \cap P_m$ . The picture below illustrates the three possible solution sets for $m=3$ equations with three unknowns.

This ends our initial exploration of solutions to systems of linear equations. Our story so far has been almost entirely algebraic in nature. However, the power and beauty of linear algebra is that it allows us to turn algebraic questions such as “Does $A\vv x = \vv b$ have a solution?” into geometric ones like “Do the planes defined by equations (23) intersect?” In the next lectures, we will explore this geometric perspective, and see that it allows us to unlock some incredibly powerful tools.