# Complexity, Information Geometry, and Loschmidt Echo near Quantum
Criticality

Nitesh Jaiswal<EMAIL_ADDRESS>Mamta Gautam<EMAIL_ADDRESS>Tapobrata
Sarkar<EMAIL_ADDRESS>Department of Physics, Indian Institute of Technology
Kanpur-208016, India

###### Abstract

We consider the Nielsen complexity ${\mathcal{C}}_{N}$, the Loschmidt echo
${\mathcal{L}}$, and the Fubini-Study complexity $\tau$ in the transverse XY
model, following a sudden quantum quench, in the thermodynamic limit. At small
times, the first two are related by ${\mathcal{L}}\sim
e^{-{\mathcal{C}}_{N}}$. By computing a novel time-dependent quantum
information metric, we show that in this regime, ${\mathcal{C}}_{N}\sim
d\tau^{2}$, up to lowest order in perturbation. The former relation continues
to hold in the same limit at large times, whereas the latter does not. Our
results indicate that in the thermodynamic limit, the Nielsen complexity and
the Loschmidt echo show enhanced temporal oscillations when one quenches from
a close neighbourhood of the critical line, while such oscillations are
notably absent when the quench is on such a line. We explain this behaviour by
studying the nature of quasi-particle excitations in the vicinity of
criticality. Finally, we argue that the triangle inequality for the Nielsen
complexity might be violated in certain regions of the parameter space, and
point out why one should be careful about the nature of the interaction
Hamiltonian, while using this measure.

##  I Introduction

Out of the many important aspects of quantum information theory, one which has
been popular in the recent past is that of complexity. The notion of
complexity commonly appears in areas of computer science and computational
complexity theories Arora ; Moore . There, complexity quantifies the
difficulty to solve a particular task. In an informal description, this
difficulty is the amount of computational resources required in the method of
computation, such as the number of steps, or volume of memory, used to perform
a sample task. Of late, complexity has received attention in the context of
widely different branches of physics Lloyd . In fact, the recent flurry of
activities in this field largely arose in the context of string theory and the
related gauge-gravity duality Myers1 ; Myers2 . The latter allows for
computation of complexity in quantum field theories, which may otherwise be
intractable. Indeed, the current literature suggests that the notion of
complexity is also related to deep questions in black hole physics, by the
same notion of duality Susskind ; Brown ; Brown1 .

What we are interested in here is a simpler situation, namely a many body
quantum system with nearest neighbour interactions, in the thermodynamic
limit, and we will mostly focus on the transverse field XY model. The notion
of complexity is easier to understand here, and provides important physical
insights. In quantum information theory, one quantification of complexity
refers to a minimal number of universal or elementary gates required to
construct a unitary transformation $U$, which acts on a given reference state
$\ket{\Psi_{R}}$ to produce a given target state $\ket{\Psi_{T}}$. Thus, with
a few arbitrary choices (such as simple reference states), the NC is defined
as the number of elementary gates in the optimal circuit. A natural difficulty
with this quantification arises, as the choices of good reference states and
elementary gates have a theoretically infinite number of possibilities.
Nielsen and collaborators Nielsen1 ; Nielsen2 ; Nielsen3  therefore adapted a
geometric method for the evaluation of complexity, dubbed the Nielsen
complexity (NC) or the circuit complexity. This geometric approach (explored
in detail recently in Liu ; xiong ; Khan ; tapo1 ) involves a continuum of the
unitary transformations $U(\tau)$ generated by any (possibly) time-dependent
Hamiltonian $H(t)$, with $\tau$ parametrising a path in the Hilbert space.

In this approach, one considers the trajectories in the space of unitaries
such that the interesting trajectory satisfies $U(\tau=0)=\mathbb{1}$ and
$U(\tau=1)=U$. Further, one identifies the optimal path or circuit, by
minimising a cost functional defined for various possible paths. These cost
functionals satisfy certain physicality conditions, and then these can be
shown to define length functionals on a Riemannian manifold that arises in the
space of unitary transformations, for a specific choice of the cost functional
Myers1 ; Myers2 . The metric on the space of unitaries is written as

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle
4\delta_{ab}\Big{[}\frac{1}{{\rm
Tr}\big{[}J^{a}.J_{a}^{T}\big{]}}\text{Tr}\Big{(}\partial_{\tau}{U(\tau)}\cdot
U^{-1}(\tau)\cdot(J^{a})^{T}\Big{)}\Big{]}\times$ (1)
$\displaystyle\Big{[}\frac{1}{{\rm
Tr}\big{[}J^{b}.J_{b}^{T}\big{]}}\text{Tr}\Big{(}\partial_{\tau}{U(\tau)}\cdot
U^{-1}(\tau)\cdot(J^{b})^{T}\Big{)}\Big{]}^{*}~{},$

with $J^{a}$s denoting the generators of the underlying symmetry group with a
superscript $T$ denoting the transpose, and $U$ denotes the unitary
transformation that takes a reference state to a target state. Then, the
complexity is quantified by the minimal geodesic paths connecting
$\ket{\Psi_{R}}$ and $\ket{\Psi_{T}}$. The complexity thus reduces to a
variational computation to find geodesics on the space of unitary
transformations. Namely, writing the metric of Eq. (1) as
$ds^{2}=g_{\alpha\beta}dy^{\alpha}dy^{\beta}$, where $y^{\alpha}$ denotes a
set of coordinates on the space of unitaries, the minimal (i.e., geodesic)
distance on the space of unitaries is the NC.

A related quantity that is also of great interest is the Fubini-Study
complexity (FSC) tapo1 ; FS . Contrary to the NC, this quantification arises
from the quantum information metric (QIM) Bengt ; Provost ; Polkov ; Zanardi ;
tapo2 ; tapo3 ; Hamma ; Venuti , which is the real part of a more generic
structure called the quantum geometric tensor, whose imaginary part gives the
Berry phase. The QIM being the Riemannian metric induced on the parameter
space of the Hamiltonian (which will always be two dimensional in our case),
measures the distance between two neighbouring quantum states. The FSC is then
the geodesic distance on the parameter manifold. Specifically, given a wave
function $\ket{\Psi}$, the geometric tensor reads

$\chi_{ij}=\bra{\partial_{i}\Psi}\partial_{j}\Psi\rangle-\bra{\partial_{i}\Psi}\Psi\rangle\bra{\Psi}\partial_{j}\Psi\rangle~{},$
(2)

with $\partial_{i}\equiv\frac{\partial}{\partial\lambda^{i}}$,
$i=1,2,\cdots,m$, where $m$ is the dimension of the parameter space
${\vec{\lambda}}$. The metric on the parameter manifold $g_{ij}={\rm
Re}[\chi_{ij}]$. Given the QIM, geodesic equations on the parameter manifold
are computed in a standard fashion but these often need to be solved
numerically. If we parametrise the geodesic distance by an affine parameter,
then inverting the geodesic equation (possibly numerically) gives a measure of
the FSC. In this work, we will be interested in a quench situation, where the
FSC becomes time dependent.

Another important quantity which has been studied in great details in the
literature for over more than a decade now, is the Loschmidt echo (LE),
denoted here by ${\mathcal{L}}$, originally introduced in the context of
quantum chaos Peres , and defined as

${\mathcal{L}}=\big{|}\bra{\Psi_{0}}e^{iHt}e^{-iH_{F}t}\ket{\Psi_{0}}\big{|}^{2}=\big{|}\bra{\Psi_{0}}e^{-iH_{F}t}\ket{\Psi_{0}}\big{|}^{2}~{},$
(3)

where $\ket{\Psi_{0}}$ is an initially prepared ground state of the transverse
XY model. Here, $H$ is a time-independent Hamiltonian and $H_{F}=H+H_{I}$,
with $H_{I}$ being a perturbative interaction. The second expression in Eq.
(3) follows as $\ket{\Psi_{0}}$ is an eigenstate of $H$. The LE is in a broad
sense a dynamical version of the QIM, and its decay and revival structures
have received a lot of attention in the past decade Hamma1 , and will be of
interest to us in this paper.

In tapo1 , the NC and FSC of a transverse XY spin chain was studied in a
static situation, following a related work of Liu  in the context of the
Kitaev model. It was shown in tapo1  that the derivative of the complexity is
a clear indicator of zero temperature quantum phase transitions (QPTs) in the
XY model, in the sense that it becomes divergent at the location of such
transitions. Here, we first show some analytic results for the NC of the
model, when the reference and target states are separated by a small change in
the parameters. This way, we are able to explicitly show that the
infinitesimal NC is related to the FSC, a formal argument for which was put
forward in tapo1 . In fact, this allows us to check an important issue. Since
the NC measures a distance, it should follow the triangle inequality. What we
find here is that this inequality is not satisfied even in the infinitesimal
version of the NC, an issue that deserves further study and will be commented
upon here.

We thereafter analyse a time-dependent sudden quench situation, with the XY
model coupled to a central spin-1/2 system Ali ; Ali1 ; Diptarka . This was
studied first by Zanardi and collaborators ZanLE  (see also LE1 ; LE2 ; LE3 ;
LE4 ; LE5 ; LE6 ; AmitShraddhaVictor ) in the context of the LE. Here, we
study this model in the context of the NC and the FSC and compare these with
the LE. Interestingly, in the thermodynamic limit, we show that for all times,
a very generic formula that holds in most part of the parameter space of the
XY model is ${\mathcal{L}}=e^{-{\mathcal{C}}_{N}}$. While for small times we
find that ${\mathcal{L}}\equiv e^{-d\tau^{2}}$, this relation is nonetheless
challenged at large times. In this paper, we further obtain the following
results. a) While ${\mathcal{L}}$ and the derivative of ${\mathcal{C}}_{N}$
are indicators of quantum phase transitions for all times, $\tau$ only
indicates such transitions at large times. b) In the thermodynamic limit,
${\mathcal{L}}$ and ${\mathcal{C}}_{N}$ show enhanced temporal oscillations
when one quenches from the critical line, while such oscillations are
completely absent when the quench is on such a line, and this is explained by
studying the nature of quasi-particle excitations in the vicinity of this
line. Finally, we also make some observations about the triangle inequality
for ${\mathcal{C}}_{N}$. We show that this might be violated in certain cases
and this indicates that the current study must be further pursued.

##  II Time-independent Nielsen complexity

To set up the notations and conventions used in the rest of this paper, we
will first revisit some issues regarding the transverse XY model. We consider
the one-dimensional spin-$1/2$ XY model in a transverse magnetic field, one
which exhibits quantum phase transitions. The Hamiltonian of the model reads

$H=-\sum\limits_{l=-M}^{M}\\!\\!\left(\frac{1+\gamma}{4}\sigma^{x}_{l}\sigma^{x}_{l+1}+\frac{1-\gamma}{4}\sigma^{y}_{l}\sigma^{y}_{l+1}-\frac{h}{2}\sigma^{z}_{l}\right)~{},$
(4)

where $M=(N-1)/2$, for odd $N$, $\gamma$ is the anisotropy parameter, and $h$
the applied magnetic field, and $\sigma$ denotes the Pauli matrices. Quantum
phase transitions in this model occurs on the lines $|h|=1$ and on $\gamma=0$.
To see this, the model is diagonalised using the Jordan-Wigner, Fourier and
Bogoliubov transformations, and the energy eigenvalues are

$\Lambda_{k\pm}=\pm\sqrt{(\cos k+h)^{2}+(\gamma\sin{k})^{2}},$ (5)

with
$k=\frac{2\pi\lambda}{N}~{},~{}~{}\lambda=-\frac{N-1}{2},....,-1,0,1,....,\frac{N-1}{2}~{}$.
The energy gap reads

$\displaystyle\Delta(k)=\Lambda_{k+}-\Lambda_{k-}=2\sqrt{(\cos
k+h)^{2}+(\gamma\sin{k})^{2}}~{}.$ (6)

The spectrum is gapless on the line $\gamma=0,~{}|h|\leq 1$, which signals an
anisotropic transition line between two ferromagnetically ordered phases, and
at $|h|=1$ (for $k=0,\pi$), which are the Ising transition lines between a
ferromagnetic and a paramagnetic phase. The ground state of the model is given
by

$\displaystyle\ket{\Psi_{0}}_{h,\gamma}=\prod_{k>0}\bigg{[}\cos\left(\frac{\theta_{k}}{2}\right)\ket{0}_{k}\ket{0}_{-k}$
$\displaystyle-$ $\displaystyle i\sin\left(\frac{\theta_{k}}{2}\right)$ (7)
$\displaystyle\times\ket{1}_{k}\ket{1}_{-k}\bigg{]}~{},$

where $\ket{0}_{k}$ and $\ket{1}_{k}$ denote the vacuum and the single
excitation states of Jordan-Wigner fermions with momentum $k$. The Bogoliubov
angle $\theta_{k}$ is given from

$\cos\theta_{k}=\frac{\cos k+h}{\sqrt{(\cos
k+h)^{2}+(\gamma\sin{k})^{2}}}~{}.$ (8)

As was derived in Liu  and extensively discussed in Liu , tapo1 , the NC
(denoted by ${\mathcal{C}}_{N}$) of a quadratic Hamiltonian is expressed in
terms of the Bogoliubov angle $\theta_{k}$ that characterises its ground
state, i.e., ${\mathcal{C}}_{N}=\sum\limits_{k}|\Delta\theta_{k}|^{2}~{}$,
where $\Delta\theta_{k}=(\theta_{k}^{T}-\theta_{k}^{R})/2$. Here,
$\theta_{k}^{R}$ and $\theta_{k}^{T}$ are the Bogoliubov angles corresponding
to reference and target states $\ket{\Psi_{R}}$ and $\ket{\Psi_{T}}$ that we
have discussed above.

We now write for the reference and the target states, $h^{R}=h$ and
$h^{T}=h+\delta$, for a fixed non-zero value of the anisotropy parameter
$\gamma$. Assuming small $\delta$, we expand the NC up to a desired order in
$\delta$, remembering that this series expansion is rendered invalid for
regions of $h$ that are infinitesimally close to the Ising phase transition.
In the thermodynamic limit, it is then a fairly standard exercise to calculate
the terms order by order in $\delta$ by going to the complex plane, and
computing residues, where we replace $\sum_{k}=N/(2\pi)\int_{0}^{\pi}dk$. Here
and everywhere else, in the thermodynamic limit, we will work with quantities
per system size, and suppress the factor of $N$. Doing this, we finally
obtain,

$\displaystyle{\mathcal{C}}_{N}\big{|}_{|h|<1}$ $\displaystyle=$
$\displaystyle\frac{\delta^{2}}{16|\gamma|\left(1-h^{2}\right)}+\frac{h\delta^{3}}{16|\gamma|\left(1-h^{2}\right)^{2}}$
$\displaystyle+$
$\displaystyle\frac{\delta^{4}\left(7\gamma^{2}\left(3h^{2}+1\right)+h^{2}-1\right)}{384|\gamma|^{3}\left(1-h^{2}\right)^{3}}+{\mathcal{O}}(\delta^{5})$
$\displaystyle{\mathcal{C}}_{N}\big{|}_{|h|>1}$ $\displaystyle=$
$\displaystyle\frac{\gamma^{2}\delta^{2}|h|}{16\left(h^{2}-1\right){\mathcal{A}}^{3}}$
(9) $\displaystyle\pm$
$\displaystyle\frac{\gamma^{2}\delta^{3}\left(\gamma^{2}+4h^{4}+\left(\gamma^{2}-3\right)h^{2}-1\right)}{32\left(h^{2}-1\right)^{2}{\mathcal{A}}^{5}}+{\mathcal{O}}(\delta^{4}),~{}~{}~{}~{}~{}$

with ${\mathcal{A}}=\sqrt{h^{2}+\gamma^{2}-1}$, and the $-(+)$ signs in the
second term of the second equation above refers to the region $h>1(<-1)$,
respectively. The coefficients of $\delta^{2}$ in the first terms of the right
hand side of the two equations in Eq. (9) are the components of the
information metric in the $h-\gamma$ plane Zanardi , Polkov . This is in lines
with the argument given in tapo1 , i.e., the infinitesimal NC (with the
differential element $dh$ identified with $\delta$) gives the line element on
the parameter space. The other terms in this equation represent higher order
corrections. Similarly, for a fixed value of the magnetic field $h$, writing
$\gamma^{R}=\gamma$ and $\gamma^{T}=\gamma+\delta$, we obtain

$\displaystyle{\mathcal{C}}_{N}\big{|}_{|h|<1}$ $\displaystyle=$
$\displaystyle\frac{\delta^{2}}{16|\gamma|(|\gamma|+1)^{2}}\mp\frac{(3|\gamma|+1)\delta^{3}}{32\gamma^{2}(|\gamma|+1)^{3}}$
(10) $\displaystyle+$
$\displaystyle\frac{(|\gamma|(43|\gamma|+28)+7)\delta^{4}}{384|\gamma|^{3}(|\gamma|+1)^{4}}+{\mathcal{O}}(\delta^{5})~{},$

where the $-(+)$ sign in the second term has to be used for $\gamma>0(<0)$,
respectively. The expression for ${\mathcal{C}}_{N}\big{|}_{|h|>1}$ being too
cumbersome to reproduce here, although we note that the
${\mathcal{O}}(\delta^{2})$ term is indeed the $\gamma-\gamma$ component of
the information metric listed in Zanardi , Polkov .

A similar exercise can be done for the reference state being at $(h,\gamma)$
and the target state at $(h+\delta,\gamma+\delta)$ where for the sake of
simplicity, we choose the value of the target parameters to be shifted by the
same amount $\delta$. In this case also, the expression for the complexity can
be evaluated perturbatively, but are lengthy beyond the second order. We find
that

$\displaystyle{\mathcal{C}}_{N}\big{|}_{|h|<1}=\frac{\delta^{2}\left(2-h^{2}+|\gamma|(|\gamma|+2)\right)}{16|\gamma|(|\gamma|+1)^{2}\left(1-h^{2}\right)}+{\mathcal{O}}(\delta^{3})~{}.$
(11)

That Eqs. (9) - (11) give excellent approximations to the NC on the $h-\gamma$
parameter space except for points arbitrarily close to the critical lines, is
readily checked, by comparing with the numerically obtained values. Close to
these lines however, the perturbative expansion in $\delta$ up to the first
few orders that we have done here is inadequate, and higher order terms start
contributing significantly. One therefore has to be careful in applications of
the equations derived here, namely that the $\delta$-expansion should not be
used to describe the physics of the cross-over regions.

Now from the above discussion, we can examine the triangle inequality for the
NC. Broadly speaking, since the NC relates to a distance on a Riemannian
manifold, the sum of the complexities resulting out of reaching a target state
from a given reference by two distinct operations should be greater than the
complexity of reaching the target by a single operation from the reference. We
start with a given reference state $(h,\gamma)$ and reach a target state
$(h+\delta,\gamma+\delta)$. We can reach the target state by a combination of
two operations ${\mathcal{O}}_{1}:(h,\gamma)\to(h+\delta,\gamma)$ and
${\mathcal{O}}_{2}:(h+\delta,\gamma)\to(h+\delta,\gamma+\delta)$.
Alternatively, we can reach it by a single operation
${\mathcal{O}}:(h,\gamma)\to(h+\delta,\gamma+\delta)$. The triangle inequality
then implies that
$\Delta=({\mathcal{C}}_{N}^{{\mathcal{O}}_{1}}+{\mathcal{C}}_{N}^{{\mathcal{O}}_{2}})-{\mathcal{C}}_{N}^{{\mathcal{O}}}\geq
0$ (for further discussions, see the recent article Yangetal ). We find that

$\displaystyle\Delta|_{|h|<1}$ $\displaystyle=$
$\displaystyle\pm\frac{\delta^{3}}{32\gamma^{2}\left(1-h^{2}\right)}\pm\frac{\delta^{4}\left(8\gamma
h-3(1-h^{2})\right)}{192\gamma^{3}\left(1-h^{2}\right)^{2}}+{\mathcal{O}}(\delta^{5})$
$\displaystyle\Delta|_{|h|>1}$ $\displaystyle=$
$\displaystyle\pm\frac{\gamma\delta^{2}}{8{\mathcal{A}}^{3}}+{\mathcal{O}}(\delta^{3})~{},$
(12)

where the $+(-)$ sign in the first equation has to be used for $\gamma>0(<0)$,
respectively, and the $+(-)$ sign in the second equation has to be used for
$h>1(<-1)$, respectively. Thus, for $|h|<1$, at ${\mathcal{O}}(\delta^{2})$,
there is no contribution to $\Delta$.

Figure 1: $\Delta$ as a function of $h$ and $\gamma$ with $\delta=0.1$

However, as one approaches the critical lines $|h|=1$, the situation changes
and $\Delta$ starts getting contributions from ${\mathcal{O}}(\delta^{3})$
terms, enhanced by the $\sim(1-h)$ terms in the denominator of Eq. (12). There
is however no divergence here, as the power of the infinitesimals will always
be non-negative, as is apparent from this equation. Let us focus on the region
$\gamma>0$, and take $\delta>0$. With these assumptions, for
$h-1\sim{\mathcal{O}}(\delta)$ upto which our series expansion is maximally
valid, $\Delta|_{|h|<1}$ is positive definite, as should be the case. However,
we find that $\Delta|_{h<-1}$ becomes negative. The triangle inequality seems
to be violated here. To avoid this, we can define the target state as $(h+{\rm
sign}(h)\delta,\gamma+{\rm sign}(\gamma)\delta)$, in which case the violations
of the triangle inequality is avoided.

Doing this, the overall picture is that whereas deep in the ferromagnetically
or paramagnetically ordered phases, infinitesimal $\Delta$ is always close to
zero, it picks up a finite value when the path is close to a critical point,
the effect being enhanced when the multi-critical point is approached. All
these facts are illustrated in Figure (1), where we have defined the target
states along with the signs of the parameters as discussed above, and by
numerical integration, we show $\Delta$ on the $h-\gamma$ plane in the
thermodynamic limit, with $\delta=0.1$.

##  III Quench scenarios

We now consider the XY model with a quantum quench, assuming the sudden quench
approximation. Here, following the original work of ZanLE , we consider an XY
model environment coupled to a two-level central spin-1/2 system. Due to this
coupling, the wave function of the XY model evolves in two distinct branches,
as the central spin backreacts differently on the environment depending on
whether it is in the ground state $\ket{g}$ or the excited state $\ket{e}$. We
will take the interaction Hamiltonian to be $H_{I}$, so that the total
Hamiltonian is $H_{F}=H+H_{I}$, with $H$ given in Eq. (4), and

$\displaystyle H_{I}$ $\displaystyle=$ $\displaystyle
c_{1}\frac{\delta}{2}\ket{e}\bra{e}\sum\limits_{l=1}^{N}\sigma^{z}_{l}$ (13)
$\displaystyle-$ $\displaystyle
c_{2}\frac{\delta}{4}\ket{e}\bra{e}\sum\limits_{l=1}^{N}\left(\sigma^{x}_{l}\sigma^{x}_{l+1}-\sigma^{y}_{l}\sigma^{y}_{l+1}\right)~{}.$

The first coupling term which corresponds to a transverse quench was studied
in ZanLE  and the second one, corresponding to an anisotropic quench was
elaborated upon in AmitShraddhaVictor . Here, $c_{1},c_{2}=0,1$ correspond to
turning the coupling(s) off or on respectively, and we have taken the same
interaction strength $\delta$, which simplifies the computations considerably
while bringing out the essential physics.

By a fairly standard approach, one first writes the ground state
$\ket{\Psi_{0}}_{h,\gamma}$ of $H$ in terms of that of $H_{F}$, labeled
$\ket{\Psi_{0,k}}_{h+c_{1}\delta,\gamma+c_{2}\delta}$ for the $k$th Fourier
mode. This gives

$\ket{\Psi_{0}}_{h,\gamma}=\prod_{k>0}\left[\cos\Omega_{k}-i\sin\Omega_{k}\chi_{k}^{\dagger}\chi_{-k}^{\dagger}\right]\ket{\Psi_{0,k}}_{h+c_{1}\delta,\gamma+c_{2}\delta}~{},$
(14)

where we have defined

$\displaystyle\Omega_{k}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left[\theta_{k}(h,\gamma)-\theta_{k}(h+c_{1}\delta,\gamma+c_{2}\delta)\right]$
$\displaystyle\chi_{k}$ $\displaystyle=$
$\displaystyle\cos\left(\frac{\theta_{k}(h+c_{1}\delta,\gamma+c_{2}\delta)}{2}\right)c_{k}$
(15) $\displaystyle+$ $\displaystyle
i\sin\left(\frac{\theta_{k}(h+c_{1}\delta,\gamma+c_{2}\delta)}{2}\right)c_{-k}^{\dagger}~{},$

with the operators $c_{k}$ and $c_{-k}^{\dagger}$ being the Fourier operators,
and $\theta_{k}$ is the Bogoliubov angle defined in Eq. (8) with the arguments
appropriately defined.

To compute the complexity, the reference and the target states are chosen to
be $\ket{\Psi_{0}}_{h,\gamma}$ and $\ket{\Psi_{e}(t)}$ respectively, where,
for a transverse quench with $c_{1}=1$ and $c_{2}=0$ for example,
$\ket{\Psi_{e}(t)}=e^{-iH_{F}(h+\delta,\gamma)t}\ket{\Psi_{0}}_{h,\gamma}$,
i.e.,

$\displaystyle\ket{\Psi_{e}(t)}$ $\displaystyle=$
$\displaystyle\prod\limits_{k>0}\\!e^{-i\epsilon_{k}(h+\delta,\gamma)t}\bigg{[}\cos(\Omega_{k})-i\sin(\Omega_{k})\times$
(16)
$\displaystyle\chi_{k}^{\dagger}\chi_{-k}^{\dagger}e^{-2i\epsilon_{k}(h+\delta,\gamma)t}\bigg{]}\ket{\Psi_{0,k}}_{h+\delta,\gamma}.$

The computation of the NC is now standard, and was outlined in Liu . The final
result for a general quench is

${\mathcal{C}}_{N}(t)\equiv\sum\limits_{k}{\mathcal{C}}_{Nk}=\sum\limits_{k}\Phi_{k}^{2}(h+c_{1}\delta,\gamma+c_{2}\delta,t)~{},$
(17)

where

$\Phi_{k}=\arccos\left(\sqrt{1-\sin^{2}(2\Omega_{k})\sin^{2}(\epsilon_{k}(h+c_{1}\delta,\gamma+c_{2}\delta)t)}\right)~{},$
(18)

with the single particle excitations
$\epsilon_{k}(h+c_{1}\delta,\gamma+c_{2}\delta)=\sqrt{(h+c_{1}\delta+\cos
k)^{2}+(\gamma+c_{2}\delta)^{2}\sin^{2}k}$. We also record the expression for
the Loschmidt echo ${\mathcal{L}}$ given from Eq. (3). Noting that
$\ket{\Psi_{0}}_{h,\gamma}$ is an eigenket of $H$, we get
$\log{\mathcal{L}}=\sum_{k}{\mathcal{L}}_{k}$, with

${\mathcal{L}}_{k}=\log\left(1-\sin^{2}(2\Omega_{k})\sin^{2}(\epsilon_{k}(h+c_{1}\delta,\gamma+c_{2}\delta)t)\right)~{}.$
(19)

Evidently then, at small times, by expanding the arccosine and the logarithm,
we have the relation

${\mathcal{L}}\simeq e^{-{\mathcal{C}}_{N}}~{},~{}~{}t\to 0~{}.$ (20)

We now illustrate this with the transverse quench.

###  III.1 Transverse Quench : Complexity at small times

First, we consider a transverse quench, obtained by setting $c_{1}=1$ and
$c_{2}=0$ in Eq. (13). Here, for small $t$ and small $\delta$, we proceed by
expanding the complexity of Eq. (17) in an appropriate power series. Due to
the nature of the terms involved, a controlled expansion (in terms of a single
small parameter) is not possible here, and the two small parameters $t$ and
$\delta$ come with unequal powers. Hence we retain smallest powers in both.
Then, by following the same procedure as outlined in section (II), we get up
to low orders in $\delta$ and $t$,

$\displaystyle{\mathcal{C}}_{N}\big{|}_{|h|<1}$ $\displaystyle=$
$\displaystyle{\mathcal{C}}_{N}^{reg}+\frac{|\gamma|\delta^{2}t^{2}}{2\left(|\gamma|+1\right)}-\frac{h\gamma^{2}\delta^{3}t^{4}}{3(1+|\gamma|)^{2}}~{},$
$\displaystyle{\mathcal{C}}_{N}\big{|}_{|h|>1}$ $\displaystyle=$
$\displaystyle{\mathcal{C}}_{N}^{reg}+\frac{\gamma^{2}\delta^{2}t^{2}\left(|h|-{\mathcal{A}}\right)}{2{\mathcal{A}}\left(1-\gamma^{2}\right)}$
$\displaystyle\pm$
$\displaystyle\frac{\gamma^{2}\delta^{3}t^{4}\left(\gamma^{2}-|h|\left(\gamma^{2}+1\right)\left({\mathcal{A}}-|h|\right)-1\right)}{3{\mathcal{A}}\left(1-\gamma^{2}\right)^{2}}~{}.$

These are also the analytic expressions for $(-\log{\mathcal{L}})$ in the
small $t$ limit, in the mentioned regions of $h$. Here, the $+$ sign in the
second line of the second equation above is appropriate for $h>1$ while in the
region $h<-1$, one requires to use the $-$ sign. The higher orders terms in
these equations are lengthy, and we omit them for brevity. Also, the “regular”
term in the expressions (i.e., ones that do not have any pole in the complex
plane and are evaluated directly) is given by
${\mathcal{C}}_{N}^{reg}=-\frac{1}{12}\gamma^{2}\delta^{2}t^{4}$ to the order
that we are considering.

Figure 2: ${\mathcal{C}}_{N}$ and $(-\log{\mathcal{L}})$ as a function of $h$
for a transverse quench with $\gamma=0.5$ and $\delta=0.1$ for $t=0.5$
(bottom), $1$ (middle) and $1.5$ (top). The numerically computed
${\mathcal{C}}_{N}$ at $t=1.5$ is shown by the dashed black line, from which
$(-\log{\mathcal{L}})$ shown by the brown dotted line (at $t=1.5$) is
indistinguishable.

In Fig. (2), we show ${\mathcal{C}}_{N}$ computed from Eq. (LABEL:cnapprox) as
a function of $h$ for $\gamma=0.5$ and $\delta=0.1$, for three different
values $t=0.5$ (bottom), $t=1$ (middle) and $t=1.5$ (top). The numerically
computed values are indistinguishable for the first two values of $t$, and
starts differing from the approximate value of Eq. (LABEL:cnapprox) only for
larger values of the time, where is shown by the dashed black curve, which
depicts the numerical value of ${\mathcal{C}}_{N}$ computed from Eq. (17) at
$t=1.5$ for $(\gamma,\delta)=(0.5,0.1)$, in the thermodynamic limit. The
dotted brown line in the figure corresponds to $(-\log{\mathcal{L}})$ computed
numerically in the thermodynamic limit at $t=1.5$, which is indistinguishable
from ${\mathcal{C}}_{N}$, confirming Eq. (20). For values of $t$ smaller than
this, $(-\log{\mathcal{L}})$ is indistinguishable from ${\mathcal{C}}_{N}$
computed via Eq. (LABEL:cnapprox).

A similar analysis holds for the anisotropic quench, and we have left the
details to Appendix A. To compare with the transverse quench, we present the
behaviour of the ${\mathcal{C}}_{N}$ and $(-\log{\mathcal{L}})$ with $\gamma$
in Fig.(3) for the anisotropic quench case, using Eq. (30). The solid lines in
this figure correspond to $t=0.5$ (bottom), $t=1$ (middle) and $t=1.5$ (top).
As before, we find that the numerically evaluated value of ${\mathcal{C}}_{N}$
and $(-\log{\mathcal{L}})$ here are indistinguishable at small values of $t$
with the ones computed via Eq. (30), and that the difference coming for larger
values, depicted by the dashed black line corresponding to $t=1.5$. The dotted
brown line in this figure indicates $(-\log{\mathcal{L}})$ which is again
indistinguishable from ${\mathcal{C}}_{N}$, as was the case with the
transverse quench.

Figure 3: ${\mathcal{C}}_{N}$ and $(-\log{\mathcal{L}})$ as a function of
$\gamma$ for an anisotropic quench with $h=0.5$ and $\delta=0.1$ for $t=0.5$
(bottom), $1$ (middle) and $1.5$ (top). The numerically computed
${\mathcal{C}}_{N}$ at $t=1.5$ is shown by the black dashed line, which is
indistinguishable from $-(\log{\mathcal{L}})$ shown in dotted brown.

For both the transverse and the anisotropic quench schemes, it is clear from
Figures (2) and (3) that the NC, and the LE shows their nonanalytical nature
at the critical points i.e., $|h|=1$ and $\gamma=0$. As in the time-
independent case, this is how ${\mathcal{C}}_{N}$ is indicative of the zero
temperature quantum phase transitions at the Ising and the critical anisotropy
lines. We will now tie up this result with the QIM.

###  III.2 Transverse Quench : QIM at small times

As we have mentioned in the beginning of this section, the quench scenario
that we consider here is obtained by coupling the transverse XY model to a
central spin $1/2$ system. Once the interaction Hamiltonian is turned on, an
initially prepared ground state of the XY model $\ket{\Psi_{0}}_{h,\gamma}$
evolves in two branches, which we denote by
$\ket{\Psi_{g}(t)}=e^{-iHt}\ket{\Psi_{0}}_{h,\gamma}$ and
$\ket{\Psi_{e}(t)}=e^{-iH_{F}t}\ket{\Psi_{0}}_{h,\gamma}$. The full wave
function can then be written as

$\ket{\Psi(t)}=k_{g}{\ket{g}}\otimes\ket{\Psi_{g}(t)}+k_{e}{\ket{e}}\otimes\ket{\Psi_{e}(t)}~{},$
(22)

where the central two-level system is initially prepared in the normalised
state $k_{g}\ket{g}+k_{e}\ket{e}$. The precise values of the coefficients
$k_{g}$ and $k_{e}$ (with $|k_{g}|^{2}+|k_{e}|^{2}=1$) are unimportant as far
as the NC and the LE is concerned. However, if we want to find the QIM
corresponding to the full wavefunction, we find using Eq. (2) and Eq. (22)
that

$g_{ij}=|k_{g}|^{2}g^{g}_{ij}+|k_{e}|^{2}g^{e}_{ij}+|k_{g}k_{e}|^{2}{\mathcal{A}}_{i}{\mathcal{A}}^{*}_{j}~{},$
(23)

where
${\mathcal{A}}_{i}=\langle\partial_{i}\Psi_{g}(t)|\Psi_{g}(t)\rangle-\langle\partial_{i}\Psi_{e}(t)|\Psi_{e}(t)\rangle$.
Here, $g^{g}_{ij}$ and $g^{e}_{ij}$ are the metrics computed out of only the
ground or only the excited state wavefunctions in Eq. (22), respectively. For
$\delta=0$, ${\mathcal{A}}_{i}=0$ and we readily see that the QIM reduces to
that of the ground state of the transverse XY model. However, for non-zero
$\delta$, the situation is more intricate, although even in that case, in a
perturbative expansion in $\delta$, the ${\mathcal{O}}(\delta^{0})$ term in
$g^{e}_{ij}$ combines with $g^{g}_{ij}$ to produce the ground state QIM.

Now in order to compare with the NC or the LE, the full wavefunction is less
useful, and we will need to focus on the QIM computed out of
$\ket{\Psi_{e}(t)}$. This is because as we have already discussed, as far as
the NC is concerned, the reference and target states are taken to be
$\ket{\Psi_{0}}_{h,\gamma}$ and $\ket{\Psi_{e}(t)}$. Even if we took the
reference state to be $\ket{\Psi_{g}(t)}$, the NC (Eq. (17)) remains
unchanged, as $\ket{\Psi_{0}}_{h,\gamma}$ and $\ket{\Psi_{g}(t)}$ are related
only by a phase. To contrast the FSC with the NC and LE, it is then more
appropriate to compute the QIM corresponding to $\ket{\Psi_{e}(t)}$. Indeed,
as we will see now, this provides interesting insights.

Of course, one might wonder that for the transverse quench, since $\gamma$ is
held fixed, one would not obtain a meaningful metric tensor, since $h$ is the
only variable. Interestingly, in this case, we obtain a time component of the
metric. For the QIM of the ground state of the transverse XY model or for the
time evolved ground state, this is absent essentially due to the same argument
as above : the time evolution of $\ket{\Psi_{0}}_{h,\gamma}$ with $H$ simply
adds a constant phase factor. For $\ket{\Psi_{e}(t)}$, the situation is more
non-trivial, and gives rise to a $t-t$ component of the metric. The metric is
then meaningful in the $t-h$ plane.

We compute the information metric close to $t=0$, and for small $\delta$.
Using Eq. (16) in Eq. (2), we find here after an elaborate but straightforward
computation that there is a $\delta=0$ component of the QIM which reduces to
the QIM of the ground state of the transverse XY model reported in Zanardi ,
Polkov  (of which only the $g_{hh}$ component is relevant here, from the
arguments above). This is more appropriately related to $g^{g}_{ij}$ as
discussed after Eq. (23). The components proportional to powers of $\delta$
are the quantities of interest here and we present them below (we drop the
superscript $e$ in the expressions below to avoid cluttering of notation). We
get, up to the lowest orders in $t$ and $\delta$,

$\displaystyle g_{tt}\big{|}_{|h|<1}$ $\displaystyle=$
$\displaystyle\frac{|\gamma|\delta^{2}}{2\left(1+|\gamma|\right)}~{},$
$\displaystyle g_{tt}\big{|}_{|h|>1}$ $\displaystyle=$
$\displaystyle\frac{\gamma^{2}\delta^{2}\left(|h|-{\mathcal{A}}\right)}{2{\mathcal{A}}\left(1-\gamma^{2}\right)}~{},$
$\displaystyle g_{hh}\big{|}_{|h|<1}$ $\displaystyle=$
$\displaystyle-\frac{h\gamma^{2}\delta t^{4}}{3(1+|\gamma|)^{2}}~{},$
$\displaystyle g_{hh}\big{|}_{|h|>1}$ $\displaystyle=$
$\displaystyle\pm\frac{\gamma^{2}\delta
t^{4}\left(\gamma^{2}-|h|\left(\gamma^{2}+1\right)\left({\mathcal{A}}-|h|\right)-1\right)}{3{\mathcal{A}}\left(1-\gamma^{2}\right)^{2}}~{},~{}~{}$
$\displaystyle g_{th}$ $\displaystyle=$
$\displaystyle\frac{t}{\delta}g_{tt}+\frac{\delta}{t}g_{hh}-\frac{1}{6}\gamma^{2}\delta
t^{3}~{},$ (24)

where the $+(-)$ sign in the fourth equation refers to the region $h>1(h<-1)$,
respectively, and the expression for $g_{th}$ is valid for both the $|h|<1$
and $|h|>1$ regions. A similar analysis holds for the anisotropic quench, and
we have left the details to Appendix A. Note that the expression for $g_{tt}$
is exact. As can be checked from Eq. (2), there are no corrections to this
expression beyond ${\mathcal{O}}(\delta^{2})$.

From Eq. (LABEL:cnapprox) and Eq. (24), we readily see that the lowest order
terms in ${\mathcal{C}}_{N}$ and $d\tau^{2}$ is
${\mathcal{O}}(\delta^{2}t^{2})$, and at this order, we have
${\mathcal{C}}_{N}\sim d\tau^{2}$, once we identify in the line element
$dh\sim\delta$ and $dt\sim t$ (as appropriate for small times). Hence
${\mathcal{L}}=e^{-d\tau^{2}}$ for small times and to lowest order in the
perturbing parameter $\delta$. The more general relation valid up to the order
that we consider in Eqs. (LABEL:cnapprox) and (24) is given as
$3{\mathcal{C}}_{N}=d\tau^{2}-{\mathcal{C}}_{N}^{reg}$ where the last term was
defined after Eq. (LABEL:cnapprox). That this last relation holds in the case
of the anisotropic quench as well can be checked from the formulae presented
in Appendix A.

Whereas the relation between ${\mathcal{C}}_{N}$ and ${\mathcal{L}}$
essentially followed from their form at small times, the outlined relation
with the line element of the QIM does not. Indeed, for the time-independent
case, the relation ${\mathcal{C}}_{N}\sim d\tau^{2}$ between the NC and the
QIM follows by definition of ${\mathcal{C}}_{N}$ tapo1 . However, in the
present situation, one cannot possibly guess this relation from the definition
of ${\mathcal{C}}_{N}$ in Eq. (17). Quite surprisingly, the $t-t$ component of
the QIM plays a crucial role here. The fact that the three fundamental
quantities used in the study of quantum information theory are related by a
simple formula is indeed quite striking. We have established this here for a
specific case of the transverse XY model.

###  III.3 Transverse Quench : FSC at small times

Having obtained the QIM, we now investigate the FSC for the transverse
quenched model. We need to carefully clarify the meaning of the FSC here. As
we have already mentioned, the QIM computed from $\ket{\Psi_{e}(t)}$ also
“contains” the static case, namely the ground state QIM appears at
$\mathcal{O}(\delta^{0})$. However, this is more appropriately associated with
the branch of the XY model that couples with the ground state of the central
spin half system. Hence, it makes sense to study that part of metric which is
dependent on $\delta$ and reflects the true effects of the coupling of the XY
model to the central spin. What we need to do here is to compute $\tau$ as a
function of the model parameters, and it will be enough for us to focus on the
region $|h|<1$ to illustrate our point. We consider three cases, with
$\gamma=0.5$, and take the initial value of the time to be $0.01$. In the
first case, we consider $h=0.88,\delta=0.1$, the second case being
$h=0.90,\delta=0.05$, and the third is $h=0.92,\delta=0.01$. In all cases, we
numerically solve the two geodesic equations arising from Eq. (24) with
appropriate boundary conditions, which involve the initial values of $t$ and
$h$, and their derivatives with respect to the affine parameter. While in all
cases we fix the initial value $dh/d\tau=-0.1$, the initial value of
$dt/d\tau$ is fixed from the normalisation condition
$g_{ij}(dx^{i}/d\tau)(dx^{j}/d\tau)=1$. This then determines the geodesic
evolution of $h$ with time. Now having obtained the numerical solution of the
geodesic equations, we invert them using a standard root finding procedure in
Mathematica. This will then give us the solution of the FSC as a function of
$h$, up to the phase boundary.

Figure 4: The affine parameter $\tau$ as a function of $h$ for initial values
$h=0.88$ (solid red), $h=0.90$ (dashed blue) and $h=0.92$ (dotted black).

Fig. (4) shows the affine parameter $\tau$ as a function of $h$, with the
initial values chosen as $h=0.88$ (solid red), $h=0.90$ (dashed blue) and
$h=0.92$ (dotted black). Clearly, there is no special behaviour of $\tau$ as
we reach the phase boundary $h=1$. The reason for this is clear. The metric
for the excited state wavefunction at small times is regular throughout the
region $|h|<1$ and so is the Ricci scalar computed out of this metric. The
$(t,h)$ parameter manifold is thus divergence-free and this information is
reflected in the behaviour of the geodesics.

##  IV Transverse Quench : Complexity at finite times

We will now consider the NC and the LE for a transverse quench at finite
times, given from Eqs. (17) and (19), where we turn off the perturbation on
$\gamma$. The analysis of ${\mathcal{C}}_{N}$ and ${\mathcal{L}}$ become
complicated here, due to the nature of the expressions involved. However, we
can make the following statements in momentum space.

Figure 5: $\sin^{2}(2\alpha_{k})$ (solid blue), ${\mathcal{C}}_{Nk}$ at $t=20$
(dashed black) and ${\mathcal{C}}_{Nk}$ at $t=200$ (solid red) as a function
of $k$ for $h=0.8,\gamma=0.5,\delta=0.1$. ${\mathcal{L}}_{k}$ is plotted in
dashed brown and is indistinguishable from the ${\mathcal{C}}_{Nk}$ graphs.

First, we note that due to the nature of $\Omega_{k}$ and $\epsilon_{k}$ given
in Eq. (17), ${\mathcal{C}}_{Nk}$ and ${\mathcal{L}}_{k}$ are oscillatory
functions of $k$, with the oscillation amplitude controlled by the
$\sin^{2}(2\alpha_{k})$, which acts as a modulation function, away from the
Ising transition lines $h=\pm 1$. We have depicted this in Fig. (5), where we
have taken $h=0.8,\gamma=0.5$ and $\delta=0.1$. Here, the solid blue line
represents $\sin^{2}(2\alpha_{k})$. The black dashed line gives
${\mathcal{C}}_{Nk}$ at $t=20$ while the solid red line represents
${\mathcal{C}}_{Nk}$ at $t=200$. In this figure, we have also plotted
${\mathcal{L}}_{k}$, which are indistinguishable from the ${\mathcal{C}}_{Nk}$
lines. From the figure, we see that while a single Fourier mode contributes
maximally to ${\mathcal{C}}_{Nk}$ and ${\mathcal{L}}_{k}$ for small but finite
times, several modes start contributing as the time increases.

Figure 6: $\sin^{2}(2\alpha_{k})$ (solid blue), ${\mathcal{C}}_{Nk}$ at
$t=200$ (dashed red) and ${\mathcal{L}}_{k}$ at $t=200$ (dashed brown) as a
function of $k$ for $h=0.95,\gamma=0.5,\delta=0.1$. The horizontal line marks
the position of unity.

Away from the critical lines, $\sin^{2}(2\alpha_{k})\ll 1$, and hence so is
$\sin^{2}(2\alpha_{k})\sin^{2}(t\epsilon_{k})$ for all times. Thus, the
perturbatively valid relation ${\mathcal{L}}=e^{-{\mathcal{C}}_{N}}$ continues
to hold at finite times in these regions. As one approaches $h\to 1$, this
picture is more challenged, with the additional features being that the
maximum of $\sin^{2}(2\alpha_{k})$ shifts towards $k=\pi$, and its maximum
value approaches unity. This is shown in Fig. (6), where the solid blue line
represents $\sin^{2}(2\alpha_{k})$ and the solid red and dashed brown
oscillating line gives ${\mathcal{C}}_{Nk}$ and ${\mathcal{L}}_{k}$
respectively, for $h=0.95,\gamma=0.5,\delta=0.1$. In these cases, the relation
between ${\mathcal{C}}_{N}$ and ${\mathcal{L}}$ cannot be expresses in an
exact form.

Note that when $h+\delta=1$, the maximum of $\sin^{2}(2\alpha_{k})\to 1$ at
$k\sim\pi$. Then, the maximally contributing mode is the one for which $k$ is
close to $\pi$. This is the situation when after the quench the system is on
the Ising critical line. We depict this in Fig. (7), where the same color
coding as Fig. (6) is used.

Figure 7: $\sin^{2}(2\alpha_{k})$ (solid blue), ${\mathcal{C}}_{Nk}$ at
$t=200$ (solid red) and ${\mathcal{L}}_{k}$ at $t=200$ as a function of $k$
for $h=0.9,\gamma=0.5,\delta=0.1$. The horizontal line marks the position of
unity.

What we further glean from the above analysis regarding the temporal
dependence of ${\mathcal{C}}_{N}$ and ${\mathcal{L}}$ in the thermodynamic
limit is the following. For $h$ away from the Ising critical line, for finite
$t$, initially a single Fourier mode contributes maximally to
${\mathcal{C}}_{N}$ and ${\mathcal{L}}$, but as $t$ increases, more Fourier
modes start contributing to these. As a function of time, this results in the
fact that while ${\mathcal{C}}_{N}$ and ${\mathcal{L}}$ are initially
oscillatory functions at finite time, the oscillations die out rapidly (the
contributing modes “interfere” destructively, as they combine from both sides
of the maximum in $k$ space). For $h$ close to the Ising transition line, the
mode at $k\simeq\pi$ contributes maximally to ${\mathcal{C}}_{N}$ and
${\mathcal{L}}$. For $h+\delta=1$, i.e., when the quenched state is on the
Ising transition line, $\epsilon_{k}\sim\pi-k\to 0$, so that the time period
of temporal oscillations effectively become infinite. There are thus no finite
time oscillations in this case. On the contrary, when $h=1$, i.e., the initial
state is on the Ising transition line, $\epsilon_{k}\to\delta$, and since no
other mode contributes significantly to ${\mathcal{C}}_{N}$ or
${\mathcal{L}}$, the oscillations continue for large times before dying down.

The above arguments are only approximate, but do capture the essential
behaviour of ${\mathcal{C}}_{N}$ and ${\mathcal{L}}$, as shown in Fig. (8)
where we choose $\gamma=0.5$ and $\delta=0.1$. In this figure, the large-
dashed red, blue, black and brown lines correspond to the time dependence of
${\mathcal{C}}_{N}$ for $h=0.8$, $0.9$, $1$ and $1.1$, respectively, while the
dotted lines of the corresponding colours show these for ${\mathcal{L}}$. As
can be seen, the curves in the figure conform to our discussion above. Namely,
for $h=0.8$ and $1.1$, there is no difference between ${\mathcal{C}}_{N}$ and
$(-\log{\mathcal{L}})$, and these are indistinguishable. The difference
becomes apparent when $h$ approaches unity on the ferromagnetic side. We have
also marked by the horizontal dashed red and dashed brown lines the large time
behaviour of ${\mathcal{C}}_{N}$, which will be discussed in the next section.

Figure 8: ${\mathcal{C}}_{N}$ (large dashed lines) and $(-\log{\mathcal{L}})$
(dotted lines) as a function of $t$ with $\gamma=0.5$ and $\delta=0.1$. The
red, blue, black and brown lines are for $h=0.8$, $0.9$, $1$ and $1.1$,
respectively. The horizontal dashed red and dashed brown lines denote the
large $t$ values for $h=0.8$ and $h=1.1$, respectively.

Before ending this section, we point out that there is another special case
where the analysis is simplified, and one can obtain analytical results,
namely for $h+\delta=0$. Here, taking $\gamma=1$ for example, it is seen that
$\epsilon_{k}=1$ and therefore ${\mathcal{C}}_{Nk}$ does not have any
oscillatory behaviour as a function of $k$. Hence, the temporal oscillations
do not die out in this particular case.

##  V Transverse Quench : Complexity at large times

At large times, the analysis of the complexity is not difficult. Our
observation here is that for such times, $\sin^{2}(\epsilon_{k}t)$ of Eq. (18)
becomes a rapidly oscillating function of momentum $k$, as with increasing
$t$, a very large number of maxima (and minima) of the sin squared function
can be accommodated between $0<k<\pi$. Hence, when a large number of Fourier
modes contribute to the NC, then to a good approximation, since
$\sin^{2}(2\Omega_{k})$ is a slowly varying function, we can set
$\sin^{2}(\epsilon_{k}t)=1/2$, i.e., its averaged value over $k$. This becomes
challenged in two special cases, where $h=1$ and $h+\delta=1$, essentially
because a single mode contributes maximally to ${\mathcal{C}}_{N}$ even at
large $t$, and the oscillatory behaviour of $\sin^{2}(\epsilon_{k}t)$ is less
relevant there. This can already be seen in Fig. (8), for the cases $h=0.8$
and $h=1.1$ the dashed red and dashed brown horizontal lines where the value
of ${\mathcal{C}}_{N}$ for the horizontal lines were computed numerically
after setting $\sin^{2}(\epsilon_{k}t)=1/2$ and one can see that these are
indeed the large time values of the NC for the corresponding values of the
parameters.

If we do not quench from or on the Ising transition lines, then to a very good
approximation we have, ${\mathcal{C}}_{N}(t\to\infty)=\sum_{k}\Phi_{k}^{2}$,
with $\Phi_{k}=\arccos(\sqrt{1-\sin^{2}(2\Omega_{k})/2})$. To lowest order in
perturbation therefore,
${\mathcal{C}}_{N}(t\to\infty)\sim\delta^{2}\sum_{k}(\partial\theta_{k}/\partial
h)^{2}$, which is precisely $\delta^{2}$ times the information metric $g_{hh}$
of the time-independent case. We get in this case,

$\displaystyle{\mathcal{C}}_{N}\big{|}_{|h|<1}(t\to\infty)$ $\displaystyle=$
$\displaystyle\frac{\delta^{2}}{8|\gamma|\left(1-h^{2}\right)}+\frac{h\delta^{3}}{8|\gamma|\left(1-h^{2}\right)^{2}}$
$\displaystyle-$
$\displaystyle\frac{\delta^{4}\left(13\gamma^{2}+\left(39\gamma^{2}+7\right)h^{2}-7\right)}{384|\gamma|^{3}\left(h^{2}-1\right)^{3}}$
$\displaystyle{\mathcal{C}}_{N}\big{|}_{|h|>1}(t\to\infty)$ $\displaystyle=$
$\displaystyle\frac{\gamma^{2}\delta^{2}|h|}{8\left(h^{2}-1\right){\mathcal{A}}^{3}}$
$\displaystyle\mp$
$\displaystyle\frac{\gamma^{2}\delta^{3}\left(\gamma^{2}+4h^{4}+\left(\gamma^{2}-3\right)h^{2}-1\right)}{16\left(h^{2}-1\right)^{2}{\mathcal{A}}^{5}}~{}.$

The first few terms of the two equations above are indeed the ones we obtained
in the static case, in Eq. (9), confirming our argument.

Figure 9: ${\mathcal{C}}_{N}$ and $(-\log{\mathcal{L}})$ as a function of $h$
with $\gamma=0.5$ and $\delta=0.1$, at large $t$. The dashed black curve is
the numerically computed value of ${\mathcal{C}}_{N}$ at $t=1000$, and is
indistinguishable from that of $(-\log{\mathcal{L}})$ shown in dotted red away
from the phase boundaries. The solid red and blue curves are the ones computed
from Eq. (LABEL:tinf1).  Figure 10: $g_{hh}$ as a function of $h$ with
$\gamma=0.5$ and $\delta=0.1$, at $t=200$. The solid lines are computed with
Eq. (26) while the dashed black line shows the result of numerical
integration.

So the picture that emerges after a transverse quench is the following. Once
the two level system is coupled to the transverse XY model environment, the
ground state of the XY model splits and evolves in two branches. As far as the
NC is concerned, the initial evolution of the two branches give rise to
completely different structures of the complexity. However, at large times,
these become identical to the static case. The physical reason here is not
difficult to guess. At large times, the NC is essentially independent of time,
given any reference and target states, as temporal oscillations die out. Then,
it is but natural that this is similar to the static case, since there are no
time scales in the problem. As an aside, we note that the only special case
where this will not hold is when $h+\delta=0$, as we have argued at the end of
section (IV). In that case however, the perturbative expansion in $\delta$
breaks down.

The large time behaviour of ${\mathcal{C}}_{N}$ and $(-\log{\mathcal{L}})$ is
shown in Fig. (9), where the dashed black line corresponds to
${\mathcal{C}}_{N}$ and the dotted red to $(-\log{\mathcal{L}})$, at $t=1000$,
confirming our arguments above. The solid lines are the ones computed from Eq.
(LABEL:tinf1). Here, we have chosen $\gamma=0.5$ and $\delta=0.1$. Comparing
with Fig. (2), we see that starting from small times, the flat region between
$h=\pm 1$ essential curves downwards so that at large times, the shape
depicted in Fig. (9) is reached. We also note that close to criticality,
$(-\log{\mathcal{L}})$ is a few times ${\mathcal{C}}_{N}$. The reason should
be clear from Fig. (7), from which we glean that ${\mathcal{L}}_{k}$ is
proportional to $\mathcal{C}_{nk}$ in these regions.

###  V.1 Transverse Quench : QIM at large times

At large times, it is straightforward to compute the IM, by analysing the
expression appearing from Eq. (16). After dropping additive terms that are
highly oscillatory in the momentum space, and average to zero, we expand the
rest in powers of $\delta$. We find that up to ${\mathcal{O}}(\delta^{2})$,

$\displaystyle g_{tt}\big{|}_{|h|<1}$ $\displaystyle=$
$\displaystyle\frac{|\gamma|\delta^{2}}{2\left(1+|\gamma|\right)}~{},$
$\displaystyle g_{hh}\big{|}_{|h|<1}$ $\displaystyle=$
$\displaystyle\frac{h\delta}{8|\gamma|\left(1-h^{2}\right)^{2}}$
$\displaystyle+$
$\displaystyle\frac{\delta^{2}\left(\gamma^{2}\left(16\left(1-h^{2}\right)^{2}t^{2}+69h^{2}+23\right)+3(1-h^{2})\right)}{256|\gamma|^{3}\left(1-h^{2}\right)^{3}}~{},$
$\displaystyle g_{ht}\big{|}_{|h|<1}$ $\displaystyle=$ $\displaystyle 0~{},$
(26)

with the corresponding expressions for the region $|h|>1$ being too lengthy to
reproduce here.

Figure 11: $\tau$ as a function of $h$ with $\gamma=0.5$ and $\delta=0.1$, at
$t=200$, computed from Eq. (26). Here, the solid red, dashed blue and dotted
black lines correspond to the initial values of $h=0.8$, $0.85$ and $0.9$,
respectively.

Unlike the NC, the QIM at large times is different from the static case
derived in Zanardi , Polkov , although curiously at the lowest order,
$g_{hh}dh^{2}$ has the same form as the first correction to the ground state
complexity of Eq. (9), upon identifying $dh\sim\delta$. Importantly, here the
$t-t$ component of the metric on the branch coupled to the excited state of
the central spin half system remains the same as in the limit of small times,
and hence at large times the QIM does not reduce to the static situation.

One can now compute the geodesics on this parameter manifold, as discussed in
subsection III.3. We depict this pictorially in Fig. (11), where we have
chosen $\gamma=0.5$, $\delta=0.1$, at the starting time is $t=200$. In this
figure, the solid red, dashed blue and dotted black lines correspond to the
initial values of $h=0.8$, $0.85$ and $0.9$, respectively. We see that the FSC
exhibits expected behaviour here, i.e., the derivative of $\tau$ diverges near
the critical line $h=1$. For $t\to\infty$, this divergence is
$\sim(1-h)^{-3/2}$.

##  VI Scaling relations for the NC

From our discussion in section (IV), it should be clear that almost all
results that have been derived in the literature regarding the finite size
scaling relations of ${\mathcal{L}}$ (see, e.g., LE3  and references therein)
will continue to remain valid for the exponential of $(-{\mathcal{C}}_{N})$.
Hence a separate analysis of the finite size behaviour of ${\mathcal{C}}_{N}$
is not necessary. For example, for both for large and small times,

$\frac{\partial{\mathcal{C}}_{N}(t)}{\partial\lambda}\sim N~{}.$ (27)

with $\lambda=h,\gamma$. For completeness, we will record the behaviour of the
derivative of ${\mathcal{C}}_{N}$ with respect to the system parameters. For
small times, we get

$\frac{1}{N}\frac{\partial{\mathcal{C}}_{N}(t)}{\partial(h+\delta)}\sim|h+\delta\pm
1|~{},~{}~{}\frac{1}{N}\frac{\partial{\mathcal{C}}_{N}(t)}{\partial(\gamma+\delta)}\sim|\gamma+\delta|~{},$
(28)

near the Ising transition line and the anisotropic transition line,
respectively. For large times, these relations change to

$\frac{1}{N}\frac{\partial{\mathcal{C}}_{N}(t\rightarrow\infty)}{\partial(h+\delta)}\sim\log|h+\delta\pm
1|~{},~{}~{}\frac{1}{N}\frac{\partial{\mathcal{C}}_{N}(t\rightarrow\infty)}{\partial(\gamma+\delta)}\sim\log|\gamma+\delta|~{}.$
(29)

##  VII Conclusions

The Nielsen complexity, the Fubini-Study complexity and the Loschmidt echo are
three fundamental quantities of interest in studies on quantum criticality. In
this paper, we have performed a detailed analysis of these quantities for the
transverse XY model in the presence of a sudden quantum quench, in the
thermodynamic limit. The complexities were considered both in a static
scenario as well as one involving the quench, and we compared the latter to
the LE. While the NC in a static scenario was considered by us earlier in
tapo1 , here we have computed analytical expressions for the NC and the FSC
both in the static as well as the quench scenarios in a perturbative setup, in
the small and large time limits. This also gives analytical expressions for
the LE, from what we have discussed.

We have shown that at small times, these quantities are related by
${\mathcal{L}}=e^{-{\mathcal{C}}_{N}}\sim$ $e^{-d\tau^{2}}$. The simple
relation between the three physical quantities at small times is indeed
remarkable. However, although the first relation here continues to hold at
large times, the second one does not. To wit, the evolution of the transverse
XY chain proceeds in two distinct branches, in which the ground state of the
model is coupled to the ground and the excited states of the central spin. As
far as the NC is concerned, after a long time, temporal oscillations die down
and the NC reduces to the static case, as we have argued. The QIM, on the
other hand, evolves differently, and its large time behaviour bears little
resemblance to the static scenario, in the presence of a time component of the
metric.

Note that in this paper, we have considered only the transverse field XY
model. Now, as discussed in tapo1 , general features of the analysis here
should be applicable to all quadratic Hamiltonians, as these only depend on
the Bogoliubov angle. We end by commenting that in quench scenarios, the
triangle inequality associated to the NC seems to be violated for both small
and finite times, as we have checked both analytically and numerically. The
exact implication of this is unclear to us as of now, and this warrants
further study.

Acknowledgments

N. J. would like to acknowledge the University Grant Commission (UGC), India,
for providing financial support. The work of T. S. is supported in part by
Science and Engineering Research Board (India) via Project No.
EMR/2016/008037.

## Appendix A

In this appendix, we will list the computation of the NC and the IM for an
anisotropic quench, at small times. The results for the region $|h|>1$ become
lengthy and we will only present those in the region $|h|<1$. Here, we find
the lowest order terms

$\displaystyle{\mathcal{C}}_{N}\big{|}_{|h|<1}$ $\displaystyle=$
$\displaystyle{\mathcal{C}}_{N}^{reg}+\frac{\delta^{2}t^{2}\left(|\gamma|+2|\gamma|h^{2}+1\right)}{4(|\gamma|+1)^{3}}\mp\frac{|\gamma|\delta^{3}t^{4}\left(3+|\gamma|{\mathcal{B}}\right)}{24(|\gamma|+1)^{5}}~{},~{}$
$\displaystyle{\mathcal{B}}$ $\displaystyle=$
$\displaystyle|\gamma|(|\gamma|+5)-8h^{4}+4(|\gamma|+1)(|\gamma|+4)h^{2}+7~{},~{}$
$\displaystyle{\mathcal{C}}_{N}^{reg}$ $\displaystyle=$
$\displaystyle-\frac{1}{48}\delta^{2}\left(4h^{2}+1\right)t^{4}~{},$ (30)

where the $-(+)$ sign is for $\gamma>0(<0)$, respectively. The IM is given to
lowest order by

$\displaystyle g_{tt}$ $\displaystyle=$
$\displaystyle\frac{\delta^{2}\left(|\gamma|+2|\gamma|h^{2}+1\right)}{4(|\gamma|+1)^{3}}~{},~{}g_{\gamma\gamma}=\mp\frac{t^{4}|\gamma|\delta\left(3+|\gamma|{\mathcal{B}}\right)}{24(|\gamma|+1)^{5}}~{},~{}$
$\displaystyle g_{t\gamma}$ $\displaystyle=$
$\displaystyle\frac{t}{\delta}g_{tt}+\frac{\delta}{t}g_{\gamma\gamma}-\frac{1}{24}\delta\left(4h^{2}+1\right)t^{3}~{}.$
(31)

## References

  * (1) S. Arora, and B. Barak, Computational complexity: a modern approach, (Cambridge University Press, 2009).
  * (2) C. Moore, and S. Mertens, The Nature of Computation, (Oxford University Press, 2011).
  * (3) S. Lloyd, Ultimate physical Limits to computation, Nature 406, (2000) 1047, [quant-ph/9908043].
  * (4) R. Jefferson, and R. C. Myers, JHEP 1710, 107 (2017).
  * (5) M. Guo, J. Hernandez, R. C. Myers and S. M. Ruan, JHEP 1810, 011 (2018).
  * (6) L. Susskind, Computational Complexity and Black Hole Horizons, Fortsch. Phys. 64, (2016), arXiv:1403.5695 [hep-th].
  * (7) A. R. Brown, D. A. Roberts, L. Susskind, B. Swingle, and Y. Zhao, Phys. Rev. Lett. 116, 191301 (2016), arXiv:1509.07876 [hep-th].
  * (8) A. R. Brown, D. A. Roberts, L. Susskind, B. Swingle, and Y. Zhao, Phys. Rev. D 93, 086006 (2016), arXiv:1512.04993 [hep-th].
  * (9) M. A. Nielsen, arXiv:quant-ph/0502070 [quant-ph].
  * (10) M. A. Nielsen, M. R. Dowling, M. Gu, and A. M. Doherty, Science 311 (2006) 1133.
  * (11) M. A. Nielsen, and M. R. Dowling, arXiv:quant-ph/0701004 [quant-ph].
  * (12) F. Liu, S. Whitsitt, J. B. Curtis, R. Lundgren, P. Titum, Z. C. Yang, J. R. Garrison and A. V. Gorshkov, Phys. Rev. Res. 2, 013323 (2020).
  * (13) Z. Xiong, D.-X. Yao, and Z. Yan, Phys. Rev. B 101, 174305 (2020).
  * (14) R. Khan, C. Krishnan, and S. Sharma, Phys. Rev. D 98, 126001 (2018).
  * (15) N. Jaiswal, M. Gautam, and T. Sarkar, Phys. Rev. E 104, 024127 (2021).
  * (16) S. Chapman, M. P. Heller, H. Marrochio and F. Pastawski, Phys. Rev. Lett. 120, 121602 (2018).
  * (17) I. Bengtsson, and K. Zyczkowski, Geometry of Quantum States: An Introduction to Quantum Entanglement (Cambridge University Press, 2007).
  * (18) J. P. Provost, and G. Vallee, Commun. Math. Phys. 76, 289 (1980).
  * (19) M. Kolodrubetz, V. Gritsev, and A. Polkovnikov, Phys. Rev. B 88, 064304 (2013).
  * (20) P. Zanardi, P. Giorda, and M. Cozzini, Phys. Rev. Lett. 99 100603 (2007).
  * (21) R. Maity, S. Mahapatra, and T. Sarkar, Phys. Rev. E 92, 052101 (2015).
  * (22) A. Dey, S. Mahapatra, P. Roy, and T. Sarkar, Phys. Rev. E 86, 031137 (2012), arXiv:1208.4710 [cond-mat.stat-mech]
  * (23) S. Montes, and A. Hamma, Phys. Rev. E 86, 021101 (2012).
  * (24) L. C. Venuti, and P. Zanardi, Phys. Rev. Lett. 99, 095701 (2007).
  * (25) A. Peres, Phys. Rev. A 30, 1610 (1984).
  * (26) J. Häppölä, G. B. Halász, and A. Hamma, Phys. Rev. A 85, 032114 (2012).
  * (27) T. Ali, A. Bhattacharyya, S. S. Haque, E. H. Kim, and N. Moynihan, (2020), arXiv:1811.05985 [hep-th]
  * (28) T. Ali, A. Bhattacharyya, S. S. Haque, E. H. Kim, and N. Moynihan, (2020), arXiv:1810.02734 [hep-th]
  * (29) H. A. Camargo, P. Caputa, D. Das, M. P. Heller, and R. Jefferson, Phys. Rev. Lett. 122, 081601 (2019).
  * (30) H. T. Quan, Z. Song, X. F. Liu, P. Zanardi, and C. P. Sun, Phys. Rev. Lett. 96, 140604 (2006).
  * (31) Z.-G. Yuan, P. Zhang, and S.-S. Li, Phys. Rev. A 75, 012102 (2007).
  * (32) D. Rossini, T. Calarco, V. Giovannetti, S. Montangero, and R. Fazio, Phys. Rev. A 75, 032333 (2007).
  * (33) R. Jafari, and H. Johannesson, Phys. Rev. Lett. 118, 015701 (2017).
  * (34) M. Zhong and P. Tong, Phys. Rev. A 84, 052105 (2011).
  * (35) A. Rajak and U. Divakaran, J. Stat. Mech. (2014), P04023.
  * (36) J. F. Huang, Y. Li, J. Q. Liao, L. M. Kuang, and C. P. Sun, Phys. Rev. A 80, 063829 (2009).
  * (37) S. Sharma, V. Mukherjee, and A. Dutta, Eur. Phys. J. B 85, 143 (2012).
  * (38) R. Q. Yang, Y. S. An, C. Niu, C. Y. Zhang and K. Y. Kim, Eur. Phys. J. C 79, no.2, 109 (2019)


# A problem on distance matrices of subsets of the Hamming cube

Ian Doust  School of Mathematics and Statistics, UNSW Sydney NSW 2052,
Australia<EMAIL_ADDRESS>and  Reinhard Wolf  Institut für Mathematik,
Universität Salzburg, Hellbrunnerstrasse 34, A-5020 Salzburg, Austria
<EMAIL_ADDRESS>
(Date: September 2021)

###### Abstract.

Let $D$ denote the distance matrix for an $n+1$ point metric space $(X,d)$. In
the case that $X$ is an unweighted metric tree, the sum of the entries in
$D^{-1}$ is always equal to $2/n$. Such trees can be considered as affinely
independent subsets of the Hamming cube $H_{n}$, and it was conjectured that
the value $2/n$ was minimal among all such subsets. In this paper we confirm
this conjecture and give a geometric interpretation of our result which
applies to any subset of $H_{n}$.

###### 2010 Mathematics Subject Classification:

Primary 46B85; Secondary 15A45, 51K99

##  1\. Introduction

There is a long study of the interaction between properties of finite metric
spaces and properties of their distance matrices. The most classical questions
in this area concern whether the metric space can be isometrically embedded in
a Euclidean space, a problem solved by Schoenberg [14], or else in some other
standard normed space. Properties of the metric space are often reflected in
linear algebraic properties of the distance matrix involving say the
determinant or inverse of the matrix.

To fix some notation, let $(X,d)$ denote a finite metric space with elements
$\\{x_{1},\dots,x_{m}\\}$ (with $m\geq 2$) and let $D=D_{X}$ denote its
distance matrix $(d(x_{i},x_{j}))_{i,j=1}^{m}$.

One particular class of spaces for which this relationship has been much
studied are those which are (isometric to) subsets of Hamming cubes
$H_{n}=\\{0,1\\}^{n}$ with the Hamming metric $d_{1}$ (which is the $\ell^{1}$
metric on ${\mathbb{R}}^{n}$, restricted to these spaces). (See, for example,
[2, 3, 4, 5, 6].) This class includes, for example, all unweighted metric
trees. Much of [2] concerns extending Graham and Pollak’s [4] formula,
$\det(D)=(-1)^{n}n2^{n-1}$, for the distance matrix of an $n+1$ point
unweighted metric tree.

If $X$ is an $n+1$ point unweighted metric tree in $H_{n}$, then $D$ is
invertible. It was shown in [2] that in this case the sum of the entries in
$D^{-1}$ is always $2/n$ and it was conjectured that this was minimal among
all affinely independent subsets of $H_{n}$. Let $\mathbf{1}$ denote the
vector $(1,\dots,1)^{T}\in{\mathbb{R}}^{m}$ so that $\langle
D^{-1}\mathbf{1},\mathbf{1}\rangle$ gives the sum of the entries in $D^{-1}$.
The aim of this note is to prove the conjecture in [2] and to provide
geometric interpretations for the value of this quantity.

A consequence of Theorem 5.1 below will be the following two results.

######  Theorem 1.1.

Suppose that $X$ is an affinely independent subset of the Hamming cube
$(H_{n},d_{1})$ with at least two points. Then

(1) $\langle
D^{-1}\mathbf{1},\mathbf{1}\rangle=\left(\frac{n}{2}-2d_{2}(h,Z_{X})^{2}\right)^{-1}$

where $d_{2}(h,Z_{X})$ is the Euclidean distance from the point
$h=\bigl{(}\frac{1}{2},\dots,\frac{1}{2}\bigr{)}$ to the affine subspace
$Z_{X}\subseteq{\mathbb{R}}^{n}$ spanned by the elements of $X$.

######  Corollary 1.2.

Suppose that $X$ is an affinely independent subset of the Hamming cube
$(H_{n},d_{1})$ with at least two points. Then

$\frac{2}{n}\leq\langle D^{-1}\mathbf{1},\mathbf{1}\rangle\leq 2.$

###### Proof.

Let $x$ and $y$ be two distinct points in $X$. The point
$m=(x+y)/2=(m_{1},\dots,m_{n})$ must lie in $Z_{X}$ and so
$d_{2}(h,Z_{X})\leq\|h-m\|_{2}$. Note that for each $j$,
$\bigl{|}m_{j}-\frac{1}{2}\bigr{|}$ is either $0$ or $\frac{1}{2}$, and, as
$x$ and $y$ are distinct, the value 0 must occur for at least one value of
$j$. Thus $\|h-m\|_{2}^{2}\leq(n-1)/4$ and so
$\frac{1}{2}\leq\frac{n}{2}-2d_{2}(h,Z_{X})^{2}\leq\frac{n}{2}$. Together with
(1), this then implies the result. ∎

######  Remark 1.3.

Formula (1) is somewhat remarkable as the left-hand side only depends on the
distances between the points, and not their positions. On the other hand, the
quantity $d_{2}(h,Z_{X})$ depends only on the linear relationship between the
points of $X$, and does not appear to depend on their relative distances. This
will be illustrated with some examples at the end of the paper.

Vital to the proof of (1) are the facts that the Hamming cube is of
$1$-negative type, and that the natural embedding of $H_{n}$ into
${\mathbb{R}}^{n}$ is a so-called S-embedding. The definitions of these
concepts are given in Section 2. Equation (1) is essentially a special case of
a formula involving the $M$-constant $M(X)$ of the space $(X,d)$. The link
between the $M$-constant and the radius of a particular sphere containing $X$
is due to Nickolas and Wolf [11, Section 3] (following earlier work of
Alexander and Stolarsky [1]), and it is this which provides the geometric
meaning for many of the quantities considered. Working with $M(X)$ is
advantageous as it is defined even when the matrix $D$ is not invertible, and
this will allow us to consider arbitrary subsets of $H_{n}$. The relationship
between $M(X)$ and $\langle D^{-1}\mathbf{1},\mathbf{1}\rangle$ is developed
in Section 3, and this provides sufficient information to prove the conjecture
in [2]. In the final sections we use the properties of S-embeddings to prove
Theorem 1.1 and to give a geometric interpretation of the value of $\langle
D^{-1}\mathbf{1},\mathbf{1}\rangle$.

To simplify the statements of the results, we shall assume throughout that all
metric spaces considered have at least two elements. (Without this restriction
the statements are usually either false or meaningless.)

##  2\. Negative type and $S$-embeddings

######  Definition 2.1.

Suppose that $(X,d)$ is a metric space and that $p\geq 0$. Then $(X,d)$ is of
$p$-negative type if for each finite subset $\\{x_{1},\dots,x_{m}\\}\subseteq
X$ and each set of scalars $\xi_{1},\dots,\xi_{m}\in{\mathbb{R}}$ with
$\xi_{1}+\dots+\xi_{m}=0$,

(2) $\sum_{i,j=1}^{m}d(x_{i},x_{j})^{p}\xi_{i}\xi_{j}\leq 0.$

It certain settings, spaces of $1$-negative type are also called
quasihypermetric spaces (see for example [12]) or spaces of generalized
roundness $1$ (see [7]).

A space is of strict $p$-negative type if (2) holds, with equality only in the
trivial case where each $\xi_{i}$ is zero. (It is worth noting that a distinct
but related concept, that of a strictly quasihypermetric space, appears in
[10]. For finite spaces, such as the ones considered in this paper, a space is
of strict $1$-negative type if and only if it is strictly quasihypermetric.)
It follows from the results of Wolf [16] and Sánchez [13] that a finite metric
space of $1$-negative type is of strict $1$-negative type if and only if $D$
is non-singular and $\langle D^{-1}\mathbf{1},\mathbf{1}\rangle\neq 0$.

By [15, Theorem 4.10] any subset of ${\mathbb{R}}^{n}$ with the $\ell^{1}$
metric, and hence any subset of $H_{n}$, has $1$-negative type. Combining the
results of Muragan [8], and Doust, Robertson, Stoneham and Weston [2] (see
also Nickolas and Wolf [12]) gives the following equivalences.

######  Theorem 2.2.

Suppose that $X=\\{x_{1},\dots,x_{m}\\}\subseteq
H_{n}\subseteq{\mathbb{R}}^{n}$. Then the following are equivalent.

  1. (1)

$X$ is of strict $1$-negative type.

  2. (2)

$X$ is affinely independent (as a subset of ${\mathbb{R}}^{n}$).

  3. (3)

$D$ is non-singular.

###### Proof.

The equivalence of (1) and (2) was shown in [8, Theorem 4.3]. The equivalence
of (2) and (3) was proven in [2, Corollary 2.5]. ∎

Clearly then, $H_{n}$ is of $1$-negative type, but not of strict $1$-negative
type.

A celebrated theorem of Schoenberg [14] says that a metric space $(X,d)$ can
be isometrically embedded in a Euclidean space if and only if it is of
$2$-negative type. This gives the following.

######  Proposition 2.3.

Let $(X,d)$ be a finite metric space. Then the following are equivalent.

  1. (1)

$(X,d)$ is of $1$-negative type (or quasihypermetric).

  2. (2)

$(X,d^{1/2})$ embeds isometrically in a Euclidean space.

An embedding $\iota:X\to{\mathbb{R}}^{n}$ which maps $(X,d^{1/2})$
isometrically into $({\mathbb{R}}^{n},\|\cdot\|_{2})$ is called an
S-embedding. It is easy to check that the natural inclusion of $H_{n}$ in
${\mathbb{R}}^{n}$ is such an embedding, and hence so is the restriction to
any subset of $H_{n}$.

##  3\. The $M$-constant and maximal measures

The quantity $\langle D^{-1}\mathbf{1},\mathbf{1}\rangle$ is closely related
to the $M$-constant of the metric space, which we shall now introduce. Working
with the $M$-constant is in fact usually preferable since it is defined even
when the distance matrix $D$ is not invertible. For further background on the
$M$-constant we refer the reader to [1] or [9].

Let $(X,d)$ be a compact metric space. For a signed Borel measure $\mu$ on
$X$, let

$I(\mu)=\int_{X}\int_{X}d(x,y)\,d\mu(x)d\mu(y)$

and define $d_{\mu}:X\to{\mathbb{R}}$ by

$d_{\mu}(x)=\int_{X}d(x,y)\,d\mu(y).$

Let $F_{1}$ denote the set of measure on $X$ of total mass one. The
$M$-constant of $(X,d)$ is defined to be

$M(X)=\sup_{\mu\in F_{1}}I(\mu).$

If $I(\mu)=M(X)$, then we say that $\mu$ is a maximal measure. It is clear
that if $X$ is a metric subspace of $Y$ then $M(X)\leq M(Y)$.

Suppose now that $X=\\{x_{1},\dots,x_{m}\\}$ is a finite metric space. In this
case we shall write $\mu=(\alpha_{1},\dots,\alpha_{m})$ to denote that
$\mu(\\{x_{i}\\})=\alpha_{i}$, $i=1,\dots,m$. Then

$I(\mu)=\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}d(x_{i},x_{j})=\langle
D\mu,\mu\rangle,$

and

$d_{\mu}(x)=\sum_{i=1}^{m}\alpha_{i}d(x_{i},x)$

although in most cases we shall retain the integral notation. We shall
identify the measures of total mass one with the hyperplane of vectors whose
elements sum to $1$. That is, $F_{1}=\\{v\in{\mathbb{R}}^{m}\,:\,\langle
v,\mathbf{1}\rangle=1\\}$, and so $M(X)=\sup_{\mu\in F_{1}}\langle
D\mu,\mu\rangle$. By considering $\mu=\frac{1}{m}\mathbf{1}$, we have
$M(X)\geq\frac{1}{m^{2}}\langle
D\mathbf{1},\mathbf{1}\rangle\geq\frac{m-1}{m}d_{0}$, where $d_{0}$ is the
smallest nonzero distance in $X$. In particular $M(X)$ is always strictly
positive.

It is less clear that for a general compact metric space $M(X)$ should always
be finite, and indeed this need not be the case (see [9, Theorem 3.1]). Even
if $M(X)$ is finite it may be that there are no maximal measures. Fortunately
for subsets of the Hamming cube, these complications do not arise. Nickolas
and Wolf [12, Theorem 4.7] showed that if $X$ is any $m$-point subset of
${\mathbb{R}}^{n}$ with the $\ell^{1}$ metric then
$M(X)\leq\frac{m}{4}\mathop{\mathrm{diam}}(X)$ .

We recall some important properties of these quantities.

######  Theorem 3.1.

Suppose that $(X,d)$ is a finite metric space of $1$-negative type and that
$M(X)<\infty$.

  1. (1)

A maximal measure exists.

  2. (2)

If $\mu$ is a maximal measure, then $d_{\mu}(x)=M(X)$ for all $x\in X$.

  3. (3)

If $\mu\in F_{1}$ and there is a constant $C$ such that $d_{\mu}(x)=C$ for all
$x\in X$, then $\mu$ is maximal and so $M(X)=C$.

###### Proof.

(1) is [10, Theorem 4.11]; (2) and (3) are from [10, Theorem 3.1]. ∎

Theorem 3.1 is closely related to the following result.

######  Theorem 3.2.

Suppose that $(X,d)$ is a finite metric space of $1$-negative type with
distance matrix $D$. Then there exists $b\in{\mathbb{R}}^{m}$ such that
$Db=\mathbf{1}$ and $\langle b,\mathbf{1}\rangle\geq 0$. Further

  1. (1)

The value of $\langle b,\mathbf{1}\rangle$ is independent of $b$. That is, if
$Db=Db^{\prime}=\mathbf{1}$ then $\langle b,\mathbf{1}\rangle=\langle
b^{\prime},\mathbf{1}\rangle$.

  2. (2)

$M(X)<\infty$ if and only if $\langle b,\mathbf{1}\rangle>0$. In this case
$\mu=\frac{1}{\langle b,\mathbf{1}\rangle}b$ is a maximal measure and

$M(X)=\frac{1}{\langle b,\mathbf{1}\rangle}.$

###### Proof.

The existence of $b$ is shown in [17, Theorem 4.2]. The independence of the
value of $\langle b,\mathbf{1}\rangle$ was noted in [17, Remark 4.4].
Statement (2) is [17, Theorem 4.8]. ∎

######  Theorem 3.3.

Suppose that $(X,d)$ is a finite metric space of strict $1$-negative type with
distance matrix $D$. Then $M(X)<\infty$ and

$M(X)=\frac{1}{\langle D^{-1}\mathbf{1},\mathbf{1}\rangle}.$

###### Proof.

By Theorem 2.2, $D$ must be invertible. Let $b=D^{-1}\mathbf{1}$. By [17,
Theorem 4.3], $\langle b,\mathbf{1}\rangle>0$ so by Theorem 3.2, $M(X)<\infty$
and $M(X)=\bigl{(}\langle D^{-1}\mathbf{1},\mathbf{1}\rangle\bigr{)}^{-1}$. ∎

######  Theorem 3.4.

$M(H_{n})=\frac{n}{2}$.

###### Proof.

Due to the symmetry of the Hamming cube, the sum of the distances from any
given point is independent of the point. Simple analysis shows that this sum
is

$\beta=\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}$

and so $D\mathbf{1}=\beta\mathbf{1}$. Let $b=\frac{1}{\beta}\mathbf{1}$, so
$Db=\mathbf{1}$ and

$\langle
b,\mathbf{1}\rangle=\frac{1}{n2^{n-1}}\langle\mathbf{1},\mathbf{1}\rangle=\frac{2^{n}}{n2^{n-1}}=\frac{2}{n}.$

By Theorem 3.2 then

$M(H_{n})=\frac{n}{2}.$

∎

Combining the above results gives a positive answer to the conjecture in [2].

######  Theorem 3.5.

Let $X$ be a subset of $H_{n}$. Then

  1. (1)

$M(X)\leq\frac{n}{2}$.

  2. (2)

If $X$ is affinely independent, then $\langle
D^{-1}\mathbf{1},\mathbf{1}\rangle=\frac{1}{M(X)}$ and hence $\langle
D^{-1}\mathbf{1},\mathbf{1}\rangle\geq\frac{2}{n}$.

###### Proof.

(1) As noted earlier if $X\subseteq H_{n}$ then $M(X)\leq M(H_{n})$, so the
result follows immediately from Theorem 3.4.

(2) This follows immediately from Theorem 2.2, Theorem 3.3 and (1). ∎

The remainder of the paper is devoted to investigating the geometric
interpretation of $M(X)$ in the context of subsets of the Hamming cube.

##  4\. S-embeddings and spheres

There is a close connection between S-embeddings onto spheres and maximal
measures. We begin with two lemmas.

######  Lemma 4.1.

Suppose that $u_{1},\dots,u_{m}\in{\mathbb{R}}^{n}$ and that
$\alpha_{1},\dots,\alpha_{m}\in{\mathbb{R}}$ satisfy
$\sum_{i=1}^{m}\alpha_{i}=1$. Then, for all $u\in{\mathbb{R}}^{n}$,

$\sum_{i=1}^{m}\alpha_{i}\|u_{i}-u\|_{2}^{2}=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}u_{i}-u\bigr{\|}_{2}^{2}+\frac{1}{2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\|u_{i}-u_{j}\|_{2}^{2}.$

###### Proof.

With the notation of the lemma

$\displaystyle\sum_{i=1}^{m}\alpha_{i}\|u_{i}-u\|_{2}^{2}$
$\displaystyle=\sum_{i=1}^{m}\alpha_{i}\|u_{i}\|_{2}^{2}+\sum_{i=1}^{m}\alpha_{i}\|u\|_{2}^{2}-2\sum_{i=1}^{m}\alpha_{i}\langle
u_{i},u\rangle$
$\displaystyle=\|u\|_{2}^{2}-2\langle\sum_{i=1}^{m}\alpha_{i}u_{i},u\rangle+\bigl{\|}\sum_{i=1}^{m}\alpha_{i}u_{i}\bigr{\|}_{2}^{2}-\bigl{\|}\sum_{i=1}^{m}\alpha_{i}u_{i}\bigr{\|}_{2}^{2}+\sum_{i=1}^{m}\alpha_{i}\|u_{i}\|_{2}^{2}$
$\displaystyle=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}u_{i}-u\bigr{\|}_{2}^{2}-\bigl{\|}\sum_{i=1}^{m}\alpha_{i}u_{i}\bigr{\|}_{2}^{2}+\sum_{i=1}^{m}\alpha_{i}\|u_{i}\|_{2}^{2}$
$\displaystyle=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}u_{i}-u\bigr{\|}_{2}^{2}-\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\langle
u_{i},u_{j}\rangle+\sum_{i=1}^{m}\alpha_{i}\|u_{i}\|_{2}^{2}$
$\displaystyle=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}u_{i}-u\bigr{\|}_{2}^{2}+\sum_{i=1}^{m}\alpha_{i}\|u_{i}\|_{2}^{2}-\frac{1}{2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\left(\|u_{i}\|_{2}^{2}+\|u_{j}\|_{2}^{2}-\|u_{i}-u_{j}\|_{2}^{2}\right)$
$\displaystyle=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}u_{i}-u\bigr{\|}_{2}^{2}+\sum_{i=1}^{m}\alpha_{i}\|u_{i}\|_{2}^{2}$
$\displaystyle\qquad-\frac{1}{2}\sum_{j=1}^{m}\alpha_{j}\sum_{i=1}^{m}\alpha_{i}\|u_{i}\|_{2}^{2}-\frac{1}{2}\sum_{i=1}^{m}\alpha_{i}\sum_{j=1}^{m}\alpha_{j}\|u_{j}\|_{2}^{2}+\frac{1}{2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\|u_{i}-u_{j}\|_{2}^{2}$
$\displaystyle=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}u_{i}-u\bigr{\|}_{2}^{2}+\frac{1}{2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\|u_{i}-u_{j}\|_{2}^{2}.$

∎

######  Lemma 4.2.

Let $(X,d)$, $X=\\{x_{1},\dots,x_{m}\\}$ be a finite metric space of
$1$-negative type, and let
$\iota:(X,d^{1/2})\to({\mathbb{R}}^{n},\|\cdot\|_{2})$ be an S-embedding of
$X$. Suppose that $\mu=(\alpha_{1},\dots,\alpha_{m})\in F_{1}$. Then, for all
$x\in X$,

$d_{\mu}(x)=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}\iota(x_{i})-\iota(x)\bigr{\|}_{2}^{2}+\frac{I(\mu)}{2}.$

###### Proof.

Using Lemma 4.1

$\displaystyle d_{\mu}(x)$
$\displaystyle=\sum_{i=1}^{m}\alpha_{i}\|\iota(x_{i})-\iota(x)\|_{2}^{2}$
$\displaystyle=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}\iota(x_{i})-\iota(x)\bigr{\|}_{2}^{2}+\frac{1}{2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\|\iota(x_{i})-\iota(x_{j})\|_{2}^{2}$
$\displaystyle=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}\iota(x_{i})-\iota(x)\bigr{\|}_{2}^{2}+\frac{1}{2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}d(x_{i},x_{j})$
$\displaystyle=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}\iota(x_{i})-\iota(x)\bigr{\|}_{2}^{2}+\frac{I(\mu)}{2}.$

∎

The content of the following result can be found in Theorem 3.2 of [11]. We
include a short proof for completeness.

######  Theorem 4.3.

Let $(X,d)$, $X=\\{x_{1},\dots,x_{m}\\}$ be a finite metric space of
$1$-negative type, and let
$\iota:(X,d^{1/2})\to({\mathbb{R}}^{n},\|\cdot\|_{2})$ be an S-embedding of
$X$. Then

  1. (1)

If $\mu=(\alpha_{1},\dots,\alpha_{m})$ is a maximal measure on $X$, then
$\iota(X)$ lies on a sphere in ${\mathbb{R}}^{n}$ with centre
$\sum_{i=1}^{m}\alpha_{i}\iota(x_{i})$ and radius

$r=\sqrt{\frac{M(X)}{2}}.$

  2. (2)

Suppose that $\iota(X)$ lies on a sphere of radius $r$ with centre $c$ which
lies inside the affine hull of $\\{\iota(x_{1}),\dots,\iota(x_{m})\\}$, say
$c=\sum_{i=1}^{m}\beta_{i}\iota(x_{i})$ with $\sum_{i=1}^{m}\beta_{i}=1$. Then
$\mu=(\beta_{1},\dots,\beta_{m})$ is a maximal measure on $X$ and

$r=\sqrt{\frac{M(X)}{2}}.$

###### Proof.

(1) Let $\mu=(\alpha_{1},\dots,\alpha_{m})\in F_{1}$ be a maximal measure on
$X$. Fix then $x\in X$. By Theorem 3.1 and Lemma 4.2

$M(X)=d_{\mu}(x)=\bigl{\|}\sum_{i=1}^{m}\alpha_{i}\iota(x_{i})-\iota(x)\bigr{\|}_{2}^{2}+\frac{I(\mu)}{2}.$

Since $\mu$ is maximal $I(\mu)=M(X)$ and hence

$\bigl{\|}\sum_{i=1}^{m}\alpha_{i}\iota(x_{i})-\iota(x)\bigr{\|}_{2}^{2}=\frac{M(X)}{2}$

which proves (1).

(2) Let $c$ be as in the statement of the theorem and suppose that $x\in X$,
so that $\|c-\iota(x)\|_{2}^{2}=r^{2}$. Let $\mu=(\beta_{1},\dots,\beta_{m})$.
By Lemma 4.2

$d_{\mu}(x)=\|c-\iota(x)\|_{2}^{2}+\frac{I(\mu)}{2}=r^{2}+\frac{I(\mu)}{2}.$

Since $d_{\mu}(x)$ is independent of $x$, from Theorem 3.1 we can conclude
that $\mu$ is maximal on $X$ and that

$M(X)=r^{2}+\frac{I(\mu)}{2}$

and hence that

$r^{2}=\frac{M(X)}{2}.$

∎

Suppose that $B=\\{v_{1},\dots,v_{k}\\}$ is a basis for a subspace
$Z\subseteq{\mathbb{R}}^{n}$. Then there is a unique point $c\in Z$ which is
equidistant from all the elements of $B$ and the origin. Indeed a small
calculation shows that if $A$ is the $n\times k$ matrix whose $i$th column is
$v_{i}$, then

(3)
$c=\sum_{i=1}^{k}\gamma_{i}v_{i}\qquad\text{where}\qquad\begin{pmatrix}\gamma_{1}\\\
\vdots\\\
\gamma_{k}\end{pmatrix}=\frac{1}{2}(A^{T}A)^{-1}\begin{pmatrix}\|v_{1}\|_{2}^{2}\\\
\vdots\\\ \|v_{k}\|_{2}^{2}\end{pmatrix}.$

This implies the following.

######  Lemma 4.4.

Suppose that $X=\\{x_{1},\dots,x_{m}\\}$ is a finite subset of
${\mathbb{R}}^{n}$ and let $Z_{X}$ be the smallest affine subspace of
${\mathbb{R}}^{n}$ containing $X$. Then there is at most one sphere in
${\mathbb{R}}^{n}$ whose centre lies in $Z_{X}$ and which contains the points
of $X$.

##  5\. The $M$-constant for subsets of the Hamming cube

Suppose that $X=\\{x_{1},\dots,x_{m}\\}\subseteq H_{n}$. Let $Z_{X}$ denote
the smallest affine subspace of ${\mathbb{R}}^{n}$ containing the points
$\\{x_{1},\dots,x_{m}\\}$. We shall use $d_{2}(x,Z_{X})$ to denote the
Euclidean distance from a point $x\in{\mathbb{R}}^{n}$ to an affine subspace
$Z_{X}$. Let
$h=\bigl{(}\frac{1}{2},\dots,\frac{1}{2}\bigr{)}\in{\mathbb{R}}^{n}$.

######  Theorem 5.1.

Suppose that $X=\\{x_{1},\dots,x_{m}\\}\subseteq H_{n}$. Then

(4) $M(X)=\frac{n}{2}-2d_{2}(h,Z_{X})^{2}.$

###### Proof.

Let $\iota:(H_{n},d_{1}^{1/2})\to({\mathbb{R}}^{n},\|\cdot\|_{2})$ be the
natural inclusion map of $H_{n}$ in ${\mathbb{R}}^{n}$. As noted in Section 2,
this map is necessarily an S-embedding.

Since $\|x-h\|_{2}^{2}=\frac{n}{4}$ for all $x\in H_{n}$, we have that
$X=\iota(X)$ lies on the sphere $S\subseteq{\mathbb{R}}^{n}$ of radius
$r=\sqrt{n}/2$ centred at $h$. Let $P$ be the orthogonal projection from
${\mathbb{R}}^{n}$ onto $Z_{X}$ and let $c_{X}=Ph$. If $u\in\iota(X)\subseteq
Z_{X}$ then, by Pythagoras,

$\|c_{X}-u\|_{2}^{2}=\|h-u\|_{2}^{2}-\|h-c_{X}\|_{2}^{2}=\frac{n}{4}-d_{2}(h,Z_{X})^{2}.$

That is, all points in $\iota(X)$ lie on a sphere $S_{X}$ with centre
$c_{X}\in Z_{X}$ and radius $r$ with $r^{2}=\frac{n}{4}-d_{2}(h,Z_{X})^{2}$.
(Note that by Lemma 4.4, there is only one such sphere.)

But by Theorem 4.3(2), the radius of such this sphere must also satisfy

$r^{2}=\frac{n}{4}-d_{2}(h,Z_{X})^{2}=\frac{M(X)}{2}$

which gives the result. ∎

Equation (4) immediately gives the following characterization of when the
maximum value of $M(X)$ is achieved.

######  Corollary 5.2.

$M(X)$ achieves its maximum value of $\frac{n}{2}$ if and only if $h$ lies in
$Z_{X}$.

Combining Theorem 5.1 and Theorem 3.5 gives Theorem 1.1 stated in the
introduction.

Following the proof of [11, Theorem 3.2], an alternative but less
geometrically illuminating verification of Theorem 5.1 can be given by noting
that for $\mu=(\alpha_{1},\dots,\alpha_{m})\in F_{1}$, and
$\\{x_{i}\\}_{i=1}^{m}\subseteq H_{n}$,

$\displaystyle I(\mu)$
$\displaystyle=\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\|x_{i}-x_{j}\|_{1}=\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\|x_{i}-x_{j}\|_{2}^{2}$
$\displaystyle=\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\|(x_{i}-h)-(x_{j}-h)\|_{2}^{2}$
$\displaystyle=\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\|(x_{i}-h)\|_{2}^{2}+\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\|(x_{j}-h)\|_{2}^{2}-2\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}\langle
x_{i}-h,x_{j}-h\rangle$
$\displaystyle=\frac{n}{2}-2\bigl{\|}\sum_{i=1}^{m}\alpha_{i}(x_{i}-h)\bigr{\|}_{2}^{2}$
$\displaystyle=\frac{n}{2}-2\bigl{\|}\sum_{i=1}^{m}\alpha_{i}x_{i}-h\bigr{\|}_{2}^{2}.$

Maximizing $I(\mu)$ then gives the result.

One consequence of Theorem 5.1 is that the value of $M(X)$ for $X\subseteq
H_{n}$ is determined by the $M$-constant of any maximal affinely independent
subset $Y$ of $X$. (Since, by Theorem 2.2, a maximal affinely independent
subset of $X$ is also a maximal subset of strict $1$-negative type, this can
also be deduced from Theorem 2.7 of [12].) Such a set $Y$ may be much smaller
than $X$, and furthermore the value of $M(Y)$ may be calculated
algorithmically rather than by an optimization process. Finding a suitable
affinely independent subset can be easily done using Gaussian elimination. The
distance matrix for $Y$ is then invertible, and Theorem 3.5 implies that
$M(X)=M(Y)=(\langle D_{Y}^{-1}\mathbf{1},\mathbf{1}\rangle)^{-1}$.

Alternatively, if $Y=\\{y_{0},\dots,y_{m}\\}$ and $v_{i}=y_{i}-y_{0}$,
$i=1,\dots,m$, then one may use (3) to compute the centre $c$ of the sphere in
$\text{span}(v_{1},\dots,v_{m})$ containing the points
$\mathbf{0},v_{1},\dots,v_{m}$. Then $M(X)=M(Y)=2\|c\|_{2}^{2}$. In the case
that $X$ is affinely independent, one may therefore use Theorem 1.1, the proof
of Theorem 5.1, and Pythagoras to see that $\langle
D^{-1}\mathbf{1},\mathbf{1}\rangle$ is equal to $(2r^{2})^{-1}$ where $r$ is
the radius of the smallest sphere containing all the points in $X$.

We finish with two small examples which illustrate Remark 1.3 concerning the
lack of an obvious relationship between the distance matrix $D$ and the
subspace $Z_{X}$ which appear on the two sides of Equation (1).

######  Example 5.3.

Let $X_{1}=\\{(0,0,0),(1,1,1)\\}$ and let $X_{2}=X_{1}\cup\\{(1,0,0)\\}$. In
this case $Z_{X_{1}}$ is different to $Z_{X_{2}}$. The point $h$ lies in both
subspaces and hence $M(X_{1})=M(X_{2})=\frac{3}{2}$. Of course the distance
matrices are quite different with

$D_{X_{1}}^{-1}=\begin{pmatrix}0&\tfrac{1}{3}\\\
\tfrac{1}{3}&0\end{pmatrix},\qquad
D_{X_{2}}^{-1}=\begin{pmatrix}-\tfrac{1}{3}&\tfrac{1}{6}&\tfrac{1}{2}\\\
\tfrac{1}{6}&-\tfrac{1}{12}&\tfrac{1}{4}\\\
\tfrac{1}{2}&\tfrac{1}{4}&-\tfrac{3}{4}\end{pmatrix},$

but the sum of the entries of each matrix inverse is $\frac{2}{3}$.

######  Example 5.4.

Let $X_{1}=\\{(0,0,0),(1,0,0),(0,1,0)\\}$ and let
$X_{2}=X_{1}\cup\\{(1,1,0)\\}$. Then $Z_{X_{1}}=Z_{X_{2}}$ and so by Theorem
5.1 we must have $M(X_{1})=M(X_{2})$. Here $X_{1}$ is affinely independent and
$\langle D_{X_{1}}^{-1}\mathbf{1},\mathbf{1}\rangle=M(X_{1})^{-1}=1$. However
$X_{2}$ is not affinely independent and $D_{X_{2}}$ is not invertible. (Using
Lagrange multipliers, one can confirm, directly from the definition, that
$M(X_{2})=1$. Alternatively, one may use Theorem 4.3 since $X_{2}$ certainly
lies in a sphere with centre in $Z_{X_{2}}$ and radius $1/\sqrt{2}$.)

## References

  * [1] R. Alexander and K. B. Stolarsky, Extremal problems of distance geometry related to energy integrals, Trans. Amer. Math. Soc. 193 (1974), 1–31.
  * [2] I. Doust, G. Robertson, A. Stoneham and A. Weston, Distance matrices of subsets of the Hamming cube, Indag. Math. 32 (2021), 646–657.
  * [3] R. L. Graham and L. Lovász, Distance matrix polynomials of trees, Adv. Math. 29 (1978), 60–88.
  * [4] R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell System Tech. J. 50 (1971), 2495–2519.
  * [5] R. L. Graham and P. M. Winkler, On isometric embeddings of graphs, Trans. Amer. Math. Soc. 288 (1985), 527–536.
  * [6] R. L. Graham and P. M. Winkler, Corrigendum to “On isometric embeddings of graphs”, Trans. Amer. Math. Soc. 294 (1986), 379.
  * [7] C. Lennard, A. Tonge A. Weston, Generalized roundness and negative type, Michigan Math. J. 44 (1997), 37–45
  * [8] M. K. Murugan, Supremal $p$-negative type of vertex transitive graphs, J. Math. Anal. Appl. 391 (2012), 376–381.
  * [9] P. Nickolas and R. Wolf, Distance geometry in quasihypermetric spaces. I, Bull. Aust. Math. Soc. 80 (2009), 1–25.
  * [10] P. Nickolas and R. Wolf, Distance geometry in quasihypermetric spaces. II, Math. Nachr. 284 (2011), 332–341.
  * [11] P. Nickolas and R. Wolf, Distance geometry in quasihypermetric spaces. III, Math. Nachr. 284 (2011), 747–760.
  * [12] P. Nickolas and R. Wolf, Finite quasihypermetric spaces, Acta Math. Hungar. 124 (2009), 243–262.
  * [13] S. Sánchez, On the supremal $p$-negative type of finite metric spaces, J. Math. Anal. Appl. 389 (2012), 98–107.
  * [14] I. J. Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522–536.
  * [15] J. H. Wells and L. R. Williams, Embeddings and extensions in analysis, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84. Springer-Verlag, New York–Heidelberg, 1975.
  * [16] R. Wolf, On the gap of finite metric spaces of p-negative type, Linear Algebra Appl. 436 (2012), 1246–1257.
  * [17] R. Wolf, Estimating the gap of finite metric spaces of strict p-negative type, Linear Algebra Appl. 556 (2018), 171–199.