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.


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$?

  • $\begingroup$ 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$. ... $\endgroup$ – MoonLightSyzygy Jan 12 at 22:03
  • $\begingroup$ ... 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)$. $\endgroup$ – MoonLightSyzygy Jan 12 at 22:04

Your interpretation is correct.

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

| cite | improve this answer | |

Your Answer

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