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!
 A: 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.
