Section LC  Linear Combinations

From A First Course in Linear Algebra
Version 2.23
© 2004.
Licensed under the GNU Free Documentation License.
http://linear.ups.edu/

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 {u}_{1},\kern 1.95872pt {u}_{2},\kern 1.95872pt {u}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {u}_{n} from {ℂ}^{m} and n scalars {α}_{1},\kern 1.95872pt {α}_{2},\kern 1.95872pt {α}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {α}_{n}, their linear combination is the vector

{α}_{1}{u}_{1} + {α}_{2}{u}_{2} + {α}_{3}{u}_{3} + \mathrel{⋯} + {α}_{n}{u}_{n}

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.

Example TLC
Two linear combinations in {ℂ}^{6}
Suppose that

\eqalignno{ {α}_{1} = 1 & &{α}_{2} = −4 & &{α}_{3} = 2 & &{α}_{4} = −1 & & & & & & & & }

and

\eqalignno{ {u}_{1} & = \left [\array{ 2\cr 4 \cr −3\cr 1 \cr 2\cr 9 } \right ] &{u}_{2} & = \left [\array{ 6\cr 3 \cr 0\cr −2 \cr 1\cr 4 } \right ] &{u}_{3} & = \left [\array{ −5\cr 2 \cr 1\cr 1 \cr −3\cr 0 } \right ] &{u}_{4} & = \left [\array{ 3\cr 2 \cr −5\cr 7 \cr 1\cr 3 } \right ] & & & & & & & & }

then their linear combination is

\eqalignno{ {α}_{1}{u}_{1} + {α}_{2}{u}_{2} + {α}_{3}{u}_{3} + {α}_{4}{u}_{4} & = (1)\left [\array{ 2\cr 4 \cr −3\cr 1 \cr 2\cr 9 } \right ] + (−4)\left [\array{ 6\cr 3 \cr 0\cr −2 \cr 1\cr 4 } \right ] + (2)\left [\array{ −5\cr 2 \cr 1\cr 1 \cr −3\cr 0 } \right ] + (−1)\left [\array{ 3\cr 2 \cr −5\cr 7 \cr 1\cr 3 } \right ] & & \cr & = \left [\array{ 2\cr 4 \cr −3\cr 1 \cr 2\cr 9 } \right ] + \left [\array{ −24\cr −12 \cr 0\cr 8 \cr −4\cr −16 } \right ] + \left [\array{ −10\cr 4 \cr 2\cr 2 \cr −6\cr 0 } \right ] + \left [\array{ −3\cr −2 \cr 5\cr −7 \cr −1\cr −3 } \right ] = \left [\array{ −35\cr −6 \cr 4\cr 4 \cr −9\cr −10 } \right ] & & }

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

\eqalignno{ {β}_{1} = 3 & &{β}_{2} = 0 & &{β}_{3} = 5 & &{β}_{4} = −1 & & & & & & & & }

and form the linear combination

\eqalignno{ {β}_{1}{u}_{1} + {β}_{2}{u}_{2} + {β}_{3}{u}_{3} + {β}_{4}{u}_{4} & = (3)\left [\array{ 2\cr 4 \cr −3\cr 1 \cr 2\cr 9 } \right ] + (0)\left [\array{ 6\cr 3 \cr 0\cr −2 \cr 1\cr 4 } \right ] + (5)\left [\array{ −5\cr 2 \cr 1\cr 1 \cr −3\cr 0 } \right ] + (−1)\left [\array{ 3\cr 2 \cr −5\cr 7 \cr 1\cr 3 } \right ] & & \cr & = \left [\array{ 6\cr 12 \cr −9\cr 3 \cr 6\cr 27 } \right ] + \left [\array{ 0\cr 0 \cr 0\cr 0 \cr 0\cr 0 } \right ] + \left [\array{ −25\cr 10 \cr 5\cr 5 \cr −15\cr 0 } \right ] + \left [\array{ −3\cr −2 \cr 5\cr −7 \cr −1\cr −3 } \right ] = \left [\array{ −22\cr 20 \cr 1\cr 1 \cr −10\cr 24 } \right ] & & }

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 {u}_{1},\kern 1.95872pt {u}_{2},\kern 1.95872pt {u}_{3},\kern 1.95872pt {u}_{4} right now. We’ll be right here when you get back. What vectors were you able to create? Do you think you could create the vector

w = \left [\array{ 13\cr 15 \cr 5\cr −17 \cr 2\cr 25} \right ]

with a “suitable” choice of four scalars? Do you think you could create any possible vector from {ℂ}^{6} by choosing the proper scalars? These last two questions are very fundamental, and time spent considering them now will prove beneficial later.

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

Example ABLC
Archetype B as a linear combination
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

\left [\array{ −7{x}_{1} − 6{x}_{2} − 12{x}_{3} \cr 5{x}_{1} + 5{x}_{2} + 7{x}_{3} \cr {x}_{1} + 4{x}_{3} } \right ] = \left [\array{ −33\cr 24 \cr 5 } \right ]

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

\left [\array{ −7{x}_{1} \cr 5{x}_{1} \cr {x}_{1} } \right ]+\left [\array{ −6{x}_{2} \cr 5{x}_{2} \cr 0{x}_{2} } \right ]+\left [\array{ −12{x}_{3} \cr 7{x}_{3} \cr 4{x}_{3} } \right ] = \left [\array{ −33\cr 24 \cr 5 } \right ]

Now we can rewrite each of these n = 3 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

{ x}_{1}\left [\array{ −7\cr 5 \cr 1 } \right ]+{x}_{2}\left [\array{ −6\cr 5 \cr 0 } \right ]+{x}_{3}\left [\array{ −12\cr 7 \cr 4 } \right ] = \left [\array{ −33\cr 24 \cr 5 } \right ]

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 × 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

\eqalignno{ {x}_{1} = −3 & &{x}_{2} = 5 & &{x}_{3} = 2 & & & & & & }

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,

(−3)\left [\array{ −7\cr 5 \cr 1 } \right ]+(5)\left [\array{ −6\cr 5 \cr 0 } \right ]+(2)\left [\array{ −12\cr 7 \cr 4 } \right ] = \left [\array{ −33\cr 24 \cr 5 } \right ]

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.

Example AALC
Archetype A as a linear combination
As a vector equality, Archetype A can be written as

\left [\array{ {x}_{1} − {x}_{2} + 2{x}_{3} \cr 2{x}_{1} + {x}_{2} + {x}_{3} \cr {x}_{1} + {x}_{2} } \right ] = \left [\array{ 1\cr 8 \cr 5 } \right ]

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

\left [\array{ {x}_{1} \cr 2{x}_{1} \cr {x}_{1} } \right ]+\left [\array{ −{x}_{2} \cr {x}_{2} \cr {x}_{2} } \right ]+\left [\array{ 2{x}_{3} \cr {x}_{3} \cr 0{x}_{3}} \right ] = \left [\array{ 1\cr 8 \cr 5 } \right ]

Rewrite each of these n = 3 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

{ x}_{1}\left [\array{ 1\cr 2 \cr 1 } \right ]+{x}_{2}\left [\array{ −1\cr 1 \cr 1 } \right ]+{x}_{3}\left [\array{ 2\cr 1 \cr 0 } \right ] = \left [\array{ 1\cr 8 \cr 5 } \right ]

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

\eqalignno{ {x}_{1} = 2 & &{x}_{2} = 3 & &{x}_{3} = 1 & & & & & & \cr {x}_{1} = 3 & &{x}_{2} = 2 & &{x}_{3} = 0 & & & & & & }

can be used together to say that,

(2)\left [\array{ 1\cr 2 \cr 1 } \right ]+(3)\left [\array{ −1\cr 1 \cr 1 } \right ]+(1)\left [\array{ 2\cr 1 \cr 0 } \right ] = \left [\array{ 1\cr 8 \cr 5 } \right ] = (3)\left [\array{ 1\cr 2 \cr 1 } \right ]+(2)\left [\array{ −1\cr 1 \cr 1 } \right ]+(0)\left [\array{ 2\cr 1 \cr 0 } \right ]

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

(2)\left [\array{ 1\cr 2 \cr 1 } \right ]+(3)\left [\array{ −1\cr 1 \cr 1 } \right ]+(1)\left [\array{ 2\cr 1 \cr 0 } \right ]+(−3)\left [\array{ 1\cr 2 \cr 1 } \right ]+(−2)\left [\array{ −1\cr 1 \cr 1 } \right ]+(−0)\left [\array{ 2\cr 1 \cr 0 } \right ] = \left [\array{ 0\cr 0 \cr 0 } \right ]

Regrouping gives

(−1)\left [\array{ 1\cr 2 \cr 1 } \right ]+(1)\left [\array{ −1\cr 1 \cr 1 } \right ]+(1)\left [\array{ 2\cr 1 \cr 0 } \right ] = \left [\array{ 0\cr 0 \cr 0 } \right ]

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, but this says that

\eqalignno{ {x}_{1} = −1 & &{x}_{2} = 1 & &{x}_{3} = 1 & & & & & & }

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’s 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.

Theorem SLSLC
Solutions to Linear Systems are Linear Combinations
Denote the columns of the m × n matrix A as the vectors {A}_{1},\kern 1.95872pt {A}_{2},\kern 1.95872pt {A}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {A}_{n}. Then x is a solution to the linear system of equations ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) if and only if b equals the linear combination of the columns of A formed with the entries of x,

{ \left [x\right ]}_{1}{A}_{1} +{ \left [x\right ]}_{2}{A}_{2} +{ \left [x\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [x\right ]}_{n}{A}_{n} = b

Proof   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 ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) as

\eqalignno{ {a}_{11}{x}_{1} + {a}_{12}{x}_{2} + {a}_{13}{x}_{3} + \mathrel{⋯} + {a}_{1n}{x}_{n} & = {b}_{1} & & \cr {a}_{21}{x}_{1} + {a}_{22}{x}_{2} + {a}_{23}{x}_{3} + \mathrel{⋯} + {a}_{2n}{x}_{n} & = {b}_{2} & & \cr {a}_{31}{x}_{1} + {a}_{32}{x}_{2} + {a}_{33}{x}_{3} + \mathrel{⋯} + {a}_{3n}{x}_{n} & = {b}_{3} & & \cr \mathop{\mathop{⋮}} & & & \cr {a}_{m1}{x}_{1} + {a}_{m2}{x}_{2} + {a}_{m3}{x}_{3} + \mathrel{⋯} + {a}_{mn}{x}_{n} & = {b}_{m} & & }

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 {\left [{A}_{j}\right ]}_{i} as the i-th entry of the column vector in column j of the coefficient matrix A. Likewise, entry i of b has two names: {b}_{i} from the linear system and {\left [b\right ]}_{i} as an entry of a vector. Our theorem is an equivalence (Technique E) so we need to prove both “directions.”

() Suppose we have the vector equality between b and the linear combination of the columns of A. Then for 1 ≤ i ≤ m,

\eqalignno{ {b}_{i} & ={ \left [b\right ]}_{i} & &\text{@(a href="fcla-jsmath-2.23li18.html#notation.CVC")Notation CVC@(/a)} & & & & \cr & ={ \left [{\left [x\right ]}_{1}{A}_{1} +{ \left [x\right ]}_{2}{A}_{2} +{ \left [x\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [x\right ]}_{n}{A}_{n}\right ]}_{i} & &\text{Hypothesis} & & & & \cr & ={ \left [{\left [x\right ]}_{1}{A}_{1}\right ]}_{i} +{ \left [{\left [x\right ]}_{2}{A}_{2}\right ]}_{i} +{ \left [{\left [x\right ]}_{3}{A}_{3}\right ]}_{i} + \mathrel{⋯} +{ \left [{\left [x\right ]}_{n}{A}_{n}\right ]}_{i} & &\text{@(a href="fcla-jsmath-2.23li23.html#definition.CVA")Definition CVA@(/a)} & & & & \cr & ={ \left [x\right ]}_{1}{\left [{A}_{1}\right ]}_{i} +{ \left [x\right ]}_{2}{\left [{A}_{2}\right ]}_{i} +{ \left [x\right ]}_{3}{\left [{A}_{3}\right ]}_{i} + \mathrel{⋯} +{ \left [x\right ]}_{n}{\left [{A}_{n}\right ]}_{i} & &\text{@(a href="fcla-jsmath-2.23li23.html#definition.CVSM")Definition CVSM@(/a)} & & & & \cr & ={ \left [x\right ]}_{1}{a}_{i1} +{ \left [x\right ]}_{2}{a}_{i2} +{ \left [x\right ]}_{3}{a}_{i3} + \mathrel{⋯} +{ \left [x\right ]}_{n}{a}_{in} & &\text{@(a href="fcla-jsmath-2.23li18.html#notation.CVC")Notation CVC@(/a)} & & & & \cr & = {a}_{i1}{\left [x\right ]}_{1} + {a}_{i2}{\left [x\right ]}_{2} + {a}_{i3}{\left [x\right ]}_{3} + \mathrel{⋯} + {a}_{in}{\left [x\right ]}_{n} & &\text{@(a href="fcla-jsmath-2.23li69.html#property.CMCN")Property CMCN@(/a)} & & & & }

This says that the entries of x form a solution to equation i of ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) for all 1 ≤ i ≤ m, in other words, x is a solution to ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ).

() Suppose now that x is a solution to the linear system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ). Then for all 1 ≤ i ≤ m,

\eqalignno{ {\left [b\right ]}_{i} & = {b}_{i} & &\text{@(a href="fcla-jsmath-2.23li18.html#notation.CVC")Notation CVC@(/a)} & & & & \cr & = {a}_{i1}{\left [x\right ]}_{1} + {a}_{i2}{\left [x\right ]}_{2} + {a}_{i3}{\left [x\right ]}_{3} + \mathrel{⋯} + {a}_{in}{\left [x\right ]}_{n} & &\text{Hypothesis} & & & & \cr & ={ \left [x\right ]}_{1}{a}_{i1} +{ \left [x\right ]}_{2}{a}_{i2} +{ \left [x\right ]}_{3}{a}_{i3} + \mathrel{⋯} +{ \left [x\right ]}_{n}{a}_{in} & &\text{@(a href="fcla-jsmath-2.23li69.html#property.CMCN")Property CMCN@(/a)} & & & & \cr & ={ \left [x\right ]}_{1}{\left [{A}_{1}\right ]}_{i} +{ \left [x\right ]}_{2}{\left [{A}_{2}\right ]}_{i} +{ \left [x\right ]}_{3}{\left [{A}_{3}\right ]}_{i} + \mathrel{⋯} +{ \left [x\right ]}_{n}{\left [{A}_{n}\right ]}_{i} & &\text{@(a href="fcla-jsmath-2.23li18.html#notation.CVC")Notation CVC@(/a)} & & & & \cr & ={ \left [{\left [x\right ]}_{1}{A}_{1}\right ]}_{i} +{ \left [{\left [x\right ]}_{2}{A}_{2}\right ]}_{i} +{ \left [{\left [x\right ]}_{3}{A}_{3}\right ]}_{i} + \mathrel{⋯} +{ \left [{\left [x\right ]}_{n}{A}_{n}\right ]}_{i} & &\text{@(a href="fcla-jsmath-2.23li23.html#definition.CVSM")Definition CVSM@(/a)} & & & & \cr & ={ \left [{\left [x\right ]}_{1}{A}_{1} +{ \left [x\right ]}_{2}{A}_{2} +{ \left [x\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [x\right ]}_{n}{A}_{n}\right ]}_{i} & &\text{@(a href="fcla-jsmath-2.23li23.html#definition.CVA")Definition CVA@(/a)} & & & & }

Since the components of b and the linear combination of the columns of A agree for all 1 ≤ i ≤ m, Definition CVE tells us that the vectors are equal.

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 ({A}_{j}) which yield the constant vector b. Or said another way, a solution to a system of equations ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) is an answer to the question “How can I form the vector b as a linear combination of the columns of A?” 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).

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,\kern 1.95872pt {x}_{2} = 5,\kern 1.95872pt {x}_{3} = 2 which we now write as

x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} } \right ] = \left [\array{ −3\cr 5 \cr 2 } \right ]

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’s 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.

Example VFSAD
Vector form of solutions for Archetype D
Archetype D is a linear system of 3 equations in 4 variables. Row-reducing the augmented matrix yields

\left [\array{ \text{1}&0&3&−2&4\cr 0&\text{1 } &1 &−3 &0 \cr 0&0&0& 0 &0 } \right ]

and we see r = 2 nonzero rows. Also, D = \left \{1,\kern 1.95872pt 2\right \} so the dependent variables are then {x}_{1} and {x}_{2}. F = \left \{3,\kern 1.95872pt 4,\kern 1.95872pt 5\right \} so the two free variables are {x}_{3} and {x}_{4}. 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 (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,

\eqalignno{ \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} } \right ] & = \left [\array{ 4 − 3{x}_{3} + 2{x}_{4} \cr −{x}_{3} + 3{x}_{4} \cr {x}_{3} \cr {x}_{4} } \right ] & & & & \text{Now we will use the definitions of column vector addition and scalar multiplication to express this vector as a linear combination,} \cr & = \left [\array{ 4\cr 0 \cr 0\cr 0 } \right ] + \left [\array{ −3{x}_{3} \cr −{x}_{3} \cr {x}_{3} \cr 0} \right ] + \left [\array{ 2{x}_{4} \cr 3{x}_{4} \cr 0\cr {x}_{ 4} } \right ] & &\text{@(a href="fcla-jsmath-2.23li23.html#definition.CVA")Definition CVA@(/a)} & & & & \cr & = \left [\array{ 4\cr 0 \cr 0\cr 0 } \right ] + {x}_{3}\left [\array{ −3\cr −1 \cr 1\cr 0 } \right ] + {x}_{4}\left [\array{ 2\cr 3 \cr 0\cr 1 } \right ] & &\text{@(a href="fcla-jsmath-2.23li23.html#definition.CVSM")Definition CVSM@(/a)} & & & & \cr & & & & }

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.

x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} } \right ] = \left [\array{ \ \cr \ \cr \ \cr \ } \right ]+{x}_{3}\left [\array{ \ \cr \ \cr \ \cr \ } \right ]+{x}_{4}\left [\array{ \ \cr \ \cr \ \cr \ } \right ]

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

x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} } \right ] = \left [\array{ \ \cr \ \cr 0 \cr 0 } \right ]+{x}_{3}\left [\array{ \ \cr \ \cr 1 \cr 0 } \right ]+{x}_{4}\left [\array{ \ \cr \ \cr 0 \cr 1 } \right ]

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.

\eqalignno{ {x}_{1} = 4 − 3{x}_{3} + 2{x}_{4} & & ⇒ & &x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} } \right ] = \left [\array{ 4\cr \ \cr 0 \cr 0 } \right ] + {x}_{3}\left [\array{ −3\cr \ \cr 1 \cr 0 } \right ] + {x}_{4}\left [\array{ 2\cr \ \cr 0 \cr 1 } \right ] & & & & & & \cr {x}_{2} = 0 − 1{x}_{3} + 3{x}_{4} & & ⇒ & &x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} } \right ] = \left [\array{ 4\cr 0 \cr 0\cr 0 } \right ] + {x}_{3}\left [\array{ −3\cr −1 \cr 1\cr 0 } \right ] + {x}_{4}\left [\array{ 2\cr 3 \cr 0\cr 1 } \right ] & & & & & & }

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

\eqalignno{ {x}_{3} = 2,\kern 1.95872pt {x}_{4} = −5 & & ⇒ & &x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} } \right ] = \left [\array{ 4\cr 0 \cr 0\cr 0 } \right ] + (2)\left [\array{ −3\cr −1 \cr 1\cr 0 } \right ] + (−5)\left [\array{ 2\cr 3 \cr 0\cr 1 } \right ] = \left [\array{ −12\cr −17 \cr 2\cr −5 } \right ] & & & & & & \text{or,} \cr {x}_{3} = 1,\kern 1.95872pt {x}_{4} = 3 & & ⇒ & &x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} } \right ] = \left [\array{ 4\cr 0 \cr 0\cr 0 } \right ] + (1)\left [\array{ −3\cr −1 \cr 1\cr 0 } \right ] + (3)\left [\array{ 2\cr 3 \cr 0\cr 1 } \right ] = \left [\array{ 7\cr 8 \cr 1\cr 3 } \right ] & & & & & & }

You’ll 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, its 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 a solution is some multiple of \left [\array{ −3\cr −1 \cr 1\cr 0 } \right ]plus a multiple of \left [\array{ 2\cr 3 \cr 0\cr 1 } \right ] plus the fixed vector \left [\array{ 4\cr 0 \cr 0\cr 0 } \right ]. 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’ll do another example.

Example VFS
Vector form of solutions
Consider a linear system of m = 5 equations in n = 7 variables, having the augmented matrix A.

A = \left [\array{ 2 & 1 &−1&−2&2&1& 5 & 21\cr 1 & 1 &−3 & 1 &1 &1 & 2 & −5 \cr 1 & 2 &−8& 5 &1&1&−6&−15\cr 3 & 3 &−9 & 3 &6 &5 & 2 &−24 \cr −2&−1& 1 & 2 &1&1&−9&−30 } \right ]

Row-reducing we obtain the matrix

B = \left [\array{ \text{1}&0& 2 &−3&0&0& 9 & 15\cr 0&\text{1 } &−5 & 4 &0 &0 &−8 &−10 \cr 0&0& 0 & 0 &\text{1}&0&−6& 11\cr 0&0 & 0 & 0 &0 &\text{1 } & 7 &−21 \cr 0&0& 0 & 0 &0&0& 0 & 0 } \right ]

and we see r = 4 nonzero rows. Also, D = \left \{1,\kern 1.95872pt 2,\kern 1.95872pt 5,\kern 1.95872pt 6\right \} so the dependent variables are then {x}_{1},\kern 1.95872pt {x}_{2},\kern 1.95872pt {x}_{5}, and {x}_{6}. F = \left \{3,\kern 1.95872pt 4,\kern 1.95872pt 7,\kern 1.95872pt 8\right \} so the n − r = 3 free variables are {x}_{3},\kern 1.95872pt {x}_{4} and {x}_{7}. We will express a generic solution for the system by two different methods: both a decomposition and a construction.

First, we will decompose (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,

\eqalignno{ \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] & = \left [\array{ 15 − 2{x}_{3} + 3{x}_{4} − 9{x}_{7} \cr −10 + 5{x}_{3} − 4{x}_{4} + 8{x}_{7} \cr {x}_{3} \cr {x}_{4} \cr 11 + 6{x}_{7} \cr −21 − 7{x}_{7} \cr {x}_{7} } \right ] & & & & \text{Now we will use the definitions of column vector addition and scalar multiplication to decompose this generic solution vector as a linear combination,} \cr & = \left [\array{ 15\cr −10 \cr 0\cr 0 \cr 11\cr −21 \cr 0 } \right ] + \left [\array{ −2{x}_{3} \cr 5{x}_{3} \cr {x}_{3} \cr 0\cr 0 \cr 0\cr 0} \right ] + \left [\array{ 3{x}_{4} \cr −4{x}_{4} \cr 0\cr {x}_{ 4} \cr 0\cr 0 \cr 0} \right ] + \left [\array{ −9{x}_{7} \cr 8{x}_{7} \cr 0\cr 0 \cr 6{x}_{7} \cr −7{x}_{7} \cr {x}_{7} } \right ] & &\text{@(a href="fcla-jsmath-2.23li23.html#definition.CVA")Definition CVA@(/a)} & & & & \cr & = \left [\array{ 15\cr −10 \cr 0\cr 0 \cr 11\cr −21 \cr 0 } \right ] + {x}_{3}\left [\array{ −2\cr 5 \cr 1\cr 0 \cr 0\cr 0 \cr 0 } \right ] + {x}_{4}\left [\array{ 3\cr −4 \cr 0\cr 1 \cr 0\cr 0 \cr 0 } \right ] + {x}_{7}\left [\array{ −9\cr 8 \cr 0\cr 0 \cr 6\cr −7 \cr 1 } \right ] & &\text{@(a href="fcla-jsmath-2.23li23.html#definition.CVSM")Definition CVSM@(/a)} & & & & }

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.

x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ \ \cr \ \cr \ \cr \ \cr \ \cr \ \cr \ } \right ]+{x}_{3}\left [\array{ \ \cr \ \cr \ \cr \ \cr \ \cr \ \cr \ } \right ]+{x}_{4}\left [\array{ \ \cr \ \cr \ \cr \ \cr \ \cr \ \cr \ } \right ]+{x}_{7}\left [\array{ \ \cr \ \cr \ \cr \ \cr \ \cr \ \cr \ } \right ]

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

x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ \cr \cr 0 \cr 0\cr \cr \cr 0 } \right ]+{x}_{3}\left [\array{ \cr \cr 1 \cr 0\cr \cr \cr 0 } \right ]+{x}_{4}\left [\array{ \cr \cr 0 \cr 1\cr \cr \cr 0 } \right ]+{x}_{7}\left [\array{ \cr \cr 0 \cr 0\cr \cr \cr 1 } \right ]

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.

\eqalignno{ {x}_{1}& = 15 − 2{x}_{3} + 3{x}_{4} − 9{x}_{7} & ⇒&&x& = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ 15\cr \cr 0 \cr 0\cr \cr \cr 0 } \right ] + {x}_{3}\left [\array{ −2\cr \cr 1 \cr 0\cr \cr \cr 0 } \right ] + {x}_{4}\left [\array{ 3\cr \cr 0 \cr 1\cr \cr \cr 0 } \right ] + {x}_{7}\left [\array{ −9\cr \cr 0 \cr 0\cr \cr \cr 1 } \right ]&&&&&& \cr {x}_{2}& = −10 + 5{x}_{3} − 4{x}_{4} + 8{x}_{7}& ⇒&&x& = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ 15\cr −10 \cr 0\cr 0\cr \cr \cr 0 } \right ] + {x}_{3}\left [\array{ −2\cr 5 \cr 1\cr 0\cr \cr \cr 0 } \right ] + {x}_{4}\left [\array{ 3\cr −4 \cr 0\cr 1\cr \cr \cr 0 } \right ] + {x}_{7}\left [\array{ −9\cr 8 \cr 0\cr 0\cr \cr \cr 1 } \right ]&&&&&& \cr {x}_{5}& = 11 + 6{x}_{7} & ⇒&&x& = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ 15\cr −10 \cr 0\cr 0 \cr 11\cr \cr 0} \right ] + {x}_{3}\left [\array{ −2\cr 5 \cr 1\cr 0 \cr 0\cr \cr 0 } \right ] + {x}_{4}\left [\array{ 3\cr −4 \cr 0\cr 1 \cr 0\cr \cr 0 } \right ] + {x}_{7}\left [\array{ −9\cr 8 \cr 0\cr 0 \cr 6\cr \cr 1 } \right ]&&&&&& \cr {x}_{6}& = −21 − 7{x}_{7} & ⇒&&x& = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ 15\cr −10 \cr 0\cr 0 \cr 11\cr −21 \cr 0 } \right ] + {x}_{3}\left [\array{ −2\cr 5 \cr 1\cr 0 \cr 0\cr 0 \cr 0 } \right ] + {x}_{4}\left [\array{ 3\cr −4 \cr 0\cr 1 \cr 0\cr 0 \cr 0 } \right ] + {x}_{7}\left [\array{ −9\cr 8 \cr 0\cr 0 \cr 6\cr −7 \cr 1 } \right ]&&&&&& }

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

\eqalignno{ {x}_{3} & = 2,\kern 1.95872pt {x}_{4} = −4,\kern 1.95872pt {x}_{7} = 3\quad \quad ⇒ & & \cr x & = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ 15\cr −10 \cr 0\cr 0 \cr 11\cr −21 \cr 0 } \right ] + (2)\left [\array{ −2\cr 5 \cr 1\cr 0 \cr 0\cr 0 \cr 0 } \right ] + (−4)\left [\array{ 3\cr −4 \cr 0\cr 1 \cr 0\cr 0 \cr 0 } \right ] + (3)\left [\array{ −9\cr 8 \cr 0\cr 0 \cr 6\cr −7 \cr 1 } \right ] = \left [\array{ −28\cr 40 \cr 2\cr −4 \cr 29\cr −42 \cr 3 } \right ] & & }

or perhaps,

\eqalignno{ {x}_{3} & = 5,\kern 1.95872pt {x}_{4} = 2,\kern 1.95872pt {x}_{7} = 1\quad \quad ⇒ & & \cr x & = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ 15\cr −10 \cr 0\cr 0 \cr 11\cr −21 \cr 0 } \right ] + (5)\left [\array{ −2\cr 5 \cr 1\cr 0 \cr 0\cr 0 \cr 0 } \right ] + (2)\left [\array{ 3\cr −4 \cr 0\cr 1 \cr 0\cr 0 \cr 0 } \right ] + (1)\left [\array{ −9\cr 8 \cr 0\cr 0 \cr 6\cr −7 \cr 1 } \right ] = \left [\array{ 2\cr 15 \cr 5\cr 2 \cr 17\cr −28 \cr 1 } \right ] & & }

or even,

\eqalignno{ {x}_{3} & = 0,\kern 1.95872pt {x}_{4} = 0,\kern 1.95872pt {x}_{7} = 0\quad \quad ⇒ & & \cr x & = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ 15\cr −10 \cr 0\cr 0 \cr 11\cr −21 \cr 0 } \right ] + (0)\left [\array{ −2\cr 5 \cr 1\cr 0 \cr 0\cr 0 \cr 0 } \right ] + (0)\left [\array{ 3\cr −4 \cr 0\cr 1 \cr 0\cr 0 \cr 0 } \right ] + (0)\left [\array{ −9\cr 8 \cr 0\cr 0 \cr 6\cr −7 \cr 1 } \right ] = \left [\array{ 15\cr −10 \cr 0\cr 0 \cr 11\cr −21 \cr 0 } \right ] & & }

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 w below was a solution to this system of equations. Could you turn the problem around and write w as a linear combination of the four vectors c, {u}_{1}, {u}_{2}, {u}_{3}? (See Exercise LC.M11.)

\eqalignno{ w & = \left [\array{ 100\cr −75 \cr 7\cr 9 \cr −37\cr 35 \cr −8 } \right ] &c & = \left [\array{ 15\cr −10 \cr 0\cr 0 \cr 11\cr −21 \cr 0 } \right ] &{u}_{1} & = \left [\array{ −2\cr 5 \cr 1\cr 0 \cr 0\cr 0 \cr 0 } \right ] &{u}_{2} & = \left [\array{ 3\cr −4 \cr 0\cr 1 \cr 0\cr 0 \cr 0 } \right ] &{u}_{3} & = \left [\array{ −9\cr 8 \cr 0\cr 0 \cr 6\cr −7 \cr 1 } \right ] & & & & & & & & & & }

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’ll now formalize the last two (important) examples as a theorem.

Theorem VFSLS
Vector Form of Solutions to Linear Systems
Suppose that \left [\left .A\kern 1.95872pt \right \vert \kern 1.95872pt b\right ] is the augmented matrix for a consistent linear system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) of m equations in n variables. Let B be a row-equivalent m × (n + 1) matrix in reduced row-echelon form. Suppose that B has r nonzero rows, columns without leading 1’s with indices F = \left \{{f}_{1},\kern 1.95872pt {f}_{2},\kern 1.95872pt {f}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {f}_{n−r},\kern 1.95872pt n + 1\right \}, and columns with leading 1’s (pivot columns) having indices D = \left \{{d}_{1},\kern 1.95872pt {d}_{2},\kern 1.95872pt {d}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {d}_{r}\right \}. Define vectors c, {u}_{j}, 1 ≤ j ≤ n − r of size n by

\eqalignno{ {\left [c\right ]}_{i} & = \left \{\array{ 0 \quad &\text{if $i ∈ F$}\cr {\left [B\right ] }_{ k,n+1}\quad &\text{if $i ∈ D$, $i = {d}_{k}$} } \right . & & \cr {\left [{u}_{j}\right ]}_{i} & = \left \{\array{ 1 \quad &\text{if $i ∈ F$, $i = {f}_{j}$} \cr 0 \quad &\text{if $i ∈ F$, $i\mathrel{≠}{f}_{j}$} \cr −{\left [B\right ]}_{k,{f}_{j}}\quad &\text{if $i ∈ D$, $i = {d}_{k}$} } \right .. & & }

Then the set of solutions to the system of equations ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) is

S = \left \{\left .c + {α}_{1}{u}_{1} + {α}_{2}{u}_{2} + {α}_{3}{u}_{3} + \mathrel{⋯} + {α}_{n−r}{u}_{n−r}\right \vert {α}_{1},\kern 1.95872pt {α}_{2},\kern 1.95872pt {α}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {α}_{n−r} ∈ {ℂ}^{}\right \}

Proof   First, ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) 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, so we will apply Definition SE.

We begin by showing that every element of S is indeed a solution to the system. Let {α}_{1},\kern 1.95872pt {α}_{2},\kern 1.95872pt {α}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {α}_{n−r} be one choice of the scalars used to describe elements of S. So an arbitrary element of S, which we will consider as a proposed solution is

x = c + {α}_{1}{u}_{1} + {α}_{2}{u}_{2} + {α}_{3}{u}_{3} + \mathrel{⋯} + {α}_{n−r}{u}_{n−r}

When r + 1 ≤ ℓ ≤ m, row 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 ≤ ℓ ≤ r. We evaluate equation of the system represented by B with the proposed solution vector x and refer to the value of the left-hand side of the equation as {β}_{ℓ},

{β}_{ℓ} ={ \left [B\right ]}_{ℓ1}{\left [x\right ]}_{1} +{ \left [B\right ]}_{ℓ2}{\left [x\right ]}_{2} +{ \left [B\right ]}_{ℓ3}{\left [x\right ]}_{3} + \mathrel{⋯} +{ \left [B\right ]}_{ℓn}{\left [x\right ]}_{n}

Since {\left [B\right ]}_{ℓ{d}_{i}} = 0 for all 1 ≤ i ≤ r, except that {\left [B\right ]}_{ℓ{d}_{ℓ}} = 1, we see that {β}_{ℓ} simplifies to

{β}_{ℓ} ={ \left [x\right ]}_{{d}_{ℓ}} +{ \left [B\right ]}_{ℓ{f}_{1}}{\left [x\right ]}_{{f}_{1}} +{ \left [B\right ]}_{ℓ{f}_{2}}{\left [x\right ]}_{{f}_{2}} +{ \left [B\right ]}_{ℓ{f}_{3}}{\left [x\right ]}_{{f}_{3}} + \mathrel{⋯} +{ \left [B\right ]}_{ℓ{f}_{n−r}}{\left [x\right ]}_{{f}_{n−r}}

Notice that for 1 ≤ i ≤ n − r

\eqalignno{ {\left [x\right ]}_{{f}_{i}} & ={ \left [c\right ]}_{{f}_{i}} + {α}_{1}{\left [{u}_{1}\right ]}_{{f}_{i}} + {α}_{2}{\left [{u}_{2}\right ]}_{{f}_{i}} + {α}_{3}{\left [{u}_{3}\right ]}_{{f}_{i}} + \mathrel{⋯} + {α}_{i}{\left [{u}_{i}\right ]}_{{f}_{i}} + \mathrel{⋯} + {α}_{n−r}{\left [{u}_{n−r}\right ]}_{{f}_{i}} & & \cr & = 0 + {α}_{1}(0) + {α}_{2}(0) + {α}_{3}(0) + \mathrel{⋯} + {α}_{i}(1) + \mathrel{⋯} + {α}_{n−r}(0) & & \cr & = {α}_{i} & & }

So {β}_{ℓ} simplifies further, and we expand the first term

\eqalignno{ {β}_{ℓ}& ={ \left [x\right ]}_{{d}_{ℓ}} +{ \left [B\right ]}_{ℓ{f}_{1}}{α}_{1} +{ \left [B\right ]}_{ℓ{f}_{2}}{α}_{2} +{ \left [B\right ]}_{ℓ{f}_{3}}{α}_{3} + \mathrel{⋯} +{ \left [B\right ]}_{ℓ{f}_{n−r}}{α}_{n−r} && \cr & ={ \left [c + {α}_{1}{u}_{1} + {α}_{2}{u}_{2} + {α}_{3}{u}_{3} + \mathrel{⋯} + {α}_{n−r}{u}_{n−r}\right ]}_{{d}_{ℓ}}+ && \cr &\quad \quad {\left [B\right ]}_{ℓ{f}_{1}}{α}_{1} +{ \left [B\right ]}_{ℓ{f}_{2}}{α}_{2} +{ \left [B\right ]}_{ℓ{f}_{3}}{α}_{3} + \mathrel{⋯} +{ \left [B\right ]}_{ℓ{f}_{n−r}}{α}_{n−r} && \cr & ={ \left [c\right ]}_{{d}_{ℓ}} + {α}_{1}{\left [{u}_{1}\right ]}_{{d}_{ℓ}} + {α}_{2}{\left [{u}_{2}\right ]}_{{d}_{ℓ}} + {α}_{3}{\left [{u}_{3}\right ]}_{{d}_{ℓ}} + \mathrel{⋯} + {α}_{n−r}{\left [{u}_{n−r}\right ]}_{{d}_{ℓ}}+ && \cr &\quad \quad {\left [B\right ]}_{ℓ{f}_{1}}{α}_{1} +{ \left [B\right ]}_{ℓ{f}_{2}}{α}_{2} +{ \left [B\right ]}_{ℓ{f}_{3}}{α}_{3} + \mathrel{⋯} +{ \left [B\right ]}_{ℓ{f}_{n−r}}{α}_{n−r} && \cr & ={ \left [B\right ]}_{ℓ,n+1} + {α}_{1}(−{\left [B\right ]}_{ℓ,{f}_{1}}) + {α}_{2}(−{\left [B\right ]}_{ℓ,{f}_{2}}) + {α}_{3}(−{\left [B\right ]}_{ℓ,{f}_{3}}) + \mathrel{⋯} + {α}_{n−r}(−{\left [B\right ]}_{ℓ,{f}_{n−r}})+&& \cr &\quad \quad {\left [B\right ]}_{ℓ{f}_{1}}{α}_{1} +{ \left [B\right ]}_{ℓ{f}_{2}}{α}_{2} +{ \left [B\right ]}_{ℓ{f}_{3}}{α}_{3} + \mathrel{⋯} +{ \left [B\right ]}_{ℓ{f}_{n−r}}{α}_{n−r} && \cr & ={ \left [B\right ]}_{ℓ,n+1} && }

So {β}_{ℓ} began as the left-hand side of equation of the system represented by B and we now know it equals {\left [B\right ]}_{ℓ,n+1}, the constant term for equation 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 x is a solution vector for the system having B as its augmented matrix. For convenience and clarity, denote the entries of x by {x}_{i}, in other words, {x}_{i} ={ \left [x\right ]}_{i}. We desire to show that this solution vector is also an element of the set S. Begin with the observation that a solution vector’s entries makes equation of the system true for all 1 ≤ ℓ ≤ m,

{ \left [B\right ]}_{ℓ,1}{x}_{1} +{ \left [B\right ]}_{ℓ,2}{x}_{2} +{ \left [B\right ]}_{ℓ,3}{x}_{3} + \mathrel{⋯} +{ \left [B\right ]}_{ℓ,n}{x}_{n} ={ \left [B\right ]}_{ℓ,n+1}

When ℓ ≤ r, the pivot columns of B have zero entries in row with the exception of column {d}_{ℓ}, which will contain a 1. So for 1 ≤ ℓ ≤ r, equation simplifies to

1{x}_{{d}_{ℓ}} +{ \left [B\right ]}_{ℓ,{f}_{1}}{x}_{{f}_{1}} +{ \left [B\right ]}_{ℓ,{f}_{2}}{x}_{{f}_{2}} +{ \left [B\right ]}_{ℓ,{f}_{3}}{x}_{{f}_{3}} + \mathrel{⋯} +{ \left [B\right ]}_{ℓ,{f}_{n−r}}{x}_{{f}_{n−r}} ={ \left [B\right ]}_{ℓ,n+1}

This allows us to write,

\eqalignno{ {\left [x\right ]}_{{d}_{ℓ}} & = {x}_{{d}_{ℓ}} & & \cr & ={ \left [B\right ]}_{ℓ,n+1} −{\left [B\right ]}_{ℓ,{f}_{1}}{x}_{{f}_{1}} −{\left [B\right ]}_{ℓ,{f}_{2}}{x}_{{f}_{2}} −{\left [B\right ]}_{ℓ,{f}_{3}}{x}_{{f}_{3}} −\mathrel{⋯} −{\left [B\right ]}_{ℓ,{f}_{n−r}}{x}_{{f}_{n−r}} & & \cr & ={ \left [c\right ]}_{{d}_{ℓ}} + {x}_{{f}_{1}}{\left [{u}_{1}\right ]}_{{d}_{ℓ}} + {x}_{{f}_{2}}{\left [{u}_{2}\right ]}_{{d}_{ℓ}} + {x}_{{f}_{3}}{\left [{u}_{3}\right ]}_{{d}_{ℓ}} + \mathrel{⋯} + {x}_{{f}_{n−r}}{\left [{u}_{n−r}\right ]}_{{d}_{ℓ}} & & \cr & ={ \left [c + {x}_{{f}_{1}}{u}_{1} + {x}_{{f}_{2}}{u}_{2} + {x}_{{f}_{3}}{u}_{3} + \mathrel{⋯} + {x}_{{f}_{n−r}}{u}_{n−r}\right ]}_{{d}_{ℓ}} & & }

This tells us that the entries of the solution vector x corresponding to dependent variables (indices in D), are equal to those of a vector in the set S. We still need to check the other entries of the solution vector 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. To this end, suppose i ∈ F and i = {f}_{j}. Then

\eqalignno{ {\left [x\right ]}_{i} & = {x}_{i} = {x}_{{f}_{j}} & & \cr & = 0 + 0{x}_{{f}_{1}} + 0{x}_{{f}_{2}} + 0{x}_{{f}_{3}} + \mathrel{⋯} + 0{x}_{{f}_{j−1}} + 1{x}_{{f}_{j}} + 0{x}_{{f}_{j+1}} + \mathrel{⋯} + 0{x}_{{f}_{n−r}} & & \cr & ={ \left [c\right ]}_{i} + {x}_{{f}_{1}}{\left [{u}_{1}\right ]}_{i} + {x}_{{f}_{2}}{\left [{u}_{2}\right ]}_{i} + {x}_{{f}_{3}}{\left [{u}_{3}\right ]}_{i} + \mathrel{⋯} + {x}_{{f}_{j}}{\left [{u}_{j}\right ]}_{i} + \mathrel{⋯} + {x}_{{f}_{n−r}}{\left [{u}_{n−r}\right ]}_{i} & & \cr & ={ \left [c + {x}_{{f}_{1}}{u}_{1} + {x}_{{f}_{2}}{u}_{2} + \mathrel{⋯} + {x}_{{f}_{n−r}}{u}_{n−r}\right ]}_{i} & & }

So entries of x and c + {x}_{{f}_{1}}{u}_{1} + {x}_{{f}_{2}}{u}_{2} + \mathrel{⋯} + {x}_{{f}_{n−r}}{u}_{n−r} are equal and therefore by Definition CVE they are equal vectors. Since {x}_{{f}_{1}},\kern 1.95872pt {x}_{{f}_{2}},\kern 1.95872pt {x}_{{f}_{3}},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {x}_{{f}_{n−r}} are scalars, this shows us that x qualifies for membership in S. So the set S contains all of the solutions to the system.

Note that both halves of the proof of Theorem VFSLS indicate that {α}_{i} ={ \left [x\right ]}_{{f}_{i}}. In other words, the arbitrary scalars, {α}_{i}, in the description of the set S actually have more meaning — they are the values of the free variables {\left [x\right ]}_{{f}_{i}}, 1 ≤ i ≤ n − r. 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’s practice some more, but with a bigger example.

Example VFSAI
Vector form of solutions for Archetype I
Archetype I is a linear system of m = 4 equations in n = 7 variables. Row-reducing the augmented matrix yields

\left [\array{ \text{1}&4&0&0&2& 1 &−3&4\cr 0&0 &\text{1 } &0 &1 &−3 & 5 &2 \cr 0&0&0&\text{1}&2&−6& 6 &1\cr 0&0 &0 &0 &0 & 0 & 0 &0 } \right ]

and we see r = 3 nonzero rows. The columns with leading 1’s are D = \{1,\kern 1.95872pt 3,\kern 1.95872pt 4\} so the r dependent variables are {x}_{1},\kern 1.95872pt {x}_{3},\kern 1.95872pt {x}_{4}. The columns without leading 1’s are F = \{2,\kern 1.95872pt 5,\kern 1.95872pt 6,\kern 1.95872pt 7,\kern 1.95872pt 8\}, so the n − r = 4 free variables are {x}_{2},\kern 1.95872pt {x}_{5},\kern 1.95872pt {x}_{6},\kern 1.95872pt {x}_{7}.

Step 1. Write the vector of variables (x) as a fixed vector (c), plus a linear combination of n − r = 4 vectors ({u}_{1},\kern 1.95872pt {u}_{2},\kern 1.95872pt {u}_{3},\kern 1.95872pt {u}_{4}), using the free variables as the scalars.

x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ \ \cr \ \cr \ \cr \ \cr \ \cr \ \cr \ } \right ]+{x}_{2}\left [\array{ \ \cr \ \cr \ \cr \ \cr \ \cr \ \cr \ } \right ]+{x}_{5}\left [\array{ \ \cr \ \cr \ \cr \ \cr \ \cr \ \cr \ } \right ]+{x}_{6}\left [\array{ \ \cr \ \cr \ \cr \ \cr \ \cr \ \cr \ } \right ]+{x}_{7}\left [\array{ \ \cr \ \cr \ \cr \ \cr \ \cr \ \cr \ } \right ]

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

x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ \ \cr 0\cr \ \cr \ \cr 0\cr 0 \cr 0 } \right ]+{x}_{2}\left [\array{ \ \cr 1\cr \ \cr \ \cr 0\cr 0 \cr 0 } \right ]+{x}_{5}\left [\array{ \ \cr 0\cr \ \cr \ \cr 1\cr 0 \cr 0 } \right ]+{x}_{6}\left [\array{ \ \cr 0\cr \ \cr \ \cr 0\cr 1 \cr 0 } \right ]+{x}_{7}\left [\array{ \ \cr 0\cr \ \cr \ \cr 0\cr 0 \cr 1 } \right ]

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.

\eqalignno{ {x}_{1} & = 4 − 4{x}_{2} − 2{x}_{5} − 1{x}_{6} + 3{x}_{7}\quad ⇒ & & \cr x & = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ 4\cr 0\cr \ \cr \ \cr 0\cr 0 \cr 0 } \right ] + {x}_{2}\left [\array{ −4\cr 1\cr \ \cr \ \cr 0\cr 0 \cr 0 } \right ] + {x}_{5}\left [\array{ −2\cr 0\cr \ \cr \ \cr 1\cr 0 \cr 0 } \right ] + {x}_{6}\left [\array{ −1\cr 0\cr \ \cr \ \cr 0\cr 1 \cr 0 } \right ] + {x}_{7}\left [\array{ 3\cr 0\cr \ \cr \ \cr 0\cr 0 \cr 1 } \right ] & & \cr {x}_{3} & = 2 + 0{x}_{2} − {x}_{5} + 3{x}_{6} − 5{x}_{7}\quad ⇒ & & \cr x & = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ 4\cr 0 \cr 2\cr \ \cr 0 \cr 0\cr 0 } \right ] + {x}_{2}\left [\array{ −4\cr 1 \cr 0\cr \ \cr 0 \cr 0\cr 0 } \right ] + {x}_{5}\left [\array{ −2\cr 0 \cr −1\cr \ \cr 1 \cr 0\cr 0 } \right ] + {x}_{6}\left [\array{ −1\cr 0 \cr 3\cr \ \cr 0 \cr 1\cr 0 } \right ] + {x}_{7}\left [\array{ 3\cr 0 \cr −5\cr \ \cr 0 \cr 0\cr 1 } \right ] & & \cr {x}_{4} & = 1 + 0{x}_{2} − 2{x}_{5} + 6{x}_{6} − 6{x}_{7}\quad ⇒ & & \cr x & = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} \cr {x}_{6} \cr {x}_{7} } \right ] = \left [\array{ 4\cr 0 \cr 2\cr 1 \cr 0\cr 0 \cr 0 } \right ] + {x}_{2}\left [\array{ −4\cr 1 \cr 0\cr 0 \cr 0\cr 0 \cr 0 } \right ] + {x}_{5}\left [\array{ −2\cr 0 \cr −1\cr −2 \cr 1\cr 0 \cr 0 } \right ] + {x}_{6}\left [\array{ −1\cr 0 \cr 3\cr 6 \cr 0\cr 1 \cr 0 } \right ] + {x}_{7}\left [\array{ 3\cr 0 \cr −5\cr −6 \cr 0\cr 0 \cr 1 } \right ] & & \cr & & }

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 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’s 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’ll do one more example. However, an important distinction will be that this system is homogeneous.

Example VFSAL
Vector form of solutions for Archetype L
Archetype L is presented simply as the 5 × 5 matrix

L = \left [\array{ −2&−1&−2&−4& 4\cr −6 &−5 &−4 &−4 & 6 \cr 10& 7 & 7 &10&−13\cr −7 &−5 &−6 &−9 & 10 \cr −4&−3&−4&−6& 6\cr } \right ]

We’ll interpret it here as the coefficient matrix of a homogeneous system and reference this matrix as L. So we are solving the homogeneous system ℒS\kern -1.95872pt \left (L,\kern 1.95872pt 0\right ) 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

\left [\array{ \text{1}&0&0& 1 &−2\cr 0&\text{1 } &0 &−2 & 2 \cr 0&0&\text{1}& 2 &−1\cr 0&0 &0 & 0 & 0 \cr 0&0&0& 0 & 0 } \right ]

and we see r = 3 nonzero rows. The columns with leading 1’s are D = \{1,\kern 1.95872pt 2,\kern 1.95872pt 3\} so the r dependent variables are {x}_{1},\kern 1.95872pt {x}_{2},\kern 1.95872pt {x}_{3}. The columns without leading 1’s are F = \{4,\kern 1.95872pt 5\}, so the n − r = 2 free variables are {x}_{4},\kern 1.95872pt {x}_{5}. 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, and subsequently would have been ignored when listing the free variables.

Step 1. Write the vector of variables (x) as a fixed vector (c), plus a linear combination of n − r = 2 vectors ({u}_{1},\kern 1.95872pt {u}_{2}), using the free variables as the scalars.

x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} } \right ] = \left [\array{ \ \cr \ \cr \ \cr \ \cr \ } \right ]+{x}_{4}\left [\array{ \ \cr \ \cr \ \cr \ \cr \ } \right ]+{x}_{5}\left [\array{ \ \cr \ \cr \ \cr \ \cr \ } \right ]

Step 2. For each free variable, use 0’s and 1’s to ensure equality for the corresponding entry of the 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.

x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} } \right ] = \left [\array{ \ \cr \ \cr \ \cr 0 \cr 0 } \right ]+{x}_{4}\left [\array{ \ \cr \ \cr \ \cr 1 \cr 0 } \right ]+{x}_{5}\left [\array{ \ \cr \ \cr \ \cr 0 \cr 1 } \right ]

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. Don’t 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.

\eqalignno{ {x}_{1} & = 0 − 1{x}_{4} + 2{x}_{5} & & ⇒ & &x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} } \right ] = \left [\array{ 0\cr \ \cr \ \cr 0 \cr 0 } \right ] + {x}_{4}\left [\array{ −1\cr \ \cr \ \cr 1 \cr 0 } \right ] + {x}_{5}\left [\array{ 2\cr \ \cr \ \cr 0 \cr 1 } \right ] & & & & & & \cr {x}_{2} & = 0 + 2{x}_{4} − 2{x}_{5} & & ⇒ & &x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} } \right ] = \left [\array{ 0\cr 0\cr \ \cr 0\cr 0 } \right ] + {x}_{4}\left [\array{ −1\cr 2\cr \ \cr 1\cr 0 } \right ] + {x}_{5}\left [\array{ 2\cr −2\cr \ \cr 0\cr 1 } \right ] & & & & & & \cr {x}_{3} & = 0 − 2{x}_{4} + 1{x}_{5} & & ⇒ & &x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} } \right ] = \left [\array{ 0\cr 0 \cr 0\cr 0 \cr 0 } \right ] + {x}_{4}\left [\array{ −1\cr 2 \cr −2\cr 1 \cr 0 } \right ] + {x}_{5}\left [\array{ 2\cr −2 \cr 1\cr 0 \cr 1 } \right ] & & & & & & }

The vector 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, and hence all the entries of c are zero. So we can write

x = \left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} } \right ] = 0+{x}_{4}\left [\array{ −1\cr 2 \cr −2\cr 1 \cr 0 } \right ]+{x}_{5}\left [\array{ 2\cr −2 \cr 1\cr 0 \cr 1 } \right ] = {x}_{4}\left [\array{ −1\cr 2 \cr −2\cr 1 \cr 0 } \right ]+{x}_{5}\left [\array{ 2\cr −2 \cr 1\cr 0 \cr 1 } \right ]

It will always happen that the solutions to a homogeneous system has c = 0 (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 {u}_{1} = \left [\array{ −1\cr 2 \cr −2\cr 1 \cr 0 } \right ]and {u}_{2} = \left [\array{ 2\cr −2 \cr 1\cr 0 \cr 1 } \right ], with no mention of any fixed vector entering into the linear combination.

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.

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 corresponding homogeneous system. This explains part of our interest in the null space, the set of all solutions to a homogeneous system.

Theorem PSPHS
Particular Solution Plus Homogeneous Solutions
Suppose that w is one solution to the linear system of equations ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ). Then y is a solution to ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) if and only if y = w + z for some vector z ∈N\kern -1.95872pt \left (A\right ).

Proof   Let {A}_{1},\kern 1.95872pt {A}_{2},\kern 1.95872pt {A}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {A}_{n} be the columns of the coefficient matrix A.

() Suppose y = w + z and z ∈N\kern -1.95872pt \left (A\right ). Then

\eqalignno{ b& ={ \left [w\right ]}_{1}{A}_{1} +{ \left [w\right ]}_{2}{A}_{2} +{ \left [w\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [w\right ]}_{n}{A}_{n} &&\text{@(a href="#theorem.SLSLC")Theorem SLSLC@(/a)} &&&& \cr & ={ \left [w\right ]}_{1}{A}_{1} +{ \left [w\right ]}_{2}{A}_{2} +{ \left [w\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [w\right ]}_{n}{A}_{n} + 0 &&\text{@(a href="fcla-jsmath-2.23li23.html#property.ZC")Property ZC@(/a)} &&&& \cr & ={ \left [w\right ]}_{1}{A}_{1} +{ \left [w\right ]}_{2}{A}_{2} +{ \left [w\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [w\right ]}_{n}{A}_{n} &&\text{@(a href="#theorem.SLSLC")Theorem SLSLC@(/a)} &&&& \cr &\quad \quad \quad \quad +{ \left [z\right ]}_{1}{A}_{1} +{ \left [z\right ]}_{2}{A}_{2} +{ \left [z\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [z\right ]}_{n}{A}_{n} && && \cr & = \left ({\left [w\right ]}_{1} +{ \left [z\right ]}_{1}\right ){A}_{1} + \left ({\left [w\right ]}_{2} +{ \left [z\right ]}_{2}\right ){A}_{2} + \mathrel{⋯} + \left ({\left [w\right ]}_{n} +{ \left [z\right ]}_{n}\right ){A}_{n} &&\text{@(a href="fcla-jsmath-2.23li23.html#theorem.VSPCV")Theorem VSPCV@(/a)}&&&& \cr & ={ \left [w + z\right ]}_{1}{A}_{1} +{ \left [w + z\right ]}_{2}{A}_{2} +{ \left [w + z\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [w + z\right ]}_{n}{A}_{n}&&\text{@(a href="fcla-jsmath-2.23li23.html#definition.CVA")Definition CVA@(/a)} &&&& \cr & ={ \left [y\right ]}_{1}{A}_{1} +{ \left [y\right ]}_{2}{A}_{2} +{ \left [y\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [y\right ]}_{n}{A}_{n} &&\text{Definition of $y$} &&&& }

Applying Theorem SLSLC we see that the vector y is a solution to ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ).

() Suppose y is a solution to ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ). Then

\eqalignno{ 0& = b − b &&\text{} &&&& \cr & ={ \left [y\right ]}_{1}{A}_{1} +{ \left [y\right ]}_{2}{A}_{2} +{ \left [y\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [y\right ]}_{n}{A}_{n} &&\text{@(a href="#theorem.SLSLC")Theorem SLSLC@(/a)} &&&& \cr &\quad \quad \quad \quad −\left ({\left [w\right ]}_{1}{A}_{1} +{ \left [w\right ]}_{2}{A}_{2} +{ \left [w\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [w\right ]}_{n}{A}_{n}\right ) && && \cr & = \left ({\left [y\right ]}_{1} −{\left [w\right ]}_{1}\right ){A}_{1} + \left ({\left [y\right ]}_{2} −{\left [w\right ]}_{2}\right ){A}_{2} + \mathrel{⋯} + \left ({\left [y\right ]}_{n} −{\left [w\right ]}_{n}\right ){A}_{n} &&\text{@(a href="fcla-jsmath-2.23li23.html#theorem.VSPCV")Theorem VSPCV@(/a)}&&&& \cr & ={ \left [y − w\right ]}_{1}{A}_{1} +{ \left [y − w\right ]}_{2}{A}_{2} +{ \left [y − w\right ]}_{3}{A}_{3} + \mathrel{⋯} +{ \left [y − w\right ]}_{n}{A}_{n}&&\text{@(a href="fcla-jsmath-2.23li23.html#definition.CVA")Definition CVA@(/a)} &&&& }

By Theorem SLSLC we see that the vector y − w is a solution to the homogeneous system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt 0\right ) and by Definition NSM, y − w ∈N\kern -1.95872pt \left (A\right ). In other words, y − w = z for some vector z ∈N\kern -1.95872pt \left (A\right ). Rewritten, this is y = w + z, 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, b, the system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) could be inconsistent, meaning there are no solutions. But if there is at least one solution (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. Either there are no solutions, or infinitely many solutions, depending on the choice of the vector of constants (b).

Example PSHS
Particular solutions, homogeneous solutions, Archetype D
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,

\eqalignno{ {y}_{1} = \left [\array{ 0\cr 1 \cr 2\cr 1 } \right ] & &{y}_{2} = \left [\array{ 4\cr 0 \cr 0\cr 0 } \right ] & &{y}_{3} = \left [\array{ 7\cr 8 \cr 1\cr 3 } \right ] & & & & & & }

We will choose to have {y}_{1} play the role of w in the statement of Theorem PSPHS, 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 w plus a solution to the corresponding homogeneous system of equations. Since 0 is always a solution to a homogeneous system we can easily write

{y}_{1} = w = w + 0.

The vectors {y}_{2} and {y}_{3} will require a bit more effort. Solutions to the homogeneous system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt 0\right ) are exactly the elements of the null space of the coefficient matrix, which by an application of Theorem VFSLS is

N\kern -1.95872pt \left (A\right ) = \left \{\left .{x}_{3}\left [\array{ −3\cr −1 \cr 1\cr 0 } \right ] + {x}_{4}\left [\array{ 2\cr 3 \cr 0\cr 1 } \right ]\right \vert {x}_{3},\kern 1.95872pt {x}_{4} ∈ {ℂ}^{}\right \}

Then

{ y}_{2} = \left [\array{ 4\cr 0 \cr 0\cr 0 } \right ] = \left [\array{ 0\cr 1 \cr 2\cr 1 } \right ]+\left [\array{ 4\cr −1 \cr −2\cr −1 } \right ] = \left [\array{ 0\cr 1 \cr 2\cr 1 } \right ]+\left ((−2)\left [\array{ −3\cr −1 \cr 1\cr 0 } \right ] + (−1)\left [\array{ 2\cr 3 \cr 0\cr 1 } \right ]\right ) = w+{z}_{2}

where

{ z}_{2} = \left [\array{ 4\cr −1 \cr −2\cr −1 } \right ] = (−2)\left [\array{ −3\cr −1 \cr 1\cr 0 } \right ]+(−1)\left [\array{ 2\cr 3 \cr 0\cr 1 } \right ]

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 {z}_{2}).

Again

{ y}_{3} = \left [\array{ 7\cr 8 \cr 1\cr 3 } \right ] = \left [\array{ 0\cr 1 \cr 2\cr 1 } \right ]+\left [\array{ 7\cr 7 \cr −1\cr 2 } \right ] = \left [\array{ 0\cr 1 \cr 2\cr 1 } \right ]+\left ((−1)\left [\array{ −3\cr −1 \cr 1\cr 0 } \right ] + 2\left [\array{ 2\cr 3 \cr 0\cr 1 } \right ]\right ) = w+{z}_{3}

where

{ z}_{3} = \left [\array{ 7\cr 7 \cr −1\cr 2 } \right ] = (−1)\left [\array{ −3\cr −1 \cr 1\cr 0 } \right ]+2\left [\array{ 2\cr 3 \cr 0\cr 1 } \right ]

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 {z}_{2}).

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

\eqalignno{ {y}_{4} = \left [\array{ 11\cr 0 \cr −3\cr −1 } \right ] & &{y}_{5} = \left [\array{ −4\cr 2 \cr 4\cr 2 } \right ] & & & & }

and form their difference,

u = \left [\array{ 11\cr 0 \cr −3\cr −1 } \right ]−\left [\array{ −4\cr 2 \cr 4\cr 2 } \right ] = \left [\array{ 15\cr −2 \cr −7\cr −3 } \right ].

It is no accident that 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 pre-images of linear transformations (Definition PI).

Subsection READ: Reading Questions

  1. Earlier, a reading question asked you to solve the system of equations
    \eqalignno{ 2{x}_{1} + 3{x}_{2} − {x}_{3} & = 0 & & \cr {x}_{1} + 2{x}_{2} + {x}_{3} & = 3 & & \cr {x}_{1} + 3{x}_{2} + 3{x}_{3} & = 7 & & }

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

  2. Find a linear combination of the vectors
    S = \left \{\left [\array{ 1\cr 3 \cr −1} \right ],\kern 1.95872pt \left [\array{ 2\cr 0 \cr 4} \right ],\kern 1.95872pt \left [\array{ −1\cr 3 \cr −5} \right ]\right \}

    that equals the vector \left [\array{ 1\cr −9 \cr 11} \right ].

  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.
    \left [\array{ \text{1}&3&0& 6 &0& 9\cr 0&0 &\text{1 } &−2 &0 &−8 \cr 0&0&0& 0 &\text{1}& 3} \right ]

Subsection EXC: 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

 
Contributed by Robert Beezer Solution [336]

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

 
Contributed by Robert Beezer Solution [336]

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

\eqalignno{ 2{x}_{1} − 4{x}_{2} + 3{x}_{3} + {x}_{5} & = 6 & & \cr {x}_{1} − 2{x}_{2} − 2{x}_{3} + 14{x}_{4} − 4{x}_{5} & = 15 & & \cr {x}_{1} − 2{x}_{2} + {x}_{3} + 2{x}_{4} + {x}_{5} & = −1 & & \cr − 2{x}_{1} + 4{x}_{2} − 12{x}_{4} + {x}_{5} & = −7 & & }

 
Contributed by Robert Beezer Solution [336]

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

\eqalignno{ − 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 & & \cr 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 & & \cr 4{x}_{1} − 2{x}_{2} + 8{x}_{3} + 2{x}_{5} − 14{x}_{6} − 2{x}_{8} + 2{x}_{9} & = 36 & & \cr − 1{x}_{1} + 2{x}_{2} + 1{x}_{3} − 6{x}_{4} + 7{x}_{6} − 1{x}_{7} − 3{x}_{9} & = −8 & & \cr 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 & & \cr − 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 & & }

 
Contributed by Robert Beezer Solution [337]

M10 Example TLC asks if the vector

w = \left [\array{ 13\cr 15 \cr 5\cr −17 \cr 2\cr 25} \right ]

can be written as a linear combination of the four vectors

\eqalignno{ {u}_{1} & = \left [\array{ 2\cr 4 \cr −3\cr 1 \cr 2\cr 9 } \right ] &{u}_{2} & = \left [\array{ 6\cr 3 \cr 0\cr −2 \cr 1\cr 4 } \right ] &{u}_{3} & = \left [\array{ −5\cr 2 \cr 1\cr 1 \cr −3\cr 0 } \right ] &{u}_{4} & = \left [\array{ 3\cr 2 \cr −5\cr 7 \cr 1\cr 3 } \right ] & & & & & & & & }

Can it? Can any vector in {ℂ}^{6} be written as a linear combination of the four vectors {u}_{1},\kern 1.95872pt {u}_{2},\kern 1.95872pt {u}_{3},\kern 1.95872pt {u}_{4}?  
Contributed by Robert Beezer Solution [338]

M11 At the end of Example VFS, the vector w is claimed to be a solution to the linear system under discussion. Verify that w really is a solution. Then determine the four scalars that express w as a linear combination of c, {u}_{1}, {u}_{2}, {u}_{3}.  
Contributed by Robert Beezer Solution [338]

Subsection SOL: Solutions

C21 Contributed by Robert Beezer Statement [332]
Solutions for Archetype A and Archetype B are described carefully in Example AALC and Example ABLC.

C22 Contributed by Robert Beezer Statement [332]
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 Contributed by Robert Beezer Statement [333]
Row-reduce the augmented matrix representing this system, to find

\left [\array{ \text{1}&−2&0& 6 &0& 1\cr 0& 0 &\text{1 } &−4 &0 & 3 \cr 0& 0 &0& 0 &\text{1}&−5\cr 0& 0 &0 & 0 &0 & 0 } \right ]

The system is consistent (no leading one 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

\left [\array{ {x}_{1} \cr {x}_{2} \cr {x}_{3} \cr {x}_{4} \cr {x}_{5} } \right ] = \left [\array{ 1\cr 0 \cr 3\cr 0 \cr −5 } \right ]+{x}_{2}\left [\array{ 2\cr 1 \cr 0\cr 0 \cr 0 } \right ]+{x}_{4}\left [\array{ −6\cr 0 \cr 4\cr 1 \cr 0 } \right ]

C41 Contributed by Robert Beezer Statement [333]
Row-reduce the augmented matrix representing this system, to find

\left [\array{ \text{1}&0&3&−2&0&−1&0&0& 3 & 6\cr 0&\text{1 } &2 &−4 &0 & 3 &0 &0 & 2 &−1 \cr 0&0&0& 0 &\text{1}&−2&0&0&−1& 3\cr 0&0 &0 & 0 &0 & 0 &\text{1 } &0 & 4 & 0 \cr 0&0&0& 0 &0& 0 &0&\text{1}& 2 &−2\cr 0&0 &0 & 0 &0 & 0 &0 &0 & 0 & 0 } \right ]

The system is consistent (no leading one in column 10, Theorem RCLS). F = \left \{3,\kern 1.95872pt 4,\kern 1.95872pt 6,\kern 1.95872pt 9,\kern 1.95872pt 10\right \}, so the free variables are {x}_{3},\kern 1.95872pt {x}_{4},\kern 1.95872pt {x}_{6} and {x}_{9}. 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

S = \left \{\left .\left [\array{ 6\cr −1 \cr 0\cr 0 \cr 3\cr 0 \cr 0\cr −2 \cr 0 } \right ] + {x}_{3}\left [\array{ −3\cr −2 \cr 1\cr 0 \cr 0\cr 0 \cr 0\cr 0 \cr 0 } \right ] + {x}_{4}\left [\array{ 2\cr 4 \cr 0\cr 1 \cr 0\cr 0 \cr 0\cr 0 \cr 0 } \right ] + {x}_{6}\left [\array{ 1\cr −3 \cr 0\cr 0 \cr 2\cr 1 \cr 0\cr 0 \cr 0 } \right ] + {x}_{9}\left [\array{ −3\cr −2 \cr 0\cr 0 \cr 1\cr 0 \cr −4\cr −2 \cr 1 } \right ]\right \vert {x}_{3},\kern 1.95872pt {x}_{4},\kern 1.95872pt {x}_{6},\kern 1.95872pt {x}_{9} ∈ {ℂ}^{}\right \}

M10 Contributed by Robert Beezer Statement [334]
No, it is not possible to create w as a linear combination of the four vectors {u}_{1},\kern 1.95872pt {u}_{2},\kern 1.95872pt {u}_{3},\kern 1.95872pt {u}_{4}. 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 {ℂ}^{6} through linear combinations of the four vectors {u}_{1},\kern 1.95872pt {u}_{2},\kern 1.95872pt {u}_{3},\kern 1.95872pt {u}_{4}.

M11 Contributed by Robert Beezer Statement [335]
The coefficient of c is 1. The coefficients of {u}_{1}, {u}_{2}, {u}_{3} lie in the third, fourth and seventh entries of w. Can you see why? (Hint: F = \left \{3,\kern 1.95872pt 4,\kern 1.95872pt 7,\kern 1.95872pt 8\right \}, so the free variables are {x}_{3},\kern 1.95872pt {x}_{4} and {x}_{7}.)