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

[Brendan McKay]

To an engineer, negative real parts are more natural since such matrices
are called "stable" in control theory and are rather important. That is,
without the {-1,+1} restriction.

As far as exhaustive search goes, note that the eigenvalues are unchanged
by simultaneous equal row and column permutation, which cuts the cases
by almost n!.  Also, multiplying some subset of the rows by -1 then the
same subset of the colums by -1 retains the eigenvalues. This gives another
factor of about 2^{n-1}.   It becomes a search over switching classes of
digraphs with loops.  n=6 is easy, n=7 is moderate, n=8 is plausible but
quite difficult.  The real problem is how to know in advance for most of
the matrices that they can't work so as to preemptively cut out most of 
the search.

Brendan.


On 15/8/2023 12:20 am, Alex Meiburg 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/