14
$\begingroup$

In this thread on MATLAB Central, I found a discussion on finding the nearest matrix with real eigenvalues. The first hypothesis was to simply truncate the complex part of the eigenvalues. So, given matrix $A$, the closest matrix to $A$ in some norm would be

$$A' = V \; \mathrm{real}(D)\; V^{-1}$$

where $A= V D V^{-1}$ is the eigendecomposition of $A$ (assuming $A$ is diagonalizable). This has been found to be false, however, with the counterexample

$$A = \begin{bmatrix} 1& 1& 0 \\ -1& 0& 0 \\ 0& 0& 0 \\ \end{bmatrix}$$

The procedure above would produce

$$A'=\begin{bmatrix} 0.5& 0& 0 \\ 0& 0.5& 0 \\ 0& 0& 0 \\ \end{bmatrix}$$

but there is another matrix

$$A''=\begin{bmatrix} 0.9& 0& 0 \\ -2& -0.1& 0 \\ 0& 0& 0 \\ \end{bmatrix}$$

that has real eigenvalues and is closest to $A$ both in spectral and Frobenius norm.

Now, let $ A = U T U' $ be the real Schur decomposition of $A$, with $U$ orthogonal and $T$ quasi-upper triangular (there are 2-by-2 blocks on the diagonal corresponding to complex eigenvalues). Consider $ A_s = U \; \mathrm{triu}(T) \; U' $ where triu returns the upper triangle part. By numerical simulations $A_s$ it is always closer to random $A$ than $A'$ and on the counterexample it is also closest to $A$ than $A''$ (in Frobenius and spectral norm).

My conjecture is that $A_s$ is the closest matrix with real eigenvalues to $A$ in Frobenius (or spectral) norm. Unfortunately I could not prove or disprove this conjecture. Can anybody?

A starting point can be

$$||A-A_s||_F = ||T-\mathrm{triu}(T)||_F$$

$\endgroup$
  • $\begingroup$ Thank. There was a mistake in $A'$, which I have corrected. $\endgroup$ – Andrea F. Jul 5 '17 at 7:31
11
$\begingroup$

I have no idea what is going on, but your conjecture is not correct. This is more transparent perhaps in the complex version. Consider $$ A = \begin{pmatrix} i & a \\ 0&-i \end{pmatrix} , \quad a>0. $$ This matrix is already in (complex) Schur form, and the obvious procedure to make the eigenvalues real and similar in spirit to what you propose would be to make the diagonal entries real (that is, set them equal to zero here). However, this is not optimal: we can also achieve real spectrum by setting $a_{21}=b$, $b>1/a$, and in fact this is a very small perturbation if $a$ was large. (So the general message is that even eigenvalues that aren't close to the real axis might need only a small perturbation to get them there.)

A real version of this example also works, it just gets somewhat messier computationally. Take $$ A = \begin{pmatrix} 0 & 1 & 0 & 0 \\ -1 & 0 & a & 0\\ 0&0&0&1 \\ 0&0&-1&0 \end{pmatrix} ,\quad a>0 . $$ Your proposal is to remove the $-1$'s, but we can also get real eigenvalues by putting $a_{32}=b$ as long as $ab>4$.

$\endgroup$
  • $\begingroup$ Thanks, I see your point, so the conjecture is false. The problem is apparently without solution, for general matrices. $\endgroup$ – Andrea F. Jul 5 '17 at 7:49
  • 1
    $\begingroup$ @AndreaF.: A few afterthoughts (which don't really add anything new and may not be useful): For normal matrices, your conjecture is correct (easy to see probably, but see also math.stackexchange.com/questions/1711713/…). In my example, the eigenvectors are almost parallel. (So for example $v_1-v_2$ is almost an eigenvector with eigenvalue $0$.) So in general one apparently has to take at least two features into account (how close are the ev's to $\mathbb R$, how small are the angles between the eigenvectors), which makes the problem hard to analyze. $\endgroup$ – Christian Remling Jul 6 '17 at 16:35
4
$\begingroup$

Another counter example to the question which shows how unstable complex eigenvalues can behave: Let $$A=\left(\begin{matrix}0&1&0&\dots &0\\ 0 &0 & 1 &\dots & 0 \\ \vdots &\ddots &\ddots &\ddots& \vdots\\ 0 & \dots&\dots &0 &1\\ 2^{-n} &0 &\dots & \dots &0 \end{matrix}\right)$$ be the $n\times n$ matrix with ones in the first superdiagonal, $2^{-n}$ in the lower left entry and zeros otherwise. Then for large $n$ the matrix $A$ is exponentially close to a nilpotent matrix $B$ (with the lower left entry set to zero) which therefore has only zero as an eigenvalue, in particular purely real spectrum. The eigenvalues of $A$, however, are uniformly distributed on the unit circle. This means that an exponentially small modification of the matrix results in a huge jump in the spectrum. The conjectured closest matrix $A_s$ though, is in spectral norm $\lVert A_s-B\rVert\sim 1$ far away from $B$.

$\endgroup$
  • 1
    $\begingroup$ I think the eigenvalues satisfy $|\lambda|=1/2$ (not $1$). Of course, that doesn't affect the general point you're making. $\endgroup$ – Christian Remling Jul 8 '17 at 21:23

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.