# Iso-entangled bases and joint measurements

Flavio Del Santo  Group of Applied Physics, University of Geneva, 1211 Geneva
4, Switzerland  Constructor University, Geneva, Switzerland  Jakub Czartowski
Doctoral School of Exact and Natural Sciences, Jagiellonian University, ul.
Łojasiewicza 11, 30-348 Kraków, Poland  Faculty of Physics, Astronomy and
Applied Computer Science, Jagiellonian University, ul. Łojasiewicza 11, 30-348
Kraków, Poland  Karol Życzkowski  Faculty of Physics, Astronomy and Applied
Computer Science, Jagiellonian University, ul. Łojasiewicza 11, 30-348 Kraków,
Poland  Center of Theoretical Physics, Polish Academy of Sciences, al.
Lotników 32/46 02-668 Warszawa  Nicolas Gisin  Group of Applied Physics,
University of Geneva, 1211 Geneva 4, Switzerland  Constructor University,
Geneva, Switzerland

###### Abstract

While entanglement between distant parties has been extensively studied,
entangled measurements have received relatively little attention despite their
significance in understanding non-locality and their central role in quantum
computation and networks. We present a systematic study of entangled
measurements, providing a complete classification of all equivalence classes
of iso-entangled bases for projective joint measurements on 2 qubits. The
application of this classification to the triangular network reveals that the
Elegant Joint Measurement, along with white noise, is the only measurement
resulting in output permutation invariant probability distributions when the
nodes are connected by Werner states. The paper concludes with a discussion of
partial results in higher dimensions.

##  I Introduction

In 1935, Schrödinger stated that entanglement is not one but rather the
characteristic trait of quantum mechanics. Indeed, today it is well known that
entanglement is not only necessary for the violation of celebrated Bell
inequalities—disproving local hidden variables—but for most of the
applications in quantum information science such as security proofs of quantum
cryptography or quantum teleportation, to name but a few examples.

Entanglement is sometimes called the “quantum teleportation channel”. However,
this overlooks the fact that entanglement plays a dual role in this
fascinating process: first as the channel connecting the distant parties,
indeed, but also in the joint measurement that triggers the teleportation
process [1]. Similarly, these joint measurements are at the heart of
entanglement swapping [2] and dense coding [3]. Formally, they are represented
in quantum theory by self-adjoint operators which in turn are characterized by
their eigenvectors. When these eigenvectors are entangled, one says that the
measurement is entangled. For example, in the best known joint measurement,
the eigenvectors are the Bell states which are all maximally entangled.

Entanglement between distant parties, traditionally named Alice and Bob, is by
now well-studied and understood. However, entangled measurements received so
far relatively little attention [4, 5] and have never been studied in a
systematic manner. This is somewhat surprising and disappointing, given their
central role in quantum computation [6] and quantum networks [7]. In fact, it
has been recently pointed out that understanding entangled measurements is one
of the most interesting future directions in the foundations of quantum
physics [8].

Studying entanglement beyond maximal value can lead to novel understanding and
applications. Indeed, it is known by now that maximally entangled states are
not always the best resource for quantum information tasks: non-maximally
entangled quantum states in general outperform maximally entangled ones in
most measures of non-locality, such as Bell inequalities, entanglement
simulation with communication, the detection loophole and quantum cryptography
[9, 10]. While this has not been investigated nearly as thoroughly for joint
measurements, it has been shown that non-maximally entangled measurements
represent stronger resources for certain tasks, such as the violation of
bilocality [11].

In this paper, we provide the first systematic study of entangled measurements
for the simplest case. The problem is known to be difficult in full
generality, hence we assume that all the eigenvectors have the same degree of
entanglement, i.e., they form an iso-entangled basis (previous works on non-
maximally entangled joint measurements and iso-entangled bases are [12, 13,
14, 11, 15, 16, 17]). Moreover, we mostly limit our analysis to projective
joint measurements on 2 qubits.

Here, we give a complete classification of all iso-entangled bases of 2
qubits, up to the natural equivalence relation of local unitary rotations and
swapping of the qubits. Next, we apply our parametrization to the triangular
network and prove that the Elegant Joint Measurement (and white noise) is the
only measurement that leads to output permutation invariant probability
distributions when the nodes are connected by identical Werner states.
Finally, we discuss partial results in higher dimensions.

##  II Complete classification of all equivalence classes of iso-entangled
bases of 2 qubits

Consider measurements on two qubits, i.e., the partition of the Hilbert space
${\cal C}^{4}={\cal C}^{2}\otimes{\cal C}^{2}$ is fixed. An iso-entangled
basis is an orthonormal basis s.t. all 4 vectors $\ket{\psi_{j}}$, $j=1,\dots
4$, have the same degree of entanglement.

There are many measures of entanglement, but for pure bipartite states
$\rho_{AB}=\ket{\psi}\bra{\psi}_{AB}$ they are all equivalent [18]. We
quantify the degree of entanglement by its tangle, equal to squared
concurrence [19, 20, 21]

$\xi=2\left(1-\textrm{Tr}(\rho_{A}^{2})\right)\in[0,1],$ (1)

where $\rho_{A}=\textrm{Tr}_{B}(\rho_{AB})$ is the reduced density matrix;
this monotonically quantifies entanglement from 0 (separable states) to 1
(maximally entangled states).

Defintion 1 (Local equivalence of bases) Let us define the equivalence
relation $\sim$ : two bases $B_{1}$ and $B_{2}$ are equivalent iff they are
identical under local unitaries, $U_{i}$ (equivalently, local changes of
basis), or identical under swap $S_{A\leftrightarrow B}$ and local unitaries,
i.e.

$B_{1}\sim B_{2}\Leftrightarrow B_{2}=(U_{A}\otimes U_{B})(\cdot)B_{1}P,$ (2)

with $(\cdot)\in\\{\mathds{1},\textrm{S}_{A\leftrightarrow B}\\}$ and $P$ an
arbitrary permutation.

Our goal is to find a parametrization of each family of equivalence classes.
Starting with 12 real parameters for an arbitrary dephased orthonormal basis
of ${\cal C}^{4}$, we subtract $3+3$ parameters for local changes of bases,
and the 3 constraints that all 4 vectors have the same degree of entanglement.
We thus expect an iso-entangled basis of two-qubits to depend in general on 3
parameters.

Our main result consists in the following proposition:

Proposition 1 (Complete classification of iso-entangled bases of 2 qubits) All
equivalence classes of iso-entangled bases on the space $C$ with respect to
the relation (2) constitute a three-dimensional manifold composed of two
families, together with the closure of discontinuous submanifolds, given by
three additional families of equivalence classes of smaller dimension. The
specific functional form of the families is provided in Eq. (35) for the
general family, (28) for the Bell family, and in Eqs. (17), (22) for the
families of smaller dimensions.

###  II.1 Constructive proof

Let $B$ be a matrix of order 4 whose columns are 4 basis vectors
$\\{\ket{\psi_{1}},\ket{\psi_{2}},\ket{\psi_{3}},\ket{\psi_{4}}\\}$ in ${\cal
C}^{4}={\cal C}^{2}\otimes{\cal C}^{2}$. Let us write $B$ in the following
skewed basis (by applying local change of basis only), consisting only of
product states, but in general different from the computational basis:

$\ket{0,0},\ket{0,1},\ket{1,\varphi},\ket{1,\varphi^{\perp}},$ (3)

where $\ket{\varphi}=\cos(\tau)\ket{0}+\sin(\tau)\ket{1}$ and
$\ket{\varphi^{\perp}}=\cos(\tau)\ket{1}-\sin(\tau)\ket{0}$. To simplify the
derivation, we use the fact that any 2-dimensional subspace of ${\cal C}^{4}$
contains at least one product state [22]. Imposing the orthonormality leads to
the following parametrization of an arbitrary equivalence class of 2-qubit
orthonormal bases (for derivation see SM, section A):

$\displaystyle B_{\ket{\varphi}}=\left(\begin{array}[]{cccc}0&0&-c\alpha\cdot
e^{i\gamma}&s\alpha\cdot e^{i\gamma}\\\ s\delta\cdot c\theta&c\delta\cdot
c\theta&-s\alpha\cdot s\theta&-c\alpha\cdot s\theta\\\ s\delta\cdot
s\theta&c\delta\cdot s\theta&s\alpha\cdot c\theta&c\alpha\cdot c\theta\\\
-c\delta\cdot e^{i\beta}&s\delta\cdot e^{i\beta}&0&0\end{array}\right),$ (8)

where we have introduced the compact notation $c\delta=\cos{\delta}$,
$s\delta=\sin\delta$ and similarly for $c\alpha$ and $s\alpha$, and $c\theta$
and $s\theta$. The subscript $\ket{\varphi}$ indicates that the coefficients
are expressed in the basis provided in Eq. (3). As expected, this
parametrization has 6 parameters: $\alpha,\delta,\theta,\gamma,\beta$ and
$\tau$ (with $\tau$ included implicitly in skewed basis (3)).

By computing the tangle $\xi_{j}$ (Eq. (1)) for each state $\ket{\psi_{j}}$ of
$B$, we can now impose the constraints of iso-entanglement:

$\xi_{i}=\xi_{j},\ \ \ \forall i,j\in\\{1,2,3,4\\}.$ (9)

Note that only 3 of these equations are independent, thus solving these
constraints will lead to a parametrization depending on $6-3=3$ parameters.
The previous equations yield the following complete set of solutions:

  * (i)

$\cos\theta=0$, or

  * (ii)

$\sin 2\theta\neq 0$, and
$\sin\tau=0\implies\alpha=\frac{\pi}{4}=\pm\delta+\frac{l\pi}{2}$, or

  * (iii.a)

$\sin\theta=0$, and $\sin\tau\neq 0\implies\alpha=\pm\delta+\frac{k\pi}{2}$,
or

  * (iii.b)

$\cos\tau=0\implies\alpha=\pm\delta+\frac{m\pi}{2}$, or

  * (iv)

$\cos\theta\neq 0$, and $\sin\theta\neq 0$, and $\cos\tau\neq 0$, and
$\sin\tau\neq 0$, and $\sin(2\delta)\neq 0$, and $\sin(2\alpha)\neq
0\implies\alpha=\pm\delta+\frac{n\pi}{2}$.

As we shall see, the first solution ($\cos\theta=0$) is somehow trivial, for
it leads to all four basis states to be separable. All the other solutions
imply that $\alpha=\pm\delta$ (omitting here the periodicity of $\pi/2$). This
condition can thus be substituted in (three of) the equations (9), leading to
the following simplified expressions for the iso-entanglement conditions:

$\displaystyle 0=\xi_{1}-\xi_{2}$ $\displaystyle=$
$\displaystyle-8\cos^{2}\theta\sin\theta\cos\tau\cdot$
$\displaystyle\cdot\bigl{(}\cos\tau\sin\theta\cos(2\delta)-\sin\tau\sin(2\delta)\cos\beta\bigr{)}$
$\displaystyle 0=\xi_{3}-\xi_{4}$ $\displaystyle=$
$\displaystyle-8\cos^{2}\theta\sin\theta\cos\tau\cdot$
$\displaystyle\cdot\bigl{(}\cos\tau\sin\theta\cos(2\delta)+\sin\tau\sin(2\delta)\cos\gamma\bigr{)}$
$\displaystyle 0=\xi_{1}-\xi_{3}$ $\displaystyle=$ $\displaystyle
8\cos^{2}\theta\sin\theta\cos\tau\cdot$
$\displaystyle\cdot\sin(2\delta)\sin^{2}\delta\sin\tau\bigl{(}\cos\beta+\cos\gamma\bigr{)}.$

We are now in position to fully characterize the different classes of
parametrizations of iso-entangled bases of two qubits. These correspond to the
5 different solutions (i)-(v) above of Eqs. (II.1),(II.1),(II.1). Note,
however, that two of the solutions (namely, (iii.a) and (iii.b)), lead to
equivalent families up to a swap (so they belong to the same equivalence
class). Therefore, we arrive at 4 families of iso-entangled bases. We will
denominate the different families $I^{(j)}$ with $j\in(1,\ldots,4)$, and we
will express them in either the computational basis or in the skewed basis
(3); we will indicate this by a subscript $\ket{0}$ or $\ket{\varphi}$,
respectively. We will see that each of them is characterized not only by a
different functional form of the states (which reflects different geometrical
properties thereof) but also by the amount of parameters which the degree of
entanglement $\xi^{(j)}$ depends on.

###  II.2 Four inequivalent families of iso-entangled bases

Solutions (i-iv) lead to the following four families of isoentangled bases:

1\. Skewed product family

Starting from condition (i), the parametrisation can be reduced to

$\displaystyle I^{(1)}_{\tiny{\ket{0}}}=\left(\begin{array}[]{cccc}1&0&0&0\\\
0&1&0&0\\\ 0&0&\cos\tau&-\sin\tau\\\ 0&0&\sin\tau&\cos\tau\end{array}\right).$
(17)

where the other parameters have been absorbed into local transformations.
Note, that the degree of entanglement is $\xi^{(1)}=0$, independently of
$\tau$. As already mentioned, this family contains only product bases,
equivalent to skewed basis provided in Eq. (3).

From the point of view of the Bloch ball (See Fig. 1) this family is composed
always from two twice degenerate points on the north and south poles in one
reduction, and two pairs of opposite poles in the other.

Figure 1: Both reductions density matrices for four pure states for an
exemplary member of the skewed product family. Note that in the first
reduction (left) all states lie on the $z$ axis, while in the second they form
a rectangle in the $x-z$ plane.

2\. Elegant family

Condition (ii) yields a family which can be parametrized as

$\displaystyle{\scriptsize
I^{(2)}_{\tiny{\ket{0}}}=\frac{1}{\sqrt{2}}\left(\begin{array}[]{cccc}0&0&-e^{i\zeta}&e^{i\zeta}\\\
c\theta&c\theta&-s\theta&-s\theta\\\ s\theta&s\theta&c\theta&c\theta\\\
1&-1&0&0\end{array}\right),}$ (22)

where we have introduced the local transformation of the form
$\exp(i\zeta\sigma_{z})^{\otimes 2}$, with $\zeta=\gamma-\beta$. Hence, this
family has only 2 parameters. Note that in this case, the skewed basis and the
computational one correspond, i.e., $\ket{\varphi}=\ket{0}$. The squared
concurrence reads:

$\xi^{(2)}=\frac{\sin^{2}(2\theta)}{4},$ (23)

which depends only on one parameter. Note that the degree of entanglement is
bound, $\xi^{(2)}\in\left[0,\frac{1}{4}\right]$. Nil entanglement (i.e.,
$\xi^{(2)}=0$) corresponds to $\theta=0$, which leads again to the separable
basis (3). The maximal amount of entanglement, $\xi^{(2)}=1/4$, is obtained by
$\theta=\pi/4$. Note that this family contains the Elegant Joint Measurement
(EJM), which play a special role in network nonlocality [23]. EJM has, in
fact, $\xi=1/4$, and is retrieved for $\zeta=\pi/2$. Since EJM is the extremal
case of this family, we name this “Elegant family". Fixing the maximal amount
of entanglement, however, does not single out EJM and leads to a 1-parameter
subfamily.

In Bloch ball representation (see Fig. 2), the first two states lie on a
hyperbole in the $x$-$z$ plane, whereas the other two lie on a full rotational
hyperboloid with symmetry around $z$ axis. The opening angle of the limiting
cone of these hyperboloids is $\theta$ in one, and $\pi-\theta$ in the other
reduction. A generic member of this family forms a simplex with three pairs of
edges of different lengths. The EJM is singled out by maximizing the volume of
both reductions.

Figure 2: Partial traces for a selected member of the Elegant family (in red)
together with the EJM (blue). A generic member of this family forms simplex
structures with all states lying on cones with opening angles $2\theta$ and
$\pi-2\theta$, for the two reductions respectively; the second pair is rotated
with respect to the first by an angle $\zeta$. In particular, EJM is found by
setting $\theta=\pi/4$ and $\zeta=\pi/2$, thus forming two regular simplices.

3\. Bell family

This family is the conflation of conditions (iii.a) and (iii.b), which are
equivalent up to a swap $\textrm{S}_{A\leftrightarrow B}$ and substituting
$\tau$ by $\theta$, respectively. In both cases the phase $e^{i\beta}$ can be
reabsorbed into the computational state $\ket{1}$ of the first qubit and
defining $\zeta=\gamma+\beta$, or into $\ket{0}$ of the second qubit and
defining $\zeta^{\prime}=\gamma-\beta$, respectively. Hence, this family
reads:

$\displaystyle
I_{\tiny{\ket{0}}}^{(3)}=\left(\begin{array}[]{cccc}0&0&-c\delta\cdot
e^{i\zeta}&s\delta\cdot e^{i\zeta}\\\ s\delta&c\delta&0&0\\\ s\tau\cdot
c\delta&-s\tau\cdot s\delta&c\tau\cdot s\delta&c\tau\cdot c\delta\\\
-c\tau\cdot c\delta&c\tau\cdot s\delta&s\tau\cdot s\delta&s\tau\cdot
c\delta\end{array}\right).$ (28)

Hence, one has the 3 expected parameters ($\delta,\zeta$ and $\tau$). The
tangle reads:

$\xi^{(3)}=\sin[2](2\delta)\sin[2](\tau),$ (29)

which depends on 2 parameters and varies between $0$ and $1$. For
$\delta=\pi/4$ and $\tau=\pi/2$ one achieves maximally entangled states, i.e.,
$\xi^{(3)}=1$. This is equivalent to the standard Bell State Measurement
(BSM), which is the unique maximally entangled basis up to local
transformations [24]. This thus suggests the name of this family. For nil
entanglement, i.e., $\xi^{(3)}=0$, one has either $\delta=0$, or
$\cos(\tau)=\pm 1$; both cases are equivalent to the already discussed
separable family (3).

Despite full range of attainable entanglement, from the perspective of the
Bloch ball, this family always produces rectangles lying in the $x$-$z$ plane
in one reduction, and in a rotated plane in the other, with rotation being
controlled by $\zeta$ phase. In particular, we note that in Bloch
representation (see Fig. 3) a part of the Bell family will overlap with the
subset of Elegant family with $\zeta=0$.

An alternative derivation of this family, resulting in a canonical form, is
given in SM, section B.

Figure 3: Generic member of the Bell family. Note that the four vectors in
both reductions form two rectangles, with the first one lying on a cone with
the rotation axis along $z$ axis.

4\. General family

In the case of condition (iv) we find that necessarily we have
$e^{i\gamma}=-e^{\pm i\beta}$ , which yields the relation:

$\tan(\tau)=\frac{\cos(2\delta)\sin(\theta)}{\sin(2\delta)\cos(\beta)}.$ (30)

Hence, the parametrization reads:

$\displaystyle
I^{(4)}_{\tiny{\ket{\varphi}}}=\left(\begin{array}[]{cccc}0&0&c\delta\cdot
e^{\pm i\beta}&-s\delta\cdot e^{\pm i\beta}\\\ s\delta\cdot
c\theta&c\delta\cdot c\theta&-s\delta\cdot s\theta&-c\delta\cdot s\theta\\\
s\delta\cdot s\theta&c\delta\cdot s\theta&s\delta\cdot c\theta&c\delta\cdot
c\theta\\\ -c\delta\cdot e^{i\beta}&s\delta\cdot
e^{i\beta}&0&0\end{array}\right).$ (35)

The expected 3 parameters are $\delta,\theta$ and $\beta$. The tangle reads:

$\displaystyle\xi^{(4)}$ $\displaystyle=$
$\displaystyle\frac{\sin[2](2\theta)\sin[2](2\delta)}{4}\cdot$ (36)
$\displaystyle\cdot\frac{\sin[2](2\delta)\cos[2](\beta)+\cos[2](2\delta)}{\sin[2](2\delta)\cos[2](\beta)+\cos[2](2\delta)\sin[2](\theta)},$

which varies between $0$ and $1$. Note that this is the most general family of
iso-entangled bases, for its degree of entanglement depends on all the three
parameters and it has overlaps with all the other families. Furthermore, a
generic basis from this family will yield non-degenerate simplices in both
reductions.

Note that Eqs. (30) and (36) have five singularity points. Studying the
(directional) limits of these multivariable functions yields the following
cases:

  * •

$\lim\beta\rightarrow\pi/2$ reduces the General family (35) to a two-parameter
subfamily of the Bell family (28). In particular, this implies that
$\tau\rightarrow{}\pi/2$ and
$\xi^{(4)}\rightarrow\cos[2](\theta)\sin[2](2\delta)$, which has the same form
of Eq. (29). Note, that the Bell family depends on the same number of
parameters as the General family, therefore it cannot be fully retrieved by
any of the limits.

  * •

$\lim\delta\rightarrow\pi/4$ reduces the General family to the Elegant family
(22).

  * •

$\lim\theta\rightarrow 0$ and $\delta\rightarrow 0$ reduces General family to
the skewed product family (17), independently of the direction of approach of
these limits.

  * •

$\lim\beta\rightarrow\pi/2$ and $\delta\rightarrow\pi/4$ leads to an
interpolationbetween a part of the Elegant family and a subfamily of the Bell
family, depending on the direction of approach of the limit. In Ref. [11], a
one-parameter iso-entangled family was proposed that also interpolates between
EJM and BSM. However, this cannot be contained within this limit case because
the latter does not admit regular-simplices within the reductions, contrarily
to the family in [11] (see SM, section C).

  * •

$\lim\beta\rightarrow\pi/2$ and $\lim\theta\rightarrow 0$ leads to a subfamily
of the Bell family wherein, however, the degree of entanglement is upper
bounded, with the bound depending on the angle of approach
$\phi\in(-\pi/2,\pi/2)$ as $(1+\tan(\left|\phi\right|))^{-2}$.

From this, one sees that the three particular families (17), (22), and (28)
(partly) form the closure of the General family.

##  III An application to quantum networks

Let us consider a triangular network scenario, in which Alice, Bob and Charlie
share pairwise a Bell state of two qubits, e.g.,

$\ket{\Psi}_{ABC}=\ket{\psi_{+}}_{AB}\otimes\ket{\psi_{+}}_{AC}\otimes\ket{\psi_{+}}_{BC},$
(37)

and each chooses a basis to perform a joint measurement on their pair of
qubits (see Ref. [25]). The scenario is said to be Output-Permutation
Invariant (OPI) if the output probability distribution can be defined by three
constants

$\displaystyle p_{1}$ $\displaystyle=p_{iii},$ $\displaystyle p_{2}$
$\displaystyle=p_{\sigma(iij)},$ $\displaystyle p_{3}$
$\displaystyle=p_{\sigma(ijk)},$ (38)

for $i\neq j\neq k\neq i$ and any permutation $\sigma$; intuitively, it means
that no node, nor output, of the network is distinguished. Similar notion can
be defined for larger networks based on the network graph automorphism group.

Figure 4: $p_{3}$-$p_{1}$ plane for OPI measurements, with the red line
representing probabilities corresponding to EJM acting on Bell states under
local noise, $\Phi_{\epsilon}(\outerproduct{\psi_{+}}{\psi_{+}})^{\otimes 3}$,
while green line corresponds to the OPI stemming from the Elegant family
acting on the network state $\outerproduct{\Psi}{\Psi}$ from (37). The Finner
inequality is known to be a bound for local and quantum distributions [26].

Since the iso-entangled bases set each of the measurement states on equal
footing, they appear to be natural candidates for measurements realizing OPI
in such networks. We find that setting $\beta=\gamma+\pi/2$ and then
$\gamma=\frac{1}{2}\arccos(-\sin(2\theta))$ in the Elegant family leads to a
1-parameter subset of measurements which leads to OPI distributions.
Interestingly, none of the measurements in this family, except for the
extremal points, remains OPI under local noise
$\Phi_{\epsilon}(\rho)=(1-\epsilon)\rho+\frac{\epsilon}{4}\mathbb{I}$ acting
on each edge of the network (see Fig. 4).

##  IV Discussion and outlook

In this letter, we have provided complete classification of all the
equivalence classes of bases of two qubits, whose four states have all the
same degree of entanglement (i.e., iso-entangled bases). In particular, we
have shown that there exist four inequivalent families of equivalence classes,
characterized by their numbers of parameters and geometrical constraints of
their reductions in the Bloch ball representation.

This study represents a first necessary step towards a deeper understanding of
entangled measurements, a topic that has received surprisingly little
attention—especially if compared to entangled states between distant
parties—despite their pivotal importance in quantum computation, and other
quantum tasks (such as quantum teleportation, dense coding, or the activation
of nonlocality in networks).

Although our findings provide the theoretical framework for further studies,
many questions remain open. Most of the aforementioned tasks, such as quantum
teleportation or dense coding, make use of Bell State Measurements. Our work
provides the tool to start asking in systematic manner questions like: for
which tasks partially entangled measurements provide stronger resource than
the maximally entangled ones? This can bring novel insights into nonlocality,
especially in the context of quantum networks with no inputs, in which
nonlocality is triggered exclusively by the selected measurements. Moreover,
further questions arise concerning implementability: which of the entangled
measurements can be experimentally realised using standard resources such as
linear optical elements?

Furthermore, this preliminary study has addressed only the problem of
entangled measurements in the simplest case of two qubits. The natural
extension to higher dimensions turns out to be hard, with sparse known
examples in literature [27, 14, 13, 15]. In SM, section D, we provide a short
review of already known families together with a new family of partially
entangled bases. This represents a first attempt towards a generalization to
higher dimensions that will remain as a direction of future research.

## Acknowledgements

We thank Otfried Gühne for pointing out Ref. [22] to us. F.D.S. acknowledges
support from FWF (Austrian Science Fund) through an Erwin Schrödinger
Fellowship (Project J 4699s). J.Cz. and K.Ż. gratefully acknowledge financial
support by Narodowe Centrum Nauki under the Quantera project number
2021/03/Y/ST2/00193 and the project number 2019/35/O/ST2/01049. The research
has also been supported by a grant from the Priority Research Area DigiWorld
under the Strategic Programme Excellence Initiative at Jagiellonian
University. N.G. acknowledges support from the Swiss National Science
Foundation via the NCCR-SwissMap.

## References

  * Bennett  _et al._ [1993] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels, Phys. Rev. Lett. 70, 1895 (1993).
  * Zukowski  _et al._ [1993] M. Zukowski, A. Zeilinger, M. A. Horne, and A. K. Ekert, "event-ready-detectors" Bell experiment via entanglement swapping., Phys. Rev. Lett. 71 (1993).
  * Bennett and Wiesner [1992] C. H. Bennett and S. J. Wiesner, Communication via one-and two-particle operators on Einstein-Podolsky-Rosen states, Phys. Rev. Lett. 69, 2881 (1992).
  * Jozsa  _et al._ [2003] R. Jozsa, M. Koashi, N. Linden, S. Popescu, S. Presnell, D. Shepherd, and A. Winter, Entanglement cost of generalised measurements, Quantum Inf. Comp. (2003).
  * Chitambar  _et al._ [2014] E. Chitambar, D. Leung, L. Mančinska, M. Ozols, and A. Winter, Everything you always wanted to know about locc (but were afraid to ask), Communications in Mathematical Physics 328, 303 (2014).
  * Nielsen and Chuang [2002] M. A. Nielsen and I. Chuang, Quantum computation and quantum information (2002).
  * Tavakoli  _et al._ [2022] A. Tavakoli, A. Pozas-Kerstjens, M.-X. Luo, and M.-O. Renou, Bell nonlocality in networks, Rep. Prog. Phys. 85, 056001 (2022).
  * Cavalcanti  _et al._ [2023] E. G. Cavalcanti, R. Chaves, F. Giacomini, and Y.-C. Liang, Fresh perspectives on the foundations of quantum physics, Nature Reviews Physics , 1 (2023).
  * Méthot and Scarani [2007] A. A. Méthot and V. Scarani, An anomaly of non-locality, Quantum Inf. Comput. 7, 157 (2007).
  * Brunner  _et al._ [2005] N. Brunner, N. Gisin, and V. Scarani, Entanglement and non-locality are different resources, New J. Phys. 7, 88 (2005).
  * Tavakoli  _et al._ [2021] A. Tavakoli, N. Gisin, and C. Branciard, Bilocal Bell inequalities violated by the quantum elegant joint measurement, Phys. Rev. Lett. 126, 220401 (2021).
  * Koniorczyk and Bužek [2005] M. Koniorczyk and V. Bužek, Nonmaximally entangled bases and their application in entanglement purification via swapping, Phys. Rev. A 71, 032331 (2005).
  * Karimipour and Memarzadeh [2006] V. Karimipour and L. Memarzadeh, Equientangled bases in arbitrary dimensions, Phys. Rev. A 73, 012329 (2006).
  * Rajchel  _et al._ [2018] G. Rajchel, A. Gąsiorowski, and K. Życzkowski, Robust Hadamard matrices, unistochastic rays in Birkhoff polytope and equi-entangled bases in composite spaces, Mathematics in Computer Science 12, 473 (2018).
  * Czartowski and Życzkowski [2021] J. Czartowski and K. Życzkowski, Bipartite quantum measurements with optimal single-sided distinguishability, Quantum 5, 442 (2021).
  * Huang  _et al._ [2022] C.-X. Huang, X.-M. Hu, Y. Guo, C. Zhang, B.-H. Liu, Y.-F. Huang, C.-F. Li, G.-C. Guo, N. Gisin, C. Branciard, and A. Tavakoli, Entanglement swapping and quantum correlations via symmetric joint measurements, Phys. Rev. Lett. 129, 030502 (2022).
  * Pimpel  _et al._ [2023] F. Pimpel, M. J. Renner, and A. Tavakoli, Do entangled states correspond to entangled measurements under local transformations?, arXiv:2301.13285 (2023).
  * Vidal [2000] G. Vidal, Entanglement monotones, J. Mod. Opt. 47, 355 (2000).
  * Wootters [1998] W. K. Wootters, Entanglement of formation of an arbitrary state of two qubits, Phys. Rev. Lett. 80, 2245 (1998).
  * Rungta  _et al._ [2001] P. Rungta, V. Bužek, C. M. Caves, M. Hillery, and G. J. Milburn, Universal state inversion and concurrence in arbitrary dimensions, Physical Review A 64, 042315 (2001).
  * Peters  _et al._ [2004] N. A. Peters, T.-C. Wei, and P. G. Kwiat, Mixed-state sensitivity of several quantum-information benchmarks, Phys. Rev. A 70, 052309 (2004).
  * Sanpera  _et al._ [1998] A. Sanpera, R. Tarrach, and G. Vidal, Local description of quantum inseparability, Phys. Rev. A 58, 826 (1998).
  * Gisin [2019] N. Gisin, Entanglement 25 years after quantum teleportation: testing joint measurements in quantum networks, Entropy 21, 325 (2019).
  * Popescu and Vaidman [1994] S. Popescu and L. Vaidman, Causality constraints on nonlocal quantum measurements, Phys. Rev. A 49, 4331 (1994).
  * Renou  _et al._ [2019a] M.-O. Renou, E. Bäumer, S. Boreiri, N. Brunner, N. Gisin, and S. Beigi, Genuine quantum nonlocality in the triangle network, Phys. Rev. Lett. 123, 140401 (2019a).
  * Renou  _et al._ [2019b] M.-O. Renou, Y. Wang, S. Boreiri, S. Beigi, N. Gisin, and N. Brunner, Limits on correlations in networks for quantum and no-signaling resources, Phys. Rev. Lett. 123, 070403 (2019b).
  * Werner [2001] R. F. Werner, All teleportation and dense coding schemes, J. Phys. A - Math. Gen. 34, 7081 (2001).

## SM A – canonical local form of the basis

Let us denote with $B$ the matrix whose columns are the vectors
$\\{\ket{\psi_{1}},\ket{\psi_{2}},\ket{\psi_{3}},\ket{\psi_{4}}\\}$ with
coefficients expressed in the computational basis. Any 2-dimensional subspace
spanned by, e.g., $\ket{\psi_{3}}$ and $\ket{\psi_{4}}$, necessarily contains
(at least) one product state (Theorem 2 in Ref. [22]). We may introduce local
rotations in such a way that it corresponds to the state $\ket{0,0}$. Hence,
the first line of the matrix representing that basis starts with 2 zeros.
Similarly, the subspace spanned by $\ket{\psi_{1}}$ and $\ket{\psi_{2}}$
contains a product state $\ket{\vartheta,\varphi}$ which is necessarily
orthogonal to $\ket{0,0}$. Without loss of generality, let us assume
$\ket{\vartheta}=\ket{1}$, whereas
$\ket{\varphi}=\cos(\tau)\ket{0}+\sin(\tau)\ket{1}$ and
$\ket{\varphi^{\perp}}=\cos(\tau)\ket{1}-\sin(\tau)\ket{0}$. Hence, one gets
$\psi_{33}\cdot\psi_{44}=\psi_{34}\cdot\psi_{43}$, where
$\psi_{jk}=\chi_{jk}e^{i\phi_{jk}}$ denotes the element $j,k$ of the matrix
$B$, i.e., the $k$th component of vector $\ket{\psi_{j}}$ in the computational
basis. Next, we choose the phases of $\psi_{3}$ and $\psi_{4}$ such that their
4th components are real, i.e., $\psi_{34}=\chi_{34}$ and
$\psi_{44}=\chi_{44}$. The aforementioned relation implies that
$\phi_{33}=\phi_{43}:=\phi$. Thus, it is possible to remove this phase by
applying the local transformation of the form
$\operatorname{exp}(i(\sigma_{z}\otimes\leavevmode\hbox{\small
1\normalsize\kern-3.30002pt1}-\leavevmode\hbox{\small
1\normalsize\kern-3.30002pt1}\otimes\sigma_{z})\phi)$. Hence, the general form
of our basis written in the computational basis is given by

$\displaystyle B_{\ket{0}}=\left(\begin{array}[]{cccc}0&0&\cdot&\cdot\\\
\cdot&\cdot&\cdot&\cdot\\\ \cdot&\cdot&\chi_{33}&\chi_{43}\\\
\cdot&\cdot&\chi_{34}&\chi_{44}\end{array}\right),$ (SM5)

where the 4 displayed entries are real and satisfy the relation
$\chi_{33}\cdot\chi_{44}=\chi_{34}\cdot\chi_{43}$.

Let us now write B in the skewed basis provided in Eq. (3). This implies that
the last 2 entrees of the last line are also zeros. Starting from the form of
the basis provided in Eq. (19), let us choose the global phases such that the
third component of each vector is real, i.e., $\psi_{k3}=\chi_{k3}$. Applying
the local change of basis in Eq. (3), leads to

$\displaystyle
B_{\ket{\varphi}}=\left(\begin{array}[]{cccc}0&0&\psi_{31}&\psi_{41}\\\
\psi_{12}&\psi_{22}&\psi_{32}&\psi_{42}\\\
\chi_{13}&\chi_{23}&\chi_{33}&\chi_{43}\\\
\psi_{14}&\psi_{24}&0&0\end{array}\right).$ (SM10)

These coefficients depend at this point, in general, on 20 real parameters (21
counting also $\tau$ in the definition of the skewed basis).

We now impose the orthogonality constraints between the pair of vectors for
which two components of the scalar product vanish. Denoting by $\chi_{jk}$ the
norm of each (in general complex) element $\psi_{jk}$, from
$\innerproduct{\psi_{1}}{\psi_{3}}$ it follows that
$\chi_{12}\cdot\chi_{32}=\pm\chi_{13}\cdot\chi_{33}$ and
$\phi_{12}=\phi_{22}(+k\pi)$; from $\innerproduct{\psi_{2}}{\psi_{3}}$, that
$\chi_{22}\cdot\chi_{32}=\pm\chi_{23}\cdot\chi_{33}$ and
$\phi_{22}=\phi_{32}(+l\pi)$; from $\innerproduct{\psi_{1}}{\psi_{4}}$, that
$\chi_{12}\cdot\chi_{42}=\pm\chi_{13}\cdot\chi_{43}$ and
$\phi_{12}=\phi_{42}(+m\pi)$; and finally, from
$\innerproduct{\psi_{2}}{\psi_{4}}$, one finds that
$\chi_{22}\cdot\chi_{42}=\pm\chi_{23}\cdot\chi_{43}$ and
$\phi_{22}=\phi_{42}(+n\pi)$.

In the next step we reintroduce the normalisation constraints. Note that since
in the considered skewed basis, each vector has only 3 non-zero components,
such that the normalization can be written as
$|\psi_{j}|^{2}=a_{j}^{2}+b_{j}^{2}+c_{j}^{2}$, where each $a_{j},b_{j},c_{j}$
is one of the non-zero real component $\chi_{jk}$ of the $j-$th vector. Note
that imposing the normalization conditions $|\psi_{j}|^{2}=1$ leads to the
following general parametrization:

$\displaystyle\begin{array}[]{cc}a_{j}=\sin(\alpha_{j})\sin(\beta_{j})\\\
b_{j}=\sin(\alpha_{j})\cos(\beta_{j})\\\ c_{j}=\cos(\alpha_{j}).\end{array}$
(SM14)

This, together with the four orthogonality conditions above, leads to reduce
the matrix of coefficients to 8 real parameters (9 counting also $\tau$ in the
definition of the skewed basis). After this simplification, we impose the
orthogonality contraints of the last two pair of vectors
$\innerproduct{\psi_{1}}{\psi_{2}}$, and $\innerproduct{\psi_{3}}{\psi_{4}}$,
which remove two additional parameters. Finally, one can apply a further local
rotation that eliminates one last parameter, leading to the form in Eq. (4)
which depends, as anticipated, on 5 explicit parameters (6 if one counts also
the implicit $\tau$).

## SM B – canonical form of the Bell family

Here we provide a canonical form of the Bell family by starting from its
geometric structure, which will allow us to give the three free parameters
explicit interpretations. We start by defining local bases

$\displaystyle\ket{A_{1}}$ $\displaystyle=\cos x\ket{0}\\!+\\!\sin x\ket{1}$
$\displaystyle\ket{A_{2}}$ $\displaystyle=\cos x\ket{0}\\!-\\!\sin x\ket{1}$
(SM15) $\displaystyle\ket{B_{1}}$ $\displaystyle=\cos y\ket{0}\\!+\\!\sin
y\ket{1}$ $\displaystyle\ket{B_{2}}$ $\displaystyle=\cos y\ket{0}\\!-\\!\sin
y\ket{1}$

together with the orthogonal states marked by the upper index,
$\ket{\cdot^{\perp}}$, defined such that the second entry is dephased. Then,
we define the four bipartite states in the basis as

$\displaystyle\ket{\psi_{1}}$ $\displaystyle=\cos
z\ket{A_{1}}\ket{B_{1}}+e^{i\phi_{1}}\sin
z\ket{A_{1}^{\perp}}\ket{B_{1}^{\perp}}$ (SM16) $\displaystyle\ket{\psi_{2}}$
$\displaystyle=\cos z\ket{A_{1}^{\perp}}\ket{B_{2}}+e^{i\phi_{2}}\sin
z\ket{A_{1}}\ket{B_{2}^{\perp}}$ $\displaystyle\ket{\psi_{3}}$
$\displaystyle=\cos z\ket{A_{2}}\ket{B_{1}^{\perp}}+e^{i\phi_{3}}\sin
z\ket{A_{2}^{\perp}}\ket{B_{1}}$ $\displaystyle\ket{\psi_{4}}$
$\displaystyle=\cos z\ket{A_{2}^{\perp}}\ket{B_{2}^{\perp}}+e^{i\phi_{4}}\sin
z\ket{A_{2}}\ket{B_{2}}$

with $z\in[0,\pi/4]$. These four states follow the general geometric property
of Bell family considered in the Bloch ball: in both reductions there are two
pairs of co-linear states, and if a pair is co-linear in reduction $A$, it is
not co-linear in reduction $B$.

In order to derive generic member of the Bell family we impose that $\sin
x\neq 0$ and analogically for cosines and $y$ variable. After carrying out
elementary inner products between the states we find that the phases are given
by

$\phi_{1}=-\phi_{2}=-\phi_{3}=\phi_{4}$ (SM17)

and

$\cos(\pm\phi_{1})=-\frac{\tan 2x\tan 2y}{\sin 2z}.$ (SM18)

In this way we arrive at the canonical form for the Bell family, since the
three parameters are well connected to the properties of the resulting bases –
$x$ and $y$ angles are connected to the geometric arrangement in the Bloch
ball, while $z$ angle corresponds to the degree of entanglement in the basis.

## SM C – placing family from [11] within the General family

A family of isoentangled bases,
$I^{(5)}=\left\\{\ket{\psi_{i}}\right\\}_{i=1}^{4}$, has been considered in
[11] in the context of violating bilocality in linear three-partite network.
It can be given explicitly in the form

${\footnotesize
I^{(5)}_{\ket{0}}\\!=\\!\frac{1}{2\sqrt{2}}\\!\left(\begin{array}[]{cccc}1\\!+\\!i&1\\!-\\!i&1\\!-\\!i&1\\!+\\!i\\\
\\!-\\!ie^{i\phi}\\!-\\!i&ie^{i\phi}\\!-i&i\\!-\\!ie^{i\phi}&ie^{i\phi}\\!+\\!i\\\
ie^{i\phi}\\!-\\!i&\\!-ie^{i\phi}\\!-\\!i&ie^{i\phi}\\!+\\!i&i\\!-\\!ie^{i\phi}\\\
1\\!-\\!i&1\\!+\\!i&1\\!+\\!i&1\\!-\\!i\\\ \end{array}\right)}$ (SM19)

which, a priori, does not correspond to any of the families introduced in this
work. By considering the simple fact that it interpolates between elegant
joint measurement and Bell state measurement for $\phi=0$ and
$\phi=\frac{\pi}{2}$, it cannot lie in skewed-product family, Bell family or
Elegant family – therefore it is natural to assume it to be fully embeddable
within the General family.

In order to find its relation to the members of the General family, let us
first define $v^{A}_{i}$ as the Bloch vector corresponding to the $A$
reduction of the state $\ket{\psi_{i}}$, and likewise for $B$ reduction. We
will consider the Gram matrices

$\displaystyle(G_{A})_{ij}=v^{A}_{i}\cdot v^{A}_{j}$
$\displaystyle(G_{B})_{ij}=v^{B}_{i}\cdot v^{B}_{j}$ (SM20)

Similarly, we define $\tilde{G}_{A}$ and $\tilde{G}_{B}$ for members of the
General family $I^{(4)}=\left\\{\ket{\tilde{\psi}_{i}}\right\\}_{i=1}^{4}$.
Using the above, we define a cost function

${\footnotesize
F(\beta,\,\theta,\,\delta)\\!=\\!\sum_{i,j}\left(G^{A}_{ij}\\!-\\!\tilde{G}^{A}_{\sigma(i)\sigma(j)}\right)^{2}\\!\\!\\!+\\!\left(G^{B}_{ij}\\!-\\!\tilde{G}^{B}_{\sigma(i)\sigma(j)}\right)^{2}}$
(SM21)

and we use minimization of the above function with respect to the parameters
$\beta,\,\theta,\,\delta$ with the acceptaince threshold of
$F\leq\epsilon=10^{-12}$. Using this we arrive numerically at curves
$(\beta(\phi),\,\theta(\phi),\,\delta(\phi))$ for embedding the family
$I^{(5)}_{\ket{0}}$ within the General family, as shown in Fig. 5.

Figure 5: Family of iso-entangled bases defined in (SM19) can be placed within
the General family as defined in (35) using numerically generated functions
$\beta(\phi),\,\theta(\phi)$ and $\delta(\phi)$, with the last one expressible
directly as $\delta=(\phi-\pi/2)/2$.

##  V SM D – isoentangled families in higher dimensions

The natural next step after the analysis of the simplest two-qubit bases is to
shift to objects with larger local dimension, residing in spaces
$\mathcal{C}^{d}\otimes\mathcal{C}^{d}$. Direct application of methods
presented in this work does not seem to be realistic, thus we expect that new
techniques would need to be developed to extend the current results beyond
qubits. Nevertheless, there exist certain partial results and limited families
in the literature.

Separable bases are the simplest case, and can be fully given in terms of
conditional measurement bases

$\ket{\psi_{ij}}=\ket{i}\otimes\ket{j_{i}},$ (SM22)

where one imposes the relations

$\innerproduct{i}{i^{\prime}}=\delta_{ii^{\prime}},\,\innerproduct{j_{i}}{j_{i^{\prime}}}=\delta_{jj^{\prime}}.$
(SM23)

and the product of the form $\innerproduct{j_{i}}{j^{\prime}_{i^{\prime}}}$
needs not to be defined for $i\neq i^{\prime}$. Using local transformations we
can always set the local bases $\ket{i}$ and $\ket{j_{0}}$ to the
computational basis, thus simplifying this family to direct sum of unitaries,
$\sum_{i=1}^{d}U_{i}$.

The other extreme—bases composed of maximally entangled states—have been
considered by Werner [27], where a 1-to-1 equivalence between maximally
entangled bases, unitary bases, teleportation schemes and dense coding schemes
has been established. Furthermore, a family of shift-and-multiply bases based
on Hadamard matrices and Latin squares has been introduced therein.

Limited families of isoentangled bases have been considered in [14, 15, 13],
without claims of being complete constructions. Below we demonstrate a method
to merge methods from [27] and [14], arriving at a new family of bases with
intermediate entanglement degrees.

First we focus on a construction from [27]. Therein, a family of unitary bases
based on Hadamard matrices and Latin squares is introduced. Given a $d\times
d$ Latin square $\lambda(j,k):I_{d}\times I_{d}\mapsto I_{d}$ and $j$ (not
necessarily distinct) Hadamard matrices, the set of unitary matrices $U^{ij}$
o f dimension $d$ is defined by

$U^{ij}\ket{k}=(H^{j})_{ik}\ket{\lambda(j,k)}$ (SM24)

and they provide an orthogonal unitary basis due to the easily verifiable
property

$\text{tr}(U^{ij\dagger}U^{i^{\prime}j^{\prime}})=d\delta_{ii^{\prime}}\delta_{jj^{\prime}}.$
(SM25)

It is also easily verified that vectorized versions

$U\mapsto\ket{U}=\frac{1}{\sqrt{d}}\sum_{nm}U_{nm}\ket{nm}$

provide a maximally entangled bases of the $d^{2}$-dimensional Hilbert space.

We may now replace Hadamard matrices with robust Hadamard matrices considered
in [14], such that $R^{j}R^{j\dagger}=\mathbb{I}$. The corresponding
bistochastic matrix has the structure

$\left|R^{j}\right|^{2}=\left(\begin{array}[]{cccc}a&b&\ldots&b\\\
b&a&\ldots&b\\\ \vdots&\vdots&\ddots&\vdots\\\ b&b&\ldots&a\end{array}\right)$
(SM26)

with absolute value understood entry-wise. Then, a non-unitary shift-and-
multiply basis

$B^{ij}\ket{k}=(R^{j})_{ik}\ket{\lambda(j,k)}.$ (SM27)

Entire proof from [27] can be retraced to demonstrate the orthogonality of the
resulting states $\ket{B^{ij}}$ and the isoentangled character of the basis
down to the specific Schmidt coefficients follows directly from the form of
vectorization map.

Indeed, one can extend the above construction to all unitary $R^{j}$ such that
all rows/columns contain the same amplitudes up to permutation.

It is important to note that the above construction is distinct from
equientangled bases given in [14], which is evident already on the level of
number of robust Hadamards $R^{j}$ used in the construction.


# Chordal Matroids arising from Generalized parallel connections II

James Dylan Douthitt  Mathematics Department
Louisiana State University
Baton Rouge, Louisiana<EMAIL_ADDRESS>and  James Oxley  Mathematics
Department
Louisiana State University
Baton Rouge, Louisiana<EMAIL_ADDRESS>
###### Abstract.

In 1961, Dirac showed that chordal graphs are exactly the graphs that can be
constructed from complete graphs by a sequence of clique-sums. In an earlier
paper, by analogy with Dirac’s result, we introduced the class of
$GF(q)$-chordal matroids as those matroids that can be constructed from
projective geometries over $GF(q)$ by a sequence of generalized parallel
connections across projective geometries over $GF(q)$. Our main result showed
that when $q=2$, such matroids have no induced minor in
$\\{M(C_{4}),M(K_{4})\\}$. In this paper, we show that the class of
$GF(2)$-chordal matroids coincides with the class of binary matroids that have
none of $M(K_{4})$, $M^{*}(K_{3,3})$, or $M(C_{n})$ for $n\geq 4$ as a flat.
We also show that $GF(q)$-chordal matroids can be characterized by an
analogous result to Rose’s 1970 characterization of chordal graphs as those
that have a perfect elimination ordering of vertices.

###### Key words and phrases:

chordal graph, parallel connection, projective geometry

###### 1991 Mathematics Subject Classification:

05B35, 05C75

##  1\. Introduction

The notation and terminology in this paper will follow [5] for graphs and [10]
for matroids. Unless stated otherwise, all graphs and matroids considered here
are simple. Thus every contraction of a set from a matroid is immediately
followed by the simplification of the resulting matroid. We will also assume
all matroids are binary unless otherwise specified. Following Cordovil, Forge,
and Klein [4], we define a simple or non-simple matroid $M$ to be chordal if,
for each circuit $D$ that has at least four elements, there are circuits
$D_{1}$ and $D_{2}$ and an element $e$ such that $D_{1}\cap D_{2}=\\{e\\}$ and
$D=(D_{1}\cup D_{2})-e$. Therefore, a simple binary matroid is chordal
precisely when it has no member of $\\{M(C_{n}):n\geq 4\\}$ as a flat, where
$C_{n}$ is the $n$-edge cycle. In Section 2, we prove an assertion made in [7]
that the class of such matroids coincides with the class of binary matroids
with no $M(C_{4})$ as an induced minor, where an induced minor of a matroid
$M$ is any matroid that can be obtained from $M$ by a sequence of contractions
and restrictions to flats. This matroid notion is analogous to a graph notion,
an induced minor of a graph $G$ being a graph that can be obtained from $G$ by
a sequence of vertex deletions and edge contractions.

For a prime power $q$, we denote the projective geometry $PG(r-1,q)$ by
$P_{r}$ when context makes the field clear. A matroid is $GF(q)$-chordal if it
can be obtained by repeated generalized parallel connections across projective
geometries over $GF(q)$ starting with projective geometries over $GF(q)$. In
Section 3, we prove the next theorem, which is the main result of the paper,
and we give an analogous result for $q>2$. The equivalence of (i) and (ii) was
shown in [7].

######  Theorem 1.1.

The following are equivalent for a binary matroid $M$.

  1. (i)

$M$ is $GF(2)$-chordal.

  2. (ii)

$M$ has no member of $\\{M(C_{4}),M(K_{4})\\}$ as an induced minor.

  3. (iii)

$M$ has no member of $\\{M(C_{n}):n\geq 4\\}\cup\\{M(K_{4}),M^{*}(K_{3,3})\\}$
as an induced restriction.

In Section 3, we also prove the following analog of Theorem 1.1 for all other
primes.

######  Theorem 1.2.

For each prime $p>2$, the following are equivalent for a $GF(p)$-representable
matroid $M$.

  1. (i)

$M$ is $GF(p)$-chordal.

  2. (ii)

$M$ has no member of $\\{U_{2,k}:3\leq k\leq p\\}$ as an induced minor.

  3. (iii)

$M$ has no member of $\\{U_{n,n+1}:n\geq 2\\}\cup\\{U_{2+t,k+t}:4\leq k\leq
p\text{ and }0\leq t\leq p+1-k\\}$ as an induced restriction.

Chordal graphs have been characterized in several other ways apart from
Dirac’s [6] description. A perfect elimination ordering of a graph $G$ is an
ordering of $V(G)$ such that, for every vertex $v$, the graph induced by $v$
and all of its neighbors that occur after $v$ in the ordering is a clique. In
1970, Rose [11] proved the following characterization.

######  Theorem 1.3.

A graph $G$ chordal if and only if $G$ has a perfect elimination ordering.

A perfect elimination ordering of cocircuits of a matroid $M$ is a collection
$C_{1}^{*},C_{2}^{*},\dots,C_{r}^{*}$ such that, for all $i$ in $[r]$, the set
$C_{i}^{*}$ is a cocircuit of the matroid $M_{i}$, which is
$M\backslash(C_{1}^{*}\cup C_{2}^{*}\cup\dots\cup C_{i-1}^{*})$, and $M|{\rm
cl}_{M_{i}}(C_{i}^{*})$ is a projective geometry. In Section 4, we prove the
following analog of Theorem 1.3 for $GF(q)$-chordal matroids.

######  Theorem 1.4.

A matroid $M$ is $GF(q)$-chordal if and only $M$ has a perfect elimination
ordering of cocircuits.

##  2\. Binary chordal matroids

In this section, we will show that the class of binary chordal matroids
coincides with the class of matroids with no $M(C_{4})$ as an induced minor.
We then give a constructive characterization of such matroids.

######  Lemma 2.1.

Let $n$ be the size of a largest circuit that is an induced minor of $M$. Then
$M$ has an $n$-element circuit as an induced restriction.

###### Proof.

We may assume that, for some independent set $I$ of $M$, the matroid ${\rm
si}(M/I)$ has an $n$-element circuit as a flat. If $|I|=0$, then the result
holds. Assume the result holds for $|I|<k$, and let $|I|=k\geq 1$. Take $e\in
I$. Then ${\rm si}((M/e)/(I-e))$ has an $n$-element circuit as a flat.
Certainly a largest circuit that occurs as an induced minor of ${\rm si}(M/e)$
has $n$ elements. Thus, by the induction assumption, ${\rm si}(M/e)$ has, as
an induced restriction, an $n$-element circuit $C$ where
$C=\\{e_{1},e_{2},\dots,e_{n}\\}$. Then $C$ is a circuit of $M/e\backslash Y$
for some set $Y$. Thus $C$ or $C\cup e$ is a circuit of $M$. We may assume
that no $n$-element circuit is an induced restriction of $M$. Now view $M$ as
a restriction of the binary projective geometry $P_{r}$ where $r=r(M)$. For
each $i$ in $[n]$, let $f_{i}$ be the third point on the projective line ${\rm
cl}_{P_{r}}(\\{e,e_{i}\\})$. For each $i$ in $[n]$, the set
$\\{e_{1},e_{2},\dots,e_{n}\\}-\\{e_{i}\\}$ is an independent set $I_{i}$ of
$M/e$ and hence of $M$. Now ${\rm cl}_{M}(I_{i})$ does not contain $e$
otherwise $I_{i}$ contains a circuit of $M/e$. Moreover, ${\rm cl}_{M}(I_{i})$
does not contain $e_{i}$ as $M$ does not have an $n$-element circuit as an
induced restriction. The projective flat ${\rm cl}_{P_{r}}(I_{i})$ must meet
$\\{e,f_{i},e_{i}\\}$ in $P_{r}$, so this intersection is $f_{i}$. If $f_{i}$
is in $E(M)$, then $M$ has $I_{i}\cup f_{i}$ as an induced restriction that is
an $n$-element circuit. Thus $\\{f_{1},f_{2},\dots,f_{n}\\}$ avoids $E(M)$. We
deduce that $C\cup e$ is an $(n+1)$-element circuit of $M$ that is an induced
minor of $M$, a contradiction. ∎

In the next theorem, the equivalence of (i) and (iii) is an immediate
consequence of the definition. In [7, Lemma 3.8], we had asserted the
equivalence of (i) and (ii). Our proof of this relies on Lemma 2.1 and is more
subtle than we originally thought, so we have included it.

######  Theorem 2.2.

The following are equivalent for a binary matroid $M$.

  1. (i)

$M$ is chordal.

  2. (ii)

$M$ has no $M(C_{4})$ as an induced minor.

  3. (iii)

$M$ has no member of $\\{M(C_{n}):n\geq 4\\}$ as an induced restriction.

###### Proof.

Clearly (iii) implies (ii). Now suppose that $M$ has $M(C_{4})$ as an induced
minor. Let $n$ be the size of a largest circuit that is an induced minor of
$M$. Since $M$ has $M(C_{4})$ as an induced minor, $n\geq 4$. Then, by Lemma
2.1, $M$ has an $n$-element circuit as an induced restriction, that is, $M$
has $M(C_{n})$ as an induced restriction for some $n\geq 4$. ∎

We now give a constructive characterization of binary chordal matroids. In a
matroid $M$, denote a vertical $k$-separation $(X,Y)$ by $(X,G,Y)$ where
$G={\rm cl}_{M}(X)\cap{\rm cl}_{M}(Y)$. For a rank-$r$ binary matroid $M$ that
is viewed as a restriction of $P_{r}$, if $X\subseteq E(P_{r})-E(M)$, we
denote by $M+X$ the matroid $P_{r}|(E(M)\cup X)$.

######  Lemma 2.3.

For some $k\geq 2$, let $(X,G,Y)$ be a vertical $k$-separation of a binary
matroid $M$ where $G=\emptyset$. Then $M$ has $M(C_{4})$ as an induced minor.

###### Proof.

Let $C$ be a smallest circuit of ${\rm cl}_{P_{r}}(M)$ such that $|C\cap({\rm
cl}_{P_{r}}(X)\cap{\rm cl}_{P_{r}}(Y))|=1$ and $C-({\rm cl}_{P_{r}}(X)\cap{\rm
cl}_{P_{r}}(Y))\subseteq X$. Let $\\{z\\}=C\cap({\rm cl}_{P_{r}}(X)\cap{\rm
cl}_{P_{r}}(Y))$, let $a$ and $b$ be distinct elements in $C-z$, and let
$M^{\prime}=(M+z)/(C-\\{a,b,z\\})$ where we do not simplify here after doing
this contraction. Then $\\{a,b,z\\}$ is a triangle of $M^{\prime}$, and, for
some $k^{\prime}\leq k$, the matroid $M^{\prime}$ has a vertical
$k^{\prime}$-separation $(X^{\prime},G^{\prime},Y)$ where
$X^{\prime}=X-(C-\\{a,b,z\\})$ and $G^{\prime}=\\{z\\}$. To see this, observe
that if $|G^{\prime}|>1$, then there is a circuit $C^{\prime}\cup z^{\prime}$
in ${\rm cl}_{P_{r}}(M)$ where $C^{\prime}$ is contained in $C-\\{a,b,z\\}$,
and $\\{z^{\prime}\\}$ is in ${\rm cl}_{P_{r}}(X)\cap{\rm cl}_{P_{r}}(Y)$.
This contradicts the choice of $C$ as a smallest circuit with these
properties. Moreover, there is no element parallel to $z$ in $M^{\prime}$. Let
$D$ be a smallest circuit of $M^{\prime}$ such that $D$ contains $z$ and $D-z$
is contained in $Y$. Note that $D\cup\\{a,b\\}$ is a circuit of $M^{\prime}$.
Moreover, ${\rm cl}_{M^{\prime}}(D\cup\\{a,b,z\\})=D\cup\\{a,b,z\\}$.
Therefore, $M^{\prime}\backslash\\{z\\}$ has an $n$-element circuit as an
induced restriction for some $n\geq 4$. By Theorem 2.2,
$M^{\prime}\backslash\\{z\\}$ has $M(C_{4})$ as an induced minor. It follows
that $M$ has $M(C_{4})$ as an induced minor. ∎

######  Lemma 2.4.

For some $k\geq 2$, suppose $(X,G,Y)$ is a vertical $k$-separation of a binary
chordal matroid $M$. Then $r_{M}(G)=k-1$.

###### Proof.

Suppose $r(G)<k-1$. Then, for $k^{\prime}=k-r(G)$, we see that $k^{\prime}\geq
2$ and $M/G$ has a vertical $k^{\prime}$-separation
$(X^{\prime},G^{\prime},Y^{\prime})$ with $G^{\prime}=\emptyset$. By Lemma
2.3, $M$ has $M(C_{4})$ as an induced minor, a contradiction to Theorem 2.2.
Therefore, $r(G)=k-1$. ∎

In the next two proofs, we allow the matroids to be non-simple and we do not
simplify after contracting. The next result seems unlikely to be new, but we
include a proof for completeness.

######  Lemma 2.5.

If $G$ is a flat of a matroid $N$ and $G-g$ is a modular flat of $N/g$ for
some $g$ in $G$, then $G$ is modular flat of $N$.

###### Proof.

The result is immediate if $g$ is a loop of $N$, so assume $r(\\{g\\})=1$. For
all flats $F$ of $N/g$,

$r_{N/g}(F)+r_{N/g}(G-g)=r_{N/g}(F\cap(G-g))+r_{N/g}(F\cup(G-g)).$ (2.1)

We shall show that, if $H$ is a flat of $N$, then

$r_{N}(H)+r_{N}(G)-r_{N}(H\cap G)-r_{N}(H\cup G)=0.$ (2.2)

Suppose $g\in H$. Then $r_{N/g}(H-g)=r_{N}(H)-1$ and $r_{N/g}((H\cup
G)-g)=r_{N}(H\cup G)-1$. Therefore, since (2.1) holds, so does (2.2).

Now suppose $g\not\in H$. Then $r_{N/g}(H)=r_{N}(H\cup g)-1$ and
$r_{N/g}(H\cap G)=r_{N}((H\cap G)\cup g)-1$. Since $H$ and $G$ are flats of
$N$, it follows that $H\cap G$ is a flat of $N$. Therefore, $r_{N}(H\cup
g)=r_{N}(H)+1$ and $r_{N}((H\cap G)\cup g)=r_{N}(H\cap G)+1$. Thus (2.2) holds
and the lemma is proved. ∎

######  Lemma 2.6.

For some $k\geq 2$, let $(X,G,Y)$ be a vertical $k$-separation of a binary
chordal matroid $M$. Then $G$ is a modular flat of $M|{\rm cl}(X)$ or of
$M|{\rm cl}(Y)$.

###### Proof.

If $k=2$, then, by Lemma 2.4, $r(G)=1$. Moreover, $M$ is a parallel connection
of $M|{\rm cl}(X)$ and $M|{\rm cl}(Y)$. By Theorem 2.2, both of these matroids
are chordal. As $G$ is a single point, it is a modular flat in both $M|{\rm
cl}(X)$ and $M|{\rm cl}(Y)$ and the result holds. Suppose the result holds for
all $k<n$ and let $(X,G,Y)$ be a vertical $n$-separation of $M$. Then, for any
$g$ in $G$, the matroid $M/g$ has a vertical $(n-1)$-separation
$(X-g,G-g,Y-g)$. By the induction assumption, $G-g$ is a modular flat in
either $(M/g)|{\rm cl}(X-g)$ or $(M/g)|{\rm cl}(Y-g)$. Therefore, by Lemma
2.5, it follows that $G$ is a modular flat of $M|{\rm cl}(X)$ or of $M|{\rm
cl}(Y)$. ∎

######  Theorem 2.7.

All binary chordal matroids can be obtained by starting with round binary
chordal matroids and repeatedly taking generalized parallel connections of two
previously constructed matroids across a set that is a modular flat of one of
them.

###### Proof.

Let $M$ be a binary chordal matroid. If $M$ has no vertical $k$-separations
for any $k$, then $M$ is round and the result holds. If $M$ has a vertical
$k$-separation $(X,G,Y)$ for some $k>1$, then, by Lemma 2.6, $M$ is a
generalized parallel connection of $M|{\rm cl}(X)$ and $M|{\rm cl}(Y)$ across
$M|{\rm cl}(G)$, and $G$ is a modular flat of $M|{\rm cl}(X)$ or of $M|{\rm
cl}(Y)$. ∎

##  3\. $GF(q)$-chordal matroids

The goal of this section is to prove Theorem 1.1. Recall that a matroid is
$GF(2)$-chordal if it can be built from binary projective geometries by
repeated generalized parallel connections across projective geometries. In [7,
Theorem 1.3], we showed that the class of $GF(2)$-chordal matroids is closed
under taking induced minors and therefore, the class is also closed under
taking induced restrictions. For a binary matroid $M$, we may uniquely specify
$M$ by describing its complement in the projective geometry $P_{r(M)}$. In
general, Brylawski and Lucas [3] (see also [10, Proposition 10.1.7]) showed
that the complement of any uniquely $GF(q)$-representable matroid $M$ is well
defined in any projective geometry of rank at least $r(M)$. We will first
examine the matroids that have $M(K_{4})$ as an induced minor.

######  Lemma 3.1.

If $M$ is a simple binary matroid with $r(M)=4$ and $|E(M)|>9$, then either
$M$ has $M(C_{4})$ or $M(K_{4})$ as an induced restriction, or $M$ does not
contain $M(K_{4})$ as an induced minor.

###### Proof.

Let $P_{4}$ be the rank-4 binary projective geometry. Suppose $T$ is a largest
subset of $E(P_{4})$ such that $P_{4}|T$ contains $M(K_{4})$ as an induced
minor, but $T$ does not contain one of $M(C_{4})$ or $M(K_{4})$ as an induced
restriction. Certainly, $P_{4}$ does not contain $M(K_{4})$ as an induced
minor and so $|T|<15$. If $|T|\in\\{13,14\\}$, then $P_{4}|T$ certainly has
$M(K_{4})$ as an induced restriction. If $|T|=12$, then $P_{4}\backslash T$ is
either $P_{2}$ or $U_{3,3}$. If $P_{4}\backslash T$ is $P_{2}$, then $P_{4}|T$
has $M(C_{4})$ as an induced restriction. If $P_{4}\backslash T$ is $U_{3,3}$,
then $P_{4}|T$ will again contain $M(K_{4})$ as an induced restriction. If
$|T|=11$, then $P_{4}\backslash T$ is $M(C_{4})$, $U_{4,4}$, or $P_{2}\oplus
U_{1,1}$. When $P_{4}\backslash T$ is $M(C_{4})$, we see that $P_{4}|T\cong
P_{P_{2}}(P_{3},P_{3})$, so it has no element whose contraction gives
$M(K_{4})$. If $P_{4}\backslash T$ is $U_{4,4}$, then $P_{4}|T$ has a plane
with exactly six points, so $P_{4}|T$ has $M(K_{4})$ as an induced
restriction. If $P_{4}\backslash T$ is $P_{2}\oplus U_{1,1}$, then $P_{4}|T$
has $M(C_{4})$ as an induced restriction. If $|T|=10$, then $P_{4}\backslash
T$ is $M(K_{4}-e)$, $M(C_{4})\oplus U_{1,1}$, or $P_{2}\oplus U_{2,2}$. In
each case, $P_{4}|T$ has $M(K_{4})$ as an induced restriction. ∎

######  Lemma 3.2.

If $M/f$ has $M(K_{4})$ as an induced restriction for some $f$ in $E(M)$, then
$M$ has $M(C_{4}),M(K_{4}),$ or $M^{*}(K_{3,3})$ as an induced restriction.

###### Proof.

It suffices to show the result holds for $r(M)=4$ since we may restrict to a
rank-4 flat $F$ such that $(M|F)/f\cong M(K_{4})$. Assume $M$ does not have
any of $M(C_{4}),M(K_{4}),$ or $M^{*}(K_{3,3})$ as an induced restriction.
Since $M/f$ is isomorphic to $M(K_{4})$, it follows that $|E(M)|\geq 7$, and,
by Lemma 3.1, we have $|E(M)|\leq 9$. Certainly $M$ is connected. If $M$ is
not 3-connected, then $M$ is isomorphic to the 2-sum or the parallel
connection of $U_{2,3}$ and $M(K_{4})$. In the former case, $M$ has $M(C_{4})$
as an induced restriction, and, in the latter case, $M$ has $M(K_{4})$ as an
induced restriction. Thus we may assume $M$ is 3-connected. Suppose $M$ is
graphic. Then $M$ is obtained from $M(K_{5})$ by deleting at most two edges.
If two incident edges have been deleted from $K_{5}$, then $M$ is not
3-connected. Therefore $M$ is isomorphic to $M(K_{5}\backslash e)$ for some
edge $e$, or $M$ is isomorphic to $M(\mathcal{W}_{4})$. In the first case, $M$
has $M(K_{4})$ as an induced restriction; in the second case, $M$ has
$M(C_{4})$ as an induced restriction.

We may now assume that $M$ is not graphic. Then $M$ has one of $M^{*}(K_{5})$,
$M^{*}(K_{3,3})$, $F_{7}$, or $F_{7}^{*}$ as a minor by a theorem of Tutte
[13] (see also [10, Theorem 6.6.7]). Since $|E(M)|\leq 9$, we have $M\not\cong
M^{*}(K_{5})$. If $M\cong M^{*}(K_{3,3})$, the result holds. If $r^{*}(M)=3$,
then $M\cong F_{7}^{*}$, and thus $M$ has $M(C_{4})$ as an induced
restriction, a contradiction. If $r^{*}(M)=4$, then, by a result of Seymour
[12] (see also [10, Lemma 12.2.4]), $M$ is isomorphic to either $AG(3,2)$ or
$S_{8}$, and, in each case, $M$ has $M(C_{4})$ as an induced restriction, a
contradiction. By the Splitter Theorem, if $|E(M)|=9$, then $M$ is an
extension of $AG(3,2)$ or $S_{8}$. Since the rank-4 complements of $AG(3,2)$
and $S_{8}$ are $F_{7}$ and $M(K_{4})\oplus U_{1,1}$, respectively, there are
exactly two possible 9-element matroids as extensions of $AG(3,2)$ and
$S_{8}$, that is, $M$ is the rank-4 complement of $M(K_{4})$ or the rank-4
complement of $M(K_{4}\backslash e)\oplus U_{1,1}$. In each case, $M$ has
$M(C_{4})$ as an induced restriction, a contradiction. ∎

To complete the proof of Theorem 1.1, we only need to consider the matroids
with $M^{*}(K_{3,3})$ as an induced minor.

######  Lemma 3.3.

If $M/e$ has $M^{*}(K_{3,3})$ as an induced minor, then $M$ contains one of
$M(C_{4}),M(K_{4}),$ or $M^{*}(K_{3,3})$ as an induced restriction.

###### Proof.

It suffices to show the result holds when $r(M)=5$ since we may restrict to
the relevant rank-5 flat. Assume $M$ does not have any member of
$\\{M(C_{4}),M(K_{4}),M^{*}(K_{3,3})\\}$ as an induced restriction. Let
$e_{1},e_{2},e_{3},e_{4}$ be the standard basis for $P_{4}$. Then we may
assume that the ground set $Z$ of the $M^{*}(K_{3,3})$-restriction of $M/e$ is
$\\{e_{1},e_{2},e_{3},e_{4},e_{1}+e_{2},e_{2}+e_{3},e_{3}+e_{4},e_{1}+e_{4},e_{1}+e_{2}+e_{3}+e_{4}\\}$.
Then the ground set of $M$ may only contain $e$, elements of $Z$, and elements
of the form $e+f$ where $f$ is an element of $Z$. Let $T$ a rank-4 flat of $M$
such that $(M/e)|{\rm cl}_{M/e}(T)\cong M^{*}(K_{3,3})$ and $|T|$ is maximal
with this property. Certainly $|T|<9$. Observe that, for every rank-4 flat $F$
of $M$ that avoids $e$, we have $(M/e)|{\rm cl}_{M/e}(F)\cong M^{*}(K_{3,3})$.

######  3.3.1.

$|T|<8$.

If $|T|=8$, then $M|T$ is isomorphic to a 4-wheel, which has $M(C_{4})$ as an
induced restriction, a contradiction. Thus 3.3.1 holds.

######  3.3.2.

$|T|<7$.

If $|T|=7$, then, to avoid having $M(C_{4})$ as an induced restriction, we may
assume
$T=\\{e_{1},e_{3},e_{4},e_{1}+e_{4},e_{2}+e_{3},e_{3}~{}+~{}e_{4},e_{1}~{}+~{}e_{2}~{}+~{}e_{3}~{}+~{}e_{4}\\}$.
Therefore, $E(M)$ must contain $\\{e,e+e_{2},e+e_{1}+e_{2}\\}$. Look at the
flat containing $\\{e_{3},e_{2}+e_{3},e+e_{2},e\\}$, noting that $e_{2}$ is
absent. Since this flat is not isomorphic to $M(C_{4})$, it must contain
either $e+e_{3}$ or $e+e_{2}+e_{3}$. Suppose that $e+e_{2}+e_{3}$ is present.
Then $M$ contains
$\\{e_{1},e_{1}+e_{4},e_{4},e_{3}+e_{4},e_{3},e+e_{2}+e_{3},e+e_{2},e+e_{1}+e_{2}\\}$
as eight elements of a rank-4 flat $F$ that avoids $e$. By 3.3.1, $|F|\leq 7$,
a contradiction. We deduce that $e+e_{2}+e_{3}$ is absent, and hence $e+e_{3}$
must be present. In this case, $M$ has
$\\{e_{1},e_{4},e_{1}+e_{4},e_{1}+e_{2}+e_{3}+e_{4},e_{2}+e_{3},e+e_{3},e+e_{2},e+e_{1}+e_{2}\\}$
as eight elements of a rank-4 flat that avoids $e$, and again we contradict
3.3.1. We conclude that, 3.3.2 holds.

######  3.3.3.

The set $Z-T$ does not contain a triangle.

Without loss of generality, suppose $Z-T$ contains the triangle
$\\{e_{1},e_{2},e_{1}+e_{2}\\}$. Then $M$ must contain the 4-element circuit
$\\{e,e+e_{1},e+e_{2},e+e_{1}+e_{2}\\}$ as a flat, a contradiction. Therefore,
3.3.3 holds.

######  3.3.4.

$|T|<6$.

If $|T|=6$, then, since $M$ does not have $M(C_{4})$ as an induced restriction
and $Z-T$ does not contain a triangle, we may assume $T$ is missing
$\\{e_{2},e_{1}+e_{2},e_{2}+e_{3}\\}$. Then $M$ contains
$\\{e+e_{2},e+e_{1}+e_{2},e+e_{2}+e_{3}\\}$. Thus $M$ contains
$\\{e_{1},e+e_{1}+e_{2},e+e_{2},e+e_{2}+e_{3},e_{3},e_{3}+e_{4},e_{4},e_{1}+e_{4}\\}$
as eight elements of a rank-4 flat of $M$ that avoids $e$, a contradiction to
3.3.1. Therefore, 3.3.4 holds.

######  3.3.5.

$|T|<5$.

If $|T|=5$, then, since $M$ does not have $M(C_{4})$ as an induced restriction
and $Z-T$ does not contain a triangle, we may assume $T$ is missing one of the
following four sets of points.

  1. (a)

$\\{e_{2},e_{3},e_{3}+e_{4},e_{1}+e_{2}\\}$

  2. (b)

$\\{e_{2},e_{2}+e_{3},e_{3}+e_{4},e_{1}+e_{2}\\}$

  3. (c)

$\\{e_{1},e_{2},e_{3}+e_{4},e_{1}+e_{2}+e_{3}+e_{4}\\}$

In case (a), $M$ has
$\\{e_{1},e+e_{1}+e_{2},e+e_{2},e+e_{3},e_{2}+e_{3},e_{1}+e_{2}+e_{3}+e_{4},e_{1}+e_{4},e_{4}\\}$
as eight elements of a rank-4 flat of $M$ that avoids $e$, which contradicts
3.3.1. In case (b),
$\\{e_{1},e+e_{1}+e_{2},e+e_{2},e+e_{2}+e_{3},e_{3},e_{4},e_{1}+e_{4}\\}$
spans a rank-4 flat $F$ of $M$ that avoids $e$ and has at least seven
elements, which contradicts 3.3.2. In case (c), $M$ has
$\\{e+e_{2},e+e_{2}+e_{3},e_{3},e_{4},e+e_{1},e_{1}+e_{2}\\}$ contained in a
rank-4 flat of $M$ avoiding $e$, which contradicts 3.3.4. Therefore, 3.3.5
holds.

If $|T|=4$, then, as $T$ must be independent and $Z-T$ contains no triangles,
we may assume that $T=\\{e_{1},e_{1}+e_{2},e_{3},e_{1}+e_{2}+e_{3}+e_{4}\\}$.
This implies that $M$ has
$\\{e_{1},e+e_{2},e+e_{2}+e_{3},e_{3},e+e_{3}+e_{4}\\}$ spanning a rank-4 flat
of $M$ that avoids $e$, a contradiction to 3.3.5. ∎

The next result establishes a connection between the excluded induced minors
of a class of matroids and the excluded induced restrictions of that class of
matroids.

######  Lemma 3.4.

Suppose $\mathcal{N}$ is a class of matroids such that if a matroid $M$ has an
element $e$ such that $M/e$ is isomorphic to a member of $\mathcal{N}$, then
$M$ has a member of $\mathcal{N}$ as an induced restriction. Let
$\mathcal{N}^{\prime}$ be the class of induced-minor-minimal members of
$\mathcal{N}$. Then the class of matroids with no member of
$\mathcal{N}^{\prime}$ as an induced minor coincides with the class of
matroids with no member of $\mathcal{N}$ as an induced restriction.

###### Proof.

Clearly if $M$ has a member of $\mathcal{N}$ as an induced restriction, then
$M$ has a member of $\mathcal{N}^{\prime}$ as an induced minor. Conversely,
suppose $M$ has a member of $\mathcal{N}^{\prime}$ as an induced minor. We may
assume that $M$ has no member of $\mathcal{N}^{\prime}$ as an induced
restriction. Then $M$ has a flat $F$ and a nonempty independent set $T$ such
that $(M|F)/T$ is isomorphic to a member of $\mathcal{N}^{\prime}$ and hence a
member of $\mathcal{N}$. We argue by induction on $|T|$ that $M$ has a member
of $\mathcal{N}$ as an induced restriction.

When $|T|=1$, we see that the assertion holds by the definition of
$\mathcal{N}$. Now assume the result holds for $|T|<n$, and let $|T|=n\geq 2$.
Let $M_{1}=M|F$, and take $e$ in $T$. Then $(M_{1}/e)/(T-e)$ is isomorphic to
a member of $\mathcal{N}$. Thus, by the induction assumption, $M_{1}/e$ has a
member of $\mathcal{N}$ as an induced restriction. Then, by the induction
assumption again, $M_{1}$ has a member of $\mathcal{N}$ as an induced
restriction, and hence $M$ has a member of $\mathcal{N}$ as an induced
restriction. ∎

###### Proof of Theorem 1.1.

Let $\mathcal{N}=\\{M(C_{n}):n\geq 4\\}\cup\\{M(K_{4}),M^{*}(K_{3,3})\\}$.
Then, by Lemmas 2.1, 3.2, and 3.3, the set $\mathcal{N}$ has the property that
if $M/e$ is isomorphic to a member of $\mathcal{N}$, then $M$ has a member of
$\mathcal{N}$ as an induced minor. Since $\\{M(C_{4}),M(K_{4})\\}$ is the set
of induced-minor-minimal members of $\mathcal{N}$, the result holds by Lemma
3.4. ∎

Next we prove the analog of Theorem 1.1 when $q>2$. Although the result is
rather unattractive, we include it for completeness. The equivalence of (i)
and (ii) was shown in [7]. Because $U_{3,q+2}$ is $GF(q)$-representable if and
only if $q$ is even, when $q$ is odd, we can omit $U_{3,q+2}$ from (ii). This
corrects a small error in Theorem 1.4 of [7]. Note that some matroids in (iii)
may be excluded as they fail to be $GF(q)$-representable. But the problem of
determining precisely which uniform matroids are $GF(q)$-representable is
open. For results on exactly which uniform matroids are known to be
$GF(q)$-representable, we direct the reader to [1, 2, 8, 9] (see also [10,
Conjecture 6.5.20]). Recall that the class of $GF(q)$-chordal matroids is the
class of matroids that can be obtained by a sequence of generalized parallel
connections across projective geometries over $GF(q)$ starting with projective
geometries over $GF(q)$.

######  Theorem 3.5.

When $q>2$, the following are equivalent for a $GF(q)$-representable matroid
$M$.

  1. (i)

$M$ is $GF(q)$-chordal.

  2. (ii)

$M$ has no member of $\\{U_{2,k}:2<k\leq q\\}\cup\\{U_{3,q+2}\\}$ as an
induced minor.

  3. (iii)

$M$ has no member of $\\{U_{n,n+1}:n\geq 2\\}\cup\\{U_{2+t,k+t}:4\leq k\leq
q\text{ and }0\leq t\leq q-3\\}\cup\\{U_{3,q+2}\\}$ as an induced restriction.

######  Lemma 3.6.

Suppose $M$ is $GF(q)$-representable. If $M/e$ has $U_{2,n}$ as an induced
minor for some $n$ with $3\leq n\leq q$, then $M$ has a member of
$\\{U_{2,k}:3\leq k\leq q\\}\cup\\{U_{3,n+1}\\}$ as an induced restriction.

###### Proof.

It suffices to show that the result holds for $r(M)=3$ since we may restrict
to the relevant rank-3 flat. Let $E(M/e)=\\{x_{1},x_{2},\dots,x_{k}\\}$. If
$M$ has a $(q+1)$-point line, then $e$ must be on that line, otherwise, $M/e$
would be $U_{2,q+1}$. Without loss of generality, suppose ${\rm
cl}(\\{e,x_{k}\\})$ is a $(q+1)$-point line, $L_{1}$. Then the line
$L_{2}={\rm cl}(\\{x_{1},x_{2}\\})$ must intersect $L_{1}$ at a point
different from $e$. Therefore, $L_{2}$ is either isomorphic to $U_{2,k}$ for
some $k$ with $3\leq k\leq q$, in which case the result holds, or $L_{2}$ is a
$(q+1)$-point line, and $M/e$ is isomorphic to $U_{2,q+1}$, a contradiction.
Therefore, we may assume that $M$ has no $(q+1)$-point lines. Let $X$ be a
3-element subset of $E(M)$. Since $M$ has no member of $\\{U_{2,k}:3\leq k\leq
q\\}$ as an induced restriction, and $M$ has no $(q+1)$-point lines, it
follows that $X$ is independent. Therefore, $M$ is isomorphic to $U_{3,n+1}$.
∎

To complete the proof Theorem 3.5, we consider the following general result
for uniform matroids.

######  Lemma 3.7.

Let $M$ be $GF(q)$-representable for some $q>2$ and suppose $M/e\cong U_{r,n}$
for some $r$ and $n$ with $2<r<n$. Then $M$ has a member of
$\\{U_{2+t,k+t}:3\leq k\leq q\text{ and }0\leq t\leq
q-3\\}\cup\\{U_{r,n},U_{r+1,n+1}\\}$ as an induced restriction.

###### Proof.

Assume the result fails. Observe that, since $U_{2,q+2}$ is not
$GF(q)$-representable, we must have $n\leq q+r-1$. Next note that if $M$ has a
hyperplane $H_{0}$ that avoids $e$, then $M|H_{0}$ must be isomorphic to a
uniform matroid for if $H_{0}$ contains a non-spanning circuit $C$, then $M/e$
must also contain $C$ as a non-spanning circuit. Moreover, $H_{0}$ can contain
at most $n$ elements as $|E(M/e)|=n$. Therefore, $M|H_{0}$ is isomorphic to
$U_{r,s}$ for some $s$ with $r\leq s\leq n$. Suppose that $H_{0}$ can be
chosen so that $s>r$. If $s=n$, then $M$ has $U_{r,n}$ as an induced
restriction, a contradiction. Thus we may suppose that $s<n$. Observe that if
$r>q-1$, then, since $U_{q,q+2}$ is not $GF(q)$-representable, we must have
$n=r+1$, so $s=n$, a contradiction. Thus we may assume that $r\leq q-1$. Then
we obtain a contradiction by taking $t=r-2$ and $k=s-r+2$ for then $t\leq q-3$
and $k<n-r+2\leq(q+r-1)-r+2=q+1$. Hence we may assume that every hyperplane
that avoids $e$ is an independent set of size $r$.

Let $E(M/e)=\\{x_{1},x_{2},\dots,x_{n}\\}$. If $M$ has a $(q+1)$-point line,
this line must contain $e$ as $M/e$ does not have a $(q+1)$-point line.
Without loss of generality, suppose ${\rm cl}_{M}(\\{e,x_{n}\\})$ is a
$(q+1)$-point line, $L$. Then ${\rm cl}_{M}(\\{x_{1},x_{2},\dots,x_{r}\\})$ is
a hyperplane $H$ of $M$ that meets $L$ at a point different from $e$.
Therefore $H$ is a hyperplane that avoids $e$ and contains a circuit of $M$, a
contradiction. We conclude that $M$ has no $(q+1)$-point lines. Therefore,
either $e$ is contained in a $U_{2,k}$ induced restriction for some $k$ with
$3\leq k\leq q$, and the result holds, or every circuit containing $e$ has
size $r+2$. Let $X$ be a subset of $E(M)-e$. If $|X|<r+1$, then $X$ is
certainly independent as $X$ must be independent in $M/e$. Suppose $|X|=r+1$
and that $X$ is dependent. Then ${\rm cl}_{M}(X)$ is a hyperplane that avoids
$e$ and contains a circuit of $M$, a contradiction. Therefore, $X$ is an
independent set of size $r+1$, and $M$ is isomorphic to $U_{r+1,n+1}$. ∎

###### Proof of Theorem 3.5.

It suffices to show the equivalence of (ii) and (iii). Let
$\mathcal{N}=\\{U_{n,n+1}:n\geq 2\\}\cup\\{U_{2+t,k+t}:4\leq k\leq q\text{ and
}0\leq t\leq q-3\\}\cup\\{U_{3,q+2}\\}$. Then, since $U_{4,q+3}$ is not
$GF(q)$-representable for any $q$, it follows by Lemmas 3.6 and 3.7 that
$\mathcal{N}$ has the property that if $M/e$ is isomorphic to a member of
$\mathcal{N}$, then $M$ has a member of $\mathcal{N}$ as an induced minor.
Since $\\{U_{2,k}:3\leq k\leq q\\}\cup\\{U_{3,q+2}\\}$ is the set of induced-
minor-minimal members of $\mathcal{N}$, the result holds by Lemma 3.4.

Note if $M$ has $U_{2+t,k+t}$ as an induced restriction for some $t$ and $k$
with $t\geq q-2$ and $k\geq 4$, then $M$ has $U_{q,q+2}$ as a minor, so $M$ is
not $GF(q)$-representable, a contradiction. ∎

Theorem 1.2 follows from Theorem 3.5 and a result of Ball [1] (see also [10,
Theorem 6.5.21]), which establishes precisely when a uniform matroid is
$GF(p)$-representable for $p$ a prime.

When $p=3$, Theorem 1.2 gives the following.

######  Corollary 3.8.

The following are equivalent for a ternary matroid $M$.

  1. (i)

$M$ is $GF(3)$-chordal.

  2. (ii)

$M$ has no $M(C_{3})$ induced minor.

  3. (iii)

$M$ has no member of $\\{M(C_{n}):n\geq 3\\}$ as an induced restriction.

Similarly, Theorem 3.5 gives the following when $q=4$.

######  Corollary 3.9.

The following are equivalent for a matroid $M$ that is representable over
$GF(4)$.

  1. (i)

$M$ is $GF(4)$-chordal.

  2. (ii)

$M$ has no member of $\\{U_{2,3},U_{2,4},U_{3,6}\\}$ as an induced minor.

  3. (iii)

$M$ has no member of $\\{U_{n,n+1}:n\geq
2\\}\cup\\{U_{2,4},U_{3,5},U_{3,6}\\}$ as an induced restriction.

##  4\. Perfect Elimination Ordering

In this section, we will prove Theorem 1.4. Recall that a perfect elimination
ordering of cocircuits of a matroid $M$ is a collection of sets
$C_{1}^{*},C_{2}^{*},\dots,C_{r}^{*}$ such that, for all $i$ in $[r]$, the set
$C_{i}^{*}$ is a cocircuit of the matroid $M_{i}=M\backslash(C_{1}^{*}\cup
C_{2}^{*}\cup\dots\cup C_{i-1}^{*})$ and $M|{\rm cl}_{M_{i}}(C_{i}^{*})$ is a
projective geometry. Observe that $M|{\rm cl}_{M_{i}}(C_{i}^{*})=M_{i}|{\rm
cl}_{M_{i}}(C_{i}^{*})$ and that $E(M_{i})$ is a flat of $M$ of rank
$r(M)-i+1$. We omit the straightforward proof of the next result.

######  Lemma 4.1.

Projective geometries have a perfect elimination ordering of cocircuits.

We now prove the second main result of the paper.

###### Proof of Theorem 1.4.

Suppose $M$ is a $GF(q)$-chordal matroid that does not have a perfect
elimination ordering of cocircuits and has $|E(M)|$ a minimum among such
matroids. Since $M$ is $GF(q)$-chordal, $M$ may be written as a
$P_{N}(M_{1},M_{2})$ where $N$ is a projective geometry and $M_{2}$ is a
projective geometry. Therefore, $M_{2}$ has a perfect elimination ordering of
cocircuits. Choose $C_{1}^{*}$ to be a cocircuit of $M_{2}$ that avoids
$E(N)$. By the minimality of $M$, the matroid $M\backslash C_{1}^{*}$ has a
perfect elimination ordering of cocircuits
$C_{2}^{*},C_{3}^{*},\dots,C_{r}^{*}$. Therefore, $M$ has a perfect
elimination ordering.

Suppose $M$ has a perfect elimination ordering of cocircuits labeled
$C_{1}^{*},C_{2}^{*},\dots,C_{r}^{*}$. Let $M_{1}=M$, and let
$M_{i}=M\backslash(C_{1}^{*}\cup C_{2}^{*}\cup\dots\cup C_{i-1}^{*})$ for each
$i$ with $2\leq i\leq r$. Certainly, $M_{r}$ is a projective geometry, and
therefore is $GF(q)$-chordal. Let $k$ be the smallest integer such that
$M_{k}$ is not $GF(q)$-chordal. Then $M_{k+1}$ is $GF(q)$-chordal, $M_{k}|{\rm
cl}_{M_{k}}(C_{k}^{*})$ is a projective geometry, and $M_{k+1}$ is a
hyperplane of $M_{k}$. Thus $E(M_{k+1})\cap E(M_{k}|{\rm
cl}_{M_{k}}(C_{k}^{*}))$ is a flat, $N$, of a projective geometry and so $M|N$
is a projective geometry. Hence $M_{k}$ is a generalized parallel connection
of $GF(q)$-chordal matroids across a projective geometry, namely
$P_{M|N}(M_{k+1},M|{\rm cl}_{M_{k}}(C_{k}^{*}))$. Thus, $M_{k}$ is
$GF(q)$-chordal, a contradiction. ∎

On combining Theorems 1.1 and 1.4, we obtain the following.

######  Corollary 4.2.

The following are equivalent for a binary matroid $M$.

  1. (i)

$M$ is $GF(2)$-chordal.

  2. (ii)

$M$ has no member of $\\{M(C_{4}),M(K_{4})\\}$ as an induced minor.

  3. (iii)

$M$ has no member of $\\{M(C_{n}):n\geq 4\\}\cup\\{M(K_{4}),M^{*}(K_{3,3})\\}$
as an induced restriction.

  4. (iv)

$M$ has a perfect elimination ordering of cocircuits.

## References

  * [1] Ball, S., On sets of vectors of a finite vector space in which every subset of basis size is a basis, J. Eur. Math. Soc. 14 (2012), 733–748
  * [2] Ball, S., and De Beule, J., On sets of vectors of a finite vector space in which every subset of basis size is a basis II, Des. Codes Cryptogr. 65 (2012), 5–14
  * [3] Brylawski, T.H., and Lucas, D., Uniquely representable combinatorial geometries, Teorie Combinatorie (Proc. 1973 Internat. Colloq.), pp. 83-104, Accademia Nazionale dei Lincei, Rome, 1976
  * [4] Cordovil, R., Forge, D., and Klein, S., How is a chordal graph like a supersolvable binary matroid?, Discrete Math. 288 (2004), 167–172.
  * [5] Diestel, R., Graph Theory, Third Edition, Springer, Berlin, 2005.
  * [6] Dirac, G.A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76.
  * [7] Douthitt, J.D., and Oxley, J., Chordal matroids arising from generalized parallel connections, Adv. in Appl. Math. 153 (2024) 102631, 10 pp.
  * [8] Hirschfeld, J.W.P., and Storme, L., The packing problem in statistics, coding theory and finite projective spaces: update 2001, Finite Geometries, 201–246, Dev. Math. 3, Kluwer Acad. Publ., Dordrecht, 2001.
  * [9] Hirschfeld, J.W.P., and Thas, J.A., General Galois Geometries, Oxford University Press, New York, 1991.
  * [10] Oxley, J., Matroid Theory, Second Edition, Oxford University Press, New York, 2011.
  * [11] Rose, D.J., Triangulated graphs and the elimination process, J. Math. Anal. Appl. 32 (1970), 597–609.
  * [12] Seymour, P.D., Minors of 3-connected matroids. European J. Combin. 6 (1985), 375–382
  * [13] Tutte, W.T., Matroids and graphs, Trans. Amer. Math. Soc. 90 (1959), 527–552.