Linear Algebra/Describing the Solution Set

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.

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

Template:Anchor 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 $y$ and $w$ . (The terms "parameter" and "free variable" do not mean the same thing. Above, $y$ and $w$ 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 $y$ and $z$ by rewriting the second equation as $w=\frac{2}{3}-\frac{1}{3}z$ . In that case, the free variables are still $y$ and $w$ , but the parameters are $y$ and $z$ . Notice that we could not have parametrized with $x$ and $y$ , 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.)

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.

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

$A=\left(\begin{array}{ccc}1& 2.2& 5\\ 3& 4& -7\end{array}\right)$

has two rows and three columns, and so is a $2\times 3$ matrix. (Read that "two-by-three"; the number of rows is always stated first.) The entry in the second row and first column is $a_{2,1}=3$ . Note that the order of the subscripts matters: $a_{1,2}\ne a_{2,1}$ since $a_{1,2}=2.2$ . (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 ${ℳ}_{n\times m}$ to denote the collection of $n\times m$ matrices.

We will also use the array notation to clarify the descriptions of solution sets. A description like $\{(2-2z+2w,-1+z-w,z,w)|z,w\in ℝ\}$ from Example 2.3 is hard to read. We will rewrite it to group all the constants together, all the coefficients of $z$ together, and all the coefficients of $w$ together. We will write them vertically, in one-column wide matrices.

$\{\left(\begin{array}{c}2\\ -1\\ 0\\ 0\end{array}\right)+\left(\begin{array}{c}-2\\ 1\\ 1\\ 0\end{array}\right)z+\left(\begin{array}{c}2\\ -1\\ 0\\ 1\end{array}\right)w|z,w\in ℝ\}$

For instance, the top line says that $x=2-2z+2w$ . The next section gives a geometric interpretation that will help us picture the solution sets when they are written in this way.

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: $\overrightarrow{a},\overrightarrow{b}$ ... or $\overrightarrow{\alpha },\overrightarrow{\beta }$ ... (boldface is also common: $𝐚$ or $\mathit{\alpha }$). For instance, this is a column vector with a third component of $7$ .

$\overrightarrow{v}=\left(\begin{array}{c}1\\ 3\\ 7\end{array}\right)$

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

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

Notice that the definitions of vector addition and scalar multiplication agree where they overlap, for instance, $\overrightarrow{v}+\overrightarrow{v}=2\overrightarrow{v}$ .

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

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 ${ℝ}^2$, or in ${ℝ}^3$, 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 $y$ and $w$ free or solve it another way and get $y$ and $z$ 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.

Exercises

/Solutions/

References

• Template:Anchor The USSR Mathematics Olympiad, number 174.
• Template:Citation