# On the quantum criticality in the ground and the thermal states of XX model

W. Son  Centre for Quantum Technologies, National University of Singapore, 3
Science Drive 2, Singapore 117543  V. Vedral  Centre for Quantum Technologies,
National University of Singapore, 3 Science Drive 2, Singapore 117543  The
School of Physics and Astronomy, University of Leeds, Leeds, LS2 9JT, United
Kingdom Department of Physics, National University of Singapore, 2 Science
Drive 3, Singapore 117542

###### Abstract

We compare the critical behavior of the ground state and the thermal state of
the XX model. We analyze the full energy spectrum and the eigenstates to
reconstruct the ground state and the thermally excited state. With the
solutions, we discuss about several physical properties of the states, which
are related to quantum phase transition, in various limits, at zero
temperature as well as at a thermal equilibrium.

Conventional definition of quantum phase transition (QPT) is given by energy
level crossing of ground energy state with varying external parameter
Sachdev99 . The definition is based on the view that the ground energy state
is taken as a quantum phase itself and, thus, QPT is a transition occurring at
the point where a zero temperature state is transited from one state to the
other. Because of the singular structure of the energy transition, the point
of QPT is known to be detected by non-analyticity of free energy.

Within the definition, a difficulty may arise if one tries to consider a
finite temperature QPT. It is because QPT is only defined at $T=0$. Typical
treatment of finite temperature phase transition so far is provided by the
non-analyticity of thermodynamic properties or the characteristic wave length
of the system Chakravarty89 ; Sachdev97 . However, it is not straightforward
how the singularity in the thermal state is consistently combined with the
notion of energy level crossing at zero temperature.

In this article, we study the full solutions of XX spin chain model, not only
the energy eignevalues but also the eignestates in the original spin basis.
With the solutions, we demonstrate how the sequential energy level crossings
at zero temperature is led to a continuous QPT in infinite spin limit,
$N\rightarrow\infty$. In the XX spin model, the number of ground energy level-
crossings grow with the size of the chain. When $N\rightarrow\infty$, the
crossing points become dense within a sharply defined critical region, giving
rise to a continuous QPT. This is a typical example when a ground state is no
longer in a pure state but in a mixed state. At the same time, each crossing
point of the ground energy state becomes fully analytic.

The situation is comparable to a state in finite temperature which is a
mixture of all the state spectrums with the Boltzmann distribution. We
investigate the structure of state in a thermally excited XX spin chain and
the purity of the state to compare it with the ground state of the infinite
chain. In the case, it can be seen that the temperature is acting as a
controlling parameter to determine the degree of state mixture in the system.
Thermodynamic properties of the thermal state are remained analytic in the
region. As temperature is increased, the state moves into a thermal mixture
which destroys the quantum correlations, entanglement, in the system.
Extensive discussions on the relation between QPT and entanglement in the XX
model can also be found at Son08 ; Amico07 ; Hide07 .

##  I XX Model and full solutions

We start our discussion by considering $N$ spin $1/2$ particles in a line,
coupled by nearest neighbor XX interaction, with Hamiltonian

$H=-\Big{[}\sum_{i=1}^{N}\frac{J}{2}(\sigma_{i}^{x}\sigma_{i+1}^{x}+\sigma_{i}^{y}\sigma_{i+1}^{y})+B\sigma_{i}^{z}\Big{]}$
(1)

where we have assumed that the exchange interaction $J$ fixes the energy unit.
The model with periodic boundary condition has been firstly solved by Katsura
Katsura62  and recently discussed at finite size in Ref. dep . Here, we assume
open boundaries, with $\sigma_{N+1}=0$. After Jordan-Wigner (JW) and Fourier
transformations,

$d_{k}=\sqrt{\frac{2}{N+1}}\sum_{l=1}^{N}\sin\left(\frac{\pi
kl}{N+1}\right)\,\bigotimes_{m=1}^{l-1}\sigma_{m}^{z}\sigma_{l}^{-},$ (2)

the Hamiltonian takes a diagonal form,
$H=\sum_{k=1}^{N}\Lambda_{k}d_{k}^{\dagger}d_{k}+NB$ where
$\Lambda_{k}=-2B+2\cos\left[(\pi k)/(N+1)\right]$. The $2^{N}$ eigenenergies
are
$\epsilon_{l}\equiv\sum_{k=1}^{N}\Lambda_{k}\langle\psi_{l}|d_{k}^{\dagger}d_{k}|\psi_{l}\rangle+NB$
and the corresponding eigenstates are found

$|\psi_{l}\rangle=\prod_{k=1}^{N}(d^{\dagger}_{k})^{\alpha_{k}^{(l)}}\,|\Omega\rangle,$
(3)

where the binary integer number $\alpha_{k}^{(l)}\in\\{0,1\\}$ identifies
eigenenergy as
$\epsilon_{l}\equiv\sum_{k=1}^{N}\Lambda_{k}\alpha_{k}^{(l)}+NB$. The state
$|\Omega\rangle$ is the vacuum: $d_{k}|\Omega\rangle=0\,\forall k$. It is also
useful to know that $\langle\psi_{i}|\psi_{j}\rangle=\delta_{i,j}$. The energy
diagram of $\epsilon_{l}$ for $N=4$ as a function of $B$ is illustrated in
Fig.1(a).

(a) (b)

Figure 1: (a) The spectrum of $2^{4}$ energy levels for the $N=4$ XX spin
chains. The energies vary as a function of magnetic field $B$. Blue lines are
the energy change of the ground state. Energy level crossings occur at the
critical points in the ground state as well as in excited states. Ground state
entanglement is jumping as the state is switched from an entangled state to
another state. (b) The ground state energy per spin against the magnetic field
$B$ in the thermodynamic limit. The energy is plotted together with large spin
chain case, $N=50$. The continuous energy level crossings occur in the limit
at the region $0<B<1$.

##  II Ground state of XX spin chain

In this section, we discuss about the ground state of the XX model. The ground
energy state is the lowest energy state which is a function of the transverse
magnetic field $B$. Letting $B_{k}=\cos[k\pi/(N+1)]$ and defining the $k$-th
region, $B_{k+1}<B<B_{k}$, we can find the ground state
$|\psi_{g}^{k}\rangle=d_{k}d_{k-1}\cdot\cdot\cdot
d_{1}|\psi_{g}^{0}\rangle=\prod_{l=k+1}^{N}d_{l}^{\dagger}|\Omega\rangle$ and
its energy as $\epsilon_{g}^{k}=-(N-2k)B-2\sum_{l=1}^{k}\cos\left(\frac{\pi
l}{N+1}\right)$ (refer Son08  for detail). The index $k$ is an integer in
$1\leq k<N$ and $B_{k}$ represents the points where energy level crossings
occur. When $B<B_{N}$ or $B>B_{1}$, no other crossing exists and the ground
state is simply given by the fermion vacuum state. The ground state energy for
$N=4$ is plotted in Fig. 1 (a) by blue lines.

The ground state in the spin bases after $k$ level crossing can be obtained
recursively
$|\varphi_{g}^{k}\rangle=\prod_{k^{\prime}=1}^{k}\left[\sum_{l=1}^{N}S_{l}^{k^{\prime}}~{}\left(\prod_{m=1}^{l-1}\sigma^{z}_{m}\sigma_{l}^{-}\right)\right]|\uparrow\rangle^{\otimes
N}$ where $S_{l}^{k}\equiv\sqrt{2/(N+1)}\sin\left[(\pi kl)/(N+1)\right]$ and
the explicit form of the state is given as

$|\varphi_{g}^{k}\rangle=\left(\frac{2}{N+1}\right)^{\frac{k}{2}}\sum_{l_{1}<l_{2}<\cdot\cdot\cdot<l_{k}}C_{l_{1}l_{2}\cdot\cdot\cdot
l_{k}}|l_{1},l_{2},\cdots,l_{k}\rangle$ (4)

where $|l_{1},l_{2},\cdots,l_{k}\rangle$ is the state whose $l_{1}$-th,
$l_{2}$-th,$\cdots$, $l_{k}$-th indicate the position of flipped spin. The
amplitudes in the state are $C_{l_{1}l_{2}\cdot\cdot\cdot
l_{k}}=\sum_{P}(-1)^{P}\sin\left(\frac{\pi
P(1)l_{1}}{N+1}\right)\sin\left(\frac{\pi
P(2)l_{2}}{N+1}\right)\cdots\sin\left(\frac{\pi P(k)l_{k}}{N+1}\right)$. Here,
the sum extends over all the permutation of the numbers from 1 to k, (denoted
by $P(k)$). We point out that, at each crossing point (caused by the variation
of $B$), the ground state jumps discontinuously from one symmetric subspace to
the another, orthogonal to the previous one. To see the state explicitly, we
illustrate the ground states for $N=4$ in spin bases which are

$\displaystyle|\varphi_{g}^{0}\rangle$ $\displaystyle=$
$\displaystyle|\uparrow,\uparrow,\uparrow,\uparrow\rangle,~{}~{}~{}~{}|\varphi_{g}^{1}\rangle=a_{1}^{-}|\downarrow,\uparrow,\uparrow,\uparrow\rangle+a_{1}^{+}|\uparrow,\downarrow,\uparrow,\uparrow\rangle+a_{1}^{+}|\uparrow,\uparrow,\downarrow,\uparrow\rangle+a_{1}^{-}|\uparrow,\uparrow,\uparrow,\downarrow\rangle$
$\displaystyle|\varphi_{g}^{2}\rangle$ $\displaystyle=$ $\displaystyle
a_{2}\left(|\downarrow,\downarrow,\uparrow,\uparrow\rangle+2|\uparrow,\downarrow,\downarrow,\uparrow\rangle+2|\downarrow,\uparrow,\uparrow,\downarrow\rangle+|\uparrow,\uparrow,\downarrow,\downarrow\rangle+\sqrt{5}|\downarrow,\uparrow,\downarrow,\uparrow\rangle+\sqrt{5}|\uparrow,\downarrow,\uparrow,\downarrow\rangle\right)$
(5) $\displaystyle|\varphi_{g}^{3}\rangle$ $\displaystyle=$ $\displaystyle
a_{3}^{-}|\uparrow,\downarrow,\downarrow,\downarrow\rangle+a_{3}^{+}|\downarrow,\uparrow,\downarrow,\downarrow\rangle+a_{3}^{+}|\downarrow,\downarrow,\uparrow,\downarrow\rangle+a_{3}^{-}|\downarrow,\downarrow,\downarrow,\uparrow\rangle,~{}~{}~{}~{}|\varphi_{g}^{4}\rangle=|\downarrow,\downarrow,\downarrow,\downarrow\rangle$

where $a_{1}^{\pm}=-a_{3}^{\pm}=\frac{1}{2}\sqrt{1\pm\frac{1}{\sqrt{5}}}$ and
$a_{2}=-\frac{1}{2\sqrt{5}}$. From the state, it is clear that the superscript
of $\varphi$ indicates the number of down spins. The ground state at the
$k$-th region is composed of ${}_{N}C_{k}=N!/[k!(N-k)!]$ orthogonal vectors in
spin bases which are the possible choices of k spins, out of total N spins.
The ground states are in an orthogonal subspace,
$\langle\varphi_{g}^{k}|\varphi_{g}^{k^{\prime}}\rangle=\delta_{k,k^{\prime}}$.

It is found that the ground energy spectrum and the ground state become
continuous at the thermodynamic limit, $N\rightarrow\infty$. In the limit, the
sum in $\epsilon_{g}^{k}$ turns into a definite integral and thus the ground
state energy reads

$\displaystyle\lim_{N\rightarrow\infty}\frac{\epsilon_{g}(B)}{N}=\frac{2}{\pi}\left[B\left(\arccos
B-\frac{\pi}{2}\right)-\sqrt{1-B^{2}}\right].$ (6)

Within the critical region the ground state energy is analytic everywhere
except for $B=\pm 1$. From the finite size analysis we observe that such a
critical line becomes a dense set of level crossing (see Fig. 1 (b)) and
therefore is possible to be considered as a line of continuous QPT. At the
crossing points $B_{k}$, the state exists as a mixed state with equal mixture
of the states in a neighboring $k$-th region, $|\varphi_{g}^{k}\rangle$ and
$|\varphi_{g}^{k+1}\rangle$, i.e.

$\rho(B_{k})=\frac{1}{2}\left(|\varphi_{g}^{k}\rangle\langle\varphi_{g}^{k}|+|\varphi_{g}^{k+1}\rangle\langle\varphi_{g}^{k+1}|\right).$
(7)

Therefore, one can find that the state in the thermodynamics limit is also
varying from a mixed state into the other mixed state continuously as a
function of $B$. That is because the critical points $B_{k}$ is now continuous
function,
$B_{\omega}=\lim_{N\rightarrow\infty}\cos(k\pi/(N+1))=\cos(\pi\omega)$ where
$0<\omega<1$. Moreover, one would find that the mixedness of the state in the
limit is remained as a constant for any $B$ in $-1<B<1$ as
$\mbox{Tr}\rho(B)^{2}=1/2$. The mixedness (or purity) $1/2$ of the ground
state in the limit can also be proved from the limiting case of a thermal
state which will be discussed in the following section.

##  III XX Spin chain in thermal equilibrium

In this section, we investigate the state in a thermal equilibrium and discuss
about the properties related with quantum phase transition. At a finite
temperature, the state exists in a mixture of all the energy state distributed
by Boltzmann statistics. The state in a diagonal basis
$|\psi_{l}\rangle=\Pi_{k=1}^{N}(d^{\dagger}_{k})^{\alpha_{k}^{(l)}}\,|\Omega\rangle$,
$\alpha_{k}^{(l)}\in\\{0,1\\}$ is given as

$\rho_{T}=\sum_{l=1}^{2^{N}}p_{l}|\psi_{l}\rangle\langle\psi_{l}|$ (8)

where $p_{l}=\exp(-\beta\epsilon_{l})/Z$ is the Boltzmann distribution of the
thermal state with the partition function $Z=e^{-\beta
NB}\prod_{k=1}^{N}\left(1+e^{-\beta\Lambda_{k}}\right)$. In terms of the spin
basis, the thermal state further can be decomposed into the states which are
in a symmetric subspace as,

$\rho_{T}=\sum_{m=0}^{N}\sum_{r=1}^{{}_{N}C_{m}}q_{r}^{m}|\varphi_{r}^{m}\rangle\langle\varphi_{r}^{m}|.$
(9)

The index $m$ in the superscript indicates a symmetric subspace where vector
components of the state contain the $m$ number of spins flipped and the
subscript index $r$ identifies the ${{}_{N}C_{m}}=N!/[m!(N-m)!]$ orthogonal
vectors within the subspace. Thus, the state satisfies the orthonormal
condition,
$\langle\varphi_{r}^{m}|\varphi_{r^{\prime}}^{m^{\prime}}\rangle=\delta_{r^{\prime},r}\delta_{m^{\prime},m}$.
The state $|\varphi_{r}^{m}\rangle$ can be obtained from the $l$-th state
$|\psi_{l}\rangle$ using the transformation in (2),
$|\varphi_{r}^{m}\rangle=\prod_{k=1}^{N}\left[\sum_{j=1}^{N}S_{j}^{k}~{}\left(\prod_{i=1}^{j-1}\sigma^{z}_{i}\sigma_{j}^{-}\right)\right]^{\alpha_{k}^{(l)}}|\uparrow\rangle^{\otimes
N}$where $S_{j}^{k}\equiv\sqrt{2/(N+1)}\sin\left[(\pi jk)/(N+1)\right]$ and
$\alpha_{k}^{(l)}\in\\{0,1\\}$. The values of the label $l$ for the binary
vectors $\vec{\alpha}_{l}=\sum_{k}\alpha_{k}^{(l)}\hat{v}_{k}$ are determined
by $r$ and $m$ through an index match $l=r+\sum_{s=0}^{m-1}{{}_{N}C_{s}}$
under the constraints $\sum_{k=1}^{N}\alpha_{k}^{(r)}=m$. (It starts from
$l=1$ when $(r,m)=(1,0)$.) Similarly, the probabilities of the Boltzmann
distribution are given as $p_{l}\equiv
q_{r}^{m}=\exp(-\beta\epsilon_{r}^{m})/Z$. The lowest energy state for a fixed
$m$ become a ground state at a given region of $B$, i.e
$|\varphi_{1}^{m}\rangle\equiv|\varphi_{g}^{m}\rangle$. Furthermore, the
corresponding energy eigenvalues by the subspace indexes $m$ and $r$ can be
found as

$\epsilon_{l}\equiv\epsilon_{r}^{m}=-(N-2m)B-2\sum_{k=1}^{N}\cos[\pi
k/(N+1)]\alpha_{k}^{(r)}.$ (10)

This shows that the slop of the energy against $B$ is invariant for the states
in a given symmetric subspace, with a fixed $m$, and, thus, it also gives a
proof that the energy level crossings of excited states occur only between the
states in a different symmetric subspace. The level crossings of the excited
states for $N=4$ spins also can be seen in Fig. 1 (a).

(a) (b)

Figure 2: Distributions of thermal state population for the $N=2$ XX spin
chain when (a) $kT=0.1$ and (b) $kT=1$. The states $|\psi^{-}\rangle$ and
$|\psi^{+}\rangle$ are the singlet and the triplet. Critical behavior
disappears as the system goes into a thermal equilibrium.

As a special case, we inspect the density matrix of the thermally excited
state when $N=2$ which is in a form,

$\rho_{T}^{N=2}=p_{1}|\uparrow,\uparrow\rangle\langle\uparrow,\uparrow|+p_{2}|\psi^{-}\rangle\langle\psi^{-}|+p_{3}|\psi^{+}\rangle\langle\psi^{+}|+p_{4}|\downarrow,\downarrow\rangle\langle\downarrow,\downarrow|$
(11)

where
$|\psi^{\pm}\rangle=\frac{1}{\sqrt{2}}\left(|\uparrow,\downarrow\rangle\pm|\downarrow,\uparrow\rangle\right)$.
The state is expended in the three different symmetric subspaces, where there
is no spin flip (m=0), one spin flip (m=1) and two spin flips (m=2). Each
subspace contains ${}_{2}C_{0}$, ${}_{2}C_{1}$ and ${}_{2}C_{2}$ orthogonal
elements of states, $\\{|\uparrow,\uparrow\rangle\\}$,
$\\{|\psi^{-}\rangle,|\psi^{+}\rangle\\}$ and
$\\{|\downarrow,\downarrow\rangle\\}$. We plot the probability distribution of
the states $p_{l}$ in Fig.2. One would find that the distribution and the
partition function become analytic for any $B$ and $T$ as $T$ is away from
zero. If we investigate entanglement in the system, one would identify that
the state become separable when $4p_{1}p_{4}>(p_{2}-p_{3})^{2}$, (from the
negativity Peres , the negative eigenvalue of partially transposed state),
leading to a critical condition for temperature $kT>1.13459$. Interestingly,
the separability condition for the two qubit thermal state is independent of
the strength of magnetic field $B$ except when $T=0$. Thus, the singular
behavior of entanglement with respect to $B$ is washed out as the temperature
increased. This also has been depicted by the purity of the two qubit system
in Fig. 3.

(a) (b)

Figure 3: (a) Purity of two qubit system as a function of magnetic field $B$
and temperature $T$. (b) Derivatives of the purity as a function of $B$ at
different temperatures, $T=0.01$ (blue), $T=0.3$ (pink), $T=0.8$ (yellow) and
$T=2$ (green). At a low temperature region, the purity of the system shows
peaks near the critical points $B=\pm 1/2$. This is the point where the
derivative of purity w.r.t. B becomes singular when $T=0$. At the high
temperature region, the purity becomes monotonic convex function of B and the
derivative of the purity approaches to a linear function.

With the density matrix of the thermal state (8), we investigate a physical
property which may be directly related to the critical behavior of the system.
The mixedness of the thermal state for any $N$ is

$\mbox{Tr}\rho_{T}^{2}=\sum_{l}p_{l}^{2}=\prod_{k=1}^{N}\Big{[}1-(1+\cosh\beta\Lambda_{k})^{-1}\Big{]}.$
(12)

This characterizes how far the state is from a pure state. The purity is
plotted in Fig.3 for a small number of qubits ($N=2$) and for a large number
of qubits ($N=10$) in Fig.4. At the $T\rightarrow\infty$ limit
($\beta\rightarrow 0$), the purity becomes $1/2^{N}$. Thus, in the high
temperature region and the thermodynamic limit, $N\rightarrow\infty$, the
purity approaches to zero where the state is in a complete mixture of
infinitely many orthogonal states. At the opposite extreme, $T\rightarrow 0$,
the purity becomes either $1$ or $1/2$ depending on the $B$ value. It is $1/2$
when $B$ is $\cos[k\pi/(N+1)]$ and 1 otherwise. When $N\rightarrow\infty$, the
purity becomes $1/2$, i.e. $\lim_{N\rightarrow\infty}\lim_{T\rightarrow
0}\mbox{Tr}\rho_{T}^{2}=1/2$ in $-1<B<1$ because there exits at least a single
value of $B$ in the interval to make $\Lambda_{k}=0$ $\exists k$. In the
$|B|>1$ region, the purity is 1\. This proves that the ground state of the
infinite XX chain in the region $|B|<1$ is the equal mixture of the
neighboring states as (7). Furthermore, it is straightforward to see that
entanglement disappears in the region $|B|>1$ and at high temperature. The
separability of infinite XX chain with entanglement witness has been fully
treated in Hide07 .

In our analysis of the XX spin chain, it has been shown that the fundamental
difference between the thermal state and the ground state of the infinite
chain is only the degree of state mixedness. In both of the cases, the changes
of states are impossible to be detected by singularity due to the continuity
of state changes. In that sense, it can be pointed out that the energy level
crossing is a particular mode of the ground state change when the state is in
a pure state. In general, the state change can be detected by the change of
entanglement, up to local unitary, which is destroyed by mixedness of the
states. In fact, entanglement identifies the true quantum phase (or state) of
a system since it is the property which can exist only in quantum systems
whether they are pure or mixed Werner89 . Our approaches are general enough to
be used for the discussions about the QPT and related properties of any other
many particle systems.

Figure 4: Plot of the purity as a function of $B$ and $T$ when $N=10$. The
state is in a pure state when $\mbox{Tr}\rho^{2}=1$ and is in a completely
mixed state when $\mbox{Tr}\rho^{2}=1/2^{10}$. The purity of state is singular
at the critical points of $B$ where the state exists as a mixture of two
orthogonal symmetric states. It becomes smaller as $T$ is increased.

Acknowledgement\- This work is supported by the National Research Foundation &
Ministry of Education, Singapore.

## References

  * (1) S. Sachdev, Quantum Phase Transitions, Cambridge University Press (1999).
  * (2) S. Chakravarty, B. I. Halperin and D. R. Nelson, Phys. Rev. B39, 2344(1989).
  * (3) S. Sachdev and A. P. Young, Phys. Rev. Lett. 78, 2220 (1997).
  * (4) L. Amico, R. Fazio, A. Osterloh and V. Vedral, Rev. Mod. Phys. 80, 517 (2008).
  * (5) W. Son, L. Amico, F. Plastina and V. Vedral, arXiv:0807.1602 (2008).
  * (6) S. Katsura, Phys. Rev. 127, 1508 (1962).
  * (7) A. De Pasquale et al., Eur. Phys. J. Special Topics 160, 127 (2008), see also arxiv: 0801.1394 (2008).
  * (8) C. Brukner, V. Vedral, quant-ph/0406040 (2004); J. Hide, W. Son, I. Lawrie and V. Vedral, Phys. Rev. A76, 022319 (2007).
  * (9) A. Peres, Phys. Rev. Lett. 77, 1413 (1996); M. Horodecki, P. Horodecki and R. Horodecki, Phys. Rev. A223, 1 (1996).
  * (10) R. F. Werner, Phys. Rev. A40, 4277 (1989).


correlation $\sigma_{\text{max}}=\kappa\bar{N}_{S}\bar{N}_{S}^{\prime}$. Since
the ratio is negligible in the small $\bar{N}_{S}$, $\kappa$ regime,
$\hat{\rho}_{b1,b2}$ is not entangled, which is consistent with the qubit
approximation [13]

The phase-insensitive cross-correlation of the actual state matches the
maximal allowed phase-insensitive (classical) correlation
$\sigma_{\text{max}}$ of the Gaussian approximation for small $\bar{N}_{S}$
and $\kappa$. Moreover, the phase-sensitive correlation becomes negligible in
comparison to $\sigma_{\text{max}}$.

Plots 28, 27 and 26 together are sufficient to justify the claims made in the
qubit approximation in [13], as well as the assumption that the thermal
photons of the $\hat{b}$-modes are maximally correlated.

##  Appendix D Calculation of the combined thermal noise of the states
entering the Green-Machine of JDR2

In order to combine the mean fields $\alpha_{k}$ of the sum-frequency modes,
the $K$ $\gamma_{k}$ beam splitters of JDR2 pictured in Fig. 8 must be
adjusted to have transmissivities

$\gamma_{k}=\frac{\sum_{i=1}^{k}\alpha_{i}^{2}}{\sum_{i=1}^{k+1}\alpha_{i}^{2}}=\frac{1-(1-\kappa(1+\bar{N}_{S}^{\prime}))^{2k}}{1-(1-\kappa(1+\bar{N}_{S}^{\prime}))^{2(k+1)}}.$
(72)

To analyze how the thermal mean photons of the $\hat{b}_{k}$ modes combine
under the assumption that they have maximally classically correlated
covariance matrices, we associate to every beam splitter $\gamma_{k}$ an
imaginary beam-splitter with transmissivity $\gamma_{k}^{\prime}$ responsible
for splitting an imaginary parent beam (also a displaced thermal state) with
the combined thermal noise of modes $\hat{d}_{k}$ and $\hat{b}_{k+1}$ shown in
the diagram of the $k^{\text{th}}$ beam splitter (Fig. LABEL:fig:gammadiag).

Figure 29: Diagram of interference of maximally correlated thermal noise on
the $\gamma$ beam-splitters.

Denote the mean thermal noise of mode $\hat{d}_{k}$ by $\bar{N}_{T}^{(k)}$, as
in Fig. LABEL:fig:gammadiag. Then since $\gamma_{k-1}^{\prime}$ splits the
parent beam into modes $\hat{b}_{k}$ with thermal mean photon number
$\kappa\bar{N}_{S}\bar{N}_{S}^{\prime}$ and $\hat{d}_{k}$ with thermal mean
photon number $\bar{N}_{T}^{(k)}$,

$\gamma_{k}^{\prime}=\frac{\bar{N}_{T}^{(k)}}{\kappa\bar{N}_{S}\bar{N}_{S}^{\prime}+\bar{N}_{T}^{(k)}}.$
(73)

With the equivalence of diagrams LABEL:fig:gammadiag and LABEL:fig:gammadiag2,
the question of determining $\bar{N}_{T}^{(k)}$ assuming maximally correlated
inputs $\hat{b}_{k}$ and $\hat{d}_{k-1}$ is reduced to interfering a thermal
state with vacuum on a beam splitter of transmissivity
$\gamma_{k}^{\prime}\circ\gamma_{k}$, as pictured in Fig. 30.

Figure 30: The effective splitting operation corresponding to Fig.
LABEL:fig:gammadiag2

The value of the effective transmissivity
$\cos(\theta_{k}^{\prime}-\theta_{k})^{2}$ is

$\cos(\text{arcos}(\sqrt{\gamma_{k}^{\prime}})-\text{arcos}(\sqrt{\gamma_{k}}))^{2}=\Bigl{(}\sqrt{\gamma_{k}^{\prime}\gamma_{k}}+\sqrt{(1-\gamma_{k}^{\prime})(1-\gamma_{k})}\Bigr{)}^{2}$

, where $\gamma_{k}^{\prime}$ and $\gamma_{k}$ are themselves functions of
$\bar{N}_{T}^{(k)}$ and $\bar{N}_{S}$ as given by Eq.s (72) and (73). This
leads to a nonlinear recurrence relation for $\bar{N}_{T}^{(k)}$ given by

$\displaystyle\bar{N}_{T}^{(k+1)}$
$\displaystyle=\Bigl{(}2\bigl{(}\gamma_{k}^{\prime}\gamma_{k}+\sqrt{\gamma_{k}(1-\gamma_{k})\gamma_{k}^{\prime}(1-\gamma_{k}^{\prime})}\,\bigr{)}+1-\gamma_{k}-\gamma_{k}^{\prime}\Bigr{)}$
$\displaystyle\times(\bar{N}_{T}^{(k)}+\kappa\bar{N}_{S}\bar{N}_{S}^{\prime}),$
(74)

which is difficult to solve analytically, so we resort to a numerical
solution. $\bar{N}_{T0}$, the thermal mean photon number of the displaced
thermal states entering the Green Machine is $\bar{N}_{T}^{(K)}$ in the
notation of Fig. LABEL:fig:gammadiag. When iterating the recurrence relation
given by Eq. (74), we choose an arbitrary large $K$ value $(5000)$ to emulate
taking the limit as $K\rightarrow\infty$.

Figure 31: Plot of $\bar{N}_{S}\bar{N}_{S}^{\prime}/\bar{N}_{T}^{(K)}$ as a
function of $\bar{N}_{S}$

As Fig. 31 shows, the resulting value of $\bar{N}_{T}^{(K)}$ is only fraction
of the total thermal noise of the sum-frequency modes, approximately fixed at
$\bar{N}_{S}\bar{N}_{S}^{\prime}/7.611$ in the low signal brightness regime
where entanglement-assisted communication has the most advantage over
classical communication.

##  Appendix E Argument for the factor of $\sqrt{2}$ in the collective
treatement of the SFG output noise modes and sum-frequency modes

Let $r_{k}^{(i)}$, the squeezing parameter of the $k^{\text{th}}$ sandwiching
squeezer (depicted by dark blue boxes in Fig. 20) of the $i^{\text{th}}$ FF-
SFG module (depicted without squeezers by light blue boxes in Fig. 9), be
proportional to $\alpha_{k}$, the magnitude of the coherent amplitude of the
$k^{\text{th}}$ SFG gate in the SFG module, as

$r_{k}^{(i)}=\lambda_{i}\alpha_{k}$ (75)

where $\lambda_{i}\in\mathbb{R}$ is the proportionality constant. The
squeezing parameter is defined as in [31], such that $S(r_{k}^{(i)})$ applied
on the quadratures of the signal and idler modes $\hat{a}_{S}$ and
$\hat{a}_{I}$ results in

$\displaystyle\hat{a}_{S}^{{}^{\prime}}=\sqrt{1+(r_{k}^{(i)})^{2}}\;\hat{a}_{S}+r_{k}^{(i)}\hat{a}_{I}^{\dagger}$
(76)
$\displaystyle\hat{a}_{I}^{{}^{\prime}}=\sqrt{1+(r_{k}^{(i)})^{2}}\;\hat{a}_{I}+r_{k}^{(i)}\hat{a}_{S}^{\dagger}.$
(77)

It can be shown based on the single-cycle analysis in the supplementary
material of [31] that under BPSK phase modulation, the true output of the
$i^{\text{th}}$ FF-SFG module of JDR2 is approximately

$\hat{\rho}^{\pm}_{\text{true}}:=\mathopen{}\mathclose{{}\left[\bigotimes_{k=1}^{K}\hat{\rho}_{\text{th}}(0,((\lambda_{i}\pm
1)\alpha_{k})^{2})}\right]\otimes\hat{\rho}_{\text{th}}((\lambda_{i}\pm
1)\alpha_{0},\bar{N}_{T0}).$ (78)

What follows is an argument that when evaluating the Holevo capacity of the
FF-SFG receiver’s output, $\hat{\rho}^{\pm}_{\text{true}}$ can effectively be
treated as a single mode displaced thermal state

$\hat{\rho}^{\pm}_{\text{eff}}:=\hat{\rho}_{\text{th}}(\pm\sqrt{2}\alpha_{0},\bar{N}_{T0}).$
(79)

This argument is based on two lemmas, the first of which we leave as a
conjecture:

  1. 1.

The Holevo capacity for BPSK amplitude modulation of a displaced thermal state
is approachable with a joint-detection receiver that uses sequential code word
nulling followed by a nondestructive multi-mode vacuum-or-not measurement
(known to attain the Holevo capacity for coherent state bpsk modulation [1])
such as the receiver depicted in Fig. 22.

  2. 2.

The transition probability matrix of the channel induced by the vacuum-or-not
(VON) receiver where received code words are encoded in the states
$\hat{\rho}^{\pm}_{\text{eff}}$ is identical with that of the channel whose
received code words are encoded in the states
$\hat{\rho}^{\pm}_{\text{true}}$.

Proof of Lemma 2. First note that overall displacement of an ensemble will not
affect its Holevo capacity since displacement can be thought of as the limit
of a unitary transformation, so $\hat{\rho}^{\pm}_{\text{eff}}$ can be
redefined without loss of generality to be
$\hat{\rho}_{\text{th}}((\lambda_{i}\pm 1)\sqrt{2}\alpha_{0},\bar{N}_{T0})$.

Let $\mathbf{c}\in\\{\pm 1\\}^{L}$ be a random code word. Then set
$\vec{\lambda}$ to null $\hat{\rho}^{c_{l}}_{\text{true}}$ and
$\hat{\rho}^{c_{l}}_{\text{eff}}$, i.e. $\lambda_{l}=-c_{l}\;\forall
l\in\\{1...L\\}$. Let $\mathbf{b}\in\\{\pm 1\\}^{L}$ be the transmitted code
word. Then the true and effective received states are

$\displaystyle\hat{\rho}_{\mathbf{b},\text{true}}:=$
$\displaystyle\bigotimes_{l=1}^{L}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left[\bigotimes_{k=1}^{K}\hat{\rho}_{\text{th}}(0,(2\alpha_{k}\delta_{b_{l},c_{l}})^{2})}\right]\otimes\hat{\rho}_{\text{th}}(2\alpha_{0}(b_{l}-c_{l}),\bar{N}_{T0})}\right)$
(80)
$\displaystyle\hat{\rho}_{\mathbf{b},\text{eff}}:=\bigotimes_{l=1}^{L}\hat{\rho}_{\text{th}}(2\sqrt{2}\alpha_{0}(b_{l}-c_{l}),\bar{N}_{T0}),$
(81)

where $\delta$ is the Kronecker-Delta symbol.

Let $|\mathbf{0}_{n}\rangle$ denote the n-mode vacuum state and
$|\alpha\rangle$ a coherent state with mean field $\alpha$. Calling the
channel in which the received states are $\hat{\rho}_{\mathbf{b},\text{true}}$
the true channel and the channel in which the received states are
$\hat{\rho}_{\mathbf{b},\text{eff}}$ the effective channel, the transition
probability matrix of the true channel induced by the VON receiver is
determined, up to asymptotically insignificant residual terms associated with
the small perturbation of the “not vacuum” outcome, by the probabilities

$\displaystyle\langle\mathbf{0}_{L(K+1)}|$
$\displaystyle\hat{\rho}_{\mathbf{b},\text{true}}|\mathbf{0}_{L(K+1)}\rangle$
$\displaystyle=\prod_{l=1}^{L}\Bigl{(}\mathopen{}\mathclose{{}\left[\prod_{k=1}^{K}\langle
0|\hat{\rho}_{\text{th}}(0,(2\alpha_{k}\delta_{b_{l},c_{l}})^{2})|0\rangle}\right]$
$\displaystyle\hskip 36.135pt\times\langle
0|\hat{\rho}_{\text{th}}(2\alpha_{0}\delta_{b_{l},c_{l}},\bar{N}_{T0})|0\rangle\Bigr{)}$
(82)

and that of the effective channel is determined entirely by the probabilities

$\langle\mathbf{0}_{L}|\hat{\rho}_{\mathbf{b},\text{eff}}|\mathbf{0}_{L}\rangle=\prod_{l=1}^{L}\langle
0|\hat{\rho}_{\text{th}}(2\sqrt{2}\alpha_{0}\delta_{b_{l},c_{l}},\bar{N}_{T0})|0\rangle,$
(83)

which are enumerated by varying the transmitted code word $\mathbf{b}$.

So the proof of assumption 2 reduces to showing that the factors in the
outermost products of Eq.s (82) and (83) equal each other.

It is shown in section E.1 that the product over $k$ in Eq. (82) approaches
$\langle 0|2\alpha_{0}\delta_{b_{l},c_{l}}\rangle\langle
2\alpha_{0}\delta_{b_{l},c_{l}}|0\rangle$ in the large $K$ limit. Then eq. 82
can be reduced to write

$\displaystyle\langle\mathbf{0}_{L(K+1)}|\hat{\rho}_{\mathbf{b},\text{true}}|\mathbf{0}_{L(K+1)}\rangle=$
$\displaystyle\prod_{l=1}^{L}\langle
0|2\delta_{b_{l},c_{l}}\alpha_{0}\rangle\langle
2\delta_{b_{l},c_{l}}\alpha_{0}|0\rangle\times\langle
0|\hat{\rho}_{\text{th}}(2\alpha_{0}\delta_{b_{l},c_{l}},\bar{N}_{T0})|0\rangle$
$\displaystyle=$
$\displaystyle\prod_{l=1}^{L}e^{-4\alpha_{0}^{2}\delta_{b_{l},c_{l}}}\langle
0|\hat{\rho}_{\text{th}}(2\alpha_{0}\delta_{b_{l},c_{l}},\bar{N}_{T0})|0\rangle$
$\displaystyle=$
$\displaystyle\prod_{l=1}^{L}\frac{e^{-4\alpha_{0}^{2}\delta_{b_{l},c_{l}}}}{1+\bar{N}_{T0}}e^{-\frac{(2\alpha_{0})^{2}\delta_{b_{l}c_{l}}}{1+\bar{N}_{T0}}}$
$\displaystyle=$
$\displaystyle\prod_{l=1}^{L}\frac{1}{1+\bar{N}_{T0}}e^{-\frac{(8+4\bar{N}_{T0})\alpha_{0}^{2}\delta_{b_{l}c_{l}}}{1+\bar{N}_{T0}}}$
$\displaystyle\approx$
$\displaystyle\prod_{l=1}^{L}\frac{1}{1+\bar{N}_{T0}}e^{-\frac{8\alpha_{0}^{2}\delta_{b_{l}c_{l}}}{1+\bar{N}_{T0}}},$
(84)

where the approximation in the last step is justified since $\bar{N}_{S}\ll
1$, $\bar{N}_{B}\sim 10$, and $\bar{N}_{S}^{{}^{\prime}}\sim\bar{N}_{B}$ so
that $\bar{N}_{T0}=\bar{N}_{S}\bar{N}_{S}^{{}^{\prime}}/7.61\ll 1$.

On the other hand,

$\displaystyle\langle\mathbf{0}_{L}|\hat{\rho}_{\mathbf{b},\text{eff}}|\mathbf{0}_{L}\rangle$
$\displaystyle=\prod_{l=1}^{L}\frac{1}{1+\bar{N}_{T0}}e^{-\frac{(2\sqrt{2}\alpha_{0})^{2}\delta_{b_{l},c_{l}}}{1+\bar{N}_{T0}}}$
(85)

and it is apparent that the final expressions 84 and 85 are equal.

###  E.1 Vacuum probability of $K$ thermal states

Let $y=(1+\bar{N}_{S}^{{}^{\prime}})$ and $x=(1-\frac{1}{K}y)$. Then
$\alpha_{k}^{2}=\alpha_{1}^{2}x^{2(k-1)}$ and
$\alpha_{0}^{2}=\alpha_{1}^{2}\frac{1-e^{-2y}}{2y}$.

Figure 32: Numerical plot of expression 86 plotted as a function of $K$. The
values for $y$ and $\eta\bar{N}_{S}(1+\bar{N}_{S})$ are chosen to be $20$ and
$0.8$ respectively. The convergence occurs faster for smaller values of
$\eta\bar{N}_{S}(1+\bar{N}_{S})$.

Then, with the $q$-Pochhammer symbol $(a;q)_{n}$ defined as

$(a;q)_{n}:=\prod_{k=0}^{n-1}\mathopen{}\mathclose{{}\left(1-aq^{k}}\right),$

the product over $k$ in Eq. (82) is

$\displaystyle\prod_{k=1}^{K}\langle
0|\hat{\rho}_{\text{th}}(0,2\delta_{b_{l},c_{l}}\alpha_{k})|0\rangle$
$\displaystyle=$
$\displaystyle\prod_{k=0}^{K-1}\frac{1}{1+4\alpha_{k}^{2}\delta_{b_{l},c_{l}}}$
$\displaystyle=$
$\displaystyle\mathopen{}\mathclose{{}\left(\prod_{k=0}^{K-1}1+4\alpha_{1}^{2}x^{2k}\delta_{b_{l},c_{l}}}\right)^{-1}$
$\displaystyle=$
$\displaystyle\begin{cases}(-4\alpha_{1}^{2};x^{2})_{K}^{-1}&,\text{if
$b_{l}=c_{l}$}\\\ 1&,\text{otherwise}.\end{cases}$ (86)

Notice that $(-4\alpha_{1}^{2};x^{2})_{K}^{-1}$ depends on $K$ not only via
its subscript but also via $x$ and
$\alpha_{1}=\sqrt{\frac{1}{K}\eta\bar{N}_{S}(1+\bar{N}_{S})}$.

On the other hand,

$\displaystyle\langle 0|2\delta_{b_{l},c_{l}}\alpha_{0}\rangle\langle
2\delta_{b_{l},c_{l}}\alpha_{0}|0\rangle=$ $\displaystyle
e^{-4\alpha_{0}^{2}\delta_{b_{l},c_{l}}}$ $\displaystyle=$
$\displaystyle\begin{cases}e^{-4\alpha_{0}^{2}}&,\text{if $b_{l}=c_{l}$}\\\
1&,\text{otherwise.}\end{cases}$

Figure 32 shows that $\prod_{k=1}^{K}\langle
0|\hat{\rho}_{\text{th}}(0,2\alpha_{k}\delta_{b_{l},c_{l}})|0\rangle$
approaches $\langle 0|2\delta_{b_{l},c_{l}}\alpha_{0}\rangle\langle
2\delta_{b_{l},c_{l}}\alpha_{0}|0\rangle$ for large $K$.

##  Appendix F Evaluation of the entries of the transition probability matrix
for JDR2

The transition probability matrix $\mathbf{X}$ of the channel consists of
entries

$\displaystyle\mathbf{X}_{2j-1,2i-1}$
$\displaystyle=P((i,+)|RM_{(j,+)}):=\int_{0}^{T}P(i;t|RM_{(j,+)})P_{\text{Ken}_{\scriptstyle
i}}(+|RM_{(j,+)};t)$ (87a) $\displaystyle\mathbf{X}_{2j-1,2i}$
$\displaystyle=P((i,-)|RM_{(j,+)}):=\int_{0}^{T}P(i;t|RM_{(j,+)})P_{\text{Ken}_{\scriptstyle
i}}(-|RM_{(j,+)};t)$ (87b) $\displaystyle\mathbf{X}_{2j,2i-1}$
$\displaystyle=P((i,+)|RM_{(j,-)}):=\int_{0}^{T}P(i;t|RM_{(j,-)})P_{\text{Ken}_{\scriptstyle
i}}(+|RM_{(j,-)};t)$ (87c) $\displaystyle\mathbf{X}_{2j,2i}$
$\displaystyle=P((i,-)|RM_{(j,-)}):=\int_{0}^{T}P(i;t|RM_{(j,-)})P_{\text{Ken}_{\scriptstyle
i}}(-|RM_{(j,-)};t)$ (87d)

for $i,j=1,2,\cdots,L$, and

$\mathbf{X}_{k,2L+1}=P(\text{no clicks}|RM_{(\pm,k)})=P_{\text{erasure}}$ (88)

for $k=1,2,\cdots,2L$, where $P(i;t|RM_{(j,\pm)})$ is the probability that the
first click is detected by the ideal photon detector of the $i^{\text{th}}$
output mode at time $t$ given that the RM code word used for modulation was
the one inducing a $\pm$-signed pulse in the $j^{\text{th}}$ mode,
$P_{\text{Ken}_{\scriptstyle
i}}(\text{sign}_{\text{out}}|RM_{(j,\text{sign}_{\text{in}})};t)$ is the
probability that the $i^{\text{th}}$ Kennedy receiver decides
sign${}_{\text{out}}$ following a first click in mode $i$ at time $t$ given
that the RM code word used for modulation was the one that induces a
sign${}_{\text{in}}$-signed displacement in the $j^{\text{th}}$ mode (with
$\text{sign}_{\text{in}},\;\text{sign}_{\text{out}}\in\\{+,-\\}$), and $T$ is
the pulse duration.

Note that $P(i;t|RM_{(j,\pm)})$ and $P_{\text{Ken}_{\scriptstyle
i}}(\text{sign}_{\text{out}}|RM_{(j,\text{sign}_{\text{in}})};t)$ are
independent of $i$ and $j$ for $i\neq j$. The latter is also independent of
sign${}_{\text{in}}$ when $i\neq j$. Similarly $P(i;t|RM_{(i,\pm)})$ and
$P_{\text{Ken}_{\scriptstyle
i}}(\text{sign}_{\text{out}}|RM_{(i,\text{sign}_{\text{in}})};t)$ are
independent of $i$. So really there are 6 independent entries of $\mathbf{X}$
that need to be worked out. Restricting $j$ to $\\{1,2\\}$ and $i$ to
$\\{1,2,2n+1\\}$ is sufficient to cover all 6:

$\displaystyle\mathbf{X}_{11},\mathbf{X}_{12},\mathbf{X}_{21},\mathbf{X}_{22},\quad\leftarrow\,$
$\displaystyle(i=j=1)$
$\displaystyle\mathbf{X}_{14},\quad\quad\quad\leftarrow\,$
$\displaystyle(i=2;j=1)$ $\displaystyle\text{and
}\mathbf{X}_{1,2L+1}=P_{\text{erasure}}.$

Figure 33: Time slicing diagram corresponding to the event that the photo-
detector of the pulse-containing mode detects a click at time $t$, the
probability of which contributes to $P(i;t|RM_{(i,\pm)})$. The two photo
detectors and beam splitters is a (equivalent) representation of an individual
photo detector measuring the pulse during different windows of time.

The pulse carrying mode at the output of the Green Machine is in a displaced
thermal state $\hat{\rho}_{\text{th}}(\sqrt{L}\alpha_{0},\bar{N}_{T0})$ To
evaluate the integrands in Eq.s (87), the Green Machine output modes must be
sliced at time t after its onset. In general, this is equivalent to using a
beam splitter of transitivity $t/T$ to split the pulse into two weaker ones.
For a coherent state, this produces a product of two weaker coherent states,
leading to the relatively easy evaluation of the conditional probabilities,
but for a displaced thermal state, the time slicing produces a two-mode mixed
state.

A beam splitter of transmissivity $t/T$ input with vacuum in one port and
$\hat{\rho}_{\text{th}}(\sqrt{L}\alpha_{0},\bar{N}_{T0})=\frac{1}{\pi\bar{N}_{T0}}\int_{\mathbb{C}}d^{2}\gamma\;e^{-\frac{|\gamma-\sqrt{L}\alpha_{0}|^{2}}{\bar{N}_{T0}}}\,|\gamma\rangle\langle\gamma|$
in the other results in the state

$\displaystyle\frac{1}{\pi\bar{N}_{T0}}\int_{\mathbb{C}}d^{2}\gamma\;$
$\displaystyle
e^{-\scriptstyle\frac{|\gamma-\sqrt{L}\alpha_{0}|^{2}}{\bar{N}_{T0}}}$
$\displaystyle\times$
$\displaystyle|\scriptstyle\sqrt{\frac{t}{T}}\displaystyle\,\gamma\rangle\langle\scriptstyle\sqrt{\frac{t}{T}}\displaystyle\,\gamma|\otimes|-\scriptstyle\sqrt{1-\frac{t}{T}}\displaystyle\,\gamma\rangle\langle-\scriptstyle\sqrt{1-\frac{t}{T}}\displaystyle\,\gamma|.$

Evaluating the conditional probabilities appearing in the integrals in Eq.s
(87) requires splitting the output modes of the GM into three temporal slices
(a succession of two beam splitters), finding the probability that no clicks
occur within the first slice among all output modes of the GM and some clicks
occur in the middle slice of only one output, and taking the limit as the
middle slice size goes to zero. Thus, the conditional probabilities
constituting the integrands of Eq.s (87) are

$\displaystyle P(1;t|RM_{(1,\pm)})$ $\displaystyle=$
$\displaystyle\underset{\Delta t\rightarrow
0}{\lim}\text{Tr}\Bigl{(}\hat{\mathcal{M}}_{|0\rangle}^{2\,\dagger}$
$\displaystyle\hat{\mathcal{M}}_{|0\rangle}^{2}\hat{\rho}_{(t;\Delta
t)}^{(0)}\Bigr{)}^{L-1}\text{Tr}\Bigl{(}(\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{2\,\dagger}\hat{\mathcal{M}}_{|0\rangle}^{2})\hat{\rho}_{(t;\Delta
t)}^{(\pm 1)}\Bigr{)}$ (89a) $\displaystyle P(2;t|RM_{(1,\pm)})$
$\displaystyle=$ $\displaystyle\underset{\Delta t\rightarrow
0}{\lim}\text{Tr}\Bigl{(}\hat{\mathcal{M}}_{|0\rangle}^{2\,\dagger}$
$\displaystyle\hat{\mathcal{M}}_{|0\rangle}^{2}\hat{\rho}_{(t;\Delta
t)}^{(0)}\Bigr{)}^{L-2}\text{Tr}\Bigl{(}\hat{\mathcal{M}}_{|0\rangle}^{2\,\dagger}\hat{\mathcal{M}}_{|0\rangle}^{2}\hat{\rho}_{(t;\Delta
t)}^{(\pm
1)}\Bigr{)}\text{Tr}\mathopen{}\mathclose{{}\left((\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{2\,\dagger}\hat{\mathcal{M}}_{|0\rangle}^{2})\hat{\rho}_{(t;\Delta
t)}^{(0)}}\right)$ (89b) $\displaystyle P_{\text{Ken}_{\scriptstyle
1}}\mathopen{}\mathclose{{}\left(-|RM_{(1,\pm)};t}\right)$
$\displaystyle=\underset{\Delta t\rightarrow
0}{\lim}\text{Tr}\mathopen{}\mathclose{{}\left(\hat{\mathcal{M}}_{|0\rangle}^{3\,\dagger}\hat{\mathcal{M}}_{|0\rangle}^{3}\hat{\mathcal{D}}_{\beta(t)}^{3}\frac{(\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{2})\hat{\rho}_{(t;\Delta t)}^{(\pm
1)}(\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{2\,\dagger})}{\text{Tr}\mathopen{}\mathclose{{}\left((\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{2\,\dagger}\hat{\mathcal{M}}_{|0\rangle}^{2})\hat{\rho}_{(t;\Delta
t)}^{(1)}}\right)}\hat{\mathcal{D}}_{\beta(t)}^{3\,\dagger}}\right)$ (89c)
$\displaystyle P_{\text{Ken}_{\scriptstyle
1}}\mathopen{}\mathclose{{}\left(+|RM_{(1,\pm)};t}\right)$
$\displaystyle=1-P_{\text{Ken}_{\scriptstyle
1}}\mathopen{}\mathclose{{}\left(-|RM_{(1,\pm)};t}\right)$ (89d)
$\displaystyle P_{\text{erasure}}$
$\displaystyle=\text{Tr}\bigl{(}|0\rangle\langle
0|\hat{\rho}_{\text{th}}(\sqrt{L}\alpha_{0},\bar{N}_{T0})\bigr{)}\text{Tr}\bigl{(}|0\rangle\langle
0|\hat{\rho}_{\text{th}}(0,\bar{N}_{T0})\bigr{)}^{L-1}$ (89e) and additional
non-zero probabilities for the non-pulse-containing outputs $\displaystyle
P_{\text{Ken}_{\scriptstyle
2}}\mathopen{}\mathclose{{}\left(-|RM_{(1,\pm)};t}\right)=\underset{\Delta
t\rightarrow
0}{\lim}\text{Tr}\mathopen{}\mathclose{{}\left(\hat{\mathcal{M}}_{|0\rangle}^{3\,\dagger}\hat{\mathcal{M}}_{|0\rangle}^{3}\hat{\mathcal{D}}_{\beta(t)}^{3}\frac{(\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{2})\hat{\rho}_{(t;\Delta
t)}^{(0)}(\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{2\,\dagger})}{\text{Tr}\mathopen{}\mathclose{{}\left((\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{2\,\dagger}\hat{\mathcal{M}}_{|0\rangle}^{2})\hat{\rho}_{(t;\Delta
t)}^{(0)}}\right)}\hat{\mathcal{D}}_{\beta(t)}^{3\,\dagger}}\right)$ (89f)
$\displaystyle P_{\text{Ken}_{\scriptstyle
2}}\mathopen{}\mathclose{{}\left(+|RM_{(1,\pm)};t}\right)=1-P_{\text{Ken}_{\scriptstyle
2}}\mathopen{}\mathclose{{}\left(-|RM_{(1,\pm)};t}\right)$ (89g)

where

$\begin{split}\hat{\rho}_{(t;\Delta t)}^{(\sigma)}=e^{\frac{\scriptstyle\eta
L\alpha_{0}^{2}}{\scriptstyle\eta\bar{N}_{T0}+1}}\frac{\eta\bar{N}_{T0}+1}{\pi\bar{N}_{T0}}\int_{\mathbb{C}}d^{2}\gamma\;e^{-\frac{|\gamma-\sigma\cdot\sqrt{L}\alpha_{0}|^{2}}{\bar{N}_{T0}}}e^{-\eta|\gamma|^{2}}\,|0\rangle\langle
0|&\otimes|-\scriptstyle\sqrt{\frac{\Delta
t}{T}}\displaystyle\,\gamma\rangle\langle-\scriptstyle\sqrt{\frac{\Delta
t}{T}}\displaystyle\,\gamma|\\\ &\otimes|\scriptstyle\sqrt{1-\frac{t+\Delta
t}{T}}\displaystyle\,\gamma\rangle\langle\scriptstyle\sqrt{1-\frac{t+\Delta
t}{T}}\displaystyle\,\gamma|\end{split}$

is a green machine output mode (with $\sigma\in\\{-1,0,1\\}$) sliced at times
$t$ and $t+\Delta t$ (with a succession of splitting operations of
transmissivity $t/T$ and $\frac{\Delta t}{T-t}$ respectively as shown in Fig.
33 whose first slice has been measured to have no clicks,
$\hat{\mathcal{D}}_{\beta(t)}^{3}$ is the displacement operator acting on the
third slice with Kennedy nulling $\beta(t)$, and
$\hat{\mathcal{M}}_{|0\rangle}^{i}$ with $i\in\\{1,2,3\\}$ is the measurement
operator of the vacuum (no clicks) outcome for the $i^{\text{th}}$ slice of
the mode. For example $\hat{\mathcal{M}}_{|0\rangle}^{1}=|0\rangle\langle
0|\otimes\mathbf{\hat{I}}\otimes\mathbf{\hat{I}}$333One can check that
$\\{\hat{\mathcal{M}}_{|0\rangle}^{i},\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{i}\\}$ is a valid measurement, as it
satisfies the POVM condition. In fact, it is a projective measurement, as
$(\hat{\mathcal{M}}_{|0\rangle}^{i\,\dagger}\hat{\mathcal{M}}_{|0\rangle}^{i})^{2}=\hat{\mathcal{M}}_{|0\rangle}^{i\,\dagger}\hat{\mathcal{M}}_{|0\rangle}^{i}$
and $((\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{i})^{\dagger}(\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{i}))^{2}=(\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{i})^{\dagger}(\mathbf{\hat{I}}^{\otimes
3}-\hat{\mathcal{M}}_{|0\rangle}^{i})$..

Equations 89 evaluate to444Traces were taken in the coherent state basis

$\displaystyle P(1;t|RM_{(1,\pm)})$
$\displaystyle=\frac{e^{-\frac{\scriptstyle
t\displaystyle}{t\bar{N}_{T0}+T}L\alpha_{0}^{2}}}{T}\mathopen{}\mathclose{{}\left(\frac{T}{t\bar{N}_{T0}+T}}\right)^{L+2}(\frac{t}{T}\bar{N}_{T0}^{2}+\bar{N}_{T0}+L\alpha_{0}^{2})\,dt$
(90a) $\displaystyle P(2;t|RM_{(1,\pm)})$
$\displaystyle=\frac{e^{-\frac{\scriptstyle
t\displaystyle}{t\bar{N}_{T0}+T}L\alpha_{0}^{2}}}{T}\mathopen{}\mathclose{{}\left(\frac{T}{t\bar{N}_{T0}+T}}\right)^{L+2}(\frac{t}{T}\bar{N}_{T0}^{2}+\bar{N}_{T0})\,dt$
(90b) $\displaystyle P_{\text{Ken}_{1}}$ $\displaystyle(-|RM_{(1,\pm)};t)=$
$\displaystyle\quad\mathopen{}\mathclose{{}\left(\frac{t\bar{N}_{T0}+T}{T}}\right)^{3}(\frac{t}{T}\bar{N}_{T0}^{2}+\bar{N}_{T0}+L\alpha_{0}^{2})^{-1}(1+\bar{N}_{T0})^{-3}$
$\displaystyle\times
e^{\frac{t\,L\alpha_{0}^{2}}{t\bar{N}_{T0}+T}-\frac{L\alpha_{0}^{2}\pm
2\sqrt{L}\alpha_{0}\beta(t)\sqrt{\frac{T-t}{T}}+\beta(t)^{2}(1+\bar{N}_{T0}\frac{t}{T})}{1+\bar{N}_{T0}}}$
$\displaystyle\times\mathopen{}\mathclose{{}\left(\bar{N}_{T0}^{2}(1+\beta(t)^{2}\scriptstyle\frac{T-t}{T}\displaystyle)+\bar{N}_{T0}(1\mp
2\sqrt{L}\alpha_{0}\beta(t)\sqrt{\scriptstyle\frac{T-t}{T}\displaystyle})+L\alpha_{0}^{2}\;}\right)$
(90c) $\displaystyle P_{\text{Ken}_{1}}$
$\displaystyle(+|RM_{(1,\pm)};t)=1-P_{\text{Ken}_{\scriptstyle
1}}\mathopen{}\mathclose{{}\left(-|RM_{(1,\pm)};t}\right)$ (90d)
$\displaystyle\hskip
30.00005ptP_{\text{erasure}}=(1+\bar{N}_{T0})^{-L}e^{-\frac{L\alpha_{0}^{2}}{\scriptstyle\bar{N}_{T0}+1\displaystyle}},$
(90e) $\displaystyle P_{\text{Ken}_{2}}(-|RM_{(1,\pm)};t)$
$\displaystyle=\frac{(t\bar{N}_{T0}+T)^{2}}{T^{3}(\bar{N}_{T0}+1)^{3}}\bigl{(}(T-t)\bar{N}_{T0}\beta(t)^{2}+T(\bar{N}_{T0}+1)\bigr{)}e^{-\frac{\scriptstyle(t\bar{N}_{T0}+T)\beta(t)^{2}\displaystyle}{\scriptstyle\bar{N}_{T0}+1\displaystyle}}$
(90f) $\displaystyle P_{\text{Ken}_{2}}(+|RM_{(1,\pm)};t)$
$\displaystyle=1-P_{\text{Ken}_{2}}(-|RM_{(1,\pm)};t)$ (90g)

where the nulling $\beta(t)=\sqrt{L}\alpha_{0}$ is taken to be exact. To
evaluate the transition probabilities, we plug in expressions 90 into Eq.s
(87) and numerically integrate over the pulse duration.

## References

  * [1] J. Chen, J. L. Habif, Z. Dutton, R. Lazarus and S. Guha “Optical code word demodulation with error rates below the standard quantum limit using a conditional nulling receiver,” Nature Photon 6, 374–379 (2012).
  * [2] H. J. Kimble, “The quantum internet,” Nature 453, 1023–1030 (2008).
  * [3] S. Wehner, D. Elkouss, R. Hanson, “Quantum internet: A vision for the road ahead,” Science 362, 6412 (2018).
  * [4] S. Guha, H. Krovi, C. A. Fuchs, Z. Dutton, J. A. Slater, C. Simon, and W. Tittel, “Rate-loss analysis of an efficient quantum repeater architecture,” Phys. Rev. A 92, 022357 (2015).
  * [5] S. Muralidharan, L. Li, J. Kim, N. Lütkenhaus, M. D. Lukin and L. Jiang, “Optimal architectures for long distance quantum communication,” Nature Scientific Reports 6, 20463 (2016).
  * [6] S. Pirandola, “Satellite quantum communications: Fundamental bounds and practical security”, Phys. Rev. Research 3, 023130 (2021).
  * [7] S. Pirandola, “End-to-end capacities of a quantum communication network,” Communications Physics, vol. 2, article number 51 (2019).
  * [8] S. Das, S. Khatri, and J. P. Dowling, “Robust quantum network architectures and topologies for entanglement distribution,” Phys. Rev. A 97, 012335 (2018).
  * [9] M. Pant, H. Krovi, D. Towsley, L. Tassiulas, L. Jiang, P. Basu, D. Englund and S. Guha, “Routing entanglement in the quantum internet,” Nature npj Quantum Information 5, 25 (2019).
  * [10] R. V. Meter and S. J. Devitt, “The Path to Scalable Distributed Quantum Computing,” IEEE Computer 49, 9 (2016).
  * [11] A. K. Ekert, “Quantum cryptography based on Bell’s theorem,” Phys. Rev. Lett. 67, 661 (1991).
  * [12] A. M. Childs, “Secure assisted quantum computation ,” Quantum Information and Computation 5, 456 (2005).
  * [13] Q. Zhuang, Z. Zhang, J. H. Shapiro, “Distributed Quantum Sensing Using Continuous-Variable Multipartite Entanglement,” Phys. Rev. A 97, 032329 (2018).
  * [14] T. Proctor, P. Knott, and J. Dunningham, “Multiparameter Estimation in Networked Quantum Sensors,” Phys. Rev. Lett. 120, 080501 (2018).
  * [15] X. Guo, C.R. Breum, J. Borregaard, et al., “Distributed quantum sensing in a continuous-variable entangled network”, Nat. Phys. 1-4 (2019)
  * [16] Y. Xia, W. Li, W. Clark, D. Hart, Q. Zhuang and Z. Zhang, accepted in Physical Review Letters, arXiv:1910.08825 (2019)
  * [17] A. S. Holevo, IEEE Trans. Inf. Theory 44, 269 (1998).
  * [18] B. W. Schumacher and M. Westmoreland, Phys. Rev. A 56, 131 (1997).
  * [19] V. Giovannetti, S. Guha, S. Lloyd, L. Maccone, J. H. Shapiro, “Minimum output entropy of Bosonic channels: a conjecture,” Phys. Rev. A 70, 032315 (2004).
  * [20] V. Giovannetti, R. Garcia-Patron, N. J. Cerf, A. S. Holevo, “Ultimate classical communication rates of quantum optical channels,” Nature Photonics 8, 796-800 (2014).
  * [21] C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, IEEE Trans. Inf. Theory 48, 2637 (2002).
  * [22] V. Giovannetti, S. Lloyd, L. Maccone, P. W. Shor, ”Broadband channel capacities,” Phys. Rev. A 68, 062323 (2003).
  * [23] A. S. Holevo and R. F. Werner, “Evaluating capacities of bosonic Gaussian channels,” Physical Review A 63 (3) 032312 (2001).
  * [24] A. S. Holevo, “On entanglement assisted classical capacity,” Journal of Mathematical Physics 43 (9), 4326–4333 (2002).
  * [25] A. S. Holevo, “Entanglement-assisted capacity of constrained channels,” Proceedings of SPIE, First International Symposium on Quantum Informatics, 5128, 62–69 (2003).
  * [26] A. S. Holevo, “Entanglement-assisted capacities of constrained quantum channels,” Theory of Probability & Its Applications, 48 (2), 243–255 (2004).
  * [27] H. Shi, Z. Zhang, Q. Zhuang, ”Practical route to entanglement-enhanced communication over noisy Bosonic channels,” Phys. Rev. Applied 13, 034029 (2020).
  * [28] C. N. Gagatsos, M. S. Bullock, B. A. Bash, “Covert Capacity of Bosonic Channels”, IEEE Journal on Selected Areas in Information Theory, Volume 1, Issue 2, (2020).
  * [29] M. Sohma and O. Hirota, “Capacity of a channel assisted by two-mode squeezed states,” Phys. Rev. A 68, 022303 (2003).
  * [30] S. Guha and B. I. Erkmen, “Gaussian-state quantum-illumination receivers for target detection,” Phys. Rev. A 80, 052310 (2009).
  * [31] Q. Zhuang, Z. Zhang, J. H. Shapiro, “Optimum mixed-state discrimination for noisy entanglement-enhanced sensing,” Phys. Rev. Lett. 118, 040801 (2017).
  * [32] Q. Zhuang, “Quantum Ranging with Gaussian Entanglement”, Phys. Rev. Lett. 126, 240501 (2021).
  * [33] S. Guha, “Structured Optical Receivers to Attain Superadditive Capacity and the Holevo Limit,” Phys. Rev. Lett. 106, 240502 (2011).
  * [34] S. Guha, Q. Zhuang, and B. A. Bash, “Infinite-Fold Enhancement in Communications Capacity Using Pre-Shared Entanglement,” in Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), pp. 1835–1839 (2020).
  * [35] C. W. Helstrom, Quantum Detection and Estimation Theory, Academic, New York, (1976).
  * [36] S.J. Dolinar, Research Laboratory of Electronics, MIT, Quarterly Progress Report No. 111, pp. 115–120, (1973).
  * [37] M. Takeoka and S. Guha, “Capacity of optical communication in loss and noise with general quantum Gaussian receivers”, Phys. Rev. A 89, 042309 (2014).
  * [38] H. W. Chung, S. Guha, and L. Zheng, ”Capacity of optical communications over a lossy Bosonic channel with a receiver employing the most general coherent electro-optic feedback control,” Phys. Rev. A 96, 012320 (2017).
  * [39] M. Jarzyna and K. Banaszek, “Efficiency of Optimized Pulse Position Modulation with Noisy Direct Detection,” arXiv:1709.00030 [quant-ph] (2017).
  * [40] S. Guha, Z. Dutton, J. H. Shapiro, “On quantum limit of optical communications: concatenated codes and joint-detection receivers,” Proc. of the IEEE International Symposium on Information Theory (ISIT), 2011.
  * [41] R. S. Kennedy, “A near-optimum receiver for the binary coherent state quantum channel” MIT RLE Quarterly Progress Report, 108 219–225 (1973).
  * [42] M. M. Wilde, S. Guha, S.-H. Tan, and S. Lloyd, “Explicit capacity-achieving receivers for optical communication and quantum reading”, Proceedings of the 2012 IEEE International Symposium on Information Theory, Cambridge, MA, USA, pages 551-555 (2012).
  * [43] D. K. L. Oi, V. Potocek, and J. Jeffers, “Nondemolition Measurement of the Vacuum State or Its Complement”, Phys. Rev. Lett. 110, 210504 (2013).
  * [44] B. A. Bash, A. H. Gheorghe, M. Patel, J. L. Habif, D. Goeckel, D. Towsley, and S. Guha, “Quantum-secure covert communication on Bosonic channels,” Nature Communications 6, 8626 (2015).
  * [45] M. S. Bullock, C. N. Gagatsos, S. Guha, and B. A. Bash, accepted by IEEE Journal of Selected Areas in Communications (J-SAC), arXiv:1907.04228 (2019).
  * [46] C. N. Gagatsos, M. S. Bullock, and B. A. Bash, “Entanglement Assisted Covert Communication and its Coding Limits over Bosonic Channels,” arXiv:2002.06733 [quant-ph] (2020).
  * [47] S. Guha, Z. Dutton, J. H. Shapiro, “On quantum limit of optical communications: concatenated codes and joint-detection receivers,” Proc. of the IEEE International Symposium on Information Theory (ISIT), 2011.
  * [48] N. Rengaswamy, H. Pfister, K. P. Seshadreesan, S. Guha “Quantum-Message-Passing Receiver for Quantum-Enhanced Classical Communications,” arXiv:2003.04356 (2020).
  * [49] S. Guha, “Quantum limits of optical communications capacity”, unpublished memorandum, DARPA Information in a Photon project (2011).
  * [50] C. Delaney, K. P. Seshadreesan, I. MacCormack, A. Galda, S. Guha, P. Narang, “Demonstration of quantum advantage by a joint detection receiver for optical communications using belief propagation on a trapped-ion device,” arXiv:2021.1305 (2021).
  * [51] S.J. Dolinar, Research Laboratory of Electronics, MIT, Quarterly Progress Report No. 111, pp. 115–120, (1973).
  * [52] M. M. Wilde and S. Guha, “Polar codes for classical-quantum channels ”, IEEE Transactions on Information Theory vol. 59, no. 2, pages 1175-1187 (2013).
  * [53] S. Guha and M. M. Wilde, “Polar coding to achieve the Holevo capacity of a pure-loss optical channel”, Proceedings of the 2012 IEEE International Symposium on Information Theory (ISIT 2012), pages 546-550, Cambridge, MA, USA (2012).
  * [54] M. Takeoka, H. Krovi and S. Guha, “Achieving the Holevo capacity of a pure state classical-quantum channel via unambiguous state discrimination”, Proceedings of the 2013 IEEE International Symposium on Information Theory (ISIT 2013), DOI: 10.1109/ISIT.2013.6620209, Istanbul, Turkey (2013).
  * [55] H. Qi, Q. Wang, and M. M. Wilde, “Applications of position-based coding to classical communication over quantum channels,” Journal of Physics A, vol. 51, no. 44, page 444002, (2018).
  * [56] D. Ding, D. S. Pavlichin, M. M. Wilde, “Quantum Channel Capacities Per Unit Cost,” IEEE Transactions on Information Theory, vol. 65, no. 1, 418–435 (2019).
  * [57] A. Anshu, R. Jain, and N. A. Warsi, “A. Anshu, R. Jain, and N. A. Warsi, IEEE Trans. Inf. Theory 65, 1287 (2019).,” IEEE Trans. Inf. Theory 65, 1287 (2019).
  * [58] S. K. Oskouei, S. Mancini, M. M. Wilde, “Union bound for quantum information processing,” Proceedings of the Royal Society A, vol. 475, no. 2221, id 20180612, (2019).
  * [59] S.-H. Tan, B. I. Erkmen, V. Giovannetti, S. Guha, S. Lloyd, L. Maccone, S. Pirandola, and J. H. Shapiro, Phys. Rev. Lett. 101, 253601 (2008).
  * [60] L. Wang and G. W. Wornell, “A refined analysis of the Poisson channel in the high-photon-efficiency regime,” IEEE Transactions on Information Theory, Volume 60, Issue 7, (2014).
  * [61] F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds., “NIST Digital Library of Mathematical Functions,” Release 1.0.25 of 2019-12-15, http://dlmf.nist.gov/.
  * [62] N. Queseda et. al. “Simulating Realistic non-Gaussian state preparation,” Phys. Rev. A 100, 022341 (2019).
  * [63] P. Kok and S. L. Braunstein.“Multi-dimensional hermite polynomials in quantum optics,” Journal of Physics A: Mathematical and General, 34, 6185 (2001).
  * [64] B. Yurke, S. L. McCall and J. T. Klaude “SU(2) and SU(1,1) interferometers,” Phys. Rev. A 33, 4033 (1986).


# Bounding the multiplicities of eigenvalues of graph matrices in terms of
circuit rank using a new approach

Ahmet Batal  Department of Mathematics, Izmir Institute of Technology, 35430,
Urla, Izmir, TURKEY<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a simple undirected graph, $\theta(G)$ be the circuit rank of $G$,
$\eta_{M}(G)$ and $m_{M}(G,\lambda)$ be the nullity and the multiplicity of
eigenvalue $\lambda$ of a graph matrix $M(G)$, respectively. In the case
$M(G)$ is the adjacency matrix $A(G)$, (the Laplacian matrix $L(G)$, the
signless Laplacian matrix $Q(G)$) we find bounds to $m_{M}(G,\lambda)$ in
terms of $\theta(G)$ when $\lambda$ is an integer (even integer,
respectively). We also show that when $\alpha$ and $\lambda$ are rational
numbers similar bounds can be found for $m_{A_{\alpha}}(G,\lambda)$ where
$A_{\alpha}(G)$ is the generalized adjaceny matrix of $G$. Our bounds contain
only $\theta(G)$, not a multiple of it. Up to now only bounds of
$m_{A}(G,\lambda)$ (and later $m_{A_{\alpha}}(G,\lambda)$) have been found in
terms of the circuit rank and all of them contains $2\theta(G)$. There is only
one exception in the case $\lambda=0$. Wong et al. (2022) showed that
$\eta_{A}(G_{c})\leq\theta(G_{c})+1$, where $G_{c}$ is a connected cactus
whose blocks are even cycles. Our result, in particular, generalizes and
extends this result to the multiplicity of any even eigenvalue of A(G) of any
even connected graph $G$, and of any even eigenvalue of $L(G)$ and $Q(G)$ of
any connected graph $G$. They also showed that $\eta_{A}(G_{c})\leq 1$ when
every block of the cactus is an odd cycle. This also corresponds a special
case of our bound. We obtain these results by following a new approach.
Instead of bounding $\eta_{M}(G)$ we bound $\text{\tiny{$2$}-}\eta_{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu}(G)$ where $\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu$ is the binary matrix
whose entries are equal to the entries of $M$ modulo $2$ and
$\text{\tiny{$2$}-}\eta_{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu}(G)$ is the nullity of
$\mkern 1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu$ over the finite
field $\mathbb{F}_{2}$. We show that the latter nullity over $\mathbb{F}_{2}$
dominates not only $\eta_{M}(G)$, but also any $m_{M}(G,\lambda)$ for even
$\lambda$. Then to connect the multiplicities to $\theta(G)$ we use the fact
that $\text{\tiny{$2$}-}\eta_{\mkern
1.5mu\overline{\mkern-1.5muL\mkern-1.5mu}\mkern 1.5mu}(G)=\beta(G)+1$ for any
connected graph $G$ where $\beta(G)$ is the dimension of the bicycle space
which is a subspace of the cycle space of $G$.

###### Key words and phrases:

multiplicity, nullity, 2-nullity, bicycle space, cycle space, circuit rank

###### 2020 Mathematics Subject Classification:

05C50

## Introduction

Let $G$ be a simple undirected graph. We denote the number of vertices, edges,
and connected components of $G$ by $\mathrm{v}(G)$, $\mathrm{e}(G)$, and
$\mathrm{c}(G)$, respectively. Degree of a vertex is the number of its
incident edges. We say $G$ is even (odd) if all of its vertices have even
(odd) degree. We also denote the number of even degree vertices of $G$ by
$\mathrm{v}_{\mathrm{e}}(G)$, number of odd degree vertices of $G$ by
$\mathrm{v}_{\mathrm{o}}(G)$, and the number of even connected components of
$G$ by $\mathrm{c}_{\mathrm{e}}(G)$.

Let $V(G)=\\{v_{1},\cdots,v_{n}\\}$ be the vertex set of $G$. Then the
adjacency matrix of $G$ is the $n\times n$ symmetric matrix $A(G)=(a_{ij})$
where $a_{ij}=1$ if $v_{i}$ is adjacent to $v_{j}$ and $a_{ij}=0$, otherwise.
$A(G)+I$ is called the closed neighborhood matrix of $G$, where $I$ is the
$n\times n$ identity matrix. Let $D(G)$ be the $n\times n$ diagonal matrix
whose ith diagonal entry is equal to the degree of $v_{i}$. Then, the
Laplacian matrix of $G$ is $L(G)=D(G)-A(G)$, and the signless Laplacian matrix
of $G$ is $Q(G)=D(G)+A(G)$. We call all these matrices graph matrices of $G$.
In general, we say $M(G)$ is a graph matrix of $G$ if
$M(G)=\mathcal{D}(G)+tA(G)$ for some $n\times n$ diagonal matrix
$\mathcal{D}(G)$ and $t\in\mathbb{R}$. We denote the multiplicity of an
eigenvalue $\lambda$ of a graph matrix $M(G)$ by $m_{M}(G,\lambda)$. We denote
the kernel space of a matrix $M$ over $\mathbb{R}$ by $Ker(M)$ and over
$\mathbb{F}_{2}$ by $Ker_{2}(M)$. We denote their dimension by $\eta_{M}$ and
$\text{\tiny{$2$}-}\eta_{M}$ and call them the nullity and $2$-nullity of $M$,
respectively. In the case $M=M(G)$ is a graph matrix of $G$, we write
$\eta_{M}=\eta_{M}(G)$
($\text{\tiny{$2$}-}\eta_{M}=\text{\tiny{$2$}-}\eta_{M}(G)$) and call it the
nullity ($2$-nullity) of $G$ with respect to $M(G)$. If $M(G)=A(G)$ we may
just call it the nullity ($2$-nullity) of $G$. Clearly,
$\eta_{M}(G)=m_{M}(G,0)$ for all graph matrices $M$. Similarly, we denote the
column space of a matrix $M$ over $\mathbb{R}$ by $Col(M)$, over
$\mathbb{F}_{2}$ by $Col_{2}(M)$ and denote its rank over $\mathbb{R}$ by
$r_{M}$, over $\mathbb{F}_{2}$ by $\text{\tiny{$2$}-}r_{M}$.

Let $E(G)=\\{uv\;|\;\text{u is adjacent to v}\\}$ be the edge set of $G$. Let
us denote the collection of subsets of $E(G)$ by $Edge(G)$. It is a vector
space over $\mathbb{F}_{2}$ where addition is taken as the symmetric
difference operation of sets. Two well known subspaces of $Edge(G)$ are the
cycle and cut spaces. The cycle space $Cycle(G)$ consists of even subgraphs of
$G$. We call the dimension $\theta(G)$ of $Cycle(G)$ the circuit rank of $G$.
It satisfies

$\theta(G)=(\text{e}-\text{v}+\text{c})(G).$

On the other hand, every subset of vertices $S$ of $V(G)$ determines a cut set
of edges $\\{uv\in E(G)|\;u\in S,\;v\in S^{c}\\},$ and the collection of all
cut sets (or spanning cut subgraphs) $Cut(G)$ is the orthogonal complement of
$Cycle(G)$. The intersection of $Cycle(G)$ and $Cut(G)$ is the bicycle space
$Bicycle(G)$ and we denote its dimension by $\beta(G)$.

Bounding the nullity of any graph (or a specific graph type) using some graph
parameters and characterizing the graphs whose nullities attain the given
bound is an active area of research of graph theory (See [14], [15], [16],
[21], [18], [25], [22], [20], [26], [24], [27], [19], [28], [29], [30], [31],
[32], [33], [23], [34], [35], [38], [39], [36], [17], [40]). In particular,
finding bounds to $\eta_{A}(G)$ as well as $m_{A}(G,\lambda)$ in terms of
$\theta(G)$ plus some additional graph parameters gained attention in recent
years (See [10], [7], [5], [11], [1], [3], [37], [8], [2], [6], [9]). One of
the pioneering work in this direction is the work of Ma, Wong, and Tian [1],
in which they showed that for all graphs $G$ which does not contain isolated
vertices,

(1) $\eta_{A}(G)\leq(2\theta+p)(G),$

where $p(G)$ is the number of pendant (degree one) vertices of $G$. Then the
generalization of this bound to any $m_{A}(G,\lambda)$ is obtained by Wang et
al. in [3]. However, considering the facts that $\mathrm{v}(G)$ is the trivial
bound of $\eta_{A}(G)$, and $2\theta(G)$ involves the term
$2\mathrm{e}(G)-2\mathrm{v}(G)$, it is clear that this estimate is not
applicable if $\mathrm{e}(G)\geq 3\mathrm{v}(G)/2$. So it would be better if
we can replace the term $2\theta(G)$ by $\theta(G)$ in the bound of
$\eta_{A}(G)$ at the cost of some additional terms if necessary. Although this
new estimate may not be stronger than (1) for all graph types, it would still
be applicable to important graph types where (1) is not applicable. As far as
we know, the only result which gives a bound of $\eta_{A}(G)$ involving
$\theta(G)$ instead of $2\theta(G)$ was obtained in a recent paper [2] of Wong
et al. However, they have been able to obtain this bound by putting strict
assumptions on $G$. More precisely, they showed that if $G$ is a bipartite
graph consisting of cycle blocks (thus, necessarily an even graph) then

(2) $\eta_{A}(G)\leq(\theta+\mathrm{c})(G).$

As we will see in a moment these assumptions are not necessary. Indeed, (2)
holds true for all even graphs $G$.

It seems like the classic approach which has been used up to now by the above
authors has its own limits which makes it very hard if not impossible to
obtain bounds of $\eta_{A}(G)$ involving $\theta(G)$ instead of $2\theta(G)$
for an arbitrary graph $G$. By classic approach we mean that the methods which
use main inequalities satisfied by $\eta_{A}(G)$ under some graph operations
and graph theoretical arguments which connects $\eta_{A}(G)$ to $\theta(G)$.

In this paper we introduce a new approach to connect $\eta_{A}(G)$ to
$\theta(G)$ which we think more natural and also shorter than the classical
one. The idea lies in the following simple observation:

$\eta_{A}(G)\leq\text{\tiny{$2$}-}\eta_{A}(G)$

for all graphs $G$ (See Lemma 1.1). So instead of bounding $\eta_{A}(G)$
directly, we can try to bound $\text{\tiny{$2$}-}\eta_{A}(G)$ by $\theta(G)$
instead. This sounds more natural because both $\text{\tiny{$2$}-}\eta_{A}(G)$
and $\theta(G)$ are dimensions of linear spaces over the same field
$\mathbb{F}_{2}$, namely $Ker_{2}(A(G))$ and $Cycle(G)$. So one can connect
$\text{\tiny{$2$}-}\eta_{A}(G)$ and $\theta(G)$ more easily if one can find a
linear algebraic correspondence between these spaces (or between spaces
related to them). Indeed there is such a correspondence in the case $G$ is an
even graph. To explain this let us write $\mkern
1.5mu\overline{\mkern-1.5mum\mkern-1.5mu}\mkern 1.5mu:=m\mod{2}$ for an
integer $m$ and $\mkern 1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu:=(\mkern 1.5mu\overline{\mkern-1.5mum_{ij}\mkern-1.5mu}\mkern 1.5mu)$
for an integer valued matrix $M=(m_{ij})$. Then $Ker_{2}(A(G))$ is equal to
$Ker_{2}(\mkern 1.5mu\overline{\mkern-1.5muL\mkern-1.5mu}\mkern 1.5mu(G))$ if
$G$ is even and a well known connection ([12, Lemma 14.15.3]) between the
latter space and the bicycle space gives us

(3)
$\text{\tiny{$2$}-}\eta_{A}(G)=(\beta+\text{c})(G)\leq(\theta+\text{c})(G),$

when $G$ is an even graph. Hence we immediately obtain (2) for any even graph
$G$ using this approach. Moreover, we can generalize (3) to any graph by a
simple argument at the cost of adding the term $\mathrm{v}_{\mathrm{o}}(G)$ to
the right hand side (See Theorem 1.8). This shows how powerful and practical
following this approach might be considering the fact that obtaining (2) even
only for very special graphs takes effort when we follow the classical
approach.

More importantly, applicability of this approach is not restricted to finding
bounds of $\eta_{A}(G)$. Indeed, $\text{\tiny{$2$}-}\eta_{A}(G)$ bounds not
only $\eta_{A}(G)$ but also any $m_{A}(G,\lambda)$ when $\lambda$ is an even
integer (See Lemma 1.1). On the other hand, for odd eigenvalues $\lambda$, we
have $m_{A}(G,\lambda)\leq\eta_{A+I}(G)$, where the latter nullity of $G$ with
respect to $A(G)+I$ can be bounded by
$(\theta+\text{c}+\mathrm{v}_{\mathrm{e}})(G)$ (See Theorem 1.8).

Adding the terms $\mathrm{v}_{\mathrm{e}}(G)$ or $\mathrm{v}_{\mathrm{o}}(G)$
to the corresponding bounds in the general case seems inevitable but there is
a graph parameter that we call $\tau(G)$ which we can subtract from these
bounds as well. To define it, let us say a cycle is even (odd) if it has even
(odd) number of edges and two cycles are disjoint if they do not share any
edge. Then we define $\tau(G)$ as the maximum of the cardinalities of the sets
of disjoint odd cycles of $G$. The reason why we can subtract $\tau(G)$ from
the bounds is because of the fact that $\tau(G)$ corresponds to the dimension
of a subspace of $Cycle(G)$ which intersects $Bicycle(G)$ only trivially (See
Lemma 1.3 and the discussion above it).

Similarly, the same approach can be directly used to estimate the
multiplicities of the integer eigenvalues of $A(G)+I$, $L(G)$ and $Q(G)$ as
well. More precisely, we have the following theorem as our main result.

######  Theorem 0.1.

Let $G$ be a graph and $\lambda$ be an integer eigenvalue of the corresponding
graph matrix. Then

$\displaystyle m_{A}(G,\lambda)$
$\displaystyle\leq(\theta-\tau+\mathrm{v}_{\mathrm{o}}+2\mathrm{c}_{\mathrm{e}}-\mathrm{c}+2i)(G)$
$\displaystyle\text{if $\lambda$ is even},$ $\displaystyle m_{A}(G,\lambda)$
$\displaystyle\leq(\theta-\tau+\mathrm{v}_{\mathrm{e}}+\mathrm{c})(G)$
$\displaystyle\text{if $\lambda$ is odd},$ $\displaystyle
m_{L}(G,\lambda),m_{Q}(G,\lambda)$
$\displaystyle\leq(\theta-\tau+\mathrm{c})(G)$ $\displaystyle\text{if
$\lambda$ is even},$ $\displaystyle m_{L}(G,\lambda),m_{Q}(G,\lambda)$
$\displaystyle\leq(\mathrm{v}-\beta-\mathrm{c})(G)$ $\displaystyle\text{if
$\lambda$ is odd},$

where $i(G)=0$ if $G$ is even and $i(G)=1$ otherwise.

The proof is given in Section $1$. Note that for $m_{L}(G,\lambda)$ and
$m_{Q}(G,\lambda)$ when $\lambda$ is odd we cannot obtain a bound in terms of
$\theta(G)$ unlike the even case. This is something expected since it is known
that $m_{L}(G,1)\geq(p-q)(G)$ where $q(G)$ is the number of vertices adjacent
to a pendant vertex of $G$ [13]. Hence, even if $\theta(G)$ is small,
$m_{L}(G,\lambda)$ can be very large for odd $\lambda$. It might be the case
that the multiplicities of odd eigenvalues are bounded in terms of $\theta(G)$
with some additional terms involving at least $(p-q)(G)$. However, such a
bound, if it exists, cannot be found using solely our approach, it must
involve some other arguments as well.

We already mentioned that Wang et al. in [3] generalized (1) to any
$m_{A}(G,\lambda)$. Later Shuchao and Wei in [5] generalized the latter result
further to any $m_{A_{\alpha}}(G,\lambda)$, where $A_{\alpha}(G)$ is the graph
matrix defined by $A_{\alpha}(G):=\alpha D(G)+(1-\alpha)A(G)$ where
$0\leq\alpha\leq 1.$ $A_{\alpha}(G)$ matrix was first introduced by Nikiforov
in [4] and its spectral analysis gained a lot of attention later on. We show
that our approach is applicable to this graph matrix as well in the case where
both $\alpha$ and $\lambda$ are rational numbers. The bound of
$m_{A_{\alpha}}(G,\lambda)$ changes drastically depending on the
representations of $\alpha$ and $\lambda$ in their lowest forms as ratio of
two integers. The results are summarized Section $2$ in Theorem 2.1.

In the last section we give examples of some types of graphs attaining the
corresponding bounds in Theorem 0.1.

##  1\. Proof of Theorem 0.1

######  Lemma 1.1.

Let $M$ be an integer valued matrix. Then

$\eta_{M}\leq\text{\tiny{$2$}-}\eta_{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu}.$

Moreover, if $M$ is a graph matrix of $G$, then

$\displaystyle\quad\quad\quad\quad\quad\quad m_{M}(G,\lambda)$
$\displaystyle\leq\text{\tiny{$2$}-}\eta_{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu}(G)$
$\displaystyle\text{if $\lambda$ is an even integer},$
$\displaystyle\quad\quad\quad\quad\quad\quad m_{M}(G,\lambda)$
$\displaystyle\leq\text{\tiny{$2$}-}\eta_{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu+I}(G)$
$\displaystyle\text{if $\lambda$ is an odd integer}.$

###### Proof.

For the proof of the first inequality, we will show that
$r_{M}\geq\text{\tiny{$2$}-}r_{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu}$. Then the result
follows by the rank nullity theorem.

Take a set of column vectors $\\{c_{1},\dots,c_{k}\\}$ of $M$ such that
$\\{\mkern 1.5mu\overline{\mkern-1.5muc_{1}\mkern-1.5mu}\mkern
1.5mu,\dots,\mkern 1.5mu\overline{\mkern-1.5muc_{k}\mkern-1.5mu}\mkern
1.5mu\\}$ is a linearly independent set in $\mathbb{F}_{2}^{n}$ where $n$ is
the number of rows of $M$. Consider the following equation

(4) $\alpha_{1}c_{1}+\cdots+\alpha_{k}c_{k}=0,$

where $\alpha_{i}\in\mathbb{R}$ for $i=1,\dots,k$. Since each $c_{i}$ has
integer entries, (4) has a nontrivial solution in $\mathbb{R}$ if and only if
it has a nontrivial solution in $\mathbb{Z}$. So without loss of generality,
we can assume all $\alpha_{i}$’s are integer. Dividing (4) by a suitable power
of $2$ if necessary, we can further assume that all $\alpha_{i}$’s are
integers such that not all of them are even unless all of them are zero. Then
the corresponding column vectors in $\mathbb{F}_{2}^{n}$ satisfy

(5) $\mkern 1.5mu\overline{\mkern-1.5mu\alpha_{1}\mkern-1.5mu}\mkern
1.5mu\mkern 1.5mu\overline{\mkern-1.5muc_{1}\mkern-1.5mu}\mkern
1.5mu+\cdots+\mkern 1.5mu\overline{\mkern-1.5mu\alpha_{k}\mkern-1.5mu}\mkern
1.5mu\mkern 1.5mu\overline{\mkern-1.5muc_{k}\mkern-1.5mu}\mkern 1.5mu=0,$

which has only the trivial solution since $\\{\mkern
1.5mu\overline{\mkern-1.5muc_{1}\mkern-1.5mu}\mkern 1.5mu,\dots,\mkern
1.5mu\overline{\mkern-1.5muc_{k}\mkern-1.5mu}\mkern 1.5mu\\}$ is linearly
independent. This means every $\alpha_{i}$ is even and this is only possible
if every $\alpha_{i}$ is zero by our assumption. Hence,
$\\{c_{1},\dots,c_{k}\\}$ is a linearly independent set of $\mathbb{R}^{n}$.
This proves $r_{M}\geq\text{\tiny{$2$}-}r_{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu}$.

For the last two inequalities just note that

$m_{M}(G,\lambda)=\eta_{M-\lambda I}(G)\leq\text{\tiny{$2$}-}\eta_{\mkern
1.5mu\overline{\mkern-1.5muM-\lambda I\mkern-1.5mu}\mkern
1.5mu}(G)=\text{\tiny{$2$}-}\eta_{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu+\mkern
1.5mu\overline{\mkern-1.5mu\lambda\mkern-1.5mu}\mkern 1.5muI}(G).$

∎

Let $P(G):=\mkern 1.5mu\overline{\mkern-1.5muL\mkern-1.5mu}\mkern
1.5mu(G)=\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu(G)$. We
call it the parity Laplacian matrix of $G$. We have the following elementary
fact which can be found in [12, Lemma 14.15.3]:

######  Proposition 1.2.

$($[12]$)$ For any graph $G$

(6) $\text{\tiny{$2$}-}\eta_{P}(G)=(\beta+\mathrm{c})(G).$

Since the bicycle space is a subspace of the cycle space, the above lemma
immediately implies

(7) $\text{\tiny{$2$}-}\eta_{P}(G)\leq(\theta+\mathrm{c})(G).$

However this inequality can be improved. Note that, in general, $Bicycle(G)$
is a proper subspace of $Cycle(G)$. It consists of those even subgraphs of $G$
which are cuts as well. Let us call these subgraphs even cuts of $G$. Since
$Cycle(G)$ and $Cut(G)$ are orthogonal to each other under the dot product
“$\cdot$”, defined by $A\cdot B:=|A\cap B|\mod 2$, a necessary condition to be
an even cut is to be orthogonal to every even subgraph. In other words, an
even cut must share even number of edges with every even subgraph including
itself. So trivially, no odd cycle or no subgraph including an odd cycle can
be an even cut. This observation leads us to the following lemma.

######  Lemma 1.3.

For any graph $G$,

$\beta(G)\leq(\theta-\tau)(G).$

###### Proof.

Let $\mathcal{T}$ be a set of disjoint odd cycles of $G$ with
$|\mathcal{T}|=\tau(G)$. Note that the span of $\mathcal{T}$,
$Span(\mathcal{T})$, is a subspace of $Cycle(G)$ with dimension $\tau(G)$ and
$Bicycle(G)\cap Span(\mathcal{T})=\\{\emptyset\\}$, where $\emptyset$ denotes
the empty spanning subgraph of $G$. Therefore, $Bicycle(G)+Span(\mathcal{T})$
is a subspace of $Cycle(G)$ with dimension $(\beta+\tau)(G)$. Hence,
$(\beta+\tau)(G)\leq\theta(G)$. ∎

Proposition 1.2 and Lemma 1.3 give us the following.

######  Theorem 1.4.

For any graph $G$

(8) $\text{\tiny{$2$}-}\eta_{P}(G)\leq(\theta-\tau+\mathrm{c})(G).$

Note that $P(G)=\mkern 1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu(G)+A(G)$ where $\mkern 1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu$ is the diagonal matrix whose diagonal entries are the parity of the
degrees of the corresponding vertices. Hence, $P(G)=A(G)$ if $G$ is even, and
$P(G)=A(G)+I$ if $G$ is odd. Therefore, from (8) we obtain

(9) $\displaystyle\text{\tiny{$2$}-}\eta_{A}(G)$
$\displaystyle\leq(\theta-\tau+\text{c})(G)$ $\displaystyle\text{if $G$ is
even},$ (10) $\displaystyle\text{\tiny{$2$}-}\eta_{A+I}(G)$
$\displaystyle\leq(\theta-\tau+\text{c})(G)$ $\displaystyle\text{if $G$ is
odd}.$

######  Remark 1.5.

Recently, Wong et al. in [2] proved that $\eta_{A}(G)\leq\theta(G)+1$ for
bipartite, cycle spliced graphs (connected even graphs consisting of cycle
blocks). On the other hand, Lemma 1.1 and (9) show us that this is true for
any connected even graph. They also showed in [2, Theorem 1.2] that if all
cycles of a cycle spliced graph are odd, then $\eta_{A}(G)\leq 1$. This fact
can also be realized by our approach. Indeed, in such a case
$\theta(G)=\tau(G)$. Therefore, Lemma 1.1, (9) and connectedness of $G$ imply
$\eta_{A}(G)\leq 1$.

In the view of Lemma 1.1, we will use (8), (9), and (10) to estimate not only
the nullities but in general the multiplicities of the integer eigenvalues of
the adjacency, the Laplacian, and the signless Laplacian matrices of $G$.
However, since (9) and (10) are true only for even and odd graphs,
respectively, to be able to benefit from them for an arbitrary graph $G$, we
construct an even and an odd graph using $G$ whose graph parameters are
related to the graph parameters of $G$ in a suitable way.

######  Definition 1.6.

For a graph $G$ we define ${G_{even}}$ as $G$ itsef if $G$ is even and
otherwise as the graph obtained from $G$ by connecting every odd degree vertex
of $G$ to a unique external vertex by an edge. We define ${G_{odd}}$ as the
graph obtained from $G$ by adding a pendant edge to every even degree vertex
of $G$.

It is clear that $G_{odd}$ is an odd graph. Also $G_{even}$ is an even graph
by the handshaking lemma. Let $i(G)$ be the binary valued function which takes
the value $0$ if $G$ is even and $1$ if $G$ is odd. Then we have the following
lemma.

######  Lemma 1.7.

Let $G$ be a graph and $M$ be a binary valued graph matrix of $G$. Then the
followings hold.

$\displaystyle i)\;$
$\displaystyle\text{\tiny{$2$}-}\eta_{M}(G_{even})\geq(\text{\tiny{$2$}-}\eta_{M}-i)(G),$
$\displaystyle v)\;$
$\displaystyle\text{\tiny{$2$}-}\eta_{M}(G_{odd})\geq(\text{\tiny{$2$}-}\eta_{M}-\mathrm{v}_{\mathrm{e}})(G),$
$\displaystyle ii)\;$
$\displaystyle\theta(G_{even})=(\theta+\mathrm{v}_{\mathrm{o}}+\mathrm{c}_{\mathrm{e}}-\mathrm{c})(G),$
$\displaystyle vi)\;$ $\displaystyle\theta(G_{odd})=\theta(G),$ $\displaystyle
iii)\;$ $\displaystyle\mathrm{c}(G_{even})=(\mathrm{c}_{\mathrm{e}}+i)(G),$
$\displaystyle vii)\;$ $\displaystyle\mathrm{c}(G_{odd})=\mathrm{c}(G),$
$\displaystyle iv)\;$ $\displaystyle\tau(G_{even})\geq\tau(G),$ $\displaystyle
viii)\;$ $\displaystyle\tau(G_{odd})=\tau(G).$

###### Proof.

We will only prove (i), (ii), (iii), and (v) since the rest are obvious.

For (i) and (v) let $H-v$ denote the induced subgraph obtained from a graph
$H$ by removing one of its vertices $v$. Then the binary graph matrix $M(H-v)$
is the principal submatrix of $M(H)$ obtained by deleting the row and column
of $M(H)$ corresponding to the vertex $v$. It is an elementary fact that in
such a case
$\text{\tiny{$2$}-}\eta_{M}(H-v)\leq\text{\tiny{$2$}-}\eta_{M}(H)+1$. If $G$
is even then $G_{even}=G$ and there is nothing to prove. Otherwise,
$G=G_{even}-u$, where $u$ is the external vertex we added to $G$ to obtain
$G_{even}$. Hence (i) immediately follows from this inequality. Also the same
inequality proves (v) since $G$ can be obtained from $G_{odd}$ by removing
$\mathrm{v}_{\mathrm{e}}(G)$ number of pendant vertices of $G_{odd}$ one by
one.

(iii) follows from the fact that not even components of $G$ become connected
to each other in $G_{even}$ via the paths of length two passing trough the
external vertex.

(ii) follows from combining the facts that
$\mathrm{e}(G_{even})=(\mathrm{e}+\mathrm{v}_{\mathrm{o}})(G)$,
$\mathrm{v}(G_{even})=(\mathrm{v}+i)(G)$, and
$\mathrm{c}(G_{even})=(\mathrm{c}_{\mathrm{e}}+i)(G)$. ∎

######  Theorem 1.8.

Let $G$ be a graph. Then

(11) $\displaystyle\text{\tiny{$2$}-}\eta_{A}(G)$
$\displaystyle\leq(\theta-\tau+\mathrm{v}_{\mathrm{o}}+2\mathrm{c}_{\mathrm{e}}-\mathrm{c}+2i)(G),$
(12) $\displaystyle\text{\tiny{$2$}-}\eta_{A+I}(G)$
$\displaystyle\leq(\theta-\tau+\mathrm{v}_{\mathrm{e}}+\mathrm{c})(G),$

###### Proof.

(9) and Lemma 1.7 imply

$\displaystyle\text{\tiny{$2$}-}\eta_{A}(G)$
$\displaystyle\leq\text{\tiny{$2$}-}\eta_{A}(G_{even})+i(G)$
$\displaystyle\leq(\theta-\tau+\text{c})(G_{even})+i(G)$
$\displaystyle\leq(\theta+\mathrm{v}_{\mathrm{o}}+\mathrm{c}_{\mathrm{e}}-\mathrm{c}-\tau+\mathrm{c}_{\mathrm{e}}+i)(G)+i(G)$
(13)
$\displaystyle=(\theta-\tau+\mathrm{v}_{\mathrm{o}}+2\mathrm{c}_{\mathrm{e}}-\mathrm{c}+2i)(G)$

and

$\displaystyle\text{\tiny{$2$}-}\eta_{A+I}(G)$
$\displaystyle\leq\text{\tiny{$2$}-}\eta_{A}(G_{odd})+\mathrm{v}_{\mathrm{e}}(G)$
$\displaystyle\leq(\theta-\tau+\text{c})(G_{odd})+\mathrm{v}_{\mathrm{e}}(G)$
$\displaystyle=(\theta-\tau+\mathrm{v}_{\mathrm{e}}+\mathrm{c})(G).$

∎

Theorem 1.4 and Theorem 1.8, together with Lemma 1.1, complete the proof of
Theorem 0.1 for the first three bounds. On the other hand, the following
theorem with Lemma 1.1 gives us the last bound.

######  Theorem 1.9.

For any graph $G$

(14) $\text{\tiny{$2$}-}\eta_{P+I}(G)\leq(\mathrm{v}-\beta-\mathrm{c})(G).$

###### Proof.

First note that $Ker_{2}(P(G)+I)\subseteq Col_{2}(P(G))$. Indeed,
$(P(G)+I)x=0$ is equivalent to say that $P(G)x=x$. Therefore, together with
the rank nullity theorem and Proposition 1.2 we have

$\displaystyle\text{\tiny{$2$}-}\eta_{P+I}(G)$
$\displaystyle\leq\text{\tiny{$2$}-}r_{P}(G)$
$\displaystyle=(\mathrm{v}-\text{\tiny{$2$}-}\eta_{P})(G)$
$\displaystyle=(\mathrm{v}-\beta-\mathrm{c})(G).$

∎

##  2\. Multiplicities of the eigenvalues of $A_{\alpha}$

Nikiforov introduced the graph matrix $A_{\alpha}(G)$ in [4] (See introduction
for the definition). It is called the generalized adjacency matrix of $G$.
Since $A_{0}(G)=A(G)$ and $2A_{1/2}(G)=Q(G)$, the spectral analysis of
$A_{\alpha}(G)$ combines the spectral analysis of $A(G)$ and $Q(G)$.
Therefore, later on the spectral properties of $A_{\alpha}(G)$ have been
studied by lots of researcher among which Shuchao and Wei in [5] showed that
$m_{A_{\alpha}}(G,\lambda)\leq(2\theta+p)(G)$ for all $\alpha\in[0,1]$, and
for all $\lambda\in\mathbb{R}$. Hence they generalized the results in [1] and
[3] to the multiplicities of the eigenvalues of $A_{\alpha}(G)$. Our method
can also be applied to this graph matrix in the case $\alpha$ and $\lambda$
are rational numbers. Indeed, we obtain the following results.

######  Theorem 2.1.

Let $G$ be a graph and $a/b$ and $p/q$ be rational numbers in their lowest
forms. Then we have the following table.

Table 1.  Bounds of $m_{A_{a/b}}(G,p/q)$ $a$ | $b$ | $p$ | $q$ | $m_{A_{a/b}}(G,p/q)$ is less than or equal to
---|---|---|---|---
odd | odd | odd | odd | $\text{\tiny{$2$}-}\eta_{\mkern 1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern 1.5mu+I}(G)=\mathrm{v}_{\mathrm{o}}(G)$
even | odd | odd | odd | $\text{\tiny{$2$}-}\eta_{A+I}(G)\leq(\theta-\tau+\mathrm{v}_{\mathrm{e}}+\mathrm{c})(G)$
odd | odd | even | odd | $\text{\tiny{$2$}-}\eta_{\mkern 1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern 1.5mu}(G)=\mathrm{v}_{\mathrm{e}}(G)$
even | odd | even | odd | $\text{\tiny{$2$}-}\eta_{A}(G)\leq(\theta-\tau+\mathrm{v}_{\mathrm{o}}+2\mathrm{c}_{\mathrm{e}}-\mathrm{c}+2i)(G)$
odd | even | - | odd | $\text{\tiny{$2$}-}\eta_{P}(G)\leq(\theta-\tau+\mathrm{c})(G)$
- | odd | odd | even | $\text{\tiny{$2$}-}\eta_{I}=0$

###### Proof.

Note that

$\displaystyle Ker(A_{a/b}-(p/q)I)$ $\displaystyle=Ker(qA_{a/b}-pI)$
$\displaystyle=Ker((qa/b)D+q(1-a/b)A-pI)$
$\displaystyle=Ker(qaD+q(b-a)A-bpI).$

So if we let $M=qaD+q(b-a)A-bpI$, then we have

$m_{A_{a/b}}(G,p/q)=\eta_{(A_{a/b}-(p/q)I)}=\eta_{M}\leq\text{\tiny{$2$}-}\eta_{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu}$

by Lemma 1.1. On the other hand,

$\mkern 1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu=\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu\mkern
1.5mu\overline{\mkern-1.5mua\mkern-1.5mu}\mkern 1.5mu\mkern
1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern 1.5mu+\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu(\mkern
1.5mu\overline{\mkern-1.5mub\mkern-1.5mu}\mkern 1.5mu+\mkern
1.5mu\overline{\mkern-1.5mua\mkern-1.5mu}\mkern 1.5mu)A+\mkern
1.5mu\overline{\mkern-1.5mub\mkern-1.5mu}\mkern 1.5mu\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5muI.$

Now the results follow by finding the special form of $\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu$ in each case and
applying Theorems 1.4, 1.8, and 1.9. ∎

######  Remark 2.2.

Our method in the not included case in Theorem 2.1 does not give a nontrivial
bound to the corresponding multiplicity.

##  3\. Existence of the extremal graphs

Before giving characterizations of the extremal graphs whose eigenvalue
multiplicities attain the corresponding bound in Theorem 0.1, we think that
one should first examine the extremal graphs whose $2$-nullities of the
corresponding graph matrix attain the bound given in Theorems 1.4, 1.8, and
1.9 since the bounds in the first theorem were obtained by the bounds of the
$2$-nullities in the latter theorems by directly applying Lemma 1.1. On the
other hand, this analysis seems to require a comprehensive study. Note that
there are four graph matrices whose $2$-nullities need to be examined, namely
$A(G)$, $A(G)+I$, $P(G)$, and $P(G)+I$. Unfortunately, as far as we know,
$2$-nullities of the corresponding matrices is not a well studied area and
their properties such as how they change under certain graph operations are
not examined enough yet. The one exception might be the $2$-nullity of $A+I$.
Because of its connection with the Lights Out game and also with the parity
domination theory some of its properties have been examined in several studies
such as [41], [42], [43], [44], [45] . So we hope that after this study, there
will be more attraction to the analysis of the $2$-nullities of the
corresponding graph matrices by other researchers as well.

One thing we can say for sure for now is that all of the bounds in Theorem
0.1, an hence in Theorems 1.4, 1.8, and 1.9 are attained. For example it is
easy to check that for each $k$, the cycle $C_{k}$ is an extremal graph
attaining the bounds in (8) and (11). Moreover,
$m_{A}(C_{4k},0)=m_{L}(C_{4k},2)=m_{Q}(C_{4k},2)=2$ which is equal to the
corresponding bounds in the first and third inequalities in Theorem 0.1.

On the other hand, any odd tree $T$ is an extremal graph attaining the bound
in (12). Indeed, $\text{\tiny{$2$}-}\eta_{A+I}(T)\leq 1$ by (12). On the other
hand, the vector $(1,\dots,1)^{t}$ is in $Ker_{2}(A(T)+I)$ since $T$ is odd,
hence $\text{\tiny{$2$}-}\eta_{A+I}(T)=1$. Moreover, it is not hard to see
that for the odd tree $H$, which is in the shape of the letter H, we have
$m_{A}(H,1)=1$ which is the bound we obtain using the second inequality in
Theorem 0.1.

Lastly, any complete graph $K_{2k+1}$ with $2k+1$ vertices is an extremal
graph attaining the bound in (14). Indeed $P(K_{2k+1})+I$ is the square matrix
all of whose entries are $1$. Therefore,
$\text{\tiny{$2$}-}\eta_{P+I}(K_{2k+1})=2k$ which is the largest possible
bound we can obtain using (14). Moreover,
$m_{L}(K_{2k+1},2k+1)=m_{Q}(K_{2k+1},2k-1)=2k$. Hence, the bound in the last
inequality of Theorem 0.1 is also attained.

Declaration of Competing Interests The author declares that he has no known
competing financial interests or personal relationships that could have
appeared to influence the work reported in this paper.

## References

  * [1] Ma, X., Wong, D. & Tian, F. Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices. Discrete Appl. Math.. 215 pp. 171-176 (2016), https://doi.org/10.1016/j.dam.2016.07.010
  * [2] Wong, D., Zhou, Q. & Tian, F. Nullity and singularity of a graph in which every block is a cycle. Discrete Math.. 345, Paper No. 112851, 8 (2022), https://doi.org/10.1016/j.disc.2022.112851
  * [3] Wang, L., Wei, L. & Jin, Y. The multiplicity of an arbitrary eigenvalue of a graph in terms of cyclomatic number and number of pendant vertices. Linear Algebra Appl.. 584 pp. 257-266 (2020), https://doi.org/10.1016/j.laa.2019.09.013
  * [4] Nikiforov, V. Merging the $A-$ and $Q-$spectral theories. Appl. Anal. Discrete Math.. 11, 81-107 (2017), https://doi.org/10.2298/AADM1701081N
  * [5] Li, S. & Wei, W. The multiplicity of an $A_{\alpha}$-eigenvalue: a unified approach for mixed graphs and complex unit gain graphs. Discrete Math.. 343, 111916, 19 (2020), https://doi.org/10.1016/j.disc.2020.111916
  * [6] Zhou, Q. & Wong, D. Graphs with eigenvalue $-1$ of multiplicity $2\theta(G)+p(G)-1$. Linear Algebra Appl.. 645 pp. 137-152 (2022), https://doi.org/10.1016/j.laa.2022.03.010
  * [7] Chang, S., Tam, B., Li, J. & Zheng, Y. Graphs G with nullity $2c(G)+p(G)-1$. Discrete Appl. Math.. 311 pp. 38-58 (2022), https://doi.org/10.1016/j.dam.2022.01.008
  * [8] Wang, X., Wong, D., Wei, L. & Tian, F. On the multiplicity of –1 as an eigenvalue of a tree with given number of pendant vertices. Linear Multilinear Algebra. 70, 3345-3353 (2022), https://doi.org/10.1080/03081087.2020.1838424
  * [9] Xu, F., Wong, D. & Tian, F. On the multiplicity of $\alpha$ as an eigenvalue of the $A_{\alpha}$ matrix of a graph in terms of the number of pendant vertices. Linear Algebra Appl.. 594 pp. 193-204 (2020), https://doi.org/10.1016/j.laa.2020.02.025
  * [10] Chang, S., Chang, A. & Zheng, Y. The leaf-free graphs with nullity $2c(G)-1$. Discrete Appl. Math.. 277 pp. 44-54 (2020), https://doi.org/10.1016/j.dam.2019.08.018
  * [11] Lu, Y., Wang, L. & Zhou, Q. Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph. Filomat. 32, 1303-1312 (2018), https://doi.org/10.2298/fil1804303l
  * [12] Godsil, C. & Royle, G. Algebraic graph theory. (Springer-Verlag, New York,2001), https://doi.org/10.1007/978-1-4613-0163-9
  * [13] Faria, I. Permanental roots and the star degree of a graph. Linear Algebra Appl.. 64 pp. 255-265 (1985), https://doi.org/10.1016/0024-3795(85)90281-2
  * [14] Chang, G., Huang, L. & Yeh, H. A characterization of graphs with rank 4. Linear Algebra Appl.. 434, 1793-1798 (2011), https://doi.org/10.1016/j.laa.2010.09.040
  * [15] Chang, G., Huang, L. & Yeh, H. A characterization of graphs with rank 5. Linear Algebra Appl.. 436, 4241-4250 (2012), https://doi.org/10.1016/j.laa.2012.01.021
  * [16] Chen, C., Huang, J. & Li, S. On the relation between the H-rank of a mixed graph and the matching number of its underlying graph. Linear Multilinear Algebra. 66, 1853-1869 (2018), https://doi.org/10.1080/03081087.2017.1374327
  * [17] Zhou, J., Sun, L., Yao, H. & Bu, C. On the nullity of connected graphs with least eigenvalue at least $-2$. Appl. Anal. Discrete Math.. 7, 250-261 (2013), https://doi.org/10.2298/AADM130710014Z
  * [18] Fan, Y., Wang, Y. & Wang, Y. A note on the nullity of unicyclic signed graphs. Linear Algebra Appl.. 438, 1193-1200 (2013), https://doi.org/10.1016/j.laa.2012.08.027
  * [19] Li, H., Fan, Y. & Su, L. On the nullity of the line graph of unicyclic graph with depth one. Linear Algebra Appl.. 437, 2038-2055 (2012), https://doi.org/10.1016/j.laa.2012.05.028
  * [20] Gong, S. & Xu, G. On the nullity of a graph with cut-points. Linear Algebra Appl.. 436, 135-142 (2012), https://doi.org/10.1016/j.laa.2011.06.039
  * [21] Cheng, B. & Liu, B. On the nullity of tricyclic graphs. Linear Algebra Appl.. 434, 1799-1810 (2011), https://doi.org/10.1016/j.laa.2011.01.006
  * [22] Gong, S., Fan, Y. & Yin, Z. On the nullity of graphs with pendant trees. Linear Algebra Appl.. 433, 1374-1380 (2010), https://doi.org/10.1016/j.laa.2010.05.016
  * [23] Sciriha, I. On the construction of graphs of nullity one. Discrete Math.. 181, 193-211 (1998), https://doi.org/10.1016/S0012-365X(97)00036-8
  * [24] Gutman, I. & Sciriha, I. On the nullity of line graphs of trees. Discrete Math.. 232, 35-45 (2001), https://doi.org/10.1016/S0012-365X(00)00187-4
  * [25] Fiorini, S., Gutman, I. & Sciriha, I. Trees with maximum nullity. Linear Algebra Appl.. 397 pp. 245-251 (2005), https://doi.org/10.1016/j.laa.2004.10.024
  * [26] Guo, J., Yan, W. & Yeh, Y. On the nullity and the matching number of unicyclic graphs. Linear Algebra Appl.. 431, 1293-1301 (2009), https://doi.org/10.1016/j.laa.2009.04.026
  * [27] Hu, S., Xuezhong, T. & Liu, B. On the nullity of bicyclic graphs. Linear Algebra Appl.. 429, 1387-1391 (2008), https://doi.org/10.1016/j.laa.2007.12.007
  * [28] Li, H., Su, L. & Sun, H. On bipartite graphs which attain minimum rank among bipartite graphs with a given diameter. Electron. J. Linear Algebra. 23 pp. 137-150 (2012), https://doi.org/10.13001/1081-3810.1510
  * [29] Li, W. & Chang, A. On the trees with maximum nullity. MATCH Commun. Math. Comput. Chem.. 56, 501-508 (2006)
  * [30] Lu, Y., Wang, L. & Zhou, Q. The rank of a signed graph in terms of the rank of its underlying graph. Linear Algebra Appl.. 538 pp. 166-186 (2018), https://doi.org/10.1016/j.laa.2017.10.013
  * [31] Luo, W., Huang, J. & Li, S. On the relationship between the skew-rank of an oriented graph and the rank of its underlying graph. Linear Algebra Appl.. 554 pp. 205-223 (2018), https://doi.org/10.1016/j.laa.2018.04.032
  * [32] Ma, X., Wong, D. & Tian, F. Skew-rank of an oriented graph in terms of matching number. Linear Algebra Appl.. 495 pp. 242-255 (2016), https://doi.org/10.1016/j.laa.2016.01.036
  * [33] Omidi, G. On the nullity of bipartite graphs. Graphs Combin.. 25, 111-114 (2009), https://doi.org/10.1007/s00373-008-0825-5
  * [34] Song, Y., Song, X. & Tam, B. A characterization of graphs G with nullity $|V(G)|-2m(G)+2c(G)$. Linear Algebra Appl.. 465 pp. 363-375 (2015), https://doi.org/10.1016/j.laa.2014.09.034
  * [35] Song, Y., Song, X. & Zhang, M. An upper bound for the nullity of a bipartite graph in terms of its maximum degree. Linear Multilinear Algebra. 64, 1107-1112 (2016), https://doi.org/10.1080/03081087.2015.1072530
  * [36] Xuezhong, T. & Liu, B. On the nullity of unicyclic graphs. Linear Algebra Appl.. 408 pp. 212-220 (2005), https://doi.org/10.1016/j.laa.2005.06.012
  * [37] Wang, L. & Wong, D. Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank. Discrete Appl. Math.. 166 pp. 276-281 (2014), https://doi.org/10.1016/j.dam.2013.09.012
  * [38] Wong, D., Ma, X. & Tian, F. Relation between the skew-rank of an oriented graph and the rank of its underlying graph. European J. Combin.. 54 pp. 76-86 (2016), https://doi.org/10.1016/j.ejc.2015.12.005
  * [39] Wong, D., Zhu, M. & Lv, W. A characterization of long graphs of arbitrary rank. Linear Algebra Appl.. 438, 1347-1355 (2013), https://doi.org/10.1016/j.laa.2012.09.017
  * [40] Zhou, Q., Wong, D. & Sun, D. An upper bound of the nullity of a graph in terms of order and maximum degree. Linear Algebra Appl.. 555 pp. 314-320 (2018), https://doi.org/10.1016/j.laa.2018.06.025
  * [41] Amin, A. & Slater, P. Neighborhood domination with parity restrictions in graphs. Proceedings Of The Twenty-third Southeastern International Conference On Combinatorics, Graph Theory, And Computing (Boca Raton, FL, 1992). 91 pp. 19-30 (1992)
  * [42] Amin, A. & Slater, P. All parity realizable trees. J. Combin. Math. Combin. Comput.. 20 pp. 53-63 (1996)
  * [43] Amin, A., Clark, L. & Slater, P. Parity dimension for graphs. Discrete Math.. 187, 1-17 (1998), https://doi.org/10.1016/S0012-365X(97)00242-2
  * [44] Amin, A., Slater, P. & Zhang, G. Parity dimension for graphs—a linear algebraic approach. Linear Multilinear Algebra. 50, 327-342 (2002), https://doi.org/10.1080/0308108021000049293
  * [45] Ballard, L., Budge, E. & Stephenson, D. Lights out for graphs related to one another by constructions. Involve. 12, 181-201 (2019), https://doi.org/10.2140/involve.2019.12.181