# Complement to part of a permutation matrix

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?

## 2 Answers

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.

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.

• 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