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$ – punctured dusk May 13 '18 at 8:58
  • $\begingroup$ Do you mean it contains a square invertible submatrix? $\endgroup$ – Bernard May 13 '18 at 9:05
  • $\begingroup$ @Bernard Yes, sorry, I've edited. $\endgroup$ – chopchopa May 13 '18 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 '18 at 9:09

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 '18 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.