# Linear Algebra/Describing the Solution Set

|current=Describing the Solution Set
|previous=Gauss' Method

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.

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=\frac23-\frac13z$ . 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=\begin{pmatrix}1&2.2&5\\3&4&-7\end{pmatrix}$$

has two rows and three columns, and so is a $2\times3$ 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
$\mathcal{M}_{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)\big|z,w\in\R\}$ 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{pmatrix}2\\-1\\0\\0\end{pmatrix}+\begin{pmatrix}-2\\1\\1\\0\end{pmatrix}z+\begin{pmatrix}2\\-1\\0\\1\end{pmatrix}w\Bigg|z,w\in\R\right\}$$

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

$$\vec v=\begin{pmatrix}1\\3\\7\end{pmatrix}$$

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\vec v$ or
$\vec v\cdot r$ , or without the \"$\cdot$\" symbol: $r\vec 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, $\vec v+\vec v=2\vec 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 $\mathbb{R}^2$, or in $\mathbb{R}^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


## References

-       *The USSR Mathematics Olympiad*, number 174.

-   
