# Diagonalize the $n \times n$ matrix with ones along both diagonals.

I'm having some trouble diagonalizing this nxn matrix with ones along both diagonals:

$\begin{bmatrix} 1&0&0&\cdots&0&0&1\\0&1&0&\cdots&0&1&0\\ 0&0&1&\cdots&1&0&0\\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&1&\cdots&1&0&0\\0&1&0&\cdots&0&1&0\\1&0&0&\cdots&0&0&1 \end{bmatrix}$

How should I approach this problem? At first, I tried cofactor expansion to find the eigenvalues and eigenspaces, but it quickly became really messy, so I'm wondering if there's any simpler way to diagonalize such a matrix. Any help would be appreciated!

Let's look at $n$ even:

If you let an eigenvector be $(x_0, x_1, \ldots x_{n-2})^T$ and just write out the eigen equations, you get $$x_0 + x_{n-1} = \lambda x_0 \\ x_1 + x_{n-2} = \lambda x_1 \\ \cdots + x_{n-2}+x_1 = \lambda x_{n-2} \\ x_{n-1}+x_0 = \lambda x_{n-1}$$ From this it is easy to see that either $\lambda = 0$ (in which case pairs $x_0 = - x_{n-1}$ and so forth), or $\lambda = 2$ (in which case pairs $x_0 = x_{n-1}$ and so forth). When $n$ is odd, ther is another case available for $\lambda = 0$, in whihc only the middle entry is non-zero.

So the eigenvalues are $2$ (with multiplicity $\left\lfloor \frac{n}{2}\right\rfloor$) and 0 (with multiplicity $\left\lfloor \frac{n+1}{2}\right\rfloor$). An orthonormal set of corresponding eigenvectors would be $$\left( \begin{array}{c} 1/\sqrt{2} \\ 0 \\ 0\\0 \\ \cdots \\ 0 \\ 0\\0\\1/\sqrt{2}\end{array} \right) \left( \begin{array}{c} 0\\ 1/\sqrt{2} \\ 0 \\ \\ \cdots \\ 0\\ \\ 1/\sqrt{2} \\ 0\end{array} \right) \cdots \left( \begin{array}{c} 0 \\ 0 \\0 \\ \cdots \\ 1/\sqrt{2} \\ 1/\sqrt{2} \\ \cdots \\ 0 \\ 0\end{array} \right) \left( \begin{array}{c} 0 \\ 0 \\0 \\ \cdots \\ 1/\sqrt{2} \\ -1/\sqrt{2} \\ \cdots \\ 0 \\ 0\end{array} \right) \cdots \left( \begin{array}{c} 0\\ 1/\sqrt{2} \\ 0 \\ \\ \cdots \\ 0\\ \\ -1/\sqrt{2} \\ 0\end{array} \right) \cdots \left( \begin{array}{c} 1/\sqrt{2} \\ 0 \\ 0\\0 \\ \cdots \\ 0 \\ 0\\0\\1/\sqrt{2}\end{array} \right)$$ where the first half of those have eigenvalue $2$ and the second half $0$.

If $n$ is odd, there is another possibility: All of the $x_i$ except the middle one are zero, and the eigenvalue is 1. So our set looks like $$\left( \begin{array}{c} 1/\sqrt{2} \\ 0 \\ 0\\0 \\ \cdots \\ \cdots \\ 0 \\ 0\\0\\1/\sqrt{2}\end{array} \right) \cdots \left( \begin{array}{c} 0 \\ 0 \\0 \\ \cdots \\ 1/\sqrt{2} \\ 0 \\ -1/\sqrt{2} \\ \cdots \\ 0 \\ 0\end{array} \right) \left( \begin{array}{c} 0 \\ 0 \\0 \\ \cdots \\ 0 \\ 1 \\ 0 \\ \cdots \\ 0 \\ 0\end{array} \right) \left( \begin{array}{c} 0 \\ 0 \\0 \\ \cdots \\ 1/\sqrt{2} \\ 0 \\ -1/\sqrt{2} \\ \cdots \\ 0 \\ 0\end{array} \right) \cdots \left( \begin{array}{c} 1/\sqrt{2} \\ 0 \\ 0\\0 \\ \cdots \\ \cdots \\ 0 \\ 0\\0\\1/\sqrt{2}\end{array} \right)$$ where the first almost-half of those have eigenvalue $2$, the middle one has eigenvalue $1$, and the second almost-half have eigenvalues $0$.

For example, $$\left( \begin{array}{ccccc} \frac{1}{\sqrt{2}} &0 & 0 & 0 & \frac{1}{\sqrt{2}} \\ 0 & \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} & 0 \\0 &0 & 1 & 0 & 1 \\ 0 & \frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}} & 0\\ \frac{1}{\sqrt{2}} & 0 &0 & 0 & -\frac{1}{\sqrt{2}} \end{array} \right) \left( \begin{array}{ccccc} 1 &0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0\\ 0 &0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0\\ 1 & 0 & 0 &0 & 1 \end{array} \right) \left( \begin{array}{ccccc} \frac{1}{\sqrt{2}} &0 & 0 & 0 & \frac{1}{\sqrt{2}} \\ 0 & \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} & 0 \\0 &0 & 1 & 0 & 1 \\ 0 & \frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}} & 0\\ \frac{1}{\sqrt{2}} & 0 &0 & 0 & -\frac{1}{\sqrt{2}} \end{array} \right) = \left( \begin{array}{ccccc} 2 &0 & 0 & 0 & 0 \\ 0 & 2 & 0 & -0 & 0 \\0 &0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{array} \right)$$

In the case that the matrix has an even size, we can find the eigenvalues of this matrix by adding $1$ to the eigenvalues of the matrix $$A = \begin{bmatrix} 0&0&0&\cdots&0&0&1\\ 0&0&0&\cdots&0&1&0\\ 0&0&0&\cdots&1&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&1&\cdots&0&0&0\\ 0&1&0&\cdots&0&0&0\\ 1&0&0&\cdots&0&0&0 \end{bmatrix}$$ Because $A^2 = I$ (check that this is the case), we can prove that the only eigenvalues $A$ can have are $\pm 1$.

Check that $A$ has an eigenvector for each eigenvalue (for example, try $e_1 + e_n$ and $e_1 - e_n$).

It follows that the original matrix has eigenvalues $0,2$.

In the case that the original matrix has an odd size, we will also have an eigenvalue $1$.

In fact, in order to diagonalize the matrix, we need to find all eigenvalues. In order to do so, verify that for each $j$, the vector $e_j + e_{n-j}$ is an eigenvector of the matrix, as is $e_j - e_{n-j}$. Here, $e_1,\dots,e_n$ denote the standard basis vectors.

Whether $n$ is even or odd, this will give you $n$ linearly independent eigenvectors, allowing you to diagonalize the matrix.

In general, a nice approach to diagonalizing matrices following a certain pattern of arbitrary size is to "guess" the eigenvectors.

• Sorry, glossed over that one. The quickest explanation is this: try multiplying the vector $e_{(n+1)/2}$ and see what happens. – Omnomnomnom Apr 28 '15 at 18:56