# Understanding a Proof for "A Square Matrix is Invertible If its Rows Are Linearly Independent"

In Eric Lengyel's book, Mathematics for 3D Game Programming and Computer Graphics, 3rd Edition, there is a theorem that states

An $$n \times n$$ matrix M is invertible if and only if the rows of M form a linearly independent set of vectors.

Two proofs were provided, each corresponding to if and only if of the theorem. I understand the first proof, but I don't fully understand the second one. I have some understanding of it, but it's not enough to fully grasp the proof. The proof, slightly modified for brevity, goes as follows:

Let the rows of M be denoted by $$R_{1}^{T}, R_{2}^{T}, \ldots, R_{n}^{T}$$. Now assume that the rows of M are a linearly independent set of vectors. We first observe that performing elementary row operations on a matrix does not alter the property of linear independence within the rows. Running through Algorithm 3.12, if step C fails, then rows j through n of the matrix at that point form a linearly dependent set since the number of columns for which the rows $$R_{j}^{T}$$ through $$R_{n}^{T}$$ have at least one nonzero entry is less than the number of rows itself. This is a contradiction, so step C of the algorithm cannot fail, and M must be invertible.

Note: A screenshot from the book of Algorithm 3.12 is available at the bottom.

What I don't fully understand is this snippet of the proof:

[...] rows j through n of the matrix at that point form a linearly dependent set since the number of columns for which the rows $$R_{j}^{T}$$ through $$R_{n}^{T}$$ have at least one nonzero entry is less than the number of rows itself. [...]

Why do the rows form a linearly dependent set based on the idea that "the number of columns for which the rows $$R_{j}^{T}$$ through $$R_{n}^{T}$$ have at least one nonzero entry is less than the number of rows itself."?

### Appendix

Algorithm 3.12 • $k$ linearly independent vectors span a space of dimension $k$. Their span cannot be contained in a space of dimension $k - 1$ or less. May 18, 2020 at 20:21
• I think your question depends on what the author has already proven/shown. Also their definition of linear independence/dependence. May 18, 2020 at 20:48

The proof appears to be using the fact that linearly independent subsets of $$\Bbb{R}^n$$ have at most $$n$$ vectors in them. For the sake of illustration, let's say we're at step C with $$j = 3$$ in an $$n \times n$$ matrix. Then our matrix looks something like this:

$$\begin{pmatrix} 1 & 0 & * & * & \cdots & * \\ 0 & 1 & * & * & \cdots & * \\ 0 & 0 & \color{red}* & * & \cdots & * \\ 0 & 0 & \color{red}* & * & \cdots & * \\ \vdots & \vdots & \color{red}\vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \color{red}* & * & \cdots & * \end{pmatrix}.$$

The proof then tries to find the largest absolute value out of the red $$\color{red}*$$s, throwing an exception if every one is $$0$$. If every one of the $$\color{red}*$$s was $$0$$, then the last $$n - 2$$ rows each begins with three $$0$$s, and the $$n - 2$$ row vectors can be embedded in $$\Bbb{R}^{n - 3}$$ (by ignoring the first three $$0$$s). There are one too many such vectors for them to be linearly independent, hence the theorem (for the $$j = 3$$ case anyway; hopefully you can see how this would generalise).

• I am starting to understand the proof better thanks to your answer. But, why $\Bbb{R}^{n - 3}$? Why ignore the first three $0$s, or, for a general case, the first $j$ entries? May 19, 2020 at 12:12
• @SeanFrancisN.Ballais In my specific example, where $j = 3$, the first $3$ entries are all $0$, so we can embed them in $\Bbb{R}^3$, preserving linear independence, by simply ignoring the first $3$ entries. In general, it will be the first $j$ entries, embedding $n - j + 1$ vectors into $\Bbb{R}^{n-j}$. I only picked $j = 3$ so that I could illustrate what's happening. May 19, 2020 at 12:36
• "Why ignore the first three 0s" -- The span of a set of vectors is by definition the set of all linear combinations of those vectors. For example, in $\mathbb{R}^3$, suppose we have the vectors $(1, 0, 0)$ and $(0, 1, 0)$. Can you see how all linear combinations of these vectors will never make the third coordinate anything other than zero? So, we say that these two vectors span a subspace of dimension 2. If you draw the picture in 3D, these two vectors span a "copy" of the $xy$-plane. It is all those vectors in 3D whose "height" is zero. Hopefully you can generalize to your example. May 20, 2020 at 3:14

I will prove the same statement for independent column vectors which is an equivalent statement.

If the columns of $$A$$ are linearly independent it is clear that $$Ax=0$$ implies $$x=0$$ and hence, the nullspace $$N(A)$$={$$0$$}.

That implies (since $$dimN(A)+dim\Re(A)=n$$) that $$dim\Re(A)=n$$ and hence every vector in $$\mathbb{R}^{n}$$ can be written as $$Ay$$. Therefore $$e_{1}=Ay_{1},e_{2}=Ay_{2},...e_{n}=Ay_{n}$$ which gives $$AY=I$$.

Also, $$N(A)^{\perp}=\mathbb{R}^{n}$$, but $$N(A)^{\perp}$$=$$\Re(A^{T})$$ which gives that every vector in $$\mathbb{R}^{n}$$ can be written as $$A^{T}z$$. Thus $$e_{1}=A^{T}z_{1},e_{2}=A^{T}z_{2},...e_{n}=A^{T}z_{n}$$

and hence $$A^{T}Z=I$$ i.e. $$Z^{T}A=I$$. Therefore $$Z^{T}AY=Z^{T} \Rightarrow Y=Z^{T}$$.

Thus there is an $$Y$$ such that $$AY=YA=I$$ which is the definition of the inverse of $$A$$. i.e. $$A^{-1}=Y$$. That completes the proof!!