# Is there a simple proof that a non-invertible matrix reduces to give a zero row?

Let $$A$$ be a square matrix that is non-invertible. I was wondering if there is a simple proof that we can apply elementary row operations to get a zero row. (For a matrix $$C$$ to be invertible, I mean there is $$B$$ such that $$CB = BC = I$$.)

I can prove this using elementary column operations but I would like a more direct proof that doesn’t appeal to column operations or the fact that row rank equals column rank, or anything to do with transposes, or the existence of RREF, or determinants, etc. The difficulty seems to be that elementary row operations are applied on the row space, whereas invertibility is sort of defined in terms of the column space.

You could also use (but it is preferred not to) facts like: A matrix $$C$$ being invertible is equivalent to null space of $$C$$ being zero (i.e. injective) is equivalent to $$C$$ being surjective.

• This is equivalent to saying that if the row space of a $A$ is a strict subspace of $\Bbb R^n$, then this subspace has a spanning set of at most $n-1$ vectors. In other words, this statement is essentially equivalent to the dimension theorem – Ben Grossmann Jul 15 '20 at 13:51

If your matrix $$A$$ is $$n\times n$$, the search for an inverse matrix is the same as solving the $$n$$ linear systems $$Ax=e_i\qquad (i=1,2,\dots,n)$$ where $$e_i$$ is the $$i$$-th column of the identity matrix. If the matrix is not invertible, then at least one of those systems must have no solution, say it's the one for $$e_i$$.

Performing row reduction on the augmented matrix $$[A\mid e_i]$$ yields that the last column must be a pivot column. If the pivot is on row $$j$$, then the row reduction of $$A$$ has a zero $$j$$-th row.

• $[A\mid e_i]$ will have no solution if $A$ has a zero $i$th row ,since $e_i$ has a non zero entry at the $i$th row , is that what you mean? – Kashmiri Apr 16 at 17:31
• @Kashmiri Not really. There is a system $Ax=e_i$ that has no solution. The row reduction on the augmented matrix $[A\mid e_i]$ will yield a last column that's no longer $e_i$. Nonetheless, this last column must be a pivot column, with the pivot in some row $j$; actually $j$ is one more than the rank of $A$. – egreg Apr 16 at 17:43
• I've got a small doubt can I ask? – Kashmiri Apr 16 at 18:19
• @Kashmiri Sure! – egreg Apr 16 at 19:39
• We are doing row reduction without row swapping to the above augmented matrix. Going on we will reach a stage where row $i$ of $A$ will be all zero and the row $i$ of $e_i$ will have $1$ . So it's the $i$th row that has the problem not $j$th. I asked this doubt on chat and they seemed to agree with me. Could you please clarify. – Kashmiri Apr 16 at 23:11

Assume a non-invertible matrix $$A$$ that does not reduce to a zero row. Then you can use the Gaussian elimination with multiple RHS to solve

$$AB=I$$ and this process will work till the end, giving (after back substitution) a solution such that

$$B=A^{-1}$$ !?

A zero row is what blocks the elimination process, making the complete resolution/inversion impossible.

Probably you talk about square matrices. This might be a "direct proof": elementary row-operation do not change the fact whether or not a matrix is invertible. So, if you can never reach a zero row, you can do Gaussian elimination to convert it to a row-echelon form such as here -- but if the matrix is square and has no zero-rows, it can only be diagonal / identity matrix.

• I was hoping to avoid using the existence of row-echelon form because I find it a little indirect – twosigma Jul 15 '20 at 13:37
• But almost anything "nice" assumes such things as "existence of dimension" and this already relies on some nontrivial facts... – Peter Franek Jul 15 '20 at 13:39
• Ok. I will try to revisit the proof of Gaussian elimination and row-echelon form. – twosigma Jul 15 '20 at 13:44

Well it is known that if $$c_1, ..., c_n \in \mathbb{R}^n$$ are linearly independent then $$A=(c_1, ..., c_n)$$ is invertible so if A isn't invertible there exist $$c_i$$ with $$1\leq i\leq n$$ such that $$c_i= \sum_{j=1}^{n} a_j c_j$$ and $$a_j=0$$.