BIMSA >
BIMSA-HSE Joint Seminar on Data Analytics and Topology
Homological obstructions to the existence of matrix diagonalization algorithms
Homological obstructions to the existence of matrix diagonalization algorithms
Organizers
Speaker
Anton Ayzenberg
Time
Monday, October 27, 2025 8:00 PM - 9:00 PM
Venue
A6-101
Online
Zoom 468 248 1222
(BIMSA)
Abstract
In applied linear algebra many problems reduce to finding eigenvalues of a real symmetric matrix A of size n. This can be done quite efficiently with asymptotical algorithms, such as QR-algorithm. Essentially, the algorithm produces a sequence A0, A1, A2, ... of isospectral matrices such that A0=A, and lim Ai is diagonal. In practice, the initial matrix A is usually sparse, meaning that the number of non-zero entries is much less than n^2. In computations with really large matrices, RAM happens to be a bottleneck, so the meaningful theoretical question: is there a diagonalization algorithm all of whose intermediate steps Ai belong to the same sparsity class as A?
The answer depends on the sparsity class. For Hessenberg matrices, i.e. matrices of staircase shape, QR-algorithm does the job. Our main result: non-Hessenberg sparsity classes (matrices that cannot be reduced to staircase shape by permutation of rows and columns) do not admit a diagonalization algorithm.
To prove this, we investigated topology of the manifold M(Γ, λ) of all sparse matrices with the specified spectrum λ, for each sparsity class Γ. Some particular cases are well-known: real full flag manifold (for full matrices), Tomei manifold (for tridiagonal matrices), twins of real Hessenberg varieties (for Hessenberg matrices). We made a systematic study of all sparsity classes and proved the alternative:
(1) If Γ is of Hessenberg class then the total Betti number β(M(Γ,λ)) equals n!.
(2) For any non-Hessenberg Γ we have β(M(Γ,λ)) > n!. In this case Morse theory implies our main result.
This alternative is proved by combination of classical results in structural graph theory, our recent results in toric topology, and a number of computational experiments with cohomology of sheaves over finite posets.
In my talk, I will explain the theories and theorems behind the proof, omitting the mathematically loaded details. The talk is based on my works with V. Buchstaber, V. Cherepanov, M. Masuda, G. Solomadin, and K. Sorokin.
The answer depends on the sparsity class. For Hessenberg matrices, i.e. matrices of staircase shape, QR-algorithm does the job. Our main result: non-Hessenberg sparsity classes (matrices that cannot be reduced to staircase shape by permutation of rows and columns) do not admit a diagonalization algorithm.
To prove this, we investigated topology of the manifold M(Γ, λ) of all sparse matrices with the specified spectrum λ, for each sparsity class Γ. Some particular cases are well-known: real full flag manifold (for full matrices), Tomei manifold (for tridiagonal matrices), twins of real Hessenberg varieties (for Hessenberg matrices). We made a systematic study of all sparsity classes and proved the alternative:
(1) If Γ is of Hessenberg class then the total Betti number β(M(Γ,λ)) equals n!.
(2) For any non-Hessenberg Γ we have β(M(Γ,λ)) > n!. In this case Morse theory implies our main result.
This alternative is proved by combination of classical results in structural graph theory, our recent results in toric topology, and a number of computational experiments with cohomology of sheaves over finite posets.
In my talk, I will explain the theories and theorems behind the proof, omitting the mathematically loaded details. The talk is based on my works with V. Buchstaber, V. Cherepanov, M. Masuda, G. Solomadin, and K. Sorokin.