# Large Language Models for Spatial Trajectory Patterns Mining

Zheng Zhang, Hossein Amiri, Zhenke Liu, Andreas Züfle, Liang Zhao Department
of Computer Science Emory University Atlanta, GA 30322, USA
<EMAIL_ADDRESS>
###### Abstract

Identifying anomalous human spatial trajectory patterns can indicate dynamic
changes in mobility behavior with applications in domains like infectious
disease monitoring and elderly care. Recent advancements in large language
models (LLMs) have demonstrated their ability to reason in a manner akin to
humans. This presents significant potential for analyzing temporal patterns in
human mobility. In this paper, we conduct empirical studies to assess the
capabilities of leading LLMs like GPT-4 and Claude-2 in detecting anomalous
behaviors from mobility data, by comparing to specialized methods. Our key
findings demonstrate that LLMs can attain reasonable anomaly detection
performance even without any specific cues. In addition, providing contextual
clues about potential irregularities could further enhances their prediction
efficacy. Moreover, LLMs can provide reasonable explanations for their
judgments, thereby improving transparency. Our work provides insights on the
strengths and limitations of LLMs for human spatial trajectory analysis.

##  1 Introduction

The widespread adoption of location-enabled mobile devices has led to a
massive collection of human mobility data [18], comprising diverse trajectory
types from individual app usages to public transportation systems. These
mobility traces can be modeled as dynamic graphs, representing sequences of
location visits with associated semantics [21]. Analyzing these dynamic graphs
enables valuable insights for applications like transportation mode
classification and detecting spatiotemporal patterns [14, 33, 5, 38, 26, 35,
1, 10]. A particularly difficult task is identifying anomalous mobility
patterns within an individual’s semantic trajectories, where the trajectory
significantly deviates from their historical patterns. Finding such anomalous
patterns of individuals may indicate a change in behavior which has many
important applications. For instance, infectious disease monitoring [17, 23,
36] or tracking elderly behaviors [25].

In recent times, there has been a surge in progress with large language models
(LLMs) [22, 15] like Transformers [29], BERT [7], GPT [6], among others. These
LLMs act as foundational models, which can be easily adapted for various
downstream applications with minimal adjustments [6, 12, 15, 37]. Notably,
breakthroughs in design and training techniques have enabled emerging
abilities in LLMs, distinguishing cutting-edge models like GPT-3.5 [6], GPT-4
[20], Claude-2 [2], BARD [9], LlaMA [27], and LlaMA-2 [28] from earlier
versions. For example, features such as in-context training [16] and zero-shot
learning [12, 31] allow these models to adapt to tasks they were not
explicitly trained for.

Despite the remarkable progress LLMs have made in diverse NLP tasks like
question answering (QA) and machine translation, their potential in analyzing
human mobility patterns remains largely unexplored. Human mobility data,
unlike typical language sequences, presents with intricate spatial-temporal
dynamics and rich topological connections between entities. Detecting
anomalous behaviors are especially difficult due to the intrinsic property of
unkown nature of anomalies. Existing methods typically rely on creating hand-
crafted features such as the total traveled distance and use heuristic rule to
determine outliers, which limits their capability to generalize effectively to
detect unseen outlier patterns. In contrast, LLMs has natural advanatge since
they can directly perceive natural langauge input. As LLMs have already shown
powerful reasoning ability and generalization capabilities directly from the
input prompt, it becomes intriguing to assess to what extent LLMs can detect
diverse anomaly behaviors under the human mobility patterns.

To systematically study the capabilities of LLMs on detecting outliers
(anomlies) in human mobility trajectories, we conduct a series of empirical
experiments with leading LLMs on diverse datasets. By comparing their
performance to specialized human mobility anomaly detection methods, we aim to
assess the potential strengths and limitations of LLMs in this domain.
Critically, by altering the input prompt formats, we aim to evaluate how
effectively LLMs can extract and leverage the underlying structural
information from the dynamic mobility patterns to enhance their performance in
subsequent tasks. Moreover, we delve into both the effectiveness and
interpretability of LLMs’ predictions.

##  2 Related Works

In recent literature, a few preliminary studies [32, 30, 19] have made
attempts to uncover the potential of applying LLMs in analyzing human mobility
patterns. Xue et al. [32] propose a pipeline called AuxMobLCast that leverages
pre-trained language models for human mobility forecasting by transforming
numeric time series data into natural language descriptions. Experiments on
real-world mobility datasets demonstrate that fine-tuning language models like
BERT with mobility prompts can effectively capture sequential patterns and
yield good performance for predicting future visitor numbers. Wang et al. [30]
propose LLM-Mob that leverages LLMs for human mobility prediction by
formatting mobility data into historical and context stays and designing
effective prompts. Their experiments the potential of harnessing LLMs for
mobility prediction through careful instructional prompting. Musleh et al.
[19] envision a BERT-like system for trajectory analysis but note challenges
like the high number of distinct GPS points compared to words, noisy
trajectory data, and long unrelated trajectories, necessitating customization
of BERT for trajectories rather than direct application. Although some initial
studies exist, our research is the first to comprehensively examine the
capability of LLMs in identifying anomalies in human mobility patterns and
compare them with state-of-the-art human mobility anomaly detection
algorithms.

##  3 Experiments

###  3.1 Experimental Settings

#### Datasets.

We conducted the experiments on two human mobility benchmark datasets: GeoLife
[39] and Patterns-of-Life [41, 11]. Brief descriptions of the datasets are as
follows:

Task
setting |  Prompt to LLM
---|---
Separate |  Task: You are a human mobility trajectory behavior anomaly detector. Given a historical human trajectory information, can you analyse the pattern behind the trajectory and give an anomaly score (from 0 to 1, where larger value indicates more abnormal) of this user’s behavior?
Here is the sequence of trajector: <Sequence>.
Give your analysis and present your esimated anomaly score (from 0 to 1, where
larger value indicates more abnormal) inside a pair of square brackets.
Separate With Hint |  Task: (…Same as Above …)
Hint: The anomaly users would suddenly change their mobility pattern starting
from a time point, which means after a certain time, their mobility behavior
would significantly deviate from their past behaviors. We would use
“***<deviate-point>***” inside each trajectory to denote the time point as
hint.
Here is the sequence of trajector: <Sequence-before> ***<deviate-point>***
<Sequence-after>.
Give your analysis and present your esimated anomaly score (from 0 to 1, where
larger value indicates more abnormal) inside a pair of square brackets.
Combine |  Task: You are a human mobility trajectory behavior anomaly detector. Given a set of N users’ historical human trajectories information, can you analyse the pattern behind each user’s trajectory and give an anomaly score (from 0 to 1, where larger value indicates more abnormal) of users’ behavior?
Here is the sequence of user 1: <Sequence-1>
…
Here is the sequence of user N: <Sequence-N>
Give your analysis and present your esimated anomaly scores about all users
(from 0 to 1, where larger value indicates more abnormal):
Table 1: Examples of different prompts used in anomaly detection experiments.
We also have ‘Combine With Hint’ prompt which is the similar way of adding
hints in ‘Separate With Hint’ prompt. A detailed prompt example is given in
Appendix C due to space limitation.

  * •

GeoLife: This dataset was created using the Microsoft Research Asia’s GPS
Trajectory dataset [39]. The GeoLife dataset, sourced from the GeoLife project
by Microsoft Research Asia, captures the GPS trajectories of 182 users over a
span of more than three years, from April 2007 to August 2012. Each trajectory
in this dataset consists of time-stamped points detailing the latitude, and
longitude. The dataset provides insights into leisure and sports activities,
such as shopping, sightseeing, dining, hiking, and cycling, offering a
comprehensive view of users’ outdoor movements. We first eliminated agents
with fewer than 50 records, resulting in a final count of 69 users. Due to the
lack of ground truth anomalies, we introduced a specific outlier type called
the “imposter outlier", by switching the trajectories with another agent after
a specific time point. In this paper we choose 80% of the stay points of
trajectories as the switching point.

  * •

Patterns-of-Life (PoL): A simulated dataset, where agents emulate human
activities such as working, socializing, and more, in a real-world-like
setting sourced from OpenStreetMap [4]. Throughout their simulated lives,
agents navigate to diverse locations, including restaurants, workplaces,
residential apartments, and recreational venues. We generate 1,000 users over
a span of 4 weeks. We introduced 90 anomaly users with three specific types of
abnormal behavior: (1) Hunger outlier: An agent under this category becomes
hungry more quickly. Such agents have to go to restaurants or their homes much
more often. (2) Social outlier: This type of agent randomly selects
recreational sites to visit when needed, rather than being guided by their
attributes and social network. (3) Work outlier: Agents in this category
abstain from going to work on workdays.

#### Comparison Methods.

We compare with several unsupervised trajectory outlier detection methods,
including three non-deep learning methods OMPAD [3], MoNav-TT [34] and TRAOD
[13], and two state-of-the-art deep learning methods DSVDD [24] and DAE [40,
8]. A detailed introduction of the comparison methods can be found in Appendix
A.

###  3.2 LLM Detection Results

Broadly, this paper focuses on studying the central question of investigating
the capabilities of LLMs on identifying anomalous behaviors within human
mobility patterns from three perspectives:

  * •

Can LLMs effectively detect anomalous behaviors within human mobility patterns
without any indicative information? It is intriguing to assess whether LLMs
can attain substantial predictive performance on anomaly detection tasks, even
in the absence of any clue about the anomalies, e.g. such as temporal
occurrence or the nature of the anomaly.

  * •

Can providing indicative clues about the anomaly enhance the detection
efficacy of LLMs? Incorporating specific clues or hints about potential
anomalies might bolster the LLM’s ability to identify irregularities more
accurately. By offering contextual information, it could guide the LLM to
focus on certain aspects of the data and make more informed predictions.

  * •

Can LLMs provide reasonable explanation to their judgements? Beyond mere
classification, it is imperative to observe whether LLMs can elucidate the
fundamental reasoning behind their determinations. Specifically, can these
models articulate the underlying rationale when predicting human mobility
patterns as anomalous or normal, thereby enhancing the transparency and
trustworthiness of their judgments?

#### Prompt Settings.

To systematically study the research questions above, we design two different
dimensions to create input prompts for the LLMs. Specifically, (1)
With/Without Hint: Given that an anomaly begins at a specific time point in
the data, it is crucial to evaluate the performance of the LLMs whether this
information is provided or not. Notably, for all comparative methods, this
hint is used to divide the data into training and testing sets.; (2) Separate
vs Combine: It would also be interesting to assess whether there is a
significant difference in performance when presenting all the trajectories in
a single prompt versus in separate prompts. This is because placing them all
in one prompt might allow the model to consider interactions between different
trajectories. In Table 1, we present examples to illustrate the details of
prompt.

#### Choices of LLMs.

We opted to utilize OpenAI’s state-of-the-art models, GPT-3.5 and GPT-4, via
their API system, and Claude-2 by Anthropic. Specifically, we use
gpt-3.5-turbo-16k-0613 and gpt-4-0613 for ‘Separate’ prompt, and Claude-2 for
‘Combine’ prompt due to its capability to hold long input prompt up to 100K
input context window size.

  * •

LLMs can effectively detect anomaly behaviors without any indicative
information. We observed that the LLM demonstrates commendable detection
results on both datasets. For the Geolife dataset, Claude-2 surpasses all non-
deep learning methods, achieving performance on par with the deep learning
method. Both GPT-3.5 and GPT-4 also produce results that are comparable to
those of other methods. This might suggest that presenting all mobility
trajectories in a single prompt may lead to better performance than using
separate prompts. As for the PoL dataset, the GPT-3.5 model significantly
outperforms all the methods it was compared against.

  * •

Providing additional indicative information can further enhance the detection
efficacy of LLMs. We observed that by incorporating a ‘hint’ into the LLMs,
detection performance consistently improved across all models when tested on
the Geolife dataset. Notably, Claude-2-with-hint demonstrated a significantly
superior detection rate, surpassing all other comparison methods. On the other
hand, there was a slight dip in performance on the PoL dataset when adding the
hint. This could arguably be attributed to the LLM’s ability to manage longer
input temporal trajectories, as evidenced by the average length of
trajectories being 52.2 for Geolife and 182.0 for PoL.

  * •

LLMs is capable to provide reasonable explanation to their judgements.
Examples of generated explanations alongside predictions can be found in
Appendix B. Notably, we observed that the LLMs are capable of providing cogent
explanations for their prediction results. Such clarity is pivotal for
ensuring transparency in anomaly detection methods.

Geolife Patterns-of-Life Model Top-10 Hits Top-25 Hits* AP score AUC score
Top-10 Hits Top-100 Hits AP score AUC score OMPAD 1 4 0.1665 0.1697 0 0 0.0079
0.4512 MoNav-TT 0 7 0.2849 0.3989 0 0 0.0094 0.4798 TRAOD 4 7 0.1060 0.5498 0
1 0.0030 0.4390 DSVDD 7 15 0.6246 0.7714 1 2 0.0120 0.5398 DAE 5 12 0.4627
0.6234 0 1 0.0089 0.4649 GPT-3.5 5 8 0.4014 0.4979 0 6 0.0365 0.7572
GPT-3.5-with-hint 4 12 0.3741 0.5917 0 2 0.0176 0.6220 GPT-4 3 9 0.2732 0.4417
- - - - GPT-4-with-hint 5 8 0.3181 0.4818 - - - - Claude-2 4 13 0.4756 0.7474
- - - - Claude-2-with-hint 7 16 0.6879 0.8875 - - - -

Table 2: Outlier detection performance for all datasets. The best performance
for AP and AUC scores is highlighted for each dataset. *We report Top-25 Hits
instead of Top-100 for Geolife dataset due to their size constraints on
datasets. (-) denotes the absence of experiments due to the API cost issue.

##  4 Conclusion and Future Works

In this work, we conduct empirical studies to provide insights on the
strengths and limitations of large language models (LLMs) for detecting
anomalous behaviors from mobility data, by comparing LLMs to specialized
anomaly detection methods. Our key findings show that LLMs can achieve
promising anomaly detection performance even without any specific cues about
potential anomalies. Furthermore, providing contextual information about
possible irregularities can enhance the prediction accuracy of LLMs. In
addition, LLMs can provide explanations for their anomaly judgments, thereby
improving model transparency. For future work, we plan to study the
effectiveness of open source LLMs such as Llama-2 models to improve model
transparency. We also aim to address the issue that LLMs have difficulty
processing long mobility trajectories due to the limited context window size.
Moreover, we intend to evaluate our approach on additional mobility datasets.
This work represents an initial exploration of applying LLMs for the important
and promising task of mobility anomaly detection. We hope it will inspire more
research in this direction.

## References

  * [1] Guangji Bai, Ziyang Yu, Zheng Chai, Yue Cheng, and Liang Zhao.  Staleness-alleviated distributed gnn training via online dynamic-embedding prediction.  arXiv preprint arXiv:2308.13466, 2023.
  * [2] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  arXiv preprint arXiv:2204.05862, 2022.
  * [3] Arslan Basharat, Alexei Gritai, and Mubarak Shah.  Learning object motion patterns for anomaly detection and improved object detection.  In 2008 IEEE conference on computer vision and pattern recognition, pages 1–8. IEEE, 2008.
  * [4] Jonathan Bennett.  OpenStreetMap.  Packt Publishing Ltd, 2010.
  * [5] Filip Biljecki, Hugo Ledoux, and Peter Van Oosterom.  Transportation mode-based segmentation and classification of movement trajectories.  International Journal of Geographical Information Science, 27(2):385–407, 2013.
  * [6] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, T. J. Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeff Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  ArXiv, abs/2005.14165, 2020.
  * [7] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
  * [8] Dario Dotti, Mirela Popa, and Stylianos Asteriadis.  A hierarchical autoencoder learning model for path prediction and abnormality detection.  Pattern Recognition Letters, 130:216–224, 2020.
  * [9] Google AI.  BARD: Deepmind’s conversational ai assistant.  https://blog.google/products/search/introducing-bard-google-ai, 2022.  Accessed: .
  * [10] Xiaojie Guo, Shiyu Wang, and Liang Zhao.  Graph neural networks: Graph transformation.  Graph Neural Networks: Foundations, Frontiers, and Applications, pages 251–275, 2022.
  * [11] Joon-Seok Kim, Hyunjee Jin, Hamdi Kavak, Ovi Chris Rouly, Andrew Crooks, Dieter Pfoser, Carola Wenk, and Andreas Züfle.  Location-based social network data generation based on patterns of life.  In 2020 21st IEEE International Conference on Mobile Data Management (MDM), pages 158–167. IEEE, 2020.
  * [12] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa.  Large language models are zero-shot reasoners.  Advances in neural information processing systems, 35:22199–22213, 2022.
  * [13] Jae-Gil Lee, Jiawei Han, and Xiaolei Li.  Trajectory outlier detection: A partition-and-detect framework.  In 2008 IEEE 24th International Conference on Data Engineering, pages 140–149. IEEE, 2008.
  * [14] Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang.  Trajectory clustering: a partition-and-group framework.  In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pages 593–604, 2007.
  * [15] Chen Ling, Xujiang Zhao, Jiaying Lu, Chengyuan Deng, Can Zheng, Junxiang Wang, Tanmoy Chowdhury, Yun Li, Hejie Cui, et al.  Domain specialization as the key to make large language models disruptive: A comprehensive survey.  arXiv preprint arXiv:2305.18703, 2023.
  * [16] Sewon Min, Mike Lewis, Luke Zettlemoyer, and Hannaneh Hajishirzi.  Metaicl: Learning to learn in context.  arXiv preprint arXiv:2110.15943, 2021.
  * [17] Mohamed Mokbel, Sofiane Abbar, and Rade Stanojevic.  Contact tracing: Beyond the apps.  SIGSPATIAL Special, 12(2):15–24, 2020.
  * [18] Mohamed Mokbel, Mahmoud Sakr, Li Xiong, Andreas Züfle, Jussara Almeida, Walid Aref, Gennady Andrienko, Natalia Andrienko, Yang Cao, Sanjay Chawla, et al.  Towards mobility data science (vision paper).  arXiv preprint arXiv:2307.05717, 2023.
  * [19] Mashaal Musleh, Mohamed F Mokbel, and Sofiane Abbar.  Let’s speak trajectories.  In Proceedings of the 30th International Conference on Advances in Geographic Information Systems, pages 1–4, 2022.
  * [20] OpenAI.  Gpt-4 technical report.  ArXiv, abs/2303.08774, 2023.
  * [21] Christine Parent, Stefano Spaccapietra, Chiara Renso, Gennady Andrienko, Natalia Andrienko, Vania Bogorny, Maria Luisa Damiani, Aris Gkoulalas-Divanis, Jose Macedo, Nikos Pelekis, et al.  Semantic trajectories modeling and analysis.  ACM Computing Surveys (CSUR), 45(4):1–32, 2013.
  * [22] Xipeng Qiu, Tianxiang Sun, Yige Xu, Yunfan Shao, Ning Dai, and Xuanjing Huang.  Pre-trained models for natural language processing: A survey.  Science China Technological Sciences, 63(10):1872–1897, 2020.
  * [23] Sirisha Rambhatla, Sepanta Zeighami, Kameron Shahabi, Cyrus Shahabi, and Yan Liu.  Toward accurate spatiotemporal COVID-19 risk scores using high-resolution real-world mobility data.  ACM Trans. Spatial Algorithms Syst., 8(2):1–30, 2022.
  * [24] Lukas Ruff, Robert Vandermeulen, Nico Goernitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Alexander Binder, Emmanuel Müller, and Marius Kloft.  Deep one-class classification.  In International conference on machine learning, pages 4393–4402. PMLR, 2018.
  * [25] Thanos G Stavropoulos, Asterios Papastergiou, Lampros Mpaltadoros, Spiros Nikolopoulos, and Ioannis Kompatsiaris.  Iot wearable sensors and devices in elderly care: A literature review.  Sensors, 20(10):2826, 2020.
  * [26] Kevin Toohey and Matt Duckham.  Trajectory similarity measures.  Sigspatial Special, 7(1):43–50, 2015.
  * [27] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample.  Llama: Open and efficient foundation language models.  ArXiv, abs/2302.13971, 2023.
  * [28] Hugo Touvron, Louis Martin, Kevin R. Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Daniel M. Bikel, Lukas Blecher, Cristian Cantón Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony S. Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel M. Kloumann, A. V. Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, R. Subramanian, Xia Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zhengxu Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom.  Llama 2: Open foundation and fine-tuned chat models.  ArXiv, abs/2307.09288, 2023.
  * [29] Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In NIPS, 2017.
  * [30] Xinglei Wang, Meng Fang, Zichao Zeng, and Tao Cheng.  Where would i go next? large language models as human mobility predictors.  arXiv preprint arXiv:2308.15197, 2023.
  * [31] Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le.  Finetuned language models are zero-shot learners.  arXiv preprint arXiv:2109.01652, 2021.
  * [32] Hao Xue, Bhanu Prakash Voutharoja, and Flora D Salim.  Leveraging language foundation models for human mobility forecasting.  In Proceedings of the 30th International Conference on Advances in Geographic Information Systems, pages 1–9, 2022.
  * [33] Di Yao, Chao Zhang, Zhihua Zhu, Jianhui Huang, and Jingping Bi.  Trajectory clustering via deep representation learning.  In 2017 international joint conference on neural networks (IJCNN), pages 3880–3887. IEEE, 2017.
  * [34] Jianting Zhang.  Smarter outlier detection and deeper understanding of large-scale taxi trip records: a case study of nyc.  In Proceedings of the ACM SIGKDD International Workshop on Urban Computing, pages 157–162, 2012.
  * [35] Zheng Zhang and Liang Zhao.  Representation learning on spatial networks.  Advances in Neural Information Processing Systems, 34:2303–2318, 2021.
  * [36] Zheng Zhang and Liang Zhao.  Unsupervised deep subgraph anomaly detection.  In 2022 IEEE International Conference on Data Mining (ICDM), pages 753–762. IEEE, 2022.
  * [37] Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al.  A survey of large language models.  arXiv preprint arXiv:2303.18223, 2023.
  * [38] Yu Zheng, Yukun Chen, Quannan Li, Xing Xie, and Wei-Ying Ma.  Understanding transportation modes based on gps data for web applications.  ACM Transactions on the Web (TWEB), 4(1):1–36, 2010.
  * [39] Yu Zheng, Xing Xie, Wei-Ying Ma, et al.  Geolife: A collaborative social networking service among user, location and trajectory.  IEEE Data Eng. Bull., 33(2):32–39, 2010.
  * [40] Chong Zhou and Randy C Paffenroth.  Anomaly detection with robust deep autoencoders.  In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 665–674, 2017.
  * [41] Andreas Züfle, Carola Wenk, Dieter Pfoser, Andrew Crooks, Joon-Seok Kim, Hamdi Kavak, Umar Manzoor, and Hyunjee Jin.  Urban life: a model of people and places.  Computational and Mathematical Organization Theory, 29(1):20–51, 2023.

##  Appendix A Comparison Methods

OMPAD [3] is an outlier detection method that analyzes objects’ movement
patterns by counting the types of locations they visit. It identifies abnormal
activities by measuring the deviations in moving trends compared to
established normal patterns.
MoNav-TT [34] is an outlier detection algorithm tailored for urban human
trajectory networks, where it detects outliers by measuring discrepancies in
traffic distances. In particular, a user is identified as an outlier if the
traveled distance significantly deviates from their previous behavior.
TRAOD  [13] is a partition-and-detect framework for trajectory outlier
detection, which partitions a trajectory into a set of line segments, and
then, detects outlying line segments for trajectory outliers.
DSVDD [24] is a deep one-class classification based outlier detection method.
We generalize it to handle the task of semantic trajectory outlier detection
in a most intuitive way. We map the weekly trajectories of each user to a high
dimensional sphere by a deep neural network encoder. Then the distance of
trajectories from the sphere’s surface is quantified as an outlier score.
DAE [40, 8] is a widely-used outlier detection method that leverages a deep
autoencoder. Utilizing an encoder-decoder model architecture, it reconstructs
input trajectories, and the resulting reconstruction error is used as an
outlier indicator, signifying deviations from the normal pattern.

For the data preprocessing, we transform the semantic types of locations into
onehot encodings and treat the spatial coordinates as 3D vectors as the input
to all the comparison methods.

##  Appendix B Example Generations

Model |  Output
---|---
GPT-3.5
No hint |  Based on the given trajectory data, the anomaly score indicates the abnormal behavior of the user’s mobility pattern. The analysis of the trajectory suggests that the user’s movements appear highly irregular and inconsistent. The user tends to visit different types of locations (e.g., Pub, Workplace, Apartment) frequently and travels long distances within short time durations. Additionally, the user exhibits sudden changes in visited locations, such as back-and-forth movements between the same places.Furthermore, the user shows unusual patterns of movement, such as traveling long distances in short periods (e.g., a trip of 250.1 km followed by a trip of 17.4 km) or visiting distant locations in rapid succession (e.g., traveling 90.3 km to a Pub). These patterns deviate significantly from regular human mobility behavior.Considering all these factors, the estimated anomaly score for this user’s behavior is [0.85]. This high score suggests that the user’s mobility trajectory exhibits highly abnormal patterns and deviates significantly from typical human movements.
GPT-4
No hint |  Analyzing the user’s given mobility trajectory, several patterns and potential anomalies are noted. Most noticeably, the user frequents pubs substantially more than any other location type. This is somewhat unusual as typically individuals might frequently visited places like apartments or workplaces. Another significant observation is the abrupt and sporadic changes in distance to the next location - with some movements being in the order of hundreds of kilometers, indicating long-distance travel, and then returning immediately to local sites in a short span of time. The routine visits to the pubs often happen at atypical time slots, including times when a standard pub would potentially not be open or the individual would traditionally be at the workplace. The lack of visit to other essential places like shops or eateries also is a little abnormal. However, the data set does not provide any benchmark for what could be considered ’normal’ behavior, making it challenging to give a precise anomaly score. Therefore, based on the noticeable inconsistencies in the temporal and spatial patterns, I would estimate the anomaly score to be moderately high, but not extreme.Estimated Anomaly Score: [0.65]
Table 3: Example LLMs’ generated answers in geolife dataset without hint.

Model |  Output
---|---
GPT-3.5
With hint |  Analysis and Estimated Anomaly Score: Looking at the given trajectory data, we can observe the following patterns:1. The user frequently visits the Pub and Apartment locations.2. The distances traveled between locations are varying, with some long distances and some short distances. 3. There is a “***<deviate-point>***” denoting a time point where the user’s mobility behavior significantly changes.Based on these patterns, we can analyze the trajectory and estimate the anomaly score. Before the deviate point:- The user visits the Pub and Apartment locations alternately with varying distances.- The trajectory seems consistent and follows a pattern.After the deviate point:- The user visits the Apartment again, but the distance traveled is shorter compared to previous visits. The user then visits the Workplace, which is a new location not seen before in the trajectory.- The user visits the Pub again but travels a longer distance than before.This change in the mobility pattern, the addition of a new location, and the differences in distance traveled suggest a deviation from the user’s past behavior.Based on these observations, the estimated anomaly score for this user’s behavior would be relatively high. Given that larger values indicate more abnormal behavior, the estimated anomaly score can be represented as [0.9].
GPT-4
With hint |  Analyzing the trajectory data before the “***<deviate-point>***”, the individual had a somewhat consistent pattern of movement. On weekends (Saturday), they frequently visited a Pub and their Apartment. Sometimes, they also visited a Restaurant. There was also consistent movement between their Apartment on Wednesdays and Thursdays.However, after the deviate point, there has been a significant change in behaviour. For example, they visit their Apartment on different days (Wednesday and Thursday), with a visit to the Workplace added into the mix. Moreover, they started going to the Pub also on Tuesday, which was not previously observed.The traveled distances also have increased after the deviate point showing that the user has significantly changed their mobility pattern, particularly regarding the type and average distance of trips. Overall, the sudden deviation from their previous behavioral pattern does indeed make the user suspicious, which we are considering as an anomaly. It clearly indicates that the user’s activity after the “deviate-point” is significantly different from their past behaviours. Anomaly score is subjectively judged based on the provided context and may vary based on specific models used, but based on my analysis, I’d put it at around [0.7] as there’s a clear and substantial change in behaviour, but this still has room for more drastic changes, such as the inclusion of entirely new location types or far greater distances. So it does pose a certain level of abnormality, but there’s potential for it to be higher.
Table 4: Example LLMs’ generated answers in geolife dataset with hint.

##  Appendix C Prompt Example

Task
setting |  Prompt to LLM
---|---
Separate |  Task: You are a human mobility trajectory behavior anomaly detector. Given a historical human trajectory information, can you analyse the pattern behind the trajectory and give an anomaly score (from 0 to 1, where larger value indicates more abnormal) of this user’s behavior?
Description of input trajectory data: A temporal sequence of visited place
points, each place is consisted of the visited timestamp and its type of
location. Then the traveled distance to next location is given.
Here is the sequence of trajector: Sat 10:36, Pub, 0.4 km ->Sat 10:57,
Apartment, 4.8 km ->Sat 13:44, Pub, 3.4 km ->Sat 04:45, Apartment, 4.9 km
->Sat 07:39, Pub, 0.6 km ->Sat 09:44, Apartment, 0.8 km ->Sat 10:14,
Apartment, 3.1 km ->Wed 00:30, Apartment, 1.1 km ->Wed 06:08, Apartment, 0.2
km ->Wed 06:44, Apartment, 1.3 km ->Wed 07:27, Apartment, 13.5 km ->Sat 03:39,
Apartment, 0.3 km ->Sat 04:17, Apartment, 2.1 km ->Sat 05:52, Apartment, 3.7
km ->Sat 08:48, Pub, 0.6 km ->Sat 09:36, Restaurant, 11.9 km ->Thu 06:01,
Apartment, 1.5 km ->Wed 08:25, Apartment, 1.3 km ->Thu 01:05, Workplace, 0.6
km ->Sat 01:18, Pub, 10.4 km ->Sat 05:33, Pub.
Give your analysis and present your esimated anomaly score (from 0 to 1, where
larger value indicates more abnormal) inside a pair of square brackets [] :
Separate With Hint |  Task: You are a human mobility trajectory behavior anomaly detector. Given a historical human trajectory information, can you analyse the pattern behind the trajectory and give an anomaly score (from 0 to 1, where larger value indicates more abnormal) of this user’s behavior? Hint: The anomaly users would suddenly change their mobility pattern starting from a time point, which means after a certain time, their mobility behavior would significantly deviate from their past behaviors. We would use "***<deviate-point>***" inside each trajectory to denote the time point as hint.
Description of input trajectory data: A temporal sequence of visited place
points, each place is consisted of the visited timestamp and its type of
location. Then the traveled distance to next location is given.
Here is the sequence of trajector: Sat 10:36, Pub, 0.4 km ->Sat 10:57,
Apartment, 4.8 km ->Sat 13:44, Pub, 3.4 km ->Sat 04:45, Apartment, 4.9 km
->Sat 07:39, Pub, 0.6 km ->Sat 09:44, Apartment, 0.8 km ->Sat 10:14,
Apartment, 3.1 km ->Wed 00:30, Apartment, 1.1 km ->Wed 06:08, Apartment, 0.2
km ->Wed 06:44, Apartment, 1.3 km ->Wed 07:27, Apartment, 13.5 km ->Sat 03:39,
Apartment, 0.3 km ->Sat 04:17, Apartment, 2.1 km ->Sat 05:52, Apartment, 3.7
km ->Sat 08:48, Pub, 0.6 km ->Sat 09:36, Restaurant, 11.9 km ->Thu 06:01,
Apartment ***<deviate-point>*** , 1.5 km ->Wed 08:25, Apartment, 1.3 km ->Thu
01:05, Workplace, 0.6 km ->Sat 01:18, Pub, 10.4 km ->Sat 05:33, Pub.
Give your analysis and present your esimated anomaly score (from 0 to 1, where
larger value indicates more abnormal) inside a pair of square brackets [] :
Table 5: A detailed ‘Separate’ prompt example in geolife dataset.


# Algebraic degrees of quasi-abelian semi-Cayley digraphs

Shixin Wang  School of Mathematics and Statistics, Beijing Jiaotong
University, Beijing 100044, P. R. China  Majid Arezoomand  Department of
Mathematics, University of Larestan, Lar, Iran  Tao Feng Supported by NSFC
under Grant 12271023 School of Mathematics and Statistics, Beijing Jiaotong
University, Beijing 100044, P. R. China

###### Abstract

For a digraph $\Gamma$, if $F$ is the smallest field that contains all roots
of the characteristic polynomial of the adjacency matrix of $\Gamma$, then $F$
is called the splitting field of $\Gamma$. The extension degree of $F$ over
the field of rational numbers $\mathbb{Q}$ is said to be the algebraic degree
of $\Gamma$. A digraph is a semi-Cayley digraph over a group $G$ if it admits
$G$ as a semiregular automorphism group with two orbits of equal size. A semi-
Cayley digraph $\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$ is called quasi-
abelian if each of $T_{11},T_{22},T_{12}$ and $T_{21}$ is a union of some
conjugacy classes of $G$. This paper determines the splitting field and the
algebraic degree of a quasi-abelian semi-Cayley digraph over any finite group
in terms of irreducible characters of groups. This work generalizes the
previous works on algebraic degrees of Cayley graphs over abelian groups and
any group having a subgroup of index 2, and semi-Cayley digraphs over abelian
groups.

Keywords: quasi-abelian semi-Cayley digraph, bi-Cayley graph, algebraic
degree, integral graph.

##  1 Introduction

A graph is integral if all the eigenvalues of its adjacency matrix are
integers. Harary and Schwenk [5] introduced the concept of integral graphs in
1974. Since then, the classification and constructions for integral graphs
have become an important research topic in algebraic graph theory. Integral
graphs are very rare [1] and in general, it is difficult to classify them.

Since the eigenvalues of graphs are all algebraic integers, Mönius, Steuding
and Stumpf [11] proposed the concept of algebraic degrees of graphs in 2018.
Given a graph $\Gamma$, if the field $K$ is the smallest extension of the
field of rational numbers $\mathbb{Q}$ containing all the eigenvalues of
$\Gamma$, then $K$ is said to be the splitting field of $\Gamma$, denoted by
$\mathrm{SF}(\Gamma)$. The algebraic degree of $\Gamma$ is defined as the
extension degree of $\mathrm{SF}(\Gamma)$ over $\mathbb{Q}$, i.e.,
$[\mathrm{SF}(\Gamma):\mathbb{Q}]$, denoted by $\mathrm{deg}(\Gamma)$. A graph
is integral if and only if its algebraic degree is one.

It is shown in [11] that a graph with large diameter must have large algebraic
degree. Mönius [12, 13] determined the splitting field and the algebraic
degree of any circulant graph. Much more work has been done, very recently, on
determining algebraic degrees of mixed Cayley graphs over abelian groups [6],
Cayley hypergraphs [15], Cayley graphs over abelian groups and dihedral groups
[9], and semi-Cayley digraphs over abelian groups [18].

A Cayley digraph $\mathrm{Cay}(G,S)$ over a finite group $G$ with respect to
$S$ is a digraph with vertex set $G$ and edge set $\\{(x,y)\mid x,y\in
G,yx^{-1}\in S\\}$. Semi-Cayley graphs as a generalization of Cayley graphs
were first proposed by de Resmini and Jungnickel [4] and also known as bi-
Cayley graphs (cf. [8]) or 2-Cayley graphs (cf. [2]). A digraph is said to be
a semi-Cayley digraph over a finite group $G$ if it admits $G$ as a
semiregular automorphism group with two orbits of equal size. Specifically,
for four subsets $T_{ij}$, $i,j\in\\{1,2\\}$, of a finite group $G$, a semi-
Cayley digraph $\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$ is a digraph with
vertex set the union of the right part $G_{1}=\\{g_{1}\mid g\in G\\}$ and the
left part $G_{2}=\\{g_{2}\mid g\in G\\}$, and the arc set the union of
$\\{(h_{1},g_{1})\mid gh^{-1}\in T_{11}\\}$, $\\{(h_{2},g_{2})\mid gh^{-1}\in
T_{22}\\}$, $\\{(h_{1},g_{2})\mid gh^{-1}\in T_{12}\\}$ and
$\\{(h_{2},g_{1})\mid gh^{-1}\in T_{21}\\}$. Note that
$\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$ is undirected if and only if
$T_{11}=T_{11}^{-1},T_{22}=T_{22}^{-1}$ and $T_{12}^{-1}=T_{21}$.

This paper is devoted to determining the splitting fields and algebraic
degrees of quasi-abelian semi-Cayley digraphs. A Cayley digraph
$\mathrm{Cay}(G,S)$ is quasi-abelian if $S$ is a conjugate-closed subset of
$G$ (that is, if $s\in S$ then $g^{-1}sg\in S$ for all $g\in G$), or
equivalently a union of conjugacy classes of $G$ (cf. [16]). Similarly, a
semi-Cayley digraph $\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$ is said to be
quasi-abelian if each of $T_{11},T_{22},T_{12}$ and $T_{21}$ is a union of
conjugacy classes of $G$ (cf. [3]). A semi-Cayley digraph over an abelian
group is a quasi-abelian semi-Cayley digraph, but not vice versa.

The paper is organized as follows. Section 2 gives some basic facts on group
representations and field extensions. Section 3.1 provides explicit
expressions for eigenvalues of quasi-abelian semi-Cayley digraphs. Section 3.2
determines the splitting fields and algebraic degrees of quasi-abelian semi-
Cayley digraphs (see Theorem 3.7). Examples of non-abelian and non-Cayley
semi-Cayley graphs are provided in Section 3.3 to illustrate the use of
Theorem 3.7. Concluding remarks are given in Section 4.

##  2 Preliminaries

All groups considered in this paper are finite and we use the multiplicative
notation for the group operation. Sets and multisets will be denoted by curly
braces $\\{~{}\\}$ and square brackets $[~{}]$, respectively. Every union will
be understood as multiset union with multiplicities of elements preserved.

For multisets $X,Y\subseteq G$ and a positive integer $z$, we define the
multisets $X^{z}:=[x^{z}\mid x\in X]$, $XY:=[xy\mid x\in X,y\in Y]$ and
$XY:=\emptyset$ if either $X$ or $Y$ is an empty set. For a positive integer
$k$ and a multiset $X$, $k*X$ is a multiset in which each element of $X$
appears $k$ times. For two multisets $X=\bigcup_{x\in G}a_{x}*\\{x\\}$ and
$Y=\bigcup_{x\in G}b_{x}*\\{x\\}$, where $a_{x}$ and $b_{x}$ are positive
integers for each $x\in G$, we define $X\setminus Y:=\bigcup_{a_{x}>b_{x},x\in
G}(a_{x}-b_{x})*\\{x\\}$ and $Y\setminus X:=\bigcup_{a_{x}<b_{x},x\in
G}(b_{x}-a_{x})*\\{x\\}$. Clearly, $(X\setminus Y)\cap(Y\setminus
X)=\emptyset$.

The reader is referred to [7] for representation theory of finite groups and
properties of characters. Here we recall only a few basic definitions. Let $G$
be a finite group. A representation of $G$ of degree $d$ is a group
homomorphism $\rho:G\rightarrow\mathrm{GL}(V)$ for some vector space $V$ of
dimension $d$, where $\mathrm{GL}(V)$ is the group of all invertible linear
transformations on $V$. Usually, we write $\rho_{g}$ instead of $\rho(g)$ and
$\rho_{g}(v)$ is the value of $\rho_{g}$ on $v\in V$. Two representations
$\varphi:G\rightarrow\mathrm{GL}(V)$ and $\psi:G\rightarrow\mathrm{GL}(W)$ are
said to be equivalent if there exists an isomorphism $\tau:V\rightarrow W$
such that $\psi_{g}=\tau\varphi_{g}\tau^{-1}$ for all $g\in G$. For a
representation $\rho:G\rightarrow\mathrm{GL}(V)$, a subspace $W\leqslant V$ is
said to be $G$-invariant if for all $g\in G$ and $w\in W$, one has
$\rho_{g}(w)\in W$. The representation $\rho$ is said to be irreducible if the
only $G$-invariant subspaces of $V$ are $\\{0\\}$ and $V$ itself. For a
representation $\rho:G\rightarrow\mathrm{GL}(V)$, the character
$\chi_{\rho}:G\rightarrow\mathbb{C}$ of $\rho$ is defined by
$\chi_{\rho}(g)=\mathrm{Tr}(\rho_{g})$, where “$\mathrm{Tr}$” is the trace
function. For a character $\chi$ of $G$ the value $\chi(1)$ is called the
degree of $\chi$ and is denoted by $d_{\chi}$. A character of an irreducible
representation is called an irreducible character.

Let $f$ be an irreducible representation or a character of a group $G$ and $A$
is a multiset of $G$. We define $f(A):=\sum_{a\in A}f(a)$. Denote by
$\mathrm{Irr}(G)$ the set of all irreducible characters of $G$. We use the
convention that $\chi(\emptyset)=0$ for any $\chi\in\mathrm{Irr}(G)$.

######  Lemma 2.1.

Let $\chi\in\mathrm{Irr}(G)$ and $\rho$ be an affording irreducible
representation of $\chi$. If $A$ and $B$ are two conjugate-closed subsets of
$G$, then

$(1)$ $\rho(A)=\frac{\chi(A)}{d_{\chi}}I_{d_{\chi}},$ |  $(2)$ $\rho(AB)=\frac{\chi(A)\chi(B)}{d_{\chi}^{2}}I_{d_{\chi}},$ |  $(3)$ $\chi(AB)=\frac{\chi(A)\chi(B)}{d_{\chi}}.$
---|---|---

###### Proof.

For every $g\in G$, since $\rho$ is a group homomorphism and $gAg^{-1}=A$, we
have

$\displaystyle\rho(g)\rho(A)\rho(g)^{-1}=\rho(g)\Big{(}\sum_{a\in
A}\rho(a)\Big{)}\rho(g^{-1})=\sum_{a\in A}\rho(gag^{-1})=\sum_{a^{\prime}\in
A}\rho(a^{\prime})=\rho(A).$

Then $(1)$ follows immediately from [7, Theorem 2.3(b)]. Since $\rho$ is a
group homomorphism, we have $\rho(A)\rho(B)=\rho(AB)$, and so $(2)$ is a
direct consequence of $(1)$. Furthermore, ${\rm tr}(\rho(AB))=\chi(AB)$, which
proves $(3)$. ∎

For a finite group $G$, the group ring $\mathbb{C}[G]$ is a ring, consisting
of all the formal sums of the free basis $\\{g\mid g\in G\\}$ over the field
of complex numbers $\mathbb{C}$, with the multiplication extending that of $G$
by linearity and distributivity. For any $\sum_{g\in G}a_{g}g\in\mathbb{C}[G]$
and $\chi\in\mathrm{Irr}(G)$, we define $\chi(\sum_{g\in G}a_{g}g):=\sum_{g\in
G}a_{g}\chi(g)$. The following lemma plays a significant role in the proof of
Theorem 3.7 in Section 3.

######  Lemma 2.2.

Let $A$ and $B$ be conjugate-closed multisets of a finite group $G$. Then
$A=B$ if and only if $\chi(A)=\chi(B)$ for every $\chi\in\mathrm{Irr}(G)$.

###### Proof.

For $\chi\in\mathrm{Irr}(G)$, let

$e_{\chi}=\frac{\chi(1)}{|G|}\sum\limits_{x\in
G}\overline{\chi(x)}x\in\mathbb{C}[G].$ (1)

Then by [7, Theorem 4.5], $\\{e_{\chi}\mid\chi\in\mathrm{Irr}(G)\\}$ is a
$\mathbb{C}$-basis of $Z(\mathbb{C}[G])$, the center of $\mathbb{C}[G]$. For
any $\mathcal{Y}\in Z(\mathbb{C}[G])$, we can write uniquely

$\mathcal{Y}=\sum_{\chi\in\mathrm{Irr}(G)}a_{\chi}(\mathcal{Y})e_{\chi},$ (2)

where $a_{\chi}(\mathcal{Y})\in\mathbb{C}$, and so
$\eta(\mathcal{Y})=\sum_{\chi\in\mathrm{Irr}(G)}a_{\chi}(\mathcal{Y})\eta(e_{\chi})$
for any $\eta\in\mathrm{Irr}(G)$. By (1), using the orthogonality relations of
characters, we have

$\eta(e_{\chi})=\frac{\chi(1)}{|G|}\sum\limits_{x\in
G}\overline{\chi(x)}\eta(x)=\left\\{\begin{array}[]{ll}\chi(1),&\eta=\chi\\\
0,&\eta\neq\chi.\end{array}\right.$

Thus
$\eta(\mathcal{Y})=\sum_{\chi\in\mathrm{Irr}(G)}a_{\chi}(\mathcal{Y})\eta(e_{\chi})=a_{\eta}(\mathcal{Y})\chi(1)=a_{\eta}(\mathcal{Y})\eta(1)$
and so $a_{\eta}(\mathcal{Y})=\frac{\eta(\mathcal{Y})}{\eta(1)}$.

If $A=B$, then $\chi(A)=\chi(B)$ for all $\chi\in\mathrm{Irr}(G)$. Conversely,
suppose that $\chi(A)=\chi(B)$ for all $\chi\in\mathrm{Irr}(G)$. Since $A$ and
$B$ are conjugate-closed multisets of $G$, we have $\Sigma_{a\in A}a$ and
$\Sigma_{b\in B}b$ are both in $Z(\mathbb{C}[G])$. It follows that
$a_{\chi}(A)=\frac{\chi(A)}{\chi(1)}=\frac{\chi(B)}{\chi(1)}=a_{\chi}(B)$ for
all $\chi\in\mathrm{Irr}(G)$, which implies $A=B$ by (2). ∎

Let $K$ be a field and $F$ be an extension field of $K$, denoted by $F/K$. The
degree of the field extension $F/K$, written as $[F:K]$, is the dimension of
$F$ as a vector space over $K$. The extension $F/K$ is finite if $[F:K]$ is
finite and is infinite otherwise. By $\mathrm{Gal}(F/K)$, the Galois group of
$F$ over $K$, we mean the set of all automorphisms of $F$ that take every
element of $K$ to itself. If $F/K$ is a finite extension and the set of all
elements fixed by $\mathrm{Gal}(F/K)$ in $F$ is exactly $K$, then $F/K$ is a
Galois extension, and $|\mathrm{Gal}(F/K)|=[F:K]$. If $F/K$ is a finite Galois
extension, then for any intermediate field $L$ such that $K\leqslant
L\leqslant F$, $F/L$ is also a finite Galois extension. The reader is referred
to [14] for Galois theory.

######  Lemma 2.3.

[14, Corollary 7.8] Let $\omega_{m}$ be a primitive $m$-th root of unity and
$\mathbb{Q}(\omega_{m})$ be the cyclotomic field obtained by adjoining
$\omega_{m}$ to $\mathbb{Q}$. Then $\mathbb{Q}(\omega_{m})/\mathbb{Q}$ is a
finite Galois extension. Furthermore, let
$\sigma:\mathbb{Q}(\omega_{m})\rightarrow\mathbb{Q}(\omega_{m})$ be an element
of $\mathrm{Gal}(\mathbb{Q}(\omega_{m})/\mathbb{Q})$. Then
$\sigma(\omega_{m})=\omega_{m}^{t}$ for some $t\in\mathbb{Z}_{m}^{*}$, and

$\displaystyle\eta:\mathrm{Gal}(\mathbb{Q}(\omega_{m})/\mathbb{Q})$
$\displaystyle\longrightarrow\mathbb{Z}_{m}^{*},~{}~{}~{}~{}~{}~{}\sigma\longmapsto
t$

is a group isomorphism, where $\mathbb{Z}_{m}^{*}$ is the multiplicative group
of the ring $\mathbb{Z}/m\mathbb{Z}$.

For a positive integer $n$ and a field $K$, let
$K^{\times}:=K\setminus\\{0\\}$ and $K^{\times n}=\\{k^{n}\mid k\in
K^{\times}\\}$ be the subgroup of $K^{\times}$. The image of element $k\in
K^{\times}$ under the natural epimorphism from $K^{\times}$ onto the quotient
group $K^{\times}/K^{\times n}$ is denoted by $[k]_{K^{\times n}}$. When
$n=2$, $[k]_{K^{\times 2}}$ is simply written as $[k]_{K}$.

######  Lemma 2.4.

[14, Theorem 11.4 and Proposition 11.10] Suppose $K$ is a field containing a
primitive $n$-th root of unity and let

$F=K(\sqrt[n]{a_{1}},\ldots,\sqrt[n]{a_{r}}),$

where $a_{i}\in K$ for $1\leqslant i\leqslant r$. Then $\mathrm{Gal}(F/K)$ is
isomorphic to the subgroup of $K^{\times}/K^{\times n}$ generated by
$[a_{1}]_{K^{\times n}},\ldots,[a_{r}]_{K^{\times n}}$.

##  3 Algebraic degrees of quasi-abelian semi-Cayley digraphs

###  3.1 Eigenvalues of quasi-abelian semi-Cayley digraphs

The algebraic degree of a graph $\Gamma$ is the extension degree
$[F:\mathbb{Q}]$ where $F$ is the smallest field containing all the
eigenvalues of the adjacency matrix of $\Gamma$. Therefore, to determine the
algebraic degree of a quasi-abelian semi-Cayley digraph, we need to know all
eigenvalues of its adjacency matrix. The following lemma can be obtained by
applying [3, Theorem 3.1]. Its proof is similar to that of [3, Corollary 3.2]
which gives eigenvalues of the adjacency matrix of a quasi-abelian semi-Cayley
undirected graph. We omit its proof here.

######  Lemma 3.1.

Let $\Gamma=\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$ be a quasi-abelian
semi-Cayley digraph. Then the eigenvalues of the adjacency matrix of $\Gamma$
are

$\lambda_{\chi}^{\pm}:=\frac{\chi(T_{11})+\chi(T_{22})\pm\sqrt{(\chi(T_{11})-\chi(T_{22}))^{2}+4\chi(T_{12})\chi(T_{21})}}{2d_{\chi}},$

where $\chi\in\mathrm{Irr}(G)$ and the multiplicities of $\lambda_{\chi}^{+}$
and $\lambda_{\chi}^{-}$ are both $d_{\chi}^{2}$.

In this section, we always assume that

$\begin{array}[]{ll}&I_{1}:=T_{11}\cup T_{22},\\\
&I_{2}:=(T_{11}T_{11})\cup(T_{22}T_{22})\cup(4*T_{12}T_{21}),\\\
&I_{3}:=2*T_{11}T_{22}.\end{array}$ (3)

They are all conjugate-closed multisets of $G$. Using $I_{1}$, $I_{2}$ and
$I_{3}$, we rewrite the eigenvalues in Lemma 3.1 as follows.

######  Lemma 3.2.

Let $\Gamma=\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$ be a quasi-abelian
semi-Cayley digraph. Then the eigenvalues of the adjacency matrix of $\Gamma$
are

$\lambda_{\chi}^{\pm}=\frac{\chi(I_{1})\pm\sqrt{d_{\chi}(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2}))}}{2d_{\chi}},$

where $\chi\in\mathrm{Irr}(G)$ and the multiplicities of $\lambda_{\chi}^{+}$
and $\lambda_{\chi}^{-}$ are both $d_{\chi}^{2}$.

###### Proof.

Clearly, $\chi(T_{11})+\chi(T_{22})=\chi(I_{1})$. Using Lemma 2.1(3), we have

$\displaystyle(\chi(T_{11})-\chi(T_{22}))^{2}+4\chi(T_{12})\chi(T_{21})$
$\displaystyle=$
$\displaystyle\chi(T_{11})\chi(T_{11})-2\chi(T_{11})\chi(T_{22})+\chi(T_{22})\chi(T_{22})+4\chi(T_{12})\chi(T_{21})$
$\displaystyle=$ $\displaystyle
d_{\chi}\chi(T_{11}T_{11})-2d_{\chi}\chi(T_{11}T_{22})+d_{\chi}\chi(T_{22}T_{22})+4d_{\chi}\chi(T_{12}T_{21})$
$\displaystyle=$ $\displaystyle
d_{\chi}\chi(I_{2})-d_{\chi}\chi(I_{3})=d_{\chi}(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2})).$

Then the desired conclusion follows immediately from Lemma 3.1. ∎

###  3.2 Determination of algebraic degrees

By Lemma 3.2, the splitting filed of $\Gamma$ is

$\begin{split}\mathrm{SF}(\Gamma)&=\mathbb{Q}(\chi(I_{1})\pm\sqrt{d_{\chi}(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2}))}\mid\chi\in\mathrm{Irr}(G))\\\
&=\mathbb{Q}(\chi(I_{1}),\sqrt{d_{\chi}(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2}))}\mid\chi\in\mathrm{Irr}(G)).\end{split}$
(4)

In order to determine the algebraic degree $[\mathrm{SF}(\Gamma):\mathbb{Q}]$
of $\Gamma$, we let

$K=\mathbb{Q}(\chi(I_{1}),\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2})\mid\chi\in\mathrm{Irr}(G)).$ (5)

It follows from (4) that

$\mathrm{SF}(\Gamma)=K(\sqrt{d_{\chi}(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2}))}\mid\chi\in\mathrm{Irr}(G)),$ (6)

and so

$\mathrm{deg}(\Gamma)=[\mathrm{SF}(\Gamma):\mathbb{Q}]=[\mathrm{SF}(\Gamma):K][K:\mathbb{Q}].$
(7)

######  Lemma 3.3.

Let $M=\langle[d_{\chi}(\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2}))]_{K}\mid\chi\in\mathrm{Irr}(G)\rangle$. Then
$[\mathrm{SF}(\Gamma):K]=|M|$.

###### Proof.

It follows from Lemma 2.4 (take $n=2$) that
$\mathrm{Gal}(\mathrm{SF}(\Gamma)/K)$ is isomorphic to the group $M$. By Lemma
2.3, $\mathrm{SF}(\Gamma)/\mathbb{Q}$ is a finite Galois extension. Since
$\mathbb{Q}\leqslant K\leqslant\mathrm{SF}(\Gamma)$, $\mathrm{SF}(\Gamma)/K$
is also a finite Galois extension. Therefore,
$|\mathrm{Gal}(\mathrm{SF}(\Gamma)/K)|=[\mathrm{SF}(\Gamma):K]=|M|$. ∎

Next we determine $[K:\mathbb{Q}]$. Let $m$ be the exponent of a finite group
$G$, i.e., the least common multiple of the orders of all elements of $G$. Let
$\mathbb{Q}(\omega_{m})$ be the cyclotomic field obtained by adjoining a
primitive $m$-th root of unity $\omega_{m}$ to $\mathbb{Q}$. By (5) we have
$\mathbb{Q}\leqslant K\leqslant\mathbb{Q}(\omega_{m})$, and so
$[K:\mathbb{Q}]=[\mathbb{Q}(\omega_{m}):\mathbb{Q}]/[\mathbb{Q}(\omega_{m}):K]$.
Since
$[\mathbb{Q}(\omega_{m}):\mathbb{Q}]=|\mathrm{Gal}(\mathbb{Q}(\omega_{m})/\mathbb{Q})|=|\mathbb{Z}_{m}^{*}|=\varphi(m)$
by Lemma 2.3, where $\varphi$ is the Euler function, in order to determine
$[K:\mathbb{Q}]$ it remains to determine $[\mathbb{Q}(\omega_{m}):K]$. Since
$\mathbb{Q}(\omega_{m})/K$ is a finite Galois extension,
$[\mathbb{Q}(\omega_{m}):K]=|\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)|$. Thus we
need to analyze the Galois group
$\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)=\\{\sigma:\mathbb{Q}(\omega_{m})\longrightarrow\mathbb{Q}(\omega_{m}){\rm\
is\ a\ field\ isomorphism}\mid\sigma(a)=a{\rm\ for\ any}\ a\in K\\}$.

By (5), $K=\mathbb{Q}(\chi(I_{1}),\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2})\mid\chi\in\mathrm{Irr}(G))$, and so for each
$\sigma\in\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)$ and
$\chi\in\mathrm{Irr}(G)$, we have

$\sigma(\chi(I_{1}))=\chi(I_{1})$ (8)

and

$\sigma(\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2}))=\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus I_{2}).$ (9)

Hence to determine $\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)$, we need to know
when (8) and (9) hold.

Before we go further, we make the following preparations. Let $\rho$ be an
irreducible representation of $G$ affording the character $\chi$. For $g\in
G$, suppose that $\alpha_{1},\ldots,\alpha_{d_{\chi}}$ are all eigenvalues of
$\rho_{g}$. It follows that for any positive integer $z$, the eigenvalues of
$\rho_{g^{z}}$ are $\alpha_{1}^{z},\ldots,\alpha_{d_{\chi}}^{z}$. Since $m$ is
the exponent of $G$, $m$ is divisible by the order of $g$, so $\alpha_{i}$ is
an $m$-th root of unity for each $i=1,\ldots,d_{\chi}$. Note that
$\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)\leqslant\mathrm{Gal}(\mathbb{Q}(\omega_{m})/\mathbb{Q})$
and there exists a group isomorphism from
$\mathrm{Gal}(\mathbb{Q}(\omega_{m})/\mathbb{Q})$ to $\mathbb{Z}_{m}^{*}$ by
Lemma 2.3, i.e.

$\eta:\mathrm{Gal}(\mathbb{Q}(\omega_{m})/\mathbb{Q})\longrightarrow\mathbb{Z}_{m}^{*},~{}~{}~{}~{}~{}\sigma\longmapsto
t,$ (10)

where $t$ satisfies $\sigma(\omega_{m})=\omega_{m}^{t}$. Suppose
$\sigma\in\mathrm{Gal}(\mathbb{Q}(\omega_{m})/\mathbb{Q})$ and
$\eta(\sigma)=t$. Then for $g\in G$,

$\sigma(\chi(g))=\sigma(\mathrm{Tr}(\rho_{g}))=\sigma(\sum\limits_{i=1}^{d_{\chi}}\alpha_{i})=\sum\limits_{i=1}^{d_{\chi}}\sigma(\alpha_{i})=\sum\limits_{i=1}^{d_{\chi}}\alpha_{i}^{t}=\chi(g^{t}).$

Thus for every multiset $X$ of $G$ we have

$\sigma(\chi(X))=\sigma(\sum_{g\in X}\chi(g))=\sum_{g\in
X}\sigma(\chi(g))=\sum_{g\in X}\chi(g^{t})=\chi(X^{t}).$ (11)

Denote by $\eta_{K}\subseteq\mathbb{Z}_{m}^{*}$ the image of
$\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)$ under $\eta$. Now we are ready to
determine when (8) and (9) hold.

######  Proposition 3.4.

$\sigma(\chi(I_{1}))=\chi(I_{1})$ for each
$\sigma\in\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)$ and each
$\chi\in\mathrm{Irr}(G)$ if and only if $I_{1}^{t}=I_{1}$ for all
$t\in\eta_{K}$.

###### Proof.

By (11), for $\sigma\in\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)$ and
$\chi\in\mathrm{Irr}(G)$, $\sigma(\chi(I_{1}))=\chi(I_{1})$ if and only if
$\chi(I_{1}^{t})=\chi(I_{1})$, where $t\in\eta_{K}$ such that
$\eta(\sigma)=t$. Then applying Lemma 2.2, we have
$\chi(I_{1}^{t})=\chi(I_{1})$ for each
$\sigma\in\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)$ and $\chi\in\mathrm{Irr}(G)$
if and only if $I_{1}^{t}=I_{1}$ for all $t\in\eta_{K}$. ∎

######  Proposition 3.5.

$\sigma(\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2}))=\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus I_{2})$ for each
$\sigma\in\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)$ and each
$\chi\in\mathrm{Irr}(G)$ if and only if $I_{2}\setminus I_{3}=(I_{2}\setminus
I_{3})^{t}$ and $I_{3}\setminus I_{2}=(I_{3}\setminus I_{2})^{t}$ for all
$t\in\eta_{K}$.

###### Proof.

By (11), for $\sigma\in\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)$ and
$\chi\in\mathrm{Irr}(G)$, $\sigma(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2}))=\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2})$ if and only if $\chi((I_{2}\setminus
I_{3})^{t})-\chi((I_{3}\setminus I_{2})^{t})=\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2})$ where $t\in\eta_{K}$ such that
$\eta(\sigma)=t$, if and only if $\chi(I_{2}\setminus
I_{3})+\chi((I_{3}\setminus I_{2})^{t})=\chi(I_{3}\setminus
I_{2})+\chi((I_{2}\setminus I_{3})^{t})$, if and only if $\chi(A)=\chi(B)$
where $A=(I_{2}\setminus I_{3})\cup(I_{3}\setminus I_{2})^{t}$ and
$B=(I_{3}\setminus I_{2})\cup(I_{2}\setminus I_{3})^{t}$. By Lemma 2.2,
$\chi(A)=\chi(B)$ for all $\chi\in\mathrm{Irr}(G)$ if and only if $A=B$. Since
$I_{2}\setminus I_{3}$ and $I_{3}\setminus I_{2}$ are disjoint, $A=B$ if and
only if $I_{2}\setminus I_{3}=(I_{2}\setminus I_{3})^{t}$ and $I_{3}\setminus
I_{2}=(I_{3}\setminus I_{2})^{t}$, as desired. ∎

######  Lemma 3.6.

Let $T=\\{t\in\mathbb{Z}_{m}^{*}\mid(I_{1})^{t}=I_{1},(I_{2}\setminus
I_{3})^{t}=I_{2}\setminus I_{3},(I_{3}\setminus I_{2})^{t}=I_{3}\setminus
I_{2}\\}$. Then $\eta_{K}=T$ and $[\mathbb{Q}(\omega_{m}):K]=|T|$. Moreover,
$K=\\{x\in\mathbb{Q}(\omega_{m})\mid\sigma(x)=x\ \text{for all}\
\sigma\in\eta^{-1}(T)\\}$.

###### Proof.

Since $K=\mathbb{Q}(\chi(I_{1}),\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2})\mid\chi\in\mathrm{Irr}(G))$ by (5), it follows from Propositions 3.4
and 3.5 that $\eta_{K}=T$. Since $\eta$ is a group isomorphism,
$|\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)|=|\eta_{K}|=|T|$, which implies
$[\mathbb{Q}(\omega_{m}):K]=|T|$. Note that
$\eta^{-1}(T)=\eta^{-1}(\eta_{K})=\mathrm{Gal}(\mathbb{Q}(\omega_{m})/K)$
keeps every element of $K$ invariant, and hence
$K=\\{x\in\mathbb{Q}(\omega_{m})\mid\sigma(x)=x\ \text{for all}\
\sigma\in\eta^{-1}(T)\\}$. ∎

We are in a position to give our main theorem in this paper.

######  Theorem 3.7.

Let $G$ be a finite group and
$\Gamma=\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$ be a quasi-abelian semi-
Cayley digraph. Let $m$ be the exponent of $G$ and $\omega_{m}$ be a primitive
$m$-th root of unity. Then the splitting field of $\Gamma$ is

$\displaystyle\mathrm{SF}(\Gamma)=$
$\displaystyle\mathbb{Q}(\chi(I_{1}),\sqrt{d_{\chi}(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2}))}\mid\chi\in\mathrm{Irr}(G))$
$\displaystyle=$ $\displaystyle K(\sqrt{d_{\chi}(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2}))}\mid\chi\in\mathrm{Irr}(G)),$

and the algebraic degree of $\Gamma$ is

$\mathrm{deg}(\Gamma)=\frac{\varphi(m)|M|}{|T|},$

where $I_{1},I_{2}$ and $I_{3}$ are defined in (3),
$T=\\{t\in\mathbb{Z}_{m}^{*}\mid(I_{1})^{t}=I_{1},(I_{2}\setminus
I_{3})^{t}=I_{2}\setminus I_{3},(I_{3}\setminus I_{2})^{t}=I_{3}\setminus
I_{2}\\}$, $K=\mathbb{Q}(\chi(I_{1}),\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus
I_{2})\mid\chi\in\mathrm{Irr}(G))=\\{x\in\mathbb{Q}(\omega_{m})\mid\sigma(x)=x\
\text{for all}\ \sigma\in\eta^{-1}(T)\\}$, $\eta$ is defined in (10), and
$M=\langle[d_{\chi}(\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2}))]_{K}\mid\chi\in\mathrm{Irr}(G)\rangle$.

###### Proof.

By (4), (5) and (6), the splitting field of $\Gamma$ is
$\mathbb{Q}(\chi(I_{1}),\sqrt{d_{\chi}(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus
I_{2}))}\mid\chi\in\mathrm{Irr}(G))=K(\sqrt{d_{\chi}(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2}))}\mid\chi\in\mathrm{Irr}(G))$. By (7), the
algebraic degree of $\Gamma$ is

$\mathrm{deg}(\Gamma)=[\mathrm{SF}(\Gamma):\mathbb{Q}]=[\mathrm{SF}(\Gamma):K][K:\mathbb{Q}]=\frac{[\mathrm{SF}(\Gamma):K][\mathbb{Q}(\omega_{m}):\mathbb{Q}]}{[\mathbb{Q}(\omega_{m}):K]}=\frac{|M|\varphi(m)}{|T|},$

where the last equality follows from Lemmas 2.3, 3.3 and 3.6. ∎

The following corollary gives the splitting field and the algebraic degree of
an abelian semi-Cayley digraph.

######  Corollary 3.8.

(abelian semi-Cayley digraph) Let $G$ be a finite abelian group and
$\Gamma=\mathrm{SC}(G,T_{11}$, $T_{22},T_{12},T_{21})$. Let $m$ be the
exponent of $G$ and $\omega_{m}$ be a primitive $m$-th root of unity. Then the
splitting field of $\Gamma$ is

$K(\sqrt{\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2})}\mid\chi\in\mathrm{Irr}(G)),$

and its algebraic degree is

$\mathrm{deg}(\Gamma)=\frac{\varphi(m)|M|}{|T|},$

where $T=\\{t\in\mathbb{Z}_{m}^{*}\mid(I_{1})^{t}=I_{1},(I_{2}\setminus
I_{3})^{t}=I_{2}\setminus I_{3},(I_{3}\setminus I_{2})^{t}=I_{3}\setminus
I_{2}\\}$, $K=\\{x\in\mathbb{Q}(\omega_{m})\mid\sigma(x)=x\ \text{for all}\
\sigma\in\eta^{-1}(T)\\}$ and $M=\langle[\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2})]_{K}\mid\chi\in\mathrm{Irr}(G)\rangle$.

###### Proof.

Since $G$ is a finite abelian group, $d_{\chi}=1$ for all
$\chi\in\mathrm{Irr}(G)$. Then apply Theorem 3.7. ∎

######  Remark 3.9.

The splitting field and the algebraic degree of a semi-Cayley digraph $\Gamma$
over an abelian group $G$ of order $n$ are also given in [18, Theorem $3.5$].
Let $H=\\{h\in\mathbb{Z}_{n}^{*}\mid(I_{1})^{h}=I_{1},(I_{2}\setminus
I_{3})^{h}=I_{2}\setminus I_{3},(I_{3}\setminus I_{2})^{h}=I_{3}\setminus
I_{2}\\}$, $L=\\{x\in\mathbb{Q}(\omega_{n})\mid\sigma(x)=x\ \text{for all}\
\sigma\in\eta^{-1}(H)\\}$ and $M=\langle[\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus I_{2})]_{K}\mid\chi\in\mathrm{Irr}(G)\rangle$. It
is shown in [18, Theorem $3.5$] that the splitting field of $\Gamma$ is
$L(\sqrt{\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2})}\mid\chi\in\mathrm{Irr}(G))$ and its algebraic degree is
$\mathrm{deg}(\Gamma)=\frac{\varphi(n)|M|}{|H|}$. We can apply Corollary 3.8
to obtain [18, Theorem $3.5$] by using the one-to-one mapping $\phi$ from
$\mathbb{Z}_{n}^{*}/H$ to $\mathbb{Z}_{m}^{*}/T$ such that
$\phi(aH)=(a\pmod{m})T$ for $aH\in\mathbb{Z}_{n}^{*}/H$, which implies
$\frac{\varphi(m)}{|T|}=\frac{\varphi(n)}{|H|}$. When the exponent $m$ of $G$
is less than the order $n$ of $G$, especially when $G$ is a $p$-group, it is
easier to apply Corollary 3.8 to count $T$ and $K$ than to apply [18, Theorem
$3.5$] to count $H$ and $L$.

######  Corollary 3.10.

(quasi-abelian Cayley digraph) Let $G$ be a finite group and $m$ be the
exponent of $G$. Let $\Gamma=\mathrm{Cay}(G,S)$ be a quasi-abelian Cayley
digraph. Then the splitting field of $\Gamma$ is

$\mathrm{SF}(\Gamma)=\\{x\in\mathbb{Q}(\omega_{m})\mid\sigma(x)=x\ \text{for
all}\ \sigma\in\eta^{-1}(T)\\}$

and its algebraic degree is

$\mathrm{deg}(\Gamma)=\frac{\varphi(m)}{|T|},$

where $T=\\{t\in\mathbb{Z}_{m}^{*}\mid S^{t}=S\\}$ and $\eta$ is defined in
(10).

###### Proof.

It is clear that $\mathrm{Cay}(G,S)$ and
$\mathrm{SC}(G,S,\emptyset,\emptyset,\emptyset)$ have the same splitting
field, and so have the same algebraic degree. Then $I_{1}=S$, $I_{2}=S^{2}$
and $I_{3}=\emptyset$. By Lemma 2.1(3), $d_{\chi}\chi(S^{2})=(\chi(S))^{2}$.
Thus $K=\mathbb{Q}(\chi(I_{1}),\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2})\mid\chi\in\mathrm{Irr}(G))=\mathbb{Q}(\chi(S)\mid\chi\in\mathrm{Irr}(G))$.
It follows from Theorem 3.7 that the splitting field of $\Gamma$ is
$K(\sqrt{d_{\chi}(\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2}))}\mid\chi\in\mathrm{Irr}(G))=K(\sqrt{(\chi(S))^{2}}\mid\chi\in\mathrm{Irr}(G))=K=\\{x\in\mathbb{Q}(\omega_{m})\mid\sigma(x)=x\
\text{for all}\ \sigma\in\eta^{-1}(T)\\}$,
$M=\langle[(\chi(S))^{2}]_{K}\mid\chi\in\mathrm{Irr}(G)\rangle=\\{[1]_{K}\\}$
and the algebraic degree of $\Gamma$ is
$\frac{\varphi(m)|M|}{|T|}=\frac{\varphi(m)}{|T|}$. ∎

######  Remark 3.11.

Corollary 3.10 is a generalization of [9, Theorem 1] that determines the
splitting field and the algebraic degree of a Cayley digraph over a finite
abelian group.

Let $G$ be a finite group and $S\subseteq G$. $\mathrm{BCay}(G,S)$ is known as
a graph with vertex set $G_{1}\cup G_{2}$ and edge set
$\\{(g_{1},(sg)_{2})\mid g\in G,s\in S\\}$ (cf. [10]). The following corollary
gives the splitting field and the algebraic degree of $\mathrm{BCay}(G,S)$
when $S$ is conjugate-closed.

######  Corollary 3.12.

Let $G$ be a finite group, $m$ be the exponent of $G$, $S$ be a conjugate-
closed subset of $G$ and $\Gamma=\mathrm{BCay}(G,S)$. Then the splitting field
of $\Gamma$ is

$K(|\chi(S)|\mid\chi\in\mathrm{Irr}(G)),$

and the algebraic degree of $\Gamma$ is

$\mathrm{deg}(\Gamma)=\frac{\varphi(m)|M|}{|T|},$

where $T=\\{t\in\mathbb{Z}_{m}^{*}\mid(SS^{-1})^{t}=SS^{-1}\\}$,
$K=\\{x\in\mathbb{Q}(\omega_{m})\mid\sigma(x)=x\ \text{for all}\
\sigma\in\eta^{-1}(T)\\}$ and
$M=\langle[|\chi(S)|^{2}]_{K}\mid\chi\in\mathrm{Irr}(G)\rangle$.

###### Proof.

Clearly $\Gamma=\mathrm{SC}(G,\emptyset,\emptyset,S,S^{-1})$. Then
$I_{1}=I_{3}=\emptyset$ and $I_{2}=4*SS^{-1}$. By Theorem 3.7 and Lemma
2.1(3), the splitting field of $\Gamma$ is
$K(\sqrt{d_{\chi}\chi(I_{2})}\mid\chi\in\mathrm{Irr}(G))=K(\sqrt{d_{\chi}\chi(SS^{-1})}\mid\chi\in\mathrm{Irr}(G))=K(\sqrt{\chi(S)\chi(S^{-1})}\mid\chi\in\mathrm{Irr}(G))=K(|\chi(S)|\mid\chi\in\mathrm{Irr}(G))$,
and the algebraic degree of $\Gamma$ is
$\mathrm{deg}(\Gamma)=\frac{\varphi(m)|M|}{|T|}$. ∎

######  Corollary 3.13.

Let $G$ be a finite group and $m$ be the exponent of $G$. Let
$\Gamma=\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$ be a quasi-abelian semi-
Cayley digraph with $T_{11}=T_{22}$ and $T_{12}=T_{12}^{-1}=T_{21}$. Then the
splitting field of $\Gamma$ is

$\mathrm{SF}(\Gamma)=\mathbb{Q}(\chi(T_{11}),\chi(T_{12})\mid\chi\in\mathrm{Irr}(G))=K(\chi(T_{12})\mid\chi\in\mathrm{Irr}(G))$

and the algebraic degree of $\Gamma$ is

$\mathrm{deg}(\Gamma)=\frac{\varphi(m)|M|}{|T|},$

where $T=\\{t\in\mathbb{Z}_{m}^{*}\mid
T_{11}^{t}=T_{11},(T_{12}T_{12})^{t}=T_{12}T_{12}\\}$,
$K=\\{x\in\mathbb{Q}(\omega_{m})\mid\sigma(x)=x\ \text{for all}\
\sigma\in\eta^{-1}(T)\\}$ and
$M=\langle[(\chi(T_{12}))^{2}]_{K}\mid\chi\in\mathrm{Irr}(G)\rangle$.

###### Proof.

Note that $I_{1}=2*T_{11}$, $I_{2}\setminus I_{3}=4*(T_{12}T_{12}^{-1})$ and
$I_{3}\setminus I_{2}=\emptyset$. We have

$\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2})=4\chi(T_{12}T_{12}^{-1})=\frac{4|\chi(T_{12})|^{2}}{d_{\chi}}=\frac{4\chi(T_{12})^{2}}{d_{\chi}},$

where the second equality follows from Lemma 2.1(3) and the third equality
follows from the fact that $T_{12}=T_{21}^{-1}$. It follows from Theorem 3.7
that the splitting field of $\Gamma$ is
$\mathbb{Q}(\chi(T_{11}),\chi(T_{12})\mid\chi\in\mathrm{Irr}(G))=K(\chi(T_{12})\mid\chi\in\mathrm{Irr}(G))$,
and the algebraic degree of $\Gamma$ is $\frac{\varphi(m)|M|}{|T|}$. ∎

######  Corollary 3.14.

(integral quasi-abelian semi-Cayley digraph) Let $G$ be a finite group and $m$
be the exponent of $G$. A quasi-abelian semi-Cayley digraph
$\Gamma=\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$ is integral if and only if
$T=\mathbb{Z}_{m}^{*}$ and $M=1$, where $T$ and $M$ are given in Theorem 3.7.

###### Proof.

$\Gamma$ is an integral graph if and only if $\mathrm{deg}(\Gamma)=1$, that is
to say $\frac{\varphi(m)}{|T|}|M|=1$ by Theorem 3.7. Since $T$ is a subgroup
of $\mathbb{Z}_{m}^{*}$ and $|\mathbb{Z}_{m}^{*}|=\varphi(m)$,
$\frac{\varphi(m)}{|T|}$ is an integer, so $|\mathbb{Z}_{m}^{*}/T|=1$ and
$|M|=1$. Thus $\Gamma$ is an integral graph if and only if
$T=\mathbb{Z}_{m}^{*}$ and $M=1$. ∎

###  3.3 Examples

In this section we construct some examples to illustrate the use of Theorem
3.7. It is readily checked that Examples 3.1, 3.2 and 3.3 are non-abelian
semi-Cayley graphs which are non-Cayley. For $g\in G$, we use the notation
$g^{G}:=\\{h^{-1}gh\mid h\in G\\}$.

######  Example 3.1.

Let $G=S_{3}$, $T_{11}=T_{12}=T_{21}=(12)^{G}$, $T_{22}=(123)^{G}$ and
$\Gamma=\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$. Then
$I_{1}=S_{3}\setminus\\{1_{G}\\}$, $I_{2}=[17*1_{G},16*(123),16*(132)]$ and
$I_{3}=[4*(13),4*(23),4*(12)]$. So $I_{2}\setminus I_{3}=I_{2}$ and
$I_{3}\setminus I_{2}=I_{3}$. The exponent of $G$ is $m=6$ and
$T=\\{1,5\\}=\mathbb{Z}_{6}^{*}$. The character table of $S_{3}$ is listed in
Table 1.

$g$ | $1_{G}$ | $(12)$ | $(123)$
---|---|---|---
$|g^{G}|$ | $1$ | $3$ | $2$
$\chi_{1}$ | $1$ | $1$ | 1
$\chi_{2}$ | $1$ | $-1$ | 1
$\chi_{3}$ | $2$ | $0$ | $-1$
Table 1: Character table of $S_{3}$

Then

$\chi_{1}(I_{1})=5$, |  $\chi_{1}(I_{2})=49$, |  $\chi_{1}(I_{3})=12$;
---|---|---
$\chi_{2}(I_{1})=1$, |  $\chi_{2}(I_{2})=49$, |  $\chi_{2}(I_{3})=-12$;
$\chi_{3}(I_{1})=-2$, |  $\chi_{3}(I_{2})=2$, |  $\chi_{3}(I_{3})=0$.

Thus $K=\mathbb{Q}(\chi(I_{1}),\chi(I_{2}\setminus I_{3})-\chi(I_{3}\setminus
I_{2})\mid\chi\in\mathrm{Irr}(G))=\mathbb{Q}$, and so by Theorem 3.7, the
splitting field of $\Gamma$ is $K(\sqrt{d_{\chi}(\chi(I_{2}\setminus
I_{3})-\chi(I_{3}\setminus
I_{2}))}\mid\chi\in\mathrm{Irr}(G))=\mathbb{Q}(\sqrt{37},\sqrt{61},\sqrt{4})=\mathbb{Q}(\sqrt{37},\sqrt{61})$.
Since
$M=\langle[37]_{\mathbb{Q}},[61]_{\mathbb{Q}},[4]_{\mathbb{Q}}\rangle=\langle[37]_{\mathbb{Q}},[61]_{\mathbb{Q}}\rangle$,
we have $\deg(\Gamma)=\frac{\varphi(6)|M|}{|T|}=|M|=4$.

######  Example 3.2.

Let $G=\langle a,b\rangle\cong A_{4}$, where $a=(12)(34)$ and $b=(123)$. Let
$T_{11}=T_{22}=b^{G}$, $T_{21}=\\{1_{G}\\}$, $T_{12}=(b^{-1})^{G}$ and
$\Gamma=\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$. Then
$I_{1}=[2*(243),2*(123),2*(134),2*(142)]$,
$I_{2}=[12*(234),12*(124),12*(132),12*(143)]$ and
$I_{3}=[8*(234),8*(124),8*(132),8*(143)]$. So $I_{2}\setminus
I_{3}=[4*(234),4*(124),4*(132),4*(143)]$ and $I_{3}\setminus I_{2}=\emptyset$.
The exponent of $G$ is $m=6$ and $T=\\{1_{G}\\}$. The character table of
$A_{4}$ is listed in Table 2, where $\omega={\sf
exp}(\frac{2\pi\mathrm{i}}{3})=-\frac{1}{2}+\mathrm{i}\frac{\sqrt{3}}{2}$.

$g$ | $1_{G}$ | $(12)(34)$ | $(123)$ | $(132)$
---|---|---|---|---
$|g^{G}|$ | 1 | 3 | 4 | 4
$\chi_{1}$ | $1$ | $1$ | 1 | 1
$\chi_{2}$ | $1$ | $1$ | $\omega$ | $\omega^{2}$
$\chi_{3}$ | $1$ | $1$ | $\omega^{2}$ | $\omega$
$\chi_{4}$ | $3$ | $-1$ | 0 | 0
Table 2: Character table of $A_{4}$

Then

$\chi_{1}(I_{1})=8$, |  $\chi_{1}(I_{2}\setminus I_{3})=16$;
---|---
$\chi_{2}(I_{1})=8\omega$, |  $\chi_{2}(I_{2}\setminus I_{3})=16\omega^{2}$;
$\chi_{3}(I_{1})=8\omega^{2}$, |  $\chi_{3}(I_{2}\setminus I_{3})=16\omega$;
$\chi_{4}(I_{1})=0$, |  $\chi_{4}(I_{2}\setminus I_{3})=0$.

This yields that $K=\mathbb{Q}(\omega)$, $\mathrm{SF}(\Gamma)=K$ and $M=1$.
Hence $\deg(\Gamma)=2$.

######  Example 3.3.

Let $n>1$ be an odd integer and $G=D_{2n}=\langle a,b\mid
a^{n}=b^{2}=(ab)^{2}=1\rangle$. Let $T_{11}=\langle a\rangle\setminus\\{1\\}$,
$T_{22}=b\langle a\rangle$, $T_{12}=T_{21}=\\{1\\}$, and
$\Gamma=\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$. Then
$I_{1}=\\{a^{i},b,ba^{i}\mid 1\leqslant i\leqslant n-1\\}$,
$I_{2}=\\{(2n+3)*1,n*a^{i}\mid 1\leqslant i\leqslant n-1\\}$ and
$I_{3}=\\{2(n-1)*b,2(n-1)*ba^{i}\mid 1\leqslant i\leqslant n-1\\}$. Since
$I_{2}$ and $I_{3}$ are disjoint, $I_{2}\setminus I_{3}=I_{2}$ and
$I_{3}\setminus I_{2}=I_{3}$. The exponent of $G$ is $m=n$ and
$T=\mathbb{Z}_{n}^{*}$. The character table of $G$ is listed in Table 3.

| $a^{k}~{}(0\leqslant k\leqslant n-1)$ | $ba^{k}~{}(0\leqslant k\leqslant n-1)$
---|---|---
$\chi_{1}$ | $1$ | $1$
$\chi_{2}$ | $1$ | $-1$
$\chi_{l}~{}(3\leqslant l\leqslant 2+\frac{n-1}{2})$ | $2\cos(\frac{2(l-2)k\pi}{n})$ | $0$
Table 3: Character table of $D_{2n}$ with odd $n$

Then

$\chi_{1}(I_{1})=2n-1$, |  $\chi_{1}(I_{2})=2n^{2}-2n+5$, |  $\chi_{1}(I_{3})=2n(n-1)$;
---|---|---
$\chi_{2}(I_{1})=-1$, |  $\chi_{2}(I_{2})=2n^{2}-2n+5$, |  $\chi_{2}(I_{3})=-2n(n-1)$,

and for $3\leqslant l\leqslant 2+\frac{n-1}{2}$,

$\chi_{l}(I_{1})=\sum\limits_{k=1}^{n-1}2\cos(\frac{2(l-2)k\pi}{n})=-2$,
---
$\chi_{l}(I_{2})=2(2n+3)+(2n-2)\sum\limits_{k=1}^{n-1}2\cos(\frac{2(l-2)k\pi}{n})=10$,
$\chi_{l}(I_{3})=0$.

This shows that $K=\mathbb{Q}$,
$\mathrm{SF}(\Gamma)=\mathbb{Q}(\sqrt{5},\sqrt{4n^{2}-4n+5},\sqrt{20})=\mathbb{Q}(\sqrt{5},\sqrt{4n^{2}-4n+5})$
and
$M=\langle[5]_{\mathbb{Q}},[4n^{2}-4n+5]_{\mathbb{Q}},[20]_{\mathbb{Q}}\rangle=\langle[5]_{\mathbb{Q}},[4n^{2}-4n+5]_{\mathbb{Q}}\rangle$.
Thus $\mathrm{deg}(\Gamma)=|M|$. Take $n=5$ for example. We have
$\mathrm{SF}(\Gamma)=\mathbb{Q}(\sqrt{5},\sqrt{85})$ and
$\mathrm{deg}(\Gamma)=|M|=|\langle[5]_{\mathbb{Q}},[85]_{\mathbb{Q}}\rangle|=4$.

##  4 Concluding remarks

Focusing on quasi-abelian semi-Cayley digraphs, this paper initializes the
study of determining splitting fields and algebraic degrees of semi-Cayley
digraphs over non-abelian groups (see Theorem 3.7). Corollary 3.14 gives a
sufficient and necessary condition for a quasi-abelian semi-Cayley digraph to
be integral, but classifying all integral quasi-abelian semi-Cayley digraphs
is still a challenging problem. Integral quasi-abelian semi-Cayley graphs were
recently proposed in [17] as a model for quantum spin networks that permit a
quantum phenomenon called perfect state transfer. This led us to study the
algebraic degrees of quasi-abelian semi-Cayley graphs.

It is clear that a subset of a group $G$ is conjugate-closed if and only if
every inner automorphism of $G$ fixes it setwise. So we encourage the reader
to study the following question. Let $S$ be a subset of $G$ which is fixed
setwise by any automorphism of $G$. Determine the splitting field and
algebraic degree of $\mathrm{Cay}(G,S)$. More generally, let $T_{ij}\subseteq
G$, $i,j\in\\{0,1\\}$, each of which is fixd setwise by any automorphism of
$G$. Determine the splitting field and algebraic degree of
$\mathrm{SC}(G,T_{11},T_{22},T_{12},T_{21})$.

## Acknowledgments

Research of this paper was carried out while the second author was visiting
Beijing Jiaotong University. He expresses his sincere thanks to the 111
Project of China (grant number B16002) for financial support and to the School
of Mathematics and Statistics of Beijing Jiaotong University for their kind
hospitality.

## References

  * [1] O. Ahmadi, N. Alon, I.F. Blake and I.E. Shparlinski, Graphs with integral spectrum, Linear Algebra Appl., 430 (2009): 547–552.
  * [2] M. Arezoomand and B.Taeri, On the characteristic polynomial of $n$-Cayley digraphs, Electron. J. Comb., 20 (2013): #P57.
  * [3] M. Arezoomand, A note on the eigenvalues of $n$-Cayley graphs, Mat. Vesn., 72 (2020): 351–357.
  * [4] M.J. de Resmini and D. Jungnickel, Strongly regular semi-Cayley graphs, J. Algebr. Comb., 1 (1992): 171–195.
  * [5] F. Harary and A.J. Schwenk, Which graphs have integral s pectra?, Springer Berlin Heidelberg, Berlin, Heidelberg, (1974): 45–51.
  * [6] X. Huang, L. Lu and K. Mönius, Splitting fields of mixed Cayley graphs over abelian groups, 2022, arXiv:2202.00987.
  * [7] B. Huppert, Character Theory of Finite Groups, Walter de Gruyter, 1998.
  * [8] I. Kovács, A. Malnič, D. Marušič and Š. Miklavič, One-matching bi-Cayley graphs over abelian groups, Eur. J. Comb., 30 (2009): 602–616.
  * [9] L. Lu and K. Mönius, Algebraic degree of Cayley graphs over abelian groups and dihedral groups, J. Algebr. Comb., 57(2023): 585–601.
  * [10] Z. Lu, C. Wang and M. Xu, On semisymmetric cubic graphs of order $6p^{2}$, Sci. China Math., 47 (2004): 1–17.
  * [11] K. Mönius, J. Steuding, P. Stumpf, Which graphs have non-integral spectra? Graphs Comb., 34 (2018): 1507–1518.
  * [12] K. Mönius, The algebraic degree of spectra of circulant graphs, J. Number Theory, 208 (2020): 295–304.
  * [13] K. Mönius, Splitting fields of spectra of circulant graphs, J. Algebra, 594 (2022): 154–169.
  * [14] P. Morandi, Field and Galois Theory, Vol. 167, Graduate Texts in Mathematics, Springer, 1996.
  * [15] N. Sripaisan and Y. Meemark, Algebraic degree of spectra of Cayley hypergraphs, Discrete Appl. Math., 316 (2022): 87–94.
  * [16] J. Wang and M. Xu, Quasi-abelian Cayley graphs and Parsons graphs, Eur. J. Comb., 18 (1997): 597–600.
  * [17] S. Wang, M. Arezoomand and T. Feng, Perfect state transfer on quasi-abelian semi-Cayley graphs, submitted.
  * [18] Y. Wu, J. Yang and L. Feng, Algebraic degrees of 2-Cayley digraphs over abelian groups, Ars Math. Contemp., (2023), available on https://doi.org/10.26493/1855-3974.2896.7e6.