We have diagonal matrices $A = \mbox{diag} (\lambda_1, \ldots, \lambda_n)$ for which matrix exponential has simple form $e^A = \mbox{diag} (e^{\lambda_1}, \ldots, e^{\lambda_n})$, and it can be computed with $\mathcal{O}(n)$ time complexity.

There are general algorithms for computing matrix exponential for general matrix, such as Pade Approximation, but they work cubic time in size of a square matrix.

I'm interested in finding classes of square matrices for which matrix exponential can be computed not harder than $\mathcal{O}(n^2)$ complexity. Is there any structured matrices that has this property?

Any literature/articles suggestions will be appreciated.


2 Answers 2


Nilpotent matrices

For example, if $\mathrm A \neq \mathrm O_n$ and $\mathrm A^2 = \mathrm O_n$, then $\mathrm A^k = \mathrm O_n$ for all $k \geq 2$ and

$$\exp(\mathrm A) = \mathrm I_n + \mathrm A + \dfrac{1}{2!} \mathrm A^2 + \dfrac{1}{3!} \mathrm A^3 + \dfrac{1}{4!} \mathrm A^4 + \cdots = \mathrm I_n + \mathrm A$$

Idempotent matrices

For example, if $\mathrm A^2 = \mathrm A$, then $\mathrm A^k = \mathrm A$ for all $k \geq 1$ and

$$\begin{array}{rl} \exp(\mathrm A) &= \mathrm I_n + \mathrm A + \dfrac{1}{2!} \mathrm A^2 + \dfrac{1}{3!} \mathrm A^3 + \dfrac{1}{4!} \mathrm A^4 + \cdots\\\\ &= \mathrm I_n + \left(1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \cdots \right) \mathrm A\\\\ &= \mathrm I_n + (e - 1) \mathrm A\end{array}$$

Projection matrices are idempotent.

Involutory matrices

If $\mathrm A$ is involutory, then $\mathrm A^2 = \mathrm I_n$ and, thus,

$$\mathrm A^k = \begin{cases} \mathrm I_n & \text{if } k \text{ is even}\\\\ \mathrm A & \text{if } k \text{ is odd}\end{cases}$$


$$\begin{array}{rl} \exp(\mathrm A) &= \mathrm I_n + \mathrm A + \dfrac{1}{2!} \mathrm A^2 + \dfrac{1}{3!} \mathrm A^3 + \dfrac{1}{4!} \mathrm A^4 + \cdots\\\\ &= \mathrm I_n + \mathrm A + \dfrac{1}{2!} \mathrm I_n + \dfrac{1}{3!} \mathrm A + \dfrac{1}{4!} \mathrm I_n + \cdots\\\\ &= \left(1 + \frac{1}{2!} + \frac{1}{4!} + \cdots \right) \mathrm I_n + \left(1 + \frac{1}{3!} + \frac{1}{5!} + \cdots \right) \mathrm A\\\\ &= \cosh (1) \, \mathrm I_n + \sinh (1) \, \mathrm A\end{array}$$

  • 2
    $\begingroup$ Another particularly interesting case is $\mathrm A^2=-\mathrm I$, so that $e^{\mathrm A}=\cos(1) \mathrm I + \sin(1)\mathrm A$. $\endgroup$
    – lisyarus
    Commented Aug 1, 2016 at 12:44
  • 2
    $\begingroup$ All these examples could be summed up in : If you know the characteristic polynomial, then you are in business. If you don't know the characteristic polynomial, you are in trouble, because it costs n^3 to compute it $\endgroup$
    – user145413
    Commented Aug 1, 2016 at 12:51
  • $\begingroup$ @lisyarus Do such matrices have a name? $\endgroup$ Commented Aug 1, 2016 at 13:00
  • $\begingroup$ @username Not necessarily. I don't need to know the characteristic polynomial of a projection matrix to know it is idempotent. Some matrices are given to us, others are constructed by us. $\endgroup$ Commented Aug 1, 2016 at 13:01
  • 2
    $\begingroup$ @RodrigodeAzevedo I'd say that the minimal polynomial can be of help, since it provides a way to express $A^n$ in terms of lower powers of $A$, and leads to a recurrence relation in the coefficients of $e^A$. $\endgroup$
    – lisyarus
    Commented Aug 1, 2016 at 13:11

Circulant matrices should be able to be exponentiated in less than $n^2$ time. You can diagonalize them via the FFT and then exponentiate the diagonal matrix.

EDIT: I believe strongly non-singular Toeplitz matrices can have their exponentiation well approximated quickly enough by combining the results of





You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .