4
$\begingroup$

Let $n$ be an even positive integer and $W_n$ be the class of all $n\times n$ matrices with entries from the set $\{-1,0,1\}$ such that all row sums and column sums are equal to $0$.

For each $M\in W_n$, let $k(M)$ be the number of ones in $M$. I think the number of $M\in W_n$ with $k(M)$ even is much bigger than the number of $M\in W_n$ with $k(M)$ odd. Am I right?

$\endgroup$
2
  • $\begingroup$ Have you tried computer enumeration on small n? There are relatively few candidates for each row (about 1100 for n=8), and once you fill in the first three rows this cuts down on the available columns to the realm of feasibility. You could use row and column permutations to compute representatives and possibly enumerate the n=10 case. Gerhard "Ask Me About Trinary Matrices" Paseman, 2016.05.11. $\endgroup$ May 11, 2016 at 16:48
  • $\begingroup$ Adding an additional row and column of $-1$'s to an alternating sign matrix yields examples. Does a similar result hold for alternating sign matrices? $\endgroup$ Oct 4, 2021 at 13:33

1 Answer 1

6
$\begingroup$

Yes, this should be true. Here is an explanation why. Equivalently, we want to assign weights $-1,0,1$ to the edges of $K_{n,n}$ such that the sum of the weights at each vertex is $0$. One way to do this is to choose edge-disjoint cycles $C_1, \dots, C_\ell$ in $K_{n,n}$ with $\bigcup_{i=1}^\ell E(C_i)=E(K_{n,n})$. For each cycle $C_i$ we either set all its edges to have weight $0$, or we alternate its edges between $1$ and $-1$. Note that there are two ways to make the edges alternating. Conversely, every assignment of weights $-1,0,1$ to the edges of $K_{n,n}$ such that the sum of the weights at each vertex is $0$ can be decomposed in this way.

Let $C_1, \dots, C_\ell$ be a cycle-partition of $E(K_{n,n})$. Call $C_i$ half-even if $|C_i|/2$ is even and $C_i$ half-odd if $|C_i|/2$ is odd. Since $n$ is even, say $n=2k$, $K_{n,n}$ has $4k^2$ edges. Working mod $4$, we conclude that there are an even number of half-odd cycles. As noted, there are $3$ ways to assign weights to each cycle $C_i$. No matter how we assign weights to the half-even cycles, the total number of ones will always be even. Thus, the parity of the number of ones only depends on how we assign weights to the half-odd cycles $O_1, \dots, O_{2m}$. The number of ways to assign weights to $O_1, \dots, O_{2m}$ so that the total number of ones is even is $$ \binom{2m}{0}2^0+\binom{2m}{2}2^2+\dots + \binom{2m}{2m}2^{2m}. $$ By the Binomial Theorem, this is equal to $\frac{3^{2m}+1}{2}$ which is slightly more than half of $3^{2m}$ (the total number of ways to assign weights to $O_{1}, \dots, O_{2m}$).

Now, the reason there should be far more weightings with an even number of ones than an odd number of ones is because there are many cycle decompositions of $K_{n,n}$ with no half-odd cycles at all. The weightings that are generated by these cycle decompositions will always have an even number of ones, while the other ones (by the argument above) still generate more weightings with an even number of ones than an odd number of ones. Note that it is possible for different cycle decompositions to generate the same weighting, so this does not constitute a proof.

$\endgroup$
4
  • $\begingroup$ Tony Huynh: It is possible that two different cycle decompositions generate a same weighting. So I think more details of the proof are needed. $\endgroup$
    – user173856
    May 12, 2016 at 7:46
  • $\begingroup$ @user173856 I was aware of that and was careful not to use the word proof in the answer. It is instead a high-level explanation. I think it is fairly convincing though. For example, it is easy to see that $K_{2k,2k}$ can de decomposed into $4$-cycles. Taking only one such decomposition already generates $3^{k^2}$ weightings with an even number of ones. $\endgroup$
    – Tony Huynh
    May 12, 2016 at 8:13
  • $\begingroup$ @user173856 I edited the answer to stress that this is not a formal proof. Thanks. $\endgroup$
    – Tony Huynh
    May 12, 2016 at 9:14
  • $\begingroup$ Tony Huynh:Thank you very much for your help. Your explanation is most illuminating. I has been trying to complete your proof these days, but I find it is not easy to give a strict proof that the "even" weightings are more than the "odd" weightings. Do you know any known conclusions about this? $\endgroup$
    – user173856
    May 20, 2016 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.