# Quantum Key Distribution using Expectation Values
of Super-classical GHZ States

Hyung S. Choi<EMAIL_ADDRESS>Ye Jin Han  Collin Kessinger  Qiaoren
Wang  Department of Physics, Greenville University, 315 E College Ave,
Greenville, IL 62246

###### Abstract

We propose a new quantum key distribution scheme that is based on the optimum
expectation values of maximally entangled Greenberger-Horne-Zeilinger states.
Our protocol makes use of the degrees of freedom in continuously variable
angles, thereby increasing the security of the key distribution. Outlined are
two protocols that distribute a key from Alice to Bob using the above idea,
followed by an extension that allows for the same key to be shared with
Charlie. We show how this scheme provides for certain detection of any
eavesdropper through absolute violation rather than the probabilistic
violation used in many protocols.

##  I Introduction

###  I.1 Cryptography and Quantum Key Distribution

Current cryptographic schemes have been threatened by the looming development
of quantum computers and potential mathematical breakthroughs in the
understanding of P vs. NP problems. This fundamental realization of
computation has already proposed a method to break RSA encryption using Shor’s
algorithm.shor  With RSA being the most commonly used public encryption
algorithm, creating a new quantum secure encryption is essential. Currently,
the only protocol that is completely quantum and classically secure is the
Vernam cipher, more commonly known as the one-time pad. To use the one-time
pad, a key consisting of random bits of equal length to the message must be
distributed. This key is then XORed with the message and the result is sent
classically to a recipient who possesses the distributed key for decoding. The
used key is then discarded and any further communication requires the
distribution of another distinct, random key. In order to achieve secure
communication, secure key distribution is critical. Quantum Physics enables
sending a key without the use of another key via quantum key distribution
(QKD). In this paper, we propose a new QKD protocol that enables certain
detection of any potential eavesdropper. We make use of three particle
entangled Greenberger-Horne-Zeilinger (GHZ) states that can safely send a key
and quickly detect an eavesdropper by making use of optimum spin or
polarization expectation values. Instead of making use of Bell’s probabilistic
inequality, we make use of a complete violation between the classical and
quantum mechanical case.

###  I.2 BB84 and Ekert91 Protocols

The BB84 protocol is a widely known QKD method that uses a string of
superposed unentangled qubits. In this scheme, Alice measures 4n qubits in
either the X or Z basis randomly. Alice then sends these qubits to Bob, who
performs his own measurements, ignorant of the basis chosen by Alice for any
particular qubit. Bob and Alice can then announce the basis they chose for
each qubit and discard qubits that were measured differently (2n). Alice then
announces the measurement results of half of the remaining bits (n). Bob and
Alice are now able to compare and determine if an eavesdropper was present. In
the end, they share a completely secret key of length n if no eavesdropper was
detected.

It has been shown that maximally entangled Bell States can be used to show
violation between classical and quantum physics. This violation is realized
through probability and requires a sufficient number of pairs to be tested in
order to acquire accurate probabilities. The Ekert91ekert  protocol makes
clever use of this probabilistic violation for QKD. Both Alice and Bob are in
possession of one qubit of n maximally entangled bell state systems. Alice
then takes secret measurements on all qubits using a basis chosen randomly
between $0,\pi/8,\pi/4.$ Bob does the same but between the bases
$0,\pi/8,-\pi/8.$ They then announce which basis they used for each qubit.
They keep the qubits that were measured using the same basis. The remaining
qubits are used to test for Eve. If Eve was present, she would have introduced
local realism, indicated by significant deviation from the theoretical quantum
probability coefficients calculated between the different bases used by Alice
and Bob for a particular pair. If no eavesdropper was present, Alice and Bob
now share a secret key of length n. Note that this scheme provides for
probabilistic detection of Eve.

###  I.3 Quantum Key Distribution Schemes Using Maximally Entangled GHZ States

Mutipartite cryptographic schemes using GHZ and W-states are not novel ideas,
and methods to superdense code with GHZ states have already been proposed.anne
,hao  Cao Hai-Jing and Song He-Shancao  present a theoretical QKD scheme with
four particles based on entanglement swapping. Their protocol users share keys
by conducting bell state measurements and sending results via a classical
channel. Liu et. alliu  demonstrates a multipartite quantum secret sharing
protocol based on a symmetric W-State and requires only a single photon
measurement in order to recover the key from the sender. Joo et. aljoo
proposes a three particle entangled W-state protocol that makes use of local
measurements on particles with different axes.

Xing-Ri Jinjin  et. al presents a protocol for simultaneous quantum secure
direct communication (QSDC) amongst $n$ members using $n$ particles in GHZ
states. The message that the party members want to send out simultaneously is
encoded via unitary operations, and an eavesdropper is detected by measuring
and checking the error rate.

T. Gao presents two different QSDC schemes with GHZ states. In his first
protocol, Gao et. algaoal  presents a deterministic QSDC scheme that uses
entanglement swapping and a three particle GHZ state as a quantum information
channel. Local and predetermined unitary operations are performed on the
particles in order to encode the message. In Gao’sgao  second protocol, the
sender directly encodes their message on a sequence of particles in the GHZ
state and transmits it via quantum teleportation. In both of Gao’s protocols,
the eavesdropper is detected by testing the security of the quantum channel.

Kai Chen & Hoi-Kwang Lokai  presents an exhaustive description and study of a
multi-partite QKD protocol using GHZ and W-States. Their protocol is unique in
that even if the initial states fail to violate the standard Bell
inequalities, their cryptographic scheme still remains secure. Their
multipartite key agreement involves a two-way classical communication that
achieves a secure key distribution for W-states when specific parameters are
met. Whenever the members of the protocol share a generalized W-state, they
achieve a secure conference key agreement. Their scheme functions not only
with GHZ states, but also with CSS states. In the case that Eve imposes as one
of the senders, Kai and Lo provide a depolarizing procedure for the ancilla
bits held by the eavesdropper. Other quantum cryptographic schemes involving
GHZ states are cited in the bibliographyfaisal ,zeng ,hillery ,tittel ,saber
,wang .

Contrary to the the mentioned QKD schemes using GHZ or W-states, our proposed
protocol makes use of GHZ states and optimum expectation values of spins or
retarders at variable angles and does not involve unitary operations on the
entangled particles. The addition of an angle makes it impossible for Eve to
determine the correct measurement, and the moment Eve tampers with the
entangled particles, she will be certainly detected. When the angles are set
within certain parameters, the eavesdropper can be detected via an apparent
and clear violation between a classical and quantum mechanical measurement
instead of Bell’s probabilistic inequality. A similar QKD protocol was
presented by Merminmermin  who used specific angles to produce similar
results.

##  II Super-classical GHZ States

It is generally impossible to classically simulate quantum physics. In very
specific cases, one can achieve a super-classical generalized EPR state,
meaning the expectation value is always equal to $\pm 1$, and it is impossible
to duplicate this result classically. In our scheme, we further expand on
Greenberger, Horne and Zeilinger’sghz  calculation of expected spin values
that lead towards a super-classical case when certain parameters are met.

###  II.1 Expectation value for Spins

Satisfying the condition

$\Upsilon(\theta)=+\ket{\theta}\bra{\theta}-\ket{\theta_{\bot}}\bra{\theta_{\bot}}$

we derive the spin-measurement operator along any polar and azimuthal angle
where $\hat{n}$ is the direction of the measurement of the spin as

$\Upsilon\equiv\vec{\sigma}\cdot\hat{n}=\begin{pmatrix}\cos{\theta}&\sin{\theta}\exp(-i\phi)\\\
\sin{\theta}\exp(i\phi)&-\cos{\theta}\end{pmatrix}$ (1)

The expected spin value of a particle can be found by using the equation

$E(n)=\braket{\psi}{\vec{\sigma}\cdot\hat{n}}{\psi}$

The expectation value of a spin measurement of more than one particle in
different directions is given by

$E(n_{1},n_{2},\dots,n_{x})=\braket{\psi}{\Upsilon_{1}\otimes\Upsilon_{2}\cdots\Upsilon_{x}}{\psi}$

where $x$ is the number of particles and $n$ is the direction in which that
particle is measured. We find the expectation value of a three particle GHZ
state $\ket{\psi}=\frac{1}{\sqrt{2}}\left(\ket{+++}-\ket{---}\right)$ when
$\theta=\frac{\pi}{2}$ is

$E=-\cos(\phi_{1}+\phi_{2}+\phi_{3})$

In general, the expectation value of a three particle GHZ state when
$\theta=\frac{\pi}{2}$ is given by

$E=\pm\cos(\pm\phi_{1}\pm\phi_{2}\pm\phi_{3})$ (2)

If the superposition is added, the cosine is positive and viceversa. For
example, $\frac{1}{\sqrt{2}}\left(\ket{+++}-\ket{---}\right)$ yields an
expectation value of $-\cos(\phi_{1}+\phi_{2}+\phi_{3})$ while
$\frac{1}{\sqrt{2}}\left(\ket{+++}+\ket{---}\right)$ yields
$+\cos(\phi_{1}+\phi_{2}+\phi_{3})$. Similarly, the signs of the left hand
side of the entangled particles determine the sign of the $\phi$’s.
$\frac{1}{\sqrt{2}}\left(\ket{++-}-\ket{--+}\right)$ yields an expected value
of $-\cos(\phi_{1}+\phi_{2}-\phi_{3})$ while
$\frac{1}{\sqrt{2}}\left(\ket{-++}-\ket{+--}\right)$ yields
$-\cos(-\phi_{1}+\phi_{2}+\phi_{3})$. This way one can quickly determine the
expected value for any three particle GHZ state.

When $\pm\phi_{1}\pm\phi_{2}\pm\phi_{3}=0,\pi$ and the spin measurement
expectation value yields $+1$ we can determine with certainty that the
measurement will collapse to $\ket{+++},\ket{+--},\ket{-+-},$ or $\ket{--+}$
with equal probability, as the product of the spins is equal to $+1$.
Consequently, the same can be said when the expectation value is $-1$. In such
case, the wave function will collapse to $\ket{---},\ket{++-},\ket{+-+},$ or
$\ket{-++}$. Within these parameters, Greenberger, Horne and Zeilingerghz
noted that if one knows the spin states of two particles and the expectation
value is $\pm 1$, the third can be predicted with 100% certainty.

###  II.2 Expectation Value of Polarization

The same result can be achieved when measuring the expected polarization value
using retarders. A retarder with its azimuthal angle $\rho=0$ and retardance
$\delta$ can be expressed as

$W=\begin{pmatrix}\exp(-i\frac{\delta}{2})&0\\\
0&\exp(i\frac{\delta}{2})\end{pmatrix}$ (3)

Satisfying the condition

$T(\theta)=+\ket{\theta}\bra{\theta}-\ket{\theta_{\bot}}\bra{\theta_{\bot}}$

the polarization measurement operator along angle $\theta$ is given by:

$T(\theta)=\begin{pmatrix}\cos{2\theta}&\sin{2\theta}\\\
\sin{2\theta}&-\cos{2\theta}\end{pmatrix}$ (4)

The polarization measurement of a particle with retarders can then be found
using

$\Lambda=W^{\dagger}TW=\begin{pmatrix}\cos{2\theta}&\sin{2\theta}\exp(i\delta)\\\
\sin{2\theta}\exp(-i\delta)&-\cos{2\theta}\end{pmatrix}$ (5)

We then calculate the expectation value of the coincident measurement of
entangled particles by computing

$E=\braket{\psi}{\Lambda_{1}\otimes\Lambda_{2}\cdots\Lambda_{i}}{\psi}$

where $i$ is the number of particles. For three entangled particles in a
general GHZ state with $\theta=\frac{\pi}{4}$, we get

$E=\pm\cos(\pm\delta_{1}\pm\delta{2}\pm\delta{3})$ (6)

Just like the spin case, whenever
$\pm\delta_{1}\pm\delta{2}\pm\delta{3}=0,\pi$, we get a super-classical GHZ
state with which one can deduce the third particle’s polarization if the
polarization measurements of the other two particles are given. The plus and
minus signs follow the same pattern as with the spin case. If we have
$\frac{1}{\sqrt{2}}\left(\ket{+-+}-\ket{-+-}\right)$, the expectation value
will be $-\cos(\delta_{1}-\delta_{2}+\delta_{3})$.

##  III Quantum Key Distribution Scheme

Using super-classical GHZ states, we now present two QKD methods. Here, a
measurement of $\ket{+}$ corresponds to the 0 bit and $\ket{-}$ corresponds to
the 1 bit. In our protocol, three parties (Alice, Bob, and Charlie) work
together to securely send a randomly generated key $K$ from Alice to Bob. We
then briefly explain an extension of either protocol that allows the same key
to also be distributed to Charlie. We denote the XOR operation with $\oplus$
and XNOR operation with $\odot$.

###  III.1 Method 1

  1. 1.

Bob prepares entangled particles $a,b,c$ in a specific GHZ state and
determines the formula for calculating the expectation value. He then declares
through a public channel three different angles (retardance values) from which
Alice, Charlie, and Bob can choose from to measure their particle’s spin or
polarization. It is ideal to select three unique angles (retardance values)
that minimize the number of combinations that do not sum to either 0 or $\pi$.

  2. 2.

Bob sends particle $a$ to Alice and $c$ to Charlie. The three participants
then take the joint measurement of their particles using one of three allowed
values randomly. The resulting measurements are labeled A,B,C accordingly.

  3. 3.

Alice and Charlie announce which angles (or retardance values) they chose
through the public channel.

  4. 4.

Bob computes $\pm\cos(\pm\phi_{a}\pm\phi_{b}\pm\phi_{c})$ (using the form that
relates to the GHZ state that he prepared). If the expectation value does not
equal $\pm 1$, Bob tells Alice to discard that qubit through a public channel.

  5. 5.

Alice takes $A\oplus K\equiv D$.

  6. 6.

Both D and C are announced through the public channel.

  7. 7.

Bob takes $D\oplus C\equiv E$.

  8. 8.

Bob takes $E\oplus B\enspace(E\odot B\enspace forE=-1)$. The result is the key
that Alice generated.

  9. 9.

Bob is then able to determine A by taking $K\oplus D$. Bob uses only qubits
from measurements with an expectation value of either $\pm 1$, not both, for
detection of Eve. If the total measurement is not equal to +1 (-1 for E = -1)
then Bob immediately knows that Eve was present.

###  III.2 Method 2

  1. 1.

Bob generates any GHZ state and sends qubits $a$ and $c$ to Alice and Charlie
respectively. The GHZ state can be generated by any party, however, it may be
ideal for Bob to generate the state. We will see later that Bob is the only
party that needs to know which of the eight unique GHZ states has been
generated.

  2. 2.

Alice and Charlie then choose and announce publicly which angle (or retardance
value), $\phi_{a}$ and $\phi_{c}$ respectively, they will use to measure.

  3. 3.

Bob then sets $\phi_{b}$ in such a way as to produce either $\pm 1$ to his
preference. Throughout the process Bob will ensure that the expectation value
is always the same as the original choice.

  4. 4.

All three parties then take the joint-measurement according to their
respective angles (retardance values). The resulting measurements are labeled
A,B,C accordingly.

  5. 5.

Alice then takes $A\oplus K\equiv D$

  6. 6.

D and C are announced publicly.

  7. 7.

Bob then takes $D\oplus C\equiv E$

  8. 8.

Bob then takes $E\oplus B\enspace(E\odot B\enspace$ for $E=-1)$. The result is
the original key that Alice generated.

  9. 9.

Bob is then able to determine A by taking $K\oplus D$. This will allow him to
check for the presence of an eavesdropper. If the total measurement is not
equal to 1 (-1 for E =-1) then Bob immediately knows that Eve was present.

###  III.3 Example of Protocol

Below is a chart containing an example of either protocol. In this example,
four bits are being sent from Alice to Bob. The chart is not laid out in order
of information generated, but rather in order of information used in the
protocol. The measurement values were chosen arbitrarily and do not come from
any real experiment. They do, however, follow the case of an expectation value
of +1 and the absence of an eavesdropper.

Note that an expectation value of +1 indicates that between A, C, and B there
must be either a zero or an even number of “1”s. The result (K) is possessed
by Bob and is the original key which Alice wishes to send.

$KEY\equiv K$ (known by Alice) | 1 | 0 | 1 | 1
---|---|---|---|---
A (known by Alice and determinable by Bob at the end) | 0 | 1 | 1 | 0
$A\oplus K\equiv D$ (public) | 1 | 1 | 0 | 1
C (public) | 0 | 0 | 1 | 0
$D\oplus C\equiv E$ (public, calculated by Bob) | 1 | 1 | 1 | 1
B (known by Bob) | 0 | 1 | 0 | 0
$E\oplus B=K$ (calculated by Bob, used to determine A for Eve detection) | 1 | 0 | 1 | 1

###  III.4 Extension to Include Key Distribution to Charlie

In both of the methods outlined above, Charlie does not receive the key, and
Alice and Bob do not need to trust Charlie. This will be shown in the
following section entitled Detection of Eve. We now briefly outline an
extension of either of the above protocols that allows the same key to be
additionally distributed to Charlie.

All three parties first run either of the two protocols which results in a
shared random key held by both Alice and Bob. The three parties then switch
roles, with Charlie acting as Bob, Bob acting as Alice, and Alice acting as
Charlie. Either protocol is implemented and Bob (acting as Alice) sends the
shared key to Charlie (acting as Bob). Now all three parties share the same
random key.

This does not decrease the security of the protocol in any way. The only
public information shared between the two protocols that could jeopardize the
secrecy of the key is the key XORed with Alice’s (Bob’s for the second
distribution) measurement seen below.

$A_{1}\oplus K=D_{1}$ $A_{2}\oplus K=D_{2}$

Both $D_{1}$ and $D_{2}$ are known publicly while $A_{1}$, $A_{2}$, and $K$
are secret. Initially, this seems to be in violation of the requirements of
the one-time pad. However, since $A_{1}$, $A_{2}$, and $K$ are quantum random,
this extension does not violate the requirements of the one-time pad. Thus,
the intersection between multiple runs of the protocol is secure.

##  IV Detection of Eve

Bob is in possession of the expectation value of the system and all three
measurement results. Since he set the expectation value to either $\pm 1$, the
total result will be that value. If there is no noise in the system, Bob knows
that the total value will not equal the expectation value only if Eve was
present. If Eve is present, she will cause absolute violation 50% of the time.
Realistically, there will be noise in all practical systems, so it is
necessary to determine a noise threshold for any system and take the average
total measurement over several runs. If this threshold is violated, Bob knows
Eve was present. We have shown that our protocol provides for absolute
detection of Eve when accounting for noise in the system.

Let us explore the case in which Eve intercepts the particle intended for
Charlie and carries out all actions normally required of Charlie, which
includes setting and announcing $\phi_{c}$ and announcing the measurement of
particle c: in this case, Eve has access to the information
$\phi_{a},\phi_{c}$, D, and C. This is not enough information to determine the
message. To do so, Eve would need to additionally obtain either A or B. While
A is encoded in D, the information contained is as secure as the one time pad
because both K and A are random. The knowledge of $\phi_{a},\phi_{c}$, and C
is not enough to determine the effect Alice’s measurement had on the key bit.
Eve would know that the key bit was flipped with a probability $\frac{1}{2}$.
Therefore, in the event of Eve imposing as Charlie, our scheme is still as
secure as the one-time pad. It is worth noting that it is not necessary for
Alice and Bob to trust Charlie.

We now discuss security details uniquely pertaining to Method 1. In the
particular case where an eavesdropper taps into Method 1’s protocol and tries
to measure particle $a$ before it reaches Alice, Eve will have to guess
between the three angles for measurement that Bob announced. If Eve were to
choose the same angle as Alice, the entangled particles will immediately
collapse, so even if Alice still measures with the same angle, the observed
value of the three particles will violate the expectation value 50% of the
time. After Bob has received and decoded the bits that Alice has sent, Bob can
use the bits that yielded an expectation value of either $+1\enspace or-1$
(but never both) to see how often the measurement and prediction yield the
same result. If Bob concludes that Eve is present, he can decide to start the
whole process over again. If Bob concludes that Eve has not been tapping in,
Alice, Bob and Charlie will continue the protocol.

##  V Concluding Remarks

The quantum cryptographic scheme we propose is based on the expectation values
of super-classical GHZ states. Contrary to the current quantum cryptography
and key distribution using probabilistic comparison, our methods make use of
the expectation value of spin or polarization, giving us an extra layer of
security and making it impossible for Eve to retrieve the message. By the
violation between classical and quantum case, Bob can immediately know if
there exists an eavesdropper. This method can also expand to a three-party key
distribution without decreasing the security of the scheme in any way. We
present our encryption and decryption algorithm under the assumption that our
particles are sent via a theoretically ideal, noiseless channel. We
hypothesize that experimental realizations of this scheme accounting for noise
will lead to complete detection of Eve.

## References

  * (1) Peter W. Shor. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” SIAM Journal on Computing 26 (5), pp. 1484 (1997)
  * (2) Artur Ekert. “Quantum Cryptography based on Bell’s Theorem” Physical Review Letters 67 (6), pp. 661 (1991).
  * (3) Anne Hillebrand. “Superdense Coding with GHZ and Quantum Key Distribution with W in the ZX-calculus” arXiv:1210.0650v1 [quant-ph].
  * (4) Jiu-Cang hao and Chuan-Feng Li and Guang-Can Guo. “Controlled dense coding using the Greenberger-Horne-Zeilinger state” Phys. Rev. A 63 (5), pp. 054301 (2001).
  * (5) Hai-Jing Cao and He-Shan Song. “Quantum Key Distribution Using Four-Qubit W State” Communications in Theoretical Physics 46 (1), pp.65-68 (2008)
  * (6) Lin-Lin Liu, Chia-Wei1 Tsai, Tzonelih Hwang. “Quantum Secret Sharing Using Symmetric W State.” International Journal of Theoretical Physics 51 (7), pp. 2291-2306 (2012)
  * (7) Jaewoo Joo, Jinhyoung Lee, Jingak Jang, and Young-Jai Park. “Quantum Secure Communication with W States” arXiv: arXiv:quant-ph/0204003
  * (8) Xing-Ri Jin, Xin Ji, Ying-Qiao Zhang, Shou Zhang, Suc-Kyoung Hong, Kyu-Hwang Yeon, and Chung-In Um. “Three-party quantum secure direct communication based on Greenberger-Horne-Zeilinger states” Physics Letters A 354 (1–2), pp. 67 (2006)
  * (9) T Gao, F L Yan, and Z X Wang. “Deterministic secure direct communication using GHZ states and swapping quantum entanglement” Journal of Physics A: Mathematical and General 38 (25), pp. 5761–5770 (2005)
  * (10) T Gao. “Controlled and Secure Direct Communication Using GHZ State and Teleportation” Z. Naturforsch 59 (9), pp. 597–601 (2004)
  * (11) Kai Chen and Hoi-Kwong Lo. “Multi-partite quantum cryptographic protocols with noisy GHZ states” Quantum Information & Computation 7 (8) pp. 689-715 (2007)
  * (12) Faisal A. A. El-Orany, Wahiddin M. R. B., Mustafa Afanddi Mat Nor, Norziana Jamil, Iskandar Bahari. “Quantum key distribution in terms of the Greenberger-Horne-Zeilinger state: Multi-key generation” Laser Physics 20 (5) pp. pp 1210–1214 (2010)
  * (13) Guihua Zeng. “Quantum key distribution based on Greenberger-Horne-Zeilinger state” arXiv:quant-ph/0001044
  * (14) Mark Hillery, Vladimír Bužek, and André Berthiaume. “Quantum secret sharing” Phys. Rev. 59 (3) pp. 1829 (1999)
  * (15) W. Tittel, H. Zbinden, and N. Gisin. “Experimental demonstration of quantum secret sharing” Phys. Rev. 63 (4) pp. 040305 (2001)
  * (16) Saber Bagherinezhad and Vahid Karimipour. “Quantum secret sharing based on reusable Greenberger-Horne-Zeilinger states as secure carriers” Phys. Rev. 67 (4) pp. 044302 (2003)
  * (17) Jian Wang,Quan Zhang, Chao-jing Tang. “Multiparty controlled quantum secure direct communication using Greenberger–Horne–Zeilinger state” Optics Communication 266 (2) pp. 732-737 (2006)
  * (18) Charles H. Bennet and Gilles Brassard. “Quantum cryptography: Public key distribution and coin tossing” Proceedings of IEEE International Conference on Computers, Systems and Signal Processing Bangalore, India, (IEEE, New York), pp. 175 (1984)
  * (19) Bennet, G. Brassard and N. Mermin. ”Quantum Cryptography without Bell’s theorem.” Physical review Letters 68 (5), pp. 557-559 (1992).
  * (20) Daniel M. Greenberger, Michael A. Horne, Anton Zeilinger. “Going Beyond Bell’s Theorem” arXiv:0712.0921v1


# A switching method for constructing
cospectral gain graphs

Aida Abiad<EMAIL_ADDRESS>Department of Mathematics and Computer
Science, Eindhoven University of Technology, The NetherlandsDepartment of
Mathematics: Analysis, Logic and Discrete Mathematics, Ghent University,
BelgiumDepartment of Mathematics and Data Science, Vrije Universiteit Brussel,
Belgium Francesco Belardo<EMAIL_ADDRESS>Department of Mathematics and
Applications R. Caccioppoli, University of Naples Federico II, Italy Antonina
P. Khramova<EMAIL_ADDRESS>Department of Mathematics and Computer Science,
Eindhoven University of Technology, The Netherlands

###### Abstract

A gain graph over a group $G$, also referred to as $G$-gain graph, is a graph
where an element of a group $G$, called gain, is assigned to each oriented
edge, in such a way that the inverse element is associated with the opposite
orientation. Gain graphs can be regarded as a generalization of signed graphs,
among others. In this work, we show a new switching method to construct
cospectral gain graphs. Some previous methods known for graph cospectrality
follow as a corollary of our results.

##  1 Introduction

Gain graphs, which can be regarded as a generalization of signed graphs [7]
where the group is $\\{-1,1\\}$, have been extensively studied, see the survey
paper [19]. Gain graphs can be also considered as particular cases of biased
graphs [18] and are related to voltage graphs [11]. Among the key notions
concerning signed and gain graphs, there are switching equivalence and
balance, see for instance [12, 18].

The spectrum of complex unit gain graphs and signed graphs with respect to the
identical representation, both of which are special cases of gain graphs and
the more general $G$-spectrum, has been considered in the literature, see
[19]. Reff [14] introduced complex unit gain graphs and investigated their
spectral properties by extending some fundamental results from spectral graph
theory. For signed graphs, characterizations of some families have been done
with respect to the identical representation, such as [1, 2, 6]. Other cases
related to gain graphs have been considered, including signed directed graphs
[5] and quaternion unit gain graphs [16]. For a general group $G$, it has been
shown that any $G$-gain graph with a cycle as its underlying graph is
determined by its $G$-spectrum [9].

Less is known regarding cospectrality of gain graphs. The well-known switching
method by Godsil and McKay [10] (GM-switching), and the more recent switching
by Wang, Qiu and Hu [15, 13] (WQH-switching), are operations on graphs that do
not change the spectrum of the adjacency matrix. The GM-switching has been
extended to signed graphs [3] and complex unit graphs [4], and more recently,
also to gain graphs over an arbitrary group [8]. The WQH-switching has also
been extended, in its simpler form, to signed graphs [3] and complex unit
graphs [4] under the name Modified Godsil-McKay switching. In this paper we
show that both results from [3, 4] hold in a more general form. In particular,
we present a new method to construct $G$-gain graphs over an arbitrary group
$G$ that are cospectral with respect to the $G$-spectrum, which is independent
of the choice of the particular representation of $G$. We will also
investigate how this new switching behaves when considering a particular
representation of $G$. Our results provide new insights into the spectral
theory of gain graphs with respect to $G$-cospectrality, which to the best of
our knowledge, has only been investigated by Cavaleri, Donno and Spessato [9,
8].

##  2 Preliminaries

We use the notation and the definitions from [8, Section 2].

For an abstract group $G$, its neutral element is denoted by $1_{G}$, except
for when $1_{G}$ coincides with $1$ of the field of complex numbers
${\mathbb{C}}$, in which case the index $G$ is omitted.

Let ${\mathbb{T}}$ denote the _group of complex units_ , or the group of
elements $\\{z\in{\mathbb{C}}:|z|=1\\}$. The group ${\mathbb{T}}_{n}$ is a
group of $n$-th roots of $1\in{\mathbb{C}}$, so ${\mathbb{T}}_{n}=\\{z\in
C:z^{n}=1\\}$. For example, ${\mathbb{T}}_{2}=\\{-1,1\\}$, or
${\mathbb{T}}_{4}=\\{i,-1,-i,1\\}$.

$M_{n,m}(F)$ denotes a set of matrices of size $n\times m$ with entries in
$F$, typically $F\in\\{{\mathbb{C}},{\mathbb{C}}G\\}$. We assume
$M_{n}(F):=M_{n,n}(F)$. Throughout the paper, the identity matrix of size $n$
is denoted by $I_{M_{n}(F)}$, while $J_{M_{n}(F)}$ is a matrix in $M_{n}(F)$
such that all its entries are $1_{G}$ in case $F={\mathbb{C}}G$ or $1$ in case
$F={\mathbb{C}}$.

A _gain graph_ over a group $G$, also referred to as _$G$ -gain graph_, is a
pair $(\Gamma,\psi)$, where $\Gamma=(V,A)$ is an underlying directed graph
such that any arc $(u,w)\in A$ has a reverse $(w,u)\in A$, and $\psi:A\to G$
is a gain function such that for any arc $(u,w)\in A$ we have
$\psi(w,u)=\psi(u,v)^{-1}$. In particular, a ${\mathbb{T}}_{2}$-gain graph is
a graph with each arc labelled by $1$ or $-1$ (or, alternatively, a sign $+$
or $-$), which is also called a _sign graph_. The concept of gain graphs has
been first introduced by Zaslavsky [18]. For a regularly updated bibliography
on signed and gain graphs we refer to [19].

For a $G$-gain graph $(\Gamma,\psi)$ on $n$ vertices
$V=\\{v_{1},v_{2},\dots,v_{n}\\}$ we define its _adjacency matrix_
$A_{(\Gamma,\psi)}$ with entries

$\left(A_{(\Gamma,\psi)}\right)_{i,j}=\begin{cases}\psi(v_{i},v_{j}),&v_{i}\sim
v_{j};\\\ 0,&\text{otherwise.}\end{cases}$

This way, $A_{(\Gamma,\psi)}\in M_{n}({\mathbb{C}}G)$. It follows from the
definition that $A^{*}_{(\Gamma,\psi)}=A_{(\Gamma,\psi)}$.

Similar to how ordinary graphs are usually considered up to isomorphism, gain
graphs are typically considered up to switching isomorphism [17]. Two gain
functions $\psi_{1}$ and $\psi_{2}$ on the same underlying graph
$\Gamma=(V,A)$ are _switching equivalent_ if there exists a function $f:V\to
G$ such that for any pair of adjacent vertices $v,w$ we have

$\psi_{2}(v,w)=f(v)^{-1}\psi_{1}(v,w)f(w).$

Two gain graphs $(\Gamma_{1},\psi_{1})$ and $(\Gamma_{2},\psi_{2})$ with
vertex sets $V_{1}$ and $V_{2}$ respectively are then _switching isomorphic_
if there exists a graph isomorphism $\phi:V_{1}\to V_{2}$ and the gain
function $\psi_{1}$ is switching equivalent to $\psi_{2}\circ\phi$ defined by
$(\psi_{2}\circ\phi)(v,w)=\psi_{2}(\phi(v),\phi(w))$ for any arc $(v,w)$ in
$\Gamma_{1}$.

It is known that the switching equivalence relation can be expressed in terms
of adjacency matrices of the gain graphs on $n$ vertices. Namely, $\psi_{1}$
and $\psi_{2}$ are switching equivalent if and only if there exists a diagonal
matrix $F\in M_{n}({\mathbb{C}}G)$ such that
$A_{(\Gamma,\psi_{2})}=F^{*}A_{(\Gamma,\psi_{1})}F$ [7, Theorem 4.1]. It
follows that the gain graphs $(\Gamma_{1},\psi_{1})$ and
$(\Gamma_{2},\psi_{2})$ are switching isomorphic if and only if there exists a
diagonal matrix $F\in M_{n}({\mathbb{C}}G)$ with $F_{i,i}\in G$ for
$i\in\\{1,\dots,n\\}$ and a permutation matrix $P\in M_{n}({\mathbb{C}}G)$
with entries $0$ and $1_{G}$ such that (see [8, Remark 2.4])

$A_{(\Gamma_{2},\psi_{2})}=(PF)^{*}A_{(\Gamma_{1},\psi_{1})}(PF).$

In case when $G\subseteq{\mathbb{C}}$, it is natural to define two $G$-gain
graphs to be cospectral if the multisets of eigenvalues of their adjacency
matrices (both in $M_{n}({\mathbb{C}})$) coincide since the characteristic
polynomial and the eigenvalues of a complex-valued matrix are well understood.
This is the definition used in [4, 14] where ${\mathbb{T}}_{n}$-gain graphs
were considered. In a general case when $G$ is not necessarily a group of
complex numbers, we define $G$-cospectrality through the equality of the
sequences of trace powers (the spectral moments) of the two adjacency matrices
up to conjugacy.

To be more precise, let $Tr:M_{n}({\mathbb{C}}G)\to{\mathbb{C}}G$ be a
function that maps matrix $A$ to $\sum_{i=1}^{n}A_{i,i}$. Also, let $[g]$ be a
conjugacy class of $g\in G$ and let ${\mathbb{C}}_{Class}[G]$ be a set of
finitely supported _class functions_ , _i.e._ functions $f:G\to{\mathbb{C}}$
such that $f(g_{1})=f(g_{2})$ whenever $g_{1},g_{2}$ are in the same conjugacy
class $[g]$. We consider a natural map
$\mu:{\mathbb{C}}G\to{\mathbb{C}}_{Class}[G]$ defined by

$\mu\left(\sum\limits_{x\in G}a_{x}x\right)(g)=\sum\limits_{x\in[g]}a_{x}.$

Then two matrices $A,B\in M_{n}({\mathbb{C}}G)$ are _$G$ -cospectral_ if
$\mu(Tr(A^{h}))=\mu(Tr(B^{h}))$ for any positive integer $h$, and two $G$-gain
graphs $(\Gamma_{1},\psi_{1})$ and $(\Gamma_{2},\psi_{2})$ are _$G$
-cospectral_ if their adjacency matrices are $G$-cospectral.

Note that, similarly to ordinary graphs, for a gain graph $(\Gamma,\psi)$ with
vertex set $V=\\{v_{1},v_{2},\dots,v_{n}\\}$ and a positive integer $h$ the
entry $(A_{(\Gamma,\psi)}^{h})_{i,j}$ corresponds to the sum of gains of all
walks of length $h$ from $v_{i}$ to $v_{j}$ [7, Lemma 4.1]. As such, the
definition of $G$-cospectrality is a generalization of the cospectrality
notion of gain graphs in the case of complex-valued adjacency matrices.

An instrumental tool in asserting $G$-cospectrality of gain graphs constructed
in Section 3 is the following lemma.

######  Lemma 1.

[8, Lemma 2.6] Let $(\Gamma_{1},\psi_{1})$ and $(\Gamma_{2},\psi_{2})$ be two
$G$-gain graphs with adjacency matrices $A_{1},A_{2}\in M_{n}({\mathbb{C}}G)$,
respectively. Let $Q,R\in M_{n}({\mathbb{C}}G)$ be such that every entry of
$R$ is a complex multiple of $1_{G}$ and $QR=RQ=I_{M_{n}({\mathbb{C}}G)}$. If
$A_{2}=QA_{1}R$ then $(\Gamma_{1},\psi_{1})$ and $(\Gamma_{2},\psi_{2})$ are
$G$-cospectral.

A _representation_ of a group $G$ of degree $k$ is a group homomorphism
$\pi:G\to GL_{k}({\mathbb{C}})$, where $GL_{k}({\mathbb{C}})$ is a set of all
invertible matrices in $M_{k}({\mathbb{C}})$. An easy example is for a
symmetric group on $k$ elements $S_{k}$. A homomorphism $\pi:S_{k}\to
GL_{k}({\mathbb{C}})$ that maps a permutation in $S_{k}$ to a respective
permutation matrix of size $k$ is a representation. Moreover, it is a _unitary
representation_ , _i.e._ a representation such that $\pi(g)\in
U_{k}({\mathbb{C}})$ for any $g\in G$, where $U_{k}({\mathbb{C}})=\\{M\in
GL_{k}({\mathbb{C}}):M^{-1}=M^{*}\\}$ is a set of unitary matrices of size $k$
over ${\mathbb{C}}$. It is a well-known fact that any finite group $G$ can be
isomorphically embedded into a symmetric group $S_{|}G|$, so a unitary
representation always exists for any finite group. Another example is a
_trivial representation_ $\pi_{0}:G\to C$ that maps any $g\in G$ to $1$ which
is also unitary. In case $G\subseteq{\mathbb{C}}$ one can also consider an
_identical representation_ $\pi_{id}:G\to GL_{1}(C)$ such that $\pi_{id}(g)=g$
for any $g\in G$.

Along with a group homomorphism $\pi:G\to GL_{k}({\mathbb{C}})$, $\pi$ will
also sometimes denote its natural linear extension to ${\mathbb{C}}G$, which
is an algebra homomorphism. Namely,

$\displaystyle\pi:{\mathbb{C}}G$ $\displaystyle\to M_{k}({\mathbb{C}})\text{
s.t.}$ $\displaystyle\sum\limits_{g\in G}a_{g}g$
$\displaystyle\mapsto\sum\limits_{g\in G}a_{g}\pi(g).$

This can be even further extended to $\pi:M_{n,m}({\mathbb{C}}G)\to
M_{nk,mk}({\mathbb{C}})$, where $A\in M_{n,m}({\mathbb{C}}G)$ is mapped to a
matrix $\pi(A)$ obtained by replacing each entry $A_{i,j}\in{\mathbb{C}}G$
with a matrix $\pi(A_{i,j})\in M_{k}({\mathbb{C}})$.

Let $(\Gamma,\psi)$ be a $G$-gain graph, and let $\pi$ be a unitary
representation of $G$. We say $\pi(A_{(\Gamma,\psi)})$ is the _represented
adjacency matrix_ of $(\Gamma,\psi)$ with respect to $\pi$. According to [7,
Proposition 3.4], $\pi(A_{(\Gamma,\psi)})$ is Hermitian since $\pi$ is
unitary, and its (real) spectrum is called the _$\pi$ -spectrum_ of
$(\Gamma,\psi)$. Finally, two $G$-gain graphs $(\Gamma_{1},\psi_{1})$ and
$(\Gamma_{2},\psi_{2})$ are _$\pi$ -cospectral_ if they have the same
$\pi$-spectrum.

It follows from [9, Theorem 4.14] that, for a finite group $G$, two $G$-gain
graphs $(\Gamma_{1},\psi_{1})$ and $(\Gamma_{2},\psi_{2})$ are $G$-cospectral
if any only if they are $\pi$-cospectral for every unitary representation
$\pi$ of $G$. This way, $G$-cospectrality is a more general notion than
$\pi$-cospectrality.

##  3 A switching to construct $G$-cospectral gain graphs

The main goal of this section is to show a new method to obtain pairs of
$G$-cospectral gain graphs. We are inspired by the Godsil-McKay switching
[10], the Wang-Qiu-Hu switching [15, 13] and its generalizations [3, 4].

Let $(\Gamma,\psi)$ be a $G$-gain graph on $n$ vertices, and suppose that

$\alpha=\\{C_{0},C_{1},C_{2},\dots,C_{2k-1},C_{2k}\\}$

is a partition of the vertex set of $V_{\Gamma}$. With respect to $\alpha$ for
every vertex $v$, we define

$\Psi_{i}(v):=\sum\limits_{w\in C_{i},w\sim v}\psi(v,w).$

######  Definition 2.

A partition $\alpha$ is a _$G$ -WQH partition_ if the following conditions
hold:

  * •

$|C_{0}|=n_{0}$ and $|C_{i}|=|C_{i+1}|=n_{i}$ for any odd $i<2k$;

  * •

for $i,j\in\\{1,\dots,2k\\}$ and $v,v^{\prime}\in C_{i}$ we have
$\Psi_{j}(v)=\Psi_{j}(v^{\prime})$;

  * •

for odd $i,j<2k$ and $v\in C_{i}$, $v^{\prime}\in C_{i+1}$ we have
$\Psi_{j}(v)=\Psi_{j+1}(v^{\prime})$ and $\Psi_{j+1}(v)=\Psi_{j}(v^{\prime})$;

  * •

for every $v\in C_{0}$ and an odd $i<2k$ we have either

    1. (a)

$\Psi_{i}(v)=\Psi_{i+1}(v)$, or

    2. (b)

$\Psi_{i}(v)=|C_{i}|g_{1}$ and $\Psi_{i+1}(v)=|C_{i+1}|g_{2}$ for some
distinct $g_{1},g_{2}\in G\cup\\{0\\}\subset{\mathbb{C}}G$.

Alternatively, in a $G$-WQH partition, the total gain over all edges from
$v\in C_{i}$ to vertices in $C_{j}$ does not depend on the choice of $v$.
Additionally, for odd $i,j<2k$ the pairs of subsets $C_{i}\cup C_{i+1}$ and
$C_{j}\cup C_{j+1}$ are subject to the following relation: the total gain over
all edges from $v\in C_{i}$ to vertices in $C_{j}$ ($C_{j+1}$) must be the
same as the total gain over all edges from $v^{\prime}\in C_{i+1}$ to vertices
in $C_{j+1}$ ($C_{j}$). Moreover, for a vertex $v\in C_{0}$ and an odd $i<2k$,
either the total gain summed over all edges to $C_{i}$ is the same as the
total gain summed over all edges to $C_{i+1}$, or such $v$ must be adjacent to
all vertices of $C_{i}$ with the same gain $g_{1}$ and to all vertices of
$C_{i+1}$ with the same gain $g_{2}$, where either gain may be zero, implying
non-adjacency. The requirement for $g_{1}$ and $g_{2}$ to be distinct is
stated to prevent overlap between the two cases, although throughout the
following definitions and proofs no conflict arises if $g_{1}=g_{2}$.

######  Example 3.

Let $(\Gamma,\psi)$ be a ${\mathbb{T}}_{4}$-gain graph on $13$ vertices
$v_{0},v_{1},\dots,v_{12}$ with adjacency matrix:

$A_{(\Gamma,\psi)}=\left(\begin{tabular}[]{c||ccc|ccc||ccc|ccc}$0$&$1$&$1$&$1$&$0$&$0$&$0$&$1$&$0$&$0$&$1$&$0$&$0$\\\
\hline\cr\hline\cr$1$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$\\\
$1$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$\\\
$1$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$\\\
\hline\cr$0$&$0$&$0$&$0$&$0$&$i$&$-i$&$0$&$0$&$0$&$0$&$0$&$0$\\\
$0$&$0$&$0$&$0$&$-i$&$0$&$i$&$0$&$0$&$0$&$0$&$0$&$0$\\\
$0$&$0$&$0$&$0$&$i$&$-i$&$0$&$0$&$0$&$0$&$0$&$0$&$0$\\\
\hline\cr\hline\cr$1$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$\\\
$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$\\\
$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$\\\
\hline\cr$1$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$i$&$-i$\\\
$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$-i$&$0$&$i$\\\
$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$i$&$-i$&$0$\\\ \end{tabular}\right).$

Then the partition $\alpha$ into subsets

$\displaystyle
C_{0}=\\{v_{0}\\},\;C_{1}=\\{v_{1},v_{2},v_{3}\\},\;C_{2}=\\{v_{4},v_{5},v_{6}\\},$
$\displaystyle
C_{3}=\\{v_{7},v_{8},v_{9}\\},\;C_{4}=\\{v_{10},v_{11},v_{12}\\}$

is a $G$-WQH partition. Indeed, we have $|C_{1}|=|C_{2}|$ and
$|C_{3}|=|C_{4}|$. Moreover, it is easily verified that for any
$i,j\in\\{1,2,3,4\\}$ and any vertex $w_{i}\in C_{i}$ we have
$\Psi_{j}(w_{i})=0$, so the second and the third conditions in Definition 2
hold up. Finally, for $v_{0}\in C_{0}$ and the subsets $C_{3}$ and $C_{4}$ we
have $\Psi_{3}(v_{0})=\Psi_{4}(v_{0})=1$, which satisfies $(a)$ of the fourth
condition, and for the subsets $C_{1}$ and $C_{2}$ we have
$\Psi_{1}(v_{0})=3=3\cdot 1$ and $\Psi_{2}(v_{0})=0=3\cdot 0$, which satisfies
$(b)$ of that condition for $g_{1}=1\in{\mathbb{T}}_{4}$ and $g_{2}=0$.

######  Definition 4.

For a $G$-WQH partition $\alpha$ and a $G$-gain graph $(\Gamma,\psi)$, we
define a _gain graph_ $(\Gamma^{\alpha},\psi^{\alpha})$ as follows (assuming
$\psi(v,w)=0$ iff $v\not\sim w$):

  * •

for $v,w\in C_{1}\cup\cdots\cup C_{2k}$, we have
$\psi^{\alpha}(v,w)=\psi(v,w)$ (that is, the adjacency and the gains between
pairs of vertices in $\bigcup\limits_{i=1}^{2k}C_{i}$ are the same as in
$(\Gamma,\psi)$);

  * •

for $v\in C_{0}$ and an odd $i<2k$ such that $\Psi_{i}(v)=\Psi_{i+1}(v)$ and
$w\in C_{i}\cup C_{i+1}$, we have $\psi^{\alpha}(v,w)=\psi(v,w)$;

  * •

for $v\in C_{0}$ and an odd $i<2k$ such that $\Psi_{i}(v)=|C_{i}|g_{1}$ and
$\Psi_{i+1}(v)=|C_{i+1}|g_{2}$ for some $g_{1},g_{2}\in G$ we have
$\psi^{\alpha}(v,w)=g_{2}$ if $w\in C_{i}$ and $\psi^{\alpha}(v,w)=g_{1}$ if
$w\in C_{i+1}$.

The $G$-WQH partition is said to be _nontrivial_ if $(\Gamma,\psi)$ and
$(\Gamma^{\alpha},\psi^{\alpha})$ are not switching isomorphic.

Finally, for a $G$-WQH partition $\alpha$, let $Q_{\alpha}\in
M_{n}({\mathbb{C}}G)$ be a block-diagonal matrix
$Q_{\alpha}=\operatorname{diag}\left(I_{M_{n_{0}}({\mathbb{C}}G)},Q_{n_{1}},\dots,Q_{n_{k}}\right)$,
where for each $i=1,\dots,k$

$Q_{n_{i}}=\left(\begin{matrix}I_{M_{n_{i}}({\mathbb{C}}G)}-\frac{1}{n_{i}}J_{M_{n_{i}}({\mathbb{C}}G)}&\frac{1}{n_{i}}J_{M_{n_{i}}({\mathbb{C}}G)}\\\
\frac{1}{n_{i}}J_{M_{n_{i}}({\mathbb{C}}G)}&I_{M_{n_{i}}({\mathbb{C}}G)}-\frac{1}{n_{i}}J_{M_{n_{i}}({\mathbb{C}}G)}\end{matrix}\right),$

where recall that $n_{i}$ is the size of $C_{i}$ and $C_{i+1}$ for any odd
$i<2k$.

Observe that the nonzero entries of $Q_{\alpha}$ are all real multiples of
$1_{G}$ and $Q_{\alpha}^{*}=Q_{\alpha}$.

######  Lemma 5.

Let $A$ be a $2n_{i}\times 2n_{j}$ block matrix

$A=\left(\begin{matrix}A_{1,1}&A_{1,2}\\\ A_{2,1}&A_{2,2}\end{matrix}\right)$

with each block has size $n_{i}\times n_{j}$ and such that the blocks
$A_{1,1}$ and $A_{2,2}$ (as well as $A_{1,2}$ and $A_{2,1}$) have constant row
sum of the same value and constant column sum of the same value. Then
$Q_{n_{i}}AQ_{n_{j}}=A$.

###### Proof.

Suppose $r_{1}$ and $c_{1}$ are, respectively, row sum and column sum
constants for $A_{1,1}$ and $A_{2,2}$, while $r_{2}$ and $c_{2}$ are such
constants for $A_{1,2}$ and $A_{2,1}$. Observe that

$\displaystyle
J_{M_{n_{i}}({\mathbb{C}}G)}A_{l,l}=c_{1}J_{M_{n_{i},n_{j}}({\mathbb{C}}G)},\quad
A_{l,l}J_{M_{n_{j}}({\mathbb{C}}G)}=r_{1}J_{M_{n_{i},n_{j}}({\mathbb{C}}G)}\text{
for }l\in\\{1,2\\};$ $\displaystyle
J_{M_{n_{i}}({\mathbb{C}}G)}A_{l,m}=c_{2}J_{M_{n_{i},n_{j}}({\mathbb{C}}G)},\quad
A_{l,m}J_{M_{n_{j}}({\mathbb{C}}G)}=r_{2}J_{M_{n_{i},n_{j}}({\mathbb{C}}G)}\text{
for }\\{l,m\\}=\\{1,2\\};$ $\displaystyle
J_{M_{n_{i}}({\mathbb{C}}G)}J_{M_{n_{i},n_{j}}({\mathbb{C}}G)}=n_{i}J_{M_{n_{i},n_{j}}({\mathbb{C}}G)},\quad
J_{M_{n_{i},n_{j}}({\mathbb{C}}G)}J_{M_{n_{j}}({\mathbb{C}}G)}=n_{j}J_{M_{n_{i},n_{j}}({\mathbb{C}}G)}.$

Using the above equalities, it is straightforward to verify that
$Q_{n_{i}}AQ_{n_{j}}=A$ by performing the block matrix multiplication. ∎

######  Theorem 6.

Let $(\Gamma,\psi)$ be a $G$-gain graph and let $\alpha$ be a $G$-WQH
partition with associated matrix $Q_{\alpha}\in M_{n}({\mathbb{C}}G)$. Then

$A_{(\Gamma^{\alpha},\psi^{\alpha})}=Q_{\alpha}A_{(\Gamma,\psi)}Q_{\alpha}.$

In particular, $(\Gamma,\psi)$ and $(\Gamma^{\alpha},\psi^{\alpha})$ are
$G$-cospectral.

###### Proof.

With a suitable labeling of vertices of $\Gamma$ we can write

$A_{(\Gamma,\psi)}=\left(\begin{matrix}C_{0,0}&C_{0,1}&\dots&C_{0,k}\\\
C_{0,1}^{*}&C_{1,1}&\dots&C_{1,k}\\\ \vdots&\cdots&\ddots&\vdots\\\
C_{0,k}^{*}&C_{1,k}^{*}&\cdots&C_{k,k}\end{matrix}\right).$

Here, for all $i,j\in\\{1,\dots,k\\}$ the block $C_{i,j}\in
M_{2n_{2i-1},2n_{2j-1}}({\mathbb{C}}G)$ describes the adjacencies and gains
from vertices in $C_{2i-1}\cup C_{2i}$ to vertices in $C_{2j-1}\cup C_{2j}$.
The block $C_{0,j}\in M_{n_{0},2n_{2j-1}}({\mathbb{C}}G)$ describes the
adjacencies and gains from vertices in $C_{0}$ to vertices in $C_{2j-1}\cup
C_{2j}$. Later we will also use a split of this block
$C_{0,j}=\left(C_{0,j}^{(1)},\;C_{0,j}^{(2)}\right)$, where $C_{0,j}^{(1)}$
describes adjacencies between the vertices of $C_{0}$ and $C_{2j-1}$, while
$C_{0,j}^{(2)}$ does so for $C_{0}$ and $C_{2j}$. Finally, the block
$C_{0,0}\in M_{n_{0}}({\mathbb{C}}G)$ describes adjacencies and gains within
the vertex subset $C_{0}$.

The following is true for $A_{(\Gamma,\psi)}$ by the definition of $G$-WQH
partition (Definition 2):

  * •

for $i\in\\{0,\dots,k\\}$ we have $C_{i,i}^{*}=C_{i,i}$;

  * •

for $i,j\in\\{0,\dots,k\\}$ the matrix $C_{i,j}$ satisfies the conditions of
Lemma 5.

By block matrix multiplication and from Lemma 5 we have:

$Q_{\alpha}A_{(\Gamma,\psi)}Q_{\alpha}=\left(\begin{matrix}C_{0,0}&C_{0,1}Q_{n_{1}}&\dots&C_{0,k}Q_{n_{k}}\\\
Q_{n_{1}}C_{0,1}^{*}&C_{1,1}&\dots&C_{1,k}\\\ \vdots&\cdots&\ddots&\vdots\\\
Q_{n_{k}}C_{0,k}^{*}&C_{1,k}^{*}&\cdots&C_{k,k}\end{matrix}\right).$

Let $v\in C_{0}$ and $j\in\\{1,\dots,k\\}$, and let ${\bf x}$ be the row of
$C_{0,j}$ which corresponds to $v$ (the following observations are just as
valid for the column ${\bf x}^{*}$ of $C_{0,j}^{*}$ corresponding to $v$).
With the use of the split $C_{0,j}=\left(C_{0,j}^{(1)},\;C_{0,j}^{(2)}\right)$
we can write down (assuming $J:=J_{M_{n_{j}}({\mathbb{C}}G)}$)

$C_{0,j}=\left(C_{0,j}^{(1)}-\frac{1}{n_{j}}C_{0,j}^{(1)}J+\frac{1}{n_{j}}C_{0,j}^{(2)}J,\quad\frac{1}{n_{j}}C_{0,j}^{(1)}J+C_{0,j}^{(2)}-\frac{1}{n_{j}}C_{0,j}^{(2)}J\right).$

There are two possible cases. First, if $\Psi_{2j-1}(v)=\Psi_{2j}(v)$, then
the row corresponding to $v$ in $A_{(\Gamma^{\alpha},\psi^{\alpha})}$ is also
${\bf x}$ as the contribution of $\frac{1}{n_{j}}C_{0,j}^{(1)}J$ and
$\frac{1}{n_{j}}C_{0,j}^{(2)}J$ terms amounts to zero in this case. On the
other hand, suppose $\Psi_{2j-1}(v)=n_{2j-1}g_{1}$ and
$\Psi_{2j}(v)=n_{2j-1}g_{2}$ for some $g_{1},g_{2}\in G\cup\\{0\\}$, or, in
other words, ${\bf x}$ takes form $(g_{1},\dots,g_{1},g_{2},\dots,g_{2})$, a
row of $n_{2j-1}$ entries $g_{1}$ followed by $n_{2j-1}$ entries $g_{2}$. Then
the row of $C_{0,j}Q_{n_{j}}$ corresponding to the vertex $v$ takes form
$(g_{2},\dots,g_{2},g_{1},\dots,g_{1})$. Either case is consistent with the
described construction of the graph $(\Gamma^{\alpha},\psi^{\alpha})$, and so
the matrix $Q_{\alpha}A_{(\Gamma,\psi)}Q_{\alpha}$ is indeed equal to the
adjacency matrix $A_{(\Gamma^{\alpha},\psi^{\alpha})}$. ∎

######  Example 7.

Let $(\Gamma,\psi)$ be a ${\mathbb{T}}_{4}$-gain graph on $13$ vertices with
the partition $\alpha$ as in Example 3. It was already shown that $\alpha$ is
a $G$-WQH partition. Moreover, the partition is nontrivial. Indeed, the graph
$(\Gamma^{\alpha},\psi^{\alpha})$ is obtained from $(\Gamma,\psi)$ by removing
edges $\\{v_{0},v_{i}\\}$, $i\in\\{1,2,3\\}$ and adding new edges
$\\{v_{0},v_{i}\\}$, $i\in\\{4,5,6\\}$ all with gain $1$. This graph is
disconnected unlike $(\Gamma,\alpha)$, and hence cannot be switching
isomorphic to it. It also cannot be constructed using the GM switching for
$G$-cospectral graphs from [8] since there is no suitable $G$-GM partition of
$V_{\Gamma}$.

##  4 A switching with respect to a representation: $\pi$-cospectral gain
graphs

In this section, we present a method to obtain pairs of $\pi$-cospectral gain
graphs for some unitary representation $\pi$ of the group $G$.

Let $(\Gamma,\psi)$ be a $G$-gain graph on $n$ vertices, and let $\pi$ be a
unitary representation $\pi:G\to U_{k}({\mathbb{C}})$ ($\pi$ also stands for a
linear extension $\pi:{\mathbb{C}}G\to M_{k}({\mathbb{C}})$). Recall the
function

$\Psi_{i}(v):=\sum\limits_{w\in C_{i},w\sim v}\psi(v,w)$

defined with respect to a partition $\alpha=\\{C_{0},C_{1},\dots,C_{2k}\\}$.
In this section, we will also use a function
$\Psi_{i,i+1}(v)=\Psi_{i}(v)+\Psi_{i+1}(v)$ for an odd $i<2k$.

######  Remark 8.

If $\pi_{0}$ is the trivial representation mapping each element of $G$ to $1$,
then $\pi_{0}(\psi_{i}(v))$ is the number of vertices of $C_{i}$ which are
adjacent to $v$.

######  Definition 9.

A partition $\alpha=\\{C_{0},C_{1},\dots,C_{2k}\\}$ of the vertex set of
$\Gamma$ is a _$\pi$ -WQH partition_ if the following conditions hold:

  * •

$|C_{0}|=n_{0}$ and $|C_{i}|=|C_{i+1}|=n_{i}$ for an odd $i<2k$;

  * •

for $i,j\in\\{1,\dots,2k\\}$ and $v,v^{\prime}\in C_{i}$ we have
$\pi(\Psi_{j}(v))=\pi(\Psi_{j}(v^{\prime}))$;

  * •

for odd $i,j<2k$ and $v\in C_{i}$, $v^{\prime}\in C_{i+1}$ we have
$\pi(\Psi_{j}(v))=\pi(\Psi_{j+1}(v^{\prime}))$ and
$\pi(\Psi_{j+1}(v))=\pi(\Psi_{j}(v^{\prime}))$;

  * •

for every $v\in C_{0}$ and an odd $i<2k$ we have either

    1. (a)

$\Psi_{i}(v)=\Psi_{i+1}(v)$, or

    2. (b)

$\Psi_{i}(v)=|C_{i}|g_{1}$ and $\Psi_{i+1}(v)=|C_{i+1}|g_{2}$ for some
distinct $g_{1},g_{2}\in G\cup\\{0\\}$.

The above definition is closely related to Definition 2. For a $\pi$-WQH
partition $\alpha$, the graph $(\Gamma^{\alpha},\psi^{\alpha})$ is constructed
exactly as described in Definition 4.

######  Example 10.

This example builds on [8, Example 4.3]. Consider an $S_{4}$-gain graph
$(\Gamma,\psi)$ depicted in the left of Figure 1; the $\psi$-image of any
unlabeled edge is $1_{S_{4}}$. Let $\alpha$ be a partition
$\\{C_{0},C_{1},C_{2},C_{3},C_{4}\\}$, where $C_{0}=\\{v_{1}\\}$,
$C_{1}=\\{v_{2},v_{3},v_{4},v_{5}\\}$, $C_{2}=\\{v_{6},v_{7},v_{8},v_{9}\\}$,
$C_{3}=\\{v_{10},v_{11},v_{12},v_{13}\\}$, and
$C_{4}=\\{v_{14},v_{15},v_{16},v_{17}\\}$. It is not a $G$-WQH partition,
since $\Psi_{1}(v)=1_{S_{4}}+(12)(34)\neq(12)+(34)=\Psi_{2}(v^{\prime})$ for
$v\in C_{1}$ and $v^{\prime}\in C_{2}$. However, by choosing a unitary
representation $\pi$ that sends a permutation from $S_{4}$ to a respective
$4\times 4$ permutation matrix, we obtain

$\displaystyle\pi(1_{S_{4}})$ $\displaystyle=\left(\begin{matrix}1&0&0&0\\\
0&1&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{matrix}\right),\;\pi((12)(34))=\left(\begin{matrix}0&1&0&0\\\
1&0&0&0\\\ 0&0&0&1\\\ 0&0&1&0\end{matrix}\right),$ $\displaystyle\pi((12))$
$\displaystyle=\left(\begin{matrix}0&1&0&0\\\ 1&0&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{matrix}\right),\;\pi((34))=\left(\begin{matrix}1&0&0&0\\\
0&1&0&0\\\ 0&0&0&1\\\ 0&0&1&0\end{matrix}\right).$

and so $\pi(\Psi_{1}(v))=\pi(\Psi_{2}(v^{\prime}))$. Similarly, for $v\in
C_{3}$ and $v^{\prime}\in C_{4}$ we have
$\pi(\Psi_{3}(v))=\pi(\Psi_{4}(v^{\prime}))$. As for the other conditions, we
have $|C_{1}|=|C_{2}|$ and $|C_{3}|=|C_{4}|$, as well as $\Psi_{j}(v_{i})=0$
for any distinct $i,j\in\\{1,2,3,4\\}$, so the first three conditions in
Definition 9 are satisfied. For the final condition, we have
$\Psi_{1}(v_{1})=4\times 1_{S_{4}}$ and $\Psi_{2}(v_{1})=4\times 0$ which
satisfies the $(a)$ part, and $\Psi_{3}(v_{1})=\Psi_{4}(v_{1})=1_{S_{4}}$
satisfying part $(b)$.

######  Theorem 11.

Let $(\Gamma,\psi)$ be a $G$-gain graph, let $\pi$ be a unitary representation
of $G$, and let $\alpha$ be a $\pi$-WQH partition. Then

$\pi(A_{(\Gamma^{\alpha},\psi^{\alpha})})=\pi(Q_{\alpha})\pi(A_{(\Gamma,\psi)})\pi(Q_{\alpha}),$

and in particular, $(\Gamma,\psi)$ and $(\Gamma^{\alpha},\psi^{\alpha})$ are
$\pi$-cospectral.

###### Proof.

Observe that (the extension to ${\mathbb{C}}G$ of) $\pi$ is a homomorphism, so
$\pi(Q_{\alpha})\pi(A_{(\Gamma,\psi)})\pi(Q_{\alpha})=\pi(Q_{\alpha}A_{(\Gamma,\psi)}Q_{\alpha})$.
Also, by the argument similar to one presented in the proof of Theorem 6, the
first $n_{0}$ rows and columns of matrix
$Q_{\alpha}A_{(\Gamma,\psi)}Q_{\alpha}$ relate to the adjacencies between
vertices from $C_{0}$ and $C_{i}$ for $i\in\\{0,1,\dots,2k\\}$ in
$(\Gamma^{\alpha},\psi^{\alpha})$. Hence all that is left to prove is that the
$\pi$-image of $(n-n_{0})\times(n-n_{0})$ principal submatrix of
$Q_{\alpha}A_{(\Gamma,\psi)}Q_{\alpha}$ obtained by removing first $n_{0}$
rows and columns is the same as the $\pi$-image of a similarly constructed
submatrix of $A_{(\Gamma^{\alpha},\psi^{\alpha})}$. We will do so by
considering individual blocks of this matrix.

We fix a pair of odd (not necessarily distinct) integers $i,j<2k$ and consider
pairs of subsets $C_{i}\cup C_{i+1}$ and $C_{j}\cup C_{j+1}$ with vertices
$v_{1},\dots,v_{2n_{i}}$ and $w_{1},\dots,w_{2n_{j}}$ respectively. Let
$A^{\prime}$ denote a $2n_{i}\times 2n_{j}$ principal submatrix of
$A_{(\Gamma,\psi)}$ obtained by taking rows corresponding to vertices
$v_{1},\dots v_{2n_{i}}$ and columns corresponding to vertices
$w_{1},\dots,w_{2n_{j}}$. The labeling of the vertices is such that an element
$A^{\prime}_{i,j}$ is $\psi(v_{i},w_{j})$ if $v_{i}$ and $w_{j}$ are adjacent
or $A^{\prime}_{i,j}=0$ otherwise. In this case, after the conjugation
$Q_{\alpha}A_{(\Gamma,\psi)}Q_{\alpha}$ this block takes form
$Q_{n_{i}}A^{\prime}Q_{n_{j}}$.

The matrix $A^{\prime}$ can be represented as a block matrix

$A=\left(\begin{matrix}A_{11}&A_{12}\\\ A_{21}&A_{22}\end{matrix}\right).$

Let $S_{1}$ be the sum of all elements in block $A_{11}$ (same as the sum of
elements in block $A_{22}$), and $S_{2}$ be the sum of all elements in block
$A_{12}$ ($A_{21}$). Let $D$ be a matrix of four $n_{i}\times n_{j}$ blocks

$D=\left(\begin{matrix}D_{11}&D_{12}\\\ D_{21}&D_{22}\end{matrix}\right),$

where

$\displaystyle D_{11}$
$\displaystyle=\left(\begin{matrix}\frac{S_{1}}{n_{i}}+\frac{S_{1}}{n_{j}}-\Psi_{i}(v_{1})-\Psi_{j}^{*}(w_{1})&\frac{S_{1}}{n_{j}}-\Psi_{j}^{*}(w_{2})&\dots&\frac{S_{1}}{n_{j}}-\Psi_{j}^{*}(w_{n_{j}})\\\
\frac{S_{1}}{n_{i}}-\Psi_{i}(v_{2})&0&\dots&0\\\ \vdots&\dots&\dots&\dots\\\
\frac{S_{1}}{n_{i}}-\Psi_{i}(v_{n_{i}})&0&\dots&0\end{matrix}\right),$
$\displaystyle D_{12}$
$\displaystyle=\left(\begin{matrix}\frac{S_{2}}{n_{i}}+\frac{S_{2}}{n_{j}}-\Psi_{i+1}(v_{1})-\Psi_{j}^{*}(w_{n_{j}+1})&\frac{S_{2}}{n_{j}}-\Psi_{j}^{*}(w_{n_{j}+2})&\dots&\frac{S_{2}}{n_{j}}-\Psi_{j}^{*}(w_{2n_{j}})\\\
\frac{S_{2}}{n_{i}}-\Psi_{i+1}(v_{2})&0&\dots&0\\\ \vdots&\dots&\dots&\dots\\\
\frac{S_{2}}{n_{i}}-\Psi_{i+1}(v_{n_{i}})&0&\dots&0\end{matrix}\right),$
$\displaystyle D_{21}$
$\displaystyle=\left(\begin{matrix}\frac{S_{2}}{n_{i}}+\frac{S_{2}}{n_{j}}-\Psi_{i}(v_{n_{i}+1})-\Psi_{j+1}^{*}(w_{1})&\frac{S_{2}}{n_{j}}-\Psi_{j+1}^{*}(w_{2})&\dots&\frac{S_{2}}{n_{j}}-\Psi_{j+1}^{*}(w_{n_{j}})\\\
\frac{S_{2}}{n_{i}}-\Psi_{i}(v_{n_{i}+2})&0&\dots&0\\\
\vdots&\dots&\dots&\dots\\\
\frac{S_{2}}{n_{i}}-\Psi_{i}(v_{2n_{i}})&0&\dots&0\end{matrix}\right),$
$\displaystyle D_{22}$
$\displaystyle=\left(\begin{matrix}\frac{S_{1}}{n_{i}}+\frac{S_{1}}{n_{j}}-\Psi_{i+1}(v_{n_{i}+1})-\Psi_{j+1}^{*}(w_{n_{j}+1})&\frac{S_{1}}{n_{j}}-\Psi_{j+1}^{*}(w_{n_{j}+2})&\dots&\frac{S_{1}}{n_{j}}-\Psi_{j+1}^{*}(w_{2n_{j}})\\\
\frac{S_{1}}{n_{i}}-\Psi_{i+1}(v_{n_{i}+2})&0&\dots&0\\\
\vdots&\dots&\dots&\dots\\\
\frac{S_{1}}{n_{i}}-\Psi_{i+1}(v_{2n_{i}})&0&\dots&0\end{matrix}\right).$

Observe that $A^{\prime}+D$ has a constant row and column sum of the same
value, as well as its two principal submatrices obtained by removing first
(last) $n_{i}$ rows and $n_{j}$ columns. Indeed, using the fact that
$\Psi_{i,i+1}(v)$ is the sum of the row of $A^{\prime}$ that corresponds to
the vertex $v$ and $\Psi_{j,j+1}^{*}(w)$ is the sum of the respective column,
it is trivial to confirm that the sum of any row or column of $A^{\prime}+D$
is equal to $\frac{S_{1}+S_{2}}{n_{i}}$ or $\frac{S_{1}+S_{2}}{n_{j}}$
respectively, while the four blocks have row sum $\frac{S_{t}}{n_{i}}$ and
column sum $\frac{S_{t}}{n_{j}}$ where $t\in\\{1,2\\}$ depending on the block
(analogous to the proof of [8, Theorem 4.4]). This means we can apply Lemma 5
to show that $Q_{n_{i}}(A^{\prime}+D)Q_{n_{j}}=A^{\prime}+D$.

In addition, we have $\pi(D)=0$. This follows from the following equalities
that hold for any $v\in C_{i}$, $v^{\prime}\in C_{i+1}$, $w\in C_{j}$, and
$w^{\prime}\in C_{j+1}$ due to the definition of $\pi$-WQH partition:

$\displaystyle\pi(S_{1})=\pi(n_{i}\Psi_{i}(v))=\pi(n_{j}\Psi_{j}^{*}(w))=\pi(n_{i}\Psi_{i+1}(v^{\prime}))=\pi(n_{j}\Psi_{j+1}^{*}(w^{\prime})),$
$\displaystyle\pi(S_{2})=\pi(n_{i}\Psi_{i+1}(v))=\pi(n_{j}\Psi_{j}^{*}(w^{\prime}))=\pi(n_{i}\Psi_{i}(v^{\prime}))=\pi(n_{j}\Psi_{j+1}^{*}(w)).$

From this it is easily derived that the $\pi$-image in any element of $D$ is
$0$.

By combining $Q_{n_{i}}(A^{\prime}+D)Q_{n_{j}}=A^{\prime}+D$ and $\pi(D)=0$,
we obtain

$\displaystyle\pi(Q_{n_{i}}A^{\prime}Q_{n_{j}})$
$\displaystyle=\pi(Q_{n_{i}}(A^{\prime}+D-D)Q_{n_{j}})$
$\displaystyle=\pi(Q_{n_{i}}(A^{\prime}+D)Q_{n_{j}})-\pi(Q_{n_{i}})\cdot
0\cdot\pi(Q_{n_{j}})$
$\displaystyle=\pi(A^{\prime}+D)=\pi(A^{\prime})+0=\pi(A^{\prime}).\qed$

$\displaystyle v_{1}$$\displaystyle v_{2}$$\displaystyle v_{3}$$\displaystyle
v_{4}$$\displaystyle v_{5}$$\displaystyle v_{6}$$\displaystyle
v_{7}$$\displaystyle v_{8}$$\displaystyle
v_{9}$$\displaystyle(12)$$\displaystyle(12)$$\displaystyle(34)$$\displaystyle(34)$$\displaystyle(12)(34)$$\displaystyle(12)(34)$$\displaystyle
v_{14}$$\displaystyle v_{15}$$\displaystyle v_{16}$$\displaystyle
v_{17}$$\displaystyle(12)$$\displaystyle(12)$$\displaystyle(34)$$\displaystyle(34)$$\displaystyle
v_{10}$$\displaystyle v_{11}$$\displaystyle v_{12}$$\displaystyle
v_{13}$$\displaystyle(12)(34)$$\displaystyle(12)(34)$$\displaystyle
v_{1}$$\displaystyle v_{2}$$\displaystyle v_{3}$$\displaystyle
v_{4}$$\displaystyle v_{5}$$\displaystyle v_{6}$$\displaystyle
v_{7}$$\displaystyle v_{8}$$\displaystyle
v_{9}$$\displaystyle(12)$$\displaystyle(12)$$\displaystyle(34)$$\displaystyle(34)$$\displaystyle(12)(34)$$\displaystyle(12)(34)$$\displaystyle
v_{14}$$\displaystyle v_{15}$$\displaystyle v_{16}$$\displaystyle
v_{17}$$\displaystyle(12)$$\displaystyle(12)$$\displaystyle(34)$$\displaystyle(34)$$\displaystyle
v_{10}$$\displaystyle v_{11}$$\displaystyle v_{12}$$\displaystyle
v_{13}$$\displaystyle(12)(34)$$\displaystyle(12)(34)$ Figure 1: A pair of
$\pi$-cospectral not switching isomorphic $S_{4}$-gain graphs from Example 12.

######  Example 12.

Consider the $S_{4}$-gain graph $(\Gamma,\psi)$ and a partition $\alpha$ from
Example 10. It was already shown that $\alpha$ is a $\pi$-WQH partition where
$\pi$ is a unitary representation that maps an element of $S_{4}$ to a
respective permutation matrix of size $4$. The graph
$(\Gamma^{\alpha},\psi^{\alpha})$ (on the right in Figure 1) is not switching
isomorphic to $(\Gamma,\psi)$. Additionally, there is no partition that both
satisfies the conditions for $\pi$-GM partition for some $\pi$ (defined in
[8]) and produces a graph that is switching isomorphic to
$(\Gamma^{\alpha},\psi^{\alpha})$.

##  5 Concluding remarks

The generalization of the spectral graph theory to gain graphs is far from
trivial. Switching methods for gain graphs were previously described in the
literature for some particular cases. In [3, Section 4], WQH-switching
(referred to as Modified Godsil-McKay switching) was generalized to signed
graphs. In [4, Section 3], the same switching was described for complex unit
gain graphs. In both cases, adaptations of WQH-switching were used to
construct cospectral graphs with respect to the identical representation. For
a general group $G\not\subseteq{\mathbb{C}}$, an approach based on group
representations was introduced in [7] in order to discuss the spectrum of a
$G$-gain graph with respect to any representation $\pi$. In [9], the notion of
$G$-cospectrality independent of the choice of $\pi$ was first introduced, and
in [8], generalizations of GM-switching with respect to both $G$\- and
$\pi$-cospectrality were described. To the authors’ knowledge, only the work
by Cavaleri, Donno and Spessato [9, 8] contributed before to the investigation
of the cospectrality in the context of gain graphs over a general group $G$.

### Acknowledgements

Aida Abiad is partially supported by FWO (Research Foundation Flanders) via
the grant 1285921N. This research is supported by NWO (Dutch Research Council)
via an ENW-KLEIN-1 project (OCENW.KLEIN.475).

## References

  * [1] S. Akbari, F. Belardo, E. Dodongeh, M.A. Nematollahi. Spectral characterizations of signed cycles. _Linear Algebra Appl._ 553:307–327 (2018).
  * [2] S. Akbari, W.H. Haemers, H.R. Maimani, L. Parsaei Maid. Signed graphs cospectral with the path. _Linear Algebra Appl._ 553:104–116 (2018).
  * [3] F. Belardo, M. Brunetti, M. Cavaleri, A. Donno. Constructing cospectral signed graphs. _Linear Multilinear Algebra._ 69(14):2717–2732 (2021).
  * [4] F. Belardo, M. Brunetti, M. Cavaleri, A. Donno. Godsil-McKay switching for mixed and gain graphs over the circle group. _Linear Algebra Appl._ 614:256–269 (2021).
  * [5] F. Belardo, M. Brunetti, N.J. Coble, N. Reff, H. Skogman. Spectra of quaternion unit gain graphs. _Linear Algebra Appl._ 632:15–49 (2022).
  * [6] F. Belardo, P. Petecki. Spectral characterizations of signed lollipop graphs. _Linear Algebra Appl._ 480:144–167 (2015).
  * [7] M. Cavaleri, D. D’Angeli, A. Donno. A group representation approach to balance of gain graphs. _J. Algebraic Combin._ 54(1): 265–293 (2021).
  * [8] M. Cavaleri, A. Donno, S. Spessato. Godsil-McKay switchings for gain graphs. arxiv:2207.10986v1 (2022).
  * [9] M. Cavaleri, A. Donno. On cospectrality of gain graphs. _Special Matrices_ 10(1): 343-365 (2022).
  * [10] C.D. Godsil, B.D. McKay. Constructing cospectral graphs. _Aequationes Math._ 25:257–268 (1982).
  * [11] J.L. Gross, T.W. Tucker. Generating all graph coverings by permutation voltage assignments. _Discrete Math._ 18(3) (1977), 273–283.
  * [12] F. Harary. On the notion of balance of a signed graph, _Michigan Math. J._ 2:143–146 (1953–1954).
  * [13] L. Qiu, Y. Ji, W. Wang. On a theorem of Godsil and McKay concerning the construction of cospectral graphs. _Linear Algebra Appl._ 603:265–274 (2020).
  * [14] N. Reff. Spectral properties of complex unit gain graphs. _Linear Algebra Appl._ 436(9):3165–3176 (2012).
  * [15] W. Wang, L. Qiu, Y. Hu. Cospectral graphs, GM-switching and regular rational orthogonal matrices of level $p$. _Linear Algebra Appl._ 563:154–177 (2019).
  * [16] P. Wissing, E.R. van Dam. Spectral fundamentals and characterizations of signed directed graphs. _J. Combin. Theory_ 187 (2022).
  * [17] T. Zaslavsky. Characterizations of signed graphs. _J. Graph Theory_ 5(4):401–406 (1981).
  * [18] T. Zaslavsky. Biased graphs. I. Bias, balance, and gains. _J. Combin. Theory_ 47(1):32–52 (1989).
  * [19] T. Zaslavsky. A mathematical bibliography of signed and gain graphs and allied areas. _Electron. J. Combin._ #DS8: Dec 21, 2018.


# The planar pure braid group is a diagram group

Daniel S. Farley  Department of Mathematics
Miami University
Oxford, OH 45056 U.S.A<EMAIL_ADDRESS>
###### Abstract.

The _$n$ -strand planar pure braid group_ is the fundamental group of
$\mathbb{R}^{n}-\Delta$, where $\Delta$ consists of all $n$-tuples in which
three or more coordinates are the same.

We prove that the $n$-strand planar pure braid group is a diagram group, for
all $n\geq 1$. Here, “diagram group” refers to the class of groups studied at
length by Guba and Sapir. We can deduce numerous corollaries. For instance,
the $n$-strand planar pure braid group acts freely and cocompactly on a CAT(0)
cubical complex. It is linear, bi-orderable, and biautomatic. The
representation of the planar pure braid groups as diagram groups also offers
procedures for computing group presentations and homology.

We similarly find that “cylindrical” versions of the planar pure braid group
are annular diagram groups. This establishes some of the above corollaries for
the cylindrical (or annular) planar pure braid groups.

After initially posting a version of this preprint to the arXiv, the author
learned that the main theorem (Theorem 1) had previously been observed by
Anthony Genevois. We refer the reader to the acknowledgments for details.

###### Key words and phrases:

diagram groups, CAT(0) cubical complex, planar braid groups

###### 2020 Mathematics Subject Classification:

Primary 20F36, 20F65; Secondary 57M07

##  1\. Introduction

Consider the space $X_{n}=\mathbb{R}^{n}-\Delta$, where $\Delta$ is the set of
all $n$-tuples of real numbers $(x_{1},\ldots,x_{n})$, such that
$x_{i}=x_{j}=x_{k}$, for some $1\leq i<j<k\leq n$. The fundamental group
$\Gamma_{n}$ of this space has been studied under several different names (for
a short guide, see the introduction to [16]), and in mathematical contexts
ranging from low-dimensional topology [14] to topological robotics [7]. We
will follow [16] in calling $\Gamma_{n}$ the _$n$ -strand planar pure braid
group_.

In this short note, we will show that $\Gamma_{n}$ is a diagram group, for all
$n\geq 1$. Indeed, it is not difficult to observe, after comparing
definitions, that $\Gamma_{n}\cong\mathcal{D}(\mathcal{P}_{n},w_{n})$, where
$w_{n}=x_{1}x_{2}\ldots x_{n}$ and

$\mathcal{P}_{n}=\langle x_{1},x_{2},\ldots,x_{n}\mid
x_{i}x_{j}=x_{j}x_{i}\,\,(i\neq j)\rangle.$

This is our main theorem. We will briefly review the necessary definitions in
the body of the paper.

The author proved that each diagram group acts freely and cellularly on an
explicitly defined CAT(0) cubical complex [3]. The quotient of the cube
complex by this action is called the _Squier complex_ in [5]. (Note that, in
[10], it is the $2$-skeleton of the above quotient that is called the Squier
complex. In this note, we use the definition from [5].) Theorem 3.13 from [3]
easily implies that the Squier complex is compact in the case of
$\mathcal{D}(\mathcal{P}_{n},w_{n})$.

Various corollaries now follow from the work of others. Genevois [5] proves
that any compact Squier complex is special. In particular, the associated
diagram group embeds into a right-angled Artin group by results of [11], and
is therefore linear [12, 13] and bi-orderable [2]. A result of Niblo and
Reeves [17] shows that any group acting properly and cocompactly on a CAT(0)
cubical complex is biautomatic. It follows directly that each $\Gamma_{n}$ is
linear, bi-orderable, and biautomatic. Guba and Sapir have proved that all
diagram groups are bi-orderable [9], which gives a second proof that the
$\Gamma_{n}$ are bi-orderable. They have also computed presentations of
diagram groups and the integral homology groups of diagram groups (see [10]
and [8], respectively).

Several of the above corollaries also follow from the literature. The
introduction of [16] clearly shows that, for each $n$, $\Gamma_{n}$ is a
finite-index subgroup of a right-angled Coxeter group. Coxeter groups are
well-known to be linear, so the linearity of $\Gamma_{n}$ follows directly.
Moreover, the main result of [18] implies that right-angled Coxeter groups act
properly and cocompactly on CAT(0) cubical complexes, which shows that
$\Gamma_{n}$ acts properly and cocompactly on a CAT(0) cubical complex. The
latter fact implies that $\Gamma_{n}$ is biautomatic [17]. We note also that
presentations of $\Gamma_{n}$ [15, 16] and integral homology groups of
$\Gamma_{n}$ [1] have been computed.

Thus, after comparing the above lists of corollaries, it appears that the
proof that $\Gamma_{n}$ is bi-orderable is our main new result. Nevertheless,
the literature on diagram groups offers a number of additional techniques that
may prove useful in the further study of planar pure braid groups.

_Acknowledgments_ : I first learned about the planar braid groups during a
stimulating talk by Jesús González at the “2nd International Workshop on
Topology and Geometry” at the National University of San Marcos, Lima, Peru,
in 2019. It is a pleasure to thank him, and the organizers of the conference.
I would also like to thank Gabriel Drummond-Cole for encouraging me to write a
short note on this topic.

[Added (9/8/2021): After I posted this preprint to the arXiv, Anthony Genevois
informed me that Theorem 1 occurs as part of Example 5.43 from [6] (or Example
5.40 from the arXiv version). His example also showed that the planar pure
braid group is acylindrically hyperbolic. I would also like to thank Shane O
Rourke for pointing out a correction.]

##  2\. Diagram Groups

In this section, we offer a short definition of semigroup pictures and diagram
groups. The reader who would like a more thorough introduction should refer to
[4] or (especially) [10].

A _semigroup presentation_ $\mathcal{P}$ is a pair
$\langle\Sigma\mid\mathcal{R}\rangle$, where $\Sigma$ is a finite set (or
_alphabet_) and $\mathcal{R}$ is a collection of equalities between positive,
non-empty words in $\Sigma$. We consider three types of ingredients:

  * •

a non-empty collection of _wires_ , each of which is homeomorphic to $[0,1]$;

  * •

a possibly-empty collection of _transistors_ , each of which is a homeomorph
of $[0,1]^{2}$. A non-empty collection of points on the top and bottom of any
given transistor are _contacts_ ; each contact is labeled by a letter from
$\Sigma$. (We do not allow the corners of a transistor to be contacts.) If we
read the labels of the contacts on a given transistor from left to right, we
obtain non-empty positive words $w_{t}$ and $w_{b}$ in the generators (from
the top and bottom of the transistor, respectively). We then say that the
transistor in question is a _$(w_{t},w_{b})$ -transistor_. The equality
$w_{t}=w_{b}$ (or $w_{b}=w_{t}$) is required to be among the equalities of
$\mathcal{R}$ (note: and _not_ merely a consequence of the latter);

  * •

a _frame_ , which is a homeomorph of $\partial[0,1]^{2}$. Certain points on
the top and bottom of the frame (but never the corners) are also called
contacts and are given labels from the alphabet $\Sigma$. By reading the
labels on these contacts from left to right, we obtain non-empty positive
words $u$ and $v$ (from the top and bottom, respectively).

We assemble the above in $\mathbb{R}^{2}$ subject to certain constraints. The
frame is to enclose all of the wires and transistors. Each wire is to be
monotonic (i.e., no horizontal line can cross the same wire twice), and no two
wires or two transistors may touch. Each wire should connect a pair of
contacts having the same label, and every contact is to be the endpoint of
some (unique) wire. The resulting figure is a _$(u,v)$ -semigroup picture over
$\mathcal{P}$_. Two such semigroup pictures are equivalent if they are
isotopic by a label-matching isotopy.

Given a $(u,v)$-semigroup picture $\Delta_{1}$ over $\mathcal{P}$ and a
$(v,w)$-semigroup picture $\Delta_{2}$ over $\mathcal{P}$, we define the
product $\Delta_{1}\circ\Delta_{2}$ by stacking $\Delta_{1}$ on top of
$\Delta_{2}$. This product is well-defined up to isotopy and
$\Delta_{1}\circ\Delta_{2}$ is a $(u,w)$-semigroup picture over $\mathcal{P}$.
Additionally, it is not difficult to see that $\circ$ is associative when the
relevant products exist. If we fix a positive non-empty word $u$ in the
alphabet $\Sigma$, then the collection of all $(u,u)$-semigroup pictures over
$\mathcal{P}$ becomes a semigroup.

$\mathbf{x_{1}}$$\mathbf{x_{2}}$$\mathbf{x_{3}}$$\mathbf{x_{3}}$$\mathbf{x_{1}}$$\mathbf{x_{2}}$$\mathbf{x_{3}}$

$\mathbf{x_{i}}$$\mathbf{x_{j}}$$\mathbf{x_{i}}$$\mathbf{x_{j}}$$\mathbf{x_{i}}$$\mathbf{x_{j}}$$\mathbf{x_{i}}$$\mathbf{x_{j}}$

Figure 1. On the left, we have an $(x_{1}x_{2}x_{3},x_{3}x_{1}x_{2})$-picture
over the presentation $\mathcal{P}_{3}=\langle x_{1},x_{2},x_{3}\mid
x_{i}x_{j}=x_{j}x_{i}\,(i\neq j)\rangle$. The right half of the figure depicts
the operation of reducing a dipole in a diagram over $\mathcal{P}_{n}$.

If a $(u,v)$-transistor $T_{1}$ occurs above a $(v,u)$-transistor $T_{2}$ in
such a way that the wires issuing from the bottom contacts of $T_{1}$ connect
bijectively and in an order-preserving fashion to the top contacts of $T_{2}$,
then we say that $T_{1}$ and $T_{2}$ form a _dipole_. We _delete_ the dipole
by removing the transistors $T_{1}$ and $T_{2}$ and the wires connecting them,
and then gluing the wires that were attached to the top of $T_{1}$, in order,
to the wires that were attached to the bottom of $T_{2}$. The inverse of the
latter operation is called _inserting_ a dipole. We say that two semigroup
pictures over $\mathcal{P}$ are _equivalent modulo dipoles_ if one can be
obtained from the other by repeatedly inserting and/or deleting dipoles.
“Equivalent modulo dipoles” is easily seen to be an equivalence relation on
semigroup diagrams over $\mathcal{P}$.

The set of all $(u,u)$-semigroup diagrams over $\mathcal{P}$ modulo dipoles
make up a group under the operation $\circ$, denoted
$\mathcal{D}(\mathcal{P},u)$ and called the _diagram group over $\mathcal{P}$
at the base word $u$_.

##  3\. Planar Pure Braids

We will use the description of planar braids that appears in [16]. Fix a
natural number $n$. A _planar braid_ is a collection of $n$ smooth descending
arcs in $\mathbb{R}^{2}$ connecting $n$ distinct points on one horizontal line
with $n$ distinct points directly beneath them on another horizontal line. A
given point in $\mathbb{R}^{2}$ is allowed to be on two of the arcs, but never
on three.

Two planar braids $b_{1}$ and $b_{2}$ are _isotopic_ if there is an endpoint-
preserving isotopy of the plane carrying $b_{1}$ onto $b_{2}$ such that all
intermediate homeomorphisms in the isotopy also carry $b_{1}$ to planar
braids. We then consider the isotopy classes of braids modulo the additional
relation that allows adjacent strands of the planar braid to pass over each
other, as pictured in Figure 2. The elements of the _$n$ -strand planar braid
group_, denoted $\overline{B}_{n}$, are the resulting equivalence classes. The
product $b_{1}b_{2}$ is defined by stacking $b_{1}$ on top of $b_{2}$.

Figure 2. We have depicted an instance of the planar braid relation, in the
case of a three-strand braid.

The _$n$ -strand planar pure braid group_ $\overline{P}_{n}$ is the subgroup
of $\overline{B}_{n}$ consisting of planar braids in which the initial and
terminal points of each descending arc lie on a vertical line.

##  4\. Proof of the main theorem

######  Theorem 1.

Let $\mathcal{P}_{n}=\langle x_{1},\ldots,x_{n}\mid
x_{i}x_{j}=x_{j}x_{i}\,(i\neq j)\rangle$. The diagram group
$\mathcal{D}(\mathcal{P}_{n},x_{1}\ldots x_{n})$ is isomorphic to the
$n$-strand planar pure braid group $\overline{P}_{n}$.

###### Proof.

We define a map
$\phi:\overline{P}_{n}\rightarrow\mathcal{D}(\mathcal{P}_{n},x_{1}\ldots
x_{n})$ as follows. Given a planar pure braid $b$, we first enclose the braid
in a frame in such a way that each strand connects a point on the top of the
frame to a point on the bottom of the frame. The points of intersection at the
top of the frame are labelled, from left to right, $x_{1}$ through $x_{n}$.
The points of intersection at the bottom of the frame are labelled in the same
way. We can now speak of the “$x_{i}$-strand”, for $i=1,\ldots,n$, which is
the unique strand connecting the point labelled $x_{i}$ at the top, to the
point labelled $x_{i}$ at the bottom. These labels are necessarily the same,
since $b$ is a planar pure braid.

We can assume, up to equivalence, that each crossing in $b$ is transverse. Let
$c$ be any such crossing. Assume that the $x_{i}$-strand crosses over the
$x_{j}$-strand from left to right as we move down the braid diagram. In this
case, we replace $c$ with an $(x_{i}x_{j},x_{j}x_{i})$-transistor. Repeating
this procedure at each crossing, we eventually arrive at an $(x_{1}\ldots
x_{n},x_{1}\ldots x_{n})$-picture over the presentation $\mathcal{P}_{n}$.
Conversely, taking any $(x_{1}\ldots x_{n},x_{1}\ldots x_{n})$-picture
$\Delta$, we can remove all labels and replace each transistor with a
transverse crossing. The result is a planar pure braid, which maps to $\Delta$
under $\phi$.

Note that the planar braid equivalence depicted in Figure 2 has its exact
counterpart in the procedure of reducing dipoles (see the right half of Figure
1). It follows that the correspondence $\phi$ is a well-defined bijection.
Finally, we note that the operation (of stacking) is identical in both groups,
which makes $\phi$ an isomorphism. ∎

######  Theorem 2.

Let $\mathcal{P}_{n}$ be as defined in Theorem 1. The annular diagram group
$D_{a}(\mathcal{P}_{n},x_{1}\ldots x_{n})$ is isomorphic to the annular planar
pure braid group.

###### Proof.

The proof is similar to that of Theorem 1. The reader who is interested in the
precise definition of annular diagram groups can consult [4] and [10]. We
indicate the isomorphism in Figure 3. ∎

Figure 3. On the left, we have an annular
$(x_{1}x_{2}x_{3},x_{1}x_{2}x_{3})$-picture over $\mathcal{P}_{3}$ and, on the
right, its corresponding annular planar pure braid. The dots on the left sides
of the inner and outer circles are basepoints that are used to define the
operation.

## References

  * [1] Anders Björner and Volkmar Welker.  The homology of “$k$-equal” manifolds and related partition lattices.  Adv. Math., 110(2):277–313, 1995.
  * [2] Gérard Duchamp and Jean-Yves Thibon.  Simple orderings for free partially commutative groups.  Internat. J. Algebra Comput., 2(3):351–355, 1992.
  * [3] Daniel S. Farley.  Finiteness and $\rm CAT(0)$ properties of diagram groups.  Topology, 42(5):1065–1082, 2003.
  * [4] Daniel S. Farley.  Actions of picture groups on CAT(0) cubical complexes.  Geom. Dedicata, 110:221–242, 2005.
  * [5] Anthony Genevois.  Hyperplanes of Squier’s cube complexes.  Algebr. Geom. Topol., 18(6):3205–3256, 2018.
  * [6] Anthony Genevois.  Contracting isometries of ${\rm CAT}(0)$ cube complexes and acylindrical hyperbolicity of diagram groups.  Algebr. Geom. Topol., 20(1):49–134, 2020.
  * [7] Jesús González, José Luis León-Medina, and Christopher Roque-Márquez.  Linear motion planning with controlled collisions and pure planar braids.  Homology Homotopy Appl., 23(1):275–296, 2021.
  * [8] V. S. Guba and M. V. Sapir.  Diagram groups and directed 2-complexes: homotopy and homology.  J. Pure Appl. Algebra, 205(1):1–47, 2006.
  * [9] V. S. Guba and M. V. Sapir.  Diagram groups are totally orderable.  J. Pure Appl. Algebra, 205(1):48–73, 2006.
  * [10] Victor Guba and Mark Sapir.  Diagram groups.  Mem. Amer. Math. Soc., 130(620):viii+117, 1997.
  * [11] Frédéric Haglund and Daniel T. Wise.  Special cube complexes.  Geom. Funct. Anal., 17(5):1551–1620, 2008.
  * [12] Tim Hsu and Daniel T. Wise.  On linear and residual properties of graph products.  Michigan Math. J., 46(2):251–259, 1999.
  * [13] Stephen P. Humphries.  On representations of Artin groups and the Tits conjecture.  J. Algebra, 169(3):847–862, 1994.
  * [14] Mikhail Khovanov.  Doodle groups.  Trans. Amer. Math. Soc., 349(6):2297–2315, 1997.
  * [15] Jacob Mostovoy.  A presentation for the planar pure braid group.  2020\.
  * [16] Jacob Mostovoy and Christopher Roque-Márquez.  Planar pure braids on six strands.  J. Knot Theory Ramifications, 29(1):1950097, 11, 2020.
  * [17] G. A. Niblo and L. D. Reeves.  The geometry of cube complexes and the complexity of their fundamental groups.  Topology, 37(3):621–633, 1998.
  * [18] G. A. Niblo and L. D. Reeves.  Coxeter groups act on ${\rm CAT}(0)$ cube complexes.  J. Group Theory, 6(3):399–413, 2003.