Skip to main content

Section LC Linear Combinations

In Section VO we defined vector addition and scalar multiplication. These two operations combine nicely to give us a construction known as a linear combination, a construct that we will work with throughout this course.

Subsection LC Linear Combinations

Definition LCCV. Linear Combination of Column Vectors.

Given \(n\) vectors \(\vectorlist{u}{n}\) from \(\complex{m}\) and \(n\) scalars \(\alpha_1,\,\alpha_2,\,\alpha_3,\,\ldots,\,\alpha_n\text{,}\) their linear combination is the vector

\begin{equation*} \lincombo{\alpha}{u}{n} \end{equation*}

So this definition takes an equal number of scalars and vectors, combines them using our two new operations (scalar multiplication and vector addition) and creates a single brand-new vector, of the same size as the original vectors. When a definition or theorem employs a linear combination, think about the nature of the objects that go into its creation (lists of scalars and vectors), and the type of object that results (a single vector). Computationally, a linear combination is pretty easy.

Suppose that

\begin{align*} \alpha_1=1&&\alpha_2=-4&&\alpha_3=2&&\alpha_4=-1 \end{align*}

and

\begin{align*} \vect{u}_1&=\colvector{2\\4\\-3\\1\\2\\9}& \vect{u}_2&=\colvector{6\\3\\0\\-2\\1\\4}& \vect{u}_3&=\colvector{-5\\2\\1\\1\\-3\\0}& \vect{u}_4&=\colvector{3\\2\\-5\\7\\1\\3} \end{align*}

then their linear combination is

\begin{align*} \alpha_1\vect{u_1}+ \alpha_2\vect{u_2}+ \alpha_3\vect{u_3}+ \alpha_4\vect{u_4}& = (1)\colvector{2\\4\\-3\\1\\2\\9}+ (-4)\colvector{6\\3\\0\\-2\\1\\4}+ (2)\colvector{-5\\2\\1\\1\\-3\\0}+ (-1)\colvector{3\\2\\-5\\7\\1\\3}\\ &=\colvector{2\\4\\-3\\1\\2\\9}+ \colvector{-24\\-12\\0\\8\\-4\\-16}+ \colvector{-10\\4\\2\\2\\-6\\0}+ \colvector{-3\\-2\\5\\-7\\-1\\-3} =\colvector{-35\\-6\\4\\4\\-9\\-10} \end{align*}

A different linear combination, of the same set of vectors, can be formed with different scalars. Take

\begin{align*} \beta_1=3&&\beta_2=0&&\beta_3=5&&\beta_4=-1 \end{align*}

and form the linear combination

\begin{align*} \beta_1\vect{u_1}+ \beta_2\vect{u_2}+ \beta_3\vect{u_3}+ \beta_4\vect{u_4}&= (3)\colvector{2\\4\\-3\\1\\2\\9}+ (0)\colvector{6\\3\\0\\-2\\1\\4}+ (5)\colvector{-5\\2\\1\\1\\-3\\0}+ (-1)\colvector{3\\2\\-5\\7\\1\\3}\\ &= \colvector{6\\12\\-9\\3\\6\\27}+ \colvector{0\\0\\0\\0\\0\\0}+ \colvector{-25\\10\\5\\5\\-15\\0}+ \colvector{-3\\-2\\5\\-7\\-1\\-3} =\colvector{-22\\20\\1\\1\\-10\\24} \end{align*}

Notice how we could keep our set of vectors fixed, and use different sets of scalars to construct different vectors. You might build a few new linear combinations of \(\vect{u}_1,\,\vect{u}_2,\,\vect{u}_3,\,\vect{u}_4\) right now. We will be right here when you get back. What vectors were you able to create? Do you think you could create the vector \(\vect{w}\) with a “suitable” choice of four scalars?

\begin{equation*} \vect{w}=\colvector{13\\15\\5\\-17\\2\\25} \end{equation*}

Do you think you could create any possible vector from \(\complex{6}\) by choosing the proper scalars? These last two questions are very fundamental, and time spent considering them now will prove beneficial later.

We can redo Example TLC with Sage. First we build the relevant vectors and then do the computation.

With a linear combination combining many vectors, we sometimes will use more compact ways of forming a linear combination. So we will redo the second linear combination of \(\vect{u}_1,\,\vect{u}_2,\,\vect{u}_3,\,\vect{u}_4\) using a list comprehension and the sum() function.

We have constructed two lists and used a list comprehension to just form the scalar multiple of each vector as part of the list multiples. Now we use the sum() function to add them all together.

We can improve on this in two ways. First, we can determine the number of elements in any list with the len() function. So we do not have to count up that we have 4 vectors (not that it is very hard to count!). Second, we can combine this all into one line, once we have defined the list of vectors and the list of scalars.

The corresponding expression in mathematical notation, after a change of names and with counting starting from 1, would roughly be:

\begin{gather*} \sum_{i=1}^4 a_i\vect{u}_i \end{gather*}

Using sum() and a list comprehension might be overkill in this example, but we will find it very useful in just a minute.

Our next two examples are key ones, and a discussion about decompositions is timely. Have a look at Proof Technique DC before studying the next two examples.

In this example we will rewrite Archetype B in the language of vectors, vector equality and linear combinations. In Example VESE we wrote the system of \(m=3\) equations as the vector equality

\begin{equation*} \colvector{-7x_1 -6 x_2 - 12x_3\\ 5x_1 + 5x_2 + 7x_3\\ x_1 +4x_3} = \colvector{-33\\24\\5}\text{.} \end{equation*}

Now we will bust up the linear expressions on the left, first using vector addition,

\begin{equation*} \colvector{-7x_1\\ 5x_1\\x_1}+ \colvector{-6 x_2\\5x_2\\0x_2}+ \colvector{-12x_3\\7x_3\\4x_3} = \colvector{-33\\24\\5}\text{.} \end{equation*}

Now we can rewrite each of these vectors as a scalar multiple of a fixed vector, where the scalar is one of the unknown variables, converting the left-hand side into a linear combination

\begin{equation*} x_1\colvector{-7\\5\\1}+ x_2\colvector{-6\\5\\0}+ x_3\colvector{-12\\7\\4} = \colvector{-33\\24\\5}\text{.} \end{equation*}

We can now interpret the problem of solving the system of equations as determining values for the scalar multiples that make the vector equation true. In the analysis of Archetype B, we were able to determine that it had only one solution. A quick way to see this is to row-reduce the coefficient matrix to the \(3\times 3\) identity matrix and apply Theorem NMRRI to determine that the coefficient matrix is nonsingular. Then Theorem NMUS tells us that the system of equations has a unique solution. This solution is

\begin{align*} x_1 = -3&&x_2 = 5&&x_3 = 2\text{.} \end{align*}

So, in the context of this example, we can express the fact that these values of the variables are a solution by writing the linear combination,

\begin{equation*} (-3)\colvector{-7\\5\\1}+ (5)\colvector{-6\\5\\0}+ (2)\colvector{-12\\7\\4} = \colvector{-33\\24\\5}\text{.} \end{equation*}

Furthermore, these are the only three scalars that will accomplish this equality, since they come from a unique solution.

Notice how the three vectors in this example are the columns of the coefficient matrix of the system of equations. This is our first hint of the important interplay between the vectors that form the columns of a matrix, and the matrix itself.

With any discussion of Archetype A or Archetype B we should be sure to contrast with the other.

As a vector equality, Archetype A can be written as

\begin{equation*} \colvector{x_1 -x_2 +2x_3\\2x_1+ x_2 + x_3\\ x_1 + x_2} = \colvector{1\\8\\5} \end{equation*}

Now bust up the linear expressions on the left, first using vector addition,

\begin{equation*} \colvector{x_1\\2x_1\\x_1}+ \colvector{-x_2\\x_2\\x_2}+ \colvector{2x_3\\x_3\\0x_3} = \colvector{1\\8\\5} \end{equation*}

Rewrite each of these vectors as a scalar multiple of a fixed vector, where the scalar is one of the unknown variables, converting the left-hand side into a linear combination

\begin{equation*} x_1\colvector{1\\2\\1}+ x_2\colvector{-1\\1\\1}+ x_3\colvector{2\\1\\0} = \colvector{1\\8\\5} \end{equation*}

Row-reducing the augmented matrix for Archetype A leads to the conclusion that the system is consistent and has free variables, hence infinitely many solutions. So for example, the two solutions

\begin{align*} x_1 = 2&&x_2 = 3&&x_3 = 1\\ x_1 = 3&&x_2 = 2&&x_3 = 0 \end{align*}

can be used together to say that

\begin{equation*} (2)\colvector{1\\2\\1}+ (3)\colvector{-1\\1\\1}+ (1)\colvector{2\\1\\0} = \colvector{1\\8\\5} = (3)\colvector{1\\2\\1}+ (2)\colvector{-1\\1\\1}+ (0)\colvector{2\\1\\0}\text{.} \end{equation*}

Ignore the middle of this equation, and move all the terms to the left-hand side,

\begin{equation*} (2)\colvector{1\\2\\1}+ (3)\colvector{-1\\1\\1}+ (1)\colvector{2\\1\\0}+ (-3)\colvector{1\\2\\1}+ (-2)\colvector{-1\\1\\1}+ (-0)\colvector{2\\1\\0} = \colvector{0\\0\\0}\text{.} \end{equation*}

Regrouping gives

\begin{equation*} (-1)\colvector{1\\2\\1}+ (1)\colvector{-1\\1\\1}+ (1)\colvector{2\\1\\0} = \colvector{0\\0\\0} \end{equation*}

Notice that these three vectors are the columns of the coefficient matrix for the system of equations in Archetype A. This equality says there is a linear combination of those columns that equals the vector of all zeros. Give it some thought, and realize this says that

\begin{align*} x_1=-1&&x_2=1&&x_3=1 \end{align*}

is a nontrivial solution to the homogeneous system of equations with the coefficient matrix for the original system in Archetype A. In particular, this demonstrates that this coefficient matrix is singular.

There is a lot going on in the last two examples. Come back to them in a while and make some connections with the intervening material. For now, we will summarize and explain some of this behavior with a theorem.

The proof of this theorem is as much about a change in notation as it is about making logical deductions. Write the system of equations \(\linearsystem{A}{\vect{b}}\) as

\begin{align*} a_{11}x_1+a_{12}x_2+a_{13}x_3+\dots+a_{1n}x_n&=b_1\\ a_{21}x_1+a_{22}x_2+a_{23}x_3+\dots+a_{2n}x_n&=b_2\\ a_{31}x_1+a_{32}x_2+a_{33}x_3+\dots+a_{3n}x_n&=b_3\\ \vdots&\\ a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\dots+a_{mn}x_n&=b_m\text{.} \end{align*}

Notice then that the entry of the coefficient matrix \(A\) in row \(i\) and column \(j\) has two names: \(a_{ij}\) as the coefficient of \(x_j\) in equation \(i\) of the system and \(\vectorentry{\vect{A}_j}{i}\) as the \(i\)-th entry of the column vector in column \(j\) of the coefficient matrix \(A\text{.}\) Likewise, entry \(i\) of \(\vect{b}\) has two names: \(b_i\) from the linear system and \(\vectorentry{\vect{b}}{i}\) as an entry of a vector. Our theorem is an equivalence (Proof Technique E) so we need to prove both “directions.”

(⇐) 

Suppose we have the vector equality between \(\vect{b}\) and the linear combination of the columns of \(A\text{.}\) Then for \(1\leq i\leq m\text{,}\)

\begin{align*} b_i &=\vectorentry{\vect{b}}{i}&&\knowl{./knowl/definition-CV.html}{\text{Definition CV}}\\ &=\vectorentry{ \vectorentry{\vect{x}}{1}\vect{A}_1+ \vectorentry{\vect{x}}{2}\vect{A}_2+ \vectorentry{\vect{x}}{3}\vect{A}_3+ \cdots+ \vectorentry{\vect{x}}{n}\vect{A}_n }{i}&&\text{Hypothesis}\\ &= \vectorentry{\vectorentry{\vect{x}}{1}\vect{A}_1}{i}+ \vectorentry{\vectorentry{\vect{x}}{2}\vect{A}_2}{i}+ \vectorentry{\vectorentry{\vect{x}}{3}\vect{A}_3}{i}+ \cdots+ \vectorentry{\vectorentry{\vect{x}}{n}\vect{A}_n}{i} &&\knowl{./knowl/definition-CVA.html}{\text{Definition CVA}}\\ &= \vectorentry{\vect{x}}{1}\vectorentry{\vect{A}_1}{i}+ \vectorentry{\vect{x}}{2}\vectorentry{\vect{A}_2}{i}+ \vectorentry{\vect{x}}{3}\vectorentry{\vect{A}_3}{i}+ \cdots+ \vectorentry{\vect{x}}{n}\vectorentry{\vect{A}_n}{i} &&\knowl{./knowl/definition-CVSM.html}{\text{Definition CVSM}}\\ &= \vectorentry{\vect{x}}{1}a_{i1}+ \vectorentry{\vect{x}}{2}a_{i2}+ \vectorentry{\vect{x}}{3}a_{i3}+ \cdots+ \vectorentry{\vect{x}}{n}a_{in} &&\knowl{./knowl/definition-CV.html}{\text{Definition CV}}\\ &= a_{i1}\vectorentry{\vect{x}}{1}+ a_{i2}\vectorentry{\vect{x}}{2}+ a_{i3}\vectorentry{\vect{x}}{3}+ \cdots+ a_{in}\vectorentry{\vect{x}}{n} &&\knowl{./knowl/property-CMCN.html}{\text{Property CMCN}}\text{.} \end{align*}

This says that the entries of \(\vect{x}\) form a solution to equation \(i\) of \(\linearsystem{A}{\vect{b}}\) for all \(1\leq i\leq m\text{,}\) in other words, \(\vect{x}\) is a solution to \(\linearsystem{A}{\vect{b}}\text{.}\)

(⇒) 

Suppose now that \(\vect{x}\) is a solution to the linear system \(\linearsystem{A}{\vect{b}}\text{.}\) Then for all \(1\leq i\leq m\text{,}\)

\begin{align*} \vectorentry{\vect{b}}{i} &=b_i&&\knowl{./knowl/definition-CV.html}{\text{Definition CV}}\\ &= a_{i1}\vectorentry{\vect{x}}{1}+ a_{i2}\vectorentry{\vect{x}}{2}+ a_{i3}\vectorentry{\vect{x}}{3}+ \cdots+ a_{in}\vectorentry{\vect{x}}{n} &&\text{Hypothesis}\\ &= \vectorentry{\vect{x}}{1}a_{i1}+ \vectorentry{\vect{x}}{2}a_{i2}+ \vectorentry{\vect{x}}{3}a_{i3}+ \cdots+ \vectorentry{\vect{x}}{n}a_{in} &&\knowl{./knowl/property-CMCN.html}{\text{Property CMCN}}\\ &= \vectorentry{\vect{x}}{1}\vectorentry{\vect{A}_1}{i}+ \vectorentry{\vect{x}}{2}\vectorentry{\vect{A}_2}{i}+ \vectorentry{\vect{x}}{3}\vectorentry{\vect{A}_3}{i}+ \cdots+ \vectorentry{\vect{x}}{n}\vectorentry{\vect{A}_n}{i} &&\knowl{./knowl/definition-CV.html}{\text{Definition CV}}\\ &= \vectorentry{\vectorentry{\vect{x}}{1}\vect{A}_1}{i}+ \vectorentry{\vectorentry{\vect{x}}{2}\vect{A}_2}{i}+ \vectorentry{\vectorentry{\vect{x}}{3}\vect{A}_3}{i}+ \cdots+ \vectorentry{\vectorentry{\vect{x}}{n}\vect{A}_n}{i} &&\knowl{./knowl/definition-CVSM.html}{\text{Definition CVSM}}\\ &=\vectorentry{ \vectorentry{\vect{x}}{1}\vect{A}_1+ \vectorentry{\vect{x}}{2}\vect{A}_2+ \vectorentry{\vect{x}}{3}\vect{A}_3+ \cdots+ \vectorentry{\vect{x}}{n}\vect{A}_n }{i}&&\knowl{./knowl/definition-CVA.html}{\text{Definition CVA}}\text{.} \end{align*}

So the entries of the vector \(\vect{b}\text{,}\) and the entries of the vector that is the linear combination of the columns of \(A\text{,}\) agree for all \(1\leq i\leq m\text{.}\) By Definition CVE we see that the two vectors are equal, as desired.

In other words, this theorem tells us that solutions to systems of equations are linear combinations of the \(n\) column vectors of the coefficient matrix (\(\vect{A}_j\)) which yield the constant vector \(\vect{b}\text{.}\) Or said another way, a solution to a system of equations \(\linearsystem{A}{\vect{b}}\) is an answer to the question “How can I form the vector \(\vect{b}\) as a linear combination of the columns of \(A\text{?}\)” Look through the Archetypes that are systems of equations and examine a few of the advertised solutions. In each case use the solution to form a linear combination of the columns of the coefficient matrix and verify that the result equals the constant vector (see Exercise LC.C21).

We can easily illustrate Theorem SLSLC with Sage. We will use Archetype F as an example.

A solution to this system is \(x_1=1,\,x_2=2,\,x_3=-2,\,x_4=4\text{.}\) So we will use these four values as scalars in a linear combination of the columns of the coefficient matrix. However, we do not have to type in the columns individually, we can have Sage extract them all for us into a list with the matrix method .columns().

With our scalars also in a list, we can compute the linear combination of the columns, like we did in Sage LC.

So we see that the solution gives us scalars that yield the vector of constants as a linear combination of the columns of the coefficient matrix. Exactly as predicted by Theorem SLSLC. We can duplicate this observation with just one line.

In a similar fashion we can test other potential solutions. With theory we will develop later, we will be able to determine that Archetype F has only one solution. Since Theorem SLSLC is an equivalence (Proof Technique E), any other choice for the scalars should not create the vector of constants as a linear combination.

Now would be a good time to find another system of equations, perhaps one with infinitely many solutions, and practice the techniques above.

Subsection VFSS Vector Form of Solution Sets

We have written solutions to systems of equations as column vectors. For example Archetype B has the solution \(x_1 = -3,\,x_2 = 5,\,x_3 = 2\) which we write as

\begin{equation*} \vect{x}=\colvector{x_1\\x_2\\x_3}=\colvector{-3\\5\\2}\text{.} \end{equation*}

Now, we will use column vectors and linear combinations to express all of the solutions to a linear system of equations in a compact and understandable way. First, here are two examples that will motivate our next theorem. This is a valuable technique, almost the equal of row-reducing a matrix, so be sure you get comfortable with it over the course of this section.

Archetype D is a linear system of 3 equations in 4 variables. Row-reducing the augmented matrix yields

\begin{equation*} \begin{bmatrix} \leading{1} & 0 & 3 & -2 & 4 \\ 0 & \leading{1} & 1 & -3 & 0\\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{equation*}

and we see \(r=2\) pivot columns. Also, \(D=\set{1,\,2}\) so the dependent variables are then \(x_1\) and \(x_2\text{.}\) \(F=\set{3,\,4,\,5}\) so the two free variables are \(x_3\) and \(x_4\text{.}\) We will express a generic solution for the system by two slightly different methods, though both arrive at the same conclusion.

First, we will decompose (Proof Technique DC) a solution vector. Rearranging each equation represented in the row-reduced form of the augmented matrix by solving for the dependent variable in each row yields the vector equality

\begin{align*} \colvector{x_1\\x_2\\x_3\\x_4}&= \colvector{4-3x_3+2x_4\\ -x_3+3x_4\\x_3\\x_4}\\ \end{align*}

Now we will use the definitions of column vector addition and scalar multiplication to express this vector as a linear combination

\begin{align*} &=\colvector{4\\0\\0\\0}+ \colvector{-3x_3\\-x_3\\x_3\\0}+ \colvector{2x_4\\3x_4\\0\\x_4}&& \knowl{./knowl/definition-CVA.html}{\text{Definition CVA}}\\ &=\colvector{4\\0\\0\\0}+ x_3\colvector{-3\\-1\\1\\0}+ x_4\colvector{2\\3\\0\\1}&& \knowl{./knowl/definition-CVSM.html}{\text{Definition CVSM}}\text{.} \end{align*}

We will develop the same linear combination a bit quicker, using three steps. While the method above is instructive, the method below will be our preferred approach.

Step 1. Write the vector of variables as a fixed vector, plus a linear combination of \(n-r\) vectors, using the free variables as the scalars.

\begin{equation*} \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4}= \colvector{\ \ \\\ \\\ \\\ }+x_3\colvector{\ \ \\\ \\\ \\\ }+x_4\colvector{\ \ \\\ \\\ \\\ }\text{.} \end{equation*}

Step 2. Use 0's and 1's to ensure equality for the entries of the vectors with indices in \(F\) (corresponding to the free variables).

\begin{equation*} \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4}= \colvector{\ \\\ \\0\\0}+x_3\colvector{\ \\\ \\1\\0}+x_4\colvector{\ \\\ \\0\\1} \end{equation*}

Step 3. For each dependent variable, use the augmented matrix to formulate an equation expressing the dependent variable as a constant plus multiples of the free variables. Convert this equation into entries of the vectors that ensure equality for each dependent variable, one at a time.

\begin{align*} x_1=4-3x_3+2x_4&&\Rightarrow&& \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4}= \colvector{4\\\ \\0\\0}+x_3\colvector{-3\\\ \\1\\0}+x_4\colvector{2\\\ \\0\\1}\\ x_2=0-1x_3+3x_4&&\Rightarrow&& \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4}= \colvector{4\\0\\0\\0}+x_3\colvector{-3\\-1\\1\\0}+x_4\colvector{2\\3\\0\\1} \end{align*}

This final form of a typical solution is especially pleasing and useful. For example, we can build solutions quickly by choosing values for our free variables, and then compute a linear combination. Such as

\begin{align*} x_3=2,\,x_4=-5&&\Rightarrow&& \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4}= \colvector{4\\0\\0\\0}+(2)\colvector{-3\\-1\\1\\0}+(-5)\colvector{2\\3\\0\\1} =\colvector{-12\\-17\\2\\-5}\\ \end{align*}

or

\begin{align*} x_3=1,\,x_4=3&&\Rightarrow&& \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4}= \colvector{4\\0\\0\\0}+(1)\colvector{-3\\-1\\1\\0}+(3)\colvector{2\\3\\0\\1} =\colvector{7\\8\\1\\3}\text{.} \end{align*}

You will find the second solution listed in the write-up for Archetype D, and you might check the first solution by substituting it back into the original equations.

While this form is useful for quickly creating solutions, it is even better because it tells us exactly what every solution looks like. We know the solution set is infinite, which is pretty big, but now we can say that each solution is the fixed vector \(\vect{c}\text{,}\) plus some multiple of \(\vect{u}_1\) plus some multiple of \(\vect{u}_2\text{,}\) where

\begin{align*} \vect{c}&=\colvector{4\\0\\0\\0} & \vect{u}_1&=\colvector{-3\\-1\\1\\0} & \vect{u}_2&=\colvector{2\\3\\0\\1}\text{.} \end{align*}

Period. So it only takes us three vectors to describe the entire infinite solution set, provided we also agree on how to combine the three vectors into a linear combination.

This is such an important and fundamental technique, we will do another example.

Consider a linear system of \(m=5\) equations in \(n=7\) variables, having the augmented matrix \(A\text{.}\)

\begin{equation*} A= \begin{bmatrix} 2 & 1 & -1 & -2 & 2 & 1 & 5 & 21 \\ 1 & 1 & -3 & 1 & 1 & 1 & 2 & -5 \\ 1 & 2 & -8 & 5 & 1 & 1 & -6 & -15 \\ 3 & 3 & -9 & 3 & 6 & 5 & 2 & -24 \\ -2 & -1 & 1 & 2 & 1 & 1 & -9 & -30 \end{bmatrix} \end{equation*}

Row-reducing we obtain the matrix

\begin{equation*} B= \begin{bmatrix} \leading{1} & 0 & 2 & -3 & 0 & 0 & 9 & 15 \\ 0 & \leading{1} & -5 & 4 & 0 & 0 & -8 & -10 \\ 0 & 0 & 0 & 0 & \leading{1} & 0 & -6 & 11 \\ 0 & 0 & 0 & 0 & 0 & \leading{1} & 7 & -21 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{equation*}

and we see \(r=4\) pivot columns. Also, \(D=\set{1,\,2,\,5,\,6}\) so the dependent variables are then \(x_1,\,x_2,\,x_5,\) and \(x_6\text{.}\) \(F=\set{3,\,4,\,7,\,8}\) so the \(n-r=3\) free variables are \(x_3,\,x_4\) and \(x_7\text{.}\) We will express a generic solution for the system by two different methods: both a decomposition and a construction.

First, we will decompose (Proof Technique DC) a solution vector. Rearranging each equation represented in the row-reduced form of the augmented matrix by solving for the dependent variable in each row yields the vector equality,

\begin{align*} \colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}&= \colvector{15-2x_3+3x_4-9x_7\\-10+5x_3-4x_4+8x_7\\x_3\\x_4\\11+6x_7\\-21-7x_7\\x_7}\\ \end{align*}

Now we will use the definitions of column vector addition and scalar multiplication to decompose this generic solution vector as a linear combination.

\begin{align*} &= \colvector{15\\ -10\\ 0\\ 0\\ 11\\ -21\\ 0 } + \colvector{ -2x_3\\ 5x_3\\ x_3\\ 0\\ 0\\ 0\\ 0 } + \colvector{ 3x_4\\ -4x_4\\ 0\\ x_4\\ 0\\ 0\\ 0 } + \colvector{ -9x_7\\ 8x_7\\ 0\\ 0\\ 6x_7\\ -7x_7\\ x_7 } &&\knowl{./knowl/definition-CVA.html}{\text{Definition CVA}}\\ &= \colvector{15\\ -10\\ 0\\ 0\\ 11\\ -21\\ 0 } + x_3\colvector{ -2\\ 5\\ 1\\ 0\\ 0\\ 0\\ 0 } + x_4\colvector{ 3\\ -4\\ 0\\ 1\\ 0\\ 0\\ 0 } + x_7\colvector{ -9\\ 8\\ 0\\ 0\\ 6\\ -7\\ 1 } &&\knowl{./knowl/definition-CVSM.html}{\text{Definition CVSM}} \end{align*}

We will now develop the same linear combination a bit quicker, using three steps. While the method above is instructive, the method below will be our preferred approach.

Step 1. Write the vector of variables as a fixed vector, plus a linear combination of \(n-r\) vectors, using the free variables as the scalars.

\begin{equation*} \vect{x}= \colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{\ \ \\\ \\\ \\\ \\\ \\\ \\\ }+x_3\colvector{\ \ \\\ \\\ \\\ \\\ \\\ \\\ }+x_4\colvector{\ \ \\\ \\\ \\\ \\\ \\\ \\\ }+x_7\colvector{\ \ \\\ \\\ \\\ \\\ \\\ \\\ } \end{equation*}

Step 2. Use 0's and 1's to ensure equality for the entries of the vectors with indices in \(F\) (corresponding to the free variables).

\begin{equation*} \vect{x}= \colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{\\ \\ 0\\ 0\\ \\ \\ 0}+x_3\colvector{\\ \\ 1\\ 0\\ \\ \\ 0}+x_4\colvector{\\ \\ 0\\ 1\\ \\ \\ 0}+x_7\colvector{\\ \\ 0\\ 0\\ \\ \\ 1} \end{equation*}

Step 3. For each dependent variable, use the augmented matrix to formulate an equation expressing the dependent variable as a constant plus multiples of the free variables. Convert this equation into entries of the vectors that ensure equality for each dependent variable, one at a time.

\begin{align*} x_1&=15-2x_3+3x_4-9x_7\ \Rightarrow\\&\vect{x}= \colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{15\\ \\ 0\\ 0\\ \\ \\ 0}+ x_3\colvector{-2\\ \\ 1\\ 0\\ \\ \\ 0}+ x_4\colvector{3\\ \\ 0\\ 1\\ \\ \\ 0}+ x_7\colvector{-9\\ \\ 0\\ 0\\ \\ \\ 1}\\ x_2&=-10+5x_3-4x_4+8x_7\ \Rightarrow\\&\vect{x}= \colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{15\\ -10\\ 0\\ 0\\ \\ \\ 0}+ x_3\colvector{-2\\ 5\\ 1\\ 0\\ \\ \\ 0}+ x_4\colvector{3\\ -4\\ 0\\ 1\\ \\ \\ 0}+ x_7\colvector{-9\\ 8\\ 0\\ 0\\ \\ \\ 1}\\ x_5&=11+6x_7\ \Rightarrow\\&\vect{x}= \colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{15\\ -10\\ 0\\ 0\\ 11\\ \\ 0}+ x_3\colvector{-2\\ 5\\ 1\\ 0\\ 0\\ \\ 0}+ x_4\colvector{3\\ -4\\ 0\\ 1\\ 0\\ \\ 0}+ x_7\colvector{-9\\ 8\\ 0\\ 0\\ 6\\ \\ 1}\\ x_6&=-21-7x_7\ \Rightarrow\\&\vect{x}= \colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{15\\ -10\\ 0\\ 0\\ 11\\ -21\\ 0}+ x_3\colvector{-2\\ 5\\ 1\\ 0\\ 0\\ 0\\ 0}+ x_4\colvector{3\\ -4\\ 0\\ 1\\ 0\\ 0\\ 0}+ x_7\colvector{-9\\ 8\\ 0\\ 0\\ 6\\ -7\\ 1} \end{align*}

This final form of a typical solution is especially pleasing and useful. For example, we can build solutions quickly by choosing values for our free variables, and then compute a linear combination. For example

\begin{align*} x_3&=2,\, x_4=-4,\, x_7=3 \quad\quad\Rightarrow\\ \vect{x}&= \colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{15\\ -10\\ 0\\ 0\\ 11\\ -21\\ 0}+ (2)\colvector{-2\\ 5\\ 1\\ 0\\ 0\\ 0\\ 0}+ (-4)\colvector{3\\ -4\\ 0\\ 1\\ 0\\ 0\\ 0}+ (3)\colvector{-9\\ 8\\ 0\\ 0\\ 6\\ -7\\ 1} = \colvector{-28\\40\\2\\-4\\29\\-42\\3} \end{align*}

or perhaps

\begin{align*} x_3&=5,\, x_4=2,\, x_7=1 \quad\quad\Rightarrow\\ \vect{x}&= \colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{15\\ -10\\ 0\\ 0\\ 11\\ -21\\ 0}+ (5)\colvector{-2\\ 5\\ 1\\ 0\\ 0\\ 0\\ 0}+ (2)\colvector{3\\ -4\\ 0\\ 1\\ 0\\ 0\\ 0}+ (1)\colvector{-9\\ 8\\ 0\\ 0\\ 6\\ -7\\ 1} = \colvector{2\\15\\5\\2\\17\\-28\\1} \end{align*}

or even

\begin{align*} x_3&=0,\, x_4=0,\, x_7=0 \quad\quad\Rightarrow\\ \vect{x}&= \colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{15\\ -10\\ 0\\ 0\\ 11\\ -21\\ 0}+ (0)\colvector{-2\\ 5\\ 1\\ 0\\ 0\\ 0\\ 0}+ (0)\colvector{3\\ -4\\ 0\\ 1\\ 0\\ 0\\ 0}+ (0)\colvector{-9\\ 8\\ 0\\ 0\\ 6\\ -7\\ 1} = \colvector{15\\ -10\\ 0\\ 0\\ 11\\ -21\\ 0}\text{.} \end{align*}

So we can compactly express all of the solutions to this linear system with just 4 fixed vectors, provided we agree how to combine them in a linear combinations to create solution vectors.

Suppose you were told that the vector \(\vect{w}\) below was a solution to this system of equations. Could you turn the problem around and write \(\vect{w}\) as a linear combination of the four vectors \(\vect{c}\text{,}\) \(\vect{u}_1\text{,}\) \(\vect{u}_2\text{,}\) \(\vect{u}_3\text{?}\) (See Exercise LC.M11.)

\begin{align*} \vect{w}&=\colvector{100\\-75\\7\\9\\-37\\35\\-8} & \vect{c}&=\colvector{15\\ -10\\ 0\\ 0\\ 11\\ -21\\ 0} & \vect{u}_1&=\colvector{-2\\ 5\\ 1\\ 0\\ 0\\ 0\\ 0} & \vect{u}_2&=\colvector{3\\ -4\\ 0\\ 1\\ 0\\ 0\\ 0} & \vect{u}_3&=\colvector{-9\\ 8\\ 0\\ 0\\ 6\\ -7\\ 1} \end{align*}

Did you think a few weeks ago that you could so quickly and easily list all the solutions to a linear system of 5 equations in 7 variables?

We will now formalize the last two (important) examples as a theorem. The statement of this theorem is a bit scary, and the proof is scarier. For now, be sure to convice yourself, by working through the examples and exercises, that the statement just describes the procedure of the two immediately previous examples.

Notice that it is possible that \(n=r\text{,}\) in which case we get the unique solution \(\vect{c}\text{.}\)

First, \(\linearsystem{A}{\vect{b}}\) is equivalent to the linear system of equations that has the matrix \(B\) as its augmented matrix (Theorem REMES), so we need only show that \(S\) is the solution set for the system with \(B\) as its augmented matrix. The conclusion of this theorem is that the solution set is equal to the set \(S\text{,}\) so we will apply Definition SE.

We begin by showing that every element of \(S\) is indeed a solution to the system. Let \(\alpha_1,\,\alpha_2,\,\alpha_3,\,\ldots,\,\alpha_{n-r}\) be one choice of the scalars used to describe elements of \(S\text{.}\) So an arbitrary element of \(S\text{,}\) which we will consider as a proposed solution is

\begin{equation*} \vect{x}= \vect{c}+\alpha_1\vect{u}_1+\alpha_2\vect{u}_2+\alpha_3\vect{u}_3+\cdots+\alpha_{n-r}\vect{u}_{n-r}\text{.} \end{equation*}

When \(r+1\leq\ell\leq m\text{,}\) row \(\ell\) of the matrix \(B\) is a zero row, so the equation represented by that row is always true, no matter which solution vector we propose. So concentrate on rows representing equations \(1\leq\ell\leq r\text{.}\) We evaluate equation \(\ell\) of the system represented by \(B\) with the proposed solution vector \(\vect{x}\) and refer to the value of the left-hand side of the equation as \(\beta_\ell\)

\begin{equation*} \beta_\ell= \matrixentry{B}{\ell 1}\vectorentry{\vect{x}}{1}+ \matrixentry{B}{\ell 2}\vectorentry{\vect{x}}{2}+ \matrixentry{B}{\ell 3}\vectorentry{\vect{x}}{3}+ \cdots+ \matrixentry{B}{\ell n}\vectorentry{\vect{x}}{n}\text{.} \end{equation*}

Since \(\matrixentry{B}{\ell d_{i}}=0\) for all \(1\leq i\leq r\text{,}\) except that \(\matrixentry{B}{\ell d_{\ell}}=1\text{,}\) we see that \(\beta_\ell\) simplifies to

\begin{equation*} \beta_\ell= \vectorentry{\vect{x}}{d_{\ell}}+ \matrixentry{B}{\ell f_1}\vectorentry{\vect{x}}{f_1}+ \matrixentry{B}{\ell f_2}\vectorentry{\vect{x}}{f_2}+ \matrixentry{B}{\ell f_3}\vectorentry{\vect{x}}{f_3}+ \cdots+ \matrixentry{B}{\ell f_{n-r}}\vectorentry{\vect{x}}{f_{n-r}}\text{.} \end{equation*}

Notice that for \(1\leq i\leq n-r\)

\begin{align*} \vectorentry{\vect{x}}{f_i} &= \vectorentry{\vect{c}}{f_i}+ \alpha_1\vectorentry{\vect{u}_1}{f_i}+ \alpha_2\vectorentry{\vect{u}_2}{f_i}+ \cdots+ \alpha_i\vectorentry{\vect{u}_i}{f_i}+ \cdots+ \alpha_{n-r}\vectorentry{\vect{u_{n-r}}}{f_i}\\ &= 0+ \alpha_1(0)+ \alpha_2(0)+ \cdots+ \alpha_i(1)+ \cdots+ \alpha_{n-r}(0)\\ &=\alpha_i\text{.} \end{align*}

So \(\beta_\ell\) simplifies further, and we expand the first term

\begin{align*} \beta_\ell &= \vectorentry{\vect{x}}{d_{\ell}}+ \matrixentry{B}{\ell f_1}\alpha_1+ \matrixentry{B}{\ell f_2}\alpha_2+ \matrixentry{B}{\ell f_3}\alpha_3+ \cdots+ \matrixentry{B}{\ell f_{n-r}}\alpha_{n-r}\\ &= \vectorentry{ \vect{c}+ \alpha_1\vect{u}_1+ \alpha_2\vect{u}_2+ \alpha_3\vect{u}_3+ \cdots+ \alpha_{n-r}\vect{u}_{n-r} }{d_{\ell}} +\\ &\quad\quad \matrixentry{B}{\ell f_1}\alpha_1+ \matrixentry{B}{\ell f_2}\alpha_2+ \matrixentry{B}{\ell f_3}\alpha_3+ \cdots+ \matrixentry{B}{\ell f_{n-r}}\alpha_{n-r}\\ &= \vectorentry{\vect{c}}{d_{\ell}}+ \alpha_1\vectorentry{\vect{u}_1}{d_{\ell}}+ \alpha_2\vectorentry{\vect{u}_2}{d_{\ell}}+ \alpha_3\vectorentry{\vect{u}_3}{d_{\ell}}+ \cdots+ \alpha_{n-r}\vectorentry{\vect{u_{n-r}}}{d_{\ell}} +\\ &\quad\quad \matrixentry{B}{\ell f_1}\alpha_1+ \matrixentry{B}{\ell f_2}\alpha_2+ \matrixentry{B}{\ell f_3}\alpha_3+ \cdots+ \matrixentry{B}{\ell f_{n-r}}\alpha_{n-r}\\ &= \matrixentry{B}{\ell,{n+1}}+\\ &\quad\quad \alpha_1(-\matrixentry{B}{\ell f_1})+ \alpha_2(-\matrixentry{B}{\ell f_2})+ \alpha_3(-\matrixentry{B}{\ell f_3})+ \cdots+ \alpha_{n-r}(-\matrixentry{B}{\ell f_{n-r}}) +\\ &\quad\quad \matrixentry{B}{\ell f_1}\alpha_1+ \matrixentry{B}{\ell f_2}\alpha_2+ \matrixentry{B}{\ell f_3}\alpha_3+ \cdots+ \matrixentry{B}{\ell f_{n-r}}\alpha_{n-r}\\ &= \matrixentry{B}{\ell,{n+1}}\text{.} \end{align*}

So \(\beta_\ell\) began as the left-hand side of equation \(\ell\) of the system represented by \(B\) and we now know it equals \(\matrixentry{B}{\ell,{n+1}}\text{,}\) the constant term for equation \(\ell\) of this system. So the arbitrarily chosen vector from \(S\) makes every equation of the system true, and therefore is a solution to the system. So all the elements of \(S\) are solutions to the system.

For the second half of the proof, assume that \(\vect{x}\) is a solution vector for the system having \(B\) as its augmented matrix. For convenience and clarity, denote the entries of \(\vect{x}\) by \(x_i\text{,}\) in other words, \(x_i=\vectorentry{\vect{x}}{i}\text{.}\) We desire to show that this solution vector is also an element of the set \(S\text{.}\) Begin with the observation that a solution vector's entries makes equation \(\ell\) of the system true for all \(1\leq\ell\leq m\text{,}\)

\begin{equation*} \matrixentry{B}{\ell,1}x_1+ \matrixentry{B}{\ell,2}x_2+ \matrixentry{B}{\ell,3}x_3+ \cdots+ \matrixentry{B}{\ell,n}x_n= \matrixentry{B}{\ell,n+1}\text{.} \end{equation*}

When \(\ell\leq r\text{,}\) the pivot columns of \(B\) have zero entries in row \(\ell\) with the exception of column \(d_\ell\text{,}\) which will contain a \(1\text{.}\) So for \(1\leq\ell\leq r\text{,}\) equation \(\ell\) simplifies to

\begin{equation*} 1x_{d_\ell}+ \matrixentry{B}{\ell,f_1}x_{f_1}+ \matrixentry{B}{\ell,f_2}x_{f_2}+ \matrixentry{B}{\ell,f_3}x_{f_3}+ \cdots+ \matrixentry{B}{\ell,f_{n-r}}x_{f_{n-r}}= \matrixentry{B}{\ell,n+1}\text{.} \end{equation*}

This allows us to write,

\begin{align*} \vectorentry{\vect{x}}{d_\ell} &= x_{d_\ell}\\ &= \matrixentry{B}{\ell,n+1} -\matrixentry{B}{\ell,f_1}x_{f_1} -\matrixentry{B}{\ell,f_2}x_{f_2} -\matrixentry{B}{\ell,f_3}x_{f_3} -\cdots -\matrixentry{B}{\ell,f_{n-r}}x_{f_{n-r}}\\ &= \vectorentry{\vect{c}}{d_\ell} +x_{f_1}\vectorentry{\vect{u}_1}{d_\ell} +x_{f_2}\vectorentry{\vect{u}_2}{d_\ell} +x_{f_3}\vectorentry{\vect{u}_3}{d_\ell} +\cdots +x_{f_{n-r}}\vectorentry{\vect{u}_{n-r}}{d_\ell}\\ &= \vectorentry{ \vect{c} +x_{f_1}\vect{u}_1 +x_{f_2}\vect{u}_2 +x_{f_3}\vect{u}_3 +\cdots +x_{f_{n-r}}\vect{u}_{n-r} }{d_\ell}\text{.} \end{align*}

This tells us that the entries of the solution vector \(\vect{x}\) corresponding to dependent variables (indices in \(D\)), are equal to those of a vector in the set \(S\text{.}\) We still need to check the other entries of the solution vector \(\vect{x}\) corresponding to the free variables (indices in \(F\)) to see if they are equal to the entries of the same vector in the set \(S\text{.}\) To this end, suppose \(i\in F\) and \(i=f_j\text{.}\) Then

\begin{align*} \vectorentry{\vect{x}}{i} &=x_{i}=x_{f_j}\\ &= 0+ 0x_{f_1}+ 0x_{f_2}+ 0x_{f_3}+ \cdots+ 0x_{f_{j-1}}+ 1x_{f_j}+ 0x_{f_{j+1}}+ \cdots+ 0x_{f_{n-r}}\\ &= \vectorentry{\vect{c}}{i}+ x_{f_1}\vectorentry{\vect{u}_1}{i}+ x_{f_2}\vectorentry{\vect{u}_2}{i}+ x_{f_3}\vectorentry{\vect{u}_3}{i}+ \cdots+ x_{f_j}\vectorentry{\vect{u}_j}{i}+ \cdots+ x_{f_{n-r}}\vectorentry{\vect{u}_{n-r}}{i}\\ &=\vectorentry{ \vect{c} +x_{f_1}\vect{u}_1 +x_{f_2}\vect{u}_2 +\cdots +x_{f_{n-r}}\vect{u}_{n-r} }{i}\text{.} \end{align*}

So entries of \(\vect{x}\) and \(\vect{c} +x_{f_1}\vect{u}_1 +x_{f_2}\vect{u}_2 +\cdots +x_{f_{n-r}}\vect{u}_{n-r}\) are equal and therefore by Definition CVE they are equal vectors. Since \(x_{f_1},\,x_{f_2},\,x_{f_3},\,\ldots,\,x_{f_{n-r}}\) are scalars, this shows us that \(\vect{x}\) qualifies for membership in \(S\text{.}\) So the set \(S\) contains all of the solutions to the system.

Note that both halves of the proof of Theorem VFSLS indicate that \(\alpha_i=\vectorentry{\vect{x}}{f_i}\text{.}\) In other words, the arbitrary scalars, \(\alpha_i\text{,}\) in the description of the set \(S\) actually have more meaning — they are the values of the free variables \(\vectorentry{\vect{x}}{f_i}\text{,}\) \(1\leq i\leq n-r\text{.}\) So we will often exploit this observation in our descriptions of solution sets.

Theorem VFSLS formalizes what happened in the three steps of Example VFSAD. The theorem will be useful in proving other theorems, and it it is useful since it tells us an exact procedure for simply describing an infinite solution set. We could program a computer to implement it, once we have the augmented matrix row-reduced and have checked that the system is consistent. By Knuth's definition, this completes our conversion of linear equation solving from art into science. Notice that it even applies (but is overkill) in the case of a unique solution. However, as a practical matter, I prefer the three-step process of Example VFSAD when I need to describe an infinite solution set. So let us practice some more, but with a bigger example.

Archetype I is a linear system of \(m=4\) equations in \(n=7\) variables. Row-reducing the augmented matrix yields

\begin{equation*} \begin{bmatrix} \leading{1} & 4 & 0 & 0 & 2 & 1 & -3 & 4 \\ 0 & 0 & \leading{1} & 0 & 1 & -3 & 5 & 2 \\ 0 & 0 & 0 & \leading{1} & 2 & -6 & 6 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{equation*}

and we see \(r=3\) pivot columns, with indices \(D=\{1,\,3,\,4\}\text{.}\) So the \(r=3\) dependent variables are \(x_1,\,x_3,\,x_4\text{.}\) The non-pivot columns have indices in \(F=\{2,\,5,\,6,\,7,\,8\}\text{,}\) so the \(n-r=4\) free variables are \(x_2,\,x_5,\,x_6,\,x_7\text{.}\)

Step 1. Write the vector of variables (\(\vect{x}\)) as a fixed vector (\(\vect{c}\)), plus a linear combination of \(n-r=4\) vectors (\(\vect{u}_1,\,\vect{u}_2,\,\vect{u}_3,\,\vect{u}_4\)), using the free variables as the scalars.

\begin{equation*} \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{\ \ \\\ \\\ \\\ \\\ \\\ \\\ }+ x_2\colvector{\ \ \\\ \\\ \\\ \\\ \\\ \\\ }+ x_5\colvector{\ \ \\\ \\\ \\\ \\\ \\\ \\\ }+ x_6\colvector{\ \ \\\ \\\ \\\ \\\ \\\ \\\ }+ x_7\colvector{\ \ \\\ \\\ \\\ \\\ \\\ \\\ } \end{equation*}

Step 2. For each free variable, use 0's and 1's to ensure equality for the corresponding entry of the vectors. Take note of the pattern of 0's and 1's at this stage, because this is the best look you will have at it. We will state an important theorem in the next section and the proof will essentially rely on this observation.

\begin{equation*} \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{\ \\0\\\ \\\ \\0\\0\\0}+ x_2\colvector{\ \\1\\\ \\\ \\0\\0\\0}+ x_5\colvector{\ \\0\\\ \\\ \\1\\0\\0}+ x_6\colvector{\ \\0\\\ \\\ \\0\\1\\0}+ x_7\colvector{\ \\0\\\ \\\ \\0\\0\\1} \end{equation*}

Step 3. For each dependent variable, use the augmented matrix to formulate an equation expressing the dependent variable as a constant plus multiples of the free variables. Convert this equation into entries of the vectors that ensure equality for each dependent variable, one at a time.

\begin{align*} x_1&=4-4x_2-2x_5-1x_6+3x_7\quad\Rightarrow\\ \vect{x}&=\colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{4\\0\\\ \\\ \\0\\0\\0}+ x_2\colvector{-4\\1\\\ \\\ \\0\\0\\0}+ x_5\colvector{-2\\0\\\ \\\ \\1\\0\\0}+ x_6\colvector{-1\\0\\\ \\\ \\0\\1\\0}+ x_7\colvector{3\\0\\\ \\\ \\0\\0\\1}\\[12pt] x_3&=2+0x_2-x_5+3x_6-5x_7\quad\Rightarrow\\ \vect{x}&=\colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{4\\0\\2\\\ \\0\\0\\0}+ x_2\colvector{-4\\1\\0\\\ \\0\\0\\0}+ x_5\colvector{-2\\0\\-1\\\ \\1\\0\\0}+ x_6\colvector{-1\\0\\3\\\ \\0\\1\\0}+ x_7\colvector{3\\0\\-5\\\ \\0\\0\\1}\\[12pt] x_4&=1+0x_2-2x_5+6x_6-6x_7\quad\Rightarrow\\ \vect{x}&=\colvector{x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7}= \colvector{4\\0\\2\\1\\0\\0\\0}+ x_2\colvector{-4\\1\\0\\0\\0\\0\\0}+ x_5\colvector{-2\\0\\-1\\-2\\1\\0\\0}+ x_6\colvector{-1\\0\\3\\6\\0\\1\\0}+ x_7\colvector{3\\0\\-5\\-6\\0\\0\\1}\text{.} \end{align*}

We can now use this final expression to quickly build solutions to the system. You might try to recreate each of the solutions listed in the write-up for Archetype I. (Hint: look at the values of the free variables in each solution, and notice that the vector \(\vect{c}\) has 0's in these locations.)

Even better, we have a description of the infinite solution set, based on just 5 vectors, which we combine in linear combinations to produce solutions.

Whenever we discuss Archetype I you know that is your cue to go work through Archetype J by yourself. Remember to take note of the 0/1 pattern at the conclusion of Step 2. Have fun — we won't go anywhere while you're away.

This technique is so important, that we will do one more example. However, an important distinction will be that this system is homogeneous.

Archetype L is presented simply as the \(5\times 5\) matrix

\begin{equation*} L=\begin{bmatrix} -2 & -1 & -2 & -4 & 4 \\ -6 & -5 & -4 & -4 & 6 \\ 10 & 7 & 7 & 10 & -13 \\ -7 & -5 & -6 & -9 & 10 \\ -4 & -3 & -4 & -6 & 6 \\ \end{bmatrix}\text{.} \end{equation*}

We will employ this matrix here as the coefficient matrix of a homogeneous system and reference this matrix as \(L\text{.}\) So we are solving the homogeneous system \(\linearsystem{L}{\zerovector}\) having \(m=5\) equations in \(n=5\) variables. If we built the augmented matrix, we would add a sixth column to \(L\) containing all zeros. As we did row operations, this sixth column would remain all zeros. So instead we will row-reduce the coefficient matrix, and mentally remember the missing sixth column of zeros. This row-reduced matrix is

\begin{equation*} \begin{bmatrix} \leading{1} & 0 & 0 & 1 & -2 \\ 0 & \leading{1} & 0 & -2 & 2 \\ 0 & 0 & \leading{1} & 2 & -1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{equation*}

and we see \(r=3\) pivot columns, with indices \(D=\{1,\,2,\,3\}\text{.}\) So the \(r=3\) dependent variables are \(x_1,\,x_2,\,x_3\text{.}\) The non-pivot columns have indices \(F=\{4,\,5\}\text{,}\) so the \(n-r=2\) free variables are \(x_4,\,x_5\text{.}\) Notice that if we had included the all-zero vector of constants to form the augmented matrix for the system, then the index 6 would have appeared in the set \(F\text{,}\) and subsequently would have been ignored when listing the free variables. So nothing is lost by not creating an augmented matrix (in the case of a homogeneous system). And maybe it is an improvement, since now every index in \(F\) can be used to reference a variable of the linear system.

Step 1. Write the vector of variables (\(\vect{x}\)) as a fixed vector (\(\vect{c}\)), plus a linear combination of \(n-r=2\) vectors (\(\vect{u}_1,\,\vect{u}_2\)), using the free variables as the scalars.

\begin{equation*} \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4\\x_5}= \colvector{\ \ \\\ \ \\\ \\\ \\\ }+ x_4\colvector{\ \ \\\ \\\ \\\ \\\ }+ x_5\colvector{\ \ \\\ \\\ \\\ \\\ } \end{equation*}

Step 2. For each free variable, use 0's and 1's to ensure equality for the corresponding entry of the vectors. Take note of the pattern of 0's and 1's at this stage, even if it is not as illuminating as in other examples.

\begin{equation*} \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4\\x_5}= \colvector{\ \\\ \\\ \\0\\0}+ x_4\colvector{\ \\\ \\\ \\1\\0}+ x_5\colvector{\ \\\ \\\ \\0\\1} \end{equation*}

Step 3. For each dependent variable, use the augmented matrix to formulate an equation expressing the dependent variable as a constant plus multiples of the free variables. Do not forget about the “missing” sixth column being full of zeros. Convert this equation into entries of the vectors that ensure equality for each dependent variable, one at a time.

\begin{align*} x_1&=0-1x_4+2x_5&&\Rightarrow&& \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4\\x_5}= \colvector{0\\\ \\\ \\0\\0}+ x_4\colvector{-1\\\ \\\ \\1\\0}+ x_5\colvector{2\\\ \\\ \\0\\1}\\ x_2&=0+2x_4-2x_5&&\Rightarrow&& \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4\\x_5}= \colvector{0\\0\\\ \\0\\0}+ x_4\colvector{-1\\2\\\ \\1\\0}+ x_5\colvector{2\\-2\\\ \\0\\1}\\ x_3&=0-2x_4+1x_5&&\Rightarrow&& \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4\\x_5}= \colvector{0\\0\\0\\0\\0}+ x_4\colvector{-1\\2\\-2\\1\\0}+ x_5\colvector{2\\-2\\1\\0\\1} \end{align*}

The vector \(\vect{c}\) will always have 0's in the entries corresponding to free variables. However, since we are solving a homogeneous system, the row-reduced augmented matrix has zeros in column \(n+1=6\text{,}\) and hence all the entries of \(\vect{c}\) are zero. So we can write

\begin{equation*} \vect{x}=\colvector{x_1\\x_2\\x_3\\x_4\\x_5}= \zerovector+ x_4\colvector{-1\\2\\-2\\1\\0}+ x_5\colvector{2\\-2\\1\\0\\1} = x_4\colvector{-1\\2\\-2\\1\\0}+ x_5\colvector{2\\-2\\1\\0\\1} \end{equation*}

It will always happen that the solutions to a homogeneous system has \(\vect{c}=\zerovector\) (even in the case of a unique solution?). So our expression for the solutions is a bit more pleasing. In this example it says that the solutions are all possible linear combinations of the two vectors \(\vect{u}_1\) and \(\vect{u}_2\text{,}\) with no mention of any fixed vector entering into the linear combination.

\begin{align*} \vect{u}_1&=\colvector{-1\\2\\-2\\1\\0} & \vect{u}_2&=\colvector{2\\-2\\1\\0\\1} \end{align*}

This observation will motivate our next section and the main definition of that section, and after that we will conclude the section by formalizing this situation.

We can now resolve a bit of the mystery around Sage's .solve_right() method. Recall from Sage SS1 that if a linear system has solutions, Sage only provides one solution, even in the case when there are infinitely many solutions. In our previous discussion, we used the system from Example ISSI.

The vector \(\vect{c}\) described in the statement of Theorem VFSLS is precisely the solution returned from Sage's .solve_right() method. This is the solution where we choose the \(\alpha_i\text{,}\) \(1\leq i\leq n-r\) to all be zero, in other words, each free variable is set to zero (how convenient!). Free variables correspond to columns of the row-reduced augmented matrix that are not pivot columns. So we can profitably employ the .nonpivots() matrix method. Let us put this all together.

Since the eighth column (numbered 7) of the reduced row-echelon form is not a pivot column, we know by Theorem RCLS that the system is consistent. We can use the indices of the remaining non-pivot columns to place zeros into the vector \(\vect{c}\) in those locations. The remaining entries of \(\vect{c}\) are the entries of the reduced row-echelon form in the last column, inserted in that order. Boom!

So we have three ways to get to the same solution: (a) row-reduce the augmented matrix and set the free variables all to zero, (b) row-reduce the augmented matrix and use the formula from Theorem VFSLS to construct \(\vect{c}\text{,}\) and (c) use Sage's .solve_right() method.

One mystery left to resolve. How can we get Sage to give us infinitely many solutions in the case of systems with an infinite solution set? This is best handled in the next section, Section SS, specifically in Sage SS3.

Subsection PSHS Particular Solutions, Homogeneous Solutions

The next theorem tells us that in order to find all of the solutions to a linear system of equations, it is sufficient to find just one solution, and then find all of the solutions to the homogeneous system with the same coefficient matrix. This explains part of our interest in the null space, the set of all solutions to a homogeneous system.

Let \(\vectorlist{A}{n}\) be the columns of the coefficient matrix \(A\text{.}\)

(⇐) 

Suppose \(\vect{y}=\vect{w}+\vect{z}\) and \(\vect{z}\in\nsp{A}\text{.}\) Then

\begin{align*} \vect{b} &= \vectorentry{\vect{w}}{1}\vect{A}_1+ \vectorentry{\vect{w}}{2}\vect{A}_2+ \vectorentry{\vect{w}}{3}\vect{A}_3+ \cdots+ \vectorentry{\vect{w}}{n}\vect{A}_n &&\knowl{./knowl/theorem-SLSLC.html}{\text{Theorem SLSLC}}\\ &= \vectorentry{\vect{w}}{1}\vect{A}_1+ \vectorentry{\vect{w}}{2}\vect{A}_2+ \vectorentry{\vect{w}}{3}\vect{A}_3+ \cdots+ \vectorentry{\vect{w}}{n}\vect{A}_n +\zerovector &&\knowl{./knowl/property-ZC.html}{\text{Property ZC}}\\ &= \vectorentry{\vect{w}}{1}\vect{A}_1+ \vectorentry{\vect{w}}{2}\vect{A}_2+ \vectorentry{\vect{w}}{3}\vect{A}_3+ \cdots+ \vectorentry{\vect{w}}{n}\vect{A}_n &&\knowl{./knowl/theorem-SLSLC.html}{\text{Theorem SLSLC}}\\ &\quad\quad + \vectorentry{\vect{z}}{1}\vect{A}_1+ \vectorentry{\vect{z}}{2}\vect{A}_2+ \vectorentry{\vect{z}}{3}\vect{A}_3+ \cdots+ \vectorentry{\vect{z}}{n}\vect{A}_n\\ &= \left(\vectorentry{\vect{w}}{1}+\vectorentry{\vect{z}}{1}\right)\vect{A}_1+ \left(\vectorentry{\vect{w}}{2}+\vectorentry{\vect{z}}{2}\right)\vect{A}_2+ &&\knowl{./knowl/theorem-VSPCV.html}{\text{Theorem VSPCV}}\\ &\quad\quad \left(\vectorentry{\vect{w}}{3}+\vectorentry{\vect{z}}{3}\right)\vect{A}_3+ \cdots+ \left(\vectorentry{\vect{w}}{n}+\vectorentry{\vect{z}}{n}\right)\vect{A}_n\\ &= \vectorentry{\vect{w}+\vect{z}}{1}\vect{A}_1+ \vectorentry{\vect{w}+\vect{z}}{2}\vect{A}_2+ \cdots+ \vectorentry{\vect{w}+\vect{z}}{n}\vect{A}_n &&\knowl{./knowl/definition-CVA.html}{\text{Definition CVA}}\\ &= \vectorentry{\vect{y}}{1}\vect{A}_1+ \vectorentry{\vect{y}}{2}\vect{A}_2+ \vectorentry{\vect{y}}{3}\vect{A}_3+ \cdots+ \vectorentry{\vect{y}}{n}\vect{A}_n &&\text{Definition of }\vect{y}\text{.} \end{align*}

Applying Theorem SLSLC we see that the vector \(\vect{y}\) is a solution to \(\linearsystem{A}{\vect{b}}\text{.}\)

(⇒) 

Suppose \(\vect{y}\) is a solution to \(\linearsystem{A}{\vect{b}}\text{.}\) Then

\begin{align*} \zerovector &= \vect{b}-\vect{b}&&\text{}\\ &= \vectorentry{\vect{y}}{1}\vect{A}_1+ \vectorentry{\vect{y}}{2}\vect{A}_2+ \vectorentry{\vect{y}}{3}\vect{A}_3+ \cdots+ \vectorentry{\vect{y}}{n}\vect{A}_n &&\knowl{./knowl/theorem-SLSLC.html}{\text{Theorem SLSLC}}\\ &\quad\quad - \left( \vectorentry{\vect{w}}{1}\vect{A}_1+ \vectorentry{\vect{w}}{2}\vect{A}_2+ \vectorentry{\vect{w}}{3}\vect{A}_3+ \cdots+ \vectorentry{\vect{w}}{n}\vect{A}_n \right)\\ &= \left(\vectorentry{\vect{y}}{1}-\vectorentry{\vect{w}}{1}\right)\vect{A}_1+ \left(\vectorentry{\vect{y}}{2}-\vectorentry{\vect{w}}{2}\right)\vect{A}_2 &&\knowl{./knowl/theorem-VSPCV.html}{\text{Theorem VSPCV}}\\ &\quad\quad + \left(\vectorentry{\vect{y}}{3}-\vectorentry{\vect{w}}{3}\right)\vect{A}_3+ \cdots+ \left(\vectorentry{\vect{y}}{n}-\vectorentry{\vect{w}}{n}\right)\vect{A}_n\\ &= \vectorentry{\vect{y}-\vect{w}}{1}\vect{A}_1+ \vectorentry{\vect{y}-\vect{w}}{2}\vect{A}_2 &&\knowl{./knowl/definition-CVA.html}{\text{Definition CVA}}\\ &\quad\quad +\vectorentry{\vect{y}-\vect{w}}{3}\vect{A}_3+ \cdots+ \vectorentry{\vect{y}-\vect{w}}{n}\vect{A}_n\text{.} \end{align*}

By Theorem SLSLC we see that the vector \(\vect{y}-\vect{w}\) is a solution to the homogeneous system \(\homosystem{A}\) and by Definition NSM, \(\vect{y}-\vect{w}\in\nsp{A}\text{.}\) In other words, \(\vect{y}-\vect{w}=\vect{z}\) for some vector \(\vect{z}\in\nsp{A}\text{.}\) Rewritten, this is \(\vect{y}=\vect{w}+\vect{z}\text{,}\) as desired.

After proving Theorem NMUS we commented (insufficiently) on the negation of one half of the theorem. Nonsingular coefficient matrices lead to unique solutions for every choice of the vector of constants. What does this say about singular matrices? A singular matrix \(A\) has a nontrivial null space (Theorem NMTNS). For a given vector of constants, \(\vect{b}\text{,}\) the system \(\linearsystem{A}{\vect{b}}\) could be inconsistent, meaning there are no solutions. But if there is at least one solution (\(\vect{w}\)), then Theorem PSPHS tells us there will be infinitely many solutions because of the role of the infinite null space for a singular matrix. So a system of equations with a singular coefficient matrix never has a unique solution. Notice that this is the contrapositive of the statement in Exercise NM.T31. With a singular coefficient matrix, either there are no solutions, or infinitely many solutions, depending on the choice of the vector of constants (\(\vect{b}\)).

Archetype D is a consistent system of equations with a nontrivial null space. Let \(A\) denote the coefficient matrix of this system. The write-up for this system begins with three solutions.

\begin{align*} \vect{y}_1=\colvector{0\\1\\2\\1}&& \vect{y}_2=\colvector{4\\0\\0\\0}&& \vect{y}_3=\colvector{7\\8\\1\\3} \end{align*}

We will choose to have \(\vect{y}_1\) play the role of \(\vect{w}\) in the statement of Theorem PSPHS, though understand that any one of the three vectors listed here (or others) could have been chosen. To illustrate the theorem, we should be able to write each of these three solutions as the vector \(\vect{w}\) plus a solution to the corresponding homogeneous system of equations. Since \(\zerovector\) is always a solution to a homogeneous system we can easily write

\begin{equation*} \vect{y}_1=\vect{w}=\vect{w}+\zerovector\text{.} \end{equation*}

The vectors \(\vect{y}_2\) and \(\vect{y}_3\) will require a bit more effort. Solutions to the homogeneous system \(\homosystem{A}\) are exactly the elements of the null space of the coefficient matrix, which by an application of Theorem VFSLS is

\begin{equation*} \nsp{A}=\setparts{ x_3\colvector{-3\\-1\\1\\0}+x_4\colvector{2\\3\\0\\1} }{ x_3,\,x_4\in\complexes }\text{.} \end{equation*}

Then

\begin{equation*} \vect{y}_2=\colvector{4\\0\\0\\0} =\colvector{0\\1\\2\\1}+\colvector{4\\-1\\-2\\-1} =\colvector{0\\1\\2\\1}+\left((-2)\colvector{-3\\-1\\1\\0}+(-1)\colvector{2\\3\\0\\1}\right) =\vect{w}+\vect{z}_2 \end{equation*}

where

\begin{equation*} \vect{z}_2 =\colvector{4\\-1\\-2\\-1} =(-2)\colvector{-3\\-1\\1\\0}+(-1)\colvector{2\\3\\0\\1} \end{equation*}

is obviously a solution of the homogeneous system since it is written as a linear combination of the vectors describing the null space of the coefficient matrix (or as a check, you could just evaluate the equations in the homogeneous system with \(\vect{z}_2\)).

Again

\begin{equation*} \vect{y}_3=\colvector{7\\8\\1\\3} =\colvector{0\\1\\2\\1}+\colvector{7\\7\\-1\\2} =\colvector{0\\1\\2\\1}+\left((-1)\colvector{-3\\-1\\1\\0}+2\colvector{2\\3\\0\\1}\right) =\vect{w}+\vect{z}_3 \end{equation*}

where

\begin{equation*} \vect{z}_3=\colvector{7\\7\\-1\\2}= (-1)\colvector{-3\\-1\\1\\0}+2\colvector{2\\3\\0\\1} \end{equation*}

is obviously a solution of the homogeneous system since it is written as a linear combination of the vectors describing the null space of the coefficient matrix (or as a check, you could just evaluate the equations in the homogeneous system with \(\vect{z}_2\)).

Here is another view of this theorem, in the context of this example. Grab two new solutions of the original system of equations, say

\begin{align*} \vect{y}_4=\colvector{11\\0\\-3\\-1}&& \vect{y}_5=\colvector{-4\\2\\4\\2} \end{align*}

and form their difference,

\begin{equation*} \vect{u}=\colvector{11\\0\\-3\\-1}-\colvector{-4\\2\\4\\2}=\colvector{15\\-2\\-7\\-3}\text{.} \end{equation*}

It is no accident that \(\vect{u}\) is a solution to the homogeneous system (check this!). In other words, the difference between any two solutions to a linear system of equations is an element of the null space of the coefficient matrix. This is an equivalent way to state Theorem PSPHS. (See Exercise MM.T50).

The ideas of this subsection will appear again in Chapter LT when we discuss preimages of linear transformations (Definition PI).

Again, Sage is useful for illustrating a theorem, in this case Theorem PSPHS. We will illustrate both “directions” of this equivalence with the system from Example ISSI.

First we will build solutions to this system. Theorem PSPHS says we need a particular solution, i.e. one solution to the system, \(\vect{w}\text{.}\) We can get this from Sage's .solve_right() matrix method. Then for any vector \(\vect{z}\) from the null space of the coefficient matrix, the new vector \(\vect{y}=\vect{w}+\vect{z}\) should be a solution. We walk through this construction in the next few cells, where we have employed a specific element of the null space, z, along with a check that it is really in the null space.

You can create solutions repeatedly via the creation of random elements of the null space. Be sure you have executed the cells above, so that coeff, n, const, nsp and w are all defined. Try executing the cell below repeatedly to test infinitely many solutions to the system. You can use the subsequent compute cell to peek at any of the solutions you create.

For the other direction, we present (and verify) two solutions to the linear system of equations. The condition that \(\vect{y}=\vect{w}+\vect{z}\) can be rewritten as \(\vect{y}-\vect{w}=\vect{z}\text{,}\) where \(\vect{z}\) is in the null space of the coefficient matrix. Which of our two solutions is the “particular” solution and which is “some other” solution? It does not matter, it is all semantics at this point. What is important is that their difference is an element of the null space (in either order). So we define the solutions, along with checks that they are really solutions, then examine their difference.

Reading Questions LC Reading Questions

1.

Earlier, a reading question asked you to solve the system of equations

\begin{align*} 2x_1 + 3x_2 - x_3&= 0\\ x_1 + 2x_2 + x_3&= 3\\ x_1 + 3x_2 + 3x_3&= 7\text{.} \end{align*}

Use a linear combination to rewrite this system of equations as a vector equality.

2.

Find a linear combination of the vectors

\begin{equation*} S=\set{\colvector{1\\3\\-1},\,\colvector{2\\0\\4},\,\colvector{-1\\3\\-5}} \end{equation*}

that equals the vector \(\colvector{1\\-9\\11}\text{.}\)

3.

The matrix below is the augmented matrix of a system of equations, row-reduced to reduced row-echelon form. Write the vector form of the solutions to the system.

\begin{equation*} \begin{bmatrix} \leading{1}&3&0&6&0&9\\ 0&0&\leading{1}&-2&0&-8\\ 0&0&0&0&\leading{1}&3 \end{bmatrix} \end{equation*}

Exercises LC Exercises

C21.

Consider each archetype that is a system of equations. For individual solutions listed (both for the original system and the corresponding homogeneous system) express the vector of constants as a linear combination of the columns of the coefficient matrix, as guaranteed by Theorem SLSLC. Verify this equality by computing the linear combination. For systems with no solutions, recognize that it is then impossible to write the vector of constants as a linear combination of the columns of the coefficient matrix. Note too, for homogeneous systems, that the solutions give rise to linear combinations that equal the zero vector.

Archetype A, Archetype B, Archetype C, Archetype D, Archetype E, Archetype F, Archetype G, Archetype H, Archetype I, Archetype J

Solution

Solutions for Archetype A and Archetype B are described carefully in Example AALC and Example ABLC.

C22.

Consider each archetype that is a system of equations. Write elements of the solution set in vector form, as guaranteed by Theorem VFSLS.

Archetype A, Archetype B, Archetype C, Archetype D, Archetype E, Archetype F, Archetype G, Archetype H, Archetype I, Archetype J

Solution

Solutions for Archetype D and Archetype I are described carefully in Example VFSAD and Example VFSAI. The technique described in these examples is probably more useful than carefully deciphering the notation of Theorem VFSLS. The solution for each archetype is contained in its description. So now you can check-off the box for that item.

C40.

Find the vector form of the solutions to the system of equations below.

\begin{align*} 2x_1-4x_2+3x_3+x_5&=6\\ x_1-2x_2-2x_3+14x_4-4x_5&=15\\ x_1-2x_2+x_3+2x_4+x_5&=-1\\ -2x_1+4x_2-12x_4+x_5&=-7 \end{align*}
Solution

Row-reduce the augmented matrix representing this system, to find

\begin{equation*} \begin{bmatrix} \leading{1} & -2 & 0 & 6 & 0 & 1\\ 0 & 0 & \leading{1} & -4 & 0 & 3\\ 0 & 0 & 0 & 0 & \leading{1} & -5\\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}\text{.} \end{equation*}

The system is consistent (no pivot column in column 6, Theorem RCLS). \(x_2\) and \(x_4\) are the free variables. Now apply Theorem VFSLS directly, or follow the three-step process of Example VFS, Example VFSAD, Example VFSAI, or Example VFSAL to obtain

\begin{equation*} \colvector{x_1\\x_2\\x_3\\x_4\\x_5} = \colvector{1\\0\\3\\0\\-5}+ x_2\colvector{2\\1\\0\\0\\0}+ x_4\colvector{-6\\0\\4\\1\\0}\text{.} \end{equation*}
C41.

Find the vector form of the solutions to the system of equations below.

\begin{align*} -2 x_1 -1 x_2 -8 x_3+ 8 x_4+ 4 x_5 -9 x_6 -1 x_7 -1 x_8 -18 x_9 &= 3\\ 3 x_1 -2 x_2+ 5 x_3+ 2 x_4 -2 x_5 -5 x_6+ 1 x_7+ 2 x_8+ 15 x_9 &= 10\\ 4 x_1 -2 x_2+ 8 x_3+ 2 x_5 -14 x_6 -2 x_8+ 2 x_9 &= 36\\ -1 x_1+ 2 x_2+ 1 x_3 -6 x_4+ 7 x_6 -1 x_7 -3 x_9 &= -8\\ 3 x_1+ 2 x_2+ 13 x_3 -14 x_4 -1 x_5+ 5 x_6 -1 x_8+ 12 x_9 &= 15\\ -2 x_1+ 2 x_2 -2 x_3 -4 x_4+ 1 x_5+ 6 x_6 -2 x_7 -2 x_8 -15 x_9 &= -7 \end{align*}
Solution

Row-reduce the augmented matrix representing this system, to find

\begin{equation*} \begin{bmatrix} \leading{1} & 0 & 3 & -2 & 0 & -1 & 0 & 0 & 3 & 6 \\ 0 & \leading{1} & 2 & -4 & 0 & 3 & 0 & 0 & 2 & -1 \\ 0 & 0 & 0 & 0 & \leading{1} & -2 & 0 & 0 & -1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & \leading{1} & 0 & 4 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \leading{1} & 2 & -2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}\text{.} \end{equation*}

The system is consistent (no pivot column in column 10, Theorem RCLS). \(F=\set{3,\,4,\,6,\,9,\,10}\text{,}\) so the free variables are \(x_3,\,x_4,\,x_6\) and \(x_9\text{.}\) Now apply Theorem VFSLS directly, or follow the three-step process of Example VFS, Example VFSAD, Example VFSAI, or Example VFSAL to obtain the solution set.

\begin{equation*} S=\setparts{ \colvector{ 6\\ -1\\ 0\\ 0\\ 3\\ 0\\ 0\\ -2\\0}+ x_3\colvector{ -3\\ -2\\ 1\\ 0\\ 0\\ 0\\ 0\\ 0\\0}+ x_4\colvector{ 2\\ 4\\ 0\\ 1\\ 0\\ 0\\ 0\\ 0\\0}+ x_6\colvector{ 1\\ -3\\ 0\\ 0\\ 2\\ 1\\ 0\\ 0\\0}+ x_9\colvector{ -3\\ -2\\ 0\\ 0\\ 1\\ 0\\ -4\\ -2\\1} }{ x_3,\,x_4,\,x_6,\,x_9\in\complexes } \end{equation*}
M10.

Example TLC asks if the vector

\begin{equation*} \vect{w}=\colvector{13\\15\\5\\-17\\2\\25} \end{equation*}

can be written as a linear combination of the four vectors

\begin{align*} \vect{u}_1&=\colvector{2\\4\\-3\\1\\2\\9}& \vect{u}_2&=\colvector{6\\3\\0\\-2\\1\\4}& \vect{u}_3&=\colvector{-5\\2\\1\\1\\-3\\0}& \vect{u}_4&=\colvector{3\\2\\-5\\7\\1\\3}\text{.} \end{align*}

Can it? Can any vector in \(\complex{6}\) be written as a linear combination of the four vectors \(\vect{u}_1,\,\vect{u}_2,\,\vect{u}_3,\,\vect{u}_4\text{?}\)

Solution

No, it is not possible to create \(\vect{w}\) as a linear combination of the four vectors \(\vect{u}_1,\,\vect{u}_2,\,\vect{u}_3,\,\vect{u}_4\text{.}\) By creating the desired linear combination with unknowns as scalars, Theorem SLSLC provides a system of equations that has no solution. This one computation is enough to show us that it is not possible to create all the vectors of \(\complex{6}\) through linear combinations of the four vectors \(\vect{u}_1,\,\vect{u}_2,\,\vect{u}_3,\,\vect{u}_4\text{.}\)

M11.

At the end of Example VFS, the vector \(\vect{w}\) is claimed to be a solution to the linear system under discussion. Verify that \(\vect{w}\) really is a solution. Then determine the four scalars that express \(\vect{w}\) as a linear combination of \(\vect{c}\text{,}\) \(\vect{u}_1\text{,}\) \(\vect{u}_2\text{,}\) \(\vect{u}_3\text{.}\)

Solution

The coefficient of \(\vect{c}\) is 1. The coefficients of \(\vect{u}_1\text{,}\) \(\vect{u}_2\text{,}\) \(\vect{u}_3\) lie in the third, fourth and seventh entries of \(\vect{w}\text{.}\) Can you see why? (Hint: \(F=\set{3,\,4,\,7,\,8}\text{,}\) so the free variables are \(x_3,\,x_4\) and \(x_7\text{.}\))