text:
\section{Interacting Particles and Phase Transitions}

\subsection{Introduction -- Origins of Interactions}

As I said already in the introductory part on the analysis tools and
asymptotic methods, until now, we have dealt almost exclusively with
systems that have additive Hamiltonians, $\calE(\bx)=\sum_i\calE(x_i)$,
which means that the particles are i.i.d.\ and there is no interaction:
each particle behaves as if it was alone in the world. In Nature, of course,
this is seldom really the case. Sometimes this is still a reasonably good
approximation, but in many others the interactions
are appreciably strong and cannot be neglected.
Among the different particles there could be
many sorts of mutual forces, e.g., mechanical, electrical, magnetic, etc.
There could also be interactions that stem from quantum--mechanical effects:
Pauli's exclusion principle asserts that for a certain type of particles,
called Fermions (e.g., electrons), no quantum state can be populated by more
than one particle. This gives rise to a certain mutal influence between
particles. Another type of interaction stems from the fact that the particles
are indistinguishable, so permutations between them are not considered as
distinct states. We have already seen this as an example at the beginning of
the previous set of lecture notes: In a quantum gas, as we eliminated the
combinatorial factor (that counted indistinguishable
states as distinguishable ones), we created statistical
dependence, which physically means interactions.\footnote{Indeed, in the case
of the boson gas, there is a well--known effect referred to as {\it
Bose--Einstein condensation}, which is actually a phase transition, but phase
transitions can occur only in systems of interacting particles, as will be
discussed in this set of lectures.}

\subsection{A Few Models That Will be Discussed in This Subsection Only}

The simplest forms of deviation from the purely
additive Hamiltonian structure
are those that consists, in addition to the individual energy
terms $\{\calE(x_i)\}$, also terms that depend on pairs, and/or triples,
and/or even larger cliques of particles.
In the case of purely pairwise interactions, this
means a structure like the following:
\begin{equation}
\calE(\bx)=\sum_{i=1}^n\calE(x_i)+\sum_{(i,j)}\varepsilon(x_i,x_j)
\end{equation}
where the summation over pairs can be defined over all pairs $i\ne j$,
or over some of the pairs, according to a given rule, e.g., depending
on the distance between particle $i$ and particle $j$, and according to
the geometry of the system, or according to a certain graph whose edges
connect the relevant pairs of variables (that in turn, are designated as nodes).
For example, in a one--dimensional array
(a lattice) of
particles, a customary model accounts for interactions between neighboring
pairs only, neglecting more remote ones, thus the second term above would be
$\sum_{i}\varepsilon(x_i,x_{i+1})$. A well known special case of this is
that of a solid, i.e., a crystal lattice, where
in the one--dimensional version of the model, atoms are thought of as
a chain of masses connected by springs (see left part of Fig.\ \ref{springs2d}),
i.e., an array of coupled harmonic oscillators. In
this case,
$\varepsilon(x_i,x_{i+1})=\frac{1}{2}K(u_{i+1}-u_i)^2$, where $K$ is a
constant and $u_i$ is the displacement of the $i$-th atom from its
equilibrium location, i.e., the potential energies of the springs.
This model has an easy analytical solution (by applying a Fourier transform
on the sequence $\{u_i\}$), where by ``solution'', we mean a closed--form,
computable formula for the log--partition function, at least in the
thermodynamic limit.
\begin{figure}[ht]
\hspace*{4cm}\input{springs2d.pstex_t}
\caption{\small Elastic interaction forces between adjacent atoms in a
one--dimensional lattice (left part of the figure) and in a two--dimensional
lattice (right part).}
\label{springs2d}
\end{figure}
In higher dimensional arrays (or lattices), similar interactions apply,
there are just more neighbors to each site,
from the various directions (see right part of Fig.\ \ref{springs2d}). In a system where the
particles are mobile and hence their locations vary
and have no geometrical structure,
like in a gas, the interaction terms are also
potential energies pertaining to the mutual forces (see Fig.\ \ref{spheres}), and these normally
depend solely on the distances $\|\vec{r}_i-\vec{r}_j\|$.
\begin{figure}[ht]
\hspace*{5cm}\input{spheres.pstex_t}
\caption{\small Mobile particles and mutual forces between them.}
\label{spheres}
\end{figure}
For example, in a non--ideal gas,
\begin{equation}
\calE(\bx)=\sum_{i=1}^n\frac{\|\vec{p}_i\|^2}{2m}+
\sum_{i\ne j}V(\|\vec{r}_i-\vec{r}_j\|).
\end{equation}
A very simple special case is that of
hard spheres (Billiard balls), without any
forces, where
\begin{equation}
V(\|\vec{r}_i-\vec{r}_j\|)=\left\{\begin{array}{ll}
\infty & \|\vec{r}_i-\vec{r}_j\| < 2R\\
0 & \|\vec{r}_i-\vec{r}_j\| \ge 2R
\end{array}\right.
\end{equation}
which expresses the simple fact that balls cannot physcially overlap.
This model can (and indeed is) being used to obtain bounds on sphere--packing
problems, which are very relevant to channel coding theory.
This model is also solvable, but this is beyond the scope of this course.

\subsection{Models of Magnetic Materials -- General}

Yet another example of a model, or more precisely, a very large class of
models with interactions, are those of magnetic materials. These models
will closely accompany our dicussions from this point onward, because some
of them lend themselves to mathematical formalisms that are analogous
to those of coding problems, as we shall see. Few of these models are
solvable, but most of them are not. For the purpose of our discussion, a
magnetic material is one for which the important property of each particle
is its {\it magnetic moment}. The magnetic moment is a vector proportional to
the angular momentum of a revolving charged particle (like a rotating electron,
or a current loop), or the {\it spin}, and it designates the intensity of its
response to the net magnetic field that this particle `feels'. This magnetic
field may be
the superposition of an externally applied magnetic field and the magnetic
fields generated by the neighboring spins.

Quantum mechanical considerations
dictate that each spin, which will be denoted by $s_i$,
is quantized -- it may take only one out of finitely many
values. In the simplest case to be adopted in our study -- only two values.
These will be designated by $s_i=+1$ (``spin up'') and $s_i=-1$ (``spin
down''), corresponding to the same intensity, but in two opposite directions,
one parallel to the magnetic field, and the other -- antiparallel (see Fig.\
\ref{spinglass}).
\begin{figure}[ht]
\hspace*{5cm}\input{spinglass1.pstex_t}
\caption{\small Ilustration of a spin array on a square lattice.}
\label{spinglass}
\end{figure}
The Hamiltonian associated with an array of spins $\bs=(s_1,\ldots,s_n)$
is customarily modeled (up to certain constants that, among other things, accommodate for the
physical units) with a structure like this:
\begin{equation}
\calE(\bs)=-B\cdot\sum_{i=1}^ns_i-\sum_{(i,j)} J_{ij}s_is_j,
\end{equation}
where $B$ is the externally applied magnetic field
and $\{J_{ij}\}$
are the coupling constants that designate the levels of interaction between
spin pairs, and they depend on properties of the magnetic material and on the
geometry of the system. The first term accounts for the
contributions of potential energies
of all spins due to the magnetic field, which in general, are
given by the inner
product $\vec{B}\cdot\vec{s}_i$, but since each $\vec{s}_i$ is either
parallel or antiparallel to $\vec{B}$, as said, these boil down to simple
products, where only the sign of each $s_i$ counts. Since $P(\bs)$ is
proportional to $e^{-\beta\calE(\bs)}$, the spins `prefer' to be parallel,
rather than antiparallel to the magnetic field.
The second term in the above Hamiltonian accounts for the interaction energy.
If $J_{ij}$ are all positive,
they also prefer to be parallel to one another (the probability for this is
larger), which is the case where
the material is called {\it ferromagnetic} (like iron and nickel). If they are all
negative, the material is {\it antiferromagnetic}. In the mixed case, it is
called a {\it spin glass}. In the latter, the behavior is rather complicated,
as we shall see later on.

Of course, the above model for the Hamiltonian can (and, in fact, is being)
generalized to include interactions formed also, by triples, quadruples, or
any fixed size $p$ (that does not grow with $n$) of spin--cliques.
At this point, it is instructive to see the relation between spin--array
models
(especially, those that involve large cliques of spins) to channel codes, in
particular, linear codes.
Consider a linear code defined by a set of $m$ partiy--check equations (in
$GF(2)$),
each involving the modulo--2 sum of some subset of the components of the
codeword $\bx$.
I.e., the $\ell$--th equation is: $x_{i_1^\ell}\oplus
x_{i_2^\ell}\oplus\cdot\cdot\cdot\oplus
x_{i_{k_\ell}}^\ell=0$, $\ell=1,\ldots,m$. Transforming from
$x_i\in\{0,1\}$ to $s_i\in\{-1,+1\}$ via $s_i=1-2x_i$, this is
equivalent to $s_{i_1^\ell}s_{i_2^\ell}\cdot\cdot\cdot
s_{i_{k_{\ell}}^\ell}=1$. The MAP decoder would estimate $\bs$ based on
the posterior
\begin{equation}
P(\bs|\by)=\frac{P(\bs)P(\by|\bs)}{Z(\by)};~~~Z(\by)=\sum_{\bs}P(\bs)P(\by|\bs)=P(\by),
\end{equation}
where $P(\bs)$ is normally assumed uniform over the codewords (we will
elaborate on this posterior later).
Assuming, e.g., a BSC or a Gaussian channel $P(\by|\bs)$,
the relevant distance between the codeword $\bs=(s_1,\ldots,s_n)$
and the channel output $\by=(y_1,\ldots,y_n)$ is proportional to
$\|\bs-\by\|^2=\mbox{const.}-2\sum_is_iy_i$.
Thus, $P(\bs|\by)$ can be thought of as a B--G distribution with Hamiltonian
\begin{equation}
\calE(\bs|\by)= -J\sum_{i=1}^ns_iy_i+\sum_{\ell=1}^m
\phi(s_{i_1^\ell}s_{i_2^\ell}\cdot\cdot\cdot s_{i_{k_{\ell}}^\ell})
\end{equation}
where $J$ is some constant (depending on the channel parameters),
the function $\phi(u)$ vanishes for $u=1$ and becomes infinite for $u\ne
1$, and the partition function given by the denominator of $P(\bs|\by)$.
The first term plays the analogous role to that of the contribution of the
magnetic field in a spin system model,
where each `spin' $s_i$ `feels' a different magnetic field proportional to $y_i$, and the
second term accounts for the interactions among cliques of spins. In the case
of LDPC
codes, where each parity check equation involves only a small number of bits
$\{s_i\}$, these
interaction terms amount to cliques of relatively small sizes.\footnote{Error
correction codes can be represented by bipartite graphs with two types of
nodes: variable nodes corresponding to the various $s_i$ and function nodes
corresponding to cliques. There is an edge between variable node $i$ and
function node $j$ if $s_i$ is a member in clique $j$. Of course each $s_i$ may
belong to more than one clique. When all cliques are of size 2, there is no
need for the function nodes, as edges between nodes $i$ and $j$ simply
correspond to
partity check equations involving $s_i$ and $s_j$.}
For a
general code, the second term is replaced by $\phi_{\calC}(\bs)$, which is
zero for $\bs\in\calC$ and infinite otherwise.

Another aspect of this model of a coded communication system pertains to
calculations of mutual information and capacity. The mutual information
between $\bS$ and $\bY$ is, of course, given by
\begin{equation}
I(\bS;\bY)=H(\bY)-H(\bY|\bS).
\end{equation}
The second term is easy to calculate for every additive channel -- it is
simply the entropy of the additive noise. The first term is harder to
calculate:
\begin{equation}
H(\bY)=-\bE\{\ln P(\bY)\}=
-\bE\{\ln Z(\bY)\}.
\end{equation}
Thus, we are facing a problem of calculating the free energy of a spin system
with random magnetic fields designated by the components of $\bY$. This is
the kind of calculations we mentioned earlier in the context of the replica
method. Indeed, the replica method is used extensively in this context.

As we will see in the sequel, it is also customary to introduce
an inverse temperature parameter $\beta$, by defining
\begin{equation}
P_\beta(\bs|\by)=\frac{P^\beta(\bs)P^\beta(\by|\bs)}{Z(\beta|\by)}=
\frac{e^{-\beta\calE(\bs|\by)}}{Z(\beta|\by)}
\end{equation}
where $\beta$ controls the sharpness of the posterior distribution and
\begin{equation}
Z(\beta|\by)=\sum_{\bs} e^{-\beta\calE(\bs|\by)}.
\end{equation}
The motivations of this will be discussed extensively later on.

We will get back
to this important class of models, as well as its many extensions, shortly.
But before that, we discuss a very important effect that exists in some
systems with strong interactions (both in magnetic
materials and in other models): the effect of {\it phase transitions}.

\subsection{Phase Transitions -- A Qualitative Discussion}

Loosely speaking, a phase transition means an abrupt change in the
collective behavior of a physical system, as we change gradually
one of the externally controlled parameters, like the temperature, pressure,
or magnetic field, and so on. The most common example of a phase transition in our everyday
life is the water that we boil in the kettle when we make coffee, or when it
turns into ice as we put it in the freezer.
What exactly are these phase transitions?
Before we refer to this question, it should be noted that there are also ``phase
transitions'' in the behavior of communication systems: As the SNR
passes a certain limit (for which capacity crosses the coding rate), there is
a sharp transition between reliable and unreliable communication, where the
error probability (almost) `jumps' from $0$ to $1$ or vice versa.
We also know about certain threshold effects in highly non--linear communication systems.
Are there any relationships between these phase transitions
and those of physics? We will see shortly that the answer is generally
affirmative.

In physics, phase transitions can occur only if the system has interactions. Consider,
the above example of an array of spins with $B=0$, and let us
suppose that all $J_{ij}> 0$ are equal, and thus will be denoted commonly by $J$. Then,
\begin{equation}
P(\bs)=\frac{\exp\left\{\beta J\sum_{(i,j)}s_is_j\right\}}{Z(\beta)}
\end{equation}
and, as mentioned earlier, this is a ferromagnetic model, where all spins
`like' to be in the same direction, especially when $\beta$ and/or $J$ is
large. In other words, the interactions, in this case, tend to introduce {\it
order} into the system. On the other hand, the second law talks about maximum
entropy, which tends to increase the {\it disorder}. So there are two
conflicting effects here. Which one of them prevails?

The answer turns out to depend on
temperature. Recall that in the canonical ensemble, equilibrium is attained at
the point of minimum free energy $f=\epsilon-Ts(\epsilon)$. Now, $T$ plays
the role of a weighting factor for the entropy. At low temperatures, the
weight of the second term of $f$ is small, and minimiizing $f$ is approximately
(and for $T=0$, this is exact)
equivalent to minimizing $\epsilon$, which is obtained by states with a high
level of order, as $\calE(\bs)=-J\sum_{(i,j)}s_is_j$, in this example.
As $T$ grows, however, the weight of the term $-Ts(\epsilon)$ increases, and
$\min f$, becomes more and more equivalent to $\max s(\epsilon)$, which is achieved by
states with a high level of disorder (see Fig.\ \ref{fgraph}).
\begin{figure}[ht]
\hspace*{5cm}\input{fgraph.pstex_t}
\caption{\small Qualitative graphs of $f(\epsilon)$ at various temperatures.
The minimizing $\epsilon$ increases with $T$.}
\label{fgraph}
\end{figure}
Thus, the order--disorder characteristics depend
primarily on temperature.
It turns out that for some magnetic systems of this kind, this transition between
order and disorder may be abrupt, in which case, we call it a {\it phase
transition}.
At a certain critical temperature, called
the {\it Curie temperature}, there
is a sudden transition between order and disorder. In the ordered phase,
a considerable fraction of the spins align in the same
direction, which means that the system is spontaneously magnetized (even
without an external magnetic field), whereas in
the disordered phase, about half of the spins are in either direction, and
then the
net magnetization vanishes.
This happens if the
interactions, or more precisely, their dimension in some sense, is strong
enough.

What is the mathematical significance of a phase transition? If we look at
the partition function, $Z(\beta)$, which is the key to all physical
quantities of interest, then
for every finite $n$, this is simply the sum of a bunch of exponentials in
$\beta$ and therefore it is continuous and differentiable as many times as we
want. So what kind of abrupt changes could there possibly be in the behavior
of this function?

It turns out that while this is true for all finite $n$, it is no longer necesarily true if we
look at the thermodynamical limit, i.e., if we look at the
behavior of $\phi(\beta)=\lim_{n\to\infty}\frac{\ln
Z(\beta)}{n}$. While $\phi(\beta)$ must be continuous for all $\beta >0$
(since it is convex), it need not necessarily have continuous derivatives.
Thus, a phase transition, if exists, is fundamentally an asymptotic property, it
may exist in the thermodynamical limit only. While a physical system is, after
all finite, it is nevertheless well approximated by the thermodynamical limit
when it is very large.
By the same token, if we look at the analogy with a coded communication
system: for any finite block--length $n$, the error probability is a `nice'
and smooth
function of the SNR, but in the limit of large $n$, it behaves like a step
function that jumps between $0$ and $1$ at the critical SNR.
We will see that the two things are
related.

Back to the physical aspects, the above discussion explains also why a system without interactions,
where all $\{x_i\}$ are i.i.d., cannot have phase transitions. In this case,
$Z_n(\beta)=[Z_1(\beta)]^n$, and so, $\phi(\beta)=\ln Z_1(\beta)$, which is
always a `nice' function without any irregularities. For a phase transition to
occur, the particles must behave in some collective manner, which is the case
only if interactions take place.

There is a distinction between two types of phase transitions:
\begin{itemize}
\item If $\phi(\beta)$ has a discontinuous first order derivative, then this
is called a {\it first order phase transition}.
\item If $\phi(\beta)$ has a continuous first order derivative,
but a discontinuous second order derivative then this
is called a {\it second order phase transition}, or a {\it continuous phase
transition}.
\end{itemize}

We can talk, of course, about phase transitions w.r.t.\ additional parameters other than
temperature. In the above magnetic example, if we introduce back the magnetic
field $B$ into the picture, then $Z$, and hence also $\phi$, become functions of $B$
too. If we then look at derivative of
\begin{equation}
\phi(\beta,B)=\lim_{n\to\infty}\frac{\ln Z(\beta,B)}{n}=
\lim_{n\to\infty}\frac{1}{n}\ln\left[\sum_{\bs}\exp\left\{\beta
B\sum_{i=1}^ns_i+\beta J\sum_{(i,j)}s_is_j\right\}\right]
\end{equation}
w.r.t.\ the product $(\beta B)$, which multiplies the magnetization,
$\sum_is_i$, at the exponent,
this would give exactly the average magnetization per spin
\begin{equation}
m(\beta,B)=\left<\frac{1}{n}\sum_{i=1}^n S_i\right>,
\end{equation}
and this quantity might not always be continuous.
Indeed, as I mentioned earlier, below the Curie
temperature there might be a spontaneous magnetization. If $B\downarrow
0$, then this magnetization is positive, and if $B\uparrow 0$, it is negative,
so there is a discontinuity at $B=0$.
We will see this more concretely later on.
We next discuss a few solvable models of spin arrays, with and without
phase transitions.

\subsection{The One--Dimensional Ising Model}

According to this model,
\begin{equation}
\calE(\bs)=-B\sum_{i=1}^ns_i -J\sum_{i=1}^n s_is_{i+1}
\end{equation}
with the periodic boundary condition $s_{n+1}=s_1$. Thus,
\begin{eqnarray}
Z(\beta,B)&=&\sum_{\bs}\exp\left\{\beta B\sum_{i=1}^ns_i+\beta J\sum_{i=1}^n
s_is_{i+1}\right\}~~~\mbox{Note: the kind of sums encountered in Markov
chains}\nonumber\\
&=&\sum_{\bs}\exp\left\{h\sum_{i=1}^ns_i+K\sum_{i=1}^n
s_is_{i+1}\right\}~~~~~h\dfn\beta B,~~K\dfn \beta J\nonumber\\
&=&\sum_{\bs}\exp\left\{\frac{h}{2}\sum_{i=1}^n(s_i+s_{i+1})+K\sum_{i=1}^n
s_is_{i+1}\right\}~~~~~\mbox{(just to symmetrize the expression)}\nonumber
\end{eqnarray}
Consider now the $2\times 2$ matrix $P$ whose entries are
$\exp\{\frac{h}{2}(s+s')+Kss'\}$, $s,s\in\{-1,+1\}$, i.e.,
\begin{equation}
P=\left(\begin{array}{cc}
e^{K+h} & e^{-K} \\
e^{-K} & e^{K-h}\end{array}\right).
\end{equation}
Also, $s_i=+1$ will be represented by the column vector $\sigma_i=(1,0)^T$ and
$s_i=-1$ will be represented by $\sigma_i=(0,1)^T$. Thus,
\begin{eqnarray}
Z(\beta,B)&=&\sum_{\sigma_1}\cdot\cdot\cdot\sum_{\sigma_n}
(\sigma_1^T
P\sigma_2)\cdot(\sigma_2^TP\sigma_2)\cdot\cdot\cdot(\sigma_n^TP\sigma_1)\nonumber\\
&=&\sum_{\sigma_1}\sigma_1^TP\left(\sum_{\sigma_2}\sigma_2\sigma_2^T\right)P
\left(\sum_{\sigma_3}\sigma_3\sigma_3^T\right)P\cdot\cdot\cdot P
\left(\sum_{\sigma_n}\sigma_n\sigma_n^T\right)P\sigma_1\nonumber\\
&=&\sum_{\sigma_1}\sigma_1^TP\cdot I\cdot P\cdot I
\cdot\cdot\cdot I\cdot P\sigma_1\nonumber\\
&=&\sum_{\sigma_1}\sigma_1^TP^n\sigma_1\nonumber\\
&=&\mbox{tr}\{P^n\}\nonumber\\
&=&\lambda_1^n+\lambda_2^n
\end{eqnarray}
where $\lambda_1$ and $\lambda_2$ are the eigenvalues of $P$, which are
\begin{equation}
\lambda_{1,2}=e^K\cosh(h)\pm\sqrt{e^{-2K}+e^{2K}\sinh^2(h)}.
\end{equation}
Letting $\lambda_1$ denote the larger (the dominant) eigenvalue, i.e.,
\begin{equation}
\lambda_{1}=e^K\cosh(h)+\sqrt{e^{-2K}+e^{2K}\sinh^2(h)},
\end{equation}
then clearly,
\begin{equation}
\phi(h,K)=\lim_{n\to\infty}\frac{\ln Z}{n}=\ln\lambda_1.
\end{equation}
The average magnetization is
\begin{eqnarray}
M(h,K)&=&\left< \sum_{i=1}^n S_i\right>\nonumber\\
&=&\frac{\sum_{\bs}(\sum_{i=1}^ns_i)\exp\{h\sum_{i=1}^ns_i+K\sum_{i=1}^ns_is_{i+1}\}}
{\sum_{\bs}\exp\{h\sum_{i=1}^ns_i+K\sum_{i=1}^ns_is_{i+1}\}}\nonumber\\
&=&\frac{\partial \ln Z(h,K)}{\partial h}
\end{eqnarray}
and so, the per--spin magnetization is:
\begin{equation}
m(h,K)\dfn\lim_{n\to\infty}\frac{M(h,K)}{n}=\frac{\partial \phi(h,K)}{\partial
h}= \frac{\sinh(h)}{\sqrt{e^{-4K}+\sinh^2(h)}}
\end{equation}
or, returning to the original parametrization:
\begin{equation}
m(\beta,B)=
\frac{\sinh(\beta B)}{\sqrt{e^{-4\beta J}+\sinh^2(\beta B)}}.
\end{equation}
For $\beta > 0$ and $B > 0$ this is a nice function, and so, there is are no
phase transitions and no spontaneous magnetization
at any finite temperature.\footnote{Note, in particular, that for
$J=0$ (i.i.d.\ spins) we get paramagnetic characteristics
$m(\beta,B)=\tanh(\beta B)$, in agreement with
the result pointed out in the example of two--level systems, in one of our
earlier discussions.} However, at the absolute zero ($\beta\to\infty$), we get
\begin{equation}
\lim_{B\downarrow 0}\lim_{\beta\to\infty}m(\beta,B)=+1;~~
\lim_{B\uparrow 0}\lim_{\beta\to\infty}m(\beta,B)=-1,
\end{equation}
thus $m$ is discontinuous w.r.t.\ $B$ at $\beta\to\infty$, which means that
there is a phase transition at $T=0$. In other words, the Curie temperature is
$T_c=0$.

We see then that one--dimensional Ising model is easy to handle, but it is not
very interesting in the sense that there is actually no phase transition. The
extension to the two--dimensional Ising model on the square lattice is
surprisingly more difficult, but it is still solvable, albeit without a magnetic
field. It was first solved by
Onsager in 1944, who has shown that it exhibits a phase transition with
Curie temperture given by
\begin{equation}
T_c=\frac{2J}{k\ln(\sqrt{2}+1)},
\end{equation}
where $k$ is
Boltzmann's constant. For lattice dimension $\ge 3$, the problem is still
open.

It turns out then that whatever counts for the existence of phase transitions, is
not the intensity of the interactions (designated by the magnitude of $J$),
but rather the ``dimensionality'' of the
structure of the pairwise interactions. If we
denote by
$n_\ell$ the number of $\ell$--th order neighbors of every given site, namely, the
number of sites that can be reached within $\ell$ steps from the given site, then
whatever counts is how fast does the sequence $\{n_\ell\}$ grow, or more
precisely, what is the value of $d\dfn \lim_{\ell\to\infty}\frac{1}{\ell}\ln
n_\ell$, which is exactly the ordinary dimensionality for hypercubic lattices.
Loosely speaking, this dimension must be sufficiently large for a phase transition to exist.

To demonstrate this point, we next discuss an extreme case of a model where
this dimensionality
is actually infinite. In this model ``everybody is a neighbor of everybody
else'' and to the same extent, so it definitely has the highest connectivity
possible. This is not quite a physically realistic model, but
the nice thing about it is that it is easy to solve and that it exhibits a
phase transition that is fairly similar to those that exist in real systems. It is also
intimately related to a very popular approximation method in statistical
mechanics, called the {\it mean field approximation}. Hence it is sometimes
called the {\it mean field model}. It is also known as the {\it Curie--Weiss
model} or the {\it infinite range model}.

Finally, I should comment that there are
other ``infinite--dimensional'' Ising models, like the one defined on the
Bethe lattice (an infinite tree without a root and without leaves),
which is also easily solvable (by recursion) and it also
exhibits phase transitions (see Baxter's book), but we will not discuss it here.

\subsection{The Curie--Weiss Model}

According to the Curie--Weiss (C--W) model,
\begin{equation}
\calE(\bs)=-B\sum_{i=1}^n s_i-\frac{J}{2n}\sum_{i\ne j}s_is_j.
\end{equation}
Here, all pairs $\{(s_i,s_j)\}$ ``talk to each other'' with the same
``voice intensity'', $J/(2n)$, and without any geometry. The $1/n$ factor here
is responsible for
keeping the energy of the system extensive (linear in $n$), as the number of
interaction terms is quadratic in $n$. The factor $1/2$ compensates for the
fact that the summation over $i\ne j$ counts each pair twice. The first
observation is the trivial fact that
\begin{equation}
\left(\sum_is_i\right)^2=\sum_is_i^2+\sum_{i\ne j}s_is_j=n+\sum_{i\ne j}s_is_j
\end{equation}
where the second equality holds since $s_i^2\equiv 1$. It follows then, that
our Hamiltonian is, upto a(n immaterial) constant, equivalent to
\begin{equation}
\calE(\bs)=-B\sum_{i=1}^n s_i-\frac{J}{2n}\left(\sum_{i=1}^ns_i\right)^2=
-n\left[B\cdot\left(\frac{1}{n}\sum_{i=1}^n s_i\right)+
\frac{J}{2}\left(\frac{1}{n}\sum_{i=1}^ns_i\right)^2\right],
\end{equation}
thus $\calE(\bs)$ depends on $\bs$ only via the magnetization
$m(\bs)=\frac{1}{n}\sum_is_i$. This fact makes the C--W model very easy to
handle similarly as in the method of types:
\begin{eqnarray}
Z_n(\beta,B)&=&\sum_{\bs}\exp\left\{n\beta\left[B\cdot
m(\bs)+\frac{J}{2}m^2(\bs)\right]\right\}\nonumber\\
&=&\sum_{m=-1}^{+1}\Omega(m)\cdot e^{n\beta(Bm+Jm^2/2)}\nonumber\\
&\exe&\sum_{m=-1}^{+1}e^{nh_2((1+m)/2)}\cdot e^{n\beta(Bm+Jm^2/2)}\nonumber\\
&\exe&\exp\left\{n\cdot\max_{|m|\le 1}\left[h_2\left(\frac{1+m}{2}\right)+
\beta Bm+\frac{\beta m^2J}{2}\right]\right\}\nonumber
\end{eqnarray}
and so,
\begin{equation}
\phi(\beta,B)=\max_{|m|\le 1}\left[h_2\left(\frac{1+m}{2}\right)+
\beta Bm+\frac{\beta m^2J}{2}\right].
\end{equation}
The maximum is found by equating the derivative to zero, i.e.,
\begin{equation}
0=\frac{1}{2}\ln\left(\frac{1-m}{1+m}\right)+\beta B+\beta Jm
\equiv -\tanh^{-1}(m)+\beta B+\beta Jm
\end{equation}
or equivalently, the maximizing (and hence the dominant)
$m$ is a solution $m^*$ to the equation\footnote{Once again, for $J=0$, we are
back to non--interacting spins and then this equation gives the
paramagnetic behavior $m=\tanh(\beta B)$.}
$$m=\tanh(\beta B+\beta Jm).$$
Consider first the case
$B=0$, where the equation boils down to
\begin{equation}
m=\tanh(\beta Jm).
\end{equation}
It is instructive to look at this equation graphically.
Referring to Fig.\ \ref{cw1}, we have to make a distinction between
two cases: If $\beta J <1$, namely, $T > T_c\dfn J/k$, the slope of the
function $y=\tanh(\beta Jm)$ at the origin, $\beta J$, is smaller than the slope of the
linear function $y=m$, which is $1$, thus these two graphs intersect only at
the origin. It is easy to check that in this case, the second derivative of
$\psi(m)\dfn h_2((1+m)/2)+\beta Jm^2/2$ at $m=0$ is negative, and therefore it is indeed the
maximum (see Fig.\ \ref{cw2}, left part). Thus,
the dominant magnetization is $m^*=0$, which means
disorder and hence no spontaneous
magnetization for $T > T_c$.
\begin{figure}[ht]
\hspace*{1cm}\input{cw1.pstex_t}
\caption{\small Graphical solutions of equation $m=\tanh(\beta Jm)$: The
left part corresponds to the case $\beta J < 1$, where there is one
solution only, $m^*=0$. The right part corresponds to the case $\beta J > 1$, where
in addition to the zero solution, there are two non--zero solutions $m^*=\pm
m_0$.}
\label{cw1}
\end{figure}
On the other hand, when $\beta J > 1$, which means temperatures lower than
$T_c$, the initial slope of the $\tanh$ function is larger than that of the
linear function, but since the $\tanh$ cannot take values outside the interval
$(-1,+1)$, the two functions must intersect also at two additional, symmetric, non--zero
points, which we denote by $+m_0$ and $-m_0$ (see Fig.\ \ref{cw1}, right part).
In this case, it can readily be
shown that the second derivative of
$\psi(m)$ is positive at the origin (i.e., there is a local
minimum at $m=0$) and negative at $m=\pm m_0$, which means that
there are maxima at these two points (see Fig.\ \ref{cw2}, right part).
Thus, the dominant magnetizations are
$\pm m_0$, each capturing about half of the probability.
\begin{figure}[ht]
\hspace*{1cm}\input{cw2.pstex_t}
\caption{\small The function $\psi(m)=  h_2((1+m)/2)+\beta Jm^2/2$ has a
unique maximum at $m=0$ when $\beta J < 1$ (left graph) and two local maxima
at $\pm m_0$,
in addition to a local minimum at $m=0$, when $\beta J > 1$ (right graph).}
\label{cw2}
\end{figure}

Consider now the case $\beta J > 1$, where the magnetic field $B$ is brought
back into the picture. This will break the symmetry of the right graph of
Fig.\ \ref{cw2} and the corresponding graphs of $\psi(m)$ would be as in Fig.\
\ref{cw3}, where now the higher local maximum (which is also the global one)
is at $m_0(B)$ whose sign is as that of $B$. But as $B\to 0$, $m_0(B)\to m_0$
of Fig.\ \ref{cw2}.
\begin{figure}[ht]
\hspace*{1cm}\input{cw3.pstex_t}
\caption{\small The case $\beta J > 1$ with a magnetic field $B$. The left
graph corresponds to $B < 0$ and the right graph -- to $B > 0$.}
\label{cw3}
\end{figure}
\begin{figure}[ht]
\hspace*{1cm}\input{cw4.pstex_t}
\caption{\small
Magnetization vs.\ magnetic field: For $T < T_c$ there is spontaneous
magnetization: $\lim_{B\downarrow 0}m(\beta,B)=+m_0$ and
$\lim_{B\uparrow 0}m(\beta,B)=-m_0$, and so there is a discontinuity at
$B=0$.}
\label{cw4}
\end{figure}
Thus, we see the spontaneous magnetization here. Even after removing the
magnetic field, the system remains magnetized to the level of $m_0$, depending
on the direction (the sign) of $B$ before its removal. Obviously, the
magnetization $m(\beta,B)$ has a discontinuity at $B=0$ for $T < T_c$, which is a first
order phase transition w.r.t.\ $B$ (see Fig.\ \ref{cw4}). We note that the point $T=T_c$ is
the boundary between the region of existence and the
region of non--existence of a phase transition
w.r.t. $B$. Such a point is called a {\it critical point}.
The phase transition w.r.t.\ $\beta$ is of the second order.

Finally, we should mention here an alternative technique that can be used
to analyze this model, which is useful in many other contexts as well. It
is based on the idea of using a transform integral, in this case, the
{\it Hubbard--Stratonovich transform}, and then the saddle point method.
Specifically, we have the following chain of equalities:
\begin{eqnarray}
Z(h,K)&=&\sum_{\bs} \exp\left\{h\sum_{i=1}^n
s_i+\frac{K}{2n}\left(\sum_{i=1}^ns_i\right)^2\right\}~~~~h\dfn \beta
B,~K\dfn \beta J\nonumber\\
&=&\sum_{\bs} \exp\left\{h\sum_{i=1}^n
s_i\right\}\cdot\exp\left\{\frac{K}{2n}\left(\sum_{i=1}^ns_i\right)^2\right\}\nonumber\\
&=&\sum_{\bs} \exp\left\{h\sum_{i=1}^n
s_i\right\}\cdot\sqrt{\frac{n}{2\pi K}}\int_\reals \dd z
\exp\left\{-\frac{nz^2}{2K}+z\cdot\sum_{i=1}^ns_i\right\}\nonumber\\
&=&\sqrt{\frac{n}{2\pi K}}\int_\reals \dd z e^{-nz^2/(2K)}
\sum_{\bs} \exp\left\{(h+z)\sum_{i=1}^n
s_i\right\}\nonumber\\
&=&\sqrt{\frac{n}{2\pi K}}\int_\reals \dd z e^{-nz^2/(2K)}
\left[\sum_{s=-1}^1 e^{(h+z)s}\right]^n\nonumber\\
&=&\sqrt{\frac{n}{2\pi K}}\int_\reals \dd z e^{-nz^2/(2K)}
[2\cosh(h+z)]^n\nonumber\\
&=&2^n\cdot\sqrt{\frac{n}{2\pi K}}\int_\reals \dd z
\exp\{n[\ln\cosh(h+z)-z^2/(2K)]\}\nonumber
\end{eqnarray}
Using the the saddle point method (or the Laplace method), this integral is
dominated by the maximum of the function in the square brackets at the
exponent of the integrand, or equivalently, the minimum of the function
\begin{equation}
\gamma(z)=\frac{z^2}{2K}-\ln\cosh(h+z).
\end{equation}
by equating its derivative to zero, we get the very same equation as
$m=\tanh(\beta B+\beta Jm)$ by setting $z=\beta Jm$.
The function $\gamma(z)$ is different from the function
$\psi$ that we maximized earlier, but the extremum is the same. This function
is called the {\it Landau free energy}.

\subsection{Spin Glass Models With Random Parameters and Random Code
Ensembles}

So far we discussed only models where the non--zero coupling coefficients,
$\bJ=\{J_{ij}\}$ are equal, thus they are either all positive (ferromagnetic models) or
all negative (antiferromagnetic models). As mentioned earlier, there are also
models where the signs of these coefficients are mixed, which are called {\it
spin glass} models.

Spin glass models have a much more complicated and more interesting behavior
than ferromagnets, because there might be metastable states due to the fact
that not necessarily all spin pairs $\{(s_i,s_j)\}$ can be in their preferred
mutual polarization. It might be the case that some of these pairs are
``frustrated.'' In order to model situations of amorphism and disorder in
such systems, it is customary to model the coupling coeffcients as random
variables.

Some models allow, in addition to the random coupling
coefficients, also random local fields, i.e., the term $-B\sum_is_i$ in the
Hamiltonian, is replaced by $-\sum_iB_is_i$, where $\{B_i\}$ are random
variables, similarly as in the representation of $P(\bs|\by)$ pertaining to a coded
communicaion system, as discussed earlier, where $\{y_i\}$ play the role of local
magnetic fields. The difference, however, is that here the $\{B_i\}$ are
normally assumed i.i.d., whereas in the communication system model $P(\by)$
exhibits memory (even if the channel is memoryless) due to memory in $P(\bs)$.
Another difference is that in the physics model, the distribution of $\{B_i\}$
is assumed to be independent of temperature, whereas in coding, if we introduce a
temperature parameter by exponentiating (i.e., $P_\beta(\bs|\by)\propto
P^\beta(s)P^\beta(\by|\bs)$), the induced marginal of $\by$ will depend on $\beta$.

In the following discussion, let us refer to the case where only the coupling
coefficients $\bJ$ are random variables (similar things can be said in the
more general case, discussed in the last paragraph). This model with random
parameters means that there are now
two levels of randomness:
\begin{itemize}
\item Randomness of the coupling coefficients $\bJ$.
\item Randomness of the spin configuration $\bs$ given $\bJ$, according
to the Boltzmann distribution, i.e.,
\begin{equation}
P(\bs|\bJ)=\frac{\exp\left\{\beta\left[B\sum_{i=1}^ns_i+\sum_{(i,j)}J_{ij}s_is_j\right]\right\}}
{Z(\beta,B|\bJ)}.
\end{equation}
\end{itemize}
However, these two sets of RV's have a rather different stature.
The underlying setting is normally such that $\bJ$ is considered to be
randomly drawn once and for all, and then remain fixed, whereas $\bs$ keeps
varying all the time (according to the dynamics of the system).
At any rate, the time scale along which $\bs$ varies is much smaller than that
of $\bJ$. Another difference is that $\bJ$ is normally not
assumed to depend on temperature, whereas $\bs$, of course, does. In the
terminlogy of physicists, $\bs$ is considered an {\it annealed} RV, whereas
$\bJ$ is considered a {\it quenched} RV. Accordingly, there is a
corresponding distinction between {\it annealed averages} and {\it quenched
averages}.

Actually, there is (or, more precisely, should be) a parallel distinction
when we consider ensembles of randomly chosen codes in Information Theory.
When we talk about random coding, we normally think of the randomly chosen
code as being drawn once and for all, we don't reselect it after each
transmission (unless there are security reasons to do so), and so, a random
code should be thought of us a quenched entity, whereas the source(s) and
channel(s) are more naturally thought of as annealed entities. Nonetheless,
this is not what we usually do in Information Theory. We normally take double
expectations of some performance measure w.r.t.\ both source/channel and
the randomness of the code, on the same footing.\footnote{
There are few exceptions to this rule, e.g., a paper by
Barg and Forney, IEEE Trans.\ on IT, Sept.\ 2002, and several follow--ups.}
We will elaborate on this point later on.

Returning to spin glass models, let's see what is exactly the difference
between the quenched averaging and the annealed one. If we examine, for
instance, the free energy, or the log--partition function, $\ln
Z(\beta|\bJ)$, this is now a RV, of course, because it depends on the random
$\bJ$. If we denote by $\langle\cdot\rangle_{\bJ}$ the
expectation w.r.t.\ the randomness of $\bJ$, then quenched averaging means
$\langle\ln Z(\beta|\bJ)\rangle_{\bJ}$ (with the motivation of
the self--averaging property of the RV $\ln Z(\beta|\bJ)$ in many cases),
whereas annealed averaging means $\ln\langle Z(\beta|\bJ)\rangle_{\bJ}$.
Normally, the relevant average is the quenched one, but it is typically
also much harder to calculate (and it is customary to apply the replica
method then).
Clearly, the annealed average is never smaller than the quenched one because of Jensen's
inequality, but they sometimes coincide at high temperatures.
The difference between them is that in quenched averaging, the
dominant realizations of $\bJ$ are the typical ones, whereas in annealed
averaging, this is not necessarily the case. This follows from the
following sketchy consideration. As for the annealed average, we have:
\begin{eqnarray}
\left<Z(\beta|\bJ\right>&=&\sum_{\bJ}P(\bJ)Z(\beta|\bJ)\nonumber\\
&\approx&\sum_{\alpha}\mbox{Pr}\{\bJ:~Z(\beta|\bJ)\exe e^{n\alpha}\}\cdot
e^{n\alpha}\nonumber\\
&\approx&\sum_{\alpha}e^{-nE(\alpha)}\cdot
e^{n\alpha}~~~~~~\mbox{(assuming exponential probabilities)}\nonumber\\
&\exe& e^{n\max_\alpha[\alpha-E(\alpha)]}
\end{eqnarray}
which means that the annealed average is dominated by realizations
of the system with
\begin{equation}
\frac{\ln Z(\beta|\bJ)}{n}\approx \alpha^*\dfn
\mbox{arg}\max_\alpha[\alpha-E(\alpha)],
\end{equation}
which may differ from the typical value of $\alpha$,
which is
\begin{equation}
\alpha=\phi(\beta)
\equiv\lim_{n\to\infty}\frac{1}{n}\left<\ln
Z(\beta|\bJ)\right>.
\end{equation}
On the other hand, when it comes to quenched averaging,
the RV $\ln Z(\beta|\bJ)$ behaves linearly in $n$,
and concentrates strongly around
the typical value $n\phi(\beta)$,
whereas other values are weighted by (exponentially) decaying probabilities.

In the coded communication
setting, there is a strong parallelism.
Here, there is a distinction between the exponent of the
average error probability, $\ln\bE P_e(\calC)$ (annealed) and the average
exponent of the error probability $\bE\ln P_e(\calC)$ (quenched), where
$P_e(\calC)$ is the error probability of a randomly selected code $\calC$.
Very similar things can be said here too.

The literature on spin glasses includes many models for the randomness of
the coupling coefficients. We end this part by listing just a few.
\begin{itemize}
\item The {\it Edwards--Anderson} (E--A) model, where $\{J_{ij}\}$ are non--zero
for nearest--neighbor pairs only (e.g., $j=i\pm 1$ in one--dimensional model).
According to this model, these $J_{ij}$'s are i.i.d.\ RV's, which are normally
modeled to have a zero--mean Gaussian pdf, or binary symmetric with levels $\pm J_0$.
It is customary to work with a zero--mean distribution if we have a pure spin
glass in mind. If the mean is nonzero, the model has either a ferromangetic
or an anti-ferromagnetic bias, according to the sign of the mean.
\item The {\it Sherrington--Kirkpatrick} (S--K) model, which is similar to the
E--A model, except that the support of $\{J_{ij}\}$ is extended to include all
$n(n-1)/2$ pairs, and not only nearest--neighbor pairs. This can be thought of
as a stochastic version of the C--W model in the sense that here too, there is
no geometry, and every spin `talks' to every other spin to the same extent,
but here the coefficients are random, as said.
\item The {\it $p$--spin} model, which is similar to the S--K model, but now
the interaction term consists, not only of pairs, but also triples,
quadraples, and so on, up to cliques of size $p$, i.e., products
$s_{i_1}s_{i_2}\cdot\cdot\cdot s_{i_p}$, where $(i_1,\ldots,i_p)$ exhaust all
possible subsets of $p$ spins out of $n$. Each such term has a Gaussian
coefficient $J_{i_1,\ldots,i_p}$ with an appropriate variance.
\end{itemize}
Considering the $p$--spin model, it turns out that if we look at the extreme
case of $p\to\infty$ (taken after the thermodynamic limit $n\to\infty$), the
resulting behavior turns out to be extremely erratic: all energy levels
$\{\calE(\bs)\}_{\bs\in\{-1,+1\}^n}$ become i.i.d.\ Gaussian RV's. This is,
of course, a toy model, which has very little to do with reality (if any),
but it is surprisingly interesting and easy to work with. It is called the
{\it random energy model} (REM). We have already mentioned it as an example
on which we demonstrated the replica method. We are next going to talk about
it extensively because it turns out to be very relevant for random coding
models.

config: arxiv


TITLE: Find numbers such that...
QUESTION [0 upvotes]: Find all the triples $(x,y,z)∈Z^3$ such that
$x^2+7y^2=2012z^2.$
It is clear that $7y^2 \equiv 0$(mod 7), so $x^2\equiv3z^2$(mod 7).
I don't know how to proceed from there.

REPLY [0 votes]: In the  solution for $y$ below
\begin{align*}
x^2+7y^2&   =2012z^2\\
\implies 7y^2&=2012z^2-x^2\\
\implies y&=\sqrt{\frac{2012z^2-x^2}{7}}
\end{align*}
the only fractions that yield intgers are when $x,z$ are both mutiples of $7.\quad$ Of those integers none are perfect squares for $x,z,\le 7000\quad$
This is not proof but it is strong evidence that the only solution is $\quad(0,0,0)$


TITLE: General solution to a 4th order ODE: $y^{(4)}-k^4 y=0$
QUESTION [0 upvotes]: How is $y=a \cos kx + b \sin kx + c \cosh kx + d \sinh kx$ the general solution of the ODE?
$$y^{(4)}-k^4 y=0$$
I can not understand how exp e transforms into sin and cos Cosh Sinh

REPLY [2 votes]: Remember that the characteristic equation here is obtained by using the ansatz $y=e^{\lambda x}$. Thus, if you substitute it into the ODE, you will obtain:
$$\lambda^4 e^{\lambda x}-k^4 e^{\lambda x}=0$$
$$e^{\lambda x}(\lambda^4-k^4)=0$$
Since $e^{\lambda x}\neq 0$ for all $\lambda, x\in \mathbb{R}$, we can reduce this to the characteristic equation:
$$\lambda^4-k^4=0$$
The roots to this are obviously $\lambda=\pm k, \pm ik$, as mentioned by @Moo. Hence, the general solution can be written as:
$$y(x)=c_1 e^{kx}+c_2 e^{-kx}+c_3 e^{ikx}+c_4 e^{-ikx} \tag{1}$$

You said that you didn't understand how the exponential transforms into the trigonometric and hyperbolic trigonometric functions:
Remember that the constants $c_1,c_2,c_3$ and $c_4$ are arbitrary. What do I mean by this? We can rewrite this general solution by remembering that $\cosh(x)\equiv \dfrac{e^x+e^{-x}}{2}$ and $\sinh(x)\equiv \dfrac{e^x-e^{-x}}{2}$. Notice that you can therefore write:
$$A\cosh(kx)=\frac{A}{2}e^{kx}+\frac{A}{2}e^{-kx} \qquad B\sinh(kx)=\frac{B}{2}e^{kx}-\frac{B}{2}e^{-kx}$$
If we add them together, we obtain:
$$\begin{align} A\cosh(kx)+B\sinh(kx)&=\left(\frac{A}{2}+\frac{B}{2}\right)e^{kx}+\left(\frac{A}{2}-\frac{B}{2}\right)e^{-kx}\\&=c_1e^{kx}+c_2e^{-kx} \end{align}$$
Since the constants are arbitrary, we can define $c_1:=\frac{A+B}{2}$ and $c_2:=\frac{A-B}{2}$ as done above, and then substitute it into $(1)$. The first part is complete.

Can you do the part with $\cos$ and $\sin$ for $c_3 e^{ikx}+c_4 e^{-ikx}$? Again, remember that constants are arbitrary.
Hint: Euler's Formula
$$e^{i\theta}\equiv \cos(\theta)+i\sin(\theta)$$
And remember that $\cos(\theta)$ is even and $\sin(\theta)$ is odd.


TITLE: Minimizing $a^2+b^2+c^2+d^2$ for positive reals satisfying $(a+b) (c+d)=143$, $(a+c)(b+d)=150$, $(a+d) (b+c)=169$
QUESTION [0 upvotes]: Can anyone do this?

Suppose $a$, $b$, $c$, and $d$ are positive real numbers that satisfy the system of equations
$$\begin{align}
(a+b) (c+d)&=143 \\
(a+c) (b+d)&=150 \\
(a+d) (b+c)&=169
\end{align}$$
Compute the smallest possible value of $a^2+b^2+c^2+d^2$.

REPLY [0 votes]: From math.stackexchange.com/questions/3014786/…  we get  $a+d=b+c$.
System
$$\begin{align}
(a+b) (c+d)&=143 \\
(a+c) (b+d)&=150 \\
(a+d) (b+c)&=169\\
a+d=b+c
\end{align}$$
has 8 solutions
$a=-\frac{\sqrt{26}+\sqrt{19}-13}{2}\operatorname{,}b=-\frac{\sqrt{26}-\sqrt{19}-13}{2}\operatorname{,}c=\frac{\sqrt{26}-\sqrt{19}+13}{2}\operatorname{,}d=\frac{\sqrt{26}+\sqrt{19}+13}{2}$;
$a=\frac{\sqrt{26}-\sqrt{19}+13}{2}\operatorname{,}b=\frac{\sqrt{26}+\sqrt{19}+13}{2}\operatorname{,}c=-\frac{\sqrt{26}+\sqrt{19}-13}{2}\operatorname{,}d=-\frac{\sqrt{26}-\sqrt{19}-13}{2}$;
$a=-\frac{\sqrt{26}-\sqrt{19}-13}{2}\operatorname{,}b=-\frac{\sqrt{26}+\sqrt{19}-13}{2}\operatorname{,}c=\frac{\sqrt{26}+\sqrt{19}+13}{2}\operatorname{,}d=\frac{\sqrt{26}-\sqrt{19}+13}{2}$;
$a=\frac{\sqrt{26}+\sqrt{19}+13}{2}\operatorname{,}b=\frac{\sqrt{26}-\sqrt{19}+13}{2}\operatorname{,}c=-\frac{\sqrt{26}-\sqrt{19}-13}{2}\operatorname{,}d=-\frac{\sqrt{26}+\sqrt{19}-13}{2}$;
$a=-\frac{\sqrt{26}+\sqrt{19}+13}{2}\operatorname{,}b=-\frac{\sqrt{26}-\sqrt{19}+13}{2}\operatorname{,}c=\frac{\sqrt{26}-\sqrt{19}-13}{2}\operatorname{,}d=\frac{\sqrt{26}+\sqrt{19}-13}{2}$;
$a=\frac{\sqrt{26}-\sqrt{19}-13}{2}\operatorname{,}b=\frac{\sqrt{26}+\sqrt{19}-13}{2}\operatorname{,}c=-\frac{\sqrt{26}+\sqrt{19}+13}{2}\operatorname{,}d=-\frac{\sqrt{26}-\sqrt{19}+13}{2}$;
$a=-\frac{\sqrt{26}-\sqrt{19}+13}{2}\operatorname{,}b=-\frac{\sqrt{26}+\sqrt{19}+13}{2}\operatorname{,}c=\frac{\sqrt{26}+\sqrt{19}-13}{2}\operatorname{,}d=\frac{\sqrt{26}-\sqrt{19}-13}{2}$;
$a=\frac{\sqrt{26}+\sqrt{19}-13}{2}\operatorname{,}b=\frac{\sqrt{26}-\sqrt{19}-13}{2}\operatorname{,}c=-\frac{\sqrt{26}-\sqrt{19}+13}{2}\operatorname{,}d=-\frac{\sqrt{26}+\sqrt{19}+13}{2}$.
On all solutions function $a^2+b^2+c^2+d^2$ has minimal value 214.
First 4 solutions is positive.


text:
\section{Technical results} \label{appendix:techResults}

\begin{proof} {\bfseries \Cref{prop:MI_SM_uncorrelatedCase}} \label{proof:prop_MI_SM_uncorrelatedCase}
If $Y_{i_j} | X$ are independent then the conditional entropy of  $\mathcal{P}^{\top}Y|X$ can be written as $
\mathcal{H}(\mathcal{P}^{\top}Y|X) = \sum_{j=1}^{k} \mathcal{H}(Y_{i_j} | X).$ This allows us to write the mutual information $\mathcal{I}(X;\mathcal{P}^{\top}Y)$ as follows:
\begin{equation} \label{eqn:MI_UncorrelatedCase}
 \mathcal{I}(X;\mathcal{P}^{\top}Y) = \mathcal{H}(\mathcal{P}^{\top}Y) - \mathcal{H}(\mathcal{P}^{\top}Y|X)= \mathcal{H}(\mathcal{P}^{\top}Y) - \sum_{j=1}^{k} \mathcal{H}(Y_{i_j} | X).
\end{equation}
Consider selection operators $\mathcal{P}_1 \in \mathbb{R}^{ m \times k_1}$ and $\mathcal{P}_2 \in \mathbb{R}^{ m \times k_2}$ such that $\mathscr{I}(\mathcal{P}_1) \subseteq \mathscr{I}(\mathcal{P}_2)$. Consider a canonical row $e_j$ that selects $Y_{i_j}$, with  $\text{supp}(e_j) \notin \mathscr{I}(\mathcal{P}_2)$. We define new selection operators $\widehat{\mathcal{P}}_1 \coloneqq  [\mathcal{P}_1, e_j] \in \mathbb{R}^{ m \times (k_1 + 1) }$ and  $\widehat{\mathcal{P}}_2 \coloneqq  [\mathcal{P}_2, e_j] \in \mathbb{R}^{ m \times (k_2+1)}$ by appending $e_j$ to $\mathcal{P}_1$ and $\mathcal{P}_2$ respectively. The  incremental change in mutual information from  incorporating $Y_{i_j}$ can be determined for each case. Let us  consider $\mathcal{I}(X;\widehat{\mathcal{P}}_2^{\top} Y) - \mathcal{I}(X;\mathcal{P}_2^{\top} Y) $; the expression can be adapted for $  \mathcal{I}(X;\widehat{\mathcal{P}}_1^{\top} Y) - \mathcal{I}(X;\mathcal{P}_1^{\top} Y)$ accordingly.
\begin{subequations} \label{eqn:MI_incrementalDiff}
\begin{align}
  \mathcal{I}(X;\widehat{\mathcal{P}}_2^{\top} Y) - \mathcal{I}(X;\mathcal{P}_2^{\top} Y)
\label{eqn:MI_incrementalDiff_a}  &= \mathcal{H}(\widehat{\mathcal{P}}_2^{\top} Y) - \mathcal{H}(\mathcal{P}_2^{\top} Y) - \mathcal{H}(Y_{i_j} | X),\\
\label{eqn:MI_incrementalDiff_b}  &= \mathcal{H}( Y_{i_j} | \mathcal{P}_2^{\top} Y) - \mathcal{H}(Y_{i_j} | X).
\end{align}
\end{subequations}
To obtain \cref{eqn:MI_incrementalDiff_b} we recognize from the chain rule for entropy that $\mathcal{H}( Y_{i_j} | \mathcal{P}_2^{\top} Y)  =   \mathcal{H}(\widehat{\mathcal{P}}_2^{\top} Y) - \mathcal{H}(\mathcal{P}_2^{\top} Y)$. Since conditioning cannot increase entropy we can assert,
\begin{align}
\mathcal{H}( Y_{i_j} | \mathcal{P}_1^{\top} Y) & \geq \mathcal{H}( Y_{i_j} | \mathcal{P}_2^{\top} Y), \\
\Rightarrow  \mathcal{I}(X;\widehat{\mathcal{P}}_1^{\top} Y) - \mathcal{I}(X;\mathcal{P}_1^{\top} Y)  & \geq   \mathcal{I}(X;\widehat{\mathcal{P}}_2^{\top} Y) - \mathcal{I}(X;\mathcal{P}_2^{\top} Y),
\end{align}
which concludes the proof.
\end{proof}

\subsection{Proofs concerning batch greedy algorithms} \label{appendix_subsec:greedy_stuff}

Below we provide a formal proof demonstrating that any function  $F$  is supermodular if and only if the supermodularity ratio $\eta = 1$. Recall that the supermodularity ratio without the cardinality parameter is defined as the largest scalar such that
\begin{displaymath}
\frac{\rho_{\mathscr{A}} (\mathscr{B})}{\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}} \rho_{\nu}(\mathscr{B})} \geq \eta ,
\qquad  \forall \mathscr{A}, \mathscr{B} \subseteq \mathscr{V}.
\end{displaymath}
\begin{proof_without_of_suffix}  \label{proof:prop_supermodularity_ratio}
    Assuming $\eta=1$, we can claim the following inequalities for any set $\mathscr{B} \subseteq \mathscr{V}$, and $\{\nu_1,\nu_2\} \in \mathscr{V} \setminus \mathscr{B}$
    \begin{align}
    		F(\{\nu_1,\nu_2\} \cup \mathscr{B}) - F(\mathscr{B}) & \geq  \sum_{i=1}^{2} \lr{  F(\{\nu_i\} \cup \mathscr{B})  - F(\mathscr{B})  },\\
\Rightarrow     		F(\{\nu_1,\nu_2\} \cup \mathscr{B}) - F(\{\nu_1\} \cup \mathscr{B}) & \geq F(\{\nu_2\} \cup \mathscr{B}) - F(\mathscr{B}).
    \end{align}
This demonstrates supermodularity  \cite[Proposition~2.3]{Bach2013} having assumed $\eta=1$. To complete the proof, we prove the proposition statement the other way around by recursively exploiting the supermodularity property. For any sets $\mathscr{A},\mathscr{B} \subseteq \mathscr{V}$ with $\abs{\mathscr{A}}\leq k, \mathscr{A} \cap \mathscr{B} = \emptyset$ consider $\nu_{k} \in \mathscr{A} $, we claim because of  supermodularity
\begin{align}
	F(\mathscr{A}\cup \mathscr{B}) - F(\mathscr{B})
	&\geq F(  \mathscr{A} \setminus \{\nu_{k}\} \cup\mathscr{B}) - F(\mathscr{B}) + \underbrace{F(\{\nu_{k}\} \cup \mathscr{B}) - F(\mathscr{B})}_{\rho_{\nu_k}(\mathscr{B})}.
\end{align}
Repeating the same argument but on the term $F(  \mathscr{A} \setminus \{\nu_{k}\} \cup\mathscr{B}) - F(\mathscr{B})$ we have,
\begin{align}
	F(\mathscr{A}\cup \mathscr{B}) - F(\mathscr{B})
	&\geq F(  \mathscr{A} \setminus \{\nu_{k},\nu_{k-1}\} \cup\mathscr{B}) - F(\mathscr{B}) + \rho_{\nu_k}(\mathscr{B}) + \rho_{\nu_{k-1}}(\mathscr{B}).
\end{align}
Continuing the process gives us the inequality
\begin{equation}
	F(\mathscr{A} \cup \mathscr{B}) - F(\mathscr{B})
	\geq \sum_{\nu \in \mathscr{A}} \lr{F(\{\nu\} \cup \mathscr{B}) - F(\mathscr{B})}.
\end{equation}\end{proof_without_of_suffix}

\subsubsection{Standard batch greedy algorithm} \label{appendix_subsubsec:std_batch_greedy}

\begin{proof}  {\bfseries \Cref{thm:batch_std_greedy}} \label{proof:theorem_batch_std_greedy}
	Our arguments closely follow those of \cite{Nemhauser1978,Wolsey1982} with suitable modifications. Let $\mathscr{A}^{*}$ be a maximizer of $F$ with $k$ elements. Let $\{a_{i_1},\ldots,a_{i_{q_j}} \}$ be the $q_j$ elements selected during the $j$--th step of the greedy algorithm. If $\mathscr{A}_{j-1}$ is the set of elements after $j-1$ steps, then $\mathscr{A}_j = \mathscr{A}_{j-1} \cup \{a_{i_1},\ldots,a_{i_{q_j}} \}$. If there are $l$ steps altogether, we naturally have $q_1 + q_2 + \cdots + q_l = k$.

	For a given $j \in \{1,\ldots,l \}$, we denote by $\{b_1,\ldots,b_m\}$ the elements of $\mathscr{A}^{*} \setminus \mathscr{A}_{j-1}$ (we must have $k \geq m \geq q_j + q_{j+1} + \cdots + q_l $). We then have
\begin{subequations}	\begin{align}
		F(\mathscr{A}^{*})
		& \overset{a}{\leq} F(\mathscr{A}^{*} \cup \mathscr{A}_{j-1}),\\
	    & \overset{b}{\leq} F(\mathscr{A}_{j-1})  + \frac{1}{\gamma_{\mathscr{V},m}}\sum_{i=1}^{m} \lr{F(\mathscr{A}_{j-1} \cup \{ b_i \}) - F(\mathscr{A}_{j-1})}\\
    	    & \overset{c}{\leq} F(\mathscr{A}_{j-1}) + \frac{m}{q_j \gamma_{\mathscr{V},m}} \sum_{t=1}^{q_j} \lr{F(\mathscr{A}_{j-1} \cup \{ a_{i_t} \}) - F(\mathscr{A}_{j-1})}\\
    	    & \overset{d}{\leq} F(\mathscr{A}_{j-1}) + \frac{m}{q_j \eta_{\mathscr{V},q_j} \gamma_{\mathscr{V},m}} \lr{F(\mathscr{A}_{j}) - F(\mathscr{A}_{j-1})}\\
\label{eqn:proof_theorem_batch_std_greedy_1}  & \overset{e}{\leq} F(\mathscr{A}_{j-1})  + \frac{k}{q_j  \eta_{\mathscr{V},q_j} \gamma_{\mathscr{V},k}} \lr{F(\mathscr{A}_{j}) - F(\mathscr{A}_{j-1})}.
	\end{align} \end{subequations}
\begin{itemize}
	\item[a)] holds because $F$ is non-decreasing,
	\item[b)] holds by definition of the submodularity ratio (\Cref{def:sm_ratio_das_kempe}),
	\item[c)] holds because $q_j \leq m$, and the $q_j$ elements in the set $\{a_{i_1},\ldots,a_{i_{q_j}} \}$ are (by virtue of the batch greedy algorithm) those that correspond to the highest incremental gains at step $j$:
	\[ \frac{\sum_{i=1}^{m} \lr{F(\mathscr{A}_{j-1} \cup \{ b_i \}) - F(\mathscr{A}_{j-1})}}{m} \leq \frac{\sum_{t=1}^{q_j} \lr{F(\mathscr{A}_{j-1} \cup \{ a_{i_t} \}) - F(\mathscr{A}_{j-1})}}{q_j} \]

	\item[d)] holds by definition of $ \eta_{\mathscr{V},q_j}$ as the supermodularity ratio (\Cref{def:supermodularity_ratio}),
	\item[e)] holds because $m \leq k$, and $\gamma_{\mathscr{V},m} \geq \gamma_{\mathscr{V},k}$.
\end{itemize}
A simple manipulation of \cref{eqn:proof_theorem_batch_std_greedy_1} allows us to write the following,
\begin{equation}
	F(\mathscr{A}^{*})  - F(\mathscr{A}_j) \leq \lr{ 1 - \frac{q_j  \eta_{\mathscr{V},q_j} \gamma_{\mathscr{V},k} }{k}} \lr{ F(\mathscr{A}^{*})  - F(\mathscr{A}_{j-1})} .
\end{equation}
This leads to $F(\mathscr{A}^{*})  - F(\mathscr{A}_l) \leq \prod_{j=1}^{l} \lr{ 1 - \frac{q_j  \eta_{\mathscr{V},q_j} \gamma_{\mathscr{V},k}}{k}}  F(\mathscr{A}^{*})$, and the theorem statement follows.
\end{proof}

\subsubsection{Distributed batch greedy algorithm} \label{appendix_subsubsec:parallel_batch_greedy}

\input{input/parallel_greedy}

\subsubsection{Stochastic batch greedy algorithm} \label{appendix_subsubsec:stochastic_batch_greedy}

\input{input/stochastic_greedy}

\subsubsection{MM batch greedy algorithm} \label{appendix_subsubsec:MM_batch_greedy}

\begin{proof} {\bfseries \Cref{thm:greedy_ascent}} \label{proof:theorem_greedy_ascent}
	The arguments are similar to the proof of \Cref{thm:batch_std_greedy}. Let $\mathscr{A}^{*}$ be a maximizer of $F$ with $k$ elements. Let $\{a_{i_1},\ldots,a_{i_{q_j}} \}$ be the $q_j$ elements selected during the $j$--th step of the greedy algorithm. If $\mathscr{A}_{j-1}$ is the set of elements after $j-1$ steps, then $\mathscr{A}_j = \mathscr{A}_{j-1} \cup \{a_{i_1},\ldots,a_{i_{q_j}} \}$. If there are $l$--steps all together, we naturally have $q_1 + q_2 + \cdots + q_l = k$.

	For a given $j \in \{1,\ldots,l \}$, we denote by $\{b_1,\ldots,b_m\}$ the elements of $\mathscr{A}^{*} \setminus \mathscr{A}_{j-1}$ (we must have $k \geq m \geq q_j + q_{j+1} + \cdots + q_l $). We then have,
\begin{subequations} \begin{align}
	F(\mathscr{A}^{*})
	& \overset{a}{\leq} F(\mathscr{A}^{*} \cup \mathscr{A}_{j-1}),\\
	&\overset{b}{=}  F(\mathscr{A}_{j-1})  +  \rho_{\mathscr{A}^{*}} \lr{ \mathscr{A}_{j-1}} , \\
	&\overset{c}{\leq}  F(\mathscr{A}_{j-1})  +   \delta_j +  \mathcal{M}_{\uparrow}  \left[  \rho_{\mathscr{A}^{*}} \lr{ \mathscr{A}_{j-1}} \right], \\
	&\overset{d}{\leq}  F(\mathscr{A}_{j-1})  +   \delta_j +  \frac{k}{q_j} \mathcal{M}_{\uparrow}  \left[  \rho_{\mathscr{A}_{j}} \lr{ \mathscr{A}_{j-1}} \right], \\
	&\overset{e}{\leq}  F(\mathscr{A}_{j-1})  +   \delta_j +  \frac{k}{q_j} 	\rho_{\mathscr{A}_{j}} \lr{ \mathscr{A}_{j-1}}, \\
\label{eqn:proof_theorem_greedy_ascent_1} 	&\overset{f}{\leq}  F(\mathscr{A}_{j-1}) + \frac{k \lr{1+\tau_j}}{q_j} \rho_{\mathscr{A}_{j}} \lr{ \mathscr{A}_{j-1}}.
\end{align} \end{subequations}
\begin{itemize}
	\item[a)] holds because $F$ is non-decreasing,
	\item[b)] is an identity since $F(\mathscr{A}^{*} \cup \mathscr{A}_{j-1}) - F(\mathscr{A}_{j-1}) \eqqcolon  \rho_{\mathscr{A}^{*}} \lr{ \mathscr{A}_{j-1}}$ is the incremental gain,
	\item[c)] holds by defining $\delta_j$ as the smallest scalar satisfying,
	\begin{equation}
       \rho_{\mathscr{A}^{*}} \lr{ \mathscr{A}_{j-1}}  \leq   \delta_j +  \mathcal{M}_{\uparrow}  \left[  \rho_{\mathscr{A}^{*}} \lr{ \mathscr{A}_{j-1}} \right],
	\end{equation}
	\item[d)] holds because $q_j \leq m \leq k$, and the $q_j$ elements in the set $\{a : a \in \mathscr{A}_j \setminus \mathscr{A}_{j-1}\}$ maximize $\mathcal{M}_{\uparrow}  \left[  \rho_{a} \lr{ \mathscr{A}_{j-1}} \right]$, and hence
	\[ \frac{\mathcal{M}_{\uparrow}  \left[  \rho_{\mathscr{A}^{*}} \lr{ \mathscr{A}_{j-1}} \right]}{m} \leq  \frac{\mathcal{M}_{\uparrow}  \left[  \rho_{\mathscr{A}_{j}} \lr{ \mathscr{A}_{j-1}} \right]}{q_j}, \]
     \item[e)] holds since $\mathcal{M}_{\uparrow}  \left[  \rho_{\mathscr{A}_{j}} \lr{ \mathscr{A}_{j-1}} \right] \leq  \rho_{\mathscr{A}_{j}} \lr{ \mathscr{A}_{j-1}}$,
		\item[f)] holds by defining  $\tau_j$ as the smallest scalar satisfying
	\begin{equation}
	 \delta_j \leq \frac{ \tau_j k \rho_{\mathscr{A}_{j}} \lr{ \mathscr{A}_{j-1}}}{q_j}.
	\end{equation}
\end{itemize}
	$\delta_j$ quantifies the slackness of the modular lower bound, while $\tau_j$ does so relative to the incremental gain at the current step. A simple manipulation of \cref{eqn:proof_theorem_greedy_ascent_1} allows us to write the following:
\begin{equation}
	F(\mathscr{A}^{*})  - F(\mathscr{A}_j) \leq \lr{ 1 - \frac{q_j}{k \lr{1+\tau_j}}} \lr{ F(\mathscr{A}^{*})  - F(\mathscr{A}_{j-1})} .
\end{equation}
This leads to $F(\mathscr{A}^{*})  - F(\mathscr{A}_l) \leq \prod_{j=1}^{l} \lr{ 1 - \frac{q_j}{k \lr{1+\tau_j}}} F(\mathscr{A}^{*})$, and the theorem statement follows.
\end{proof}

\subsection{Proofs concerning linear Bayesian experimental design criterion} \label{appendix_subsec:lbip}

\begin{proof} {\bfseries \Cref{prop:eigen_prob_equivalence}} \label{proof:prop_eigen_prob_equivalence}
Let $(\sigma_j, U_j)$  be any generalized eigenvalue-eigenvector pair of the definite pair $(\Gamma_{Y}-\Gamma_{Y|X},\Gamma_{Y|X})$.
Since  $\Gamma_{Y}-\Gamma_{Y|X}\succeq 0$ and $\Gamma_{Y|X} \succ 0$, we can claim $\sigma_j \geq 0$. It is evident that $(1+\sigma_j, U_j)$ is the corresponding generalized eigenvalue-eigenvector pair of the definite pair $(\Gamma_{Y},\Gamma_{Y|X})$. To
establish \cref{enumerate:prop_eigen_prob_equivalence_1} and \cref{enumerate:prop_eigen_prob_equivalence_2}, we need to show that $\sigma_j$ and $1+\sigma_j$ are the corresponding generalized eigenvalues of the definite pair $(\Gamma_{X}- \Gamma_{X|Y},\Gamma_{X|Y})$ and $(\Gamma_{X},\Gamma_{X|Y})$, respectively. \Cref{enumerate:prop_eigen_prob_equivalence_1} $\Leftrightarrow$ \cref{enumerate:prop_eigen_prob_equivalence_2} then holds automatically.

Using the specified linear statistical model \cref{eqn:linearFwdModel}, we can deduce $\Gamma_{Y}-\Gamma_{Y|X} = G \Gamma_{X} G^{\top}$. For the generalized eigenvalue-eigenvector pair $(\sigma_j, U_j)$, we have the relationship
\begin{equation} \label{eqn:eigProb_Yspace}
	G \Gamma_{X} G^{\top} U_j = \Gamma_{Y|X} U_j \sigma_j.
\end{equation}
Multiplying \cref{eqn:eigProb_Yspace} by $G^{\top} \Gamma_{Y|X}^{-1}$, we have
\begin{equation} \label{eqn:eigProb_Xspace_interim}
	G^{\top} \Gamma_{Y|X}^{-1} G \Gamma_{X} G^{\top} U_j = G^{\top} U_j \sigma_j.
\end{equation}
Define $\widetilde{V}_j\coloneqq \frac{1}{\alpha_j} \Gamma_{X} G^{\top} U_j$, where $\alpha_j$ is some scaling parameter to obtain the desired orthogonality, and rewrite \cref{eqn:eigProb_Xspace_interim} as
\begin{equation} \label{eqn:eigProb_Xspace}
	G^{\top} \Gamma_{Y|X}^{-1} G  \widetilde{V}_j = \Gamma_{X}^{-1} \widetilde{V}_j \sigma_j.
\end{equation}
 From \cref{eqn:eigProb_Xspace}, we claim $(\sigma_j,\widetilde{V}_j)$ is a generalized eigenvalue-eigenvector pair of  $(G^{\top} \Gamma_{Y|X}^{-1} G, \Gamma_{X}^{-1})$. Consequently, $(1+\sigma_j,\widetilde{V}_j)$ is the corresponding pair of  $(\Gamma_{X}^{-1}+G^{\top} \Gamma_{Y|X}^{-1} G, \Gamma_{X}^{-1}) \eqqcolon  (\Gamma_{X|Y}^{-1}, \Gamma_{X}^{-1}) $. By definition the definite pairs $(\Gamma_{X|Y}^{-1}, \Gamma_{X}^{-1}) $ and  $(\Gamma_{X},\Gamma_{X|Y})$ have the same spectrum. Further, if $(1+\sigma_j,\widetilde{V}_j)$ is a generalized eigenvalue-eigenvector pair of  $(\Gamma_{X|Y}^{-1}, \Gamma_{X}^{-1}) $, then  $(1+\sigma_j,\Gamma_{X}^{-1}\widetilde{V}_j)$ is the corresponding pair of $(\Gamma_{X},\Gamma_{X|Y})$. This completes the proof for  \cref{enumerate:prop_eigen_prob_equivalence_2}. We could have alternatively defined $\Gamma_{X|Y}^{-1}\widetilde{V}_j$ as the generalized eigenvector without any bearing on the spectrum. The choice we make is motivated by the orthogonality of eigenvectors we desire.

Let us define $V_j \coloneqq  \Gamma_{X}^{-1}\widetilde{V}_j$. Then \cref{enumerate:prop_eigen_prob_equivalence_1} follows by recognizing that $(\sigma_j,V_j)$ is the corresponding generalized eigenvalue-eigenvector pair of  $(\Gamma_{X}-\Gamma_{X|Y},\Gamma_{X|Y})$.
\end{proof}

\begin{proposition}\label{prop:expSymKLDiv}
Let $X \in \mathbb{R}^{n}$ and $Y \in \mathbb{R}^{m}$ be jointly Gaussian random variables as defined in \Cref{subsubsec:lbip_notation_setup}. Let $\mathcal{P} \in \mathbb{R}^{m \times k }$ be a selection operator such that $Y_{\mathcal{P}} \coloneqq  \mathcal{P}^{\top}Y = \left[ Y_{i_1},\ldots,Y_{i_{k}} \right] ^{\top}$. The expected symmetrized Kullback--Leiber divergence, $\mathbb{E}_{\pi_{Y_{\mathcal{P}}}} \left[ D^{sym}_{\text{KL}} (\pi_{X|Y_{\mathcal{P}}}, \pi_{X} ) \right]$, between the prior  $\pi_{X}$ and the posterior $\pi_{X|Y_{\mathcal{P}}}$

 is equal to the sum of the generalized eigenvalues $\widehat{\sigma}_j$ of the definite pair $(\Gamma_{Y_{\mathcal{P}}} - \Gamma_{Y_{\mathcal{P}}|X},\Gamma_{Y_{\mathcal{P}}|X})$ or equivalently $(\Gamma_{X} - \Gamma_{X|Y_{\mathcal{P}} },\Gamma_{X|Y_{\mathcal{P}} })$, i.e.,
\begin{displaymath}
		\mathbb{E}_{\pi_{Y_{\mathcal{P}}}} \left[ D^{sym}_{\text{KL}} (\pi_{X|Y_{\mathcal{P}}}, \pi_{X} ) \right] \coloneqq  \mathbb{E}_{\pi_{Y_{\mathcal{P}}}} \left[ D_{\text{KL}}(\pi_{{X|Y_{\mathcal{P}} }} \| \pi_{{X}} ) + D_{\text{KL}}(\pi_{{X}} \| \pi_{{X|Y_{\mathcal{P}} }} )\right]  =  \sum_j   \widehat{\sigma}_{j}.
\end{displaymath}
\end{proposition}

\begin{proof}  {\bfseries \Cref{prop:expSymKLDiv} }  \label{proof:prop_expSymKLDiv}
Since the prior and posterior are normal distributions, we can write the expected symmetrized KL divergence analytically,
\begin{multline} \label{eqn:expSymDKL}
	\mathbb{E}_{\pi_{Y_{\mathcal{P}}}} \left[ D^{sym}_{\text{KL}} (\pi_{X|Y_{\mathcal{P}}}, \pi_{X} ) \right]
     = \frac{1}{2} \Bigl( \tr{\Gamma_{X}^{-1}\Gamma_{X|Y_{\mathcal{P}}}}   +	\mathbb{E} \left[ \mu_{X|Y_{\mathcal{P}}}^{\top }\Gamma_{X}^{-1}\mu_{X|Y_{\mathcal{P}}} \right]  \\
      + \tr{\Gamma_{X|Y_{\mathcal{P}}}^{-1}\Gamma_{X}} +\mathbb{E}\left[ \mu_{X|Y_{\mathcal{P}}}^{\top }\Gamma_{X|Y_{\mathcal{P}}}^{-1}\mu_{X|Y_{\mathcal{P}}} \right] - 2n  \Bigr).
\end{multline}
Above we have assumed without any loss of generality that the prior has zero mean. The posterior mean $\mu_{X|Y_{\mathcal{P}}} \coloneqq  \Gamma_{X|Y_{\mathcal{P}}} G^{\top}_{\mathcal{P}} \Gamma_{Y_{\mathcal{P}}|X}^{-1} Y_{\mathcal{P}}$ is a function of the actual realization of data, unlike the covariance operator $\Gamma_{X|Y_{\mathcal{P}}}$ which is independent of data.

Simplifying the above expression is easier when we evaluate $\mathbb{E}_{\pi_{Y_{\mathcal{P}}}} \left[ \mu_{X|Y_{\mathcal{P}}} \mu_{X|Y_{\mathcal{P}}}^{\top } \right]$.
\begin{subequations}\begin{align}
	\mathbb{E}_{\pi_{Y_{\mathcal{P}}}} \left[ \mu_{X|Y_{\mathcal{P}}} \mu_{X|Y_{\mathcal{P}}}^{\top } \right]
	&= \Gamma_{X|Y_{\mathcal{P}}} G^{\top}_{\mathcal{P}} \Gamma_{Y_{\mathcal{P}}|X}^{-1}  \mathbb{E} \left[ Y_{\mathcal{P}} Y_{\mathcal{P}}^{\top} \right]  \Gamma_{Y_{\mathcal{P}}|X}^{-1} G_{\mathcal{P}} \Gamma_{X|Y_{\mathcal{P}}}, \\
	&\overset{(i)}{=}  \Gamma_{X|Y_{\mathcal{P}}} G^{\top}_{\mathcal{P}} \Gamma_{Y_{\mathcal{P}}|X}^{-1}  \lr{ \Gamma_{Y_{\mathcal{P}}|X}  + G_{\mathcal{P}} \Gamma_{X} G^{\top}_{\mathcal{P}}} \Gamma_{Y_{\mathcal{P}}|X}^{-1} G_{\mathcal{P}} \Gamma_{X|Y_{\mathcal{P}}}, \\
	&=  \Gamma_{X|Y_{\mathcal{P}}}  \lr{ \Gamma_{X}^{-1}  + G^{\top}_{\mathcal{P}} \Gamma_{Y_{\mathcal{P}}|X}^{-1} G_{\mathcal{P}}} \Gamma_{X} G^{\top}_{\mathcal{P}}\Gamma_{Y_{\mathcal{P}}|X}^{-1} G_{\mathcal{P}} \Gamma_{X|Y_{\mathcal{P}}}, \\
	&\overset{(ii)}{=}  \Gamma_{X|Y_{\mathcal{P}}}  \Gamma_{X|Y_{\mathcal{P}}}^{-1}  \Gamma_{X} \lr{ \Gamma_{X|Y_{\mathcal{P}}}^{-1} - \Gamma_{X} } \Gamma_{X|Y_{\mathcal{P}}}, \\
	&=   \Gamma_{X} - \Gamma_{X|Y_{\mathcal{P}}}.
\end{align} \end{subequations}
In the above set of equations, $(i)$ holds since $\Gamma_{Y_{\mathcal{P}}|X}  + G_{\mathcal{P}} \Gamma_{X} G^{\top}_{\mathcal{P}} = \mathbb{E}_{\pi_{Y_{\mathcal{P}}}} \left[ Y_{\mathcal{P}} Y_{\mathcal{P}}^{\top} \right] \eqqcolon  \Gamma_{Y_{\mathcal{P}}}$ is the marginal of the data, and $(ii)$ holds since $ \Gamma_{X}^{-1}  + G^{\top}_{\mathcal{P}} \Gamma_{Y_{\mathcal{P}}|X}^{-1} G_{\mathcal{P}} \eqqcolon  \Gamma_{X|Y_{\mathcal{P}}}^{-1}$ is the posterior precision.

Using the cyclic property of trace and linearity of the expectation operator it is now easy to see that,
\begin{align}
\label{eqn:expPostMeanPriorPrecision}\mathbb{E}_{\pi_{Y_{\mathcal{P}}}} \left[ \mu_{X|Y_{\mathcal{P}}}^{\top }\Gamma_{X}^{-1}\mu_{X|Y_{\mathcal{P}}} \right]
&= \tr{\Gamma_{X}^{-1} \lr{\Gamma_{X} - \Gamma_{X|Y_{\mathcal{P}}}}} = n - \tr{\Gamma_{X}^{-1}\Gamma_{X|Y_{\mathcal{P}}}} , \\
\label{eqn:expPostMeanPostPrecision} \mathbb{E}_{\pi_{Y_{\mathcal{P}}}} \left[ \mu_{X|Y_{\mathcal{P}}}^{\top }\Gamma_{X|Y_{\mathcal{P}}}^{-1}\mu_{X|Y_{\mathcal{P}}} \right]
&= \tr{\Gamma_{X|Y_{\mathcal{P}}}^{-1} \lr{\Gamma_{X} - \Gamma_{X|Y_{\mathcal{P}}}}} =  \tr{\Gamma_{X|Y_{\mathcal{P}}}^{-1} \Gamma_{X}} -n.
\end{align}

Using \cref{eqn:expPostMeanPriorPrecision} and \cref{eqn:expPostMeanPostPrecision} in \cref{eqn:expSymDKL} we have,
\begin{equation}
\mathbb{E}_{\pi_{Y_{\mathcal{P}}}} \left[ D^{sym}_{\text{KL}} (\pi_{X|Y_{\mathcal{P}}}, \pi_{X} ) \right]
=  \tr{\Gamma_{X|Y_{\mathcal{P}}}^{-1}\Gamma_{X}}  - n.
\end{equation}
The proof is completed by recognizing that $ \tr{\Gamma_{X|Y_{\mathcal{P}}}^{-1}\Gamma_{X}}$ is the sum of generalized eigenvalues of the definite pair $\lr{\Gamma_{X},\Gamma_{X|Y_{\mathcal{P}}}}$, which we know from \Cref{prop:eigen_prob_equivalence}  is $n + \sum_j \widehat{\sigma}_j $, where $\widehat{\sigma}_j$ are the generalized eigenvalues of the definite pair $(\Gamma_{X} - \Gamma_{X|Y_{\mathcal{P}} },\Gamma_{X|Y_{\mathcal{P}} })$ or equivalently $(\Gamma_{Y_{\mathcal{P}}} - \Gamma_{Y_{\mathcal{P}}|X},\Gamma_{Y_{\mathcal{P}}|X})$.

\end{proof}

\subsubsection{Bounds on sub/sup--modularity ratios}

We adapt an eigenvalue interlacing result for definite pairs which will be useful in proving \Cref{prop:bound_sup_sub_modularity_ratio}.
\begin{theorem}\textbf{\rm \bf (Cauchy Interlacing Theorem \cite{horn_johnson_2012,bhatia1997}, \cite[Theorem~2.3]{Kressner2014}, \cite[Theorem~2.1]{KovacStriko_Veselic_1995})}
\label{thm:cauchy_interlacing}
Let $A,B \in \mathbb{R}^{n \times n}$ with $A \succeq 0 ,B \succ 0$, and let $\gamma_1 \geq \gamma_2 \geq \cdots  \geq \gamma_{\widehat{n}} > 0, \ \widehat{n} \leq n$, be the eigenvalues of $(A,B)$.
For any $Z \in \mathbb{R}^{n \times p}$, with  $p \leq n$ and full column-rank, let $\mu_1 \geq \mu_2 \geq \cdots  \geq \mu_{\widehat{p}} > 0, \ \widehat{p} \leq p,$ be the eigenvalues of $(Z^{\top}AZ,Z^{\top}BZ)$. Then:
\begin{displaymath}
\gamma_{n-p+k}
\leq \mu_k
\leq \gamma_k , \qquad k = 1,\ldots,\widehat{p}.
\end{displaymath}
If additionally  $A \succ 0$, then $\widehat{n} = n$ and $\widehat{p} = p$.
\end{theorem}

\begin{proof}  {\bfseries \Cref{prop:bound_sup_sub_modularity_ratio}} \label{proof:prop_bound_sup_sub_modularity_ratio}
In \cite{Bian_etal_2017}  the authors provide a bound on the submodularity ratio for the Bayesian A-optimality design criterion. Our arguments use that proof as a template, but are modified to account for the mutual information design criterion. In addition we seek a bound for the supermodularity ratio, which intriguingly is the same.

In order to  bound the \emph{submodularity} ratio we need to lower bound,
\begin{displaymath}
	\frac{\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}} \rho_{\nu}(\mathscr{B})}{\rho_{\mathscr{A}} (\mathscr{B})} = \frac{\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}}  F(\nu \cup\mathscr{B}) -F(\mathscr{B})}{ F(\mathscr{A}\cup\mathscr{B}) -F(\mathscr{B})}, \qquad \forall \mathscr{A}, \mathscr{B} \subseteq \mathscr{V}.
\end{displaymath}
Similarly, in order to  bound the \emph{supermodularity} ratio we need to lower bound,
\begin{displaymath}
	\frac{\rho_{\mathscr{A}} (\mathscr{B})}{\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}} \rho_{\nu}(\mathscr{B})} = \frac{ F(\mathscr{A}\cup\mathscr{B}) -F(\mathscr{B})}{\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}}  F(\nu \cup\mathscr{B}) -F(\mathscr{B})}, \qquad \forall \mathscr{A}, \mathscr{B} \subseteq \mathscr{V}.
\end{displaymath}
It is clear that we can achieve the above tasks by finding lower and upper bounds for  $F(\mathscr{A}\cup\mathscr{B}) -F(\mathscr{B})$ and
$\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}}  F(\nu \cup\mathscr{B}) -F(\mathscr{B})$ respectively.

First we introduce some notation to aid the proof.  For any index set $\mathscr{A}$ with corresponding selection operator $\mathcal{P}_{\mathscr{A}}$, let $\zeta_j^{\mathscr{A}}$ represent the eigenvalue of the compressed pencil $\lr{\mathcal{P}_{\mathscr{A}}^{\top} \Gamma_Y \mathcal{P}_{\mathscr{A}}, \mathcal{P}_{\mathscr{A}}^{\top} \Gamma_{Y|X}\mathcal{P}_{\mathscr{A}}}$.
 $\zeta_j$ \emph{without any superscript} will continue to represent any eigenvalue of the pencil $\lr{\Gamma_Y, \Gamma_{Y|X}}$. Since we consider mutual information as the objective, $F(\mathscr{A})$ in terms of the eigenvalues $\zeta_j^{\mathscr{A}}$ is simply (\cref{eqn:mutualInfoGaussians_using_logDet,eqn:mutualInfoGaussians_reduced_data}),
\begin{equation}
	F(\mathscr{A}) = \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{A}}} \zeta_j^{\mathscr{A}}.
\end{equation}

We now state a simple corollary of \Cref{thm:cauchy_interlacing}. We omit the proof since it is quite trivial. For any two index sets $\mathscr{A}, \mathscr{B}$  we have,
\begin{equation} \label{eqn:corr_cauchy_interlacing}
	\zeta_j^{\mathscr{A} \cup \mathscr{B}} \geq \zeta_j^{\mathscr{B}} \geq \zeta^{\mathscr{A}  \cup \mathscr{B}}_{\abs{\mathscr{A} \cup \mathscr{B}} - \abs{\mathscr{B}} + j}, \qquad j=1,\ldots,\abs{\mathscr{B}}.
\end{equation}
As in \Cref{thm:cauchy_interlacing}, in the above statement we have ordered the eigenvalues such that $\zeta_1^{\mathscr{B}} \geq \cdots \geq \zeta_{\abs{\mathscr{B}}}^{\mathscr{B}}$ and $\zeta_1^{\mathscr{A} \cup \mathscr{B}} \geq \cdots \geq \zeta_{\abs{\mathscr{A} \cup \mathscr{B}}}^{\mathscr{A}\cup \mathscr{B}}$. This simple result proves handy in bounding $ F(\mathscr{A} \cup \mathscr{B}) -F(\mathscr{B})$.
\begin{subequations} \label{eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound1} \begin{align}
 F(\mathscr{A} \cup \mathscr{B}) -F(\mathscr{B})
 	&=  \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{A} \cup \mathscr{B}}}  \zeta_j^{\mathscr{A}  \cup\mathscr{B}} - \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{B}}} \zeta_j^{\mathscr{B}}, \\
 	&=  \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{A} \cup \mathscr{B}} - \abs{\mathscr{B}}} \zeta_j^{\mathscr{A}  \cup\mathscr{B}} + \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{B}}}  \frac{ \zeta_{\abs{\mathscr{A} \cup \mathscr{B}} - \abs{\mathscr{B}} + j}^{\mathscr{A}  \cup\mathscr{B}}}{\zeta_j^{\mathscr{B}}}, \\
 	&\leq \frac{1}{2}  \log \prod_{j=1}^{\abs{\mathscr{A} \setminus \mathscr{B}}} \zeta_j^{\mathscr{A}  \cup\mathscr{B}}, \quad \because \quad \text{\cref{eqn:corr_cauchy_interlacing}} \Rightarrow  \frac{ \zeta_{\abs{\mathscr{A} \cup \mathscr{B}} - \abs{\mathscr{B}} + j}^{\mathscr{A}  \cup\mathscr{B}}}{\zeta_j^{\mathscr{B}}} \leq 1, \\
 	&\leq \frac{1}{2} \log \lr{ \zeta_1^{\mathscr{A}  \cup\mathscr{B}} }^{\abs{\mathscr{A} \setminus \mathscr{B}}},  \quad \because \quad  \zeta_1^{\mathscr{A}  \cup\mathscr{B}} \geq  \zeta_j^{\mathscr{A}  \cup\mathscr{B}} \quad \forall j,   \\
 	&\leq \frac{\abs{\mathscr{A} \setminus \mathscr{B}}}{2} \log  \zeta_1^{\mathscr{A}  \cup\mathscr{B}}.
\end{align}  \end{subequations}
\begin{subequations} \label{eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound2} \begin{align}
 F(\mathscr{A} \cup \mathscr{B}) -F(\mathscr{B})
 	&=  \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{A} \cup \mathscr{B}} - \abs{\mathscr{B}}} \zeta_{\abs{\mathscr{B}} + j}^{\mathscr{A}  \cup\mathscr{B}} + \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{B}}}  \frac{ \zeta_{j}^{\mathscr{A}  \cup\mathscr{B}}}{\zeta_j^{\mathscr{B}}}, \\
 	&\geq \frac{1}{2}  \log \prod_{j=1}^{\abs{\mathscr{A} \setminus \mathscr{B}}} \zeta_{\abs{\mathscr{B}} + j}^{\mathscr{A}  \cup\mathscr{B}}, \quad \because \quad \text{\cref{eqn:corr_cauchy_interlacing}} \Rightarrow   \frac{ \zeta_{j}^{\mathscr{A}  \cup\mathscr{B}}}{\zeta_j^{\mathscr{B}}} \geq 1,  \\
 	&\geq \frac{1}{2} \log \lr{ \zeta_{\abs{\mathscr{A} \cup \mathscr{B}}}^{\mathscr{A}  \cup\mathscr{B}}}^{\abs{\mathscr{A}  \setminus \mathscr{B}}},  \quad \because \quad \zeta^{\mathscr{A}  \cup\mathscr{B}}_{\abs{\mathscr{A} \cup \mathscr{B}}} \leq \zeta^{\mathscr{A}  \cup\mathscr{B}}_{\abs{\mathscr{B}}+j} \quad \forall j, \\
 	&\geq \frac{\abs{\mathscr{A} \setminus \mathscr{B}}}{2} \log  \zeta_{\abs{\mathscr{A} \cup \mathscr{B}}}^{\mathscr{A}  \cup\mathscr{B}}.
\end{align}  \end{subequations}

Specializing  \cref{eqn:corr_cauchy_interlacing} to the case when the set $\mathscr{A}$ is a singleton set consisting of the element $\nu$ we have the following result,
\begin{equation} \label{eqn:corr_cauchy_interlacing_special_case}
	\zeta_j^{\nu \cup \mathscr{B}} \geq \zeta_j^{\mathscr{B}} \geq \zeta^{\nu \cup \mathscr{B}}_{j+1}, \qquad j=1,\ldots,\abs{\mathscr{B}}.
\end{equation}
Using \cref{eqn:corr_cauchy_interlacing_special_case}  we can bound the term $\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}}  F(\nu \cup\mathscr{B}) -F(\mathscr{B})$ using similar arguments as  in \cref{eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound1,eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound2}.
\begin{subequations} \label{eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound3} \begin{align}
	\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}}  F(\nu \cup\mathscr{B}) -F(\mathscr{B})
	&= \sum_{\nu \in \mathscr{A} \setminus \mathscr{B}} \lr{ \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{B}}+1} \zeta_j^{\nu \cup\mathscr{B}} - \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{B}}} \zeta_j^{\mathscr{B}} }, \\
	&= \sum_{\nu \in \mathscr{A} \setminus \mathscr{B}} \lr{ \frac{1}{2} \log  \zeta_{\abs{\mathscr{B}}+1}^{\nu \cup \mathscr{B}} +  \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{B}}} \frac{\zeta_j^{\nu \cup\mathscr{B}}}{\zeta_j^{\mathscr{B}} } }, \\
	&\geq   \frac{\abs{\mathscr{A} \setminus \mathscr{B}}}{2}  \log  \zeta_{\abs{\mathscr{B}}+1}^{\nu^{\dagger} \cup \mathscr{B}}, \quad \because \quad  \frac{\zeta_j^{\nu \cup\mathscr{B}}}{\zeta_j^{\mathscr{B}}} \geq 1,
\end{align}  \end{subequations}
where $\nu^{\dagger} = \argmin_{\nu \in \mathscr{A} \setminus \mathscr{B}}  \zeta_{\abs{\mathscr{B}}+1}^{\nu \cup \mathscr{B}}$.
\begin{subequations}  \label{eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound4} \begin{align}
	\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}}  F(\nu \cup\mathscr{B}) -F(\mathscr{B})
	&= \sum_{\nu \in \mathscr{A} \setminus \mathscr{B}} \lr{ \frac{1}{2} \log  \zeta_{1}^{\nu \cup \mathscr{B}} +  \frac{1}{2} \log \prod_{j=1}^{\abs{\mathscr{B}}} \frac{\zeta_{j+1}^{\nu \cup\mathscr{B}}}{\zeta_j^{\mathscr{B}} } }, \\
	&\leq   \frac{\abs{\mathscr{A} \setminus \mathscr{B}}}{2}  \log  \zeta_{1}^{\nu^{\ddagger} \cup \mathscr{B}},  \quad \because \quad  \frac{\zeta_{j+1}^{\nu \cup\mathscr{B}}}{\zeta_j^{\mathscr{B}}} \leq 1,
\end{align}  \end{subequations}
where $\nu^{\ddagger} = \argmax_{\nu \in \mathscr{A} \setminus \mathscr{B}}  \zeta_{1}^{\nu \cup \mathscr{B}}$.
Gathering the results from \cref{eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound1,eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound2,eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound3,eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound4} we have,
\begin{alignat}{2}
\label{eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound5}	 \frac{\abs{\mathscr{A} \setminus \mathscr{B}}}{2}  \log  \zeta_{\abs{\mathscr{B}}+1}^{\nu^{\dagger} \cup \mathscr{B}}
	& 	\leq  \sum_{\nu \in \mathscr{A} \setminus \mathscr{B}}  F(\nu \cup\mathscr{B}) -F(\mathscr{B})
	&& \leq \frac{\abs{\mathscr{A} \setminus \mathscr{B}}}{2}  \log  \zeta_{1}^{\nu^{\ddagger} \cup \mathscr{B}},\\
\label{eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound6}	 \frac{\abs{\mathscr{A} \setminus \mathscr{B}}}{2}  \log  \zeta_{\abs{\mathscr{A} \cup \mathscr{B}}}^{\mathscr{A}  \cup\mathscr{B}}
	&  \leq \quad  F(\mathscr{A} \cup \mathscr{B}) -F(\mathscr{B})
	&& \leq \frac{\abs{\mathscr{A} \setminus \mathscr{B}}}{2}  \log  \zeta_1^{\mathscr{A}  \cup\mathscr{B}} .
\end{alignat}

Using \cref{eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound5,eqn:prop_bound_sup_sub_modularity_ratio_helpful_bound6} we have,
\begin{equation}
	 \frac{\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}}  F(\nu \cup\mathscr{B}) -F(\mathscr{B})}{ F(\mathscr{A}\cup\mathscr{B}) -F(\mathscr{B})}
	 \geq \frac{ \log  \zeta_{\abs{\mathscr{B}}+1}^{\nu^{\dagger} \cup \mathscr{B}} }{\log  \zeta_1^{\mathscr{A}  \cup\mathscr{B}}} \geq \frac{\log \zeta_{\text{min}}}{\log \zeta_{\text{max}}}.
\end{equation}
\begin{equation}
	\frac{ F(\mathscr{A}\cup\mathscr{B}) -F(\mathscr{B})}{\sum_{\nu \in \mathscr{A} \setminus \mathscr{B}}  F(\nu \cup\mathscr{B}) -F(\mathscr{B})}
    \geq \frac{\log  \zeta_{\abs{\mathscr{A} \cup \mathscr{B}}}^{\mathscr{A}  \cup\mathscr{B}} }{\log  \zeta_{1}^{\nu^{\ddagger} \cup \mathscr{B}}} \geq  \frac{\log \zeta_{\text{min}}}{\log \zeta_{\text{max}}}.
\end{equation}
\end{proof}

\iffalse
We state few facts about normally distributed random variables and their properties without proof. We shall use these multiple times in our arguments. Each of the facts can be easily verified from first principles.

\begin{property}\label{fact:conditionalLinearTransformedGaussian}
For any normally distributed random variables $X$ and $Y$ with  covariance operators $\Gamma_X \in \mathbb{R}^{n \times n}$ and $\Gamma_Y \in \mathbb{R}^{m \times m}$ respectively; and for any linear operator $Z \in \mathbb{R}^{m \times p}$ with full column-rank,  the conditional covariance operator of $Z^{\top} Y | X \eqqcolon  \Gamma_{Y_{Z} | X} = Z^{\top} \Gamma_{Y|X} Z$.
\end{property}

\begin{property}\label{fact:entropyLinearTransformedGaussian}
For any normally distributed random variable $X$ with  covariance operator $\Gamma_X \in \mathbb{R}^{n \times n}$, and for any linear operator $W \in \mathbb{R}^{n \times p}$ with full column-rank, the  entropy of  $W^{\top} X$, $H(W^{\top} X) = \frac{1}{2}\log \det ( W^{\top} \Gamma_{X}  W) +  \frac{n}{2} \log(2 \pi e)$.
\end{property}

\begin{property}\label{fact:conditionalEntropyGaussians}
For any zero mean, normally distributed random variables $X$ and $Y$, with respective covariance operators $\Gamma_X \in \mathbb{R}^{n \times n}$ and $\Gamma_Y \in \mathbb{R}^{m \times m}$, the conditional entropy $H(Y|X) = \frac{1}{2}\log (\det (\Gamma_{Y|X}) +  \frac{m}{2} \log(2 \pi e)$, where $\Gamma_{Y|X} \in \mathbb{R}^{m \times m}$ is the conditional covariance operator of $Y | X$
\end{property}

\begin{property}\label{fact:KLDivGaussians}
The relative entropy or Kullback--Leibler divergence between the densities of two multivariate normal distributions $\pi, \widehat{\pi}$ in $\mathbb{R}^{n}$, with means $\mu, \widehat{\mu}$, and (nonsingular) covariance matrices $\Gamma,  \widehat{\Gamma}$ is as follows,
\begin{displaymath}
	D_{\text{KL}}(  \pi \|  \widehat{\pi}   ) = \frac{1}{2} \lr{ \log { \frac{\det \widehat{\Gamma}}{ \det \Gamma} + \tr{ \widehat{\Gamma}^{-1} \Gamma}+\left(\widehat{\mu}-\mu\right)^{\top }\widehat{\Gamma}^{-1}(\widehat{\mu}-\mu) -n}}.
\end{displaymath}
\end{property}

\begin{property}\label{fact:mutualInfoGaussians}
For any zero mean, normally distributed random variables $X$ and $Y$, with respective covariance operators $\Gamma_X \in \mathbb{R}^{n \times n}$ and $\Gamma_Y \in \mathbb{R}^{m \times m}$, the mutual information between them $\mathcal{I}(X;Y)$ or equivalently $\mathcal{I}(Y;X)$ can be written as,
\begin{displaymath}
\mathcal{I}(X;Y) = \mathcal{I}(Y;X) = \frac{1}{2}\log { \frac{\det (\Gamma_{Y})}{\det (\Gamma_{Y|X})}} = \frac{1}{2}\log { \frac{\det (\Gamma_{X})}{\det (\Gamma_{X|Y})}}.
\end{displaymath}
Here $\Gamma_{Y|X} \in \mathbb{R}^{m \times m}$ is the conditional covariance operator of $Y | X$, and $\Gamma_{X|Y} \in \mathbb{R}^{n \times n}$ is the conditional covariance operator of $ X|Y$.
\end{property}

\fi

\subsection{Proofs concerning MM algorithms for linear Bayesian experimental design} \label{appendix_subsec:lbip_mm}

This subsection is devoted to proving \Cref{prop:MBound_MI} and its corollaries.  We begin by stating certain standard results in linear algebra, subsequently deducing useful corollaries, and some helpful lemmas from them, all of which contribute to the argument of the main result.

\begin{theorem} [Hadamard's inequality \cite{horn_johnson_2012}] \label{thm:hadamard_inequality} Let $A \in \mathbb{R}^{m \times m}$ be any positive definite Hermitian matrix, with $a_{ij}$ representing its individual entries. Then,
\begin{displaymath}
	\det A \leq a_{11} \cdots a_{mm}
\end{displaymath}
\end{theorem}
\begin{corollary} \label{corr:logDetInequality_hadamard}  Let $A \in \mathbb{R}^{m \times m}$ be any positive definite Hermitian matrix, and $\mathcal{P} \in  \mathbb{R}^{m \times k}, k < m$ be a selection operator (\Cref{def:selectionOperator}), then:
\begin{displaymath}
	\log \lr{ \det \lr{ \mathcal{P}^{\top} A \mathcal{P}}} \leq  \tr{\mathcal{P}^{\top} \log \lr{\mathrm{diag}\lr{A}}  \mathcal{P}}
\end{displaymath}
\end{corollary}
\begin{proof_without_of_suffix}
The corollary follows immediately from \Cref{thm:hadamard_inequality}.
\end{proof_without_of_suffix}
\begin{remark} The $\log \det$ of a principal submatrix is a submodular function with respect to the indices defining the submatrices \cite{Gantmacher_Krein_1960,Kotelyanskii_1950,Fan_1967,Fan_1968,Kelmans_1983,Johnson_1985}. We know that submodularity implies subadditivity for nonnegative functions, thus the modular upper bound in the statement of \Cref{corr:logDetInequality_hadamard} can be understood in that sense as well.
\end{remark}

\begin{theorem} [Operator concave inequality \cite{Chandler_1957,Hansen1980,HansenPedersen1982,hansen_pedersen_2003,Bourin_2006}] \label{thm:operator_concave_inequality}
Let $A$ be any Hermitian operator defined on a Hilbert space, and $K$ be an isometry on a subspace of the Hilbert space. Denote    the compression of $A$ by $K$ as $K^{*} A K$, then for any operator concave function $\phi(\cdot)$ we have that,
\begin{displaymath}
 K^{*} \phi(A) K	 \preceq \phi (K^{*} A K)
\end{displaymath}
\end{theorem}

\begin{theorem} [Matrix versions of the Cauchy and Kantorovich inequalities \cite{Marshall_Olkin_1990,MondPecaric1994,Bourin_2005}] \label{thm:Cauchy_Kantorovich_inequality} Let $A \in \mathbb{R}^{m \times m}$ be any positive definite Hermitian matrix, with eigenvalues contained in the interval $[\lambda_{s},\lambda_{l}] \subset \mathbb{R}_{> 0}$. If $K$ is an isometry then:
\begin{displaymath}
\frac{4 \lambda_{s} \lambda_{l}}{\lr{\lambda_{s} + \lambda_{l}}^{2}}  K^{*} A^{-1} K
\preceq \lr{K^{*} A K}^{-1}
\preceq  K^{*} A^{-1} K
\end{displaymath}
\end{theorem}
As pointed out in \cite{Marshall_Olkin_1990}, if $K$ is merely a selection operator, then the upper bound of \Cref{thm:Cauchy_Kantorovich_inequality} reduces to a standard result in linear algebra, first established in \cite{Chollet_1982} and now a common theorem in texts \cite[Theorem 7.7.15.]{horn_johnson_2012}; the inverse of a principal submatrix of any definite matrix is less than or equal to the corresponding submatrix of the inverse.

\begin{corollary} \label{corr:logDetInequality} Let $A \in \mathbb{R}^{m \times m}$ be any positive definite Hermitian matrix with an eigenvalue interval $[\lambda_{s},\lambda_{l}]$ as prescribed in \Cref{thm:Cauchy_Kantorovich_inequality}. Define the scalar parameter $\varrho \coloneqq  \frac{4 \lambda_{s} \lambda_{l}}{\lr{\lambda_{s} + \lambda_{l}}^{2}}$. If $K \in  \mathbb{R}^{m \times k}, k < m$ is an isometry, $K^{*}K = I_{k}$, then:
\begin{displaymath}
 \tr{ K^{*} \log \lr{ A} K} \leq \log \det \lr{K^{*} A K} \leq  \tr{ K^{*} \lr{ \log \lr{A} - I_{m}\log\lr{\varrho} } K}
\end{displaymath}
\end{corollary}
\begin{proof} {\bfseries \Cref{corr:logDetInequality}} \label{proof:corr_logDetInequality}
Since $A \succ 0$, its compression by $K$, $K^{*} A K \succ 0$. Hence we have the identity $\tr{\log \lr{K^{*} A K}} =  \log \det \lr{K^{*} A K}$. Since $\log$ is a concave function, we claim using \Cref{thm:operator_concave_inequality} $\log \lr{K^{*} A K} \succeq K^{*} \log \lr{ A} K$, and this implies the lower bound.

To prove the upper bound, we begin by using the identity
\begin{equation}
	\log \det \lr{K^{*} A K} = -\log \det \lr{K^{*} A K}^{-1}  = -\tr{ \log  \lr{K^{*} A K}^{-1}}.
\end{equation}
Using the lower bound in \Cref{thm:Cauchy_Kantorovich_inequality} we have,
\begin{align}
 \log \det \lr{ \varrho K^{*} A^{-1} K} &\leq \log \det\lr{K^{*} A K}^{-1}.\\
  \label{eqn:upper_bound_proof_1}
\Rightarrow	-\tr{\log  \lr{K^{*} A K}^{-1}}   &\leq     -\tr{\log \lr{ K^{*} A^{-1} K}} - \tr{I_{k} \log\lr{\varrho}}.
\end{align}
 $ K^{*} A^{-1} K$ is a compression by $K$ of $A^{-1} \succ 0$. Using  \Cref{thm:operator_concave_inequality} we claim,
 \begin{equation}
 			 \log \lr{K^{*} A^{-1} K}  \succeq K^{*} \log \lr{A^{-1}} K = -K^{*} \log \lr{A} K.
 \end{equation}
	\begin{equation} \label{eqn:upper_bound_proof_2}
\Rightarrow -\tr{\log \lr{K^{*} A^{-1} K}}  \leq \tr{K^{*} \log \lr{A} K}.
	\end{equation}
Using \cref{eqn:upper_bound_proof_2} in \cref{eqn:upper_bound_proof_1} we have,
 \begin{equation}
	-\tr{\log  \lr{K^{*} A K}^{-1}}   \leq     \tr{K^{*} \log \lr{A} K} - \tr{I_{k} \log\lr{\varrho}}.
 \end{equation}
The upper bound in the corollary statement is now immediately obtained by  linearity of the trace operator and the isometry property of $K$.
\end{proof}

\begin{proof} {\bfseries \Cref{prop:MBound_MI}} \label{proof:prop_MBound_MI}
Equation \cref{eqn:mutualInfoGaussians_reduced_data} provides an expression for the mutual information $\mathcal{I}(  X;Y_{\mathcal{P}})$,
\begin{displaymath}
	   \mathcal{I}(  X; Y_{\mathcal{P}})  =  \frac{1}{2} \log \lr{ \frac{\det \lr{ \mathcal{P}^{\top} \Gamma_{Y}  \mathcal{P}}}{\det \lr{ \mathcal{P}^{\top}\Gamma_{Y|X}  \mathcal{P}}} }.
\end{displaymath}
The proposition statement and the alternative modular bounds in \cref{eqn:alt_MBound_MI} are easily obtained by using \Cref{corr:logDetInequality_hadamard,corr:logDetInequality} on the two $\log\det$ terms.

\end{proof}

\begin{proof} {\bfseries \Cref{corr:MI_deviation_from_SM}} \label{proof:corr_MI_deviation_from_SM}
\Cref{eqn:corr_MI_deviation_from_SM_eq1} is simply a restatement of the lower bound in  \Cref{prop:MBound_MI}. The equivalence between \cref{eqn:corr_MI_deviation_from_SM_eq1} and \cref{eqn:corr_MI_deviation_from_SM_eq2} is trivial. Rewriting \cref{eqn:corr_MI_deviation_from_SM_eq2} with $Y \setminus Y_\mathcal{P}$ as the argument, and subtracting that term from $\mathcal{I}(  X;Y)$ we obtain  \cref{eqn:corr_MI_deviation_from_SM_eq1}. In a similar way we can obtain  \cref{eqn:corr_MI_deviation_from_SM_eq2} from  \cref{eqn:corr_MI_deviation_from_SM_eq1}.

\end{proof}

\begin{proof} {\bfseries \Cref{corr:MI_SM_case_bounding_BP} } \label{proof:corr_MI_SM_case_bounding_BP}
If $Y_{i_k} | X$ are independent, then we know $\Gamma_{Y|X}$ is diagonal, and hence $\log \mathrm{diag} \lr{\Gamma_{Y|X}} = \log \lr{\Gamma_{Y|X}}$. Thus the corollary statement is apparent as a consequence  of \Cref{corr:MI_deviation_from_SM}.
\end{proof}

\begin{proof} {\bfseries \Cref{prop:min_MI_loss_upper_bound}} \label{proof:prop_min_MI_loss_upper_bound}
Observe that
\begin{equation}
		\mathcal{I}(X;Y \setminus Y_{\mathcal{P}} |Y_{\mathcal{P}_1}) - \mathcal{I}(X;Y \setminus Y_{\mathcal{P}}, Y_{\mathcal{P}_1})
	=
	\mathcal{I}(Y_{\mathcal{P}_1}; Y \setminus Y_{\mathcal{P}},Y_{\mathcal{P}_1} |X) - \mathcal{I}(Y_{\mathcal{P}_1};Y \setminus Y_{\mathcal{P}},Y_{\mathcal{P}_1}).
\end{equation}
This implies
\begin{equation} \label{eqn:proof_prop_min_MI_loss_upper_bound_1}
   \mathcal{I}(X;Y \setminus Y_{\mathcal{P}} |Y_{\mathcal{P}_1}) 	-\mathcal{I}(X;Y \setminus Y_{\mathcal{P}}, Y_{\mathcal{P}_1})  \leq  \mathcal{I}(Y_{\mathcal{P}_1}; Y \setminus Y_{\mathcal{P}},Y_{\mathcal{P}_1} |X).
\end{equation}
Using \cref{eqn:proof_prop_min_MI_loss_upper_bound_1}, we have
\begin{equation}
 \mathcal{I}(X;Y|Y_{\mathcal{P}_1}) - \mathcal{I}(X;Y \setminus Y_{\mathcal{P}_1}, Y_{\mathcal{P}})  \leq
  \mathcal{I}(X;Y|Y_{\mathcal{P}_1}) - \mathcal{I}(X;Y \setminus Y_{\mathcal{P}} | Y_{\mathcal{P}_1}) + \mathcal{I}(Y_{\mathcal{P}_1}; Y \setminus Y_{\mathcal{P}},Y_{\mathcal{P}_1} |X).
\end{equation}
Consider the term $\mathcal{I}(X;Y|Y_{\mathcal{P}_1}) - \mathcal{I}(X;Y \setminus Y_{\mathcal{P}} | Y_{\mathcal{P}_1})$; adapting the result in \Cref{corr:MI_deviation_from_SM} we have the following bound:
\begin{align} \label{eqn:proof_prop_min_MI_loss_upper_bound_2}
	  \mathcal{I}(X;Y|Y_{\mathcal{P}_1}) - \mathcal{I}(X;Y \setminus Y_{\mathcal{P}} | Y_{\mathcal{P}_1})
\nonumber	  & \leq \tr{ \widehat{\mathcal{P}}^{\top} \lr{ \log \lr{\Gamma_{Y|Y_{\mathcal{P}_1}}} - \log \lr{\Gamma_{Y|X,Y_{\mathcal{P}_1}}} }\widehat{\mathcal{P}}} \\
& \quad +  \tr{ \widehat{\mathcal{P}}^{c}{}^{\top} \lr{ \log \mathrm{diag} \lr{\Gamma_{Y|X,Y_{\mathcal{P}_1}}} - \log \lr{\Gamma_{Y|X,Y_{\mathcal{P}_1}}} }\widehat{\mathcal{P}}^{c}} .
\end{align}
Now consider the term $ \mathcal{I}(Y_{\mathcal{P}_1}; Y \setminus Y_{\mathcal{P}},Y_{\mathcal{P}_1} |X)$. Using \Cref{corr:logDetInequality_hadamard,corr:logDetInequality} we have the following bound:
\begin{align} \label{eqn:proof_prop_min_MI_loss_upper_bound_3}
 \mathcal{I}(Y_{\mathcal{P}_1}; Y \setminus Y_{\mathcal{P}},Y_{\mathcal{P}_1} |X) \leq  \tr{ \widehat{\mathcal{P}}^{c}{}^{\top} \lr{ \log \mathrm{diag} \lr{\Gamma_{Y \setminus Y_{\mathcal{P}_1}|X}} - \log \lr{\Gamma_{Y|X,Y_{\mathcal{P}_1}}} }\widehat{\mathcal{P}}^{c}}.
\end{align}
Adding \cref{eqn:proof_prop_min_MI_loss_upper_bound_1,eqn:proof_prop_min_MI_loss_upper_bound_2}, we get the proposition statement.
\end{proof}

\iffalse

\subsection{Miscellaneous proofs}

\begin{lemma}\label{lemma:trace_inequality}
Let  $A,B \in \mathbb{R}^{m \times m}$, with $A\succeq 0$, and $B \succ 0$.  Let $\Sigma$ be the diagonal matrix of eigenvalues of the definite pair $(A,B)$. For any isometry $K \in  \mathbb{R}^{m \times k}, k < m, K^{*}K = I_{k}$, define the compressed definite pair $(K^{*} A K,K^{*} B K )$ and let $\widehat{\Sigma}$ be its corresponding diagonal matrix of eigenvalues. Then
\begin{displaymath}
\tr{\widehat{\Sigma}}
\leq  \tr{ K^{*} B^{-\frac{1}{2}} A B^{-\frac{1}{2}} K}
\leq  \tr{\Sigma}
\end{displaymath}
The equality for the lower bound holds if $B$ is diagonal.
\end{lemma}
\begin{proof} \label{proof:lemma_trace_inequality}
Using the upper bound in \Cref{thm:Cauchy_Kantorovich_inequality}, we claim
\begin{equation} \label{eqn:inverse_subMatrix_partial_order}
 (K^{*} B K)^{-1} \preceq K^{*} B^{-1} K
\end{equation}
The partial ordering of semi-definite matrices is preserved under the appropriate left and right application of any operator not necessarily full-rank \cite[Theorem~7.7.2]{horn_johnson_2012}. Choosing $K$ as the operator and using the ordering given by  \cref{eqn:inverse_subMatrix_partial_order} we have,
\begin{equation}
K\lr{K^{*} B K}^{-1} K^{*} \preceq K \lr{K^{*} B^{-1} K} K^{*}
\end{equation}
We note that $B^{- \frac{1}{2}} K K^{*} B^{- \frac{1}{2}} $ and $K (K B^{-1} K^{*}) K^{*}$ have the same eigen-spectrum \cite[Theorem~1.3.22]{horn_johnson_2012}, hence
\begin{equation}
K \lr{K^{*} B K}^{-1} K^{*} \preceq B^{- \frac{1}{2}} K K^{*} B^{- \frac{1}{2}}.
\end{equation}
Since $A\succeq 0$ we now claim
\begin{equation}
\tr{A K \lr{K^{*} B K}^{-1} K^{*}} \leq  \tr{A  B^{- \frac{1}{2}} K K^{*} B^{- \frac{1}{2}}} .
\end{equation}
Using the cyclic property of the trace operator we can rearrange terms to obtain
\begin{equation}
\tr{K^{*} A K \lr{K^{*} B K}^{-1}} \leq \tr{K^{*} B^{- \frac{1}{2}} A  B^{- \frac{1}{2}} K}.
\end{equation}
Since $K K^{*} \preceq I_{m}$ and $B^{- \frac{1}{2}} A  B^{- \frac{1}{2}} \succ 0$, we can claim
\begin{equation}
\tr{K^{*} B^{- \frac{1}{2}} A  B^{- \frac{1}{2}} K} \leq \tr{ A  B^{-1}}.
\end{equation}
Combining the previous two inequalities we have
\begin{equation}
\tr{K^{*} A K \lr{K^{*} B K}^{-1} }
\leq \tr{K^{*} B^{- \frac{1}{2}} A  B^{- \frac{1}{2}} K}
\leq \tr{ A  B^{-1}}.
\end{equation}
We know $\tr{\widehat{\Sigma}} = \tr{K^{*} A K \lr{K^{*} B K}^{-1} }$ and $\tr{\Sigma} = \tr{ A  B^{-1}}$, which completes the proof for the main statement of the theorem. The equality in the lower bound for the case of $B$ being diagonal stems from \Cref{thm:Cauchy_Kantorovich_inequality} being redundant in such a scenario, since $ (K^{*} B K)^{-1} = K^{*} B^{-1} K$
\end{proof}

\begin{proof} {\bfseries \Cref{prop:MI_MBound_noLog} } \label{proof:prop_MI_MBound_noLog}
To obtain the modular upper bound we recall \cref{eqn:mutualInfoGaussians_reduced_data} again, where we had derived an expression for the mutual information $\mathcal{I}(  X;\mathcal{P}^{\top} Y)$ in terms of the generalized eigenvalues $\widehat{\sigma}_{k}$,
\begin{displaymath}
\mathcal{I}\lr{X;Y_{\mathcal{P}}}  \leq \frac{1}{2} \sum_{k} \widehat{\sigma}_{k}.
\end{displaymath}
Here $\widehat{\sigma}_{k}$ are the generalized eigenvalues of the definite pair $\lr{ \Gamma_{Y_{\mathcal{P}}} - \Gamma_{Y_{\mathcal{P}}|X}, \Gamma_{Y_{\mathcal{P}}|X}}$. Using a standard logarithmic inequality we claim $ \mathcal{I}\lr{X;Y_{\mathcal{P}}}  \leq \frac{1}{2} \sum_{k} \widehat{\sigma}_{k}$. The trace of the eigenvalues is further bounded by the desired term in the theorem statement owing to \Cref{lemma:trace_inequality}.
\begin{equation}
  \mathcal{I}\lr{X;Y_{\mathcal{P}}}  \leq \frac{1}{2} \sum_{k} \widehat{\sigma}_{k}.
\end{equation}
\end{proof}

\fi