show/hide this revision's text 3 Removed the subquestion as I answered it myself; edited body

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?

As a subquestion: Is there a matrix $A$ with a decomposition not closed under taking inverses, i.e. with a decomposition containing $\sigma_i$ but not $\sigma_i^{-1}$? Or to state this differently: Can non-symmetric, fixed-point free permutation matrices which are pairwise non-inverse add up to a symmetric matrix?

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
show/hide this revision's text 2 deleted 14 characters in body

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.

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

As a subquestion: Is there a matrix $A$ with a decomposition not closed under taking inverses, i.e. with a decomposition containing $\sigma_i$ but not $\sigma_i^{-1}$? Or to state this another waydifferently: Is there another way for the Can non-symmetric, fixed-point free permutation matrices to which are pairwise non-inverse add up to something a symmetric , other than adding their inversesmatrix?

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
show/hide this revision's text 1

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.

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

As a subquestion: Is there a matrix $A$ with a decomposition not closed under taking inverses, i.e. with a decomposition containing $\sigma_i$ but not $\sigma_i^{-1}$? Or to state this another way: Is there another way for the non-symmetric permutation matrices to add up to something symmetric, other than adding their inverses?

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