Skip to main content
co.combinatorics
Link
Goldstern
  • 14k
  • 1
  • 47
  • 71
Source Link

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?