5
$\begingroup$

This question is similar to a previous one: Gauss Elimination with constraints, but it is different.

Given an $n \times n$ matrix $M$ and a number $1 \leq m \leq n-1$, we partition M as a block matrix: $ M=\left[ \begin{array}{cc} A & B \\ C & D \end{array}\right] $ where $A$ is an $m \times m$ matrix and $D$ is an $(n-m) \times (n-m)$ matrix. We then say that $M$ is m-good if both $A$ and $D$ are invertible.

The question: Given any invertible matrix $M \in GL_n(\mathbb{F})$ and a number $1 \leq m \leq n-1$, is it always possible to permute the rows of $M$ to make it m-good?

Note: I only care about the case $\mathbb{F}=\mathbb{Z}_p$, but I asked the question more generally because my feeling is that it doesn't matter what the field is.

  • 0
    @Jack: Robert's answer if sufficient for my current needs, but if I find any useful algorithmic insights I will update.2011-05-01

1 Answers 1

4

Using the Laplace expansion, $\det M$ is a sum of terms of the form $ \pm \det(A) \det(D)$ over all ways of partitioning the rows (see e.g. http://accessscience.com/content/Determinant/188900 : the term "Laplace expansion" is sometimes used for the cofactor expansion along a single row or column, but it's really more general). So if $\det(A) \det(D)$ was always 0, $\det(M)$ would also be 0.

  • 1
    You can look at it this way. $\det(M)$ is the sum of $(-1)^{sgn(\sigma)} \prod_j a_{j,\sigma_j}$ over all permutations $\sigma$ (which you can think of as one-to-one maps of rows to columns). If you restrict to those permutations that map a particular set of $m$ rows to the the first $m$ columns, you have one term of the Laplace expansion.2011-05-02