# Jordan Decomposition of Sparse matrix

Suppose we are given $$n \times n$$ rational matrix, $$A$$ with at most $$k$$ nonzero elements in each row and each column with $$k \ll n$$.

What is the best algorithm to compute its Jordan decomposition? What would the dependence on $$n$$ be?

• The diagonal elements of the Jordan decomposition are the eigenvalues, which are in general not rational, and not even representable by radicals. In what sense do you mean to compute them? As floating-point approximations or symbolic RootOf? – Robert Israel Jun 24 '19 at 19:26
• Sparsity of the matrix does not help much: the companion matrix of a polynomial is quite sparse... Also, for any rational matrix $A$ and any $\epsilon >0$ there exists another rational matrix that differs from $A$ less than $\epsilon$ (entrywise) and which is diagonalizable. – Dirk Jun 24 '19 at 20:20
• @ Robert Israel symbolic RootOf. – gondolf Jun 25 '19 at 3:20
• @Dirk Thank you very much – gondolf Jun 25 '19 at 3:20
• On a second thought, I am not so sure about the claim about a nearby diagonalizable matrix... Another thing: a rational matrix may have not a single rational eigenvalues, so a rational Jordan decomposition may not exist. – Dirk Jun 25 '19 at 4:36