# Effective Jordan normal form

Given $$A \in \mathrm{GL}_m(\mathbb{C})$$, I can conjugate it by some $$B \in \mathrm{GL}_m(\mathbb{C})$$ into its Jordan normal form. That is, for some $$n\le m$$, there exists a $$J \in \mathrm{GL}_n(\mathbb{C})$$ containing all Jordan blocks which are not the $$1 \times 1$$ block with entry $$1$$ such that our Jordan normal form looks like \begin{align} BAB^{-1}= \begin{pmatrix} J & 0 & \dots &0 \\ 0 & 1 & \dots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 \end{pmatrix} \end{align}

In my setting the parameter $$m$$ is to be thought of as large and $$n$$ as small, and we define $$n$$ to be the size of $$A$$.

My question is if such a $$B$$ can be chosen in an efficient way. That is, is there such a $$B$$ which conjugates $$A$$ into its Jordan normal form and $$B$$ has linearly bounded size $$\leq Kn$$ for some $$K \in \mathbb{N}$$ itself? That means that a Jordan normal form of $$B$$ has a linearly bounded number of nontrivial Jordan blocks for a particular choice of $$B$$ or equivalently a choice of $$B$$ which has a large subspace on which it acts by the identity, if that was already true for $$A$$.

• Obviously it is impossible to find the Jordan canonical form of $A$ unless $A$ is determined with infinite precision, i.e. symbolically, since Jordan canonical form is discontinuous. So numerical methods to arrive at the form seem unlikely to be useful. – Ben McKay Jul 27 at 17:49