# Spectrum of circulant block matrix of circulant blocks (Adjacency matrix of discrete torus)

I am currently investigating the spectrum of a matrix $$M \in \mathbb{R}^{12 \times 12}$$. The matrix has the following form, $$M = \begin{bmatrix} 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ \end{bmatrix}.$$

We can rewrite this matrix as $$3 \times 3$$ block matrix, where each block is in $$\mathbb{R}^{4 \times 4}$$. Then we have, $$M = \left( \begin{array}{c|c|c} A & \mathbb{I}_{3} & \mathbb{I}_{3} \\ \hline \mathbb{I}_{3} & A & \mathbb{I}_{3} \\ \hline \mathbb{I}_{3} & \mathbb{I}_{3} & A \\ \end{array} \right),$$ where $$\mathbb{I}_{3}$$ is the $$3 \times 3$$ identity matrix and $$M \in \mathbb{R}^{3 \times 3}$$ is given by, $$M = \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ \end{bmatrix}.$$ Clearly, $$M$$ is circulant in block form and both $$A$$ and $$\mathbb{I}_{3}$$ are also circulant. However, $$M$$ itself is not a circulant matrix. Since $$A$$ and $$\mathbb{I}_{3}$$ we know that a orthonormal basis is given by the Fourier modes, $$v_j=\frac{1}{\sqrt{n}}\left(1, \omega^j, \omega^{2 j}, \ldots, \omega^{(n-1) j}\right). \quad j=0,1, \ldots, n-1$$ where $$\omega$$ is the $$n$$-unit root, i.e., $$\omega = e^{2\pi i/n}$$. Since in our case $$n=4$$ we get that $$v_j=\frac{1}{2}\left(1, \omega^{1j}, \omega^{2j}, \omega^{3 j}\right). \quad j=0,1,2,3$$ are the eigenvectors of $$A$$ and $$\mathbb{I}_{3}$$. I believe I can construct $$4$$ of the eigenvectors of $$M$$ using the Fourier-modes $$v_{j}$$, $$j=0,1,2,3$$. Since a vector $$w_{j}$$ $$w_j =\begin{bmatrix} v_{j} \\ v_{j} \\ v_{j} \end{bmatrix},$$ is an eigenvector of $$M$$. This holds since, $$Aw_{j}= \left( \begin{array}{c|c|c} A & \mathbb{I}_{3} & \mathbb{I}_{3} \\ \hline \mathbb{I}_{3} & A & \mathbb{I}_{3} \\ \hline \mathbb{I}_{3} & \mathbb{I}_{3} & A \\ \end{array} \right) \begin{bmatrix} v_{j} \\ v_{j} \\ v_{j} \end{bmatrix} = \begin{bmatrix} Av_{j} + v_{j} + v_{j} \\ v_{j} + Av_{j} + v_{j} \\ v_{j} + v_{j} +Av_{j} \end{bmatrix} = \begin{bmatrix} \lambda_{j}v_{j} + 2 v_{j} \\ \lambda_{j}v_{j} + 2 v_{j} \\ \lambda_{j}v_{j} + 2 v_{j} \end{bmatrix} = (\lambda_{j}v_{j} + 2 v_{j})\begin{bmatrix} v_{j} \\ v_{j} \\ v_{j} \end{bmatrix} = (\lambda_{j}v_{j} + 2 v_{j})w_{j} ,$$ where $$\lambda_{j}$$ is the eigenvalue of $$A$$ corresponding to the eigenvector $$v_{j}$$. We observe that the vectors $$w_{j}$$ are no Fourier modes for $$n=12$$.

Observe, the $$M$$ is the adjacency matrix for the undirected Cayley graph of the group $$\mathbb{Z}_{3} \times \mathbb{Z}_{4}$$ generated by the set $$\{ (1,0),(-1,0),(0,1),(0,1) \}$$. Clearly $$\mathbb{Z}_{3} \times \mathbb{Z}_{4} \simeq \mathbb{Z}_{12}$$, and $$\mathbb{Z}_{12}$$ is the cyclical group and the adjacency matrix of its Cayley graph is circular. Thus, I would imagine that the Fourier modes with $$n=12$$ are the eigenvectors of $$M$$. This seems inconsistent with the eigenvectors we constructed before.

Now to my questions:

Is there a way to calculate the entire spectrum of $$M$$? Are the Fourier modes also the eigenvectors of $$M$$ but with $$n=12$$? It would be helpful for me but does not seem to be the case. If they are not the eigenvectors, where am I going wrong in my second approach?

If your question is "is there a practical way to compute the eigenvectors" then you can simply ask your favorite programming language.

I used python's library sympy

from sympy import *
A = Matrix([[0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 ], [1 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 ], [0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 ], [1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 ], [1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 ], [0 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 0 ], [0 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 ], [0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 ], [1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 ], [0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 0 ], [0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 1 ], [0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 ]])
A.eigenvects()

which returns

[(-3, 2, [Matrix([ [ 1], [-1], [ 1], [-1], [-1], [ 1], [-1], [ 1], [ 0], [ 0], [ 0], [ 0]]),
Matrix([ [ 1], [-1], [ 1], [-1], [ 0], [ 0], [ 0], [ 0], [-1], [ 1], [-1], [ 1]])]),
(-1, 4, [Matrix([ [ 1], [ 0], [-1], [ 0], [-1], [ 0], [ 1], [ 0], [ 0], [ 0], [ 0], [ 0]]),
Matrix([ [ 0], [ 1], [ 0], [-1], [ 0], [-1], [ 0], [ 1], [ 0], [ 0], [ 0], [ 0]]),
Matrix([ [ 1], [ 0], [-1], [ 0], [ 0], [ 0], [ 0], [ 0], [-1], [ 0], [ 1], [ 0]]),
Matrix([ [ 0], [ 1], [ 0], [-1], [ 0], [ 0], [ 0], [ 0], [ 0], [-1], [ 0], [ 1]])]),
(0, 1, [Matrix([ [-1], [ 1], [-1], [ 1], [-1], [ 1], [-1], [ 1], [-1], [ 1], [-1], [ 1]])]),
(1, 2, [Matrix([ [-1], [-1], [-1], [-1], [ 1], [ 1], [ 1], [ 1], [ 0], [ 0], [ 0], [ 0]]),
Matrix([ [-1], [-1], [-1], [-1], [ 0], [ 0], [ 0], [ 0], [ 1], [ 1], [ 1], [ 1]])]),
(2, 2, [Matrix([ [-1], [ 0], [ 1], [ 0], [-1], [ 0], [ 1], [ 0], [-1], [ 0], [ 1], [ 0]]),
Matrix([ [ 0], [-1], [ 0], [ 1], [ 0], [-1], [ 0], [ 1], [ 0], [-1], [ 0], [ 1]])]),
(4, 1, [Matrix([ [1], [1], [1], [1], [1], [1], [1], [1], [1], [1], [1], [1]])])]

meaning that $$-3$$ is an eigenvalue of multiplicity $$2$$ associated with the eigenvectors $$\begin{pmatrix}1\\ -1\\ 1\\ -1\\ -1\\ 1\\ -1\\ 1\\ 0\\ 0\\ 0\\ 0 \end{pmatrix}$$ and $$\begin{pmatrix} 1\\ -1\\ 1\\ -1\\ 0\\ 0\\ 0\\ 0\\ -1\\ 1\\ -1\\ 1 \end{pmatrix}$$

(and so on for the other lines)

It means that the spectrum is $$S(M) = \{-3_2, -1_4, 0, 1_2,2_2,4\}$$.

From a theoretical point of view, you could look for a $$3 \times 3$$ generalization of the lemma "if $$AC=CA$$, $$\text{Det}\left( \begin{pmatrix} A & B\\ C & D\\ \end{pmatrix} \right) = \text{Det}\left( AD -CB \right)$$".

since you've got lots of identities matrices.