Ytukyg

Saw this claim in this video https://www.youtube.com/watch?v=cBSf2pGYAcA&list=PL06960BA52D0DB32B&index=4 at 23m35s and struggled in vain to prove it.

Searching for it on Google proved fruitless.

Here's a simple proof. Let $V$ and $W$ be vector spaces. Let $T:Vto W$ be a linear map. Let $A$ be any matrix representing this map. Then $newcommandrk{operatorname{rank}}rk A$ is the dimension of the image of $T$, and the number of rows of $A$ is the dimension of $W$. Thus for $T$ to be surjective, we must have that the rank of $A$ is equal to the number of rows of $A$. Since row rank equals column rank, the rank of $A$ is the number of linearly independent rows of $A$. Hence $T$ is surjective if and only if the rows of any matrix representing it are linearly independent.

Edit I realized there a perhaps slightly more direct proof, which sort of mixes the proof above with the proof that row rank equals column rank.

Review of some relevant linear algebra

First recall some notions. If $V$ is a vector space over a field $K$, then the dual vector space to $V$ is defined to be $V^*:=newcommandHom{operatorname{Hom}}Hom_K(V,K)$. If $T:Vto W$ is a linear map, then its dual is $T^*:W^*to V^*$ defined by $T^*(lambda) = lambda circ T$. Also if ${v_i}$ and ${w_j}$ are bases for $V$ and $W$ with dual bases ${v_i^*}$ and ${w_j^*}$, then it is easy to show that the matrix for $T$ with respect to the $v_i$ and $w_j$s is $A_{ij}=w_j^*Tv_i$, and the matrix for $T^*$ with respect to $w_j^*$ and $v_i^*$ is $B_{ji}=(T^*w_j^*)v_i=(w_j^*circ T)v_i=w_j^*Tv_i=A_{ij}$. Thus the matrix for $T^*$ is the transpose of the matrix for $T$.

Now onto the proof

Proof

Let $T:Vto W$. Let $A$ be any matrix representing this map. Then $T$ is surjective if and only if there are no nonzero linear functionals on $W$ that vanish on the image of $T$. However if $lambda$ vanishes on the image of $T$, then we have $T^*lambda=0$, and recalling that the matrix of $T^*$ is $A^t$, we see that the coordinates of $lambda$ give an explicit linear dependence among the columns of $A^t$ (which are the rows of $A$). Conversely any linear dependence among the rows of $A$ gives such a linear functional $lambda$, proving that $T$ is not surjective.

For a matrix A to be onto, there has to be a pivot in every row. To test the linear independence of the rows, you can look at A$^T$ and row reduce. If every column of A$^T$ has a pivot, the columns are linearly independent. Note that the columns of A$^T$ are the rows of A. I leave it to you to show that the row reduction doesn't affect the linear independence.