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

Thomas Scheuerle ts181 at mail.ru
Fri Aug 11 20:15:36 CEST 2023

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 …

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

More information about the SeqFan mailing list