Linear Algebra/General = Particular + Homogeneous

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.

$\{\underset{\begin{array}{c}\\ \text{particular}\\ \text{solution}\end{array}}{\underbrace{\left(\begin{array}{c}0\\ 4\\ 0\\ 0\\ 0\end{array}\right)}}+\underset{\begin{array}{c}\\ \text{unrestricted}\\ \text{combination}\end{array}}{\underbrace{w\left(\begin{array}{c}1\\ -1\\ 3\\ 1\\ 0\end{array}\right)+u\left(\begin{array}{c}1/2\\ -1\\ 1/2\\ 0\\ 1\end{array}\right)}}|w,u\in ℝ\}$

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 $\overrightarrow{p}$ and also the unrestricted linear combination of the $\overrightarrow{\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 $\overrightarrow{p}+c_1{\overrightarrow{\beta }}_1+\dots +c_k{\overrightarrow{\beta }}_k$ can be shortened to $c_1{\overrightarrow{\beta }}_1+\dots +c_k{\overrightarrow{\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}{ccccccccc}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. Template:AnchorThe second reason is that the row-by-row nature of back substitution leads to a proof that uses the technique of mathematical induction. 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.

We say that the set $\{c_1{\overrightarrow{\beta }}_1+\cdots +c_k{\overrightarrow{\beta }}_k|c_1,\dots ,c_k\in ℝ\}$ is generated by or spanned by the set of vectors $\{{\overrightarrow{\beta }}_1,\dots ,{\overrightarrow{\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.

Template:TextBox 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 solution exists?	yes	unique solution	infinitely many solutions
	no	no solutions	no 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}{ccccc}3x& +& 2y& =& 5\\ 3x& +& 2y& =& 5\end{array}\begin{array}{ccccc}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}{ccccc}3x& +& 2y& =& 5\\ 4x& +& 2y& =& 4\end{array}\begin{array}{ccccc}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}{ccccccc}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\ne 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

/Solutions/