Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 4 / a

The three elementary row operations are:

The nonzero requirement in the second operation ensures that each elementary row operation is reversible.

For a square matrix, the corresponding changes in its determinant areThese follow respectively from the alternating property, multilinearity in the rows, and the fact that a determinant with two equal rows vanishes.

If a square matrix $A$ is an invertible matrix, multiplicativity of the determinant givesso $\det A\ne 0$.

Conversely, suppose $\det A\ne 0$. Use Gaussian elimination to reduce $A$ to row echelon form $U$. Each elementary row operation multiplies the determinant by a nonzero factor, so $\det U\ne 0$. If this square matrix had fewer than $n$ pivots, its row echelon form would have a zero row and hence zero determinant, a contradiction. Therefore it has a pivot in every row and column, and further elementary row operations reduce it to $I$.

Each elementary row operation is multiplication on the left by an invertible matrix, its inverse being the reverse operation. Thus $E_k\cdots E_{1}A=I$ implies $A=E_1^{-1}\cdots E_k^{-1}$, a product of invertible matrices. Hence