How to compute the semisimple part of the Jordan (SN) decomposition of a matrix How do you compute the semisimple part of the Jordan (SN) decomposition of a matrix $A\in M_n(K)$?  The method I believe is correct is this:


*

*Compute the eigenvalues $a_1,\dots,a_r$ of $A$ and their generalized eigenspaces $\tilde{V}_{a_1},\dots,\tilde{V}_{a_r}$.

*Compute a basis $(b_{k,1},\dots,b_{k,d_k})$ for each generalized eigenspace $\tilde{V}_{a_k}$, and let $P$ be a matrix $(b_{1,1},\dots,b_{1,d_1},\dots,b_{k,1},\dots,b_{k,d_k},\dots,b_{r,1},\dots,b_{r,d_r})$, where each vector is regarded as a column vector.

*Let $B = a_1I_{d_1}\oplus\cdots\oplus a_rI_{d_r}$ and then $P^{-1}BP$ will be the semisimple part.


Is this a correct and convenient way to compute the semisimple part by hand?
 A: Let $p$ be the minimal polynomial of $A$. Then there is a unique polynomial $s\in K[X]$ of degree less than $\deg p$ such that $s(A)$ is the semi-simple part of $A$. 
Assume, as we may, that $p$ splits in $K$ as, say, 
$$
p=\prod_{\lambda\in\Lambda}\ (X-\lambda)^{m(\lambda)}
$$
with $m(\lambda) > 0$ for all $\lambda$.
Then $s$ is the unique degree less than $\deg p$ solution to the congruences
$$
s\equiv\lambda\quad\bmod\quad(X-\lambda)^{m(\lambda)},\quad\lambda\in\Lambda, 
$$
and it is given by 
$$
s=\sum_{\lambda\in\Lambda}\ \lambda\ T_\lambda\left(\frac{(X-\lambda)^{m(\lambda)}}{p}\right)\frac{p}{(X-\lambda)^{m(\lambda)}}\quad,
$$
where $T_\lambda(f)$ means "order less than $m(\lambda)$ Taylor polynomial of $f$ at $\lambda$".
EDIT. Here is a proof. Put 
$$
B_\lambda:=\frac{K[X]}{(X-\lambda)^{m(\lambda)}}\quad.
$$
(A) We have canonical $K[X]$-algebra isomorphisms 
$$
K[A]\simeq\frac{K[X]}{(p)}\simeq\prod_{\lambda\in\Lambda}\ B_\lambda=:B,
$$
the second isomorphism being given by the Chinese Remainder Theorem. 
We way (and will) work in $B$ instead of working in $K[A]$. 
Let $x\in B$ be the canonical image of $X$, and $e_\lambda$ the element of $B$ whose $\lambda$ component is $1$, and whose other components are $0$. 
We must find the semi-simple part of $x$. But this is clearly the sum of the $\lambda e_\lambda$. In view of (A), this shows that, as claimed, $s$ is the unique degree less than $\deg p$ solution to the congruences
$$
s\equiv\lambda\quad\bmod\quad(X-\lambda)^{m(\lambda)},\quad\lambda\in\Lambda,  
$$
and we're left with solving these congruences. 
It's not harder to solve the general congruence system 
$$
s\equiv p_\lambda\quad\bmod\quad(X-\lambda)^{m(\lambda)},\quad\lambda\in\Lambda,
$$
where the $p_\lambda\in K[X]$ are arbitrary. 
The trick is to use the Ansatz 
$$
s:=\sum_{\lambda\in\Lambda}\ s_\lambda\ \frac{p}{(X-\lambda)^{m(\lambda)}}\quad,\quad\deg s_\lambda < m(\lambda), 
$$ 
which gives the solution 
$$
\sum_{\lambda\in\Lambda}\ T_\lambda\left(p_\lambda\ \frac{(X-\lambda)^{m(\lambda)}}{p}\right)\frac{p}{(X-\lambda)^{m(\lambda)}}\quad.
$$
[Recall that $A$ admits a Jordan decomposition if and only if its eigenvalues are separable over $K$ (Bourbaki, Algèbre, Théorème VII.5.9.1). We assume here that such is the case.]
A: Your method is correct but requires to compute the root of the characteristic polynomial of $A$, which can't be done in general (there is no algorithm if $K=\mathbb{C}$, but if $K$ is finite there are algorithms such as Cantor-Zassenhaus).
The only way I know (but there may be other ones) to compute the semi-simple part of $A$ is the following : let $P(X) = \frac{\chi_A(X)}{GCD(\chi_A(X),\chi'_A(X))}$. Compute the sequence $(A_k)$ of matrices by $A_0=A$ and $A_{k+1} = A_k - P(A) P'(A)^{-1}$. Then for $k \geq \log_2 n$, $A_k$ is the semi-simple part of $A$ (the key point to prove this is to note that the semis-simple part of $A$ is a zero of $P(X)$).
