6
$\begingroup$

Dear community,

I have the following combinatorial question which I will explain in short first and then with some more detail. At the end you will find a very simple example.

Short version

Le $A \in \mathbb{N}_0^{n \times n}$ be a symmetric matrix with zeros on the diagonal, whose row- and column-sums add up to some fixed, positive integer $c$. In how many ways can we write $A$ as a sum of permutation matrices, ignoring the order of summation?

Detailed version

Suppose you have a quadratic matrix $A$ of dimension $n$ with non-negative integral entries whose row- and column-sums add up to some common number $c$. Then it is known that $A$ can be written as a sum of $c$ permutation matrices, i.e. we have that $$A = P_{\sigma_1} + P_{\sigma_2} + \ldots + P_{\sigma_c},$$ where each $P_{\sigma_i}$ is a permutation matrix representing a permutation $\sigma_i \in S_n$, $S_n$ being the symmetric group of order $n$. Let's call the set $\{ \sigma_1, \sigma_2, \ldots, \sigma_n \}$ a decomposition for $A$.

If we add the property that the diagonal of $A$ vanishes (i.e. contains only zeros), the permutation matrices $P_{\sigma_i}$ of any decomposition as above will have vanishing diagonals, too, i.e. the corresponding permutations $\sigma_i$ will have no fixed points.

If we add another property to $A$, namely that it is symmetric, we get decompositions with even more structure. Either all matrices of a decomposition are symmetric themselves (which in this framework is the case, if and only if the cycles of the corresponding permutations are all of length two), or the non-symmetric matrices add up to something which is symmetric. This is for example the case if for a given permutation $\sigma_i$, the permutation $\sigma_i^{-1}$ (inverse in $S_n$, i.e. with respect to composition) is also in the decomposition, because $P_{\sigma_i^{-1}} = P_{\sigma_i}^T$ and $P_{\sigma_i} + P_{\sigma_i}^T$ is symmetric, but this condition is not necessary.

My question is the following: How many decompositions are there in total?

Example

Let me give you a very simple example for the situation in the case $n=3$.

If $$A = \begin{pmatrix} 0 &1 &1 \\ 1 &0 &1 \\ 1 &1 &0 \end{pmatrix} $$

the only possible way to write this as a sum of permutation matrices (up to order of summands) is

$$ A = \begin{pmatrix} 0 &0 &1 \\ 1 &0 &0 \\ 0 &1 &0 \end{pmatrix} + \begin{pmatrix} 0 &1 &0 \\ 0 &0 &1 \\ 1 &0 &0 \end{pmatrix}, $$ and the corresponding decomposition is $\{ (1 3 2), (2 3 1) \}$.

Thanks for your help,

Simon

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Although you deleted this part of the question, here is a construction showing that the permutations need not come in inverse pairs is as follows: Consider $C_5 \oplus C_5$ acting on a $10$ element set with generators $a,b$ cyclically permuting disjoint $5$-element subsets while fixing the other $5$ elements. The sum of the matrices corresponding to $\{ab,a^2b^3,a^3b^4,a^4b^2\}$ is symmetric and this set is not fixed by inversion. $\endgroup$
    – Douglas Zare
    Commented Sep 7, 2011 at 10:52
  • $\begingroup$ I strongly suspect this problem is #P complete en.wikipedia.org/wiki/Sharp-P-complete . Roughly, this means that it is as hard as any counting problem. In particular, if we could give a polynomial time algorithm for exactly computing this quantity, this would imply P=NP. Since most things you would be likely to accept as an answer would imply a polynomial time algorithm, this suggests you were not receive an acceptable answer. Since I can't prove this is #P complete, I'm leaving this as a comment in the hopes that someone else can. If I have time later, I'll write up my attempts. $\endgroup$
    – David E Speyer
    Commented Sep 7, 2011 at 12:32
  • $\begingroup$ @Douglas: Yes indeed, there are even simpler examples in lower dimensions @David: Being #P complete does not exclude the possibility of nice formulas (of course it all depends on your definition of nice). I'm actually not interested in the actual numeric value but want to relate the decompositions to another quantity. For this, a (maybe recursive) formula, involving terms which are hard to compute (for example the partition function or something related) would do. $\endgroup$
    – herrsimon
    Commented Sep 7, 2011 at 21:16

1 Answer 1

Reset to default
9
$\begingroup$

In general the number of decompositions depends on the structure of the matrix, not just on its size and row sum. This is even so in the case of 0-1 matrices, where the question is equivalent to 1-factorization of regular bipartite graphs. Even very simple-looking cases are difficult, for example if the matrix is full of ones the decompositions are the Latin squares (only counted exactly up to order 11). A lower bound for the 0-1 case follows from Schrijver's lower bound on the permanent, and an upper bound follows from the van der Waerden upper bound on the permanent. These bounds are far apart. Sharper upper bounds exist for the 0-1 case with row sums not too large. Symmetry and zero diagonal don't make a great difference as far as I know. There are some asymptotic results. In the symmetric case there are asymptotic results for the number of decompositions into symmetric permutation matrices (which corresponds to 1-factorisation of regular graphs). Let us know which aspects interest you.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much! Actually I'm not looking for asymptotics but was hoping to get some "nice", maybe recursive formula - obviously this was way too naive :-) $\endgroup$
    – herrsimon
    Commented Sep 7, 2011 at 21:08
  • $\begingroup$ I don't think there is anything like that which would be useful in general. For Latin squares, nobody knows of any formula or recursion that is plausible for apply for $n=12$ even with a few decades of cpu time available. If you want to do it for some very special family of very sparse matrices, there is more of a chance. $\endgroup$
    – Brendan McKay
    Commented Sep 8, 2011 at 4:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .