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?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ 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? $\endgroup$– Robert IsraelCommented Jun 24, 2019 at 19:26
-
$\begingroup$ 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. $\endgroup$– DirkCommented Jun 24, 2019 at 20:20
-
1$\begingroup$ @ Robert Israel symbolic RootOf. $\endgroup$– gondolfCommented Jun 25, 2019 at 3:20
-
$\begingroup$ @Dirk Thank you very much $\endgroup$– gondolfCommented Jun 25, 2019 at 3:20
-
$\begingroup$ 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. $\endgroup$– DirkCommented Jun 25, 2019 at 4:36
|
Show 1 more comment