8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – parsiad Jul 13 '16 at 13:59
  • 1
    $\begingroup$ In practice, I would think that a random perturbation would work well enough; the result will be diagonalizable with probability $1$. $\endgroup$ – Ben Grossmann Jul 13 '16 at 20:23
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.