# Trouble understanding proof #1 3.C linear algebra done right

Problem:Suppose $$V$$ and $$W$$ are finite dimensional and $$T \in \mathcal{L}(V,W)$$. Show that with respect to each choice of bases of $$V$$ and $$W$$, the matrix $$T$$ has at least dim range $$T$$ nonzero entries.

Proof:

Suppose for some basis $$v_1,...,v_n$$ of $$V$$ and some basis $$w_1,...w_m$$ of $$W$$, the matrix of $$T$$ has at most dimrange$$T-1$$ nonzero entries. Then there are at most dimrange$$T-1$$ nonzero vectors in $$Tv_1,...,Tv_n$$. Note that range$$T=$$span$$(Tv_1,...,Tv_n)$$, it follows that dimrange$$T \leq$$ dimrange$$T-1$$.A contradiction.

I am confused about several parts of this proof. I know it is a proof by contradiction, they are assuming there exists a matrix $$T$$ with respect to the bases that has at most dimrange$$T-1$$ nonzero entries.

Because of this there are at most dimrange$$T-1$$ nonzero columns in the matrix of $$T$$.

Here is where my confusion begins:

Since $$Tv_1,...,Tv_n$$ span the range of $$T$$ it follows that dimrange$$T\leq$$ dimrange$$T-1$$.

My interpretation of this result:

I am lost on this last step but I think it means since range$$T=$$span$$(Tv_1,...,Tv_n)$$, the list of vectors $$v_1,...,v_n$$ is not necessarily linearly independent, hence can be reduced to a linearly independent basis accordingly that is less than or equal to the dimension of range$$T-1$$.

Also why must it be less than or equal to dimrange$$T-1$$?

• That argument is a mess. The proof can be something like this. Assume that the number of non-zero entries in the matrix $M$ of $T$, in some pairs of bases $A=\{v_1,...,v_n\}$ of $V$ and $B=\{w_1,...,w_m\}$ of $W$, has $K$ non-zero entries. Then it has no more than $K$ non-zero columns. Now note that the columns $e_1=(1,0,...0)^T,e_2=(0,1,0,...,0)^T,...,e_n=(0,0,...,1)^T$ are the coordinates of $A$ in the basis $A$. Then, the coordinates of $Tv_i$ in the basis $B$ is the column $Me_i$. Note that $Me_i$ is the $i$-th column of $M$. ... – MoonLightSyzygy Jan 12 at 22:03
• ... Therefore, there are at most $K$ non-zero vectors among $Tv_1,...,Tv_n$. Since the number of linearly independent vectors among $Tv_1,...,Tv_n$ is the dimension of the range of $T$ and this in turn is not more than the number of non-zero vectors among them, then we have that $K\geq \dim\operatorname{range}(T)$. – MoonLightSyzygy Jan 12 at 22:04

By the indirect hypothesis, at most $$r-1$$ of these vectors are nonzero, hence they can't span $$\ge r$$ dimensions, where $$r=\dim\mathrm{range} T$$.