most recent 30 from http://mathoverflow.net 2013-05-20T18:01:27Z http://mathoverflow.net/feeds/question/74728 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/74728/counting-the-additive-decompositions-of-a-quadratic-symmetric-empty-diagonal herrsimon 2011-09-07T09:47:31Z 2011-09-07T11:30:57Z

<p>Dear community,</p> <p>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.</p> <h2>Short version</h2> <p>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?</p> <h2>Detailed version</h2> <p>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 <code>$\{ \sigma_1, \sigma_2, \ldots, \sigma_n \}$</code> a <em>decomposition</em> for $A$.</p> <p>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. </p> <p>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. </p> <p>My <strong>question</strong> is the following: How many decompositions are there in total?</p> <h2>Example</h2> <p>Let me give you a very simple example for the situation in the case $n=3$. </p> <p>If <code>$$A = \begin{pmatrix} 0 &amp;1 &amp;1 \\ 1 &amp;0 &amp;1 \\ 1 &amp;1 &amp;0 \end{pmatrix} $$</code></p> <p>the only possible way to write this as a sum of permutation matrices (up to order of summands) is </p> <p><code>$$ A = \begin{pmatrix} 0 &amp;0 &amp;1 \\ 1 &amp;0 &amp;0 \\ 0 &amp;1 &amp;0 \end{pmatrix} + \begin{pmatrix} 0 &amp;1 &amp;0 \\ 0 &amp;0 &amp;1 \\ 1 &amp;0 &amp;0 \end{pmatrix}, $$</code> and the corresponding decomposition is <code>$\{ (1 3 2), (2 3 1) \}$</code>.</p> <p>Thanks for your help,</p> <p>Simon</p>

http://mathoverflow.net/questions/74728/counting-the-additive-decompositions-of-a-quadratic-symmetric-empty-diagonal/74733#74733 Brendan McKay 2011-09-07T11:22:27Z 2011-09-07T11:22:27Z

<p>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.</p>