[seqfan] Re: Number of n x n {-1, 1}-matrices which have only eigenvalues with strictly negative real part.

[Hugo Pfoertner]

The topic is not entirely new. To see which similar problems have already
been covered, you might want to look at the "binary matrices" index entry
and search for terms such as eigenvalues or positive definite.
https://oeis.org/index/Mat#binmat
See e.g. https://oeis.org/A055165 or https://oeis.org/A085656
I did some computations myself a few years ago. The crossrefs in these
sequences may also lead to further finds
https://oeis.org/A086510 , https://oeis.org/A098148




On Mon, Aug 14, 2023 at 4:21 PM Alex Meiburg <timeroot.alex at gmail.com>
wrote:

> If you negate each element, you negate each eigenvalue, so then you're
> looking for strictly positive eigenvalues. That seems a bit more natural to
> count.
>
> If the matrix were symmetric, then there's the rich theory of PSD matrices.
> Sylvester's criterion, for instance, would be a powerful way to search
> quickly by computer. But the theory falls apart quickly when the matrices
> aren't symmetric. And what attention there is, is about matrices with xMx >
> 0, not positive real parts of eigenvalues (two conditions which are
> equivalent only if the matrix is symmetric).
>
> On Mon, Aug 14, 2023, 08:49 <israel at math.ubc.ca> wrote:
>
> > Since the trace is the sum of the eigenvalues, it's certainly true that
> > the entries of -1 must be the majority on the main diagonal.
> >
> > Cheers,
> > Robert
> >
> > On Aug 14 2023, Thomas Scheuerle via SeqFan wrote:
> >
> > >Hello Seqfan list,
> > >
> > >I have planned to prepare a sequence
> > >which enumerates all matrices where all entries are -1 or 1
> > >and the eigenvalues have real parts < 0.
> > >
> > >Two of the 20  3 x 3 matrices would be:
> > >    -1     1     1
> > >    -1    -1     1
> > >    -1     1    -1
> > >
> > >    -1     1     1
> > >     1    -1     1
> > >    -1    -1    -1
> > >            ...
> > >By naively counting I got for a(1) to a(5) already this values:
> > >1, 2, 20, 640, 97824, ...
> > >
> > > I noticed that there are likely many algorithms which are faster and
> > more
> > > sophisticated. Also I expected that this problem was already researched
> > > somewhere O
> > >
> > > As my knowledge is very limited I propose this topic here to allow some
> > > brainstorming of the crowd.
> > >
> > > The first improvement could be based on the main diagonal and the trace
> > > of the matrices. It appears that negative entries on the main diagonal
> > > must be at least in the majority. n = 5 is the least n where not all
> > > entries on the main diagonal are -1.
> > >
> > >Also I lack the sufficient knowledge to decide which symmetries are
> valid.
> > >
> > > Another idea would be some heuristics to exclude determinant = 0
> somehow
> > > fast ?
> > >
> > >But frankly I have not any good concepts yet.
> > >
> > >Thank you very much
> > >
> > >Thomas Scheuerle
> > >
> > >--
> > >Seqfan Mailing list - http://list.seqfan.eu/
> > >
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>