A086215 & A085656

[Max]

I confirm that a(4)=79505.
I have also found that a(5)=105311665 and a(6)=642005451319 giving

%S A086215 1, 7, 311, 79505, 105311665, 642005451319

My approach is following:

We iterate over all symmetric positive definite matrices M of size nxn
with elements from {-2,0,2} on the main diagonal and the other elements from {-2,-1,0,1,2}.
For every such matrix we count the number of matrices P with element from {-1,0,1}
such that P + P^T = M.

There are necessary conditions for a symmetric matrix to be positive definite, see
http://mathworld.wolfram.com/PositiveDefiniteMatrix.html
Applied to the matrix M, they imply that M has 2's on the main diagonal and the other elements must belong {-2,-1,0,1}.

Another trick speeding up iterations over M comes from the following criterion of positive definiteness (also known as Sylvester's criterion):
matrix M is positive definite iff the determinants associated with all upper-left submatrices of M are positive.

It suggests that the matrix M should be constructed as a sequence of upper-left submatrices of size kxk where k=1..n.
If a submatrix of size kxk has a positive determinant then we extend it to a submatrix of size (k+1)x(k+1) in all possible ways and so on.
On the other hand, if the determinant of some submatrix is zero or negative then there is no sense to extent this submatrix further.

The number of matrices P with element from {-1,0,1} such that P + P^T = M can be computed simply as
3^z * 2^t
where z is the number of zeros below the main diagonal in M
and t is the number of plus-minus ones below the main diagonal in M.

The described approach was implemented in the following PARI code:

{ a(n) = M=matrix(n,n,i,j,2*(i==j)); r=0; b(1); r }
{ b(k) = local(v,z,t);
   if(k>n,
     z=0; t=0;
     for(i=1,n, for(j=1,i-1,
       if(M[i,j]==0,z++);
       if(abs(M[i,j])==1,t++)
     ));
     r+=3^z*2^t;
     return
   );
   forvec(x=vector(k-1,i,[-2,1]),
     for(i=1,k-1,M[k,i]=M[i,k]=x[i]);
     if( matdet(vecextract(M,2^k-1,2^k-1),1)>0, b(k+1) )
   )
}


Similarly, it possible to extend A085656 which counts the number of nxn positive definite matrices with elements {0,1}.
I have computed first 3 more terms:

%S A085656 1, 3, 27, 681, 43369, 6184475, 1688686483, 665444089745

Max


wouter meeussen wrote:
> is a wise rule.
> So I tried to extend it.
> 
> %I A086215
> %S A086215 1, 7, 311
> %N A086215 Number of (-1, 0, 1) n X n matrices that are positive definite.
> %H A086215 Eric Weisstein's World of Mathematics, < a href =
>   "http://mathworld.wolfram.com/PositiveDefiniteMatrix.html" >
>     Positive Definite Matrix < /a >
> %Y A086215 Sequence in context :
>         A082168 A015005 A002437 this_sequence A082160 A002000 A049686
> %Y A086215 Adjacent sequences :
>     A086212 A086213 A086214 this_sequence A086216 A086217 A086218
> %K A086215 nonn, more
> %O A086215 1, 2
> %A A086215 Eric W. Weisstein (eric(AT)weisstein.com), Jul 12, 2003
> 
> and found a(4)=79505 after a bit over an hour.
> 
> But ... it needs checking, since the listing of the eigenvalues depends on numeric, not symbolic
> computation. These eigenvalues then need to be checked for being real and strictly positive, and an
> error close to zero is not uncommon in such calculations.
> 
> Therefore I tried a different attack :
> instead of
> generating all 729*729 (-1,0,1)'P' matrices by adding all 729 lower triangular ones to their
> transposes in all possible ways, and then adding to that all 31 diagonal (-1,0,1)'D' matrices with
> positive trace (pigeonhole:: all eigenvalues positive implies positive trace), and then count those
> with all eigenvalues >0 , or equivalently,
> generate T= P+D; count the T that satisfy Eigenvalues of (T+transpose(T))/2 >0
> I rather did:
> first take the union of all  P+transpose(P) -matrices, and combine those with the diagonal
> D-matrices into T'-matrices, only then count the T' that satisfy Eigenvalues of T' >0.
> 
> What's so different?
> Aha, there are only 393 different T' matrices we need to calculate eigenvalues for.
> but each of those can be generated by many different P-matrices.
> 
> 8 T-matrices, each resulting from 64 different P matrices giving the same (P+tr_P) =512
> 48 T-matrices, each from 96 different P matrices =4608
> 120 T-matrices, each from 144 different P matrices =17280
> 144 T-matrices, each from 216 different P matrices =31104
> 60 T-matrices, each from 324 different P matrices =19440
> 12 T-matrices, each from 486 different P matrices =5832
> 1 T-matrix, resulting from 729 different P matrices giving the same (P+tr_P) =729
> 
> 8+48+120+144+60+12+1 =393, and
> 512+4608+17280+31104+19440+5832+729 =79505 (* so that checks out*)
> the lowest eigenvalue(s) are 0.133975, well away fom zero, so that checks out too.
> 
> ergo : %S A086215 1, 7, 311, 79505
> 
> Wouter.
> 
> 
> 
> 
> 
>