Proving A = rref(B) with a Matrix S

[johndoe3344]

Let's say we're given that A = rref(B)

I know this means that there is some matrix (let's call it S) such that A = SB.

How do I prove this?

I know that to change a matrix into its rref form, you perform a sequence of elementary row operations on it - why does this necessarily mean there will be a matrix S such that A = SB?

 

[Hurkyl]

You know every elementary row operation is the result of left-multiplying by an elementary matrix, right?

 

[johndoe3344]

What do you mean?

If I had the matrix:

[ 1 0 0]
[ 0 1 1]
[ 0 0 1]

To change that into rref, I would just subtract Row III from Row II.

 

[HallsofIvy]

I don't think you intended it but the matrix you give is an "elementary" matrix- it can be derived from the identity matrix by a single row operation- here adding row III to row II (so that your "subtract Row III from Row II" changes it back to the identity matrix and so row reduces it). Hurkyl's point is that apply a rwo operation to a matrix is exactly the same as multiplying that matrix by the corresponding row operation: If A is any 3 by 3 matrix, multiplying A by the matrix you gave will "add row III to row II".

Since applying a row operation is the same as multiplying by an elementary matrix, applying a series of row operations (to row reduce a matrix) is the same as multiplying the matrix by the corresponding elementary matrices which is the same as multiplying the matrix by a single matrix, the product of those elementary matrices.