Weisstein's Conjecture

Author

Eric W. Weisstein
March 18, 2016

This notebook downloaded from http://mathworld.wolfram.com/notebooks/LinearAlgebra/WeissteinsConjecture.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/WeissteinsConjecture.html.

©2016 Wolfram Research, Inc. except for portions noted otherwise

Statement

The numbers of positive eigenvalued (0,1)-matrices for , 2, ... are 1, 3, 25, 543, 29281, ... (OEIS A003024). Weisstein's conjecture (July 10, 2003) proposed that positive eigenvalued (0,1)-matrices were in one-to-one correspondence with labeled acyclic digraphs on n nodes, and this was subsequently proved by McKay et al. (2003, 2004).

http://arXiv.org/abs/math.CO/0310423

Compute

PositiveEigenvaluedQ[{{a_}}]:=a>0
PositiveEigenvaluedQ[m_]:=Positive/@And@@Eigenvalues[m]

PositiveDefiniteQ[m_]:=PositiveEigenvaluedQ[m+Transpose[m]]

ListMatrices[n_,l_List:{0,1}]:=Partition[#,n]&/@Flatten[Outer[List,Sequence@@Table[l,{n^2}]],n^2-1]

Table[Print[{n,Count[ListMatrices[n],_?PositiveEigenvaluedQ]//Timing}],{n,4}];

FindSequenceFunction[{1,3,25,543}]

Search OEIS

http://oeis.org/A003024

Formula

Labeled acyclic digraphs on n nodes

Harary and Palmer (1973, p. 19); Robinson (1973, pp. 239–273)

(Subscript[a, n])==(∑_(k=1)^n)(((-1))^(k-1))(({{n}, {k}}))(2^(k(n-k)))(Subscript[a, n-k])

with (Subscript[a, 0])==1

a[0]=1;
a[n_]:=a[n]=Sum[(((-1))^(k-1))Binomial[n,k](2^(k(n-k)))a[n-k],{k,n}]

Array[a,5]