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
    Incidentally, if you are doing these things algorithmically, I might be interested in how you are finding the actual permutations, etc. PLU is common, and I have code for Bruhat, and I suspect this problem is important for block preconditioning, so you might be developing a reasonable useful collection of routines.2011-05-01
  • 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.

  • 0
    I'd have to pay $29.95 to follow that link.2011-05-01
  • 0
    Here's a link to a free document with a proof of this expansion, which often seems to be called the "generalized Laplace expansion": http://www.imvibl.org/imvibl/buletin/bultetin_15_2008/buletin_15(2008)5-7.pdf2011-05-01
  • 0
    Another cool version: http://www.t-kougei.ac.jp/research/pdf/vol1-25-09.pdf2011-05-01
  • 0
    However, I'm not entirely sure I see Robert Israel's proof. The expansion is over all sorts of row *and* column selections. Maybe the row selections with the identity column selection are all 0, and it is up to the other column selections to make up the difference?2011-05-01
  • 0
    @Jack: As I understand it, the expansion is over all row selections for a fixed column selection. So you can select the first $m$ and last $n-m$ columns and get exactly the sum that you need for Robert's argument.2011-05-01
  • 0
    @Joriki: Marvelous, thanks. I misread *both* papers. :-)2011-05-01
  • 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