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