# Compute a diagonalizable matrix close in matrix exponential

It is known that for any matrix $A$, one can perturb $A$ slightly so that the resulting $A(\epsilon)$ is diagonalizable.

I am wondering whether for any matrix $A$, $\epsilon>0$, there is an algorithm to compute a diagonalizable matrix $A(\epsilon)$ such that

$$\|e^A - e^{A(\epsilon)}\|_2\leq \epsilon$$

Here $e^A$ is the matrix exponential, and $\|\cdot\|_2$ is the 2-norm.

• Is a naive binary search not an option? (i.e., start with a big perturbation; keep halving it until you satisfy your inequality). Are you looking for a faster/cleverer algorithm? Jul 13, 2016 at 13:59
• In practice, I would think that a random perturbation would work well enough; the result will be diagonalizable with probability $1$. Jul 13, 2016 at 20:23

A matrix $A$ is diagonalizable over the field of complex numbers if all eigenvalues of $A$ are distinct. To see this consider the Jordan decomposition $A = VJV^{-1}$, where $J$ is a complex matrix in the Jordan form. If all eigenvalues of $A$ are distinct, then $J$ contains only blocks of size $1\times 1$, hence $J$ is diagonal.
In order to compute a perturbation, that makex $A$ diagonalizable consider the complex Schur factorization of $A$, i.e. $A = UTU'$, where $U$ is unitary and $T$ is upper triangular with complex entries, and $U'$ denotes conjugate transposition. Diagonal of $T$ contains eigenvalues of $A$.
Let $\tilde{A} = U(T+D)U'$, where $D$ is a diagonal matrix, such that all diagonal elements of $T+D$ are distinct and $\|D\|_2\leq \mu$ for some $0 < \mu \leq 1$. Such matrix can be easlily constructed. Then $\tilde{A} = A + UDU'\equiv A + P$, and $\|P\|_2 = \|D\|_2 \leq \mu$. The matrix $\tilde{A}$ is diagonalizable.
For any two matrices $X$, $Y$ and any matrix norm: $$\|e^{X+Y} - e^X\| \leq \|Y\|e^{\|X\|}e^{\|Y\|}$$ Thus $$\|e^{A+P} - e^A\|_2 \leq \|P\|_2e^{\|A\|_2}e^{\|P\|_2} \leq \mu e^{\|A\|_2}e^{\mu} \leq \mu e^{\|A\|_2 + 1}$$ If we take $\mu = \min(1,\epsilon / e^{\|A\|_2 + 1})$, then $\|e^{A+P} - e^A\|_2\leq \epsilon$.
For a real matrix $A$ containing complex eigenvalues it is not possible to find a small perturbation $P$, such that $A + P$ is diagonalizable over the field of real numbers, but it is possible if $A$ has only real eigenvalues. Then, this construction can be repeated using the real Schur factorization.