0
$\begingroup$

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

Description of Algorithm 3.12

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

2 Answers 2

2
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ May 19, 2020 at 12:12
  • $\begingroup$ @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. $\endgroup$
    – user790072
    May 19, 2020 at 12:36
  • $\begingroup$ "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. $\endgroup$
    – twosigma
    May 20, 2020 at 3:14
0
$\begingroup$

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!!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.