# Column rank, linear independence and RRE form

• Apr 10th 2010, 10:51 PM
Bucephalus
Column rank, linear independence and RRE form
if I have a matrix A like this:

A = $\displaystyle \left[\begin{matrix}1 & 1 & 0 & 0 & 1 & 0 & 0\\1 & 1 & 0 & 0 & 0 & 1 & 0\\1 & 1 & 0 & 0 & 0 & 0 & 1\\1 & 0 & 1 & 0 & 1 & 0 & 0\\1 & 0 & 1 & 0 & 0 & 1 & 0\\1 & 0 & 1 & 0 & 0 & 0 & 1\\1 & 0 & 0 & 1 & 1 & 0 & 0\\1 & 0 & 0 & 1 & 0 & 1 & 0\\1 & 0 & 0 & 1 & 0 & 0 & 1\end{matrix}\right]$

when I do a reduced row echelon form rref in matlab it comes out like this:

$\displaystyle \left[\begin{matrix}1 & 0 & 0 & 1 & 0 & 0 & 1\\0 & 1 & 0 & -1 & 0 & 0 & 0\\0 & 0 & 1 & -1 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 0 & -1\\0 & 0 & 0 & 0 & 0 & 1 & -1\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{matrix}\right]$

Well I thought that when there is a pivot in a column, then that column is linearly independent, but I can see simply that column one in matrix A, $\displaystyle c_1$ is a combination of $\displaystyle c_2$ and $\displaystyle c_3$ and $\displaystyle c_4$.
So why is $\displaystyle c_1$ linearly independent?
• Apr 10th 2010, 11:18 PM
dwsmith
Instead of saying $\displaystyle c_1$ can be written as combination, you can say $\displaystyle c_4=c_1-c_2-c_3$; therefore, $\displaystyle c_4$ is lin. dep and can be written as a linear combination.
• Apr 10th 2010, 11:22 PM
PiperAlpha167
Quote:

Originally Posted by Bucephalus
if I have a matrix A like this:

A = $\displaystyle \left[\begin{matrix}1 & 1 & 0 & 0 & 1 & 0 & 0\\1 & 1 & 0 & 0 & 0 & 1 & 0\\1 & 1 & 0 & 0 & 0 & 0 & 1\\1 & 0 & 1 & 0 & 1 & 0 & 0\\1 & 0 & 1 & 0 & 0 & 1 & 0\\1 & 0 & 1 & 0 & 0 & 0 & 1\\1 & 0 & 0 & 1 & 1 & 0 & 0\\1 & 0 & 0 & 1 & 0 & 1 & 0\\1 & 0 & 0 & 1 & 0 & 0 & 1\end{matrix}\right]$

when I do a reduced row echelon form rref in matlab it comes out like this:

$\displaystyle \left[\begin{matrix}1 & 0 & 0 & 1 & 0 & 0 & 1\\0 & 1 & 0 & -1 & 0 & 0 & 0\\0 & 0 & 1 & -1 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 0 & -1\\0 & 0 & 0 & 0 & 0 & 1 & -1\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{matrix}\right]$

Well I thought that when there is a pivot in a column, then that column is linearly independent, but I can see simply that column one in matrix A, $\displaystyle c_1$ is a combination of $\displaystyle c_2$ and $\displaystyle c_3$ and $\displaystyle c_4$.
So why is $\displaystyle c_1$ linearly independent?

Here's another way to look at it:

The mistake is identifying column one in A with column one in the result handed to you by matlab.
A reordering has taken place.

Correction. The above is not stated well at all.

Reordering the columns amounts to a relabeling of the unknowns.
It is performed (conceptually at least) by applying a succession of permutations from the right to A.
The intention here (at least one) is to put the resulting matrix in a "nice" form, i.e., push the non-zero pivots
as far to the left as possible. Certainly, you can see this is going to happen to A simply by eye.
After the first several reduction steps, the second column will be all zeros. So your matlab is going to "fix it" by
relabeling the unknowns. Note also, that there has been a reordering of the rows (which is in effect simply an interchanging
of the equations). This process has no effect on the labeling of the unknowns, and could be carried out (again conceptually) by
a preliminary multiply of an appropriate permutation matrix to A, this time from the left.

This is why you cannot (in general) identify the columns of A with the corresponding columns of
the resulting matrix.

Also, this experience should suggest that it's a good idea on your part to know exactly what any software package
is going to do (or might do) to what you hand it.
• Apr 10th 2010, 11:27 PM
Bucephalus
Quote:

Originally Posted by dwsmith
Instead of saying $\displaystyle c_1$ can be written as combination, you can say $\displaystyle c_4=c_1-c_2-c_3$; therefore, $\displaystyle c_4$ is lin. dep and can be written as a linear combination.

So areyou saying that we can kind of choose which column is dependent, depending on how we look at it?
• Apr 10th 2010, 11:29 PM
Bucephalus
Quote:

Originally Posted by PiperAlpha167
Here's another way to look at it:

The mistake is identifying column one in A with column one in the result handed to you by matlab.
A reordering has taken place.

Matlab reordered it? Does this go back to what the previous person was saying in that it isn't necessarily the first obvious choice? In fact that are different choices and what makes it liek this is because it's the whole set that is linearly dependent?
• Apr 11th 2010, 01:11 AM
Bucephalus
Thanks
Thanks both of you. Those responses were helpful.

David.
• Apr 11th 2010, 01:11 AM
PiperAlpha167
Quote:

Originally Posted by Bucephalus
Matlab reordered it? Does this go back to what the previous person was saying in that it isn't necessarily the first obvious choice? In fact that are different choices and what makes it liek this is because it's the whole set that is linearly dependent?

There is a correction in my first post. You might take a look at it.

If you carry out the reduction process yourself you'll see that the linearly independent columns of A are 1,3 and 4.
This is not at all difficult; it can be done by eye.

The matrix returned from matlab tells you immediately that there are only three linearly independent columns in A.
But due to other matlab activities, the three nonzero pivots are sitting in columns 1,2 and 3.

The breakdown in the correspondence between the columns of A and the columns of the matlab result is clearly evident.
• Apr 11th 2010, 01:58 AM
Bucephalus
But how can column 1 be linearly independent if it can be built from columne 2, 3 and 4?
would c2 + c2 + c3 = c4
It seems I'm back to where I started?
If c1 can be built by a linear combination of the othter columns why is it linearly independent?
I'm missing something here.
• Apr 11th 2010, 02:07 AM
Bucephalus
Confusion
How can you look at that A matrix and tell by eye, that for instance the first column is linearly independent. I'm sure you know something I don't about linear independence, take away the row reduction and matlab.

David.
• Apr 11th 2010, 06:32 AM
HallsofIvy
You need to understand that it doesn't make sense to say that a specific vector is "independent" or "dependent". A set of vectors may be independent or dependent. What your row reduction shows is that (the set of) the first three vectors are independent but the first four are not.
• Apr 11th 2010, 07:37 AM
PiperAlpha167
Quote:

Originally Posted by Bucephalus
How can you look at that A matrix and tell by eye, that for instance the first column is linearly independent. I'm sure you know something I don't about linear independence, take away the row reduction and matlab.

David.

First, you continue to refer to column vector 1, and ask how it can be linearly independent.
When you say that, what do you have in mind? It doesn't make sense to me.
Certainly, if you throw any nonzero vector into a set by itself, you can say it is a linearly independent set.
(After all, for nonzero vector v, what is the only scalar, c, that will make cv = 0?)
But I don't see what it has to do with this problem.

Second, I claimed that the reduction could be carried out by eye.
Well, I'm sorry to say that I didn't do it myself correctly, so where do I get off suggesting that anyone else should be able to do it correctly?
Certainly, column 2 does not become a column of all zeros, as I claimed.

Trying again (with more care), I see that columns 1, 2, 3, 5 and 6 form a linearly independent set. This is in accord with the matlab result. You can see the unit pivots clearly in those five columns.
So the rank of A is 5. Dimension of column space and row space is each 5; dimension of null space is 2; dimension of left-null space is 4.

Now I expect you will object again, since column 1 is still in this set.
And, you will ask again, how can it be linearly independent.
I think you can answer this question yourself by noting that the column 4 vector is not in the above set.

P.S. I don't think I've made any claim about knowing something (or anything) that you don't already know concerning the notion of linear independence.
Have a good day.
• Apr 11th 2010, 08:36 AM
Bucephalus
Quote:

Originally Posted by HallsofIvy
You need to understand that it doesn't make sense to say that a specific vector is "independent" or "dependent". A set of vectors may be independent or dependent. What your row reduction shows is that (the set of) the first three vectors are independent but the first four are not.

Yes that makes sense to me. Thankyou for that. It was kind of what I was asking. It's the set, so I have some flexibility in what columns I remove to make an independent set, i.e. rank 5.
Yes that makes sense now.
• Apr 11th 2010, 08:38 AM
Bucephalus
Quote:

Originally Posted by PiperAlpha167
First, you continue to refer to column vector 1, and ask how it can be linearly independent.
When you say that, what do you have in mind? It doesn't make sense to me.
Certainly, if you throw any nonzero vector into a set by itself, you can say it is a linearly independent set.
(After all, for nonzero vector v, what is the only scalar, c, that will make cv = 0?)
But I don't see what it has to do with this problem.

Second, I claimed that the reduction could be carried out by eye.
Well, I'm sorry to say that I didn't do it myself correctly, so where do I get off suggesting that anyone else should be able to do it correctly?
Certainly, column 2 does not become a column of all zeros, as I claimed.

Trying again (with more care), I see that columns 1, 2, 3, 5 and 6 form a linearly independent set. This is in accord with the matlab result. You can see the unit pivots clearly in those five columns.
So the rank of A is 5. Dimension of column space and row space is each 5; dimension of null space is 2; dimension of left-null space is 4.

Now I expect you will object again, since column 1 is still in this set.
And, you will ask again, how can it be linearly independent.
I think you can answer this question yourself by noting that the column 4 vector is not in the above set.

P.S. I don't think I've made any claim about knowing something (or anything) that you don't already know concerning the notion of linear independence.
Have a good day.

Thanks for spending the time to write all that.
cheers.