1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .