How to compute the semisimple part of the Jordan (SN) decomposition of a matrix

linear-algebra matrices eigenvalues-eigenvectors

1,032

Solution 1

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.]

Solution 2

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)$).

1,032

Pteromys

Updated on January 07, 2020

Comments

Pteromys almost 3 years
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:
1. Compute the eigenvalues $a_1,\dots,a_r$ of $A$ and their generalized eigenspaces $\tilde{V}_{a_1},\dots,\tilde{V}_{a_r}$.
2. 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.
3. 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?
Pteromys almost 11 years

Could you give me more details about $T_\lambda$? (and what I really meant to ask was whether the method I described was correct.)
Pierre-Yves Gaillard almost 11 years

Dear @Pteromys: I'll write a proof as soon as possible, but I'm very slow. Thanks in advance for your patience.
Pierre-Yves Gaillard almost 11 years

Dear @Pteromys: I tried to give a proof.
Pteromys almost 11 years

Perhaps my wording was a bit confusing, but what I wanted to ask was all about computing it for matrices $\in M(\mathbb{R})$ by hand, e.g., when solving exercises on textbooks.