Torsten Sillke, 1997-12-12
Problem:
Count the number A(n) of symmetric {-1, +1} matrices of order n
with non negative row (column) sums.
All matrices for n=2 and n=3:
A(2) = 5
+ + + + - + - + + -
+ + + - + + + - - +
A(3) = 14
+ + + + + + + + + - + + + + + - + + - + +
+ + + + + + + - + + + + + - + + + + + - +
+ + + + + - + + + + + + + + - + + - + + +
+ - + + + - + + + - + + - + + + + - + - +
- + + + + + + + - + - + + + - + - + - + +
+ + + - + + + - + + + - + - + - + + + + -
Let S(n,k) be the number of symmetric {-1, +1} matrices of order n
with the condition to the first k rows to have non negative sums.
Lemma:
S(n,k-1) <= 2 * S(n,k) for 1 <= k <= n
Proof:
For every matrix counted in S(n,k-1) but not in S(n,k) there
is a matrix counted in S(n,k) too. If the k-th row sum is -r
replace the row with a vector of row sum r. Then change the
r-th column too. We must insure the non negative sum condition
for the first k-1 rows. This is satisfied if we never change
a +1 into a -1. Thus a involution is induced via [1, 2] a
symmetric chain decomposition of the posets of subsets of {1,..,n}.
As we have S(n,0) = 2^(Binomial(n+1,2)) and S(n,n) = A(n) we
have the inequality:
2^(Binomial(n+1,2)) >= A(n) >= 2^(Binomial(n,2)).
Lets look at the question as a problem of probability. What is
the probability that a random symmetric {-1, +1} matrice of order n
has no row with negative sum.
If the non negative sum condition of the rows were independent,
we would get A(n) / S(n,0) = 1 / 2^n. But each row with positive sum
increases the probability that the other row sums are non negative too.
Achim Flammenkamp conjectures that the right order of the
probability is 1/2^(n/2) at least for n even.
Prop 1: (Achim Flammenkamp, 1987)
A(n) is odd iff n is a power of two.
Achim constructed an involution on this set of matrices,
which has one fixpoint iff n is a power of two.
Table of A(n): (Achim Flammenkamp, Torsten Sillke)
-------------- 1987 for n=1..16, 1998-09 for n=17
1 1
2 5
3 14
4 315
5 2634
6 301262
7 8035168
8 4451407563
9 392447922178
10 1028823851939030
11 306635655405986312
12 3743721825782942609558
13 3832881704712490758507152
14 215313862348697780762374273824
15 766493362781127793638943080523776
16 196222469681558506008588371784165178651
17 2452358136558134202145977229121349160510450
EIS entry:
----------
%I A027832
%S A027832 1,5,14,315,2634,301262,8035168,4451407563,392447922178,
%T A027832 1028823851939030,306635655405986312,3743721825782942609558,
%U A027832 3832881704712490758507152,215313862348697780762374273824
%N A027832 Symmetric {-1, +1} matrices of order n with nonnegative row and column sums.
%O A027832 1,2
%K A027832 nonn
%D A027832 Torsten Sillke and Achim Flammenkamp, unpublished.
References:
-----------
[1] Ian Anderson,
Combinatorics of Finite Sets,
Oxford Sci. Publ, 1987
(Chap. 3.1: Symmetric Chain Decompositions)
[2] C. Greene, D. J. Kleitman,
Strong versions of Sperner's Theorem,
Journal of Combinatorial Theory, (A) 20 (1976) 80-88
Computation Times:
(n,t) = (matrix order, tabulate sum-vectors for matrix order)
(14,7) 3.3 min HP 9000/778
(15,8) 1 h HP 9000/778
(15,9) 19.5 h HP 9000/778
(16,8) 8 h HP 9000/778
(17,9) 215 h HP 9000/778 1998-09-18
--
mailto:Sillke@mathematik.uni-bielefeld.de