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.
Best Answer
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}$$
Hence,
$$\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}$$