# Linear Algebra/General = Particular + Homogeneous

|current=General = Particular + Homogeneous
|previous=Describing the Solution Set

## Description of Solution Sets

The prior subsection has many descriptions of solution sets. They all
fit a pattern. They have a vector that is a particular solution of the
system added to an unrestricted combination of some other vectors. The
solution set from Example
2.13
illustrates.

$$\left\{
\underbrace{
\begin{pmatrix} 0 \\ 4 \\ 0 \\ 0 \\ 0 \end{pmatrix}}_{\begin{array}{c}\\[-19pt]\scriptstyle\text{particular} \\[-5pt]\scriptstyle\text{solution}\end{array}}+
\underbrace{w\begin{pmatrix} 1 \\ -1 \\ 3 \\ 1 \\ 0 \end{pmatrix}+
u\begin{pmatrix} 1/2 \\ -1 \\ 1/2 \\ 0 \\ 1 \end{pmatrix}}_{\begin{array}{c}\\[-19pt]\scriptstyle\text{unrestricted}\\[-5pt]\scriptstyle\text{combination}\end{array}}
\,\big|\, w,u\in\mathbb{R}\right\}$$

The combination is unrestricted in that $w$ and $u$ can be any real
numbers--- there is no condition like \"such that $2w-u=0$\" that would
restrict which pairs $w,u$ can be used to form combinations.

That example shows an infinite solution set conforming to the pattern.
We can think of the other two kinds of solution sets as also fitting the
same pattern. A one-element solution set fits in that it has a
particular solution, and the unrestricted combination part is a trivial
sum (that is, instead of being a combination of two vectors, as above,
or a combination of one vector, it is a combination of no vectors). A
zero-element solution set fits the pattern since there is no particular
solution, and so the set of sums of that form is empty.

We will show that the examples from the prior subsection are
representative, in that the description pattern discussed above holds
for every solution set.

This description has two parts, the particular solution $\vec{p}$ and
also the unrestricted linear combination of the $\vec{\beta}$\'s. We
shall prove the theorem in two corresponding parts, with two lemmas.

## Homogeneous Systems

We will focus first on the unrestricted combination part. To do that, we
consider systems that have the vector of zeroes as one of the particular
solutions, so that $\vec{p}+c_1\vec{\beta}_1+\dots+c_k\vec{\beta}_k$ can
be shortened to $c_1\vec{\beta}_1+\dots+c_k\vec{\beta}_k$.

(These are \"homogeneous\" because all of the terms involve the same
power of their variable--- the first power--- including a \"$0x_{0}$\"
that we can imagine is on the right side.)

Studying the associated homogeneous system has a great advantage over
studying the original system. Nonhomogeneous systems can be
inconsistent. But a homogeneous system must be consistent since there is
always at least one solution, the vector of zeros.

There are many different zero vectors, e.g., the one-tall zero vector,
the two-tall zero vector, etc. Nonetheless, people often refer to
\"the\" zero vector, expecting that the size of the one being discussed
will be clear from the context.

We now have the terminology to prove the two parts of Theorem
3.1 . The first lemma deals with
unrestricted combinations.

Before the proof, we will recall the back substitution calculations that
were done in the prior subsection.

Imagine that we have brought a system to this echelon form.

$$\begin{array}{*{4}{rc}r}
x  &+  &2y  &-  &z  &+  &2w &=  &0  \\
&   &-3y &+  &z  &   &   &=  &0  \\
&   &    &   &   &   &-w &=  &0
\end{array}$$

We next perform back-substitution to express each variable in terms of
the free variable $z$. Working from the bottom up, we get first that $w$
is $0\cdot z$, next that $y$ is $(1/3)\cdot z$, and then substituting
those two into the top equation $x+2((1/3)z)-z+2(0)=0$ gives
$x=(1/3)\cdot z$. So, back substitution gives a parametrization of the
solution set by starting at the bottom equation and using the free
variables as the parameters to work row-by-row to the top. The proof
below follows this pattern.

*Comment:* That is, this proof just does a verification of the
bookkeeping in back substitution to show that we haven\'t overlooked any
obscure cases where this procedure fails, say, by leading to a division
by zero. So this argument, while quite detailed, doesn\'t give us any
new insights. Nevertheless, we have written it out for two reasons. The
first reason is that we need the result--- the computational procedure
that we employ must be verified to work as promised.
The second reason is that the
row-by-row nature of back substitution leads to a proof that uses the
technique of mathematical induction.[^1] This is an important, and
non-obvious, proof technique that we shall use a number of times in this
book. Doing an induction argument here gives us a chance to see one in a
setting where the proof material is easy to follow, and so the technique
can be studied. Readers who are unfamiliar with induction arguments
should be sure to master this one and the ones later in this chapter
before going on to the second chapter.

`</math>`{=html} and substitute its expression in terms of free
variables. The result has the form

$$a_{m-(t+1),\ell_{m-(t+1)}}x_{\ell_{m-(t+1)}}+
\text{sums of multiples of free variables}=0$$

where $a_{m-(t+1),\ell_{m-(t+1)}}\neq 0$. We move the free variables to
the right-hand side and divide by $a_{m-(t+1),\ell_{m-(t+1)}}$, to end
with $x_{\ell_{m-(t+1)}}$ expressed in terms of free variables.

Because we have shown both the base step and the inductive step, by the
principle of mathematical induction the proposition is true. }}

We say that the set
$\{c_1\vec{\beta}_1+\cdots+c_k\vec{\beta}_k \,\big|\, c_1,\ldots,c_k\in\mathbb{R}\}$
is **generated by** or **spanned by** the set of vectors
$\{{\vec{\beta}_1},\ldots,{\vec{\beta}_k}\}$. There is a tricky point to
this definition. If a homogeneous system has a unique solution, the zero
vector, then we say the solution set is generated by the empty set of
vectors. This fits with the pattern of the other solution sets: in the
proof above the solution set is derived by taking the $c$\'s to be the
free variables and if there is a unique solution then there are no free
variables.

This proof incidentally shows, as discussed after Example
2.4
, that solution sets can always be parametrized using the free
variables.

## Nonhomogeneous Systems

The next lemma finishes the proof of Theorem
3.1 by considering the particular
solution part of the solution set\'s description.

The two lemmas above together establish Theorem
3.1 . We remember that theorem with
the slogan
\"$\text{General} = \text{Particular} + \text{Homogeneous}$\".

This table summarizes the factors affecting the size of a general
solution.

+---------------+-----------+---------------------------------+-------------------+
|               |           | *number of solutions of the*\   |                   |
|               |           | *associated homogeneous system* |                   |
+---------------+-----------+---------------------------------+-------------------+
|               |           | *one*                           | *infinitely many* |
+---------------+-----------+---------------------------------+-------------------+
| *particular*\ | *yes*     | unique\                         | infinitely many\  |
| *solution*\   |           | solution                        | solutions         |
| *exists?*     |           |                                 |                   |
+---------------+-----------+---------------------------------+-------------------+
| *no*          | no\       | no\                             |                   |
|               | solutions | solutions                       |                   |
+---------------+-----------+---------------------------------+-------------------+

The factor on the top of the table is the simpler one. When we perform
Gauss\' method on a linear system, ignoring the constants on the right
side and so paying attention only to the coefficients on the left-hand
side, we either end with every variable leading some row or else we find
that some variable does not lead a row, that is, that some variable is
free. (Of course, \"ignoring the constants on the right\" is formalized
by considering the associated homogeneous system. We are simply putting
aside for the moment the possibility of a contradictory equation.)

A nice insight into the factor on the top of this table at work comes
from considering the case of a system having the same number of
equations as variables. This system will have a solution, and the
solution will be unique, if and only if it reduces to an echelon form
system where every variable leads its row, which will happen if and only
if the associated homogeneous system has a unique solution. Thus, the
question of uniqueness of solution is especially interesting when the
system has the same number of equations as variables.

The above table has two factors. We have already considered the factor
along the top: we can tell which column a given linear system goes in
solely by considering the system\'s left-hand side--- the constants on
the right-hand side play no role in this factor. The table\'s other
factor, determining whether a particular solution exists, is tougher.
Consider these two

$$\begin{array}{*{2}{rc}r}
3x &+ &2y &= &5  \\
3x &+ &2y &= &5
\end{array}
\qquad
\begin{array}{*{2}{rc}r}
3x &+ &2y &= &5  \\
3x &+ &2y &= &4
\end{array}$$

with the same left sides but different right sides. Obviously, the first
has a solution while the second does not, so here the constants on the
right side decide if the system has a solution. We could conjecture that
the left side of a linear system determines the number of solutions
while the right side determines if solutions exist, but that guess is
not correct. Compare these two systems

$$\begin{array}{*{2}{rc}r}
3x &+ &2y &= &5  \\
4x &+ &2y &= &4
\end{array}
\qquad
\begin{array}{*{2}{rc}r}
3x &+ &2y &= &5  \\
3x &+ &2y &= &4
\end{array}$$

with the same right sides but different left sides. The first has a
solution but the second does not. Thus the constants on the right side
of a system don\'t decide alone whether a solution exists; rather, it
depends on some interaction between the left and right sides.

For some intuition about that interaction, consider this system with one
of the coefficients left as the parameter $c$.

$$\begin{array}{*{3}{rc}r}
x  &+  &2y  &+  &3z  &=  &1  \\
x  &+  &y   &+  &z   &=  &1  \\
cx  &+  &3y  &+  &4z  &=  &0
\end{array}$$

If $c=2$ this system has no solution because the left-hand side has the
third row as a sum of the first two, while the right-hand does not. If
$c\neq 2$ this system has a unique solution (try it with $c=1$). For a
system to have a solution, if one row of the matrix of coefficients on
the left is a linear combination of other rows, then on the right the
constant from that row must be the same combination of constants from
the same rows.

More intuition about the interaction comes from studying linear
combinations. That will be our focus in the second chapter, after we
finish the study of Gauss\' method itself in the rest of this chapter.

## Exercises


## Footnotes

```{=html}
<references/>
```
|current=General = Particular + Homogeneous
|previous=Describing the Solution Set
|next=Comparing Set Descriptions}}`{=mediawiki}


[^1]: More information on mathematical induction is in the appendix.
