# Why does this work?

1. Feb 26, 2014

### SmilingDave

Cullen in a question seems to say this;

You have a matrix A of any size. Make a matrix B consisting of only the linearly independent columns of A, choosing them by going from left to right through the columns of A. Then make a matrix C such that BC=A [The q was to prove this is always possible. But I'm not asking about that]

He then says that the rows of C are exactly the rows of A in row reduced echelon form. I tried an example, and it works.

My q is, why is this so? I assume it's not just coincidence, so what is going on?

2. Feb 26, 2014

### Simon Bridge

Because the columns of B are linearly independent.
i.e. what does it mean to reduce to row echelon form?

3. Feb 26, 2014

### SmilingDave

To have the rows interact until they produce a basis for the row space of A.

What I don't see is how did C get to have exactly those same rows. I mean, C was introduced into the picture to have its columns operate on the columns in B so as to produce from B the whole of A. Its rows were never given a thought and didn't play a part. So how did they magically become the rows of A in RREF?

4. Feb 26, 2014

### Simon Bridge

Are the rows, then, not related to the columns?

5. Feb 27, 2014

### SmilingDave

What I know is that the rank of the row space is always equal to the rank of the column space, but I don't know of any other connection between them. The bases can be very different. For example, if A is 3x5, the rows are elements of a five dimensional space, and the columns of a three dimensional one.

6. Feb 27, 2014

### Erland

Something is wrong here. If A has type m x n, and rank(A)=k<m, then B has type m x k, so if C satifies BC=A, then C has type k x n, which is not the same as the type of A. But then, C is not the reduced row echolon form of A, sice A and C have different types.

7. Feb 27, 2014

### SmilingDave

Erland,

The RREF of A will have a bunch of zero rows underneath the rows of C [which are all nonzero].

8. Feb 27, 2014

### Simon Bridge

The other way of seeing this is that you take your matrix A, row reduce it (to reduced row echelon form), call this C, then find the matrix B: BC=A.

Perhaps if you picked a simple case and treated it as a system of simultaneous equations it would help you see what is happening at each stage: what you are doing to the equations.

Note: when you row-reduce A like that, you are finding a particular basis, not just any old basis.
It should come as no surprise that this basis should have a special relationship with A.

9. Mar 1, 2014

### SmilingDave

I see some light. Let R be the matrix that represents all the row operations used to row reduce A. Then RA=C

Thus A=BC, where B is R-inverse.

Let A have rank r.

Since C is also of rank r, it is just rows of zeros beyond row r, and thus it will only use the first r columns of B to build A from B.

So we can get the same effect, meaning get A, by using a matrix consisting of just the first r columns of B, and multiplying by the first r rows of C, and we will get A.

[If A is mxn, modified B will be mxr, and modified C will be rxn, so the dimension are OK].

But I'm still a bit in the dark. We have shown that there is a decomposition of A into R-inverse [modified] and C [modified].

Also, that there is a decomposition using the first lin ind columns of A [call it A modified] and some other matrix, call it D. So that A= R-inverse-modified times C-modified and also = A-modified times D.

But maybe A has two decompositions, using completely different matrices. How do we know A-modified equals R-inverse modified, and that C-modified equals D?

Still working on it. Will try your suggestion of a concrete example.

Thanks for all the help.

10. Mar 1, 2014

### Simon Bridge

Are there more than one decomposition that fits all the conditions?
Have you covered LU and LDU decomposition yet?