Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 4 / d

The rank of $A$ is the dimension of its column space, equivalently the dimension of its row space or the number of pivot columns in a row-echelon form. For an $n\times n$ matrix it lies between zero and $n$.

Each elementary matrix is obtained by applying one invertible elementary row operation to the identity matrix. Its inverse is the elementary matrix for the reverse operation. A product of elementary matrices is therefore invertible and has full rank $n$.

Conversely, if $\mathrm{rank}A=n$, Gaussian elimination has a pivot in every column and reduces $A$ to the identity. Writing the successive row operations as left multiplication gives $E_r\cdots E_{1}A=I$. Hence $A=E_1^{-1}\cdots E_r^{-1}$, a product of elementary matrices. This proves both directions of the elementary-matrix factorization theorem.