Homological obstructions to existence of diagonalization algorithms forsparse matrices [Anton Ayzenberg (Faculty ofComputer Science, HighelSchool ofEconomics, and Noeon Research)

Abstract

For a simple graph on n vertices, consider a space M(, ) of all -shaped Hermitian matrices of sizen with a given simple spectrum . Here a graph is used to encode a sparsity type of a matrix. For ageneric spectrum, the manifold M(, )is smooth and carries a canonical torus action with isolatecfixed points, making it a subject of interest in toric topology

We proved an alternative:

(1) is a proper interval graph. Matrices have Hessenberg shape. The manifold M(, ) of suchmatrices is cohomologically equivariantly formal. The total Betti number (M(,) equals n!. There exisiasymptotical diagonalization algorithms for such matrices (e.g. QR-algorithm and Toda flow).(2) is not proper interval. M(, )is not equivariantly formal. We have (M(, ))>n!. No asymptoticadiagonalization algorithm of Morse-Smale type exists for such sparsity shapes.

The same alternative is valid for real symmetric matrices.

The proof required two principal steps, theoretical and computational. We proved a general result irtoric topology relating equivariant formality of manifolds with torus actions with acyclicity of theiunderlying combinatorial structures, face posets. We then computed, on our Lab's clusterhomology of face posets of specific isospectral matrix manifolds and GKM-sheaves - to prove thaithese manifolds are not equivariantly formal without computing their own cohomology directly.

This talk is based on my works with V. Buchstaber, V. Cherepanov, M. Masuda, G. Solomadin, andK. Sorokin.