# HS-integral and Eisenstein 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 called _second kind hermitian integral_ (_HS-integral_) if
the eigenvalues of its Hermitian-adjacency matrix of the second kind are
integers. A mixed graph is called _Eisenstein integral_ if the eigenvalues of
its (0, 1)-adjacency matrix are Eisenstein integers. We characterize the set
$S$ for which a mixed circulant graph $\text{Circ}(\mathbb{Z}_{n},S)$ is HS-
integral. We also show that a mixed circulant graph is Eisenstein integral if
and only if it is HS-integral. Further, we express the eigenvalues and the HS-
eigenvalues of unitary oriented circulant graphs in terms of generalized
M$\ddot{\text{o}}$bius function.

Keywords. integral graphs; HS-integral mixed graph; Eisenstein integer; mixed
circulant graph.
Mathematics Subject Classifications: 05C50, 05C25

##  1 Introduction

A _mixed graph_ $G$ is a pair $(V(G),E(G))$, where $V(G)$ is a nonempty finite
set and $E(G)$ is a subset of $\left(V(G)\times
V(G)\right)\setminus\\{(u,u)~{}|~{}u\in V(G)\\}$. The sets $V(G)$ and $E(G)$
are called the vertex set and the edge set of $G$, respectively. If $(v,u)\in
E(G)$ if and only if $(u,v)\in E(G)$, then $G$ is called a _simple graph_. If
$(v,u)\not\in E(G)$ whenever $(u,v)\in E(G)$), then $G$ is called an _oriented
graph_.

Let $G$ be a mixed graph on $n$ vertices. The $(0,1)$-adjacency matrix and the
Hermitian-adjacency matrix of the second kind of $G$ are denoted by
$\mathcal{A}(G):=(a_{uv})_{n\times n}$ and $\mathcal{H}(G):=(h_{uv})_{n\times
n}$, respectively, where

$a_{uv}=\left\\{\begin{array}[]{rl}1&\mbox{ if }(u,v)\in E\\\ 0&\textnormal{
otherwise,}\end{array}\right.~{}~{}~{}~{}~{}\text{ and
}~{}~{}~{}~{}~{}~{}h_{uv}=\left\\{\begin{array}[]{cl}1&\mbox{ if }(u,v)\in
E\textnormal{ and }(v,u)\in E\\\ \frac{1+i\sqrt{3}}{2}&\mbox{ if }(u,v)\in
E\textnormal{ and }(v,u)\not\in E\\\ \frac{1-i\sqrt{3}}{2}&\mbox{ if
}(u,v)\not\in E\textnormal{ and }(v,u)\in E\\\ 0&\textnormal{
otherwise.}\end{array}\right.$

The Hermitian-adjacency matrix of the second kind was introduced by Bojan
Mohar [11]. The matrix obtained by replacing the numbers
$\frac{1+i\sqrt{3}}{2}$ and $\frac{1-i\sqrt{3}}{2}$ of $\mathcal{H}(G)$ by the
numbers $i$ and $-i$, respectively, is called the _Hermitian-adjacency_ matrix
(of the first kind) of $G$. Indeed, these Hermitian-adjacency matrices of
mixed graphs are special cases of the adjacency matrix of weighted directed
graphs discussed in [3].

By an _eigenvalue_ (resp. _HS-eigenvalue_) of $G$, we mean an eigenvalue of
$\mathcal{A}(G)$ (resp. $\mathcal{H}(G)$). Similarly, the spectrum (resp. _HS-
spectrum_) of $G$ is the multi-set of the eigenvalues (resp. HS-eigenvalues)
of $G$.

A simple graph is said to be integral if all of its eigenvalues are integers.
A mixed graph $G$ is said to be HS-integral if all of its HS-eigenvalues are
integers. A mixed graph $G$ is said to be Eisenstein integral if all of its
eigenvalues are Eisenstein integers. Note that complex numbers of the form
$a+b\omega_{3}$, where $a,b\in\mathbb{Z},\omega_{3}=\frac{-1+i\sqrt{3}}{2}$,
are known as _Eisenstein integers_. If $G$ is a simple graph, then
$\mathcal{A}(G)=\mathcal{H}(G)$. As a result, the terms HS-eigenvalue, HS-
spectrum, and HS-integrality of $G$ have the same meaning with the terms
eigenvalue, spectrum, and integrality of $G$ in the case of a simple graph
$G$.

In 1974, Harary and Schwenk [7] proposed a characterization of integral
graphs. This problem has inspired a lot of interest over the last decades. For
more results on integral graphs, we refer the reader to [1, 2, 5, 15, 16].

We consider $\Gamma$ to be a finite group throughout the paper. Let $S$ be a
subset of $\Gamma$ that does not contain the identity element. If $S$ is
closed under inverse (resp. $a^{-1}\not\in S$ for all $a\in S$), it is said to
be symmetric (resp. skew-symmetric). Define $\overline{S}=\\{u\in
S:u^{-1}\not\in S\\}$. Then $S\setminus\overline{S}$ is symmetric, while
$\overline{S}$ is skew-symmetric. The mixed Cayley graph
$\text{Cay}(\Gamma,S)$ is a mixed graph with $V(\text{Cay}(\Gamma,S))=\Gamma$
and $E(\text{Cay}(\Gamma,S))=\\{(a,b):a,b\in\Gamma,ba^{-1}\in S\\}$. If $S$ is
symmetric (resp. skew-symmetric), then $\text{Cay}(\Gamma,S)$ is a simple
Cayley graph (resp. oriented Cayley graph). If $G={\mathbb{Z}}_{n}$, then the
graph $\text{Cay}(\Gamma,S)$ is called a _circulant_ graph, and it is denoted
by $\text{Circ}(\mathbb{Z}_{n},S)$.

In this paper, we characterize the set $S$ for which a mixed circulant graph
$\text{Circ}(\mathbb{Z}_{n},S)$ is HS-integral. We also show that a mixed
circulant graph is Eisenstein integral if and only if it is HS-integral.
Indeed, the characterizations of this paper are special cases of that in [9],
in which we considered the group to be abelian. However, due to the speciality
of the group ${\mathbb{Z}}_{n}$, intermediary results and their proof
techniques in this paper are different than that in [9]. In this paper, we
also express the eigenvalues and the HS-eigenvalues of unitary oriented
circulant graphs in terms of generalized M$\ddot{\text{o}}$bius function,
which was not considered in [9]. We discussed integrality of the eigenvalues
of the Hermitian-adjacency matrix (of the first kind) of mixed circulant
graphs in [10]. The results in this paper are influenced from that in [10]. As
a result, proof techniques and flow of results in this paper have some
similarities with that in [10].

This paper is organized as follows. In Section 2, some preliminary concepts
and results are discussed. In particular, we express the HS-eigenvalues of a
mixed circulant graph as a sum of HS-eigenvalues of a simple circulant graph
and an oriented circulant graph. In Section 3, we obtain a sufficient
condition on the connection set for the HS-integrality of an oriented
circulant graph. In Section 4, we first characterize HS-integrality of
oriented circulant graphs by proving the necessity of the condition obtained
in Section 3. After that, we extend this characterization to mixed circulant
graphs. In Section 5, we prove that a mixed circulant graph is Eisenstein
integral if and only if it is HS-integral. In the last section, we express the
eigenvalues and the HS-eigenvalues of unitary oriented circulant graphs in
terms of generalized M$\ddot{\text{o}}$bius function.

##  2 Preliminaries

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

$C=\begin{bmatrix}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{bmatrix},$

where each row is a cyclic shift of the row above it. The circulant matrix $C$
is also denoted by $\text{Circ}(c_{0},c_{1},\ldots,c_{n-1})$. Note that the
$(j,k)$-th entry of $C$ is $c_{k-j\ (\mathrm{mod}\ n)}$. A circulant matrix is
diagonalizable by the matrix $F$ whose $j$-th column is given by

$F_{j}=\frac{1}{\sqrt{n}}\left[1~{}~{}\omega_{n}^{j}~{}~{}\ldots~{}~{}\omega_{n}^{(n-1)j}\right]^{T},$

where $\omega_{n}=\exp{\left(\frac{2\pi i}{n}\right)}$ and $0\leq j\leq n-1$.
The eigenvalues of $C$ are given by

$\lambda_{j}=\sum\limits_{k=0}^{n-1}c_{k}\omega_{n}^{jk}\textnormal{ for
}j\in\\{0,1,...,n-1\\}.$ (1)

See [6] for more details on circulant matrices.

######  Lemma 2.1.

Let $S$ be a subset of $\mathbb{Z}_{n}$ such that $0\notin S$. Then the HS-
spectrum of the mixed circulant graph $\text{Circ}(\mathbb{Z}_{n},S)$ is
$\\{\gamma_{0},\gamma_{1},...,\gamma_{n-1}\\}$, where
$\gamma_{j}=\lambda_{j}+\mu_{j}$,

$\lambda_{j}=\sum\limits_{k\in
S\setminus\overline{S}}\omega_{n}^{jk}~{}~{}\text{ and
}~{}~{}\mu_{j}=\sum\limits_{k\in\overline{S}}(\omega_{6}\omega_{n}^{jk}+\omega_{6}^{5}\omega_{n}^{-jk})\textnormal{
for }j\in\\{0,1,...,n-1\\}.$

###### Proof.

Let

$c_{s}=\left\\{\begin{array}[]{rl}1&\mbox{ if }s\in S\setminus\overline{S}\\\
\omega_{6}&\mbox{ if }s\in\overline{S}\\\ \omega_{6}^{5}&\mbox{ if
}s\in\overline{S}^{-1}\\\ 0&\textnormal{ otherwise.}\end{array}\right.$

Then the HS-spectrum of $\text{Circ}(\mathbb{Z}_{n},S)$ is same as the
spectrum of $\text{Circ}(c_{0},...,c_{n-1})$. Now the proof follows from
Equation (1). ∎

From Lemma 2.1, we observe that the HS-eigenvalues of a mixed circulant graph
$\text{Circ}(\mathbb{Z}_{n},S)$ are the sum of the HS-eigenvalues of the mixed
graphs $\text{Circ}(\mathbb{Z}_{n},S\setminus\overline{S})$ and
$\text{Circ}(\mathbb{Z}_{n},\overline{S})$. Note that
$\omega_{6}=-\omega_{3}^{2}$ and $\omega_{6}^{5}=-\omega_{3}$. Therefore the
eigenvalue $\mu_{j}$ can also be written as
$\mu_{j}=-\sum\limits_{k\in\overline{S}}(\omega_{3}^{2}\omega_{n}^{jk}+\omega_{3}\omega_{n}^{-jk})$.
Further, one can see that the eigenvalues of $\text{Circ}(\mathbb{Z}_{n},S)$
are given by $\sum\limits_{k\in S}\omega_{n}^{jk}$ for each
$j\in\\{0,1,...,n-1\\}$.

Let $n\geq 2$ be a fixed positive integer. We review some basic definitions
and notations from [14]. For a divisor $d$ of $n$, define

$\displaystyle M_{n}(d)=\\{dk:1\leq dk\leq n-1\\}~{}\text{ and}$
$\displaystyle G_{n}(d)=\\{dk:1\leq dk\leq n-1,\gcd(dk,n)=d\\}.$

It is clear that $M_{n}(n)=G_{n}(n)=\emptyset$, $M_{n}(d)=dM_{\frac{n}{d}}(1)$
and $G_{n}(d)=dG_{\frac{n}{d}}(1)$.

######  Lemma 2.2.

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

Wasin So [14] characterized integral circulant graphs in the following
theorem.

######  Theorem 2.3.

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

Let $n\equiv 0\ (\mathrm{mod}\ 3)$. For a divisor $d$ of
$\frac{n}{3},r\in\\{0,1,2\\}$ and $g\in\mathbb{Z}$, define the following sets:

$\displaystyle M_{n,3}^{r}(d)=\\{dk:0\leq dk\leq n-1,k\equiv r\ (\mathrm{mod}\
3)\\},$ $\displaystyle G_{n,3}^{r}(d)=\\{dk:1\leq dk\leq
n-1,\gcd(dk,n)=d,k\equiv r\ (\mathrm{mod}\ 3)\\},$ $\displaystyle
D_{g,3}=\\{k:k\text{ divides }g,k\not\equiv 0\ (\mathrm{mod}\ 3)\\}~{}\text{
and}$ $\displaystyle D_{g,3}^{r}=\\{k:k\text{ divides }g,k\equiv r\
(\mathrm{mod}\ 3)\\}.$

It is clear $D_{g,3}=D_{g,3}^{1}\bigcup\limits D_{g,3}^{2}$.

######  Lemma 2.4.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$, $d$ divide $\frac{n}{3}$ and
$g=\frac{n}{3d}$. Then the following hold:

  1. (i)

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

  2. (ii)

$M_{n,3}^{0}(d)=M_{n}(3d)\cup\\{0\\}$.

###### Proof.

  1. (i)

Let $dk\in M_{n,3}^{1}(d)\cup M_{n,3}^{2}(d)$. Lemma 2.2 gives
$M_{n,3}^{1}(d)\cup M_{n,3}^{2}(d)\subseteq M_{n}(d)=\bigcup\limits_{h\mid
3g}G_{n}(hd)$. So there exists a divisor $h$ of $3g$ such that $dk=\alpha hd$,
for some $\alpha\in\mathbb{Z}$ with $\gcd(\alpha,\frac{3g}{h})=1$. Now we have
$h=\frac{k}{\alpha}$ and $k$ is not a multiple of $3$, which imply that $h|g$
and $h$ is not a multiple of $3$. Thus $h\in D_{g,3}$, and so
$dk\in\bigcup\limits_{h\in D_{g,3}}G_{n}(hd)$. Conversely, let
$x\in\bigcup\limits_{h\in D_{g,3}}G_{n}(hd)$. Then there exists $h\in D_{g,3}$
such that $x=\alpha hd$, where $\alpha\in\mathbb{Z}$ and
$\gcd(\alpha,\frac{3g}{h})=1$. Note that $\alpha$ and $h$ are not multiples of
$3$. Thus $\alpha h\equiv 1$ or $2\ (\mathrm{mod}\ 3)$, and so $x\in
M_{n,3}^{1}(d)\cup M_{n,3}^{2}(d)$.

  2. (ii)

By definition, we have

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

∎

We now prove that $G_{n}(d)$ is a disjoint union of $G_{n,3}^{1}(d)$ and
$G_{n,3}^{2}(d)$.

######  Lemma 2.5.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$, $d$ divide $\frac{n}{3}$ and
$g=\frac{n}{3d}$. Then the following hold:

  1. (i)

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

  2. (ii)

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

  3. (iii)

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

  4. (iv)

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

###### Proof.

  1. (i)

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

  2. (ii)

Since $G_{n,3}^{1}(d)\subseteq G_{n}(d)$ and $G_{n,3}^{2}(d)\subseteq
G_{n}(d)$, we have $G_{n,3}^{1}(d)\cup G_{n,3}^{2}(d)\subseteq G_{n}(d)$.
Conversely, let $x\in G_{n}(d)$. Then $x=d\alpha$ for some $\alpha$ satisfying
$\gcd(\alpha,3g)=1$, and so $\alpha\equiv 1$ or $2\ (\mathrm{mod}\ 3)$. Hence
$G_{n}(d)\subseteq G_{n,3}^{1}(d)\cup G_{n,3}^{2}(d)$.

  3. (iii)

Let $dk\in M_{n,3}^{1}(d)$ so that $k\equiv 1\ (\mathrm{mod}\ 3)$. By Lemma
2.4, there exists $h\in D_{g,3}$ satisfying $dk\in G_{n}(hd)$. Thus $dk\in
G_{n,3}^{1}(hd)$ or $dk\in G_{n,3}^{2}(hd)$.
Case 1. Assume that $h\equiv 1\ (\mathrm{mod}\ 3)$. Let, if possible, $dk\in
G_{n,3}^{2}(hd)$, that is, $dk=\alpha hd$ for some $\alpha\equiv 2\
(\mathrm{mod}\ 3)$ satisfying $\gcd(\alpha,\frac{3g}{h})=1$. Then we have
$k=\alpha h\equiv 2\ (\mathrm{mod}\ 3)$, a contradiction. Hence $dk\in
G_{n,3}^{1}(hd)$.

Case 2. Assume that $h\equiv 2\ (\mathrm{mod}\ 3)$. Proceeding as in Case 1,
we get $k\equiv 2\ (\mathrm{mod}\ 3)$, a contradiction. Hence $dk\in
G_{n,3}^{2}(hd)$. Thus $M_{n,3}^{1}(d)\subseteq\bigg{(}\bigcup\limits_{h\in
D_{g,3}^{1}}G_{n,3}^{1}(hd)\bigg{)}\cup\bigg{(}\bigcup\limits_{h\in
D_{g,3}^{2}}G_{n,3}^{2}(hd)\bigg{)}$.

Conversely, if $\alpha hd\in G_{n,3}^{1}(hd)$, where $h\in D_{g,3}^{1}$ and
$\alpha\equiv 1\ (\mathrm{mod}\ 3)$, we get $\alpha h\equiv 1\ (\mathrm{mod}\
3)$, that is, $\alpha hd\in M_{n,3}^{1}(d)$. Similarly, $\beta hd\in
G_{n,3}^{2}(hd)$, where $h\in D_{g,3}^{2}$ and $\beta\equiv 1\ (\mathrm{mod}\
3)$, imply that $\beta hd\in M_{n,3}^{1}(d)$. Therefore
$\bigg{(}\bigcup\limits_{h\in
D_{g,3}^{1}}G_{n,3}^{1}(hd)\bigg{)}\cup\bigg{(}\bigcup\limits_{h\in
D_{g,3}^{2}}G_{n,3}^{2}(hd)\bigg{)}\subseteq M_{n,3}^{1}(d)$.

  4. (iv)

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

∎

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-\omega_{n}^{a}).$

Clearly, the degree of $\Phi_{n}(x)$ is $\varphi(n)$, where $\varphi$ denotes
the Euler $\varphi$-function. It is well known that the cyclotomic polynomial
$\Phi_{n}(x)$ is monic and irreducible in $\mathbb{Z}[x]$. See [8] for more
details on cyclotomic polynomials.

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

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

Further, if $n\equiv 0\ (\mathrm{mod}\ 3)$ then
$\mathbb{Q}(\omega_{3},\omega_{n})=\mathbb{Q}(\omega_{n})$, and so

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

Note that
$\mathbb{Q}(\omega_{3})=\mathbb{Q}(\omega_{6})=\mathbb{Q}(i\sqrt{3})$.
Therefore $\Phi_{n}(x)$ is irreducible over
$\mathbb{Q}(\omega_{3}),\mathbb{Q}(\omega_{6})$ or $\mathbb{Q}(i\sqrt{3})$ if
and only if $n\not\equiv 0\ (\mathrm{mod}\ 3)$.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$. From Lemma 2.5, we know that $G_{n}(1)$ is
a disjoint union of $G_{n,3}^{1}(1)$ and $G_{n,3}^{2}(1)$. Define

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

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

######  Lemma 2.6.

If $n\equiv 0\ (\mathrm{mod}\ 3)$ then the following hold:

  1. (i)

$x^{\frac{n}{3}}-\omega_{3}=\prod\limits_{h\in
D_{\frac{n}{3},3}^{1}}\Phi_{\frac{n}{h},3}^{1}(x)\prod\limits_{h\in
D_{\frac{n}{3},3}^{2}}\Phi_{\frac{n}{h},3}^{2}(x)$; and

  2. (ii)

$x^{\frac{n}{3}}-\omega_{3}^{2}=\prod\limits_{h\in
D_{\frac{n}{3},3}^{1}}\Phi_{\frac{n}{h},3}^{2}(x)\prod\limits_{h\in
D_{\frac{n}{3},3}^{2}}\Phi_{\frac{n}{h},3}^{1}(x)$.

###### Proof.

  1. (i)

We have $|M_{n,3}^{1}(1)|=\frac{n}{3}$ and $\omega_{n}^{a}$ is a root of
$x^{\frac{n}{3}}-\omega_{3}$ for each $a\in M_{n,3}^{1}(1)$. Therefore

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

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

  2. (ii)

We have $|M_{n,3}^{2}(1)|=\frac{n}{3}$ and $\omega_{n}^{a}$ is a root of
$x^{\frac{n}{3}}-\omega_{3}^{2}$ for each $a\in M_{n,3}^{2}(1)$. Now the proof
is similar to the proof of Part $(i)$.

∎

######  Corollary 2.7.

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

###### Proof.

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

######  Theorem 2.8.

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

###### Proof.

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

##  3 A sufficient condition for the HS-integrality of oriented circulant
graphs

In this section, we obtain a sufficient condition for the HS-integrality of
oriented circulant graphs on $n$ vertices. Throughout this section, we
consider $S$ to be a skew-symmetric subset of $\mathbb{Z}_{n}$.

######  Lemma 3.1.

Let $S$ be a skew-symmetric subset of $\mathbb{Z}_{n}$. If $\sum\limits_{k\in
S}i\sqrt{3}(\omega_{n}^{jk}-\omega_{n}^{-jk})=0$ for each
$j\in\\{0,1,...,n-1\\}$ then $S=\emptyset$.

###### Proof.

Let $A_{S}=(a_{uv})_{n\times n}$ be the matrix whose rows and columns are
indexed by elements of $\mathbb{Z}_{n}$, where

$a_{uv}=\left\\{\begin{array}[]{rl}i\sqrt{3}&\mbox{ if }v-u\in S\\\
-i\sqrt{3}&\mbox{ if }v-u\in S^{-1}\\\ 0&\textnormal{
otherwise.}\end{array}\right.$

Observe that $A_{S}$ is a circulant matrix. Therefore the spectrum of $A_{S}$
is $\\{\alpha_{j}:j=0,1,...,n-1\\}$, where $\alpha_{j}=\sum\limits_{k\in
S}i\sqrt{3}(\omega_{n}^{jk}-\omega_{n}^{-jk})$. Given that $\alpha_{j}=0$ for
all $j=0,1,...,n-1$. This implies that all the entries of $A_{S}$ are zero,
and hence $S=\emptyset$. ∎

######  Theorem 3.2.

Let $n\not\equiv 0\ (\mathrm{mod}\ 3)$. Then the oriented circulant graph
$\text{Circ}(\mathbb{Z}_{n},S)$ is HS-integral if and only if $S=\emptyset$.

###### Proof.

Let $G=\text{Circ}(\mathbb{Z}_{n},S)$ and
$Sp_{H}(G)=\\{\mu_{0},\mu_{1},...,\mu_{n-1}\\}$. Assume that $G$ is HS-
integral. By Lemma 2.1,

$\mu_{j}=\sum\limits_{k\in{S}}(\omega_{6}\omega_{n}^{jk}+\omega_{6}^{5}\omega_{n}^{-jk})\in\mathbb{Z}\textnormal{
for }0\leq j\leq n-1.$

Observe that $\omega_{n}$ is a root of the polynomial
$p(x)=\sum\limits_{k\in{S}}(\omega_{6}x^{jk}+\omega_{6}^{5}x^{j(n-k)})-\mu_{j}\in\mathbb{Q}(\omega_{6})[x]$.
Since $n\not\equiv 0\ (\mathrm{mod}\ 3)$, the polynomial $\Phi_{n}(x)$ is
irreducible in $\mathbb{Q}(\omega_{6})[x]$. Therefore $p(x)$ is a multiple of
the irreducible polynomial $\Phi_{n}(x)$, and so
$\omega_{n}^{-1}=\omega_{n}^{n-1}$ is also a root of $p(x)$, that is,
$\mu_{j}=\mu_{n-j}$. Thus

$\displaystyle 0=\mu_{j}-\mu_{n-j}=\sum_{k\in
S}(\omega_{6}-\omega_{6}^{5})\omega_{n}^{kj}+(\omega_{6}^{5}-\omega_{6})\omega_{n}^{-kj}=\sum_{k\in
S}i\sqrt{3}(\omega_{n}^{kj}-\omega_{n}^{-kj}).$

Therefore by Lemma 3.1, $S=\emptyset$. Conversely, if $S=\emptyset$ then
$\text{Circ}(\mathbb{Z}_{n},S)$ has no edges, and hence all its eigenvalues
are zero. ∎

Theorem 3.2 characterizes integral oriented circulant graphs for the case
$n\not\equiv 0\ (\mathrm{mod}\ 3)$.

######  Lemma 3.3.

Let $S$ be a skew-symmetric subset of $\mathbb{Z}_{n}$ and $k\in\mathbb{N}$.
Then

$\sum\limits_{q\in S}\omega_{k}\omega_{n}^{jq}+\sum\limits_{q\in
S^{-1}}\omega_{k}^{k-1}\omega_{n}^{jq}\in\mathbb{Z}\textnormal{ for each
}j\in\\{0,1,...,n-1\\}$

if and only if

$\sum\limits_{q\in S}\omega_{k}^{k-1}\omega_{n}^{jq}+\sum\limits_{q\in
S^{-1}}\omega_{k}\omega_{n}^{jq}\in\mathbb{Z}\textnormal{ for each
}j\in\\{0,1,...,n-1\\}.$

###### Proof.

Let $H_{S}=[h_{uv}]_{n\times n}$ be the matrix, whose rows and columns are
indexed by elements of $\mathbb{Z}_{n}$, where

$h_{uv}=\left\\{\begin{array}[]{rl}\omega_{k}&\mbox{ if }v-u\in S\\\
\omega_{k}^{k-1}&\mbox{ if }v-u\in S^{-1}\\\ 0&\textnormal{
otherwise.}\end{array}\right.$

Since $H_{S}$ is a circulant matrix, $\sum\limits_{q\in
S}\omega_{k}\omega_{n}^{jq}+\sum\limits_{q\in
S^{-1}}\omega_{k}^{k-1}\omega_{n}^{jq}$ is an eigenvalue of $H_{S}$ for all
$j\in\\{0,1,...,n-1\\}$. Let $\overline{H}_{S}$ be obtained by taking the
complex conjugate of the corresponding entry of $H_{S}$. Note that
$\overline{H}_{S}=H_{S^{-1}}$. The result follows from the fact that the
eigenvalues of $H_{S}$ are integers if and only if the eigenvalues of
$\overline{H}_{S}$ are integers. ∎

######  Lemma 3.4.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$, $d$ divide $\frac{n}{3}$ and
$g=\frac{n}{3d}$. Then $\sum\limits_{q\in
M_{n,3}^{0}(d)}\omega_{n}^{jq}\in\mathbb{Z}$ for $j\in\\{0,1,...,n-1\\}$.

###### Proof.

Using Lemma 2.4 and Lemma 2.2, we get $M_{n,3}^{0}(d)=\bigcup\limits_{h\mid
g}G_{n}(3hd)\bigcup\limits\\{0\\}$. Therefore

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

By Theorem 2.3, the eigenvalue $\sum\limits_{q\in G_{n}(3hd)}\omega_{n}^{jq}$
of the circulant graph $\text{Circ}(\mathbb{Z}_{n},G_{n}(3hd))$ is an integer
for each $h\mid g$. Thus $\sum\limits_{q\in
M_{n}^{0}(d)}\omega_{n}^{jq}\in\mathbb{Z}$ for each $j\in\\{0,1,...,n-1\\}$. ∎

######  Lemma 3.5.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$, $d$ divide $\frac{n}{3}$ and
$g=\frac{n}{3d}$. Then

$\sum\limits_{q\in M_{n,3}^{2}(d)}\omega_{3}\omega_{n}^{jq}+\sum\limits_{q\in
M_{n,3}^{1}(d)}\omega_{3}^{2}\omega_{n}^{jq}\in\mathbb{Z}\mbox{ for each
}j\in\\{0,1,...,n-1\\}.$

###### Proof.

It is enough to show that $\sum\limits_{q\in
M_{n,3}^{2}(d)}\omega_{3}z^{q}+\sum\limits_{q\in
M_{n,3}^{1}(d)}\omega_{3}^{2}z^{q}$ is an integer for all $z\in\mathbb{C}$
satisfying $z^{n}=1$. We have

$\displaystyle z^{n}-1$
$\displaystyle=(z^{d}-\omega_{3})\bigg{(}\sum\limits_{k=1}^{3g}\omega_{3}^{k-1}z^{n-dk}\bigg{)}$
$\displaystyle=(z^{d}-\omega_{3})\bigg{(}\sum\limits_{k=1}^{3g}\omega_{3}^{k}z^{n-dk}\bigg{)}\omega_{3}^{2}$
$\displaystyle=(z^{d}-\omega_{3})\bigg{(}\sum\limits_{\begin{subarray}{c}1\leq
k\leq 3g\\\ k\equiv 0\ (\mathrm{mod}\
3)\end{subarray}}z^{n-dk}+\sum\limits_{\begin{subarray}{c}1\leq k\leq 3g\\\
k\equiv 1\ (\mathrm{mod}\
3)\end{subarray}}\omega_{3}z^{n-dk}+\sum\limits_{\begin{subarray}{c}1\leq
k\leq 3g\\\ k\equiv 2\ (\mathrm{mod}\
3)\end{subarray}}\omega_{3}^{2}z^{n-dk}\bigg{)}\omega_{3}^{2}$
$\displaystyle=(z^{d}-\omega_{3})\bigg{(}\sum\limits_{q\in
M_{n,3}^{0}(d)}z^{q}+\sum\limits_{q\in
M_{n,3}^{2}(d)}\omega_{3}z^{q}+\sum\limits_{q\in
M_{n,3}^{1}(d)}\omega_{3}^{2}z^{q}\bigg{)}\omega_{3}^{2}.$ (2)

Let $z\in\mathbb{C}$ such that $z^{n}=1$. By Equation (2), we get two possible
cases.
Case 1. Assume that $z^{d}-\omega_{3}=0$.
If $q\in M_{n,3}^{1}(d)$ then $q=(3y_{1}+1)d$ for some $y_{1}\in\mathbb{Z}$.
So $z^{q}=z^{(3y_{1}+1)d}=\omega_{3}^{3y_{1}+1}=\omega_{3}$.
If $q\in M_{n,3}^{2}(d)$ then $q=(3y_{2}+2)d$ for some $y_{2}\in\mathbb{Z}$.
So $z^{q}=z^{(3y_{2}+2)d}=\omega_{3}^{3y_{2}+2}=\omega_{3}^{2}$. Thus

$\sum\limits_{q\in M_{n,3}^{2}(d)}\omega_{3}z^{q}+\sum\limits_{q\in
M_{n,3}^{1}(d)}\omega_{3}^{2}z^{q}=\sum\limits_{q\in
M_{n,3}^{2}(d)}1+\sum\limits_{q\in M_{n,3}^{1}(d)}1=|M_{n,3}^{1}(d)\cup
M_{n,3}^{2}(d)|\in\mathbb{Z}.$

Case 2. Assume that $z^{d}-\omega_{3}\neq 0$. Then

$\displaystyle\sum\limits_{q\in M_{n,3}^{0}(d)}z^{q}+\sum\limits_{q\in
M_{n,3}^{2}(d)}\omega_{3}z^{q}+\sum\limits_{q\in
M_{n,3}^{1}(d)}\omega_{3}^{2}z^{q}=0$ $\displaystyle\Rightarrow$
$\displaystyle\sum\limits_{q\in
M_{n,3}^{2}(d)}\omega_{3}z^{q}+\sum\limits_{q\in
M_{n,3}^{1}(d)}\omega_{3}^{2}z^{q}=\sum\limits_{q\in
M_{n,3}^{0}(d)}z^{q}\in\mathbb{Z},\textnormal{ by Lemma
}\ref{NewTooSmallLemma}.$

∎

For $n\equiv 0\ (\mathrm{mod}\ 3)$ and $j\in\\{0,1,\ldots,n-1\\}$, define

$Z_{n}^{1}(j)=\sum\limits_{q\in
G_{n,3}^{1}(1)}\left(\omega_{3}\omega_{n}^{jq}+\omega_{3}^{2}\omega_{n}^{-jq}\right)~{}\text{
and }~{}Z_{n}^{2}(j)=\sum\limits_{q\in
G_{n,3}^{2}(1)}\left(\omega_{3}\omega_{n}^{jq}+\omega_{3}^{2}\omega_{n}^{-jq}\right).$

By Lemma 3.3, $Z_{n}^{1}(j)$ is an integer if and only if $Z_{n}^{2}(j)$ is an
integer.

Note that $G_{n}(d)=dG_{\frac{n}{d}}(1)$,
$G_{n,3}^{1}(d)=dG_{\frac{n}{d},3}^{1}(1)$ and
$G_{n,3}^{2}(d)=dG_{\frac{n}{d},3}^{2}(1)$. Therefore, if $d$ is a divisor of
$\frac{n}{3}$ then

$\begin{split}Z_{\frac{n}{d}}^{1}(j)=\sum_{q\in
G_{\frac{n}{d},3}^{1}(1)}\left[\omega_{3}(\omega_{\frac{n}{d}})^{jq}+\omega_{3}^{2}(\omega_{\frac{n}{d}})^{-jq}\right]&=\sum_{q\in
G_{\frac{n}{d},3}^{1}(1)}\left[\omega_{3}(\omega_{n}^{d})^{jq}+\omega_{3}^{2}(\omega_{n}^{d})^{-jq}\right]\\\
&=\sum_{q\in
dG_{\frac{n}{d},3}^{1}(1)}\left(\omega_{3}\omega_{n}^{jq}+\omega_{3}^{2}\omega_{n}^{-jq}\right)\\\
&=\sum_{q\in
G_{n,3}^{1}(d)}\left(\omega_{3}\omega_{n}^{jq}+\omega_{3}^{2}\omega_{n}^{-jq}\right).\end{split}$

Similarly, if $d$ be a divisor of $\frac{n}{3}$ then

$Z_{\frac{n}{d}}^{2}(j)=\sum_{q\in
G_{n,3}^{2}(d)}\left(\omega_{3}\omega_{n}^{jq}+\omega_{3}^{2}\omega_{n}^{-jq}\right).$

######  Lemma 3.6.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$ and $d$ divide $\frac{n}{3}$. Then
$Z_{\frac{n}{d}}^{1}(j)$ is an integer for each $j\in\\{0,1,\ldots,n-1\\}$.

###### Proof.

Let $d_{1}=\frac{n}{3},d_{2},...,d_{r}=1$ be the positive divisors of
$\frac{n}{3}$ in decreasing order. Apply induction on $k$ to prove that
$Z_{\frac{n}{d_{k}}}(j)$ is an integer for each $j\in\mathbb{Z}$. For $k=1$,
$Z_{\frac{n}{d_{1}}}^{1}(j)=Z_{3}^{1}(j)=\sum\limits_{q\in
G_{3,3}^{1}(1)}\left(\omega_{3}\omega_{3}^{jq}+\omega_{3}^{2}\omega_{3}^{-jq}\right)$
is an integer for each $j\in\\{0,1,\ldots,n-1\\}$. Assume that
$Z_{\frac{n}{d_{k}}}^{1}(j)$ is an integer for each $j\in\mathbb{Z}$, where
$1\leq k<r$. Let $n=3d_{k+1}g_{k+1}$ for some $d_{k+1},g_{k+1}\in\mathbb{Z}$.
By Lemma 2.5, we have

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

Note that $hd_{k+1}$ is also a divisor of $\frac{n}{3}$. If $h>1$ then
$hd_{k+1}=d_{s}$ for some $s<k+1$, and so by induction hypothesis
$Z_{\frac{n}{hd_{k+1}}}^{1}(j)$ and $Z_{\frac{n}{hd_{k+1}}}^{2}(j)$ are
integers for each $j\in\mathbb{Z}$. Note that the unions in (3) is disjoint.
We have

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

Therefore

$\displaystyle\sum\limits_{q\in
M_{n,3}^{1}(d_{k+1})}\left(\omega_{3}\omega_{n}^{jq}+\omega_{3}^{2}\omega_{n}^{-jq}\right)=Z_{\frac{n}{d_{k+1}}}^{1}(j)+\sum\limits_{h\in
D_{g_{k+1},3}^{1},h>1}Z_{\frac{n}{hd_{k+1}}}^{1}(j)+\sum\limits_{h\in
D_{g_{k+1},3}^{2}}Z_{\frac{n}{hd_{k+1}}}^{2}(j),$

and so

$\displaystyle Z_{\frac{n}{d_{k+1}}}^{1}(j)=\sum\limits_{q\in
M_{n,3}^{1}(d_{k+1})}\left(\omega_{3}\omega_{n}^{jq}+\omega_{3}^{2}\omega_{n}^{-jq}\right)-\sum\limits_{h\in
D_{g_{k+1},3}^{1},h>1}Z_{\frac{n}{hd_{k+1}}}^{1}(j)-\sum\limits_{h\in
D_{g_{k+1},3}^{2}}Z_{\frac{n}{hd_{k+1}}}^{2}(j).$ (4)

By Lemma 3.3 and Lemma 3.5, the first summand in the right of (4) is an
integer, and by induction hypothesis the other two summands are also integers.
Hence $Z_{\frac{n}{d_{k+1}}}^{1}(j)$ is an integer for each $j\in\mathbb{Z}$.
Thus the proof is complete by induction. ∎

######  Corollary 3.7.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$ and $d$ a divisor of $\frac{n}{3}$. If
$S\in\\{G_{n,3}^{1}(d),G_{n,3}^{2}(d)\\}$, then the sum $\sum\limits_{q\in
S}(\omega_{3}\omega_{n}^{qj}+\omega_{3}^{2}\omega_{n}^{-qj})$ is an integer
for each $j\in\\{0,1,...,n-1\\}$.

###### Proof.

The proof follows from Lemma 3.3 and Lemma 3.6. ∎

######  Corollary 3.8.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$ and $d$ a divisor of $\frac{n}{3}$. If
$S\in\\{G_{n,3}^{1}(d),G_{n,3}^{2}(d)\\}$, then the sum $\sum\limits_{q\in
S}(\omega_{6}\omega_{n}^{qj}+\omega_{6}^{5}\omega_{n}^{-qj})$ is an integer
for each $j\in\\{0,1,...,n-1\\}$.

###### Proof.

Note that $\omega_{3}=-\omega_{6}^{5},\omega_{3}^{2}=-\omega_{6}$ and
$\left(G_{n,3}^{1}(d)\right)^{-1}=G_{n,3}^{2}(d)$. Therefore the proof follows
from Corollary 3.7. ∎

In the next result, we get a sufficient condition on the connection set $S$
for which the oriented circulant graph $\text{Circ}(\mathbb{Z}_{n},S)$ is HS-
integral.

######  Theorem 3.9.

Let $S$ be a subset of $\mathbb{Z}_{n}$ such that

$S=\left\\{\begin{array}[]{ll}\emptyset&\text{ if }n\not\equiv 0\
(\mathrm{mod}\ 3)\\\ \bigcup\limits_{d\in\mathscr{D}}S_{n}(d)&\text{ if
}n\equiv 0\ (\mathrm{mod}\ 3),\end{array}\right.$

where $\mathscr{D}\subseteq\\{d:d\mid\frac{n}{3}\\}$ and
$S_{n}(d)\in\\{G_{n,3}^{1}(d),G_{n,3}^{2}(d)\\}$. Then the oriented circulant
graph $\text{Circ}(\mathbb{Z}_{n},S)$ is HS-integral.

###### Proof.

The proof follows from Theorem 3.2 and Corollary 3.8. ∎

##  4 Characterization of HS-integral mixed circulant graphs

In this section, we first characterize HS-integrality of oriented circulant
graphs by proving the necessity of Theorem 3.9. After that, we extend this
characterization to mixed circulant graphs. Recall that the case $n\not\equiv
0\ (\mathrm{mod}\ 3)$ have already been considered in Theorem 3.2. Now let
$n\equiv 0\ (\mathrm{mod}\ 3)$ and $d$ a divisor of $\frac{n}{3}$. Define
$u(d)=\left[u(d)_{1},\ldots,u(d)_{n}\right]^{T}$ to be the $n$-vector, where

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

Let $E=[e_{st}]$ be the $n\times n$ matrix defined by
$e_{st}=\omega_{n}^{st}$. Note that $E$ is an invertible matrix and
$EE^{*}=nI_{n}$, where $E^{*}$ is the conjugate transpose of $E$. Using
Theorem 3.9, we get $Eu(d)\in\mathbb{Z}^{n}$.

######  Lemma 4.1.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$ and $v\in\mathbb{Q}^{n}(\omega_{3})$ such
that $Ev\in\mathbb{Q}^{n}$. Let the coordinates of $v$ be indexed by the
elements of $\mathbb{Z}_{n}$. Then

  1. (i)

$\overline{v}_{s}=v_{n-s}$ for all $1\leq s\leq n$;

  2. (ii)

if $d\mid\frac{n}{6}$ then $v_{s}=v_{t}$ for all $s,t\in G_{n,3}^{1}(d)$; and

  3. (iii)

if $d\nmid\frac{n}{3},d\mid n$ and $d<n$ then $v_{r}=v_{n-r}$ for all $r\in
G_{n}(d)$.

###### Proof.

Let $u=Ev\in\mathbb{Q}^{n}$, where $v\in\mathbb{Q}^{n}(\omega_{3})$. Then
$v=\frac{1}{n}E^{*}u$, and so

$\displaystyle v_{s}=\frac{1}{n}\sum_{j=1}^{n}u_{j}\omega_{n}^{s(n-j)}.$ (5)

  1. (i)

Taking complex conjugate of both sides in Equation 5, we get
$\overline{v}_{s}=v_{n-s}$ for all $1\leq s\leq n$.

  2. (ii)

Assume that $d\mid\frac{n}{3}$ and $s,t\in G_{n,3}^{1}(d)$. Then
$\frac{s}{d},\frac{t}{d}\in G_{\frac{n}{d},3}^{1}(1)$, and so
$\omega_{n}^{s}$, $\omega_{n}^{t}$ are roots of $\Phi_{\frac{n}{d},3}^{1}(x)$.
Note that
$v_{s}=\frac{1}{n}\sum\limits_{j=1}^{n}u_{j}\omega_{n}^{s(n-j)}\in\mathbb{Q}(\omega_{3})$.
Therefore $\omega_{n}^{s}$ is a root of
$p(x)=\frac{1}{n}\sum\limits_{j=1}^{n}u_{j}x^{n-j}-v_{s}\in\mathbb{Q}(\omega_{3})[x]$.
Hence $p(x)$ is a multiple of the irreducible monic polynomial
$\Phi_{\frac{n}{d},3}^{1}(x)$, and so $\omega_{n}^{t}$ is also a root of
$p(x)$, that is,
$v_{s}=\frac{1}{n}\sum\limits_{j=1}^{n}u_{j}\omega_{n}^{t(n-j)}=v_{t}$.

  3. (iii)

Assume that $d\nmid\frac{n}{3},d\mid n$, $d<n$ and $r\in G_{n}(d)$. Then
$r,n-r\in G_{n}(d)$, and so $\omega_{n}^{r}$, $\omega_{n}^{n-r}$ are roots of
$\Phi_{\frac{n}{d}}(x)$. Since
$v_{r}=\frac{1}{n}\sum\limits_{j=1}^{n}u_{j}\omega_{n}^{r(n-j)}\in\mathbb{Q}(\omega_{3})$,
we find that $\omega_{n}^{r}$ is a root of the polynomial
$q(x)=\frac{1}{n}\sum\limits_{j=1}^{n}u_{j}x^{(n-j)}-v_{r}\in\mathbb{Q}(\omega_{3})[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}(\omega_{3})$ as $\frac{n}{d}\not\equiv 0\ (\mathrm{mod}\ 3)$. Thus
$\omega_{n}^{n-r}$ is also a root of $q(x)$, that is,
$v_{r}=\frac{1}{n}\sum\limits_{j=1}^{n}u_{j}\omega_{n}^{(n-r)(n-j)}=v_{n-r}$.

∎

In the next theorem, we prove the converse of Theorem 3.9.

######  Theorem 4.2.

Let $S$ be a skew-symmetric subset of $\mathbb{Z}_{n}$. Then the oriented
circulant graph $\text{Circ}(\mathbb{Z}_{n},S)$ is HS-integral if and only if

$S=\left\\{\begin{array}[]{ll}\emptyset&\text{ if }n\not\equiv 0\
(\mathrm{mod}\ 3)\\\ \bigcup\limits_{d\in\mathscr{D}}S_{n}(d)&\text{ if
}n\equiv 0\ (\mathrm{mod}\ 3),\end{array}\right.$

where $\mathscr{D}\subseteq\\{d:d\mid\frac{n}{3}\\}$ and
$S_{n}(d)\in\\{G_{n,3}^{1}(d),G_{n,3}^{2}(d)\\}$.

###### Proof.

We proved the sufficient part in Theorem 3.9. Assume that
$\text{Circ}(\mathbb{Z}_{n},S)$ is HS-integral. If $n\not\equiv 0\
(\mathrm{mod}\ 3)$ then by Theorem 3.2, $S=\emptyset$. Let $n\equiv 0\
(\mathrm{mod}\ 3)$ and let $v$ be the vector of length $n$ defined by

$v_{k}=\left\\{\begin{array}[]{rl}-\omega_{3}^{2}&\text{ if }k\in S\\\
-\omega_{3}&\text{ if }n-k\in S\\\ 0&\text{ otherwise}.\end{array}\right.$

Note that each entry of $Ev$ is an HS-eigenvalue of
$\text{Circ}(\mathbb{Z}_{n},S)$, and so $Ev\in\mathbb{Z}^{n}$. Thus $v$
satisfies all the conditions of Lemma 4.1.

By conditions $(i)$ and $(iii)$ of Lemma 4.1, if $d\nmid\frac{n}{3},d\mid n$
and $d<n$ then $v_{r}=v_{n-r}\in{\mathbb{R}}$ for all $r\in G_{n}(d)$. Also,
by definition of $v$ we have, $v_{r}\in{\mathbb{R}}$ if and only if $r\notin
S\cup S^{-1}$. Therefore
$S\subseteq\bigcup\limits_{d\mid\frac{n}{3}}\left[G_{n,3}^{1}(d)\cup
G_{n,3}^{2}(d)\right]$.

Further, if $r\in S\cap G_{n,3}^{1}(d)$ for some $d\mid\frac{n}{3}$, again by
condition $(ii)$ of Lemma 4.1, we have $G_{n,3}^{1}(d)\subseteq S$. Similarly,
if $r\in S\cap G_{n,3}^{2}(d)$ for some $d\mid\frac{n}{3}$ then
$G_{n,3}^{2}(d)\subseteq S$. Thus there exists
$\mathscr{D}\subseteq\\{d:d\mid\frac{n}{3}\\}$ such that

$S=\left\\{\begin{array}[]{ll}\emptyset&\text{ if }n\not\equiv 0\
(\mathrm{mod}\ 3)\\\ \bigcup\limits_{d\in\mathscr{D}}S_{n}(d)&\text{ if
}n\equiv 0\ (\mathrm{mod}\ 3),\end{array}\right.$

where $S_{n}(d)\in\\{G_{n,3}^{1}(d),G_{n,3}^{2}(d)\\}$. ∎

The following example illustrates Theorem 4.2.

######  Example 4.3.

Consider $\Gamma=\mathbb{Z}_{12}$ and $S=\\{2,5,11\\}$. The oriented graph
$\text{Circ}(\mathbb{Z}_{12},S)$ is shown in Figure 1(a). We see that
$G_{12,3}^{2}(1)=\\{5,11\\}$ and $G_{12,3}^{1}(2)=\\{2\\}$. Therefore
$S=G_{12,3}^{2}(1)\cup G_{12,3}^{1}(2)$, and hence
$\text{Circ}(\mathbb{Z}_{12},S)$ is HS-integral. Further, using Corollary 2.1,
the HS-eigenvalues of $\text{Circ}(\mathbb{Z}_{12},S)$ are obtained as

$\mu_{j}=\cos\left(\frac{\pi j}{3}\right)+\cos\left(\frac{5\pi
j}{6}\right)+\cos\left(\frac{11\pi
j}{6}\right)-\sqrt{3}\left[\sin\left(\frac{\pi
j}{3}\right)+\sin\left(\frac{5\pi j}{6}\right)+\sin\left(\frac{1\pi
j}{6}\right)\right],$

$\text{for each }j\in\mathbb{Z}_{12}$. We find that
$\mu_{0}=3,\mu_{1}=-1,\mu_{2}=2,\mu_{3}=-1,\mu_{4}=3,\mu_{5}=2,\mu_{6}=-1,$
$\mu_{7}=-1,\mu_{8}=-6,\mu_{9}=-1,\mu_{10}=-1$ and $\mu_{11}=2$. Thus all the
HS-eigenvalues of $\text{Circ}(\mathbb{Z}_{12},S)$ are integers. ∎

$\ 0$$\ 1$$2$$\ 3$$\ 6$$4$$5$$\ 11$$10$$\ 9$$8$$7$ (a) $S=\\{2,5,11\\}$

$\ 0$$\ 1$$2$$\ 3$$\ 6$$4$$5$$\ 11$$10$$\ 9$$8$$7$ (b) $S=\\{2,5,10,11\\}$

Figure 1: The graph $Circ(\mathbb{Z}_{12},S)$.

######  Lemma 4.4.

Let $S$ be a skew-symmetric subset of $\mathbb{Z}_{n}$ and $t(\neq
0)\in\mathbb{Q}$. If $\sum\limits_{k\in
S}it\sqrt{3}(\omega_{n}^{jk}-\omega_{n}^{-jk})$ is an integer for each
$j\in\\{0,...,n-1\\}$ then

$S=\left\\{\begin{array}[]{ll}\emptyset&\text{ if }n\not\equiv 0\
(\mathrm{mod}\ 3)\\\ \bigcup\limits_{d\in\mathscr{D}}S_{n}(d)&\text{ if
}n\equiv 0\ (\mathrm{mod}\ 3),\end{array}\right.$

where $\mathscr{D}\subseteq\\{d:d\mid\frac{n}{3}\\}$ and
$S_{n}(d)\in\\{G_{n,3}^{1}(d),G_{n,3}^{2}(d)\\}$.

###### Proof.

Let $\alpha_{j}=\sum\limits_{k\in
S}it\sqrt{3}(\omega_{n}^{jk}-\omega_{n}^{-jk})$ for each
$j\in\\{0,...,n-1\\}$. Assume that $n\not\equiv 0\ (\mathrm{mod}\ 3)$, so that
$\Phi_{n}(x)$ is irreducible in $\mathbb{Q}(\omega_{3})[x]$. Then
$\omega_{n}^{j}$ is a root of $p(x)=\sum\limits_{k\in
S}it\sqrt{3}(x^{k}-x^{n-k})-\alpha_{j}\in\mathbb{Q}(\omega_{3})[x]$. Therefore
$p(x)$ is a multiple of the irreducible polynomial $\Phi_{n}(x)$, and so
$\omega_{n}^{-j}=\omega_{n}^{n-j}$ is also a root of $p(x)$, that is,
$\alpha_{j}=\alpha_{n-j}$. Thus $\alpha_{j}=-\alpha_{n-j}$ and
$\alpha_{j}=\alpha_{n-j}$ implies that $\alpha_{j}=\alpha_{n-j}=0$. By Lemma
3.1, we get $S=\emptyset$.

Assume that $n\equiv 0\ (\mathrm{mod}\ 3)$. Let $v$ be the vector of length
$n$ defined by

$v_{k}=\left\\{\begin{array}[]{rl}it\sqrt{3}&\mbox{if }k\in S\\\
-it\sqrt{3}&\mbox{if }n-k\in S\\\ 0&\mbox{otherwise}.\end{array}\right.$

Since $v\in\mathbb{Q}^{n}(\omega_{3})$ and the $j$-th coordinate of $Ev$ is
$\alpha_{j}$, we have $Ev\in\mathbb{Q}^{n}$. Thus $v$ satisfies all the
conditions of Lemma 4.1. Hence

$S=\left\\{\begin{array}[]{ll}\emptyset&\text{ if }n\not\equiv 0\
(\mathrm{mod}\ 3)\\\ \bigcup\limits_{d\in\mathscr{D}}S_{n}(d)&\text{ if
}n\equiv 0\ (\mathrm{mod}\ 3),\end{array}\right.$

where $\mathscr{D}\subseteq\\{d:d\mid\frac{n}{3}\\}$ and
$S_{n}(d)\in\\{G_{n,3}^{1}(d),G_{n,3}^{2}(d)\\}$. ∎

######  Lemma 4.5.

Let $S$ be a skew-symmetric subset of $\mathbb{Z}_{n}$ and $t(\neq
0)\in\mathbb{Q}$. If $\sum\limits_{k\in
S}it\sqrt{3}(\omega_{n}^{jk}-\omega_{n}^{-jk})$ is an integer for each
$j\in\\{0,...,n-1\\}$ then $\sum\limits_{k\in S\cup
S^{-1}}\omega_{n}^{jk}\in\mathbb{Z}$ for each $j\in\\{0,...,n-1\\}$.

###### Proof.

By Lemma 4.4, there is nothing to prove if $n\not\equiv 0\ (\mathrm{mod}\ 3)$.
Assume $n\equiv 0\ (\mathrm{mod}\ 3)$. Again by Lemma 4.4,
$S=\bigcup\limits_{d\in\mathscr{D}}S_{n}(d)$, where
$\mathscr{D}\subseteq\\{d:d\mid\frac{n}{3}\\}$ and
$S_{n}(d)\in\\{G_{n,3}^{1}(d),G_{n,3}^{2}(d)\\}$. Therefore $S\cup
S^{-1}=\bigcup\limits_{d\in\mathscr{D}}G_{n}(d)$. By Theorem 2.3, the graph
$\text{Circ}(\mathbb{Z}_{n},S\cup S^{-1})$ is integral. Note that
$\sum\limits_{k\in S\cup S^{-1}}\omega_{n}^{jk}$ is an eigenvalue of
$\text{Circ}(\mathbb{Z}_{n},S\cup S^{-1})$ for each $j\in\\{0,...,n-1\\}$.
Hence $\sum\limits_{k\in S\cup S^{-1}}\omega_{n}^{jk}\in\mathbb{Z}$ for each
$j\in\\{0,...,n-1\\}$. ∎

######  Lemma 4.6.

Let $S\subseteq\mathbb{Z}_{n}$ such that $0\notin S$. Then the mixed circulant
graph $\text{Circ}(\mathbb{Z}_{n},S)$ is HS-integral if and only if both
$\text{Circ}(\mathbb{Z}_{n},{S\setminus\overline{S}})$ and
$\text{Circ}(\mathbb{Z}_{n},{\overline{S}})$ are HS-integral.

###### Proof.

Assume that the mixed circulant graph $\text{Circ}(\mathbb{Z}_{n},S)$ is HS-
integral. Let the HS-spectrum of $\text{Circ}(\mathbb{Z}_{n},S)$ be
$\\{\gamma_{0},\gamma_{1},...,\gamma_{n-1}\\}$, where
$\gamma_{j}=\lambda_{j}+\mu_{j}$,

$\lambda_{j}=\sum\limits_{k\in S\setminus\overline{S}}\omega_{n}^{jk}\text{
and
}\mu_{j}=\sum\limits_{k\in\overline{S}}(\omega_{6}\omega_{n}^{jk}+\omega_{6}^{5}\omega_{n}^{-jk})\textnormal{
for each }j\in\\{0,...,n-1\\}.$

By assumption $\gamma_{j}\in\mathbb{Z}$, and so
$\gamma_{j}-\gamma_{n-j}=\sum\limits_{k\in\overline{S}}i\sqrt{3}(\omega_{n}^{jk}-\omega_{n}^{-jk})\in\mathbb{Z}$
for each $j\in\\{0,...,n-1\\}$. By Lemma 4.5, we get
$\sum\limits_{k\in\overline{S}\cup\overline{S}^{-1}}\omega_{n}^{jk}\in\mathbb{Z}$
for each $j\in\\{0,...,n-1\\}$. Since

$\displaystyle\mu_{j}=\frac{1}{2}\sum\limits_{k\in\overline{S}\cup\overline{S}^{-1}}\omega_{n}^{jk}+\frac{1}{2}\sum\limits_{k\in\overline{S}}i\sqrt{3}(\omega_{n}^{jk}-\omega_{n}^{-jk}),$

the number $\mu_{j}$ is a rational algebraic integer for each
$j\in\\{0,...,n-1\\}$. Thus $\text{Circ}(\mathbb{Z}_{n},\overline{S})$ is HS-
integral. Now we have $\gamma_{j},\mu_{j}\in\mathbb{Z}$ for each
$j\in\\{0,...,n-1\\}$, and so $\lambda_{j}=\gamma_{j}-\mu_{j}\in\mathbb{Z}$
for each $j\in\\{0,...,n-1\\}$. Thus
$\text{Circ}(\mathbb{Z}_{n},S\setminus\overline{S})$ is also HS-integral.

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

######  Theorem 4.7.

Let $S\subseteq\mathbb{Z}_{n}$ such that $0\notin S$. Then the mixed circulant
graph $\text{Circ}(\mathbb{Z}_{n},S)$ is HS-integral if and only if
$S\setminus\overline{S}=\bigcup\limits_{d\in\mathscr{D}_{1}}G_{n}(d)$ and

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

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

###### Proof.

By Lemma 4.6, $\text{Circ}(\mathbb{Z}_{n},S)$ is HS-integral if and only if
$\text{Circ}(\mathbb{Z}_{n},S\setminus\overline{S})$ and
$\text{Circ}(\mathbb{Z}_{n},\overline{S})$ are HS-integral. Therefore the
result follows from Theorem 2.3 and Theorem 4.2. ∎

The following example illustrates Theorem 4.7.

######  Example 4.8.

Consider $\Gamma=\mathbb{Z}_{12}$ and $S=\\{2,5,10,11\\}$. The mixed graph
$\text{Circ}(\mathbb{Z}_{12},S)$ is shown in Figure 1(b). We see that
$G_{12,3}^{2}(1)=\\{5,11\\}$ and $G_{12}(2)=\\{2,10\\}$. Therefore
$S=G_{12,3}^{2}(1)\cup G_{12}(2)$, and hence $\text{Circ}(\mathbb{Z}_{12},S)$
is HS-integral. Further, using Corollary 2.1, the HS-eigenvalues of
$\text{Circ}(\mathbb{Z}_{12},S)$ are obtained as

$\gamma_{j}=2\cos\left(\frac{\pi j}{3}\right)+\cos\left(\frac{5\pi
j}{6}\right)+\cos\left(\frac{11\pi
j}{6}\right)-\sqrt{3}\left[\sin\left(\frac{5\pi
j}{6}\right)+\sin\left(\frac{11\pi j}{6}\right)\right],$

$\text{for each }j\in\mathbb{Z}_{12}$. One can see that
$\gamma_{0}=4,\gamma_{1}=1,\gamma_{2}=3,\gamma_{3}=-2,\gamma_{4}=1,\gamma_{5}=1,\gamma_{6}=0,\gamma_{7}=1,$
$\gamma_{8}=-5,\gamma_{9}=-2,\gamma_{10}=-3$ and $\gamma_{11}=1$. Thus all the
HS-eigenvalues of $\text{Circ}(\mathbb{Z}_{12},S)$ are integers. ∎

##  5 Characterization of Eisenstein integral mixed circulant graphs

In 1918, Ramanujan [13] introduced the sum, known as Ramanujan sum, defined by

$\begin{split}C_{n}(q)=\sum_{a\in G_{n}(1)}\cos\left(\frac{2\pi
aq}{n}\right)~{}~{}\text{for each }n,q\in\mathbb{N}.\end{split}$ (6)

It is well known that $C_{n}(q)$ is an integer for all $n,q\in\mathbb{Z}$. For
$n\equiv 0\ (\mathrm{mod}\ 3)$, define

$T_{n}(q)=\sum\limits_{a\in
G_{n,3}^{1}(1)}i\sqrt{3}(\omega_{n}^{aq}-\omega_{n}^{-aq})=\sum\limits_{a\in
G_{n,3}^{1}(1)}-2\sqrt{3}\sin\bigg{(}\frac{2\pi aq}{n}\bigg{)}.$

######  Lemma 5.1.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$. Then $T_{n}(q)\in\mathbb{Z}$ for all
$n,q\in\mathbb{Z}$.

###### Proof.

We have

$\begin{split}Z_{n}^{1}(q)=\sum\limits_{a\in
G_{n,3}^{1}(1)}\left(\omega_{3}\omega_{n}^{aq}+\omega_{3}^{2}\omega_{n}^{-aq}\right)=-\frac{1}{2}\sum\limits_{q\in
G_{n}(1)}\omega_{n}^{jq}+\frac{i\sqrt{3}}{2}\sum\limits_{a\in
G_{n,3}^{1}(1)}(\omega_{n}^{aq}-\omega_{n}^{-aq})=-\frac{C_{n}(q)}{2}+\frac{T_{n}(q)}{2}.\\\
\end{split}$

Thus $T_{n}(q)=2Z_{n}^{1}(q)+C_{n}(q)\in\mathbb{Z}$ for all
$n,q\in\mathbb{Z}$. ∎

######  Lemma 5.2.

Let $n=3^{t}m$ with $m\not\equiv 0\ (\mathrm{mod}\ 3)$. Then the following
statements hold.

  1. (i)

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

  2. (ii)

If $t=1$ then

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

  3. (iii)

If $t\geq 2$ then

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

  4. (iv)

If $t\geq 2$ then

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

  5. (v)

If $t\geq 2$ then

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

###### Proof.

  1. (i)

Assume that $t=1$. Let $k\in m+3G_{\frac{n}{3}}(1)$. We get $k=m+3r$ for some
$r\in G_{\frac{n}{3}}(1)$. Then $\gcd(r,\frac{n}{3})=1$ suggests that
$\gcd(m+3r,n)=1$. Therefore $m+3G_{\frac{n}{3}}(1)\subseteq G_{n}(1)$.
Similarly, $2m+3G_{\frac{n}{3}}(1)\subseteq G_{n}(1)$. Conversely, the size of
both
$\left(m+3G_{\frac{n}{3}}(1)\right)\cup\left(2m+3G_{\frac{n}{3}}(1)\right)$
and $G_{n}(1)$ are same, and hence both are equal.

  2. (ii)

Assume that $t=1$ and $m\equiv 1\ (\mathrm{mod}\ 3)$. Using Part (i), we have
$m+3G_{\frac{n}{3}}(1)\subseteq G_{n,3}^{1}(1)$, and each element of
$m+3G_{\frac{n}{3}}(1)$ is congruent to $1$ modulo $3$. Hence
$G_{n,3}^{1}(1)=m+3G_{\frac{n}{3}}(1)$. Similarly, if $t=1$ and $m\equiv 2\
(\mathrm{mod}\ 3)$ then $G_{n,3}^{1}(1)=2m+3G_{\frac{n}{3}}(1)$.

  3. (iii)

The proof is similar to Part (i).

  4. (iv)

The proof is similar to Part (i).

  5. (v)

Use Part (iii) and Part (iv).

∎

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

######  Lemma 5.3.

Let $n=3m$ with $m\not\equiv 0\ (\mathrm{mod}\ 3)$. Then

$T_{n}(q)=\left\\{\begin{array}[]{rl}-2\sqrt{3}\Im(\omega_{3}^{q})C_{\frac{n}{3}}(q)&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 3)\\\
-2\sqrt{3}\Im(\omega_{3}^{2q})C_{\frac{n}{3}}(q)&\mbox{if }m\equiv 2\
(\mathrm{mod}\ 3).\end{array}\right.$

Moreover, $\frac{T_{n}(q)}{3}$ is an integer for all $q\in\mathbb{Z}$.

###### Proof.

We have

$\begin{split}T_{n}(q)&=\sum\limits_{a\in
G_{n,3}^{1}(1)}i\sqrt{3}(\omega_{n}^{aq}-\omega_{n}^{-aq})\\\
&=\left\\{\begin{array}[]{rl}\sum\limits_{a\in
G_{\frac{n}{3}}(1)}i\sqrt{3}(\omega_{n}^{mq}\omega_{n}^{3aq}-\omega_{n}^{-mq}\omega_{n}^{-3aq})&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 3)\\\ \sum\limits_{a\in
G_{\frac{n}{3}}(1)}i\sqrt{3}(\omega_{n}^{2mq}\omega_{n}^{3aq}-\omega_{n}^{-2mq}\omega_{n}^{-3aq})&\mbox{if
}m\equiv 2\ (\mathrm{mod}\ 3)\end{array}\right.\\\
&=\left\\{\begin{array}[]{rl}-2\sqrt{3}\Im(\omega_{n}^{mq})\sum\limits_{a\in
G_{\frac{n}{3}}(1)}\omega_{\frac{n}{3}}^{aq}&\mbox{if }m\equiv 1\
(\mathrm{mod}\ 3)\\\ -2\sqrt{3}\Im(\omega_{n}^{2mq})\sum\limits_{a\in
G_{\frac{n}{3}}(1)}\omega_{\frac{n}{3}}^{aq}&\mbox{if }m\equiv 2\
(\mathrm{mod}\ 3)\end{array}\right.\\\
&=\left\\{\begin{array}[]{rl}-2\sqrt{3}\Im(\omega_{3}^{q})C_{\frac{n}{3}}(q)&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 3)\\\
-2\sqrt{3}\Im(\omega_{3}^{2q})C_{\frac{n}{3}}(q)&\mbox{if }m\equiv 2\
(\mathrm{mod}\ 3).\end{array}\right.\end{split}$

Here the second equality follows from Part $(ii)$ of Lemma 5.2. Since
$2\Im(\omega_{3})=\sqrt{3}$, therefore $\frac{T_{n}(q)}{3}$ is an integer for
all $q\in\mathbb{Z}$. ∎

######  Lemma 5.4.

Let $n=3^{t}m$ with $m\not\equiv 0\ (\mathrm{mod}\ 3)$ and $t\geq 2$. Then

$2T_{n}(q)=\left\\{\begin{array}[]{rl}-2\sqrt{3}\Im(\omega_{n}^{mq}+\omega_{n}^{4mq}+\omega_{n}^{7mq})C_{\frac{n}{3}}(q)&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 3)\\\
-2\sqrt{3}\Im(\omega_{n}^{2mq}+\omega_{n}^{5mq}+\omega_{n}^{8mq})C_{\frac{n}{3}}(q)&\mbox{if
}m\equiv 2\ (\mathrm{mod}\ 3).\end{array}\right.$

Moreover, $\frac{T_{n}(q)}{3}$ is an integer for all $q\in\mathbb{Z}$.

###### Proof.

We use the fact that $G_{n,3}^{1}(1)$ can be written as disjoint unions in two
different ways using Part $(iii)$ and Part $(iv)$ of Lemma 5.2. We have

$\begin{split}&~{}~{}2T_{n}(q)\\\ =&\sum\limits_{a\in
G_{n,3}^{1}(1)}i\sqrt{3}(\omega_{n}^{aq}-\omega_{n}^{-aq})+\sum\limits_{a\in
G_{n,3}^{1}(1)}i\sqrt{3}(\omega_{n}^{aq}-\omega_{n}^{-aq})\\\
=&\left\\{\begin{array}[]{rl}\sum\limits_{a\in
G_{\frac{n}{3}}(1)}i\sqrt{3}((\omega_{n}^{mq}+\omega_{n}^{4mq}+\omega_{n}^{7mq})\omega_{n}^{3aq}-(\omega_{n}^{-mq}+\omega_{n}^{-4mq}+\omega_{n}^{-7mq})\omega_{n}^{-3aq})&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 3)\\\ \sum\limits_{a\in
G_{\frac{n}{3}}(1)}i\sqrt{3}((\omega_{n}^{2mq}+\omega_{n}^{5mq}+\omega_{n}^{8mq})\omega_{n}^{3aq}-(\omega_{n}^{-2mq}+\omega_{n}^{-5mq}+\omega_{n}^{-8mq})\omega_{n}^{-3aq})&\mbox{if
}m\equiv 2\ (\mathrm{mod}\ 3)\end{array}\right.\\\
=&\left\\{\begin{array}[]{rl}-2\sqrt{3}\Im(\omega_{n}^{mq}+\omega_{n}^{4mq}+\omega_{n}^{7mq})\sum\limits_{a\in
G_{\frac{n}{3}}(1)}\omega_{\frac{n}{3}}^{aq}&\mbox{if }m\equiv 1\
(\mathrm{mod}\ 3)\\\
-2\sqrt{3}\Im(\omega_{n}^{2mq}+\omega_{n}^{5mq}+\omega_{n}^{8mq})\sum\limits_{a\in
G_{\frac{n}{3}}(1)}\omega_{\frac{n}{3}}^{aq}&\mbox{if }m\equiv 2\
(\mathrm{mod}\ 3)\end{array}\right.\\\
=&\left\\{\begin{array}[]{rl}-2\sqrt{3}\Im(\omega_{n}^{mq}+\omega_{n}^{4mq}+\omega_{n}^{7mq})C_{\frac{n}{3}}(q)&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 3)\\\
-2\sqrt{3}\Im(\omega_{n}^{2mq}+\omega_{n}^{5mq}+\omega_{n}^{8mq})C_{\frac{n}{3}}(q)&\mbox{if
}m\equiv 2\ (\mathrm{mod}\ 3).\end{array}\right.\end{split}$

Here the second equality follows from Part $(v)$ of Lemma 5.2. If $t=2$, then

$\begin{split}2T_{n}(q)=\left\\{\begin{array}[]{rl}C_{9}(q)C_{\frac{n}{3}}(q)&\mbox{if
}m\equiv 1\ (\mathrm{mod}\ 3)\\\ C_{9}(q)C_{\frac{n}{3}}(q)&\mbox{if }m\equiv
2\ (\mathrm{mod}\ 3).\end{array}\right.\end{split}$

Thus $\frac{T_{n}(q)}{3}$ is an integer for all $q\in\mathbb{Z}$. Assume that
$t\geq 3$. If $C_{\frac{n}{3}}(q)\neq 0$ then both
$-2\sqrt{3}\Im(\omega_{n}^{mq}+\omega_{n}^{4mq}+\omega_{n}^{7mq})$ and
$-2\sqrt{3}\Im(\omega_{n}^{2mq}+\omega_{n}^{5mq}+\omega_{n}^{8mq})$ are
rational algebraic integers, and hence both are integers for each
$q\in\mathbb{Z}$. As $C_{\frac{n}{3}}(q)$ is an integer multiple of $3$, we
find that $\frac{T_{n}(q)}{3}$ is an integer for all $q\in\mathbb{Z}$. ∎

######  Lemma 5.5.

Let $n\equiv 0\ (\mathrm{mod}\ 3)$. Then $C_{n}(q)$ and $\frac{T_{n}(q)}{3}$
are integers of the same parity for all $q\in\mathbb{Z}$.

###### Proof.

Since $T_{n}(q)-C_{n}(q)=2Z_{n}^{1}(q)$ is an even integer, $C_{n}(q)$ and
$T_{n}(q)$ are integers of the same parity for each $q\in\mathbb{Z}$. By Lemma
5.3 and Lemma 5.4, $\frac{T_{n}(q)}{3}$ is an integer for all
$q\in\mathbb{Z}$. Hence $C_{n}(q)$ and $\frac{T_{n}(q)}{3}$ are integers of
the same parity for all $q\in\mathbb{Z}$. ∎

Let $S$ be a subset of $\mathbb{Z}_{n}$ and $j\in\\{0,1,...,n-1\\}$. Define

$\alpha_{j}(S)=\sum\limits_{k\in S\setminus\overline{S}}\omega_{n}^{jk}\hskip
14.22636pt\textnormal{ and }\hskip
14.22636pt\beta_{j}(S)=\sum\limits_{k\in\overline{S}}(\omega\omega_{n}^{jk}+\overline{\omega}\omega_{n}^{-jk}),$

where $\omega=\frac{1}{2}-\frac{i\sqrt{3}}{6}$. It is clear that
$\alpha_{j}(S)$ and $\beta_{j}(S)$ are real numbers. We have

$\sum_{k\in
S}\omega_{n}^{jk}=\alpha_{j}(S)+\beta_{j}(S)+\bigg{(}\frac{-1}{2}+\frac{i\sqrt{3}}{2}\bigg{)}(\beta_{j}(S)-\beta_{n-j}(S)).$

Note that $\alpha_{j}(S)=\alpha_{n-j}(S)$ for each $j$. Therefore if
$\alpha_{j}(S)+\beta_{j}(S)\in\mathbb{Z}$ for each $j\in\\{0,1,...,n-1\\}$
then
$\beta_{j}(S)-\beta_{n-j}(S)=[\alpha_{j}(S)+\beta_{j}(S)]-[\alpha_{n-j}(S)+\beta_{n-j}(S)]$
is also an integer for each $j\in\\{0,1,...,n-1\\}$. Hence the mixed circulant
graph $\text{Circ}(\mathbb{Z}_{n},S)$ is Eisenstein integral if and only if
$\alpha_{j}(S)+\beta_{j}(S)$ is an integer for each $j\in\\{0,1,...,n-1\\}$.

######  Lemma 5.6.

Let $S\subseteq\mathbb{Z}_{n}$ such that $0\notin S$. Then the mixed circulant
graph $\text{\text{Circ}}(\mathbb{Z}_{n},S)$ is Eisenstein integral if and
only if $2\alpha_{j}(S)$ and $2\beta_{j}(S)$ are integers of the same parity
for each $j\in\\{0,1,...,n-1\\}$.

###### Proof.

Suppose the mixed circulant graph $\text{\text{Circ}}(\mathbb{Z}_{n},S)$ is
Eisenstein integral and $j\in\\{0,1,...,n-1\\}$. Then
$\alpha_{j}(S)+\beta_{j}(S)$ and
$\beta_{j}(S)-\beta_{n-j}(S)=\sum\limits_{k\in\overline{S}}\frac{-i\sqrt{3}}{3}(\omega_{n}^{jk}-\omega_{n}^{-jk})$
are integers. By Lemma 4.5,
$\sum\limits_{k\in\overline{S}\cup\overline{S}^{-1}}\omega_{n}^{jk}\in{\mathbb{Z}}$.
Since

$2\beta_{j}(S)=\sum\limits_{k\in\overline{S}\cup\overline{S}^{-1}}\omega_{n}^{jk}-\sum\limits_{k\in\overline{S}}\frac{i\sqrt{3}}{3}(\omega_{n}^{jk}-\omega_{n}^{-jk}),$

we find that $2\beta_{j}(S)$ is an integer. Therefore
$2\alpha_{j}(S)=2(\alpha_{j}(S)+\beta_{j}(S))-2\beta_{j}(S)$ is also an
integer of the same parity with $2\beta_{j}(S)$.

Conversely, assume that $2\alpha_{j}(S)$ and $2\beta_{j}(S)$ are integers of
the same parity for each $j\in\\{0,1,...,n-1\\}$. Then
$\alpha_{j}(S)+\beta_{j}(S)$ is an integer for each $j\in\\{0,1,...,n-1\\}$.
Hence the mixed circulant graph $\text{\text{Circ}}(\mathbb{Z}_{n},S)$ is
Eisenstein integral. ∎

######  Lemma 5.7.

Let $S\subseteq\mathbb{Z}_{n}$ such that $0\notin S$. Then the mixed circulant
graph $\text{\text{Circ}}(\mathbb{Z}_{n},S)$ is Eisenstein integral if and
only if $\alpha_{j}(S)$ and $\beta_{j}(S)$ are integers for each
$j\in\\{0,1,...,n-1\\}$.

###### Proof.

By Lemma 5.6, it is enough to show that $2\alpha_{j}(S)$ and $2\beta_{j}(S)$
are integers of the same parity if and only if $\alpha_{j}(S)$ and
$\beta_{j}(S)$ are integers. If $\alpha_{j}(S)$ and $\beta_{j}(S)$ are
integers, then clearly $2\alpha_{j}(S)$ and $2\beta_{j}(S)$ are even integers.
Conversely, assume that $2\alpha_{j}(S)$ and $2\beta_{j}(S)$ are integers of
the same parity. Since $\alpha_{j}(S)$ is an algebraic integer, the
integrality of $2\alpha_{j}(S)$ implies that $\alpha_{j}(S)$ is an integer.
Thus $2\alpha_{j}(S)$ is even, and so by the assumption $2\beta_{j}(S)$ is
also an even integer. Hence $\beta_{j}(S)$ is an integer. ∎

######  Theorem 5.8.

Let $S\subseteq\mathbb{Z}_{n}$ such that $0\notin S$. Then the mixed circulant
graph $\text{\text{Circ}}(\mathbb{Z}_{n},S)$ is Eisenstein integral if and
only if $\text{\text{Circ}}(\mathbb{Z}_{n},S)$ is HS-integral.

###### Proof.

By Lemma 5.7, it is enough to show that $\alpha_{j}(S)$ and $\beta_{j}(S)$ are
integers for each $j\in\\{0,1,...,n-1\\}$ if and only if
$\text{\text{Circ}}(\mathbb{Z}_{n},S)$ is HS-integral. Note that
$\alpha_{j}(S)$ is an eigenvalue of the circulant graph
$\text{\text{Circ}}(\mathbb{Z}_{n},S\setminus\overline{S})$. By Theorem 2.3,
$\alpha_{j}(S)$ is an integer for each $j\in\\{0,1,...,n-1\\}$ if and only if
$S\setminus\overline{S}=\bigcup\limits_{d\in\mathscr{D}_{1}}G_{n}(d)$ for some
$\mathscr{D}_{1}\subseteq\\{d:d\mid n\\}$. Assume that $\alpha_{j}(S)$ and
$\beta_{j}(S)$ are integers for each $j$. Then
$-\frac{i\sqrt{3}}{3}\sum\limits_{k\in\overline{S}}(\omega_{n}^{jk}-\omega_{n}^{-jk})=\beta_{j}(S)-\beta_{n-j}(S)$
is also an integer for each $j$. Using Theorem 2.3 and Lemma 4.4, we see that
$S\setminus\overline{S}$ and $\overline{S}$ satisfy the conditions of Theorem
4.7. Hence $\text{\text{Circ}}(\mathbb{Z}_{n},S)$ is HS-integral.

Conversely, assume that $\text{\text{Circ}}(\mathbb{Z}_{n},S)$ is HS-integral.
Then $\text{\text{Circ}}(\mathbb{Z}_{n},S\setminus\overline{S})$ is integral,
and hence $\alpha_{j}(S)$ is an integer for each $j\in\\{0,1,...,n-1\\}$. By
Theorem 4.7, we have

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

where $\mathscr{D}_{2}\subseteq\\{d:d\mid\frac{n}{3}\\}$ and
$S_{n}(d)\in\\{G_{n,3}^{1}(d),G_{n,3}^{2}(d)\\}$. Then

$\begin{split}\beta_{j}(S)&=\frac{1}{2}\sum\limits_{k\in\overline{S}\cup\overline{S}^{-1}}\omega_{n}^{jk}-\frac{1}{6}\sum\limits_{k\in\overline{S}}i\sqrt{3}(\omega_{n}^{jk}-\omega_{n}^{-jk})\\\
&=\frac{1}{2}\sum\limits_{d\in\mathcal{D}_{2}}\sum\limits_{k\in
G_{n}(d)}\omega_{n}^{jk}+\frac{1}{6}\sum\limits_{d\in\mathcal{D}_{2}}\sum\limits_{k\in
S_{n}(d)}i\sqrt{3}(\omega_{n}^{jk}-\omega_{n}^{-jk})\\\
&=\frac{1}{2}\sum\limits_{d\in\mathcal{D}_{2}}C_{\frac{n}{d}}(j)\pm\frac{1}{6}\sum\limits_{d\in\mathcal{D}_{2}}T_{\frac{n}{d}}(j)\\\
&=\frac{1}{2}\sum\limits_{d\in\mathcal{D}_{2}}\left(C_{\frac{n}{d}}(j)\pm\frac{1}{3}T_{\frac{n}{d}}(j)\right).\end{split}$

By Lemma 5.5, $C_{\frac{n}{d}}(j)\pm\frac{1}{3}T_{\frac{n}{d}}(j)$ are even
integers for all $d\in\mathcal{D}_{2}$. Hence $\beta_{j}(S)$ is an integer for
each $j\in\\{0,1,...,n-1\\}$. ∎

The following example illustrates Theorem 5.8.

######  Example 5.9.

Consider the HS-integral graph $\text{\text{Circ}}(\mathbb{Z}_{12},S)$ of
Example 4.8. By Theorem 5.8, the graph $\text{\text{Circ}}(\mathbb{Z}_{12},S)$
is Eisenstein integral. Indeed, the eigenvalues of
$\text{\text{Circ}}(\mathbb{Z}_{12},S)$ are obtained as

$\begin{split}\gamma_{j}=&2\cos\left(\frac{\pi
j}{3}\right)+\cos\left(\frac{5\pi j}{6}\right)+\cos\left(\frac{11\pi
j}{6}\right)+\frac{1}{\sqrt{3}}\left[\sin\left(\frac{5\pi
j}{6}\right)+\sin\left(\frac{11\pi j}{6}\right)\right]\\\
&+\omega_{3}\frac{2}{\sqrt{3}}\left[\sin\left(\frac{5\pi
j}{6}\right)+\sin\left(\frac{11\pi j}{6}\right)\right]~{}~{}\text{for each
}j\in\mathbb{Z}_{12}.\end{split}$

One can see that
$\gamma_{0}=4,\gamma_{1}=1,\gamma_{2}=-1-2\omega_{3},\gamma_{3}=-2,\gamma_{4}=-3-2\omega_{3},\gamma_{5}=1,\gamma_{6}=0,\gamma_{7}=1,$
$\gamma_{8}=-1+2\omega_{3},\gamma_{9}=-2,\gamma_{10}=1+2\omega_{3}$ and
$\gamma_{11}=1$. Thus $\gamma_{j}$ is an Eisenstein integer for each
$j\in\mathbb{Z}_{12}$. ∎

##  6 Eigenvalues and HS-eigenvalues of unitary oriented circulant graphs in
terms of generalized M$\ddot{\text{o}}$bius function

Let $n\equiv 0\ (\mathrm{mod}\ 3)$. The underlying graph of
$\text{\text{Circ}}(\mathbb{Z}_{n},G_{n,3}^{1}(1))$ is known as an unitary
simple circulant graph. The graph
$\text{\text{Circ}}(\mathbb{Z}_{n},G_{n,3}^{1}(1))$ is called an unitary
oriented circulant graph (UOCG). Using Theorem 4.7 and Theorem 5.8, UOCG is an
HS-integral as well as Eisenstein integral graph. The eigenvalues and the HS-
eigenvalues of UOCG are
$\frac{C_{n}(j)}{2}+\frac{T_{n}(j)}{6}+\omega_{3}^{2}\frac{T_{n}(j)}{3}$ and
$\frac{C_{n}(j)}{2}+\frac{T_{n}(j)}{2}$, respectively, for each
$j\in\\{0,1,\ldots,n-1\\}$. Note that $C_{n}(j)$ is an eigenvalue of the
underlying graph of UOCG for each $j\in\\{0,1,\ldots,n-1\\}$. Using Lemma 5.3
and Lemma 5.4, we can express $T_{n}(j)$ in terms of $C_{\frac{n}{3}}(j)$.
This, in turn, express the eigenvalues and the HS-eigenvalues of UOCG in terms
of Ramanujan sums. The Ramanujan sum $C_{n}(j)$ is well known [12] in terms of
M$\ddot{\text{o}}$bius function. In particular, we have

$C_{n}(j)=\sum\limits_{d\mid\delta}d\mu(n/d)=\frac{\mu(n/\delta)\varphi(n)}{\varphi(n/\delta)},$

where $\delta=\gcd(n,j)$. We attempt to obtain similar expression for
$T_{n}(j)$ in terms of generalized M$\ddot{\text{o}}$bius function. That, in
turn, will express the eigenvalues and the HS-eigenvalues of UOCG in terms of
generalized M$\ddot{\text{o}}$bius function.

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$ 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.1.

[12] $\sum\limits_{d\mid n}\mu(d)=\delta(n).$

E. Cohen [4] 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}$ with
$\gcd(n_{1},n_{2})=1$, then $n_{1}n_{2}\in P$ (resp. $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$ with
$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 setting

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

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

######  Theorem 6.2.

[4] $\sum\limits_{d\mid n,d\in Q}\mu_{P}\left(\frac{n}{d}\right)=\delta(n).$

######  Theorem 6.3.

[4] 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).$

For the remaining part of this section, we consider the direct factors
$P=\\{2^{k}:k\geq 0\\}$, and $Q$, the set of all odd natural numbers.

######  Lemma 6.4.

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.$

Note that if $n\equiv 0\ (\mathrm{mod}\ 3)$ then
$D_{n,3}^{2}=D_{\frac{n}{3},3}^{2}$.

######  Theorem 6.5.

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

$\displaystyle T_{n}(j)=\sum_{\begin{subarray}{c}d\mid\frac{n}{3}\\\
\frac{j}{d}\equiv 1\ (\mathrm{mod}\
3)\end{subarray}}-3d\mu\left(\frac{n}{3d}\right)+\sum_{\begin{subarray}{c}d\mid\frac{n}{3}\\\
\frac{j}{d}\equiv 2\ (\mathrm{mod}\
3)\end{subarray}}3d\mu\left(\frac{n}{3d}\right).$

###### Proof.

Let

$\begin{split}f_{n}(j)=\sum_{a\in
M_{n,3}^{1}(1)}i\sqrt{3}(\omega_{n}^{aj}-\omega_{n}^{-aj})=\left\\{\begin{array}[]{rl}-n&\mbox{
if }j\equiv\frac{n}{3}\ (\mathrm{mod}\ n)\\\ n&\mbox{ if }j\equiv\frac{2n}{3}\
(\mathrm{mod}\ n)\\\ 0&\mbox{ otherwise.}\end{array}\right.\end{split}$

Using Lemma 2.5, we have

$\begin{split}f_{n}(j)=\sum_{a\in
M_{n,3}^{1}(1)}i\sqrt{3}(\omega_{n}^{aj}-\omega_{n}^{-aj})&=\sum_{d\in
D_{n,3}^{1}}\sum_{a\in
G_{n,3}^{1}(d)}i\sqrt{3}(\omega_{n}^{aj}-\omega_{n}^{-aj})\\\ &=\sum_{d\in
D_{n,3}^{1}}\sum_{a\in
dG_{\frac{n}{d},3}^{1}(1)}i\sqrt{3}(\omega_{n}^{aj}-\omega_{n}^{-aj})\\\
&=\sum_{d\in D_{n,3}^{1}}\sum_{a\in
G_{\frac{n}{d},3}^{1}(1)}i\sqrt{3}[(\omega_{n}^{d})^{aj}-(\omega_{n}^{d})^{-aj}]=\sum_{d\in
D_{n,3}^{1}}T_{\frac{n}{d}}(j).\end{split}$

In the last equation, we have used the fact that
$\omega_{n}^{d}=\exp(\frac{2\pi i}{n/d})$ is a primitive $\frac{n}{d}$-th root
of unity. Since $D_{n,3}^{1}\subseteq Q$, from Theorem 6.3 we have

$\displaystyle T_{n}(j)=$ $\displaystyle\sum_{\begin{subarray}{c}d\mid n\\\
j\equiv\frac{d}{3}\ (\mathrm{mod}\
d)\end{subarray}}f_{d}(j)\mu_{P}\left(\frac{n}{d}\right)+\sum_{\begin{subarray}{c}d\mid
n\\\ j\equiv\frac{2d}{3}\ (\mathrm{mod}\
d)\end{subarray}}f_{d}(j)\mu_{P}\left(\frac{n}{d}\right)$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}d\mid n\\\ j\equiv\frac{d}{3}\
(\mathrm{mod}\
d)\end{subarray}}-d\mu_{P}\left(\frac{n}{d}\right)+\sum_{\begin{subarray}{c}d\mid
n\\\ j\equiv\frac{2d}{3}\ (\mathrm{mod}\
d)\end{subarray}}d\mu_{P}\left(\frac{n}{d}\right)$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}3d\mid n\\\ j\equiv d\ (\mathrm{mod}\
3d)\end{subarray}}-3d\mu\left(\frac{n}{3d}\right)+\sum_{\begin{subarray}{c}3d\mid
n\\\ j\equiv 2d\ (\mathrm{mod}\
3d)\end{subarray}}3d\mu\left(\frac{n}{3d}\right)$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}d\mid\frac{n}{3}\\\ \frac{j}{d}\equiv
1\ (\mathrm{mod}\
3)\end{subarray}}-3d\mu\left(\frac{n}{3d}\right)+\sum_{\begin{subarray}{c}d\mid\frac{n}{3}\\\
\frac{j}{d}\equiv 2\ (\mathrm{mod}\
3)\end{subarray}}3d\mu\left(\frac{n}{3d}\right).$

∎

The case that $n=3m$ with $m$ an even integer is not covered in Theorem 6.5.
Now assume that $n=3m$ with $m$ an even integer, so that $n\equiv 0\
(\mathrm{mod}\ 6)$. For a divisor $d$ of $\frac{n}{6},r\in\\{1,5\\}$ and
$g\in\mathbb{Z}$, define the following sets:

$\displaystyle M_{n,6}^{r}(d)=\\{dk:0\leq dk<n,k\equiv r\ (\mathrm{mod}\
6)\\};$ $\displaystyle G_{n,6}^{r}(d)=\\{dk:1\leq dk<n,k\equiv r\
(\mathrm{mod}\ 6),\gcd(dk,n)=d\\};~{}\text{ and}$ $\displaystyle
D_{g,6}^{r}=\\{k:k\text{ divides }g,k\equiv r\ (\mathrm{mod}\ 6)\\}.$

######  Lemma 6.6.

Let $n\equiv 0\ (\mathrm{mod}\ 6)$, $d$ divides $\frac{n}{6}$ and
$g=\frac{n}{6d}$. Then the following hold:

  1. (i)

$G_{n,6}^{1}(d)\cap G_{n,6}^{5}(d)=\emptyset$;

  2. (ii)

$G_{n}(d)=G_{n,6}^{1}(d)\cup G_{n,6}^{5}(d)$;

  3. (iii)

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

  4. (iv)

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

###### Proof.

The proof is similar to the proof of Lemma 2.5. ∎

Note that $D_{n,6}^{5}=D_{\frac{n}{6},6}^{5}$. In the next result, we
calculate $T_{n}(j)$ for the values of $n$ not covered in Theorem 6.5.

######  Theorem 6.7.

Let $n\equiv 0\ (\mathrm{mod}\ 6)$ and $D_{n,6}^{5}=\emptyset$. Then

$\displaystyle T_{n}(j)=\sum_{\begin{subarray}{c}d\mid\frac{n}{6}\\\
\frac{j}{d}\equiv 1\mbox{ or }2\ (\mathrm{mod}\
6)\end{subarray}}-3d\mu_{P}\left(\frac{n}{6d}\right)+\sum_{\begin{subarray}{c}d\mid\frac{n}{6}\\\
\frac{j}{d}\equiv 4\mbox{ or }5\ (\mathrm{mod}\
6)\end{subarray}}3d\mu_{P}\left(\frac{n}{6d}\right),$

###### Proof.

Let

$\begin{split}f_{n}(j)=\sum_{a\in
M_{n,6}^{1}(1)}i\sqrt{3}(\omega_{n}^{aj}-\omega_{n}^{-aj})=\left\\{\begin{array}[]{rl}-\frac{n}{2}&\mbox{
if }j\equiv\frac{n}{6}\ (\mathrm{mod}\ n)\\\ -\frac{n}{2}&\mbox{ if
}j\equiv\frac{2n}{6}\ (\mathrm{mod}\ n)\\\ 0&\mbox{ if }j\equiv\frac{3n}{6}\
(\mathrm{mod}\ n)\\\ \frac{n}{2}&\mbox{ if }j\equiv\frac{4n}{6}\
(\mathrm{mod}\ n)\\\ \frac{n}{2}&\mbox{ if }j\equiv\frac{5n}{6}\
(\mathrm{mod}\ n)\\\ 0&\mbox{ otherwise.}\end{array}\right.\end{split}$

By Lemma 6.6 we get

$\begin{split}f_{n}(j)=\sum_{a\in
M_{n,6}^{1}(1)}i\sqrt{3}(\omega_{n}^{aj}-\omega_{n}^{-aj})&=\sum_{d\in
D_{n,6}^{1}}\sum_{a\in
G_{n,6}^{1}(d)}i\sqrt{3}(\omega_{n}^{aj}-\omega_{n}^{-aj})\\\ &=\sum_{d\in
D_{n,6}^{1}}\sum_{a\in
dG_{\frac{n}{d},6}^{1}(1)}i\sqrt{3}(\omega_{n}^{aj}-\omega_{n}^{-aj})\\\
&=\sum_{d\in D_{n,6}^{1}}\sum_{a\in
G_{\frac{n}{d},6}^{1}(1)}i\sqrt{3}[(\omega_{n}^{d})^{aj}-(\omega_{n}^{d})^{-aj}]\\\
&=\sum_{d\in D_{n,6}^{1}}T_{\frac{n}{d}}(j).\end{split}$

In the last equation, we have used the fact that $\omega_{n}^{d}$ is a
primitive $\frac{n}{d}$-th root of unity and
$G_{\frac{n}{d},6}^{1}(1)=G_{\frac{n}{d},3}^{1}(1)$ for all $d\in
D_{n,6}^{1}$. Since $D_{n,6}^{1}\subset Q$, by Theorem 6.3 we get

$\displaystyle T_{n}(j)=$ $\displaystyle\sum_{\begin{subarray}{c}d\mid n\\\
j\equiv\frac{d}{6}\ (\mathrm{mod}\
d)\end{subarray}}f_{d}(j)\mu_{P}\left(\frac{n}{d}\right)+\sum_{\begin{subarray}{c}d\mid
n\\\ j\equiv\frac{2d}{6}\ (\mathrm{mod}\
d)\end{subarray}}f_{d}(j)\mu_{P}\left(\frac{n}{d}\right)$
$\displaystyle+\sum_{\begin{subarray}{c}d\mid n\\\ j\equiv\frac{4d}{6}\
(\mathrm{mod}\
d)\end{subarray}}f_{d}(j)\mu_{P}\left(\frac{n}{d}\right)+\sum_{\begin{subarray}{c}d\mid
n\\\ j\equiv\frac{5d}{6}\ (\mathrm{mod}\
d)\end{subarray}}f_{d}(j)\mu_{P}\left(\frac{n}{d}\right)$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}d\mid n\\\ j\equiv\frac{d}{6}\mbox{ or
}\frac{2d}{6}\ (\mathrm{mod}\
d)\end{subarray}}-\frac{d}{2}\mu_{P}\left(\frac{n}{d}\right)+\sum_{\begin{subarray}{c}d\mid
n\\\ j\equiv\frac{4d}{6}\mbox{ or }\frac{5d}{6}\ (\mathrm{mod}\
d)\end{subarray}}\frac{d}{2}\mu_{P}\left(\frac{n}{d}\right)$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}6d\mid n\\\ j\equiv d\mbox{ or }2d\
(\mathrm{mod}\
6d)\end{subarray}}-3d\mu_{P}\left(\frac{n}{6d}\right)+\sum_{\begin{subarray}{c}6d\mid
n\\\ j\equiv 4d\mbox{ or }5d\ (\mathrm{mod}\
6d)\end{subarray}}3d\mu_{P}\left(\frac{n}{6d}\right)$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}d\mid\frac{n}{6}\\\ \frac{j}{d}\equiv
1\mbox{ or }2\ (\mathrm{mod}\
6)\end{subarray}}-3d\mu_{P}\left(\frac{n}{6d}\right)+\sum_{\begin{subarray}{c}d\mid\frac{n}{6}\\\
\frac{j}{d}\equiv 4\mbox{ or }5\ (\mathrm{mod}\
6)\end{subarray}}3d\mu_{P}\left(\frac{n}{6d}\right).$

∎

## References

  * [1] 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.
  * [2] 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.
  * [3] R.B. Bapat, D. Kalita, and S. Pati.  On weighted directed graphs.  Linear Algebra and its Applications, 436(1) (2012), 99–111.
  * [4] 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.
  * [5] P. Csikvári.  Integral trees of arbitrarily large diameters.  Journal of Algebraic Combinatorics 32(3) (2010), 371–377.
  * [6] P.J. Davis.  Circulant matrices.  Wiley (1979).
  * [7] F. Harary and A.J. Schwenk.  Which graphs have integral spectra?  In Graphs and Combinatorics. Springer (1974), 45–51.
  * [8] K. Ireland and M. Rosen.  A classical introduction to modern number theory.  Springer Verlag (1984).
  * [9] M. Kadyan and B. Bhattacharjya.  HS-integral and Eisenstein integral mixed Cayley graphs over abelian groups.  Linear Algebra and its Applications 645 (2022), 68-90.
  * [10] M. Kadyan and B. Bhattacharjya.  Integral mixed circulant graphs.  arXiv preprint arXiv:2106.01261, 2021.
  * [11] B. Mohar.  A new kind of Hermitian matrices for digraphs.  Linear Algebra and its Applications 584 (2020), 343–352.
  * [12] M.R. Murty.  Problems in analytic number theory. Volume 206,  Springer Science & Business Media (2008).
  * [13] 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.
  * [14] W. So.  Integral circulant graphs.  Discrete Mathematics 306(1) (2006), 153–158.
  * [15] M. Watanabe.  Note on integral trees.  Mathematics Reports 2 (1979), 95–100.
  * [16] M. Watanabe and A.J. Schwenk.  Integral starlike trees.  Journal of the Australian Mathematical Society 28(1) (1979), 120–128.