Exercise 4.3.23

of columns of $B$ is independent. Now consider the $k\times n$ submatrix $C$ of $A$ obtained by deleting those rows who were deleted when we construct $B$. So $S$ is a subset of the set of columns of $C$. This means

and hence rank$(C)=k$. So this also means that the set of the $k$ rows of $C$ independent. And thus the matrix $A$ contains $k$ independent rows and hence rank$(A)\ge k$, a contradiction.

Conversely, we construct a $r\times r$ submatrix of $A$, where $r$ is rank$(A)$, to deduce that rank$(A)\le k$. Since rank of $A$ is $r$, we have $r$ independent rows, say $u_1,u_2,\dots ,u_r$. Let $D$ be the $r\times n$ submatrix such that the $i$-th row of $D$ is $u_i$. Since the set of rows of $D$ is independent, we have that

and hence rank$(D)=r$. Similarly we have $w_1,w_2,\dots ,w_r$ to be the $r$ independent columns of $D$. And si-similarly we can construct a $r\times r$ matrix $E$ such that the $i$-th column of $E$ is $w_i$. Since $E$ is a $r\times r$ matrix with $r$ independent rows, we have rank$(E)=r$. This complete the proof.