Eigenvalues of symmetric block matrices related How to find eigenvalues of following block matrices? 
$M=\begin{bmatrix}
A & B & O & O & O  & O & O & \cdots & O & B\\
B & A & B & O & O  & O & O & \cdots & O & O\\
O & B & A & B & O  & O & O & \cdots & O & O\\
O & O & B & A & B  & O & O & \cdots & O & O\\
O & O & O & B & A  & B & O & \cdots & O & O\\
\vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \cdots & \vdots & \vdots\\
\vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \cdots & \vdots & \vdots\\
\vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \cdots & \vdots & \vdots\\
O & O & O & O & O  & O & O & O & A & B\\
B & O & O & O & O  & O & O & O & B & A\\
\end{bmatrix} $
$N=\begin{bmatrix}
A & B & O & O & O  & O & O & \cdots & O & O\\
B & A & B & O & O  & O & O & \cdots & O & O\\
O & B & A & B & O  & O & O & \cdots & O & O\\
O & O & B & A & B  & O & O & \cdots & O & O\\
O & O & O & B & A  & B & O & \cdots & O & O\\
\vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \cdots & \vdots & \vdots\\
\vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \cdots & \vdots & \vdots\\
\vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \cdots & \vdots & \vdots\\
O & O & O & O & O  & O & O & O & A & B\\
O & O & O & O & O  & O & O & O & B & A\\
\end{bmatrix} $
Where,
$A=\begin{bmatrix}
0 & 1 & 1 \\ 
1 & 0 & 1 \\ 
1 & 1 & 0
\end{bmatrix}$
$B=\begin{bmatrix}
1 & 0 & 0 \\ 
0 & 0 & 0 \\ 
0 & 0 & 0
\end{bmatrix}$
$O=\begin{bmatrix}
0 & 0 & 0 \\ 
0 & 0 & 0 \\ 
0 & 0 & 0
\end{bmatrix}$
 A: Let $n$ be the number of $3 \times 3$ blocks in each row and column of $M$.
Let $P$ be the $3n \times 3n$ permutation matrix such that $P_{k,3k-2} = P_{n+k,3k-1} = P_{2n+k,3k} = 1$ for $k = 1,2,\ldots,n$ and all other entries are $0$. 
Then, we have $$PMP^{-1} = \begin{bmatrix}X&I_{n \times n}&I_{n \times n}\\I_{n \times n}&O_{n \times n}&I_{n \times n}\\I_{n \times n}&I_{n \times n}&O_{n \times n}\end{bmatrix}$$ where $X$ is the $n \times n$ matrix defined by $$X = \begin{bmatrix}0 & 1 & & & 1 \\ 1 & 0 & \ddots & & \\ & \ddots & \ddots & \ddots & \\ & & \ddots & 0 & 1 \\ 1 & & & 1 & 0\end{bmatrix}.$$
The eigenvalues $\mu_k$ and corresponding eigenvectors $u_k$ of $X$ are $$\mu_k = 2\cos \dfrac{2k\pi}{n} \ \text{and} \ u_k = \begin{bmatrix}1\\e^{i2\pi k/n} \\ e^{i4\pi k/n} \\ \vdots \\ e^{i(2n-2)\pi/n}\end{bmatrix}, \ \text{for} \ k = 1,2,\ldots,n.$$
If $\lambda$ is an eigenvalue of $PMP^{-1}$ with corresponding eigenvector $\begin{bmatrix}a\\b\\c\end{bmatrix} \neq 0$, then \begin{align*}Xa+b+c = \lambda a \\ a+c = \lambda b \\ a+b = \lambda c \end{align*}
Adding equations 2 and 3 gives $2a = (\lambda-1)(b+c)$, so $b+c = \dfrac{2}{\lambda-1}a$ (I'll let you show that $\lambda = 1$ isn't possible). Substituting this into equation 1 gives $Xa = \left(\lambda - \dfrac{2}{\lambda-1}\right)a$. 
There are 2 possibilities:
1) $a$ is a scalar multiple of $u_k$ and $\lambda-\dfrac{2}{\lambda-1} = \mu_k \leadsto \lambda = \dfrac{1}{2}\left(\mu_k+1 \pm \sqrt{\mu_k^2-2\mu_k+9}\right)$
2) $a = 0$, which yields $b+c = 0$, and thus, $c = -b$. 
Combining the two cases, we get $3n$ eigenvalues and linearly independent eigenvectors of $PMP^{-1}$: 
$$\lambda_{+}^{(k)} = \dfrac{1}{2}\left(\mu_k+1+\sqrt{\mu_k^2-2\mu_k+9}\right) \ \text{and} \ w_{+}^{(k)} = \begin{bmatrix}u_k \\ \tfrac{1}{\lambda_{+}^{(k)}-1}u_k \\ \tfrac{1}{\lambda_{+}^{(k)}-1}u_k \end{bmatrix}, \ \text{for} \ k = 1,2,\ldots,n$$
$$\lambda_{-}^{(k)} = \dfrac{1}{2}\left(\mu_k+1-\sqrt{\mu_k^2-2\mu_k+9}\right) \ \text{and} \ w_{-}^{(k)} = \begin{bmatrix}u_k \\ \tfrac{1}{\lambda_{-}^{(k)}-1}u_k \\ \tfrac{1}{\lambda_{-}^{(k)}-1}u_k \end{bmatrix}, \ \text{for} \ k = 1,2,\ldots,n$$
$$\lambda^{(k)} = -1 \ \text{and} \ w^{(k)} = \begin{bmatrix}0\\\hat{e}_k \\ -\hat{e}_k\end{bmatrix}, \ \text{for} \ k = 1,2,\ldots,n.$$
The eigenvalues of $M$ are the same as the eigenvalues of $PMP^{-1}$.
We can do a similar calculation to get the eigenvalues of $N$. The only difference is that the eigenvalues for the matrix $X$ in this case are $\mu_k = 2\cos\dfrac{k\pi}{n+1}$, and the eigenvectors $u_k$ are different.
