# Integral mixed circulant graphs

Monu Kadyan and Bikash Bhattacharjya
Department of Mathematics
Indian Institute of Technology Guwahati, India
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Abstract

A mixed graph is said to be integral if all the eigenvalues of its Hermitian
adjacency matrix are integers. The mixed circulant graph
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is a mixed graph on the vertex set
$\mathbb{Z}_{n}$ and edge set $\\{(a,b):b-a\in\mathcal{C}\\}$, where
$0\not\in\mathcal{C}\subset{\mathbb{Z}}_{n}$. If $\mathcal{C}$ is closed under
inverse, then $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is called a circulant
graph. We express the eigenvalues of $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$
in terms of primitive $n$-th roots of unity, and find a sufficient condition
for integrality of the eigenvalues of
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$. For $n\equiv 0\ (\mathrm{mod}\ 4)$,
we factorize the $n$-th degree cyclotomic polynomial into two irreducible
factors over $\mathbb{Q}(i)$. Using this factorization, we characterize
integral mixed circulant graphs in terms of their symbol set. We also express
the integer eigenvalues of an integral oriented circulant graph in terms of a
Ramanujan type sum, and discuss some of their properties.

Keywords. mixed graph; Hermitian adjacency matrix; integral mixed graph; mixed
circulant graph.
Mathematics Subject Classification: 05C50, 05C25.

##  1 Introduction

We only consider graphs without loops and multi-edges. A (simple) graph $G$ is
denoted by $G=(V(G),E(G))$, where $V(G)$ is the vertex set of $G$, and the
edge set $E(G)\subset V(G)\times V(G)\setminus\\{(u,u)|u\in V(G)\\}$ with
$(u,v)\in E(G)$ if and only if $(v,u)\in E(G)$. A graph $G$ is said to be
oriented if $(u,v)\in E(G)$ implies that $(v,u)\not\in E(G)$. A graph $G$ is
said to be mixed if $(u,v)\in E(G)$ does not always imply that $(v,u)\in
E(G)$, see [24] for details. In a mixed graph $G$, we call an edge with end
vertices $u$ and $v$ to be undirected (resp. directed) if both $(u,v)$ and
$(v,u)$ belong to $E(G)$ (resp. only one of $(u,v)$ and $(v,u)$ belongs to
$E(G)$). An undirected edge $(u,v)$ is denoted by $u\leftrightarrow v$, and a
directed edge $(u,v)$ is denoted by $u\rightarrow v$. Hence a mixed graph can
have both directed and undirected edges. Note that if all edges of a mixed
graph $G$ are directed (resp. undirected) then $G$ is an oriented graph (resp.
a simple graph). For a mixed graph $G$, the underlying graph $G_{U}$ of $G$ is
the simple undirected graph in which all edges of $G$ are considered
undirected. By the terms of order, size, number of components, degree of a
vertex, distance between two vertices etc., we mean that they are the same as
in their underlying graphs.

In 2015, Liu and Li [24] introduced Hermitian adjacency matrix of a mixed
graph. For a mixed graph with $n$ vertices, its Hermitian adjacency matrix is
denoted by $H(G)=(h_{uv})_{n\times n}$, where $h_{uv}$ is given by

$h_{uv}=\left\\{\begin{array}[]{rl}1&\mbox{ if }(u,v)\in E\textnormal{ and
}(v,u)\in E\\\ i&\mbox{ if }(u,v)\in E\textnormal{ and }(v,u)\not\in E\\\
-i&\mbox{ if }(u,v)\not\in E\textnormal{ and }(v,u)\in E\\\ 0&\textnormal{
otherwise.}\end{array}\right.$

Here $i=\sqrt{-1}$ is the imaginary number unit. Hermitian adjacency matrix of
a mixed graph incorporates both adjacency matrix of simple graph and skew-
adjacency matrix of an oriented graph. The Hermitian spectrum of $G$, denoted
by $Sp_{H}(G)$, is the multi set of the eigenvalues of $H(G)$. It is easy to
see that $H(G)$ is a Hermitian matrix and so $Sp_{H}(G)\subseteq\mathbb{R}$.

For each edge $(i,j)$ of an weighted directed graph $G$, let a complex number
$w_{ij}$ of unit modulus be considered as an weight of the edge $(i,j)$. In
[6], the authors defined the adjacency matrix $A(G)=[a_{ij}]$ of an weighted
directed graph $G$ by

$a_{ij}=\left\\{\begin{array}[]{ll}w_{ij}&\mbox{ if }(i,j)\in E(G)\\\
\overline{w}_{ij}&\mbox{ if }(j,i)\in E(G)\\\ 0&\textnormal{
otherwise.}\end{array}\right.$

The authors in [6] mainly discussed singularity of the corresponding Laplacian
matrix of an weighted directed graph. One can see that the Hermitian adjacency
matrix of a mixed graph is a special case of the adjacency matrix of an
weighted directed graph. In this article, our focus however is to study
integrality of the spectrum of the Hermitian adjacency matrix of a mixed
circulant graph.

A mixed graph is said to be integral if all the eigenvalues of its Hermitian
adjacency matrix are integers. Integral graphs were first defined by Harary
and Schwenk in 1974 [18] and proposed a classification of integral graphs. See
[5] for a survey on integral graphs. Watanabe and Schwenk [32, 33] proved
several interesting results on integral trees in 1979. Csikvari [15]
constructed integral trees with arbitrary large diameters in 2010. Further
research on integral trees can be found in [10, 11, 30, 31]. In $2009$, Ahmadi
et al. [2] proved that only a fraction of $2^{-\Omega(n)}$ of the graphs on
$n$ vertices have an integral spectrum. Bussemaker et al. [12] proved that
there are exactly $13$ connected cubic integral graphs. Stevanović [29]
studied the $4$-regular integral graphs avoiding $\pm 3$ in the spectrum, and
Lepović et al. [23] proved that there are $93$ non-regular, bipartite integral
graphs with maximum degree four. In 2017, Guo et. al. [17] found all possible
mixed graphs on $n$ vertices with spectrum $\\{-n+1,-1,-1,...,-1\\}$.

Let $\Gamma$ be a group, $\mathcal{C}\subseteq\Gamma$ and $\mathcal{C}$ does
not contain identity element of $\Gamma$. The set $\mathcal{C}$ is said to be
symmetric (resp. skew-symmetric) if $\mathcal{C}$ is closed under inverse
(resp. $a^{-1}\not\in\mathcal{C}$ for all $a\in\mathcal{C}$). Define
$\overline{\mathcal{C}}=\\{u\in\mathcal{C}:u^{-1}\not\in\mathcal{C}\\}$.
Clearly $\mathcal{C}\setminus\overline{\mathcal{C}}$ is symmetric and
$\overline{\mathcal{C}}$ is skew-symmetric. The mixed Cayley graph
$G=Cay(\Gamma,\mathcal{C})$ is a mixed graph, where $V(G)=\Gamma$ and
$E(G)=\\{(a,b):a,b\in\Gamma,ba^{-1}\in\mathcal{C}\\}$. Since we have not
assumed that $\mathcal{C}$ is symmetric, so mixed Cayley graph can have
directed edges. If $\mathcal{C}$ is symmetric, then $G$ is a (simple) Cayley
graph. If $\mathcal{C}$ is skew-symmetric then $G$ is an oriented Cayley
graph.

In 1982, Bridge and Mena [9] introduced a characterization of integral Cayley
graphs over abelian group. Later on, same characterization was rediscovered by
Wasin So [28] for cyclic groups in 2006. In 2009, Abdollahi and Vatandoost [1]
proved that there are exactly seven connected cubic integral Cayley graphs. On
the same year, Klotz and Sander [21] proved that if a Cayley graph
$Cay(\Gamma,\mathcal{C})$ over an abelian group $\Gamma$ is integral then
$\mathcal{C}$ belongs to the Boolean algebra $\mathbb{B}(\Gamma)$ generated by
the subgroups of $\Gamma$. Moreover, they conjectured that the converse is
also true, which was proved by Alperin and Peterson [4]. In 2014, Cheng et al.
[22] proved that normal Cayley graphs (its symbol set is closed under
conjugation) over symmetric groups are integral. Alperin [3] gave a
characterization of integral Cayley graphs over finite groups. In 2017, Lu et
al. [25] gave necessary and sufficient condition for the integrality of Cayley
graphs over dihedral group $D_{n}=\langle
a,b|a^{n}=b^{2}=1,bab=a^{-1}\rangle$. In particular, they completely
determined all integral Cayley graphs over the dihedral group $D_{p}$ for a
prime $p$. In 2019, Cheng et al.[13] obtained several simple sufficient
conditions for the integrality of Cayley graphs over dicyclic group
$T_{4n}=\langle a,b|a^{2n}=1,a^{n}=b^{2},b^{-1}ab=a^{-1}\rangle$. In
particular, they also completely determined all integral Cayley graphs over
the dicyclic group $T_{4p}$ for a prime $p$. However, it is far from being
solved to obtain an explicit characterization of integral mixed Cayley graphs.
As a simple attempt to this aspect, we give a characterization of integral
mixed Cayley graphs over cyclic groups in this paper. If
$\Gamma=\mathbb{Z}_{n}$ then the mixed Cayley graph
$Cay(\mathbb{Z}_{n},\mathcal{C})$ is known as mixed circulant graph, we denote
it by $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$. If $\mathcal{C}$ is symmetric
then $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is a (simple) circulant graph.
If $\mathcal{C}$ is skew-symmetric then
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is an oriented circulant graph.

This paper is organized as follows. In second section, we express the
eigenvalues of a mixed circulant graph as a sum of eigenvalues of a simple
circulant graph and an oriented circulant graph. In third section, for
$n\equiv 0\ (\mathrm{mod}\ 4)$, we obtain a sufficient condition on the set
$\mathcal{C}$ for integral mixed circulant graphs. In fourth section, for
$n\equiv 0\ (\mathrm{mod}\ 4)$, we obtain two monic irreducible factors
$\Phi_{n}^{1}(x)$ and $\Phi_{n}^{3}(x)$ of the cyclotomic polynomial
$\Phi_{n}(x)$ over $\mathbb{Q}(i)$ such that
$\Phi_{n}(x)=\Phi_{n}^{1}(x)\cdot\Phi_{n}^{3}(x)$. Note that for $n\not\equiv
0\ (\mathrm{mod}\ 4)$, the cyclotomic polynomial $\Phi_{n}(x)$ is irreducible
over $\mathbb{Q}(i)$. We prove for even positive integer $n$ that
$n/2=\sum\limits_{d\in D_{n}}\varphi(n/d)$, where $D_{n}$ is the set of all
odd divisors of $n$. In Section 5, we characterize integral mixed circulant
graphs in terms of their symbol set. In the last section, we express the
integer eigenvalues of an integral oriented circulant graph in terms of a
Ramanujan type sum, and discuss some of their properties.

Indeed, Theorem 5.4 of this paper is a special case of Theorem 25 in [20]. The
group for the Cayley graph in this present paper is the special abelian group
${\mathbb{Z}}_{n}$. As a result, the proof techniques of a few intermediary
results in this paper are quite different from that in [20]. Due to the
special abelian group ${\mathbb{Z}}_{n}$, the results and their proofs in this
paper give more insights into the concepts and derivations as compared to that
in [20]. Further, the results of Section 6 of this paper has great potential
of using in the investigation of “Quantum State Transfers” (ref. [7]) of mixed
circulant graphs.

##  2 Oriented and mixed circulant graphs

An $n\times n$ circulant matrix $C$ have the form

$C=\begin{pmatrix}c_{0}&c_{1}&c_{2}&\cdots&c_{n-1}\\\
c_{n-1}&c_{0}&c_{1}&\cdots&c_{n-2}\\\ c_{n-2}&c_{n-1}&c_{0}&\cdots&c_{n-3}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
c_{1}&c_{2}&c_{3}&\cdots&c_{0}\end{pmatrix},$

where each row is a cyclic shift of the preceding row. We see that the
$(j,k)$-th entry of $C$ is $c_{k-j\ (\mathrm{mod}\ n)}$. We denote such a
circulant matrix by $C=\text{Circ}(c_{0},...,c_{n-1})$.

The circulant matrix $C$ is diagonalizable by the matrix $F$ whose $k$-th
column is given by

$F_{k}=\frac{1}{\sqrt{n}}[1,w_{n}^{k},...,w_{n}^{(n-1)k}]^{t},$

where $w_{n}=\exp(2\pi i/n)$ and $0\leq k\leq(n-1)$. The eigenvalues of $C$
are

$\lambda_{k}=\sum\limits_{l=0}^{n-1}c_{l}w_{n}^{lk}\textnormal{ for
}k=0,1,...,n-1.$

See [16] for more information on circulant matrices. Let
$G=\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ be a mixed circulant graph on $n$
vertices. Let $c_{j\ (\mathrm{mod}\ n)}=h_{1~{}j+1}$. We see that
$h_{jk}=c_{k-j\ (\mathrm{mod}\ n)}$. So the Hermitian adjacency matrix of a
mixed circulant graph is a circulant matrix.

######  Lemma 2.1.

The spectrum of the mixed circulant graph
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is
$\\{\gamma_{0},\gamma_{1},...,\gamma_{n-1}\\}$, where
$\gamma_{j}=\lambda_{j}+\mu_{j}$,

$\lambda_{j}=\sum\limits_{k\in\mathcal{C}\setminus\overline{\mathcal{C}}}w_{n}^{jk}\textnormal{
and
}\mu_{j}=i\sum\limits_{k\in\overline{\mathcal{C}}}(w_{n}^{jk}-w_{n}^{-jk})\textnormal{
for }j=0,1,...,n-1.$

###### Proof.

Since Hermitian adjacency matrix of a mixed circulant graph is a circulant
matrix, the eigenvalues of $H(G)$ are

$\gamma_{j}=\sum\limits_{k\in\mathcal{C}\setminus\overline{\mathcal{C}}}w_{n}^{jk}+i\sum\limits_{k\in\overline{\mathcal{C}}}w_{n}^{jk}-i\sum\limits_{k\in\overline{\mathcal{C}}}w_{n}^{-jk}=\lambda_{j}+\mu_{j}.$

∎

Observe that $\lambda_{j}=\lambda_{n-j}$ and $\mu_{j}=-\mu_{n-j}$ for all
$j=0,1,...,n-1$. Next two corollaries are special cases of Lemma 2.1.

######  Corollary 2.1.1.

[8] The spectrum of the circulant graph
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is
$\\{\lambda_{0},\lambda_{1},...,\lambda_{n-1}\\}$, where

$\lambda_{j}=\sum\limits_{k\in\mathcal{C}}w_{n}^{jk}\textnormal{ for
}j=0,1,...,n-1.$

######  Corollary 2.1.2.

The spectrum of the oriented circulant graph
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is
$\\{\mu_{0},\mu_{1},...,\mu_{n-1}\\}$, where

$\mu_{j}=i\sum\limits_{k\in{\mathcal{C}}}(w_{n}^{jk}-w_{n}^{-jk})\textnormal{
for }0\leq j\leq n-1.$

From Lemma 2.1, we observe that the eigenvalues of a mixed circulant graph
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ are the sum of the eigenvalues of
the circulant graph
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C}\setminus\overline{\mathcal{C}})$ and
the oriented circulant graph
$\text{Circ}(\mathbb{Z}_{n},\overline{\mathcal{C}})$.

Let $n\geq 2$ be a fixed positive integer. We review some basic definitions
and notations from Wasin So [28]. For a divisor $d$ of $n$, define
$M_{n}(d)=\\{d,2d,...,n-d\\}$, the set of all positive multiples of $d$ less
than $n$. Similarly, for a divisor $d$ of $n$, define $G_{n}(d)=\\{k:1\leq
k\leq n-1,\gcd(k,n)=d\\}$. It is clear that $M_{n}(n)=G_{n}(n)=\emptyset$,
$M_{n}(d)=dM_{(n/d)}(1)$ and $G_{n}(d)=dG_{(n/d)}(1)$.

######  Lemma 2.2.

[28] If $n=dg$ for some $d,g\in\mathbb{Z}$ then
$M_{n}(d)=\bigcup\limits_{h\mid g}G_{n}(hd)$.

######  Theorem 2.3.

[28] Let $d$ be a proper divisor of $n$. If $x^{n}=1$ then
$\sum\limits\limits_{q\in G_{n}(d)}x^{q}\in\mathbb{Z}$.

Wasin So [28] characterized integral circulant graphs in the following
theorem. Several results of this paper are influenced by [28].

######  Theorem 2.4.

[28] The circulant graph $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is integral
if and only if $\mathcal{C}=\bigcup\limits_{d\in\mathscr{D}}G_{n}(d)$, where
$\mathscr{D}\subseteq\\{d:d\mid n\\}$.

The next lemma will help us to extend characterization of integral oriented
circulant graphs to integral mixed circulant graphs.

######  Lemma 2.5.

The mixed circulant graph $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is
integral if and only if both
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C}\setminus\overline{\mathcal{C}})$ and
$\text{Circ}(\mathbb{Z}_{n},\overline{\mathcal{C}})$ are integral.

###### Proof.

Let $\gamma_{j}$ be an integer eigenvalue of the mixed circulant graph
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$. By Lemma 2.1,
$\gamma_{j}=\lambda_{j}+\mu_{j}$ and $\gamma_{n-j}=\lambda_{j}-\mu_{j}$ for
all $j=0,...,n-1$, where $\lambda_{j}$ is an eigenvalue of
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C}\setminus\overline{\mathcal{C}})$ and
$\mu_{j}$ is an eigenvalue of
$\text{Circ}(\mathbb{Z}_{n},\overline{\mathcal{C}})$. Thus
$\lambda_{j}=\frac{\gamma_{j}+\gamma_{n-j}}{2}\in\mathbb{Q}$ and
$\mu_{j}=\frac{\gamma_{j}-\gamma_{n-j}}{2}\in\mathbb{Q}$. As $\lambda_{j}$ and
$\mu_{j}$ are algebraic integers, $\lambda_{j},\mu_{j}\in\mathbb{Q}$ implies
that $\lambda_{j}$ and $\mu_{j}$ are integers. Thus the circulant graph
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C}\setminus\overline{\mathcal{C}})$ and
the oriented circulant graph
$\text{Circ}(\mathbb{Z}_{n},\overline{\mathcal{C}})$ are integral.

Conversely, assume that both
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C}\setminus\overline{\mathcal{C}})$ and
$(\mathbb{Z}_{n},\overline{\mathcal{C}})$ are integral. Then Lemma 2.1 implies
that $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is integral. ∎

Since some characterization of integral circulant graphs are known from [28],
in view of Lemma 2.5, it is enough to find characterization of oriented
circulant graphs. Note that $x^{n}=1$ if and only if $x\in\\{w_{n}^{t}:0\leq
t\leq n-1\\}$, where $w_{n}=\exp(\frac{2\pi i}{n})$. Therefore the oriented
circulant graph $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is integral if and
only if $\sum\limits_{k\in\mathcal{C}}i(x^{k}-x^{(n-k)})\in\mathbb{Z}$ for all
$x$ satisfying $x^{n}=1$.

##  3 Sufficient condition for integral mixed circulant graph on $n\equiv 0\
(\mathrm{mod}\ 4)$ vertices

Let $n\equiv 0\ (\mathrm{mod}\ 4)$ be a fixed positive integer throughout this
section. For a divisor $d$ of $\frac{n}{4}$ and $r\in\\{0,1,2,3\\}$, define
$M_{n}^{r}(d)=\\{dk:0\leq dk<n,k\equiv r\ (\mathrm{mod}\ 4)\\}$. For
$g\in\mathbb{Z}$, let $D_{g}$ be the set of all odd divisors of $g$.

######  Lemma 3.1.

Let $n=4dg$ for some $d,g\in\mathbb{Z}$. Then the following are true:

  1. (i)

$M_{n}^{1}(d)\bigcup M_{n}^{3}(d)=\bigcup\limits_{h\in D_{g}}G_{n}(hd)$,

  2. (ii)

$M_{n}^{2}(d)=\bigcup\limits_{h\in D_{g}}G_{n}(2hd)$,

  3. (iii)

$M_{n}^{0}(d)=M_{n}(4d)\bigcup\\{0\\}$.

###### Proof.

  1. (i)

Let $dk\in M_{n}^{1}(d)\bigcup\limits M_{n}^{3}(d)$. Since $k\equiv 1$ or $3\
(\mathrm{mod}\ 4)$, it follows that $k$ is an odd integer. So $\gcd(k,g)=h\in
D_{g}$. Hence $\gcd(kd,n)=\gcd(kd,4dg)=hd$ implies that $M_{n}^{1}(d)\bigcup
M_{n}^{3}(d)\subseteq\bigcup\limits_{h\in D_{g}}G_{n}(hd)$. On the other hand,
if $x\in\bigcup\limits_{h\in D_{g}}G_{n}(hd)$ then there exists $h\in D_{g}$
such that $\gcd(x,n)=hd$. So there exists $x_{0}\in\mathbb{Z}$ such that
$x=hdx_{0}$ and $\gcd(x_{0},\frac{n}{hd})=1$. Since $\frac{n}{hd}$ is an even
integer and $\gcd(x_{0},\frac{n}{hd})=1$, so $x$ is an odd multiple of $d$.
Note that $M_{n}^{1}(d)\bigcup M_{n}^{3}(d)$ is the set of all odd multiples
of $d$ between $0$ and $n$. Thus $x\in M_{n}^{1}(d)\bigcup M_{n}^{3}(d)$.
Hence $\bigcup\limits_{h\in D_{g}}G_{n}(hd)\subseteq M_{n}^{1}(d)\bigcup
M_{n}^{3}(d)$.

  2. (ii)

Let $dk\in M_{n}^{2}(d)$ and $h=\gcd(\frac{k}{2},g)$. Since $k\equiv 2\
(\mathrm{mod}\ 4)$, we see that $\gcd(k,4g)=2h$. This gives
$\gcd(kd,n)=\gcd(kd,4dg)=2hd$, and so
$M_{n}^{2}(d)\subseteq\bigcup\limits_{h\in D_{g}}G_{n}(2hd)$. On the other
hand, if $x\in\bigcup\limits_{h\in D_{g}}G_{n}(2hd)$, there exists $h\in
D_{g}$ such that $\gcd(x,n)=2hd$. So there exists $x_{0}\in\mathbb{Z}$ such
that $x=2hdx_{0}$ and $\gcd(x_{0},\frac{n}{2hd})=1$. Since $\frac{n}{2hd}$ is
an even integer and $\gcd(x_{0},\frac{n}{2hd})=1$, so $x_{0}$ is an odd
integer. Now $h,x_{0}$ are odd integers, and so letting $\alpha=2hx_{0}$, we
get $x=\alpha d$, where $\alpha\equiv 2\ (\mathrm{mod}\ 4)$. Hence $x\in
M_{n}^{2}(d)$. Thus $\bigcup\limits_{h\in D_{g}}G_{n}(2hd)\subseteq
M_{n}^{2}(d)$.

  3. (iii)

By definition, we have

$\begin{split}M_{n}^{0}(d)&=\\{dk:0\leq dk\leq n-1,k=4\alpha\textnormal{ for
some }\alpha\in\mathbb{Z}\\}\\\ &=\\{4\alpha d:1\leq 4\alpha d\leq
n-1\textnormal{ for some }\alpha\in\mathbb{Z}\\}\cup\\{0\\}\\\
&=M_{n}(4d)\cup\\{0\\}.\end{split}$

∎

######  Lemma 3.2.

If $x^{n}=1$ and $n=4dg$ for some $d,g\in\mathbb{Z}$, then $\sum\limits_{q\in
M_{n}^{r}(d)}x^{q}\in\mathbb{Z}$ for $r=0,2$.

###### Proof.

From Lemma 3.1 and Lemma 2.2, we have $M_{n}^{0}(d)=\bigcup\limits_{h\mid
g}G_{n}(4hd)\bigcup\limits\\{0\\}$. Therefore

$\begin{split}\sum\limits_{q\in M_{n}^{0}(d)}x^{q}=1+\sum\limits_{h\mid
g}\sum\limits_{q\in G_{n}(4hd)}x^{q}.\end{split}$ (1)

As $G_{n}(4gd)=G_{n}(n)=\emptyset$, the summation in (1) is over proper
divisors of $g$. Theorem 2.3 now implies that $\sum\limits_{q\in
M_{n}^{0}(d)}x^{q}\in\mathbb{Z}$. Similarly, one can show that
$\sum\limits_{q\in M_{n}^{2}(d)}x^{q}\in\mathbb{Z}$. ∎

######  Lemma 3.3.

If $x^{n}=1$ and $n=4dg$ for some $d,g\in\mathbb{Z}$, then

$i\bigg{(}\sum\limits_{q\in
M_{n}^{1}(d)}x^{q}\bigg{)}-i\bigg{(}\sum\limits_{q\in
M_{n}^{3}(d)}x^{q}\bigg{)}\in\mathbb{Z}.$

###### Proof.

We have

$\begin{split}(x^{n}-1)&=(x^{d}-i)\bigg{(}\sum\limits_{k=1}^{4g}i^{k-1}x^{n-dk}\bigg{)}\\\
&=(x^{d}-i)\bigg{(}\sum\limits_{k=1}^{4g}i^{k}x^{n-dk}\bigg{)}(-i)\\\
&=-i(x^{d}-i)\bigg{(}\sum\limits_{\begin{subarray}{c}1\leq k\leq 4g\\\ k\equiv
0\ (\mathrm{mod}\
4)\end{subarray}}x^{n-dk}-\sum\limits_{\begin{subarray}{c}1\leq k\leq 4g\\\
k\equiv 3\ (\mathrm{mod}\
4)\end{subarray}}ix^{n-dk}-\sum\limits_{\begin{subarray}{c}1\leq k\leq 4g\\\
k\equiv 2\ (\mathrm{mod}\
4)\end{subarray}}x^{n-dk}+\sum\limits_{\begin{subarray}{c}1\leq k\leq 4g\\\
k\equiv 1\ (\mathrm{mod}\ 4)\end{subarray}}ix^{n-dk}\bigg{)}\\\
&=-i(x^{d}-i)\bigg{(}\sum\limits_{q\in M_{n}^{0}(d)}x^{q}-\sum\limits_{q\in
M_{n}^{1}(d)}ix^{q}-\sum\limits_{q\in M_{n}^{2}(d)}x^{q}+\sum\limits_{q\in
M_{n}^{3}(d)}ix^{q}\bigg{)}\\\ &=i(x^{d}-i)\bigg{(}\sum\limits_{q\in
M_{n}^{1}(d)}ix^{q}-\sum\limits_{q\in M_{n}^{3}(d)}ix^{q}-\sum\limits_{q\in
M_{n}^{0}(d)}x^{q}+\sum\limits_{q\in M_{n}^{2}(d)}x^{q}\bigg{)}.\end{split}$

Case 1. Assume that $x^{d}-i=0$.
If $q\in M_{n}^{1}(d)$ then $q=(4y_{1}+1)d$ for some $y_{1}\in\mathbb{Z}$. So
$x^{q}=x^{4y_{1}d+d}=x^{d}(x^{d})^{4y_{1}}=i\cdot i^{4y_{1}}=i$.
If $q\in M_{n}^{3}(d)$ then $q=(4y_{3}+3)d$ for some $y_{3}\in\mathbb{Z}$. So
$x^{q}=x^{4y_{3}d+3d}=(x^{d})^{3}(x^{d})^{4y_{3}}=i^{3}\cdot i^{4y_{3}}=-i$.
Thus

$i\bigg{(}\sum\limits_{q\in
M_{n}^{1}(d)}x^{q}\bigg{)}-i\bigg{(}\sum\limits_{q\in
M_{n}^{3}(d)}x^{q}\bigg{)}=i\bigg{(}\sum\limits_{q\in
M_{n}^{1}(d)}i\bigg{)}-i\bigg{(}\sum\limits_{q\in
M_{n}^{3}(d)}-i\bigg{)}=-|M_{n}^{1}(d)\cup M_{n}^{3}(d)|\in\mathbb{Z}.$

Case 2. Assume that $x^{d}-i\neq 0$. Then

$\sum\limits_{q\in M_{n}^{1}(d)}ix^{q}-\sum\limits_{q\in
M_{n}^{3}(d)}ix^{q}-\sum\limits_{q\in M_{n}^{0}(d)}x^{q}+\sum\limits_{q\in
M_{n}^{2}(d)}x^{q}=0,\textnormal{ as }x^{n}-1=0$

$\Rightarrow\sum\limits_{q\in M_{n}^{1}(d)}ix^{q}-\sum\limits_{q\in
M_{n}^{3}(d)}ix^{q}=\sum\limits_{q\in M_{n}^{0}(d)}x^{q}-\sum\limits_{q\in
M_{n}^{2}(d)}x^{q}\in\mathbb{Z},\textnormal{ by Lemma }\ref{iocg2}.$

∎

Let $n=4dg$ for some $d,g\in\mathbb{Z}$. Since $1\in D_{g}$, Lemma 3.1 gives
$G_{n}(d)\subseteq M_{n}^{1}(d)\cup M_{n}^{3}(d)$. For $r\in\\{1,3\\}$, define

$G_{n}^{r}(d)=\\{dk:k\equiv r\ (\mathrm{mod}\ 4),\gcd(dk,n)=d\\}.$

In the next lemma, we prove that $G_{n}(d)$ is a disjoint union of
$G_{n}^{1}(d)$ and $G_{n}^{3}(d)$. For $r\in\\{1,3\\}$, define $D_{g}^{r}$ to
be the set of all odd divisors of $g$ which are congruent to $r$ modulo $4$.
Note that $D_{g}=D_{g}^{1}\bigcup\limits D_{g}^{3}$.

######  Lemma 3.4.

If $n=4dg$ for some $d,g\in\mathbb{Z}$, then the following hold:

  1. (i)

$G_{n}^{1}(d)\cap G_{n}^{3}(d)=\emptyset$,

  2. (ii)

$G_{n}(d)=G_{n}^{1}(d)\cup G_{n}^{3}(d)$,

  3. (iii)

$M_{n}^{1}(d)=\bigg{(}\bigcup\limits_{h\in
D_{g}^{1}}G_{n}^{1}(hd)\bigg{)}\cup\bigg{(}\bigcup\limits_{h\in
D_{g}^{3}}G_{n}^{3}(hd)\bigg{)}$,

  4. (iv)

$M_{n}^{3}(d)=\bigg{(}\bigcup\limits_{h\in
D_{g}^{1}}G_{n}^{3}(hd)\bigg{)}\cup\bigg{(}\bigcup\limits_{h\in
D_{g}^{3}}G_{n}^{1}(hd)\bigg{)}$.

###### Proof.

  1. (i)

It is clear from the definitions of $G_{n}^{1}(d)$ and $G_{n}^{3}(d)$ that
$G_{n}^{1}(d)\cap G_{n}^{3}(d)=\emptyset$.

  2. (ii)

Since $G_{n}^{1}(d)\subseteq G_{n}(d)$ and $G_{n}^{3}(d)\subseteq G_{n}(d)$,
so $G_{n}^{1}(d)\cup G_{n}^{3}(d)\subseteq G_{n}(d)$. On the other hand, if
$x\in G_{n}(d)$ then $x=d\alpha$ for some $\alpha$. Note that
$\gcd(\alpha,\frac{n}{d})=1$, so $\alpha$ is an odd integer. Thus
$\alpha\equiv 1\ (\mathrm{mod}\ 4)$ or $\alpha\equiv 3\ (\mathrm{mod}\ 4)$.
Hence $G_{n}(d)\subseteq G_{n}^{1}(d)\cup G_{n}^{3}(d)$.

  3. (iii)

Let $dk\in M_{n}^{1}(d)$ so that $k\equiv 1\ (\mathrm{mod}\ 4)$. Lemma 3.1
gives an $h\in D_{g}$ satisfying $dk\in G_{n}(hd)$. Thus $dk\in G_{n}^{1}(hd)$
or $dk\in G_{n}^{3}(hd)$, by Part $(ii)$.
Case 1: Assume that $h\equiv 1\ (\mathrm{mod}\ 4)$.
Let, if possible, $dk\in G_{n}^{3}(hd)$, $i.e.$, $dk=\alpha hd$, where
$\alpha\equiv 3\ (\mathrm{mod}\ 4)$ and $\gcd(\alpha,\frac{n}{hd})=1$. Then we
have $k=\alpha h\equiv 3\ (\mathrm{mod}\ 4)$, a contradiction. Hence $dk\in
G_{n}^{1}(hd)$.
Case 2: Assume that $h\equiv 3\ (\mathrm{mod}\ 4)$.
Let, if possible, $dk\in G_{n}^{1}(hd)$. Then as in Case 1, we get a
contradiction. Hence $dk\in G_{n}^{3}(hd)$.
Thus $M_{n}^{1}(d)\subseteq\bigg{(}\bigcup\limits_{h\in
D_{g}^{1}}G_{n}^{1}(hd)\bigg{)}\cup\bigg{(}\bigcup\limits_{h\in
D_{g}^{3}}G_{n}^{3}(hd)\bigg{)}$. On the other hand, if $\alpha hd\in
G_{n}^{1}(hd)$, where $h\in D_{g}^{1}$ and $\alpha\equiv 1\ (\mathrm{mod}\
4)$, we get $\alpha h\equiv 1\ (\mathrm{mod}\ 4)$, $i.e.$, $\alpha hd\in
M_{n}^{1}(d)$. Similarly, $\beta hd\in G_{n}^{3}(hd)\Rightarrow\beta hd\in
M_{n}^{1}(d)$. Therefore, $\bigg{(}\bigcup\limits_{h\in
D_{g}^{1}}G_{n}^{1}(hd)\bigg{)}\cup\bigg{(}\bigcup\limits_{h\in
D_{g}^{3}}G_{n}^{3}(hd)\bigg{)}\subseteq M_{n}^{1}(d)$.

  4. (iv)

The proof of this part is similar to the proof of Part (iii).

∎

Note that $G_{n}(d)=dG_{(n/d)}(1)$. Therefore $G_{n}(d)=G_{n}^{1}(d)\cup
G_{n}^{3}(d)$ gives that $G_{n}^{1}(d)=dG_{(n/d)}^{1}(1)$ and
$G_{n}^{3}(d)=dG_{(n/d)}^{3}(1)$.

######  Theorem 3.5.

Let $n\equiv 0\ (\mathrm{mod}\ 4)$ and $d_{1}=\frac{n}{4}>d_{2}>...>d_{s}=1$
be all positive divisors of $\frac{n}{4}$. If $x^{n}=1$, then

$\sum\limits_{q\in G_{n}^{1}(d_{k})}ix^{q}-\sum\limits_{q\in
G_{n}^{3}(d_{k})}ix^{q}\in\mathbb{Z}\textnormal{ for }k=1,2,...,s.$

###### Proof.

Apply induction on $k$. For $k=1$, take $d_{1}=\frac{n}{4}$, $g_{1}=1$ in
Lemma 3.4 to get $M_{n}^{1}(d_{1})=G_{n}^{1}(d_{1})$ and
$M_{n}^{3}(d_{1})=G_{n}^{3}(d_{1})$.
Hence by Lemma 3.3, $\sum\limits_{q\in
G_{n}^{1}(d_{1})}ix^{q}-\sum\limits_{q\in
G_{n}^{3}(d_{1})}ix^{q}\in\mathbb{Z}$.
Assume that the statement holds for $k$, where $1\leq k<s$. To show that
$\sum\limits_{q\in G_{n}^{1}(d_{k+1})}ix^{q}-\sum\limits_{q\in
G_{n}^{3}(d_{k+1})}ix^{q}$ is an integer. Now $n=4d_{k+1}g_{k+1}$ for some
$d_{k+1},g_{k+1}\in\mathbb{Z}$. Lemma 3.4 implies that

$\begin{split}M_{n}^{1}(d_{k+1})=\bigg{(}\bigcup\limits_{h\in
D_{g_{k+1}}^{1}}G_{n}^{1}(hd_{k+1})\bigg{)}\cup\bigg{(}\bigcup\limits_{h\in
D_{g_{k+1}}^{3}}G_{n}^{3}(hd_{k+1})\bigg{)}\end{split}$ (2)

and

$\begin{split}M_{n}^{3}(d_{k+1})=\bigg{(}\bigcup\limits_{h\in
D_{g_{k+1}}^{1}}G_{n}^{3}(hd_{k+1})\bigg{)}\cup\bigg{(}\bigcup\limits_{h\in
D_{g_{k+1}}^{3}}G_{n}^{1}(hd_{k+1})\bigg{)}.\end{split}$ (3)

Note that $hd_{k+1}$ is also a divisor of $\frac{n}{4}$. If $h>1$ then
$hd_{k+1}=d_{j}$ for some $j<k+1$, and so by induction hypothesis

$\sum\limits_{q\in G_{n}^{1}(hd_{k+1})}ix^{q}-\sum\limits_{q\in
G_{n}^{3}(hd_{k+1})}ix^{q}\in\mathbb{Z}.$

Note that the unions in (2) and (3) are disjoint unions. We have

$\begin{split}\sum\limits_{q\in M_{n}^{1}(d_{k+1})}ix^{q}-\sum\limits_{q\in
M_{n}^{3}(d_{k+1})}ix^{q}~{}~{}=&\bigg{(}\sum\limits_{q\in
G_{n}^{1}(d_{k+1})}ix^{q}-\sum\limits_{q\in
G_{n}^{3}(d_{k+1})}ix^{q}\bigg{)}\\\ &+\sum\limits_{h\in
D_{g_{k+1}}^{1},h>1}\bigg{(}\sum\limits_{q\in
G_{n}^{1}(hd_{k+1})}ix^{q}-\sum\limits_{q\in
G_{n}^{3}(hd_{k+1})}ix^{q}\bigg{)}\\\ &+\sum\limits_{h\in
D_{g_{k+1}}^{3},h>1}\bigg{(}\sum\limits_{q\in
G_{n}^{3}(hd_{k+1})}ix^{q}-\sum\limits_{q\in
G_{n}^{1}(hd_{k+1})}ix^{q}\bigg{)}.\end{split}$

Hence

$\displaystyle\sum\limits_{q\in G_{n}^{1}(d_{k+1})}ix^{q}-\sum\limits_{q\in
G_{n}^{3}(d_{k+1})}ix^{q}~{}~{}=$ $\displaystyle\bigg{(}\sum\limits_{q\in
M_{n}^{1}(d_{k+1})}ix^{q}-\sum\limits_{q\in M_{n}^{3}(d_{k+1})}ix^{q}\bigg{)}$
$\displaystyle-\sum\limits_{h\in D_{g_{k+1}}^{1},h>1}\bigg{(}\sum\limits_{q\in
G_{n}^{1}(hd_{k+1})}ix^{q}-\sum\limits_{q\in
G_{n}^{3}(hd_{k+1})}ix^{q}\bigg{)}$ $\displaystyle-\sum\limits_{h\in
D_{g_{k+1}}^{3},h>1}\bigg{(}\sum\limits_{q\in
G_{n}^{3}(hd_{k+1})}ix^{q}-\sum\limits_{q\in
G_{n}^{1}(hd_{k+1})}ix^{q}\bigg{)}.$ (4)

Observe that the first summand in the right of (3) is an integer by Lemma 3.3,
and the other two summands are also integers by induction hypothesis. Hence
$\sum\limits_{q\in G_{n}^{1}(d_{k+1})}ix^{q}-\sum\limits_{q\in
G_{n}^{3}(d_{k+1})}ix^{q}\in\mathbb{Z}$. Thus the proof follows by induction.
∎

Now using Corollary 2.1.2 and Theorem 3.5, we get a sufficient condition on
the symbol set $\mathcal{C}$ for which the oriented circulant graph
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is integral.

######  Corollary 3.5.1.

Let $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ be an oriented circulant graph
on $n\equiv 0\ (\mathrm{mod}\ 4)$ vertices. Let
$\mathcal{C}=\bigcup\limits_{d\in\mathscr{D}}S_{n}(d)$, where
$\mathscr{D}\subseteq\\{d:d\mid\frac{n}{4}\\}$ and $S_{n}(d)=G_{n}^{1}(d)$ or
$S_{n}(d)=G_{n}^{3}(d)$. Then $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is
integral.

Using Theorem 2.4 and Corollary 3.5.1, we get a sufficient condition on the
symbol set $\mathcal{C}$ for which the mixed circulant graph
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is integral.

######  Corollary 3.5.2.

Let $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ be a mixed circulant graph on
$n\equiv 0\ (\mathrm{mod}\ 4)$ vertices. Let
$\mathcal{C}\setminus\overline{\mathcal{C}}=\bigcup\limits_{d\in\mathscr{D}_{1}}G_{n}(d)$
and $\overline{\mathcal{C}}=\bigcup\limits_{d\in\mathscr{D}_{2}}S_{n}(d)$,
where $\mathscr{D}_{1}\subseteq\\{d:d\mid n\\}$,
$\mathscr{D}_{2}\subseteq\\{d:d\mid\frac{n}{4}\\}$,
$\mathscr{D}_{1}\cap\mathscr{D}_{2}=\emptyset$, and $S_{n}(d)=G_{n}^{1}(d)$ or
$S_{n}(d)=G_{n}^{3}(d)$. Then $\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is
integral.

##  4 Irreducible factors of cyclotomic polynomial over $\mathbb{Q}(i)$

The cyclotomic polynomial $\Phi_{n}(x)$ is the monic polynomial whose zeros
are the primitive $n^{th}$ roots of unity. That is

$\Phi_{n}(x)=\prod_{a\in G_{n}(1)}(x-w_{n}^{a}),$

where $w_{n}=\exp(\frac{2\pi i}{n})$. Clearly the degree of $\Phi_{n}(x)$ is
$\varphi(n)$. See [19] for more details on cyclotomic polynomial.

######  Lemma 4.1.

[19] $x^{n}-1=\prod\limits_{d\mid n}\Phi_{d}(x)$ and
$\Phi_{n}(x)\in\mathbb{Z}[x]$.

######  Theorem 4.2.

[19] The cyclotomic polynomial $\Phi_{n}(x)$ is irreducible in
$\mathbb{Z}[x]$.

The polynomial $\Phi_{n}(x)$ is irreducible over $\mathbb{Q}(i)$ if and only
if $[\mathbb{Q}(i,w_{n}):\mathbb{Q}(i)]=\varphi(n)$. Also $\mathbb{Q}(w_{n})$
does not contain the number $i=\sqrt{-1}$ if and only if $n\not\equiv 0\
(\mathrm{mod}\ 4)$. Thus, if $n\not\equiv 0\ (\mathrm{mod}\ 4)$ then
$[\mathbb{Q}(i,w_{n}):\mathbb{Q}(w_{n})]=2=[\mathbb{Q}(i),\mathbb{Q}]$, and
therefore

$[\mathbb{Q}(i,w_{n}):\mathbb{Q}(i)]=\frac{[\mathbb{Q}(i,w_{n}):\mathbb{Q}(w_{n})]\times[\mathbb{Q}(w_{n}):\mathbb{Q}]}{[\mathbb{Q}(i):\mathbb{Q}]}=[\mathbb{Q}(w_{n}):\mathbb{Q}]=\varphi(n).$

Hence for $n\not\equiv 0\ (\mathrm{mod}\ 4)$, the polynomial $\Phi_{n}(x)$ is
irreducible over $\mathbb{Q}(i)$.

Let $n\equiv 0\ (\mathrm{mod}\ 4)$. Then
$\mathbb{Q}(i,w_{n})=\mathbb{Q}(w_{n})$, and so

$[\mathbb{Q}(i,w_{n}):\mathbb{Q}(i)]=\frac{[\mathbb{Q}(i,w_{n}):\mathbb{Q}]}{[\mathbb{Q}(i):\mathbb{Q}]}=\frac{\varphi(n)}{2}.$

Hence the polynomial $\Phi_{n}(x)$ is not irreducible over $\mathbb{Q}(i)$.

For $n\equiv 0\ (\mathrm{mod}\ 4)$, we factorize $\Phi_{n}(x)$ into two
irreducible monic polynomials over $\mathbb{Q}(i)$. From Lemma 3.4, we know
that $G_{n}(1)$ is a disjoint union of $G_{n}^{1}(1)$ and $G_{n}^{3}(1)$.
Define

$\Phi_{n}^{1}(x)=\prod_{a\in G_{n}^{1}(1)}(x-w_{n}^{a})\textnormal{ and
}\Phi_{n}^{3}(x)=\prod_{a\in G_{n}^{3}(1)}(x-w_{n}^{a}).$

It is clear from the definition that
$\Phi_{n}(x)=\Phi_{n}^{1}(x)\Phi_{n}^{3}(x)$.

######  Lemma 4.3.

If $n\equiv 0\ (\mathrm{mod}\ 4)$, then the following are true:

  1. (i)

$x^{\frac{n}{4}}-i=\prod_{d\in D_{n}^{1}}\Phi_{n/d}^{1}(x)\prod_{d\in
D_{n}^{3}}\Phi_{n/d}^{3}(x),$

  2. (ii)

$x^{\frac{n}{4}}+i=\prod_{d\in D_{n}^{1}}\Phi_{n/d}^{3}(x)\prod_{d\in
D_{n}^{3}}\Phi_{n/d}^{1}(x).$

###### Proof.

  1. (i)

Note that $|M_{n}^{1}(1)|=\frac{n}{4}$ and $w_{n}^{a}$ is a root of
$x^{\frac{n}{4}}-i$ for all $a\in M_{n}^{1}(1)$. Therefore

$\begin{split}x^{\frac{n}{4}}-i&=\prod_{a\in M_{n}^{1}(1)}(x-w_{n}^{a})\\\
&=\prod_{h\in D_{n}^{1}}\prod_{a\in G_{n}^{1}(h)}(x-w_{n}^{a})\prod_{h\in
D_{n}^{3}}\prod_{a\in G_{n}^{3}(h)}(x-w_{n}^{a}),\hskip
28.45274pt(\textnormal{ using Lemma }\ref{iocg4})\\\ &=\prod_{h\in
D_{n}^{1}}\prod_{a\in hG_{n/h}^{1}(1)}(x-w_{n}^{a})\prod_{h\in
D_{n}^{3}}\prod_{a\in hG_{n/h}^{3}(1)}(x-w_{n}^{a})\\\ &=\prod_{h\in
D_{n}^{1}}\prod_{a\in G_{n/h}^{1}(1)}(x-(w_{n}^{h})^{a})\prod_{h\in
D_{n}^{3}}\prod_{a\in G_{n/h}^{3}(1)}(x-(w_{n}^{h})^{a})\\\ &=\prod_{h\in
D_{n}^{1}}\Phi_{n/h}^{1}(x)\prod_{h\in
D_{n}^{3}}\Phi_{n/h}^{3}(x).\end{split}$

In the last line, we use the fact that $w_{n}^{h}=\exp(\frac{2\pi i}{n/h})$ is
a primitive $\frac{n}{h}$-th root of unity.

  2. (ii)

Note that $|M_{n}^{3}(1)|=\frac{n}{4}$ and $w_{n}^{a}$ is a root of
$x^{\frac{n}{4}}+i$ for all $a\in M_{n}^{3}(1)$. Now proceed as in Part $(i)$
to get the proof of this part.

∎

######  Corollary 4.3.1.

Let $n\equiv 0\ (\mathrm{mod}\ 4)$. The factors $\Phi_{n}^{1}(x)$ and
$\Phi_{n}^{3}(x)$ of $\Phi_{n}(x)$ are monic polynomials in $\mathbb{Z}(i)[x]$
of degree $\varphi(n)/2$.

###### Proof.

By definition, $\Phi_{n}^{1}(x)$ and $\Phi_{n}^{3}(x)$ are monic. Also,
$G_{n}(1)=G_{n}^{1}(1)\cup G_{n}^{3}(1)$ is a disjoint union and that
$|G_{n}^{1}(1)|=|G_{n}^{3}(1)|$. Therefore the degree of $\Phi_{n}^{1}(x)$ and
$\Phi_{n}^{3}(x)$ is $\varphi(n)/2$. Now we proceed by induction on $n$ to
show that $\Phi_{n}^{1}(x),\Phi_{n}^{3}(x)\in\mathbb{Z}(i)[x]$. For $n=4$, the
polynomials $\Phi_{4}^{1}(x)=x-i$ and $\Phi_{4}^{3}(x)=x+i$ are clearly in
$\mathbb{Z}(i)[x]$. Assume that $\Phi_{k}^{1}(x)$ and $\Phi_{k}^{3}(x)$ are in
$\mathbb{Z}(i)[x]$ for $k<n$ and $k\equiv 0\ (\mathrm{mod}\ 4)$. By Lemma 4.3,
$\Phi_{n}^{1}(x)=\frac{x^{\frac{n}{4}}-i}{f(x)}$ and
$\Phi_{n}^{3}(x)=\frac{x^{\frac{n}{4}}+i}{g(x)}$, where $f(x)$ and $g(x)$ are
monic polynomials. By induction hypothesis $f(x),g(x)\in\mathbb{Z}(i)[x]$. It
now follows by “long division” that $\Phi_{n}^{1}(x)\in\mathbb{Z}(i)[x]$ and
$\Phi_{n}^{3}(x)\in\mathbb{Z}(i)[x]$. Hence the proof is complete by induction
∎

######  Corollary 4.3.2.

Let $n\equiv 0\ (\mathrm{mod}\ 4)$. Then

$\frac{n}{2}=\sum\limits_{d\in D_{n}}\varphi\left(\frac{n}{d}\right).$

###### Proof.

We get the desired equality by comparing the degree of the polynomials in
Lemma 4.3. ∎

######  Corollary 4.3.3.

Let $n$ be an positive even integer. Then

$\frac{n}{2}=\sum\limits_{d\in D_{n}}\varphi\left(\frac{n}{d}\right).$

###### Proof.

Since $2n\equiv 0\ (\mathrm{mod}\ 4)$ and $\frac{2n}{d}\equiv 0\
(\mathrm{mod}\ 4)$ for all $d\in D_{n}$, so
$\varphi(\frac{2n}{d})=2\varphi(\frac{n}{d})$ for $d\in D_{n}=D_{2n}$. Thus by
Corollary 4.3.2, $\frac{2n}{2}=\sum\limits_{d\in
D_{2n}}\varphi(\frac{2n}{d})=\sum\limits_{d\in D_{n}}2\varphi(\frac{n}{d}).$ ∎

######  Corollary 4.3.4.

Let $n=2^{k}$ for $k\geq 2$. Then
$\Phi_{n}^{1}(x)=x^{\frac{n}{4}}+i\textnormal{ and
}\Phi_{n}^{3}(x)=x^{\frac{n}{4}}-i.$

######  Theorem 4.4.

Let $n\equiv 0\ (\mathrm{mod}\ 4)$. The factors $\Phi_{n}^{1}(x)$ and
$\Phi_{n}^{3}(x)$ of $\Phi_{n}(x)$ are irreducible monic polynomials in
$\mathbb{Q}(i)[x]$ of degree $\frac{\varphi(n)}{2}$.

###### Proof.

In view of Corollary 4.3.1, we only need to show that $\Phi_{n}^{1}(x)$ and
$\Phi_{n}^{3}(x)$ are irreducible in $\mathbb{Q}(i)$. For $n\equiv 0\
(\mathrm{mod}\ 4)$, we have
$[\mathbb{Q}(i,w_{n}):\mathbb{Q}(i)]=\frac{\varphi(n)}{2}$. So there is a
unique irreducible monic polynomial $p(x)\in\mathbb{Q}(i)[x]$ of degree
$\frac{\varphi(n)}{2}$ having $w_{n}$ as a root. Since $w_{n}$ is also a root
of $\Phi_{n}^{1}(x)$, so $\Phi_{n}^{1}(x)=p(x)f(x)$, where
$f(x)\in\mathbb{Q}(i)[x]$. As $\Phi_{n}^{1}(x)$ is a monic polynomial of
degree $\varphi(n)/2$, so $f(x)=1$. Hence $\Phi_{n}^{1}(x)=p(x)$, that is,
$\Phi_{n}^{1}(x)$ is irreducible. Similarly, for $a\in G_{n}^{3}(1)$, we have
$[\mathbb{Q}(i,w_{n}^{a}):\mathbb{Q}(i)]=\frac{\varphi(n)}{2}$. This, along
with Corollary 4.3.1, gives that $\Phi_{n}^{3}(x)$ is irreducible. ∎

##  5 Characterization of mixed circulant graphs

For a fixed $n\equiv 0\ (\mathrm{mod}\ 4)$ and $n\geq 4$, let
$d\mid\frac{n}{4}$. Define $u(d)$ to be the $(n-1)$-vector, where

$u(d)_{k}=\left\\{\begin{array}[]{rl}1&\mbox{if }k\in G_{n}^{1}(d)\\\
-1&\mbox{if }k\in G_{n}^{3}(d)\\\ 0&\mbox{otherwise}.\end{array}\right.$

Let $E=[e_{st}]$ be an $(n-1)\times(n-1)$ matrix defined by

$e_{st}=iw_{n}^{st}.$

Note that $E$ is invertible. Using Theorem 3.5, we get
$Eu(d)\in\mathbb{Z}^{n-1}$. Define
$\mathbb{U}=\\{u\in\mathbb{Q}^{n-1}:Eu\in\mathbb{Q}^{n-1}\\}$ so that
$u(d)\in\mathbb{U}$. Let span${}_{\mathbb{Q}}\\{u(d):d\mid\frac{n}{4}\\}$ be
the set of all linear combinations of $\\{u(d):d\mid\frac{n}{4}\\}$ over
$\mathbb{Q}$. Therefore span${}_{\mathbb{Q}}\\{u(d):d\mid\frac{n}{4}\\}$ is a
subspace of $\mathbb{U}$ over $\mathbb{Q}$. Let
$E(\mathbb{U})=\\{Eu:u\in\mathbb{U}\\}$. Now we propose the following lemma.

######  Lemma 5.1.

Let $n\equiv 0\ (\mathrm{mod}\ 4)$. Then $E(\mathbb{U})\subseteq$
span${}_{\mathbb{Q}}\\{u(d):d\mid\frac{n}{4}\\}$.

###### Proof.

Let $u=[u_{1},u_{2},...,u_{n-1}]^{t}\in U$ and
$v=Eu=[v_{1},v_{2},...,v_{n-1}]^{t}$. Since $G_{n}(d_{1})\cap
G_{n}(d_{2})=\emptyset$ for $d_{1}\neq d_{2}$ and $\bigcup\limits_{d\mid
n}G_{n}(d)=\\{1,2,...,n-1\\}$, it is enough to show the following:

  1. (i)

$v_{s}=-v_{n-s}$ for all $1\leq s\leq n-1$,

  2. (ii)

If $d\mid\frac{n}{4}$ then $v_{s}=v_{t}$ for all $s,t\in G_{n}^{1}(d)$, and

  3. (iii)

If $d\nmid\frac{n}{4},d\mid n$ and $d<n$ then $v_{r}=0$ for all $r\in
G_{n}(d)$.

Since $Eu=[v_{1},v_{2},...,v_{n-1}]^{t}$ for $1\leq s\leq n-1$, we get

$v_{n-s}=\sum\limits_{j=1}^{n-1}iu_{j}w_{n}^{(n-s)j}=\sum\limits_{j=1}^{n-1}iu_{j}w_{n}^{-sj}=\overline{\sum\limits_{j=1}^{n-1}(-i)u_{j}w_{n}^{sj}}=-\overline{v_{s}}=-v_{s}.$

Assume that $d\mid\frac{n}{4}$ and $s,t\in G_{n}^{1}(d)$, so that
$\frac{s}{d},\frac{t}{d}\in G_{\frac{n}{d}}^{1}(1)$ and $w_{n}^{s}$,
$w_{n}^{t}$ are roots of $\Phi_{\frac{n}{d}}^{1}(x)$. Again,
$v_{s}=\sum\limits_{j=1}^{n-1}iu_{j}w_{n}^{sj}\in\mathbb{Q}$, and so
$w_{n}^{s}$ is a root of the polynomial
$p(x)=\sum\limits_{j=1}^{n-1}iu_{j}x^{j}-v_{s}\in\mathbb{Q}(i)[x]$. Therefore
$p(x)$ is a multiple of the irreducible monic polynomial
$\Phi_{\frac{n}{d}}^{1}(x)$, and so $w_{n}^{t}$ is also a root of $p(x)$,
_i.e._ , $v_{s}=\sum\limits_{j=1}^{n-1}iu_{j}w_{n}^{tj}=v_{t}$. Hence
$v_{s}=v_{t}$.

Now assume that $d\nmid\frac{n}{4},d\mid n$, $d<n$ and $r\in G_{n}(d)$. Then
$r,n-r\in G_{n}(d)$ and $w_{n}^{r}$, $w_{n}^{n-r}$ are roots of
$\Phi_{\frac{n}{d}}(x)$. Again
$v_{r}=\sum\limits_{j=1}^{n-1}iu_{j}w_{n}^{rj}\in\mathbb{Q}$, and hence
$w_{n}^{r}$ is a root of the polynomial in
$q(x)=\sum\limits_{j=1}^{n-1}iu_{j}x^{j}-v_{r}\in\mathbb{Q}(i)[x]$. Therefore
$q(x)$ is a multiple of the irreducible monic polynomial
$\Phi_{\frac{n}{d}}(x)$. Note that $\Phi_{\frac{n}{d}}(x)$ is irreducible over
$\mathbb{Q}(i)$ as $n\not\equiv 0\ (\mathrm{mod}\ 4)$. Thus $w_{n}^{n-r}$ is
also a root of $q(x)$, _i.e._ ,
$v_{r}=\sum\limits_{j=1}^{n-1}iu_{j}w_{n}^{(n-r)j}=v_{n-r}$. This gives
$v_{r}=v_{n-r}$. Now $v_{r}=v_{n-r}$ and $v_{r}=-v_{n-r}$ altogether give
$v_{r}=v_{n-r}=0$. ∎

The next theorem is crucial in proving the necessity of the sufficient
condition of Corollary 3.5.1.

######  Theorem 5.2.

Let $n\equiv 0\ (\mathrm{mod}\ 4)$. Then $\mathbb{U}=$
span${}_{\mathbb{Q}}\\{u(d):d\mid\frac{n}{4}\\}$.

###### Proof.

By Lemma 5.1, $E(\mathbb{U})\subseteq$
span${}_{\mathbb{Q}}\\{u(d):d\mid\frac{n}{4}\\}\subseteq\mathbb{U}$. Since $E$
is invertible, we get $\dim E(\mathbb{U})=\dim\mathbb{U}$, and hence
$E(\mathbb{U})=$ span${}_{\mathbb{Q}}\\{u(d):d\mid\frac{n}{4}\\}=\mathbb{U}$.
∎

######  Theorem 5.3.

Let $G=\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ be an oriented circulant
graph.

  1. (i)

If $n\not\equiv 0\ (\mathrm{mod}\ 4)$ then $G$ is integral if and only if
$\mathcal{C}=\emptyset$.

  2. (ii)

If $n\equiv 0\ (\mathrm{mod}\ 4)$ then $G$ is integral if and only if
$\mathcal{C}=\bigcup\limits_{d\in\mathscr{D}}S_{n}(d)$, where
$\mathscr{D}\subseteq\\{d:d\mid\frac{n}{4}\\}$ and $S_{n}(d)=G_{n}^{1}(d)$ or
$S_{n}(d)=G_{n}^{3}(d)$.

###### Proof.

  1. (i)

Assume that $G$ is integral. Let
$Sp_{H}(G)=\\{\mu_{0},\mu_{1},...,\mu_{n-1}\\}$. By Corollary 2.1.2,
$\mu_{j}=-\mu_{n-j}\in\mathbb{Q}$ for all $j=0,...,n-1$, where

$\mu_{j}=i\sum\limits_{k\in{\mathcal{C}}}w_{n}^{jk}-i\sum\limits_{k\in{\mathcal{C}}}w_{n}^{-jk}\textnormal{
for }0\leq j\leq n-1.$

Hence $w_{n}^{j}$ is a root of the polynomial
$p(x)=i\sum\limits_{k\in{\mathcal{C}}}x^{k}-i\sum\limits_{k\in{\mathcal{C}}}x^{-k}-\mu_{j}\in\mathbb{Q}(i)[x]$.
Since $n\not\equiv 0\ (\mathrm{mod}\ 4)$, the polynomial $\Phi_{n}(x)$ is
irreducible in $\mathbb{Q}(i)[x]$. Therefore $p(x)$ is a multiple of the
irreducible polynomial $\Phi_{n}(x)$, and so $w_{n}^{-j}=w_{n}^{n-j}$ is also
a root of $p(x)$, _i.e._ , $\mu_{j}=\mu_{n-j}$. Now $\mu_{j}=\mu_{n-j}$ and
$\mu_{j}=-\mu_{n-j}$ implies that $\mu_{j}=\mu_{n-j}=0$ for all $j=0,...,n-1$.
Hence $\mathcal{C}=\emptyset$. Converse part is easy to prove.

  2. (ii)

We have already proved the sufficient part in Corollary 3.5.1. Assume that $G$
is an integral oriented circulant graph with non-empty symbol set
$\mathcal{C}$. Let $u$ be the vector of length $n-1$ defined by

$u_{k}=\left\\{\begin{array}[]{rl}1&\mbox{if }k\in\mathcal{C}\\\ -1&\mbox{if
}n-k\in\mathcal{C}\\\ 0&\mbox{otherwise}.\end{array}\right.$

Note that each entry of $Eu$ is an eigenvalue of $G$, and so
$Eu\in\mathbb{Z}^{n-1}$. Therefore $u\in\mathbb{U}$, and by Theorem 5.2,
$u\in$ span${}_{\mathbb{Q}}\\{u(d):d\mid\frac{n}{4}\\}$. That is,

$u=\sum\limits_{d\mid\frac{n}{4}}c_{d}u(d),\textnormal{ where
}c_{d}\in\mathbb{Q}\textnormal{ for }d\mid\frac{n}{4}.$

Note that the coordinates of $u$ and $u(d)$ belong to $\\{0,\pm 1\\}$. Since
$G_{n}(d_{1})\cap G_{n}(d_{2})=\emptyset$ for all $d_{1}\neq d_{2}$, so
$u_{k}=c_{d}u(d)_{k}$ for all $k\in G_{n}(d)$. This implies that
$c_{d}\in\\{0,\pm 1\\}$ for all $d\mid\frac{n}{4}$. Let $\mathscr{D}$ be the
set of all $d$ for which $c_{d}\neq 0$ and $d\mid\frac{n}{4}$. Thus
$\mathcal{C}=\bigcup\limits_{d\in\mathscr{D}}S_{n}(d)$, where
$S_{n}(d)=G_{n}^{1}(d)$ or $S_{n}(d)=G_{n}^{3}(d)$.

∎

######  Theorem 5.4.

Let $G=\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ be a mixed circulant graph on
$n$ vertices with symbol set $\mathcal{C}$. Then $G$ is integral if and only
if
$\mathcal{C}\setminus\overline{\mathcal{C}}=\bigcup\limits_{d\in\mathscr{D}_{1}}G_{n}(d)$
and

$\overline{\mathcal{C}}=\left\\{\begin{array}[]{ll}\emptyset&\textnormal{if
}n\not\equiv 0\ (\mathrm{mod}\ 4)\\\
\bigcup\limits_{d\in\mathscr{D}_{2}}S_{n}(d)&\textnormal{if }n\equiv 0\
(\mathrm{mod}\ 4),\end{array}\right.$

where $\mathscr{D}_{1}\subseteq\\{d:d\mid n\\}$,
$\mathscr{D}_{2}\subseteq\\{d:d\mid\frac{n}{4}\\}$,
$\mathscr{D}_{1}\cap\mathscr{D}_{2}=\emptyset$, and $S_{n}(d)=G_{n}^{1}(d)$ or
$S_{n}(d)=G_{n}^{3}(d)$.

###### Proof.

By Theorem 2.5, $G$ is integral if and only if both
$(\mathbb{Z}_{n},\mathcal{C}\setminus\overline{\mathcal{C}})$ and
$(\mathbb{Z}_{n},\overline{\mathcal{C}})$ are integral. Therefore the result
follows from Theorem 2.4 and Theorem 5.3. ∎

Wasin So [28] gave an upper bound on the number of integral circulant graphs
on $n$ vertices.

######  Corollary 5.4.1.

[28] Let $\tau(n)$ be the number of divisors of $n$. Then there are at most
$2^{\tau(n)-1}$ integral circulant graphs on $n$ vertices.

In the next result, we give a similar upper bound on the number of integral
mixed circulant graphs on $n$ vertices.

######  Corollary 5.4.2.

Let $\tau(n)$ be the number of divisors of $n$. Then there are at most $k(n)$
integral mixed circulant graphs on $n$ vertices, where

$k(n)=\left\\{\begin{array}[]{ll}2^{\tau(\frac{n}{4})+\tau(n)-1}&\textnormal{if
}n\equiv 0\ (\mathrm{mod}\ 4)\\\ 2^{\tau(n)-1}&\textnormal{if }n\not\equiv 0\
(\mathrm{mod}\ 4).\end{array}\right.$

###### Proof.

If $n\not\equiv 0\ (\mathrm{mod}\ 4)$ then Theorem 5.4 says that every
integral mixed circulant graph is undirected. By Corollary 5.4.1, there are at
most $2^{\tau(n)-1}$ integral mixed circulant graphs on $n$ vertices. Assume
that $n\equiv 0\ (\mathrm{mod}\ 4)$ and
$\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ is a mixed circulant graph on $n$
vertices with symbol set $\mathcal{C}$. For every divisor $d$ of
$\frac{n}{4}$, by Theorem 5.4, $G_{n}(d)$, $G_{n}^{1}(d)$, $G_{n}^{3}(d)$ and
$\emptyset$ are subsets of the symbol set $\mathcal{C}$. Thus, we have
$4^{\tau{(\frac{n}{4})}}$ distinct symbol sets for an integral mixed circulant
graph corresponding to each divisor of $\frac{n}{4}$. For each proper divisor
$d$ of $n$ which is not a divisor of $\frac{n}{4}$, by Theorem 5.4, $G_{n}(d)$
and $\emptyset$ are subsets of the symbol set $\mathcal{C}$. Thus, we have
$2^{\tau(n)-\tau{(\frac{n}{4})-1}}$ distinct symbol sets for an integral mixed
circulant graph corresponding to proper divisors of $n$ which are not divisors
of $\frac{n}{4}$. Hence we have $4^{\tau{(\frac{n}{4})}}\cdot
2^{\tau(n)-\tau{(\frac{n}{4})-1}}=2^{\tau(\frac{n}{4})+\tau(n)-1}$ distinct
symbol sets for an integral mixed circulant graph. Since distinct symbol sets
may correspond to isomorphic circulant graphs, so there are at most
$2^{\tau(\frac{n}{4})+\tau(n)-1}$ integral mixed circulant graphs on $n$
vertices. ∎

##  6  Ramanujan sum and eigenvalues of oriented circulant graphs

In 1918, Ramanujan [27] published a seminal paper in which he introduced a sum
(now called Ramanujan sum), for each $n,q\in\mathbb{N}$, defined by

$\begin{split}c_{n}(q)=\sum_{a\in G_{n}(1)}\cos\bigg{(}\frac{2\pi
aq}{n}\bigg{)}.\end{split}$ (5)

This sum can also be written as

$c_{n}(q)=\sum_{a\in G_{n}(1)}w_{n}^{aq}=\sum_{\begin{subarray}{c}a\in
G_{n}(1)\\\ a<\frac{n}{2}\end{subarray}}2\cos\bigg{(}\frac{2\pi
aq}{n}\bigg{)},$

where $w_{n}=\exp(\frac{2\pi i}{n})$. A set $\mathcal{C}\subseteq G_{n}(1)$ is
said to be skew-symmetric in $G_{n}(1)$ if $n-a\not\in\mathcal{C}$ for all
$a\in\mathcal{C}$ and $\mathcal{C}\cup\mathcal{C}^{-1}=G_{n}(1)$. It is clear
that a skew-symmetric set in $G_{n}(1)$ contains exactly
$\frac{\varphi(n)}{2}$ elements.

It is easy to see, for any skew-symmetric set $\mathcal{C}$ in $G_{n}(1)$,
that the Ramanujan sum (5) can be re-written as

$\begin{split}c_{n}(q)=\sum_{a\in\mathcal{C}}2\cos\bigg{(}\frac{2\pi
aq}{n}\bigg{)}.\end{split}$ (6)

######  Lemma 6.1.

[26] Let $m\in\mathbb{N}$. Then

$c_{m}(t)=\frac{\mu({\frac{m}{\delta_{t}}}).\varphi(m)}{\varphi(\frac{m}{\delta_{t}})},$

where $\delta_{t}=\gcd(m,t)$.

One of the important properties of Ramanujan sum is that $c_{n}(q)$ is an
integer for all $q,n\in\mathbb{N}$. So, it is a natural question to ask, “if
we replace cosine with sine in Ramanujan sum, then is the sum remain an
integer for all $q,n\in\mathbb{N}$?”. Let us replace the cosine by sine in
(6), and write

$\begin{split}s_{n}^{\mathcal{C}}(q)=\sum_{a\in\mathcal{C}}2\sin\bigg{(}\frac{2\pi
aq}{n}\bigg{)},\end{split}$ (7)

where $\mathcal{C}$ is any skew-symmetric set in $G_{n}(1)$. The sum (7) can
be re-written as

$\begin{split}s_{n}^{\mathcal{C}}(q)=\sum_{a\in\mathcal{C}}\frac{w_{n}^{aq}-w_{n}^{-aq}}{i}.\end{split}$
(8)

######  Theorem 6.2.

The following are true.

  1. (i)

For $n\not\equiv 0\ (\mathrm{mod}\ 4)$, there does not exist skew-symmetric
set $\mathcal{C}$ in $G_{n}(1)$ such that
$s_{n}^{\mathcal{C}}(q)\in\mathbb{Z}$ for all $q,n\in\mathbb{N}$.

  2. (ii)

For $n\equiv 0\ (\mathrm{mod}\ 4)$, $s_{n}^{\mathcal{C}}(q)\in\mathbb{Z}$ for
all $q,n\in\mathbb{N}$ if and only if $\mathcal{C}=G_{n}^{1}(1)$ or
$\mathcal{C}=G_{n}^{3}(1)$.

The proof of Theorem 6.2 follows from Theorem 5.3. In what follows, we
consider $\mathcal{C}=G_{n}^{1}(1)$ for the sums in (7) and (8), and we simply
write $s_{n}^{\mathcal{C}}(q)$ by $s_{n}(q)$. That is,

$\begin{split}s_{n}(q)=\sum_{a\in
G_{n}^{1}(1)}\frac{w_{n}^{aq}-w_{n}^{-aq}}{i}.\end{split}$

In Theorem 6.2, we found that $s_{n}(q)$ is an integer for all
$n,q\in\mathbb{N}$ and $n\equiv 0\ (\mathrm{mod}\ 4)$.

######  Theorem 6.3.

[28] Let $G=\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ be an integral circulant
graph on $n$ vertices with $Sp_{H}(G)=\\{\lambda_{0},...,\lambda_{n-1}\\}$.
Let $\mathcal{C}=G_{n}(d)$, where $d\mid n$. Then

$\lambda_{j}=c_{n/d}(j)\textnormal{ for }0\leq j\leq n-1.$

Further, $Sp_{H}(G)$ is equal to $d$ copies of
$\\{c_{n/d}(0),c_{n/d}(1),...,c_{n/d}((n/d)-1)\\}$.

######  Theorem 6.4.

Let $G=\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ be an integral oriented
circulant graph on $n\equiv 0\ (\mathrm{mod}\ 4)$ vertices with
$Sp_{H}(G)=\\{\mu_{0},...,\mu_{n-1}\\}$. Let $\mathcal{C}=G_{n}^{1}(d)$, where
$d\mid\frac{n}{4}$. Then

$\mu_{j}=-s_{n/d}(j)\textnormal{ for }0\leq j\leq n-1.$

Further, $Sp_{H}(G)$ is equal to $d$ copies of
$\\{-s_{n/d}(0),-s_{n/d}(1),...,-s_{n/d}((n/d)-1)\\}$.

###### Proof.

Using Corollary 2.1.2, we get

$\begin{split}\mu_{j}=i\sum\limits_{k\in{\mathcal{C}}}(w_{n}^{jk}-w_{n}^{-jk})=-\sum_{a\in
G_{n}^{1}(d)}\frac{w_{n}^{aj}-w_{n}^{-aj}}{i}&=-\sum_{a\in
dG_{n}^{1}(1)}\frac{w_{n}^{aj}-w_{n}^{-aj}}{i}\\\ &=-\sum_{a\in
G_{n}^{1}(1)}\frac{(w_{n}^{d})^{aj}-(w_{n}^{d})^{-aj}}{i}\\\
&=-s_{n/d}(j).\end{split}$

Since $s_{n/d}(t_{1})=s_{n/d}(t_{2})$ for $t_{1}\equiv
t_{2}(\mathrm{mod}\hskip 2.84544pt\frac{n}{d})$, the spectrum
$\\{\mu_{1},...,\mu_{n-1}\\}$ is equal to $d$ copies of
$\\{-s_{n/d}(0),-s_{n/d}(1),...,-s_{n/d}((n/d)-1)\\}$. ∎

######  Corollary 6.4.1.

Let $G=\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ be an integral oriented
circulant graph on $n\equiv 0\ (\mathrm{mod}\ 4)$ vertices with
$Sp_{H}(G)=\\{\mu_{0},...,\mu_{n-1}\\}$. Then

$\mu_{j}=\sum_{d\in\mathscr{D}}\pm s_{n/d}(j)\textnormal{ for }0\leq j\leq
n-1,\textnormal{ where
}\mathscr{D}\subseteq\left\\{d:d\mid\frac{n}{4}\right\\}.$

###### Proof.

By Theorem 5.3, $\mathcal{C}=\bigcup\limits_{d\in\mathscr{D}}S_{n}(d)$, where
$\mathscr{D}\subseteq\\{d:d\mid\frac{n}{4}\\}$ and $S_{n}(d)=G_{n}^{1}(d)$ or
$S_{n}(d)=G_{n}^{3}(d)$. Using Corollary 2.1.2, we get

$\begin{split}\mu_{j}&=i\sum\limits_{k\in{\mathcal{C}}}(w_{n}^{jk}-w_{n}^{-jk})=\sum_{d\in\mathscr{D}}\sum_{a\in
S_{n}(d)}-\frac{w_{n}^{aj}-w_{n}^{-aj}}{i}=\sum_{d\in\mathscr{D}}\pm
s_{n/d}(j).\\\ \end{split}$

∎

######  Corollary 6.4.2.

Let $G=\text{Circ}(\mathbb{Z}_{n},\mathcal{C})$ be an integral mixed circulant
graph on $n$ vertices with $Sp_{H}(G)=\\{\gamma_{0},...,\gamma_{n-1}\\}$. Then

$\gamma_{j}=\sum_{d\in\mathscr{D}_{1}}c_{n/d}(j)+\sum_{d\in\mathscr{D}_{2}}\pm
s_{n/d}(j)\textnormal{ for }0\leq j\leq n-1,$

where $\mathscr{D}_{1}\subseteq\\{d:d\mid n\\}$,
$\mathscr{D}_{2}\subseteq\\{d:d\mid\frac{n}{4}\\}$ and
$\mathscr{D}_{1}\cap\mathscr{D}_{2}=\emptyset$.

###### Proof.

By Theorem 5.4,
$\mathcal{C}\setminus\overline{\mathcal{C}}=\bigcup\limits_{d\in\mathscr{D}_{1}}G_{n}(d)$
and

$\overline{\mathcal{C}}=\left\\{\begin{array}[]{lll}\emptyset&\mbox{if}&n\not\equiv
0\ (\mathrm{mod}\ 4)\\\
\bigcup\limits_{d\in\mathscr{D}_{2}}S_{n}(d)&\mbox{if}&n\equiv 0\
(\mathrm{mod}\ 4),\end{array}\right.$

where $\mathscr{D}_{1}\subseteq\\{d:d\mid n\\}$,
$\mathscr{D}_{2}\subseteq\\{d:d\mid\frac{n}{4}\\}$,
$\mathscr{D}_{1}\cap\mathscr{D}_{2}=\emptyset$ and, $S_{n}(d)=G_{n}^{1}(d)$ or
$S_{n}(d)=G_{n}^{3}(d)$. Using Lemma 2.1, we get

$\begin{split}\gamma_{j}&=\sum_{d\in\mathscr{D}_{1}}\sum_{a\in
G_{n}(d)}w_{n}^{aj}+\sum_{d\in\mathscr{D}_{2}}\sum_{a\in
S_{n}(d)}-\frac{w_{n}^{aj}-w_{n}^{-aj}}{i}=\sum_{d\in\mathscr{D}_{1}}c_{n/d}(j)+\sum_{d\in\mathscr{D}_{2}}\pm
s_{n/d}(j).\end{split}$

∎

From Theorem 6.4, it is clear that $s_{n}(q)$ plays an important role in the
eigenvalues of integral mixed circulant graph. In the next result we see some
basic properties of $s_{n}(q)$.

######  Theorem 6.5.

The following are some basic properties of $s_{n}(q)$.

  1. (i)

$s_{n}(t_{1})=s_{n}(t_{2})$ for $t_{1}\equiv t_{2}\ (\mathrm{mod}\ n)$.

  2. (ii)

$s_{n}(n-t)=-s_{n}(t)$.

  3. (iii)

$s_{n}(0)=s_{n}(\frac{n}{2})=0$.

  4. (iv)

$s_{n}(\frac{n}{4})=\varphi(n)$.

  5. (v)

$s_{n}(\frac{3n}{4})=-\varphi(n)$.

######  Lemma 6.6.

Let $n=2^{t}m$ with $m$ odd. Then the following statements are true.

  1. (i)

If $t\geq 2$ then

$G_{n}^{1}(1)=\left\\{\begin{array}[]{ll}3m+2G_{\frac{n}{2}}(1)&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 4)\\\ m+2G_{\frac{n}{2}}(1)&\mbox{if }m\equiv 3\
(\mathrm{mod}\ 4).\end{array}\right.$

  2. (ii)

If $t\geq 2$ then

$G_{n}^{3}(1)=\left\\{\begin{array}[]{ll}m+2G_{\frac{n}{2}}(1)&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 4)\\\ 3m+2G_{\frac{n}{2}}(1)&\mbox{if }m\equiv 3\
(\mathrm{mod}\ 4).\end{array}\right.$

  3. (iii)

If $t\geq 2$ then
$G_{n}(1)=\left(m+2G_{\frac{n}{2}}(1)\right)\cup\left(3m+2G_{\frac{n}{2}}(1)\right)$.

###### Proof.

  1. (i)

Assume that $t\geq 2$ and $m\equiv 1\ (\mathrm{mod}\ 4)$. Let $3m+2r\in
3m+2G_{\frac{n}{2}}(1)$ for some $r\in G_{\frac{n}{2}}(1)$. Then
$\gcd(r,\frac{n}{2})=1$, and it implies that $\gcd(3m+2r,n)=1$ and
$3m+2r\equiv 1\ (\mathrm{mod}\ 4)$. Thus $3m+2r\in G_{n}^{1}(1)$. Since the
size of $G_{n}^{1}(1)$ and $3m+2G_{\frac{n}{2}}(1)$ are same,
$G_{n}^{1}(1)=3m+2G_{\frac{n}{2}}(1)$. Similarly, if $m\equiv 3\
(\mathrm{mod}\ 4)$ then $G_{n}^{1}(1)=m+2G_{\frac{n}{2}}(1)$.

  2. (ii)

The proof is similar to the proof of Part $(i)$.

  3. (iii)

Use Part $(i)$ and Part $(ii)$ in $G_{n}(1)=G_{n}^{1}(1)\cup G_{n}^{3}(1)$.

∎

######  Proposition 6.7.

Let $n=2^{t}m$ with $m$ odd and $t\geq 2$. Then

$s_{n}(q)=\left\\{\begin{array}[]{ll}2\sin\frac{3\pi
q}{2^{t-1}}c_{\frac{n}{2}}(q)&\mbox{if }m\equiv 1\ (\mathrm{mod}\ 4)\\\
2\sin\frac{\pi q}{2^{t-1}}c_{\frac{n}{2}}(q)&\mbox{if }m\equiv 3\
(\mathrm{mod}\ 4).\end{array}\right.$

###### Proof.

Let $\Im(z)$ denote the imaginary part of a complex number $z$. We have

$\begin{split}s_{n}(q)&=\sum_{a\in
G_{n}^{1}(1)}\frac{w_{n}^{aq}-w_{n}^{-aq}}{i}\\\
&=\left\\{\begin{array}[]{ll}(-i)\sum\limits_{a\in
G_{\frac{n}{2}}^{1}(1)}(w_{n}^{(3m+2a)q}-w_{n}^{-(3m+2a)q})&\mbox{if }m\equiv
1\ (\mathrm{mod}\ 4)\\\ (-i)\sum\limits_{a\in
G_{\frac{n}{2}}^{1}(1)}(w_{n}^{(m+2a)q}-w_{n}^{-(m+2a)q})&\mbox{if }m\equiv 3\
(\mathrm{mod}\ 4)\end{array}\right.\\\
&=\left\\{\begin{array}[]{ll}2\Im(\omega_{n}^{3mq})\sum\limits_{a\in
G_{\frac{n}{2}}^{1}(1)}w_{n}^{2aq}&\mbox{if }m\equiv 1\ (\mathrm{mod}\ 4)\\\
2\Im(\omega_{n}^{mq})\sum\limits_{a\in
G_{\frac{n}{2}}^{1}(1)}w_{n}^{2aq}&\mbox{if }m\equiv 3\ (\mathrm{mod}\
4)\end{array}\right.\\\
&=\left\\{\begin{array}[]{ll}2\Im(\omega_{n}^{3mq})c_{\frac{n}{2}}(q)&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 4)\\\
2\Im(\omega_{n}^{mq})c_{\frac{n}{2}}(q)&\mbox{if }m\equiv 3\ (\mathrm{mod}\
4)\end{array}\right.\\\
&=\left\\{\begin{array}[]{ll}2\Im(\omega_{2^{t}}^{3q})c_{\frac{n}{2}}(q)&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 4)\\\
2\Im(\omega_{2^{t}}^{q})c_{\frac{n}{2}}(q)&\mbox{if }m\equiv 3\ (\mathrm{mod}\
4)\end{array}\right.\\\ &=\left\\{\begin{array}[]{ll}2\sin\frac{3\pi
q}{2^{t-1}}c_{\frac{n}{2}}(q)&\mbox{if }m\equiv 1\ (\mathrm{mod}\ 4)\\\
2\sin\frac{\pi q}{2^{t-1}}c_{\frac{n}{2}}(q)&\mbox{if }m\equiv 3\
(\mathrm{mod}\ 4).\end{array}\right.\\\ \end{split}$

Here the second equality follows from Part $(i)$ of Lemma 6.6. ∎

######  Proposition 6.8.

Let $n=2^{k}$ and $k\geq 2$. Then

$s_{n}(t)=\left\\{\begin{array}[]{cl}2^{k-1}&\textnormal{ if $t\equiv 2^{k-2}\
(\mathrm{mod}\ n)$ }\\\ -2^{k-1}&\textnormal{ if $t\equiv 3\cdot 2^{k-2}\
(\mathrm{mod}\ n)$ }\\\ 0&\textnormal{ otherwise.}\end{array}\right.$

###### Proof.

Since $n=2^{k}$ implies that $G_{n}^{1}(1)=M_{n}^{1}(1)$, we have

$\begin{split}s_{n}(t)&=\sum_{a\in
M_{n}^{1}(1)}\frac{w_{n}^{at}-w_{n}^{-at}}{i}\\\
&=\frac{1}{i}(w_{n}^{t}-w_{n}^{3t}+w_{n}^{5t}-\ldots-
w_{n}^{(n-1)t}).\end{split}$

As $s_{n}(t)$ is a sum of a geometric progression with common ratio
$-w_{n}^{2t}$, the required result follows. ∎

The classical M$\ddot{\text{o}}$bius function $\mu(n)$ is defined by

$\mu(n)=\left\\{\begin{array}[]{cl}1&\mbox{if }n=1\\\ (-1)^{k}&\mbox{if
}n\textnormal{ is a product of $k$ distinct primes}\\\
0&\mbox{otherwise.}\end{array}\right.$

Let $\delta$ be the indicator function defined by

$\delta(n)=\left\\{\begin{array}[]{lll}1&\mbox{if}&n=1\\\
0&\mbox{if}&n>1.\end{array}\right.$

######  Theorem 6.9.

[26]

$\sum_{d\mid n}\mu(d)=\delta(n).$

E. Cohen [14] introduced a generalized M$\ddot{\text{o}}$bius inversion
formula of arbitrary direct factor sets. Let $P$ and $Q$ be two non-empty
subsets of $\mathbb{N}$ such that if
$n_{1},n_{2}\in\mathbb{N},~{}\gcd(n_{1},n_{2})=1$, then $n=n_{1}n_{2}\in P$
(resp. $n=n_{1}n_{2}\in Q$) if and only if $n_{1},n_{2}\in P$ (resp.
$n_{1},n_{2}\in Q$). If each integer $n\in\mathbb{N}$ possesses a unique
factorization of the form $n=ab$ $(a\in P,b\in Q)$, then the sets $P$ and $Q$
are called direct factor sets of $\mathbb{N}$. In what follows, $P$ will
denote such a direct factor set with (conjugate) factor set $Q$. The
M$\ddot{\text{o}}$bius function can be generalized to an arbitrary direct
factor set $P$ by writing

$\mu_{P}(n)=\sum_{d\mid n,d\in P}\mu\left(\frac{n}{d}\right),$

where $\mu$ is the classical M$\ddot{\text{o}}$bius function. For example,
$\mu_{1}(n)=\mu_{\\{1\\}}(n)$ and $\mu_{\mathbb{N}}(n)=\delta(n)$.

######  Theorem 6.10.

[14]

$\sum_{d\mid n,d\in Q}\mu_{P}\left(\frac{n}{d}\right)=\delta(n).$

######  Theorem 6.11.

[14] If $f(n)$ and $g(n)$ are arithmetic functions then

$f(n)=\sum_{d\mid n,d\in Q}g\left(\frac{n}{d}\right)\textnormal{ if and only
if }g(n)=\sum_{d\mid n}f(d)\mu_{P}\left(\frac{n}{d}\right).$

Let $P=\\{2^{k}:k\geq 0\\}$, and $Q$ the set of all odd natural numbers. It is
clear that $P$ and $Q$ are direct factor sets. The following lemma is easy to
prove.

######  Lemma 6.12.

Let $P=\\{2^{k}:k\geq 0\\}$. Then

$\mu_{P}(n)=\left\\{\begin{array}[]{lll}0&\mbox{if $n$ is even}\\\
\mu(n)&\mbox{if $n$ is odd.}\end{array}\right.$

######  Theorem 6.13.

Let $n\equiv 0\mod 4$ and $D_{n}^{3}=\emptyset$. Then

$s_{n}(t)=2\delta_{t}\mu_{P}(n_{t})\sum_{\begin{subarray}{c}e\mid\delta_{t}\\\
\frac{te}{\delta_{t}}\textnormal{ is odd}\\\
\gcd(n_{t},e)=1\end{subarray}}(-1)^{\frac{te-\delta_{t}}{2\delta_{t}}}\frac{\mu_{P}(e)}{e},$

where $\delta_{t}=\gcd(\frac{n}{4},t)$ and $n_{t}=\frac{n}{4\delta_{t}}$.

###### Proof.

Let

$\begin{split}f_{n}(t)&=\sum_{a\in
M_{n}^{1}(1)}\frac{w_{n}^{at}-w_{n}^{-at}}{i}\\\
&=\frac{1}{i}(w_{n}^{t}-w_{n}^{3t}+w_{n}^{5t}-\ldots-
w_{n}^{(n-1)t}).\end{split}$

As $f_{n}(t)$ is a sum of a geometric progression with common ratio
$-w_{n}^{2t}$, we find that

$f_{n}(t)=\left\\{\begin{array}[]{rl}\frac{n}{2}&\mbox{ if
}t\equiv\frac{n}{4}\ (\mathrm{mod}\ n)\\\ -\frac{n}{2}&\mbox{ if
}t\equiv\frac{3n}{4}\ (\mathrm{mod}\ n)\\\ 0&\mbox{
otherwise.}\end{array}\right.$

Using Lemma 3.4, we have

$\begin{split}f_{n}(t)=\sum_{a\in
M_{n}^{1}(1)}\frac{w_{n}^{at}-w_{n}^{-at}}{i}=\sum_{d\in D_{n}^{1}}\sum_{a\in
G_{n}^{1}(d)}\frac{w_{n}^{at}-w_{n}^{-at}}{i}&=\sum_{d\in D_{n}^{1}}\sum_{a\in
dG_{n/d}^{1}(1)}\frac{w_{n}^{at}-w_{n}^{-at}}{i}\\\ &=\sum_{d\in
D_{n}^{1}}\sum_{a\in
G_{n/d}^{1}(1)}\frac{(w_{n}^{d})^{at}-(w_{n}^{d})^{-at}}{i}\\\ &=\sum_{d\in
D_{n}^{1}}s_{n/d}(t).\end{split}$

In the last equation, we use the fact that $w^{d}=\exp(\frac{2\pi i}{n/d})$ is
an $\frac{n}{d}$-th root of unity. From Theorem 6.11,

$\begin{split}s_{n}(t)&=\sum_{\begin{subarray}{c}d\mid n\\\
t\equiv\frac{d}{4}\ (\mathrm{mod}\
d)\end{subarray}}f_{d}(t)\mu_{P}\left(\frac{n}{d}\right)+\sum_{\begin{subarray}{c}d\mid
n\\\ t\equiv\frac{3d}{4}\ (\mathrm{mod}\
d)\end{subarray}}f_{d}(t)\mu_{P}\left(\frac{n}{d}\right)\\\
&=\sum_{\begin{subarray}{c}d\mid n\\\ t\equiv\frac{d}{4}\ (\mathrm{mod}\
d)\end{subarray}}\frac{d}{2}\mu_{P}\left(\frac{n}{d}\right)-\sum_{\begin{subarray}{c}d\mid
n\\\ t\equiv\frac{3d}{4}\ (\mathrm{mod}\
d)\end{subarray}}\frac{d}{2}\mu_{P}\left(\frac{n}{d}\right)\\\
&=\sum_{\begin{subarray}{c}4d\mid n\\\ t\equiv d\ (\mathrm{mod}\
4d)\end{subarray}}2d\mu_{P}\left(\frac{n}{4d}\right)-\sum_{\begin{subarray}{c}4d\mid
n\\\ t\equiv 3d\ (\mathrm{mod}\
4d)\end{subarray}}2d\mu_{P}\left(\frac{n}{4d}\right)\\\
&=\sum_{\begin{subarray}{c}d\mid\frac{n}{4}\\\ \frac{t}{d}\equiv 1\
(\mathrm{mod}\
4)\end{subarray}}2d\mu_{P}\left(\frac{n}{4d}\right)-\sum_{\begin{subarray}{c}d\mid\frac{n}{4}\\\
\frac{t}{d}\equiv 3\ (\mathrm{mod}\
4)\end{subarray}}2d\mu_{P}\left(\frac{n}{4d}\right)\\\
&=\sum_{\begin{subarray}{c}d\mid\gcd(\frac{n}{4},t)\\\ \frac{t}{d}\textnormal{
is
odd}\end{subarray}}(-1)^{\frac{t-d}{2d}}2d\mu_{P}\left(\frac{n}{4d}\right).\\\
\end{split}$

Let $\delta_{t}=\gcd(\frac{n}{4},t)$ and $\frac{n}{4}=\delta_{t}n_{t}$. We
have

$\begin{split}s_{n}(t)=\sum_{\begin{subarray}{c}d\mid\delta_{t}\\\
\frac{t}{d}\textnormal{ is
odd}\end{subarray}}(-1)^{\frac{t-d}{2d}}2d\mu_{P}\left(\frac{n}{4d}\right)&=\sum_{\begin{subarray}{c}de=\delta_{t}\\\
\frac{t}{d}\textnormal{ is
odd}\end{subarray}}(-1)^{\frac{t-d}{2d}}2d\mu_{P}(n_{t}e)\\\
&=2\mu_{P}(n_{t})\sum_{\begin{subarray}{c}de=\delta_{t}\\\
\frac{t}{d}\textnormal{ is odd}\\\
\gcd(n_{t},e)=1\end{subarray}}(-1)^{\frac{t-d}{2d}}d\mu_{P}(e)\\\
&=2\delta_{t}\mu_{P}(n_{t})\sum_{\begin{subarray}{c}e\mid\delta_{t}\\\
\frac{te}{\delta_{t}}\textnormal{ is odd}\\\
\gcd(n_{t},e)=1\end{subarray}}(-1)^{\frac{te-\delta_{t}}{2\delta_{t}}}\frac{\mu_{P}(e)}{e}.\end{split}$

∎

######  Corollary 6.13.1.

Let $n\equiv 0\ (\mathrm{mod}\ 4)$ and $D_{n}^{3}=\emptyset$. Then

$s_{n}(t)=\left\\{\begin{array}[]{ll}(-1)^{\frac{t-1}{2}}2\mu_{P}(\frac{n}{4})&\textnormal{
if $t$ is odd}\\\ 0&\textnormal{ if $t$ is even,}\end{array}\right.$

where $\gcd(\frac{n}{4},t)=1$.

###### Proof.

Put $\delta_{t}=\gcd(\frac{n}{4},t)=1$ in Theorem 6.13. ∎

######  Corollary 6.13.2.

Let $n=4m$ with $m$ an odd integer and $D_{n}^{3}=\emptyset$. Then

$s_{n}(t)=\left\\{\begin{array}[]{ll}(-1)^{\frac{t-1}{2}}2c_{m}(t)&\textnormal{
if $t$ is odd}\\\ 0&\textnormal{ if $t$ is even.}\end{array}\right.$

###### Proof.

If $t$ is an even integer then $\frac{te}{\delta_{t}}$ is not odd whenever
$e\mid\delta_{t}$ and $0\leq t\leq n-1$. Therefore by Theorem 6.13 we get
$s_{n}(t)=0$. Assume that $t$ is an odd integer. Since $D_{n}^{3}=\emptyset$
and $m$ is odd, $\delta_{t}\equiv 1\ (\mathrm{mod}\ 4)$ for all $0\leq t\leq
n-1$. Note that $\frac{te}{\delta_{t}}\equiv 1\ (\mathrm{mod}\ 4)$ (resp. $3\
(\mathrm{mod}\ 4)$) if and only if $t\equiv 1\ (\mathrm{mod}\ 4)$ (resp. $3\
(\mathrm{mod}\ 4)$) for all $e\mid\delta_{t}$ and $0\leq t\leq n-1$. By Lemma
6.12 and Theorem 6.13, we have

$\begin{split}s_{n}(t)=2\delta_{t}\mu_{P}(n_{t})\sum_{\begin{subarray}{c}e\mid\delta_{t}\\\
\frac{te}{\delta_{t}}\textnormal{ is odd}\\\
\gcd(n_{t},e)=1\end{subarray}}(-1)^{\frac{te-\delta_{t}}{2\delta_{t}}}\frac{\mu_{P}(e)}{e}&=2\delta_{t}\mu(n_{t})\sum_{\begin{subarray}{c}e\mid\delta_{t}\\\
\gcd(n_{t},e)=1\end{subarray}}(-1)^{\frac{t-1}{2}}\frac{\mu(e)}{e}\\\
&=(-1)^{\frac{t-1}{2}}2\mu(n_{t})\delta_{t}\sum_{\begin{subarray}{c}e\mid\delta_{t}\\\
\gcd(n_{t},e)=1\end{subarray}}\frac{\mu(e)}{e}\\\
&=(-1)^{\frac{t-1}{2}}2\mu(n_{t})\delta_{t}\prod_{\begin{subarray}{c}p\mid\delta_{t}\\\
p\nmid n_{t}\end{subarray}}\bigg{(}1-\frac{1}{p}\bigg{)}\\\
&=(-1)^{\frac{t-1}{2}}2\mu(n_{t})\frac{\varphi(m)}{\varphi(m/\delta_{t})}\\\
&=(-1)^{\frac{t-1}{2}}2\frac{\mu({m/\delta_{t}})\varphi(m)}{\varphi(m/\delta_{t})}=(-1)^{\frac{t-1}{2}}2c_{m}(t).\end{split}$

In the fourth equality, we use

$\frac{\varphi(m)}{\varphi({m/\delta_{t}})}=\frac{m}{m/\delta_{t}}\prod_{\begin{subarray}{c}p\mid\delta_{t}\\\
p\nmid
n_{t}\end{subarray}}\bigg{(}1-\frac{1}{p}\bigg{)}=\delta_{t}\prod_{\begin{subarray}{c}p\mid\delta_{t}\\\
p\nmid n_{t}\end{subarray}}\bigg{(}1-\frac{1}{p}\bigg{)}.$

Last equality holds because of Lemma 6.1. ∎

Conflict of Interest: We declare that we have no conflict of interest to this
work.

Acknowledgements

We sincerely thank Prof. Rupam Barman and Dr. Debajit Kalita for going through
the manuscript and giving some useful comments. We also sincerely thank the
anonymous reviewers for carefully reading our manuscript and providing
insightful comments and suggestions that helped us in improving the
presentation of the article.

## References

  * [1] A. Abdollahi and E. Vatandoost.  Which Cayley graphs are integral?  The Electronic Journal of Combinatorics 16(1) (2009), #R122.
  * [2] O. Ahmadi, N. Alon, I.F. Blake and I.E. Shparlinski.  Graphs with integral spectrum.  Linear Algebra and its Applications 430(1) (2009), 547–552.
  * [3] R.C. Alperin.  Rational subsets of finite groups.  International Journal of Group Theory 3(2) (2014), 53–55.
  * [4] R.C. Alperin and B.L. Peterson.  Integral sets and Cayley graphs of finite groups.  The Electronic Journal of Combinatorics 19(1) (2012), #P44.
  * [5] K. Balińska, D. Cvetković, Z. Radosavljević, S. Simić and D. Stevanović.  A survey on integral graphs.  Publikacije Elektrotehničkog fakulteta. Serija Matematika (2002), 42–65.
  * [6] R.B. Bapat, D. Kalita and S. Pati.  On weighted directed graphs.  Linear Algebra and its Applications 436(1) (2012), 99–111.
  * [7] M. Bašić, M. D. Petković and D. Stevanović.  Perfect state transfer in integral circulant graphs.  Applied Mathematics Letters 22 (2009), 1609-1615.
  * [8] N.L. Biggs.  Algebraic graph theory, Volume 67,  Cambridge University Press (1993).
  * [9] W.G. Bridges and R.A. Mena.  Rational g-matrices with rational eigenvalues.  Journal of Combinatorial Theory, Series A 32(2) (1982), 264–280.
  * [10] A.E. Brouwer.  Small integral trees.  The Electronic Journal of Combinatorics 15 (2008), #N1.
  * [11] A.E. Brouwer and W.H. Haemers.  The integral trees with spectral radius 3.  Linear Algebra and its Applications 429(11-12) (2008), 2710–2718.
  * [12] F.C. Bussemaker and D.M. Cvetković.  There are exactly 13 connected, cubic, integral graphs.  Publikacije Elektrotehničkog fakulteta. Serija Matematika i fizika (544/576) (1976), 43–48.
  * [13] T. Cheng, L. Feng and H. Huang.  Integral Cayley graphs over dicyclic group.  Linear Algebra and its Applications 566 (2019), 121–137.
  * [14] E. Cohen.  A class of residue systems (mod $r$) and related arithmetical functions. i. a generalization of möbius inversion.  Pacific Journal of Mathematics 9(1) (1959), 13–23.
  * [15] P. Csikvári.  Integral trees of arbitrarily large diameters.  Journal of Algebraic Combinatorics 32(3) (2010), 371–377.
  * [16] P.J. Davis.  Circulant matrices.  Wiley, (1979).
  * [17] K. Guo and B. Mohar.  Hermitian adjacency matrix of digraphs and mixed graphs.  Journal of Graph Theory 85(1) (2017), 217–248.
  * [18] F. Harary and A.J. Schwenk.  Which graphs have integral spectra?  In Graphs and Combinatorics. Springer (1974), 45–51.
  * [19] K. Ireland and M. Rosen.  A classical introduction to modern number theory.  Springer Verlag (1984).
  * [20] M. Kadyan and B. Bhattacharjya.  Integral mixed Cayley graphs over abelian groups.  The Electronic Journal of Combinatorics 28(4) (2021), #P4.46.
  * [21] W. Klotz and T. Sander.  Integral Cayley graphs over abelian groups.  The Electronic Journal of Combinatorics 17 (2010), #R81.
  * [22] C.Y. Ku, T. Lau and K.B. Wong.  Cayley graph on symmetric group generated by elements fixing $k$ points.  Linear Algebra and its Applications 471 (2015), 405–426.
  * [23] M. Lepović, S.K. Simić, K.T. Balińska and K.T. Zwierzyński.  There are 93 non-regular, bipartite integral graphs with maximum degree four.  The Technical University of Poznań, CSC Report 511 (2005).
  * [24] J. Liu and X. Li.  Hermitian-adjacency matrices and hermitian energies of mixed graphs.  Linear Algebra and its Applications 466 (2015), 182–207.
  * [25] L. Lu, Q. Huang and X. Huang.  Integral Cayley graphs over dihedral groups.  Journal of Algebraic Combinatorics 47(4) (2018), 585–601.
  * [26] M.R. Murty.  Problems in analytic number theory. Volume 206,  Springer Science & Business Media (2008).
  * [27] S. Ramanujan.  On certain trigonometrical sums and their applications in the theory of numbers.  Transactions of the Cambridge Philosophical Society 22(13) (1918), 259–276.
  * [28] W. So.  Integral circulant graphs.  Discrete Mathematics 306(1) (2006), 153–158.
  * [29] D. Stevanović.  4-regular integral graphs avoiding $\pm$3 in the spectrum.  Publikacije Elektrotehničkog fakulteta. Serija Matematika (2003), 99–110.
  * [30] L. Wang and X. Li.  Some new classes of integral trees with diameters 4 and 6.  Australasian Journal of Combinatorics 21 (2000), 237–244.
  * [31] L. Wang, X. Li and X. Yao.  Integral trees with diameters 4, 6 and 8.  Australasian Journal of Combinatorics 25 (2002), 29–44.
  * [32] M. Watanabe.  Note on integral trees.  Mathematics Reports 2 (1979), 95–100.
  * [33] M. Watanabe and A.J. Schwenk.  Integral starlike trees.  Journal of the Australian Mathematical Society 28(1) (1979), 120–128.