0

If a matrix $A$ (it doesn't need to be a square matrix) has rank $r$, is it always possible to choose $r$ rows and $r$ columns in $A$ such that the matrix $B$ formed by removing the rows and columns that are not selected also has rank $r$, i.e., $B$ is invertible? If so, how can this be proven?

HelloGoodbye
  • 571
  • 2
  • 12
  • What have you tried? As a guess, I'd suggest picking $r$ linearly independent columns, and $r$ linearly independent rows, and then combine them into an $r \times r$ matrix by deleting the rows and columns not picked. – Richard Jensen Aug 27 '20 at 12:51
  • 1
    @RichardJensen I also realized that! So I answered my own question. – HelloGoodbye Aug 27 '20 at 12:52
  • For the columns you will use the pivot columns in Gauss Jordan elimination. But I don't recall any snappy argument why this is true. And it's usually called "rank" I think. – Jake Mirra Aug 27 '20 at 12:52
  • @JakeMirra Thanks. I proved the conjecture in my answer, and I have changed "rang" to "rank." – HelloGoodbye Aug 27 '20 at 12:58

1 Answers1

1

If $A$ has rank $r$ it has at least $r$ rows. If it has more than $r$ rows, some of the rows can be formed by combining the other rows linearly, and can therefore be removed to form a matrix $A^-$ with only $r$ rows but also with the rank $r$. The same goes for the columns, so if $A^-$ has more than $r$ columns, some of them can be removed to form an $r$-by-$r$ matrix $B$, also of rank $r$.

HelloGoodbye
  • 571
  • 2
  • 12
  • It is not clear, after you remove some of the rows, that the columns are still rank r. – Jake Mirra Aug 28 '20 at 04:04
  • @JakeMirra From the definition of matrix rank, i.e., the dimension of the vector space generated (or spanned) by its columns, or equivalently, the dimension of the vector space generated by its rows, it should be pretty straightforward. What is it that is unclear? – HelloGoodbye Aug 28 '20 at 11:03