# Eigenvalues of some peculiar matrices

While I was toying around with matrices, I chanced upon a family of tridiagonal matrices $M_n$ that take the following form: the superdiagonal entries are all $1$'s, the diagonal entries take the form $m_{j,j}=4 j (2 n + 3) - 8 j^2 - 6 n - 5$, and the subdiagonal entries take the form $m_{j+1,j}=4 j (2 j - 1) (2 n - 2 j + 1) (n - j)$.

For example, the $4\times 4$ member of this family looks like this:

$$M_4=\begin{pmatrix} 7 & 1 & 0 & 0 \\ 84 & 27 & 1 & 0 \\ 0 & 240 & 31 & 1 \\ 0 & 0 & 180 & 19\end{pmatrix}$$

I checked the eigenvalues of members of this family and I found that each member has the squares of the first few odd integers as eigenvalues. (For example, the eigenvalues of $M_4$ are $1,9,25,49$.) I couldn't find a way to prove this though.

I wish someone would help me! Thanks!

• You... you were just... toying around when you found this? :o Anyway, the proof of this fact (assuming it's true) will likely go the route of explicitly constructing the eigenvectors. We should try to find a pattern in them and that should lead to the answer. Either that or more or less determine the characteristic polynomial and show its roots are squares of odds.
– anon
Sep 9 '11 at 4:56
• Off-topic, but I could not resist reading this in Tara Strong's voice. Sep 9 '11 at 4:56
• well, I can easily check that the trace is correct :) And I'm pretty sure if you successively (starting from i=1) subtract the proper multiples of row i from row i+1 (to make the (i+1, i) entry 0), then the diagonal entries become 1*(2n-1), 3*(2n-3), etc. So the determinant is correct too.
– Ted
Sep 9 '11 at 6:15
• The way you came up with this matrix might suggest some useful ways to transform your matrix to a simpler form. Sep 9 '11 at 10:30
• Not sure if this is relevant, but the diagonal terms of $M$ can be written as $m_{jj} = 2(2j - 3/2)[2(n-j)+3/2] - 1/2$ and $m_{j,j+1} = 4 j (n-j)(2j - 1)[2(n-j) + 1]$, which contains a lot of terms of the form $(Aj - B)(A(n-j) + B)$. So there's some structure to the madness ;-). Sep 9 '11 at 14:29

I think I have something. My solution's a bit convoluted, and I'd be glad to see a shorter path to do this.

Since symmetric matrices are "easier" to handle, we apply a symmetrizing diagonal similarity transformation $\mathbf D^{-1}\mathbf M\mathbf D$ to the matrix $\mathbf M$, where $\mathbf D$ has the diagonal elements

$$d_{k,k}=\left(\prod_{j=1}^{k-1} \left(4j(2j-1)(2n-2j+1)(n-j)\right)\right)^\frac12$$

(This transformation of an unsymmetric tridiagonal matrix to a symmetric one is due to Jim Wilkinson.) The new matrix, call it $\mathbf W$, has diagonal entries that are identical to that of $\mathbf M$, while the sub- and superdiagonal entries are the square roots of the subdiagonal entries of $\mathbf M$. For instance, here is $\mathbf W_4$:

$$\begin{pmatrix} 7 & 2 \sqrt{21} & 0 & 0 \\ 2 \sqrt{21} & 27 & 4 \sqrt{15} & 0 \\ 0 & 4 \sqrt{15} & 31 & 6 \sqrt{5} \\ 0 & 0 & 6 \sqrt{5} & 19 \end{pmatrix}$$

I've found that $\mathbf W$ is symmetric positive definite; it should thus have a Cholesky decomposition $\mathbf W=\mathbf C^\top\mathbf C$, where the Cholesky triangle $\mathbf C$ is an upper bidiagonal matrix. Luckily, the entries of $\mathbf C$ take a (somewhat) simple(r) form:

\begin{align*}c_{k,k}&=\sqrt{(2k-1)(2n-2k+1)}\\c_{k,k+1}&=2\sqrt{k(n-k)}\end{align*}

Here's $\mathbf C_4$ for instance:

$$\begin{pmatrix} \sqrt{7} & 2 \sqrt{3} & 0 & 0 \\ 0 & \sqrt{15} & 4 & 0 \\ 0 & 0 & \sqrt{15} & 2 \sqrt{3} \\ 0 & 0 & 0 & \sqrt{7} \end{pmatrix}$$

Why look at the Cholesky decomposition when it's the eigenvalues that we're interested in? It is sometimes expedient to compute the eigenvalues of a symmetric positive definite matrix by considering the singular values of its Cholesky triangle. More precisely, if $\sigma_1,\dots,\sigma_n$ are the singular values of $\mathbf C$, then the eigenvalues of $\mathbf W$ are $\sigma_1^2,\dots,\sigma_n^2$.

Here's where it clicked for me. On a hunch, I decided to consider the Golub-Kahan tridiagonals corresponding to $\mathbf C$.

It is part of the theory of the singular value decomposition that if $\mathbf C$ has the singular values $\sigma_1,\dots,\sigma_n$, then the $2n\times 2n$ block matrix

$$\mathbf K=\left(\begin{array}{c|c}\mathbf 0&\mathbf C^\top \\\hline \mathbf C&\mathbf 0\end{array}\right)$$

has the eigenvalues $\pm\sigma_1,\dots,\pm\sigma_n$. It is also known that there exists a permutation matrix $\mathbf P$, such that this matrix realizes a similarity transformation between $\mathbf K$ and a special tridiagonal matrix $\mathbf T$:

$$\mathbf T=\mathbf P\mathbf K\mathbf P^\top$$

and $\mathbf T$ looks like ($n=4$):

$$\begin{pmatrix} 0 & \sqrt{7} & 0 & 0 & 0 & 0 & 0 & 0 \\ \sqrt{7} & 0 & 2 \sqrt{3} & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 \sqrt{3} & 0 & \sqrt{15} & 0 & 0 & 0 & 0 \\ 0 & 0 & \sqrt{15} & 0 & 4 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 & 0 & \sqrt{15} & 0 & 0 \\ 0 & 0 & 0 & 0 & \sqrt{15} & 0 & 2 \sqrt{3} & 0 \\ 0 & 0 & 0 & 0 & 0 & 2 \sqrt{3} & 0 & \sqrt{7} \\ 0 & 0 & 0 & 0 & 0 & 0 & \sqrt{7} & 0 \end{pmatrix}$$

Note the structure of $\mathbf T$: the diagonal entries are zero, and the off-diagonal entries are the diagonal and superdiagonal entries of $\mathbf C$ "riffled" together. $\mathbf T$ is what is referred to as a Golub-Kahan tridiagonal matrix.

As it turns out, a further diagonal similarity transformation $\mathbf T^\prime=\mathbf F\mathbf T\mathbf F^{-1}$, with diagonal entries $f_{k,k}=\sqrt{\binom{2n-1}{k-1}}$ turns $\mathbf T$ to a rather famous set of matrices. Here's the $2n\times 2n$ matrix $\mathbf T^\prime$, for $n=4$:

$$\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 7 & 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 6 & 0 & 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 4 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 & 6 & 0 \\ 0 & 0 & 0 & 0 & 0 & 2 & 0 & 7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}$$

$\mathbf T^\prime$ is what is known as the Clement-Kac(-Sylvester) matrix. It is well-known (see here or here, for instance) that the $2n\times 2n$ Clement-Kac(-Sylvester) matrix has the eigenvalues $\pm1,\dots,\pm(2n-1)$ (and thus these are the eigenvalues of $\mathbf T$ and $\mathbf K$ as well). From this, we find that the singular values of $\mathbf C$ are $1,\dots,2n-1$ (the first few odd numbers), and thus the eigenvalues of $\mathbf W=\mathbf C^\top\mathbf C$ and the original matrix $\mathbf M$ are $1,9,\dots,(2n-1)^2$.

Whew!

• I have yet to comprehend what you have revealed here, but I'm pretty amazed at your persistence in solving this problem! Nov 10 '11 at 13:47
• OK, finished reading it. This is ... ingenious. Nov 10 '11 at 17:58
• I'm still hoping somebody can outdo my answer, though. :) Nov 10 '11 at 18:07

Here is the eigendecomposition $M_4= VDV^{-1}$ confirming @Craig's observation:

$$\begin{pmatrix} 1 &1 &1 &1\\ 42 &18 &2 &-6\\ 840 &-120 &-120 &72\\ 5040 &-3600 &2160 &-720 \end{pmatrix} \begin{pmatrix}49\\&25\\&&9\\&&&1\end{pmatrix}\begin{pmatrix} 1 &1 &1 &1\\ 42 &18 &2 &-6\\ 840 &-120 &-120 &72\\ 5040 &-3600 &2160 &-720 \end{pmatrix}^{-1}$$ If you can provide a little hint on how you came up with this, then we can probably understand why $V$ has this special structure. Also, you can distribute the squares to the left and right matrices and obtain an even weirder situation.

If I'm not mistaken, the largest eigenvector is of the form

$\begin{pmatrix} 1 \\ (2n-1)!/(2n-3)! \\ (2n-1)!/(2n-5)! \\ \vdots \\ (2n-1)!/1! \end{pmatrix}$.

This shouldn't be too difficult to prove, and I think the smallest eigenvector has a similarly compact form. My suspicion is that there is a simple rotation or pair of rotations you can do to see the eigenvalues explicitly. I would look for something of the form $ULDL^{-1}U^{-1}$ or $LUDU^{-1}L^{-1}$, where $L$ is non-zero except on the diagonal and subdiagonal, and $U$ is zero except on the diagonal and superdiagonal.