# Linear algebra. If Ax = 0, why does this imply that a series of elementary matrices multiplied by A = I?

So I have seen that a system of linear equations represented by $Ax = O$ has only the trivial solution. But why does this imply that the augmented matrix [A O] can be rewritten in the form [I O] (using elementary row operations corresponding to $E_1$, $E_2$, . . . , and $E_k$)?

Additionally if $E_k$. . .$E_3E_2E_1A=I$ why does it follow that $A = E_1^{-1}E_2^{-1}E_3^{-}1. . .E_k^{-1}$ (A can be written as the product of elementary matrices).

This is some relevant text to the first paragraph:

I can see that x is a trivial solution when $b = 0$.

• Correction: $Ax=0$ has only the trivial solution $x=0$ if and only if $A$ is nonsingular. – parsiad Jul 27 '18 at 20:57

An elementary row (column) operation is defined as one of the following

1. interchanging any two rows ( columns) of $A$
2. multiplying any rows (columns) by a nonzero scalar
3. adding scalar multiples of a row (column) of $A$ to another row

this is Gaussian elimination

$$A = E_{1}^{-1}E_{2}^{-1} \cdots E_{k}^{-1} \implies (E_{1}^{-1}E_{2}^{-1} \cdots E_{k}^{-1}) E_{k}\cdots E_{2} E_{1} = I$$

Since

$$E_{k} \cdots E_{2} E_{1} = A^{-1}$$

then

$$AA^{-1} = A^{-1}A = I$$

Every row operation corresponds to an application of an elementary matrix... If the reduced matrix is the identity, then each of the variables is zero, and we get only the trivial solution.

The RREF is the identity precisely for nonsingular $A$. This is the heart of the matter. For the equivalency, one direction is obvious. For the other, note that the only nonsingular RREF is the identity...

Note that: if $A$ is nonsingular, then $A^{-1}$ exists... Now apply $A^{-1}$ to both sides of $A\vec x=\vec0$ and use that any linear transformation takes $\vec0$ to $\vec0$. That is: $$A^{-1}A\vec x=A^{-1}\vec0\implies I\vec x=\vec0\implies \vec x=\vec0$$.