# Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices

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) \}$.

• 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. Commented Sep 7, 2011 at 10:52
• 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. Commented Sep 8, 2011 at 4:39