4
$\begingroup$

When does the circulant matrix have only integral roots?

For example: all roots of the adjacency matrix of the complete graph $K_n$ are integer, which its adjacency matrix is circulant, but in case of Cycle on $n>3$ vertices,$C_n$, the adjacency matrix is circulant but it may not have an integral roots.

$\endgroup$
6
$\begingroup$

Let $C$ be circulant of order $n\times n$. The first row of $C$ defines a complex function from the cyclic group $\mathbb{Z}_n$; denote its value on $i$ by $\rho(i)$. Define two elements $a$ and $b$ of $\mathbb{Z}_n$ to equivalent, and write $a\approx b$ if $a$ and $b$ generate the same subgroup of $\mathbb{Z}_n$. Then the eigenvalues of $C$ are all integers if and only the function $\rho$ is constant on $\approx$-classes.

Comments. First, this is due to Bridges and Mena ``Rational G-matrices with rational eigenvalues'', J. Comb. Theory A, (1982), 264-280,. Second it is easy to verify that the stated condition is sufficient and the necessity uses some elementary Galois theory. Finally, we do not need the group to be cyclic, just abelian (with the appropriate modifications to the definition of circulant).

$\endgroup$
  • $\begingroup$ I got that paper you mentioned, I will go through it. $\endgroup$ – L S B. user255259 Aug 19 '15 at 5:19
2
$\begingroup$

There are some good classification of Integral Cayley graphs, which by your terminology means all their adjacency matrix eigenvalues are integer. The adjacency matrices of Cayley graphs over cyclic groups is circulant.

Prof. Alireza Abdollahi and Dr. Vatandoost did some good classification of such graphs in the paper with name:

"Which Cayley Graphs are Integral?, The electronic journal of combinatorics 16 (2009), #R122"

Also, there is an other good resource for study the classification of integral Cayley graphs, which is:

"Integral Cayley graphs and groups, A. Ahmady, J. P. Bell, B. Mohar"

Also, you can see the paper:

"On groups all of whose undirected Cayley graphs of bounded valency are integral"

There are some good references in these three papers that I mentioned above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.