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?

  • $\begingroup$ Necessity means the implication from right to left, sufficiency left to right. Is this what you mean? $\endgroup$ May 13, 2018 at 8:58
  • $\begingroup$ Do you mean it contains a square invertible submatrix? $\endgroup$
    – Bernard
    May 13, 2018 at 9:05
  • $\begingroup$ @Bernard Yes, sorry, I've edited. $\endgroup$
    – chopchopa
    May 13, 2018 at 9:07
  • $\begingroup$ @barto No, I thought necessity means the implication from left to right. I've edited the question. In that case I need to proof necessity. $\endgroup$
    – chopchopa
    May 13, 2018 at 9:09

1 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.
  • $\begingroup$ But this prooves necessity, no? I think, sufficiency is formulated as "If there is square submatrix then A is full rank". $\endgroup$
    – chopchopa
    May 13, 2018 at 8:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .