Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Jack Schmidt May 1 '11 at 22:12
    
@Jack: Robert's answer if sufficient for my current needs, but if I find any useful algorithmic insights I will update. –  user3533 May 1 '11 at 22:53

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
I'd have to pay $29.95 to follow that link. –  joriki May 1 '11 at 22:14
    
Here's a link to a free document with a proof of this expansion, which often seems to be called the "generalized Laplace expansion": imvibl.org/imvibl/buletin/bultetin_15_2008/… –  joriki May 1 '11 at 22:22
    
Another cool version: t-kougei.ac.jp/research/pdf/vol1-25-09.pdf –  Jack Schmidt May 1 '11 at 22:30
    
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? –  Jack Schmidt May 1 '11 at 22:31
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. –  Robert Israel May 2 '11 at 7:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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