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

Question

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?

Answer 1

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:

1. linearly independent iff $f_A$ is injective.
2. a spanning set iff $f_A$ is surjective.
3. 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.