For $T\in L(V,W)$, prove that there are bases such that $M(T)$ is 1 on the first dim range $T$ elements of the diagonal and zero everywhere else.

Question

I'd like to solve the following problem from Chapter 3, "Linear Maps", section 3.C "Matrices", from Axler's Linear Algebra Done Right.

3. Suppose $V$ and $W$ are finite-dimensional and $T\in L(V,W)$. Prove that there exist a basis of $V$ and a basis of $W$ such that with respect to these bases, all entries of $M(T)$ are $0$ except that the entries in row $j$, column $j$, equal 1 for $1\leq j\leq$ dim range $T$.

Let dim $V=n$ and dim $W=m$.

It seems to me that there is an easy case that occurs when $m\geq n$ In this case, we can reduce the set of vectors $Tv_1,...,Tv_n \in $ range $T$ to a basis of dimension $l\leq n$.

Without loss of generality, assume this basis is formed by the vectors

$$Tv_1,...,Tv_l$$

Extend these vectors to a basis of $W$

$$Tv_1,...,Tv_l,w_1,...,w_{m-l}$$

Then, the matrix of $T$ is $m$ by $n$ and has the desired properties.

I saw a solution on a website and it only contained this first case. But is there not a second case?

My question is about the second case. Namely, if $m<n$.

$T$ is given.

Again, let's call dim range $T=l$.

We know that

$$\mathrm{dim\ null}\ T +\mathrm{dim\ range}\ T=\mathrm{dim}\ V$$

$$\mathrm{dim\ null}\ T + l = n$$

Thus, since $$l= \text{dim range}\ T\leq m<n=\text{dim}\ V$$

then dim null $T=n-l\geq 1$.

Of the $n$ vectors $v_1, ...,v_n$, $n-l$ are in the nullspace.

Suppose $v_1,...,v_l$ are not in the nullspace and $v_{l+1},...,v_n$ are.

Then, for every vector $v\in V$ we have

$$v=\sum_{i=1}^n c_i v_i$$

and so

$$Tv=\sum_{i=1}^n c_i Tv_i$$

$$=\sum_{i=1}^l c_i Tv_i$$

and so range $T=\text{ span }(Tv_1, ...,Tv_l)$. Since dim range $T=l$ and there are $l$ vectors in $(Tv_1, ..., Tv_l)$ it is a basis for range $T$.

Now we expand this basis into a basis for $W$

$$(Tv_1, ...,Tv_l,u_1,...,u_{m-l})$$

The matrix of $T$ relative to $(v_1,...,v_n)$ and $(Tv_1, ...,Tv_l,u_1,...,u_{m-l})$ has the desired properties.

Is this proof correct?

Answer 1

Based on the comments to the original question, I will try to fix the original proof.

First, however, I would like to try to write the simpler proof suggested by Anne Bauval.

Here it is

Let's first define some variables:

• $T:V\to W$

• dim range $T=l$

• dim $V=n$

• dim $W=m$

We know that

$$\text{dim null}\ T=\text{dim} V-\text{dim range}\ T=n-l$$

Let $(u_1,...,u_{n-l})$ be a basis of null $T$.

Expand this to a basis of $V$: $(u_1,...,u_{n-l},v_1,...,v_l)$.

Then, for any $v\in V$, we can write

$$v=\sum_{i=1}^{n-l} a_i u_i +\sum_{i=1}^l b_i v_i$$

$$Tv=\sum_{i=1}^l b_iTv_i=\sum_{i=1}^l b_iw_i$$

Thus, the vectors $(w_1,...,w_l)$ span range $T$. Since dim range $T=l$ then these vectors are a basis for range $T$.

Now, $l\leq m$ and $l\leq n$.

Thus, it is always the case that $l\leq m$, which means that either $(w_1,...,w_l)$ is a basis for $W$ (if $l=m$) or we can expand this basis to become a basis of $W$

$$(w_1,...,w_m)$$

In any case, we end up with a basis of $W$ and when we map the basis $(u_1,...,u_{n-l},v_1,...,v_l)$ using $T$ the resulting vectors in $W$ do not involve multiples of $w_{l+1},...,w_m$.

In other words, as we've seen, the vectors $v_1,...,v_l$ get mapped to $w_1,...,w_l$ and $u_1,...,u_{n-l}$ get mapped to zero.

If we reorder the basis of $V$ to

$$v_1,...,v_l,u_1,...,u_{n-l}$$

then we get the exact matrix that is asked for.

Answer 2

There are essentially two ways to construct the required base of $V$ and $W$, which are "dual" to each other, starting either in $V$ or $W$. Since the previous answer started in $V$, I'll give the dual construction, starting in $W$:

The dual proof:

By starting with a basis of $\alpha(V)$ and extending it to a basis of $W$ we may find a basis $\{w_1,\ldots,w_m\}$ of $W$ such that $\{w_1,\ldots,w_r\}$ is a basis of $\alpha(V)$ ($1\leq r \leq m$).

Now pick vectors $v_1,\ldots,v_r \in V$ satisfying $\alpha(v_i)=w_i$, $1\leq i\leq r$ and set $S=\text{span}\{v_1,\ldots,v_r\}$. It is immediate from the definition of the $v_i$s that $\alpha_{|S}\colon S\to W$ is an injective linear map with image $\alpha(V)$.

Next we claim that $V = S\oplus K$, where $K=\text{ker}(\alpha)$. For this, first note that $K\cap S = \text{ker}(\alpha_{|S})=\{0\}$. Next, for any $v\in V$, we have $\alpha(v)\in \alpha(V)=\alpha(S)$ hence there is some $s \in S$ such that $\alpha(s)=\alpha(v)$, and thus $v = s+(v-s) \in S+K$ as required.

But now picking a basis of $K$, say $\{u_1,\ldots,u_n\}$ we see that the matrix of $\alpha$ with respect to the basis $\{v_1,\ldots,v_r\}\cup\{u_1,\ldots,u_n\}$ of $V$ and $\{w_1,\ldots,w_r\}\cup\{e_1,\ldots,e_m\}$ of $W$ has the required form.

$\blacksquare$

Note that the theorem can be phrased as saying that the only "invariant" of a linear map $\alpha\colon V\to W$ is its rank, i.e. the only property of a matrix representing $\alpha$ with respect to choices of bases for $V$ and $W$ which is independent of the choice of basis made, is the rank of that matrix. In the language of group actions, this says that the action of $\mathrm{GL}(V)\times\mathrm{GL}(W)$ on $L(V,W)$ has $\dim(V)+1$ orbits, where an orbit is the set of all linear maps of a given rank $k$, where $0\leq k \leq \dim(V)$.

Moreover, the theorem also implies the rank-nullity theorem, namely that $\dim(V) = \dim(\alpha(V))+ \dim(\text{ker}(\alpha))$ (indeed in the proof above, this is contained in the step where we check that $V=S\oplus K$).

Finally, the most concrete way to prove the theorem is to use the methods we use to solve (homogeneous) linear systems of equations: If you are given an explicit linear map, then it will almost surely be given in terms of its matrix $A$ with respect to some bases of $V$ and $W$. If the $j$-th column has $a_{ij}\neq 0$ and $a_{kl}=0$ for all $(k,l)$ with $k<i$, we can move the first $i-1$ rows of $A$ to become the last $i-1$ rows, and swap columns $1$ and $i$ (these operations correspond to reordering the given bases of $V$ and $W$). Now by using row operations we may modify $A$ so that its first column becomes equal to $(1,0,\ldots,0)^\intercal$, where the row operations correspond to modifying the basis of $W$. Similarly, we can use column operations to modify the first row of into the form $(1,0,\ldots,0)$, giving a matrix of the form $$ \left( \begin{array}{c|ccc}1 & 0 & \ldots & 0 \\ \hline 0 & & & \\ \vdots & & A_1 & \\ 0 & & & \end{array}\right) $$ Now if $A_1=0$ we are done, otherwise we iterate -- find a column with a non-zero entry in the highest row in which $A_1$ has nonzero entries, and perform the same operations as before. Since this process must terminate in at most $\text{min}\{n,m\}$ steps, the result follows.

In essence, in the concrete argument, one starts with bases of $V$ and $W$ already given to you, and show how they can be modified to yield bases of $V$ and $W$ with the required property. In the more abstract argument, one gives oneself the freedom to choose bases for various subspaces.