[Math] Swapping rows or columns of Toeplitz matrix changes sign of one eigenvalue

eigenvalues-eigenvectorslinear algebramatricestoeplitz-matrices

Given some arbitrary Toeplitz matrix, if I swap two rows, one of the eigenvalues change its sign. For example,

$$X =
\begin{bmatrix}
A & B & C \\
D & A & B \\
E & D & A
\end{bmatrix}$$

and

$$Y = \begin{bmatrix}
D & A & B \\
A & B & C \\
E & D & A
\end{bmatrix}$$

have the same eigenvalues up to sign. I can see this for small examples, but how would I go about proving this?

In particular, if I flip the matrix upside down or left-side-right, half (rounding down) of the eigenvalues flip sign, and the singular values are the same. (It becomes a Hankel matrix.)

Numerical demonstration with MATLAB code:

d = 5;
X = toeplitz(randn(d,1));
   -0.8655   -0.1765    0.7914   -1.3320   -2.3299
   -0.1765   -0.8655   -0.1765    0.7914   -1.3320
    0.7914   -0.1765   -0.8655   -0.1765    0.7914
   -1.3320    0.7914   -0.1765   -0.8655   -0.1765
   -2.3299   -1.3320    0.7914   -0.1765   -0.8655

J = flipud(eye(d));
   0     0     0     0     1
   0     0     0     1     0
   0     0     1     0     0
   0     1     0     0     0
   1     0     0     0     0

svd(X)'
    4.0897    2.0381    1.8456    0.8649    0.8198

svd(X*J)'
    4.0897    2.0381    1.8456    0.8649    0.8198

eig(X)'
   -4.0897   -2.0381   -0.8649    0.8198    1.8456

eig(X*J)'
   -4.0897   -1.8456   -0.8649    0.8198    2.0381

eig(J*X)'
   -4.0897   -1.8456   -0.8649    0.8198    2.0381

EDIT: non-symmetric toeplitz example

Best Answer

What you claim is not necessarily true if you swap two rows arbitrarily. It is easy to generate a random counterexample by computer. However, if $J$ is the backward identity matrix (as shown in your MATLAB code), then the eigenvalues of $JA$ (or $AJ$, which is similar to $JA$) and $A$ are identical except that $\lfloor \frac n2\rfloor$ pairs of them have different signs.

The essential reason behind this phenomenon is that a symmetric Toeplitz matrix has an eigenbasis in which $\lceil \frac n2\rceil$ eigenvectors $v$ are "symmetric" (i.e. $Jv=v$) and the remaining $\lfloor \frac n2\rfloor$ are "skew-symmetric" ($Jv=-v$).

So, if $v$ is a symmetric eigenvector corresponding to an eigenvalue $\lambda$, we have $JAv=J(\lambda v)=\lambda Jv=\lambda v$, i.e. $\lambda$ is also an eigenvalue of $JA$.

In contrast, if $v$ is a skew-symmetric eigenvector corresponding to some eigenvalue $\lambda$, then $JAv=J(\lambda v)=\lambda Jv=-\lambda v$, i.e. the sign of the eigenvalue is flipped in $JA$.

Related Question