pos def matrices

[Eric W. Weisstein]

On Sat, 12 Jul 2003, N. J. A. Sloane wrote:

> 1.  Eric, I think you may be using the wrong definition of positive
> definite matrix, both in sequences A085505 and A085506 and on your web
> site.
> 
> A real matrix A is pos def (pd in this email) if x A x' > 0 for all
> nonzero real vectors x.

Happily, the definition on
http://mathworld.wolfram.com/PositiveDefiniteMatrix.html says exactly this
and so is actually correct.

> (This is not the same as all eigenvectors being positive.)
>
> (Lemma:  a real matrix A is pd iff the symmetric matrix A+A' is pd
> iff the eigenvectors of A+A' are positive)

This is where the inconsistency is.  The counts I sent as A085505 and
A085506 and listed at the bottom of PositiveDefiniteMatrix.html are
actually counts of matrices with positive eigenvalues.

As you correctly point out, this is not the same as positive definite
matrices.  For example:

PositiveEigenvaluesQ[m_]:=Positive/@And@@Eigenvalues[m]
a=Select[Matrices[3],PositiveEigenvaluesQ];
b=Select[Matrices[3],PositiveEigenvaluesQ[#+Transpose[#]]&];

Length/@{a,b}
{25,27}

c=Complement[b,a]
{{{1,0,1},{1,1,0},{0,1,1}},
{{1,1,0},{0,1,1},{1,0,1}}}

pd = ({{x, y, z}}.#.{{x}, {y}, {z}})[[1, 1]] & /@b;
And@@(Resolve[ForAll[{x,y,z},
        (x|y|z)\[Element]Reals&&x y z\[NotEqual]0,
        #>0
        ]]&/@pd)
True

I will fix this error on MathWorld.
 
> I find that the no. of pd 0,1 matrices begins 
> 1, 3, 27, 681, ...
> a new sequence (A085656).

Yes, I agree.

{253.96 Second, {0, 3, 27, 681}}

I'll compute the next term later today (unless someone beats me to it ;)

> 2.  I think your sequence A085505 is the no. of (0,1) matrices with all
> eigenvalues (real and) positive. Agreed?

Yes.
 
> And I think this is the same as the number of directed acyclic digraphs.
> But our proof needs to be rechecked.

Yes, I conjectured this based on the fact that A085505 and A003024 agree
out to n=5, so it seems very likely to be true.  It seems unlikely that
the apparent 1-1 correspondence between labeled DAGs and positive
eigenvalued (0,1)-matrices is not already known, but I've never seen it.  
I haven't tried to prove the correspondence though, so I'm very interested
to know if your proof does indeed establish the correspondence.
 
> We were misled in our earlier investigations (2 days ago) because Maple
> gives wrong answers when you ask if a matrix is pos def.  Possibly Mma
> has the same bug. Maple thinks that a non-symmetric matrix cannot be pd.

Actually, Mathematica has no built-in pd command (although writing one is
a 1-2 liner; see below), so the bug was purely in my incorrectly equating
pos. eigenvalues = pos. definite.
  
> 3.  I think your sequence A085506 is probably the number of
> (0,1,-1)-matrices with all eigenvalues (real and) positive. Can you
> confirm that?

Yes.
 
> PS.  Here is Maple:

Happily, Mathematica gets it right :)

PositiveEigenvaluesQ[m_] := Positive /@ And @@ Eigenvalues[m]
PositiveDefiniteQ[m_] := PositiveEigenvaluesQ[m + Transpose[m]]
PositiveDefiniteQ/@{
    {{2,1,0},{1,2,0},{0,0,2}},
    {{1,1,0},{0,1,0},{0,0,1}}
    }
{True,True}

Thanks again, Neil!  I wouldn't have through to connect DAGs and positive 
eigenvalued matrices without OEIS! :)

Cheers,
-E

> with(linalg);
> 
> > t1:=array(1..3,1..3,[[2,1,0],[1,2,0],[0,0,2]]);                                                
>                                                    [2    1    0]
>                                                    [           ]
>                                              t1 := [1    2    0]
>                                                    [           ]
>                                                    [0    0    2]
> 
> > definite(t1, positive_def);                                                                    
>                                                      true 
> 
> > t2:=array(1..3,1..3,[[1,1,0],[0,1,0],[0,0,1]]);              
>                                                    [1    1    0]
>                                                    [           ]
>                                              t2 := [0    1    0]
>                                                    [           ]
>                                                    [0    0    1]
> 
> > definite(t2, positive_def);                    
>                                                     false
> 
> but it is!