MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a rectangular $(m \times n)$ matrix $\underline E_1$ with $m < n$ that has only $0$ or $1$ entries. It has exactly one $1$ entry in each row and not more than one $1$ entry in each column. Consider it being a selection of $m$ rows out of a $(n \times n)$ permutation matrix $\underline P$.

Given $\underline E_1$ I'm looking for an elegant way to describe the set $\mathcal{P}$ of $((n-m) \times n)$ matrices so that any $\underline E_2 \in \mathcal{P}$ combined with $\underline E_1$, like so

$\underline E = \begin{pmatrix} \underline E_1 \\\ \underline E_2 \end{pmatrix}$

forms a valid $(n \times n)$ permutation matrix $\underline E$, i.e. something like $\mathcal{P} = \operatorname{percomp}_n( \underline E_1 )$ (there are $(n-m)!$ elements in $\mathcal{P}$)

Is there anything like this used in mathematical parlance already?

share|cite|improve this question
up vote 1 down vote accepted

You get all possible $E_2$ by starting with an $(n-m) \times (n-m)$ permutation matrix, and expand it to being $(n-m) \times n$ by inserting columns of zeros under each of the ones of $E_1$. That is, there's an easy bijection between your set and the order $(n-m)$ permutation matrices. I think you knew this already.

I guess what I'm driving at is that even if there is some canonical name for this object in some field of mathematics, the set that you want to name is simple enough that you can describe it in one sentence. If you need to give this set a name, just call it $percomp_n(E_1)$, like you wanted to do. People do this all the time. Indeed, most of us would be even more confused if you dig up an obscure, but technically correct, name.

share|cite|improve this answer

It's basically a coset? You have an injective function to extend to a permutation. If it were the identity on the first m elements you'd have the n - m other elements to permute. So if you multiply on one side by a permutation matrix, you should have a coset of the smaller symmetric group.

share|cite|improve this answer
That's not quite what I'm looking for. I'd like to describe the set of complements and not have to create new definitions by myself. – Marcus S. Feb 20 '12 at 8:07

Your Answer


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.