5
$\begingroup$

Consider the anti-bidiagonal matrix $B_6\in\mathbb{R}^{6\times 6}$, defined along its anti-diagonals as follows

$$ B_6=\begin{bmatrix} & & & & & 6\\ & & & & 5 & -5\\ & & & 4 & -4\\ & & 3 & -3\\ & 2 & -2\\ 1 & -1 \end{bmatrix}. $$

Its eigenvalues are $\lambda(B_6)=\{1,-2,3,-4,5,-6\}$, a fact easily verified numerically e.g. on MATLAB.

Furthermore, one can numerically verify that this pattern persist. With this, I'm looking for a proof to the following statement.

Proposition 1. For a matrix $B_n$ defined as above, its eigenvalues are given $$\lambda(B_n)=\{(-1)^{i+1}i\}_{i=1}^n\equiv\{1,-2,3,-4,\ldots\}.$$

This has turned out to be surprisingly difficult. It is tempting to predict the eigenvalues by reading off the diagonals. However the matrix is genuinely not triangular, nor does it share many properties with triangular matrices. It is easy to construct counter-examples where the eigenvalues do not coincide with the antidiagonals.

The ramification of this statement is that it characterizes an entire class of graphs to be "well-connected", and the corresponding class of linear algebra problems to be well-conditioned irrespective of problem size. The fact that the eigenvalues are integers is quite significant, since it implies that the solutions to integer and linear program versions of this matrix would coincide, and this can be exploited to prove several graph results. I can give more background if necessary.

Some candidate approaches I have tried:

  1. Recursive characteristic polynomial. It is routine to write down a formula for $\mathrm{det}(B_n - \lambda I_n)$. However, it's difficult to find its roots without resorting to variations on Newton iterations.

  2. Golub-Kahan form. One may reorder the rows and columns to yield a tridiagonal matrix with zeros along the main diagonal. More specifically, let $e_i$ denote the i-th column of the identity, define a similarity transform $E=\begin{bmatrix} e_1 & e_n & e_2 & e_{n-1} & \ldots\end{bmatrix}$, and consider $\hat{B}=E^TBE$. However, its characteristic polynomial is a mess, and we encounter the same problem trying to prove roots of the polynomial.

  3. Matrix inverse. The matrix $B_6$ has the following inverse $$B_{6}^{-1}=\begin{bmatrix}\frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6}\\ \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5}\\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4}\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ \frac{1}{2} & \frac{1}{2}\\ 1 \end{bmatrix}.$$ A proof of this is simply gaussian elimation of a triangle-like matrix. Thus Prop 1 can be reworded as $\lambda(B_6^{-1})=\{1,-1/2,1/3,-1/4,1/5,-1/6\}$. It does not appear to be any easier to obtain the eigenvalues of $B^{-1}_n$. Indeed, its characteristic polynomial is even harder to write down.

  4. Interpretation as difference operator. Finally, the matrix can be viewed as a difference operator, and in the limit $\lim_{n\to\infty}B_n$, its eigenfunctions are orthogonal polynomials. This approach yields a proof. However it does not say anything about the cases where $n$ is small, e.g. 4 or 5.

Any advice or suggestions?

$\endgroup$
  • 1
    $\begingroup$ Is the question, "Find a simple proof that the eigenvalues are . . . "? Also, you say "one can show that this pattern persists." How does that proof go? $\endgroup$ – Noah Schweber Oct 27 '14 at 19:28
  • 1
    $\begingroup$ The right eigenvector for $\left(-1\right)^n n$ (the eigenvalue with largest absolute value) seems to be nice enough: $\left(\left(-1\right)^0 \binom{n-1}{0}, \left(-1\right)^1 \binom{n-1}{1}, \left(-1\right)^2 \binom{n-1}{2}, \cdots, \left(-1\right)^{n-1} \binom{n-1}{n-1}\right)$. The left eigenvector for the same eigenvalue seems to be $\left(\left(-1\right)^0 \binom{n}{0}, \left(-1\right)^1 \binom{n}{1}, \left(-1\right)^2 \binom{n}{2}, \cdots, \left(-1\right)^{n-1} \binom{n}{n-1}\right) ^T$. This suggests a recursive approach. $\endgroup$ – darij grinberg Oct 27 '14 at 19:52
  • 1
    $\begingroup$ In your approach 1, why do you want to find the roots? Why not just plug in the suspected values? $\endgroup$ – Alex Degtyarev Oct 27 '14 at 20:33
  • 1
    $\begingroup$ To me this seems like essentially a duplicate of: mathoverflow.net/questions/156090/… $\endgroup$ – Suvrit Oct 27 '14 at 21:00
  • 1
    $\begingroup$ @RichardZhang: I am quite interested in such matrices, and it would be great if you could provide some concrete background / examples where such matrices arise. $\endgroup$ – Suvrit Oct 27 '14 at 21:31
10
$\begingroup$

This problem is essentially the same as this one. In particular, let $J$ be the anti-diagonal identity matrix, and $P^{-1}$ be the matrix mentioned in the link above. Then, the matrix in the current post is nothing but \begin{equation*} B_n = JP^{-T}J^T. \end{equation*} Since $J^TJ=I$, we can recover eigenvectors and values of $B_n$ using the derivation for $P$ in the linked post.

$\endgroup$
  • $\begingroup$ I just saw your response. And wow it looks both right and extremely elegant. Nice. Let me quickly code this up to verify. $\endgroup$ – Richard Zhang Oct 27 '14 at 21:26
  • $\begingroup$ @RichardZhang: You can download the matlab file linked in my answer to get the closed form eigenvalues and eigenvectors of the matrix $P$ in my other answer; the eigenvectors for your matrix are then easily obtained I think as: $JV^TS^T$, for matrices $V$ and $S$ computed by my matlab code. $\endgroup$ – Suvrit Oct 27 '14 at 21:29
  • $\begingroup$ In my initial question, I was looking for a relatively short proof of the eigenvalue proposition, without necessarily constructing the eigenvectors. As you have shown, the eigenvectors are fairly complicated, thus leaving a direct $B_n x = \lambda x$ proof filling many pages. Instead, your $V$ matrix gets us there indirectly, since $VP^{-1}V^{-1}$ is a triangular matrix. To prove that it is triangular, we can do a proof by induction: project every $B_n$ onto the final two columns of their respective $V$. This turns out to be exactly what Darij had suggested in his comment. $\endgroup$ – Richard Zhang Oct 28 '14 at 0:39
  • $\begingroup$ @RichardZhang: I constructed that $V$ matrix, because in that question, the OP wanted all eigenvectors of the matrix; eigenvalues he already knew how to obtain; You may also want to have a look at page 3 of math.mit.edu/~plamen/files/KoevDopicoSR.pdf --- in particular, the relation of the two anti bi-diagonal matrices mentioned in there. $\endgroup$ – Suvrit Oct 28 '14 at 1:01

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.