How to show that matrix over $\mathbb{F}_2^{m \times n}$ is full rank $\iff$ it has square invertible submatrix $\in \mathbb{F}_2^{m \times m}$? Let $A \in \mathbb{F}_2^{m \times n}$,  $m\leq n$. Then $A$ is a full rank matrix $\iff $ $A$ has a square invertible $m \times m$ submatrix.
I can prove sufficiency, but have problems with necessity.
Proof. a) Sufficiency. If $A$ is a full rank then $rank A = m$. It means that there are $m$ linearly independent columns in matrix $A$, i.e. there is square $m \times m$ submatrix in $A$.
How to prove necessity?
 A: The equivalence reduces to the following: a square $m \times m$ matrix $A$ is invertible iff it has full rank.
If $A$ has full rank, then the columns of $A$ form a basis $(c_i)$ of $\mathbb F_2^m$. Then $A$ is the change of basis matrix from the standard basis $(e_i)$ to the basis $(c_i)$. Any change of basis matrix is invertible; the inverse of $A$ is the change of basis matrix for $(c_i)$ to $(e_i)$.
Conversely, we can use the following criterion. We work over any field $F$. Take a $k$-tuple of column vectors in $F^m$ and let $A$ be the matrix with those columns. Consider the linear map $F^k \to F^m : v \mapsto Av$, let's denote it $f_A$. Then the vectors are:


*

*linearly independent iff $f_A$ is injective.

*a spanning set iff $f_A$ is surjective.

*a basis iff $f_A$ is an isomorphism.


This is really just a reformulation of what it means to be linearly independent/surjective/a basis.
This gives both directions:


*

*$A$ is invertible
iff (because sending a linear map to its matrix representation is a ring isomorphism $\operatorname{End}_F(F^m) \to M_{m\times m}(F)$, i.e. $f_{A+B} = f_A + f_B$ and $f_{AB} = f_Af_B$)

*$f_A$ is invertible
iff (by the criterion)

*the columns of $A$ form a basis, i.e. $A$ has full rank.

