# Linear independence of columns and covering the whole space (algebraic rationale)

It would be great if someone could explain me the following. If I understand the lecture correctly, given a system of, say, following equations:

$x+2y-2z=1$
$2x+4y+z=3$
$4x+8y+4z=10$

We can say that the they do not describe the whole 3D space because the vectors formed by the first and second columns ( $\begin{pmatrix} 1 \\ 2 \\ 4 \end{pmatrix}$ and $\begin{pmatrix} 2 \\ 4 \\ 8 \end{pmatrix}$ respectively) are not linearly independent (meaning we can't solve the given equations for all possible RHS). From what I understand, it makes sense geometrically -- if we start at an arbitrary point in 3D, we can cover only a plane as we have only two directions we could move in. However, could someone please explain the meaning of the statement above in algebraic terms? What is it about the coefficients of a given variable that when they can be expressed via multiplication of some $c$ (where $c=2$ for the two aforementioned columns) by coefficients of some other variable, not all RHS values generate solutions? Thanks a lot!

-
Thanks a whole lot for the answers -- current and future. I am sorry I didn't make it quite clear -- I was looking for an explanation (if it exists) of why these equations behave this way without the usage of geometry (which includes vectors). It's entirely possible that there is no other explanation, but I thought I would give it a try! –  InterestedGuest Dec 13 '10 at 7:08
While I"m sure that answers that use less mention of vectors are possible, the problem itself is stated in terms of having a linear dependence between vectors, so I'm not sure what you mean by an explanation that doesn't use vectors. How about this: The coefficient matrix is not invertible, while a matrix is invertible if and only if it represents a surjective linear map, and therefore the map is not surjective. –  Jonas Meyer Dec 13 '10 at 7:18
@Jonas: That was mostly my explanation of the geometric understanding of the problem. In my second last sentence I tried to restate the question in purely algebraic terms -- why not all RHS work if coefficients are like the ones described above. The vector explanations certainly do make sense, and I will vote them up once my daily voting quota is replenished. :) –  InterestedGuest Dec 13 '10 at 7:23
I do not understand what your purely algebraic formulation is, but I hope someone does and gives you a good answer along those lines. However, you do not need geometry to see that if $a$, $b$, and $c$ are not all zero, then not all triples of numbers $x$, $y$, and $z$ can satisfy the equation $ax+by+cz=0$ (the description in my last paragraph). (Vectors are algebraic, too.) –  Jonas Meyer Dec 13 '10 at 7:32

You seem to want some explanation that does not involve vectors, subspaces spanned by columns, etc. I have to say that, in my personal opinion, vectors, subspaces, spans, etc. are the best way to think about it, but let me give it a try.

Suppose you have a $3\times 3$ linear system in $x$, $y$, and $c$, $$\begin{array}{rcccccl} a_1x & + & b_1y & + & c_1z & = & r_1\\ a_2x & + & b_2y & + & c_2z & = & r_2\\ a_3x & + & b_3y & + & c_3z & = & r_3 \end{array}$$ and that there is a constant $k$ such that $b_1=ka_1$, $b_2=ka_2$, and $b_3=kc_3$. Why does this mean that the system will not necessarily have solutions for any given $r_1$, $r_2$, and $r_3$?

Set $w=x+ky$. Then we can rewrite $a_ix + b_iy = a_ix + ka_iy = a_i(x+ky) = a_iw$. So we can rewrite the system as a system of three equations in two unknowns: $$\begin{array}{rcccl} a_1w & + & c_1z & = & r_1\\ a_2w & + & c_2z & = & r_2\\ a_3w & + & c_3z & = & r_3 \end{array}$$ This is an overdetermined system (more equations than unknowns), so we know that there are ways to make the right hand side inconsistent and for the system to have no solutions. So it is not the case that the system has solutions for all possible choices of $r_1$, $r_2$, and $r_3$.

Note that a solution to the original system gives a solution to this system by simply letting $w=x+ky$. Does a solution to this system correspond to a solution of the original system? Yes. Suppose that $w=a$, $z=c$ is a solution. Set $x=a$ and $y=0$ to get a solution to the original system (in fact, you can let $x=u$ and $y = (a-u)/k$ if $k\neq 0$ and get a solution, for any real $u$; if $k=0$, then you take $x=a$ and $y$ arbitrary). So solutions to this system are equivalent to solutions of the original system.

The same thing happens if what you have is that there exist nonzero $k$ and $\ell$ such that $a_i = kb_i+\ell c_i$ (another way for the columns to be linearly independent). Then we can rewrite $$a_ix + b_iy + c_iz = b_i(kx+y) + c_i(\ell x + z)$$ so letting $w_1 = kx+y$ and $w_2=\ell x+z$ you get an overdetermined system again. And again, solutions of this system correspond to solutions of the original, in the sense that the original has a solution if and only if this one has a solution.

-
Thanks a lot Arturo, the 'overdetermined system of equations' did it for me, I think that's the kind of algebraic explanation I was looking for! –  InterestedGuest Dec 14 '10 at 0:47

It seems that whatever algebraic way you try to look at it is, upon some thought, really just a paraphrase of the geometric one. One way of answering your question is that to generate all RHS values, we must have sufficient variation of the variables. However since one of the variables in this case has coefficients a multiple of another, as it varies to try to change the RHS it really is just doing the work of the other variable and so there is just not enough variation to go around to give what you want on the RHS.

-

If you understand what it means in geometric terms, then you are most of the way there. I'll try to elaborate a little on the algebra involved.

The equation can be rewritten as $xv_1+yv_2+zv_3=b$, where $v_1$, $v_2$, and $v_3$ are the column vectors. The question is, based on the relationship among the columns, which vectors $b$ can you plug in to make the equation have a solution. Since there is a linear relationship among the columns, the answer, as you said, is that not all choices of $b$ will work. You have $v_2=2v_1$, so the equation can also be written as $(x+2y)v_1+zv_3=b$. Thus, $b$ must lie in the $2$-dimensional subspace spanned by $v_1$ and $v_3$, your first and third columns.

More generally, if there is some nontrivial linear relationship among the columns of the form $a_1v_1+a_2v_2+a_3v_3=0$, where $a_1$, $a_2$, and $a_3$ are scalars and at least one is nonzero, then you can write one of your vectors as a linear combination of the other $2$, and hence any vector in the span (possible "right-hand sides" in your question) will have to be in the span of these $2$. The same idea generalizes to all (finite) dimensions. If the set of column vectors is not linearly independent, then the span of the columns has lower dimension.

If you want to see explicitly what choices of $b$ will not work in your example, you can write out what the span of $v_1$ and $v_3$ looks like, and choose any vectors not in this span. For a quick example in this case, you could choose the cross product $v_1\times v_3$, since it is orthogonal to both $v_1$ and $v_3$.

Another way to look at this is that if the columns are not linearly independent, then neither are the rows, and a linear relationship among the row vectors translates to a linear relationship among the entries of the right hand side. That is, if $A$ has row vectors $r_1$, $r_2$, and $r_3$, then $A\mathbf{x}= \begin{bmatrix} r_1\cdot\mathbf{x}\\ r_2\cdot\mathbf{x}\\ r_3\cdot\mathbf{x} \end{bmatrix}$, and if there are scalars $a_1$, $a_2$, and $a_3$, not all zero, such that $a_1r_1+a_2r_2+a_3r_3=0$, then it follows from the linearity of the dot product in each variable that $a_1(r_1\cdot\mathbf{x})+a_2(r_2\cdot\mathbf{x})+a_3(r_3\cdot\mathbf{x})=0$. That is, the right-hand side must lie in the plane described by the equation $a_1x+a_2y+a_3z=0$.

-

With $\rm\ c_i = i$'th column, the system is $\rm\ c_1\ x + c_2\ y + c_3\ z\ =\ d\:.\:$ This has a solution iff $\rm\:d\:$ lies in the space spanned by the columns. Since two of the three columns are linearly dependent, the columns can span at most a two-dimensional space. Therefore the system is not solvable for all $\rm\:d\:,\:$ i.e. the associated map is not onto.

-