Computing exponential of a matrix without Jordan form

Question

is it possible to find the exponential of a matrix without the Jordan normal form (not a numerical approximation)? I've been thinking about this problem and trying to tackle it using a more general approach with the rational form but I failed to find an appropriate solution

Answer 1

Let $A\in M_n(\mathbb{K})$ where $K$ is a subfield of $\mathbb{C}$ (for example). If you don't know exactly all the eigenvalues $(\lambda_i)_i$ of $A$, then you cannot calculate exactly the values of $e^A$ or $\sqrt A$ or $\log(A)$ or $\cdots$. -Note that we should define what we mean by "we know explicitly this or that number"-

In particular, if $n\geq 5$ and $A$ is random, then we cannot calculate $e^A$ -with probability $1$- because $\chi_A$ is not solvable -with probability $1$-.

The first thing to see is that the problem reduces to the case of the semi-simple matrices. Indeed, we can always calculate the Jordan Chevalley decomposition of $A$, that is, $A=D+N$, where $D\in K[A]$ is semi-simple, $N\in K[A]$ is nilpotent and $DN=ND$. Then $e^A=e^D(I+N+\cdots+\dfrac{N^{n-1}}{(n-1)!})$. It "remains" to calculate $e^D$, that is impossible; indeed, it is not difficult to see that the entries of $e^D$ are in the extension of $K$ containing the entries of $A$, the $(\lambda_i)$ and the $(e^{\lambda_i})$.

Now, if you are satisfied with an approximation of $e^A$ (in fact you have no choice), then you can do as follows; assume that $A\in M_5$ with $|a_{i,j}|\leq 1$. We work with $30$ significative digits

Let $B=2^{-10}A$, $r$ be the remainder of the division of $\sum_{i=0}^{10}x^i/i!$ by $\chi_B$. Put $s=r(B)$ and do

for i from 1 to 10 do s:=s^2:od:

The output $s$ is a good approximation of $e^A$.

EDIT. -Answer to Reinhard Meier- Absolutely, and this is what makes the interest of this algorithm.

The Jordan-Chevalley decomposition uses only operations in $K$, in fact a finite number of such operations and, moreover, the complexity of the algorithm is polynomial (in $O(n^3)$ or $O(n^4)$).

The idea is as follows: we assume that $K$ is a perfect field (every irreducible $P\in K[x]$ has only simple roots).

Let $P\in K[x]$ be irreducible; with a like-Newton method, we can construct a sequence $(Q_i)_{i\geq 1}\in K[x]$ s.t. $Q_1(x)=x,P(Q_i(x))=0 \mod P^i$ and $Q_i(x)=x \mod P$.

Let $U\in M_n(K)$; there is $P\in K[x]$ irreducible s.t. $P^m(U)=0$. Then (cf. above) $U=D+(U-D)$ where $D=Q_m(U)$. Moreover, $D\in K[U],P(D)=0,(U-D)^m=0$.

A reference in french

https://arxiv.org/pdf/1103.5020.pdf

Answer 2

There are different methods of finding the exponential of a matrix.

One method is the diagonalization of the matrix which requires having linearly independent eigenvectors.

The other method is using the Cayley Hamilton Theorem which does not require the eigenvector and takes advantage of the characteristic polynomial of the matrix.

If you are lucky and you can find the infinite series approach, then that is also possible for some simple matrices.

Answer 3

I assume that the field is $\mathbb{C}.$

You do not need the Jordan normal form, but you need the eigenvalues.

Let $H$ be the Hermite interpolation polynomial of maximum degree $n-1$ that interpolates an analytic function $f$ at the eigenvalues of $A$ with the associated algebraic multiplicities of the eigenvalues. This means, if $\lambda_i$ is an eigenvalue of $A$ with algebraic multiplicity $r_i,$ then we calculate the polynomial coefficients of $H$ such that $$ H(\lambda_i) = f(\lambda_i) \\ H'(\lambda_i) = f'(\lambda_i) \\ H''(\lambda_i) = f''(\lambda_i) \\ H^{(r_i-1)}(\lambda_i) = f^{(r_i-1)}(\lambda_i) $$ which is always possible. This is a regular system of $n$ linear equations with $n$ unknows.

Then $f(A) = H(A).$ You can use this with $f(t) = e^t$.