# How to prove that an invertible matrix is a product of elementary matrices?

Let $$A = (a_{ij})$$ be an invertible $$n\times n$$ matrix. I wonder how to prove that $$A$$ is a product of elementary matrices. I suspect that we need to transform it into the identity matrix by using elementary row operations, but how to do it exactly?

P.S. I've checked questions which could be considered similar and neither of them deals with this exact (general) situation. Please don't mark this question as a duplicate unless you find a precise answer.

• You want to prove it is a product of elementary matrices. The RREF of an invertible matrix is the identity, because all columns become pivot columns. Commented Jun 15, 2019 at 23:31
• @egreg Thanks for noticing a mistake, I will edit. However, but why all column become pivot column? How to prove it exactly? Commented Jun 15, 2019 at 23:33
• @egreg Oh, I've found a source regarding this. Apparently, the only invertible RREG if the identity. Commented Jun 15, 2019 at 23:36
• An invertible $n\times n$ matrix has rank $n$, so the elimination must find $n$ pivots. Commented Jun 15, 2019 at 23:41
• @egreg Oh, that's clever. Thanks. Commented Jun 15, 2019 at 23:48

You simply need to translate each row elementary operation of the Gauss' pivot algorithm (for inverting a matrix) into a matrix product.

If you permute two rows, then you do a left multiplication with a permutation matrix.

If you multiply a row by a nonzero scalar then you do a left multiplication with a dilatation matrix.

If you add a multiple of a row to another row, then you do a left multiplication with a transvection matrix.

And the inverse is therefore the product of all those elementary matrices.

If A is an invertible nxn matrix, $$A\bar x = \bar 0$$ has only the trivial solution of $$\bar 0$$ because $$A^{-1}A\bar x = \bar x = A^{-1}\bar0 =\bar0 \tag{1}\label{1}$$ This implies A is a product of elementary matrices because it implies A is row equivalent to I

Let's assume the A is in REF, if one of the diagonal elements were $$0$$ we would have a row filled with $$0$$'s and would have more unknowns than equations (proof n>m implies nontrivial solution omitted) and as a consequence has a nontrivial solution. Therefore, since we have no nontrivial solution $$\ref{1}$$, I is the RREF of A and A is composed of elementary row operations of I