Skip to main content

Section 2.3 Solving linear systems

Let's continue with our model example from Section 2.2. Summarizing the various steps, we have

\begin{align*} \begin{array}{rcc} -2x_3+7x_5\amp =\amp 12 \\ 2x_1+4x_2-10x_3+6x_4+12x_5\amp = \amp 28 \\ 2x_1+4x_2-5x_3+6x_4-5x_5\amp =\amp -1 \end{array} \amp \xrightarrow[]{\text{ aug. mat. } }\begin{bmatrix}0\amp 0\amp -2\amp 0\amp 7\amp 12\\ 2\amp 4\amp -10\amp 6\amp 12\amp 28\\ 2\amp 4\amp -5\amp 6\amp -5\amp -1 \end{bmatrix}\\ \amp \xrightarrow[]{\text{ Gauss. elim. } }\begin{bmatrix}1\amp 2\amp -5\amp 3\amp 6\amp 14\\ 0\amp 0\amp 1\amp 0\amp -\frac{7}{2}\amp -6\\ 0\amp 0\amp 0\amp 0\amp 1\amp 2 \end{bmatrix}\\ \amp \xrightarrow[]{\text{ new system } }\begin{array}{rcc} x_1+2x_2-5x_3+3x_4+6x_5\amp =\amp 14\\ x_3-\frac{7}{2}x_5\amp =\amp -6\\ x_5\amp =\amp 2 \end{array}\text{.} \end{align*}

The new system in row echelon form is undoubtedly simpler, but describing all of its solutions still requires some subtle analysis.

Subsection 2.3.1 Model example

We begin by illustrating the general method for solving a linear system using our model example; a careful description of the procedure, along with a proof of its validity, is found in Theorem 2.3.5.

A key first step involves separating the variables of the system into free and leading variables.

Definition 2.3.1. Free and leading variables.

Let \(L\) be a linear system in the unknowns \(x_1,x_2,\dots, x_n\text{,}\) and let \(A\) be its associated augmented matrix. Assume \(L\) (and hence \(A\)) is in row echelon form.

The unknown \(x_j\) is a leading variable if the corresponding column in \(A\) (i.e., the \(i\)-th column) contains a leading one; it is a free variable if the corresponding column in \(A\) does not contain a leading one.

Let \(L\) be the linear system in the unknowns \(x_1, x_2, x_3, x_4\) with augmented matrix

\begin{equation*} A=\begin{amatrix}[cccc|r]\boxed{1}\amp1\amp3\amp2\amp4\\ 0\amp\boxed{1}\amp1\amp2\amp3\\ 0\amp0\amp0\amp\boxed{1}\amp-5 \end{amatrix}\text{.} \end{equation*}

Then \(x_1, x_2, x_4\) are leading variables, since the first, second, and fourth columns of \(A\) have leading ones, as indicated by the boxes. The variable \(x_3\) is free since the third column of \(A\) has no leading one.

In our model example we transformed the original system \(L\) to the equivalent system \(L'\) below:

\begin{equation*} \begin{linsys}{5} x_1\amp +\amp 2x_2\amp-\amp 5x_3\amp+\amp 3x_4 \amp +\amp 6x_5\amp =\amp 14\\ \amp \amp \amp \amp x_3\amp-\amp \amp \amp \frac{7}{2}x_5\amp =\amp -6\\ \amp \amp \amp \amp \amp \amp \amp \amp x_5\amp =\amp 2 \end{linsys}\text{.} \end{equation*}

The free variables of \(L'\) are \(x_2\) and \(x_4\text{;}\) the leading variables are \(x_1, x_3\text{,}\) and \(x_5\text{.}\) Observe that if we assign \(x_2=s\) and \(x_4=t\text{,}\) where \(r\) and \(s\) are any real numbers, then we are left with a system \(L''\) in three unknowns (\(x_1,x_3,x_5\)) of the form

\begin{equation*} \begin{linsys}{3} x_1\amp-\amp 5x_3\amp+\amp 6x_5\amp= \amp 14-2s-3t\\ \amp \amp x_3\amp -\amp \frac{7}{2}x_5\amp = \amp -6\\ \amp \amp \amp \amp x_5\amp =\amp 2 \end{linsys}\text{.} \end{equation*}

Using back-substitution, we see that the unknowns \(x_1, x_3, x_5\) are then uniquely expressed in terms of \(s\) and \(t\) as

\begin{equation} x_5=2, x_3=1, x_1=7-2s-3t.\label{ex_modelSolve}\tag{2.3.1} \end{equation}

Thus for any choice of real numbers \(s\) and \(t\) we get a unique solution of the form

\begin{equation*} (x_1,x_2,x_3,x_4,x_5)=(7-2s-3t, s, 1, t, 2)\text{.} \end{equation*}

We conclude the set \(S\) of solutions to \(L\) is given as

\begin{equation} S=\left\{(7-2s-3t, s, 1, t, 2)\colon s, t\in\R\right\}.\label{s_solving_eq_setnotation}\tag{2.3.2} \end{equation}

Alternatively, we can describe the solutions to \(L\) with the parametric equations

\begin{equation} x_1=7-2s-3t, x_2=s, x_3=1, t=t, x_5=2, \ t,s\in\R.\label{s_solving_eq_parametric}\tag{2.3.3} \end{equation}

Remark 2.3.3. Mandate.

Get used to describing solutions to linear systems using either the set notation format of (2.3.2) or the parametric equation format of (2.3.3).

Note also the distinct roles played by free and leading variables in the description of solutions. We assign each free variable freely to any choice of real parameters (\(s\) and \(t\) in our example), and then solve for the leading variables in terms of these parameters in a unique manner. In particular, the leading variables are completely determined by our assignment of free variables.

Subsection 2.3.2 General method for solving linear systems

Before describing a precise algorithm for computing the set of solutions to a linear system, we must address the possibility that there are no solutions to the system whatsoever. Such a system is called inconsistent.

Definition 2.3.4. Consistent and inconsistent systems.

A linear system is consistent if it has at least one solution; it is inconsistent if it has no solutions.

We are now in a position to describe an algorithm for computing the set of solutions of a linear system.

First recall that \(L\) and \(L'\) have the same set of solutions (Theorem 2.1.12). So it suffices to show that the algorithm returns the correct set of solutions to \(L'\text{.}\)

Regarding consistency: if the last column of the augmented matrix \(U\) associated to \(L'\) has a leading one in the \(i\)-th row, then the corresponding equation in \(L'\) is

\begin{equation*} 0x_1+0x_2+\cdots 0x_n=1. \end{equation*}

Clearly this equation has no solutions, and hence the set of solutions to \(L'\) is empty.

Suppose now that the last column of \(U\) does not have a leading one.

Case 1: no free variables.

Suppose in Step 3 you determine that there are no free variables. Then each of the first \(n\) columns of \(U\) has a leading one in it. If follows that for each \(1\leq i \leq n\) the \(i\)-th equation of \(L'\) is of the form

\begin{equation} x_i+c_{i,i+1}x_{i+1}+\cdots c_{i,n}x_n=b_i.\label{s_solving_case1eq}\tag{2.3.4} \end{equation}

Since \(U\) does not have a leading one in the last column, it follows that all equations beyond the \(n\)-th equation are of the form \(0x_1+0x_2+\cdots 0x_n=0\text{,}\) and as such may be disregarded since they are satisfied by any choice of the \(x_i\text{.}\) The remaining system of \(n\) equations in \(n\) unknowns can be solved by back-substitution, yielding a unique solution \((x_1,x_2,\dots, x_n)\) of the form

\begin{align*} x_n \amp =b_n \\ x_{n-1}\amp =b_{n-1}-c_{n-1,n}x_n=b_{n-1}-c_{n-1,n}b_n \\ x_{n-2}\amp = b_{n-2}-c_{n-2,n}x_{n}-c_{n-2,n-1}x_{n-1}\\ \amp =b_{n-2}-c_{n-2,n}b_n-c_{n-2,n-1}(b_{n-1}-c_{n-1,n}b_n)\\ \amp \vdots \end{align*}

Do not concern yourself overly with the exact formulas. The important point here is that once we know there is a unique assignment of the variables \(x_n, x_{n-1},\dots, x_{i+1}\) that satisfies the system, (2.3.4) allows us to solve for \(x_i\) in terms of the the \(x_j\text{,}\) \(j>i\text{.}\) As such working our way up from the last equation, we find there is a unique solution to the system.

Case 2: free variables.

Suppose now that \(x_{i_1}, x_{i_2},\dots , x_{i_r}\) are the leading variables of \(L'\text{,}\) and \(x_{j_1}, x_{j_2},\dots, x_{j_s}\) are the free variables. Again, since \(U\) does not have a leading one in the last column, there are exactly \(r\) nonzero equations in \(L'\text{:}\) one for each leading variable. After bringing any terms involving free variables to the right, the \(k\)-th such equation takes the form

\begin{equation*} x_{i_k}+c_{k,k+1}x_{i_{k+1}}+\cdots c_{k,r}x_{i_{r}}=d_k-G_k(x_{j_1},x_{j_2},\dots, x_{j_s})\text{.} \end{equation*}

As in the previous case, back-substitution now allows us to solve for each leading variable as a function of the free variables:

\begin{align*} x_{i_r}\amp =d_r-G_r(x_{j_1},x_{j_2},\dots, x_{j_s})\\ \amp =F_s(x_{j_1},x_{j_2},\dots, x_{j_s})\\ x_{i_{r-1}}\amp=d_{r-1}-c_{r}x_{i_r}-G_{r-1}(x_{j_1},x_{j_2},\dots, x_{j_s})\\ \amp = d_{r-1}-c_{r}F_r(x_{j_1},x_{j_2},\dots, x_{j_s})-G_{r-1}(x_{j_1},x_{j_2},\dots, x_{j_s})\\ \amp =F_{r-1}(x_{j_1},x_{j_2},\dots, x_{j_s})\\ \amp \vdots \\ x_1 \amp=F_1(x_{j_1},x_{j_2},\dots, x_{j_s}) \end{align*}

This new system of equations clearly has the same set of solutions as \(L'\) (and \(L\)), since it was obtained from \(L'\) by deleting zero rows of \(U\) and using only addition and subtraction operations. Furthermore, it is clear that any assignment of the free variables

\begin{equation*} x_{j_1}=t_1, x_{j_2}=t_2,\dots, x_{j_s}=t_s \end{equation*}

extends uniquely to the solution of \(L'\) that further assigns

\begin{equation*} x_{i_1}=F_1(t_1,t_2,\dots, t_s), x_{i_2}=F_2(t_1,t_2,\dots, t_s), \dots, x_r=F_r(t_1,t_2,\dots, t_s)\text{.} \end{equation*}

The idea behind uniqueness here, is that once you assign values to the free variables, the values of the leading variables are completely determined by the equations \(x_{i_k}=F_k(x_{j_1},x_{j_2},\dots, x_{j_s})\text{.}\)

Lastly, we show that every solution of \(L'\) (and \(L\)) is obtained in this way. Suppose \(u=(u_1,u_2,\dots, u_n)\) is a solution. According to the discussion above \(u\) must be the unique solution to \(L'\) corresponding to the free variable assignment

\begin{equation*} x_{j_1}=u_{j_1}, x_{j_2}=u_{j_2},\dots , x_{j_s}=u_{j_s} \end{equation*}

and corresponding leading variable assignment

\begin{equation*} x_{i_1}=F_1(u_{j_1},x_{j_2},\dots, x_{i_2}), x_{i_2}=F_2(u_{j_1},x_{j_2},\dots, x_{j_s}),\dots, x_{i_r}=F_r(u_{j_1},x_{j_2},\dots, x_{j_s})\text{.} \end{equation*}

Interesting in its own right is the following corollary of Theorem 2.3.5, which tells us that a linear system has either no solutions, exactly one solutions, or infinitely many solutions.

The decision tree in Figure 2.3.7 concisely summarizes the different cases articulated in Corollary 2.3.6.

Figure 2.3.7. Decision tree for the number of solutions to a linear system with augmented matrix \(U\) in row echelon form.

Video examples of solving linear systems.

Figure 2.3.8. First example: solving linear systems
Figure 2.3.9. Second example: solving linear systems

Solutions to homogeneous systems.

Consider the special case of a homogeneous system

\begin{equation*} \homsys \end{equation*}

Such a system is always consistent. Why? Observe that \((x_1,x_2,\dots, x_n)=(0,0,\dots, 0)\) is guaranteed to be a solution. Alternatively, it is easy to see that row reducing the system results in an augmented matrix \(U\) whose last column is a zero column: a zero column certainly contains no leading ones. Thus, in the special case of a homogeneous system, Corollary 2.3.6 boils down to the following result.

Exercises 2.3.3 Exercises

Exercise Group.

Solve the following systems of equations.

  • When row reducing follow Gaussian elimination to the letter.

  • Make sure to indicate how variables are sorted into free and dependent variables.

  • Express your answer in both the parametric equation format and set notation format.

1.
\begin{equation*} \begin{linsys}{4} x_1\amp +\amp 2x_2\amp =\amp x_3\amp +\amp x_4\amp +\amp 3\\ 3x_1\amp +\amp 6x_2\amp =\amp 2x_3\amp -\amp 4x_4\amp +\amp 8\\ -x_1\amp +\amp 2x_3\amp =\amp 2x_2\amp -\amp x_4\amp -\amp 1 \end{linsys} \end{equation*}
Solution.

We saw in Exercise 2.2.3.4 that the system is equivalent to a system \(L'\) with augmented matrix

\begin{equation*} \begin{amatrix}[rrrr|r]\boxed{1}\amp 2\amp -1\amp -1\amp 3\\ 0\amp 0\amp \boxed{1}\amp 7\amp -1\\ 0\amp 0\amp 0\amp \boxed{1}\amp -\frac{3}{7} \end{amatrix}\text{.} \end{equation*}

The row echelon matrix tells us that \(x_2=t\) is the only free variable of \(L'\text{.}\) Back substitution then yields the parametric equation description:

\begin{align*} x_1\amp = \frac{32}{7}-2t\\ x_2\amp = t\\ x_3\amp = 2\\ x_4\amp = -\frac{3}{7}\text{.} \end{align*}

Thus the set of solutions is

\begin{equation*} \left\{ \left(\frac{32}{7}-2t, t, 2, -\frac{3}{7}\right)\colon t\in \R\right\}\text{.} \end{equation*}
2.
\begin{equation*} \begin{linsys}{4} x_1\amp +\amp x_2\amp -\amp x_3\amp +\amp x_4\amp =\amp 1\\ -2x_1\amp -\amp 2x_2\amp +\amp 2x_3\amp -\amp 2x_4\amp =\amp -2\\ x_1\amp +\amp x_2\amp +\amp x_3\amp +\amp 2x_4\amp =\amp 3 \end{linsys} \end{equation*}
3.
\begin{equation*} \begin{linsys}{3} 2x_1 \amp +\amp 2x_2 \amp +\amp 2x_3\amp =\amp 0\\ -2x_1 \amp +\amp 5x_2 \amp +\amp 2x_3\amp =\amp 1\\ 8x_1 \amp +\amp x_2 \amp +\amp 4x_3\amp =\amp -1 \end{linsys} \end{equation*}
4.
\begin{equation*} \begin{linsys}{3} \amp \amp -2b \amp +\amp 3c\amp =\amp 1\\ 3a \amp +\amp 6b \amp -\amp 3c\amp =\amp -2\\ 6a \amp +\amp 6b \amp +\amp 3c\amp =\amp 5 \end{linsys} \end{equation*}
5.
\begin{equation*} \begin{linsys}{5} \amp \amp \amp \amp T_3\amp +\amp T_4\amp +\amp T_5 \amp =\amp 0\\ -T_1\amp -\amp T_2 \amp +\amp 2T_3 \amp -\amp 3T_4\amp +\amp T_5 \amp =\amp 0\\ T_1\amp + \amp T_2 \amp -\amp 2T_3 \amp \amp \amp -\amp T_5 \amp =\amp 0\\ 2T_1\amp + \amp 2T_2 \amp -\amp T_3 \amp \amp \amp +\amp T_5 \amp =\amp 0 \end{linsys} \end{equation*}

6.

For each system below determine all values of \(a\) for which the system below has (a) no solutions, (b) a unique solution, and (c) infinitely many solutions.

  1. \begin{equation*} \begin{linsys}{3} x\amp +\amp 2y\amp +\amp z\amp =\amp 2\\ 2x\amp -\amp 2y\amp +\amp 3z\amp =\amp 1\\ x\amp +\amp 2y\amp -\amp (a^2-3)z\amp =\amp a \end{linsys} \end{equation*}

  2. \begin{equation*} \begin{linsys}{3} x\amp +\amp 2y\amp -\amp 3z\amp =\amp 4\\ 3x\amp -\amp y\amp +\amp 5z\amp =\amp 2\\ 4x\amp +\amp y\amp +\amp (a^2-14)z\amp =\amp a+2 \end{linsys} \end{equation*}

7.

Show that a linear system with more unknowns than equations has either 0 solutions or infinitely many solutions.

8.

True or false. If true, provide a proof; if false, provide an explicit counterexample.

  1. Every matrix has a unique row echelon form.

  2. Any homogeneous linear system with more unknowns than equations has infinitely many solutions.

  3. If a homogeneous linear system of \(n\) equations in \(n\) unknowns has a corresponding augmented matrix with a reduced row echelon form containing \(n\) leading ones, then the linear system has the unique solution \(s=(0,0,\dots, 0)\text{.}\)

  4. All leading ones in of a matrix in row echelon form must occur in distinct columns.

  5. If the reduced row echelon form of the augmented matrix for a linear system has a zero row, then the system must have infinitely many solutions.

  6. If a linear system has more unknowns than equations, then it must have infinitely many solutions.

9.

Interpret each matrix below as an augmented matrix of a linear system. Asterisks represent an unspecified real number. For each matrix, determine whether the corresponding system is consistent or inconsistent. If the system is consistent, decide further whether the solution is unique or not. If there is not enough information answer ‘inconclusive’ and back up your claim by giving an explicit example where the system is consistent, and an explicit example where the system is inconsistent.

  1. \(\displaystyle \begin{bmatrix}1\amp *\amp *\amp *\\ 0\amp 1\amp *\amp *\\ 0\amp 0\amp 1\amp 1 \end{bmatrix}\)

  2. \(\displaystyle \begin{bmatrix}1\amp 0\amp 0\amp *\\ *\amp 1\amp 0\amp *\\ *\amp *\amp 1\amp * \end{bmatrix}\)

  3. \(\displaystyle \begin{bmatrix}1\amp 0\amp 0\amp 0\\ 1\amp 0\amp 0\amp 1\\ 1\amp *\amp *\amp * \end{bmatrix}\)

  4. \(\displaystyle \begin{bmatrix}1\amp *\amp *\amp *\\ 1\amp 0\amp 0\amp 1\\ 1\amp 0\amp 0\amp 1 \end{bmatrix}\)

10.

What condition must \(a, b,\) and \(c\) satisfy in order for the system below to be consistent? Express your answer as an equation involving \(a, b,\) and \(c\text{.}\)

\begin{equation*} \begin{linsys}{3} x\amp +\amp 3y\amp +\amp z\amp =\amp a\\ -x\amp -\amp 2y\amp +\amp z\amp =\amp b\\ 3x\amp +\amp 7y\amp -\amp z\amp =\amp c \end{linsys} \end{equation*}

11.

Solve the system of equations below for \(x\text{,}\) \(y\text{,}\) and \(z\text{.}\)

\begin{equation*} \begin{linsys}{3} \frac{1}{x}\amp +\amp \frac{2}{y}\amp -\amp \frac{4}{z}\amp =\amp 1\\ \\ \frac{2}{x}\amp +\amp \frac{3}{y}\amp +\amp \frac{8}{z}\amp =\amp 0\\ \\ -\frac{1}{x}\amp +\amp \frac{9}{y}\amp +\amp \frac{10}{z}\amp =\amp 5 \end{linsys} \end{equation*}
Hint.

First replace the given nonlinear system with a linear one using a change of variable substitution.

12.

If \(A\) is a matrix with three rows and five columns, then what is the maximum possible number of leading ones in its reduced row echelon form? Justify your answer.

Provide an explicit example of a matrix that attains this maximum number of leading ones.

13.

If \(A\) is a matrix with three rows and six columns, then what is the maximum possible number of free variables in the general solution of the linear system with augmented matrix \(A\text{?}\) Justify your answer.

Provide an explicit example of a matrix that attains this maximal number of free variables.

14.

If \(A\) is a matrix with five rows and three columns, then what is the minimum possible number of zero rows in any row echelon form of \(A\text{?}\)

Provide an explicit example of a matrix that attains this minimal number of zero rows.