Linear Algebra/Describing the Solution Set

Linear Algebra
 ← Gauss' Method Describing the Solution Set General = Particular + Homogeneous → 

A linear system with a unique solution has a solution set with one element. A linear system with no solution has a solution set that is empty. In these cases the solution set is easy to describe. Solution sets are a challenge to describe only when they contain many elements.

Example 2.1

This system has many solutions because in echelon form

not all of the variables are leading variables. The Gauss' method theorem showed that a triple satisfies the first system if and only if it satisfies the third. Thus, the solution set can also be described as . However, this second description is not much of an improvement. It has two equations instead of three, but it still involves some hard-to-understand interaction among the variables.

To get a description that is free of any such interaction, we take the variable that does not lead any equation, , and use it to describe the variables that do lead, and . The second equation gives and the first equation gives . Thus, the solution set can be described as . For instance, is a solution because taking gives a first component of and a second component of .

The advantage of this description over the ones above is that the only variable appearing, , is unrestricted — it can be any real number.

Definition 2.2

The non-leading variables in an echelon-form linear system are free variables.

In the echelon form system derived in the above example, and are leading variables and is free.

Example 2.3

A linear system can end with more than one variable free. This row reduction

ends with and leading, and with both and free. To get the description that we prefer we will start at the bottom. We first express in terms of the free variables and with . Next, moving up to the top equation, substituting for in the first equation and solving for yields . Thus, the solution set is .

We prefer this description because the only variables that appear, and , are unrestricted. This makes the job of deciding which four-tuples are system solutions into an easy one. For instance, taking and gives the solution . In contrast, is not a solution, since the first component of any solution must be minus twice the third component plus twice the fourth.

Example 2.4

After this reduction

lead, are free. The solution set is . For instance, satisfies the system — take and . The four-tuple is not a solution since its first coordinate does not equal its second.

We refer to a variable used to describe a family of solutions as a parameter and we say that the set above is parametrized with and . (The terms "parameter" and "free variable" do not mean the same thing. Above, and are free because in the echelon form system they do not lead any row. They are parameters because they are used in the solution set description. We could have instead parametrized with and by rewriting the second equation as . In that case, the free variables are still and , but the parameters are and . Notice that we could not have parametrized with and , so there is sometimes a restriction on the choice of parameters. The terms "parameter" and "free" are related because, as we shall show later in this chapter, the solution set of a system can always be parametrized with the free variables. Consequently, we shall parametrize all of our descriptions in this way.)

Example 2.5

This is another system with infinitely many solutions.

The leading variables are . The variable is free. (Notice here that, although there are infinitely many solutions, the value of one of the variables is fixed — .) Write in terms of with . Then . To express in terms of , substitute for into the first equation to get . The solution set is .

We finish this subsection by developing the notation for linear systems and their solution sets that we shall use in the rest of this book.

Definition 2.6

An matrix is a rectangular array of numbers with rows and columns. Each number in the matrix is an entry.

Matrices are usually named by upper case roman letters, e.g. . Each entry is denoted by the corresponding lower-case letter, e.g. is the number in row and column of the array. For instance,

has two rows and three columns, and so is a matrix. (Read that "two-by-three"; the number of rows is always stated first.) The entry in the second row and first column is . Note that the order of the subscripts matters: since . (The parentheses around the array are a typographic device so that when two matrices are side by side we can tell where one ends and the other starts.)

Matrices occur throughout this book. We shall use to denote the collection of matrices.

Example 2.7

We can abbreviate this linear system

with this matrix.

The vertical bar just reminds a reader of the difference between the coefficients on the systems's left hand side and the constants on the right. When a bar is used to divide a matrix into parts, we call it an augmented matrix. In this notation, Gauss' method goes this way.

The second row stands for and the first row stands for so the solution set is . One advantage of the new notation is that the clerical load of Gauss' method — the copying of variables, the writing of 's and 's, etc. — is lighter.

We will also use the array notation to clarify the descriptions of solution sets. A description like from Example 2.3 is hard to read. We will rewrite it to group all the constants together, all the coefficients of together, and all the coefficients of together. We will write them vertically, in one-column wide matrices.

For instance, the top line says that . The next section gives a geometric interpretation that will help us picture the solution sets when they are written in this way.

Definition 2.8

A vector (or column vector) is a matrix with a single column. A matrix with a single row is a row vector. The entries of a vector are its components.

Vectors are an exception to the convention of representing matrices with capital roman letters. We use lower-case roman or greek letters overlined with an arrow: ... or ... (boldface is also common: or ). For instance, this is a column vector with a third component of .

Definition 2.9

The linear equation with unknowns is satisfied by

if . A vector satisfies a linear system if it satisfies each equation in the system.

The style of description of solution sets that we use involves adding the vectors, and also multiplying them by real numbers, such as the and . We need to define these operations.

Definition 2.10

The vector sum of and is this.

In general, two matrices with the same number of rows and the same number of columns add in this way, entry-by-entry.

Definition 2.11

The scalar multiplication of the real number and the vector is this.

In general, any matrix is multiplied by a real number in this entry-by-entry way.

Scalar multiplication can be written in either order: or , or without the "" symbol: . (Do not refer to scalar multiplication as "scalar product" because that name is used for a different operation.)

Example 2.12

Notice that the definitions of vector addition and scalar multiplication agree where they overlap, for instance, .

With the notation defined, we can now solve systems in the way that we will use throughout this book.

Example 2.13

This system

reduces in this way.

The solution set is . We write that in vector form.

Note again how well vector notation sets off the coefficients of each parameter. For instance, the third row of the vector form shows plainly that if is held fixed then increases three times as fast as .

That format also shows plainly that there are infinitely many solutions. For example, we can fix as , let range over the real numbers, and consider the first component . We get infinitely many first components and hence infinitely many solutions.

Another thing shown plainly is that setting both to 0 gives that this

is a particular solution of the linear system.

Example 2.14

In the same way, this system


to a one-parameter solution set.

Before the exercises, we pause to point out some things that we have yet to do.

The first two subsections have been on the mechanics of Gauss' method. Except for one result, Theorem 1.4— without which developing the method doesn't make sense since it says that the method gives the right answers— we have not stopped to consider any of the interesting questions that arise.

For example, can we always describe solution sets as above, with a particular solution vector added to an unrestricted linear combination of some other vectors? The solution sets we described with unrestricted parameters were easily seen to have infinitely many solutions so an answer to this question could tell us something about the size of solution sets. An answer to that question could also help us picture the solution sets, in , or in , etc.

Many questions arise from the observation that Gauss' method can be done in more than one way (for instance, when swapping rows, we may have a choice of which row to swap with). Theorem 1.4 says that we must get the same solution set no matter how we proceed, but if we do Gauss' method in two different ways must we get the same number of free variables both times, so that any two solution set descriptions have the same number of parameters? Must those be the same variables (e.g., is it impossible to solve a problem one way and get and free or solve it another way and get and free)?

In the rest of this chapter we answer these questions. The answer to each is "yes". The first question is answered in the last subsection of this section. In the second section we give a geometric description of solution sets. In the final section of this chapter we tackle the last set of questions. Consequently, by the end of the first chapter we will not only have a solid grounding in the practice of Gauss' method, we will also have a solid grounding in the theory. We will be sure of what can and cannot happen in a reduction.


This exercise is recommended for all readers.
Problem 1

Find the indicated entry of the matrix, if it is defined.

This exercise is recommended for all readers.
Problem 2

Give the size of each matrix.

This exercise is recommended for all readers.
Problem 3

Do the indicated vector operation, if it is defined.

This exercise is recommended for all readers.
Problem 4

Solve each system using matrix notation. Express the solution using vectors.

This exercise is recommended for all readers.
Problem 5

Solve each system using matrix notation. Give each solution set in vector notation.

This exercise is recommended for all readers.
Problem 6

The vector is in the set. What value of the parameters produces that vector?

  1.  ,  
  2.  ,  
  3.  ,  
Problem 7

Decide if the vector is in the set.

  1.  ,  
  2.  ,  
  3.  ,  
  4.  ,  
Problem 8

Parametrize the solution set of this one-equation system.

This exercise is recommended for all readers.
Problem 9
  1. Apply Gauss' method to the left-hand side to solve
    for  ,  ,  , and  , in terms of the constants  ,  , and  . Note that   will be a free variable.
  2. Use your answer from the prior part to solve this.
This exercise is recommended for all readers.
Problem 10

Why is the comma needed in the notation " " for matrix entries?

This exercise is recommended for all readers.
Problem 11

Give the   matrix whose  -th entry is

  1.  ;
  2.   to the   power.
Problem 12

For any matrix  , the transpose of  , written  , is the matrix whose columns are the rows of  . Find the transpose of each of these.

This exercise is recommended for all readers.
Problem 13
  1. Describe all functions   such that   and  .
  2. Describe all functions   such that  .
Problem 14

Show that any set of five points from the plane   lie on a common conic section, that is, they all satisfy some equation of the form   where some of   are nonzero.

Problem 15

Make up a four equations/four unknowns system having

  1. a one-parameter solution set;
  2. a two-parameter solution set;
  3. a three-parameter solution set.
? Problem 16
  1. Solve the system of equations.
    For what values of   does the system fail to have solutions, and for what values of   are there infinitely many solutions?
  2. Answer the above question for the system.

(USSR Olympiad #174)

? Problem 17

In air a gold-surfaced sphere weighs   grams. It is known that it may contain one or more of the metals aluminum, copper, silver, or lead. When weighed successively under standard conditions in water, benzene, alcohol, and glycerine its respective weights are  ,  ,  , and   grams. How much, if any, of the forenamed metals does it contain if the specific gravities of the designated substances are taken to be as follows?

Aluminum 2.7 Alcohol 0.81
Copper 8.9 Benzene 0.90
Gold 19.3 Glycerine 1.26
Lead 11.3 Water 1.00
Silver 10.8

(Duncan & Quelch 1952)



  • The USSR Mathematics Olympiad, number 174.
  • Duncan, Dewey (proposer); Quelch, W. H. (solver) (1952), Mathematics Magazine, 26 (1): 48 {{citation}}: Missing or empty |title= (help); Unknown parameter |month= ignored (help)
Linear Algebra
 ← Gauss' Method Describing the Solution Set General = Particular + Homogeneous →