# Recovering a Magnitude-Symmetric Matrix from its Principal Minors

Victor-Emmanuel Brunel, John Urschel

###### Abstract.

We consider the inverse problem of finding a magnitude-symmetric matrix
(matrix with opposing off-diagonal entries equal in magnitude) with a
prescribed set of principal minors. This problem is closely related to the
theory of recognizing and learning signed determinantal point processes in
machine learning, as kernels of these point processes are magnitude-symmetric
matrices. In this work, we prove a number of properties regarding sparse and
generic magnitude-symmetric matrices. We show that principal minors of order
at most $\ell$, for some invariant $\ell$ depending only on principal minors
of order at most two, uniquely determines principal minors of all orders. In
addition, we produce a polynomial-time algorithm that, given access to
principal minors, recovers a matrix with those principal minors using only a
quadratic number of queries. Furthermore, when principal minors are known only
approximately, we present an algorithm that approximately recovers a matrix,
and show that the approximation guarantee of this algorithm cannot be improved
in general.

##  1\. Introduction

In this paper, we study an algebraic problem that is inherently related to the
statistical properties of finite determinantal point processes (DPPs). A DPP
is a random subset of a finite ground set whose probability distribution is
characterized by the principal minors of some fixed matrix. DPPs emerge
naturally in many probabilistic settings such as random matrices and
integrable systems [3], and have also recently attracted interest in machine
learning for their ability to model random choices while being tractable and
mathematically elegant [14]. Given a finite set, say, $[N]=\\{1,\ldots,N\\}$
where $N$ is a positive integer, a DPP is a random subset $Y\subseteq[N]$ such
that $P(S\subseteq Y)=\det(K_{S})$, for all fixed $S\subseteq[N]$, where
$K\in\mathbb{R}^{N\times N}$ is a given matrix called the kernel of the DPP
and $K_{S}=(K_{i,j})_{i,j\in S}$ is the principal submatrix of $K$ associated
with the set $S$. Assumptions on $K$ that yield the existence of a DPP can be
found in [5] and it is easily seen that uniqueness of the DPP is then
automatically guaranteed. For instance, if $I-K$ is invertible ($I$ being the
identity matrix), then $K$ is the kernel of a DPP if and only if $K(I-K)^{-1}$
is a $P_{0}$-matrix, i.e., all its principal minors are nonnegative (see [11]
for properties of $P_{0}$-matrices). When $I-K$ is invertible, the DPP is also
an $L$-ensemble, with probability mass function given by
$P(Y=S)=\det(L_{S})/\det(I+L)$, for all $S\subseteq[N]$, where $L=K(I-K)^{-1}$
[3, Theorem 5.1]. DPPs with a symmetric kernel have attracted a great deal of
interest in machine learning because they satisfy a property called negative
association, which models repulsive interactions between items [2]. For
instance, when applied to recommender systems, DPPs enforce diversity in the
items within one basket [7]. Recently, DPPs with non-symmetric kernels have
also gained interest in the machine learning community [1, 5, 6, 17].

From a statistical point of view, DPPs raise two essential questions. First,
what kernels are equivalent, in the sense that they give rise to one and the
same DPP? Second, given observations of independent realisations of a DPP, how
to recover its kernel (which, as foreseen by the first question, is not
necessarily unique)? These two questions are directly related to the principal
minor assignment problem (PMA). Given a class of matrices, (1) decide if there
exists a matrix with a prescribed list of principal minors, and, if such a
matrix does exist, (2) find one such matrix. While the first task is
theoretical in nature, the second one is algorithmic and should be solved
relatively quickly and using as few queries of the prescribed principal minors
as possible.

(PMA) is well understood for symmetric matrices. Given a symmetric matrix
$K_{0}\in\mathbb{R}^{N\times N}$, the set of symmetric matrices with the same
list of principal minors as $K_{0}$ is exactly given by all the matrices of
the form $DK_{0}D$ for some diagonal matrix $D$ with $1$ and $-1$ on its
diagonal [16]. Moreover, given access to the list of principal minors of
$K_{0}$, a polynomial-time algorithm that finds a solution is given in [18],
using combinatorial properties of the sparsity graph of $K_{0}$, which can be
deduced from its principal minors. In [21], by analyzing the cycle space of
the sparsity graph, a graph invariant $\ell$ called cycle sparsity was
considered, and it was shown that principal minors of order at most $\ell$
uniquely determine principal minors of all orders. This led to a polynomial-
time algorithm that computes a solution using principal minors of minimal
length, and an optimal (w.r.t. sample complexity) algorithm for learning the
kernel of a symmetric DPP from samples – i.e., when only a random noisy
version of the principal minors is available – under some mild separability
assumptions.

Classes containing non-symmetric matrices have also attracted some interest,
yet the problem is significantly harder in general. A matrix
$K\in\mathbb{R}^{N\times N}$ is called irreducible if there is no proper
subset $S\subset[N]$ such that either $K_{S,\bar{S}}$ or $K_{\bar{S},S}$ is
zero, where $\bar{S}$ is the complement of $S$ and, for all subsets
$S,T\subseteq[N]$, $K_{S,T}$ is the submatrix of $K$ obtained by keeping only
the rows and the columns whose indices are in $S$ and $T$ respectively. A
matrix $K$ is called HL-indecomposable if for all subsets $S\subset[N]$ with
$2\leq|S|\leq N-2$, the matrix $K_{S,\bar{S}}$ has rank at least two. In [15,
Theorem 1], Loewy proved the following. Let
$K,K^{\prime}\in\mathbb{R}^{N\times N}$ (or more generally, in $F^{N\times N}$
for an arbitrary field $F$), such that $K$ is irreducible and HL-
indecomposable. Then, $K$ and $K^{\prime}$ have the same principal minors if
and only if there exists an invertible diagonal matrix $D$ such that either
$K^{\prime}=DKD^{-1}$ or $K^{\prime}=DK^{\top}D^{-1}$. In [8], the authors
consider the class of dense matrices whose principal submatrices all have
dense Schur complements (i.e., that only contain nonzero entries) and design
an iterative algorithm to find a solution in polynomial time. The case of
dense skew-symmetric matrices was studied in [4], where the authors improved
on the more general results of Hartfiel and Loewy [9, 15] for this specific
class of matrices. In the context of learning signed DPPs, [5] considers
matrices that are symmetric in magnitudes, i.e., $|K_{i,j}|=|K_{j,i}|$, for
all $i,j\in[N]$. Such matrices are relevant in machine learning applications
because they have much more modeling power than symmetric matrices for DPPs.
An essential assumption made in [5] is that $K$ is dense (all off-diagonal
entries non-zero), which significantly simplifies the analysis. In this work,
we consider matrices that are symmetric in magnitudes, as in [5], but we do
not assume that the matrices are dense. In this more general setting, we must
account for different sparsity structures, which also necessitates a
combinatorial approach.

###  1.1. Our contributions

We treat both theoretical and algorithmic questions related to recovering a
magnitude-symmetric matrix (a matrix $K$ satisfying $|K_{i,j}|=|K_{j,i}|$ for
all $i,j\in[N]$) from its principal minors. First, in Section 2 we define the
set of magnitude-symmetric matrices under consideration (sparse matrices with
a mild genericity condition on cycles of length four), formally state the
questions of interest, make a number of preliminary observations using
principal minors of low order, and show key connections to the theory of edge-
wise charged ($\epsilon(e)$ equals $+1$ or $-1$ for all edges $e$)
graphs111Such graphs are typically called “signed graphs.” However, in
addition to the signing of edges of a graph, we also consider the signing of
non-zero entries of a matrix. To avoid ambiguity, we refer to the former as
the “charge” of an edge, and save the term “sign” exclusively for entries of a
matrix.. In Section 3, given a charged graph, we prove a number of
combinatorial properties regarding cycle bases for the span of positive cycles
(cycles with an even number of edges signed $-1$). In Section 4 we show that,
for a given magnitude-symmetric matrix $K$, the principal minors of length at
most $\ell$, for some graph invariant $\ell$ depending only on principal
minors of order one and two, uniquely determine principal minors of all
orders, and that this quantity $\ell$ is tight (Theorem 1). Finally, in
Section 5 we describe an efficient algorithm that, given the principal minors
of a magnitude-symmetric matrix, computes a matrix with those principal
minors. This algorithm queries only $O(N^{2})$ principal minors, all of a
bounded order that depends solely on the sparsity of the matrix (Theorem 2).
In addition, in Subsection 5.3 we also consider the question of recovery when
principal minors are only known approximately, and show that a modification of
the aforementioned efficient algorithm, for sufficiently generic matrices and
sufficiently small error, recovers the matrix almost exactly (Theorem 3).
Recovery from approximate principal minors is directly related to learning
signed DPPs, as the principal minors of the kernel of a DPP can be well-
approximated by independent samples with high probability (using the method of
moments).

###  1.2. Notation and Definitions

For any number $N\in\mathbb{N}$, let $[N]=\\{1,2,\ldots,N\\}$ and
$\mathbb{R}^{N\times N}$ be the set of all $N\times N$ real matrices. In this
work, we consider matrices $K\in\mathbb{R}^{N\times N}$ satisfying
$|K_{i,j}|=|K_{j,i}|$ for $i,j\in[N]$, which we refer to as magnitude-
symmetric matrices. If $K\in\mathbb{R}^{N\times N}$ and $S\subseteq[N]$,
$K_{S}:=(K_{i,j})_{i,j\in S}$, and $\Delta_{S}(K):=\det K_{S}$ is the
principal minor of $K$ associated with the set $S$ ($\Delta_{\emptyset}(K)=1$
by convention). When it is clear from the context, we simply write
$\Delta_{S}$ instead of $\Delta_{S}(K)$, and for sets of order at most four,
we replace the set itself by its elements, e.g., write $\Delta_{\\{1,2,3\\}}$
as $\Delta_{1,2,3}$. Similarly, when considering the set difference between a
set $S$ and some small set of elements, we may again replace the set by its
elements, e.g., write $\Delta_{S\backslash\\{1,2,3\\}}$ as
$\Delta_{S\backslash 1,2,3}$.

In addition, we recall a number of relevant graph-theoretic definitions. In
this work, all graphs $G=(V,E)$ are simple, undirected graphs, i.e., $V$ is a
nonempty finite set and $E$ is a collection of subsets of $V$ of order two.
The vertex set and the edge set of a graph $G$ are denoted by $V(G)$ and
$E(G)$, respectively. Given a graph $G=(V,E)$, a subgraph $H$ of $G$, denoted
$H\subseteq G$, is a graph $H$ with $V(H)\subseteq V$ and
$E(H)\subseteq\\{\\{i,j\\}:i,j\in V(H),\\{i,j\\}\in E\\}$. If $S\subseteq V$,
the subgraph of $G$ induced by $S$, denoted $G[S]$, is the subgraph
$H\subseteq G$ with $V(H)=S$ and $E(H)=\\{\\{i,j\\}:i,j\in S,\\{i,j\\}\in
E\\}$. An articulation point or cut vertex of a graph $G$ is a vertex whose
removal disconnects the graph. A graph $G$ is said to be two-connected if it
has at least two vertices and has no articulation points. A maximal two-
connected subgraph $H$ of $G$ is called a block of $G$. If a block $H$ is of
order two, we say $H$ is a trivial block (as $H$ contains no cycles). Given a
graph $G$, a cycle $C$ is a subgraph of $G$ in which every vertex of $C$ has
even degree (within $C$)222A cycle $C$ may have several connected components..
A simple cycle $C$ is a connected subgraph of $G$ in which every vertex of $C$
has degree two. For simplicity, we may sometimes describe $C$ by a traversal
of its vertices along its edges, i.e., $C=i_{1}\;i_{2}\;...\;i_{k}\;i_{1}$. In
this description, we have the choice of both the start vertex and the
orientation of the cycle. A simple cycle $C$ of a graph $G$ is not necessarily
induced, i.e., it does not necessarily hold that $C=G[V(C)]$, and while the
cycle itself has all vertices of degree two, this cycle may contain some
number of chords in the original graph $G$, and we denote this set of chords
by $\gamma(C):=E(G[V(C)])\backslash E(C)$.

Given any subgraph $H$ of $G$, we can associate with $H$ an incidence vector
$\chi_{H}\in\textsf{GF}(2)^{m}$, $m=|E|$, where $\chi_{H}(e)=1$ if and only if
$e\in E(H)$, and $\chi_{H}(e)=0$ otherwise. Here, $\textsf{GF}(2)$ is the
field with two elements. Given two subgraphs $H_{1},H_{2}\subseteq G$, we
define their sum $H_{1}+H_{2}$ as the graph containing all edges in exactly
one of $E(H_{1})$ and $E(H_{2})$ (i.e., their symmetric difference) and no
isolated vertices. This corresponds to the graph resulting from the sum of
their incidence vectors: $\chi_{H_{1}+H_{2}}=\chi_{H_{1}}+\chi_{H_{2}}$. The
cycle space of $G$ is given by

$\mathcal{C}(G)=\text{span}\\{\chi_{C}\,|\,C\text{ is a cycle of
}G\\}\subseteq\textsf{GF}(2)^{m}.$

It has dimension $\nu:=m-N+\kappa(G)$, where $\kappa(G)$ denotes the number of
connected components of $G$. The quantity $\nu$ is commonly referred to as the
cyclomatic number or circuit rank. The cycle sparsity $\ell$ of the graph $G$
is the smallest number for which the set of incidence vectors $\chi_{C}$ of
cycles of edge length at most $\ell$ spans $\mathcal{C}(G)$.

In this work, we require the use and analysis of graphs $G=([N],E)$ endowed
with a linear Boolean function $\epsilon$ that maps subgraphs of $G$ to $\pm
1$, i.e., $\epsilon(e)\in\\{-1,+1\\}$ for all $e\in E(G)$ and

$\epsilon(H)=\prod_{e\in E(H)}\epsilon(e)$

for all subgraphs $H$. We note that for all subgraphs $H_{1},H_{2}$ of $G$,
$\epsilon(H_{1}+H_{2})=\epsilon(H_{1})\epsilon(H_{2})$. The graph $G$ combined
with a linear Boolean function $\epsilon$ is denoted by $G=([N],E,\epsilon)$
and referred to as a charged graph. If $\epsilon(H)=+1$ (resp.
$\epsilon(H)=-1$), then we say the subgraph $H$ is positive (resp. negative).
For simplicity, we often denote $\epsilon(\\{i,j\\})$, $\\{i,j\\}\in E(G)$, by
$\epsilon_{i,j}$. Given a magnitude-symmetric matrix $K\in\mathbb{R}^{N\times
N}$, we define the charged sparsity graph of $K$ as $G_{K}=([N],E,\epsilon)$,
where

$E:=\\{i,j\in[N]\,|\,i\neq j,\,|K_{i,j}|\neq
0\\},\qquad\epsilon(\\{i,j\\}):=\text{sgn}(K_{i,j}K_{j,i}),$

and when clear from context, we simply write $G$ instead of $G_{K}$. We define
the span of the incidence vectors of positive cycles as

$\mathcal{C}^{+}(G)=\text{span}\\{\chi_{C}\,|\,C\text{ is a cycle of
}G,\,\epsilon(C)=+1\\}.$

As we will see, when $H$ is a block, the space $\mathcal{C}^{+}(H)$ is spanned
by positive simple cycles (Proposition 2). We define the simple cycle sparsity
$\ell_{+}$ of $\mathcal{C}^{+}(G)$, for a two-connected graph $G$, to be the
smallest number for which the set of incidence vectors $\chi_{C}$ of positive
simple cycles of edge length at most $\ell_{+}$ spans $\mathcal{C}^{+}(G)$. If
$G$ is not two-connected, then we define $\ell_{+}$ of $\mathcal{C}^{+}(G)$ to
be the maximum simple cycle sparsity of $\mathcal{C}^{+}(H)$ over all blocks
$H$ of $G$. If $G$ is a trivial block or if it contains no blocks, then, for
simplicity, we set $\ell_{+}=2$ (rather than $\ell+=0$, which would follow
from the above definition). The study of bases of $\mathcal{C}^{+}(H)$, for
blocks $H$, consisting of incidence vectors of simple cycles constitutes the
major graph-theoretic subject of this work, and has connections to the
recovery of a magnitude-symmetric matrix from its principal minors.

##  2\. Principal Minors and Magnitude-Symmetric Matrices

In this section, we formally describe the problems/questions of interest and
make a number of basic observations that motivate the remainder of this work.
Using only principal minors of order one and two, the quantities $K_{i,i}$,
$|K_{i,j}|$, and the charged sparsity graph $G_{K}$ can be computed
immediately, as $K_{i,i}=\Delta_{i}$ for $i\in[N]$, and

$|K_{i,j}|=\sqrt{|\Delta_{i}\Delta_{j}-\Delta_{i,j}|}\quad\text{ and
}\quad\epsilon_{i,j}=\text{sgn}(\Delta_{i}\Delta_{j}-\Delta_{i,j})\text{ for
$i\neq j$.}$

The main focus of this work is to obtain further information on $K$ using
principal minors of order greater than two, identify which principal minors
uniquely determine $K$ (up to some equivalence class), and use this
information to efficiently recover $K$ from its principal minors. To avoid the
unintended cancellation of terms in a principal minor, in what follows we
assume that $K$ is generic in the sense that it satisfies the following
condition.

######  Condition 1.

If $K_{i,j}K_{j,k}K_{k,\ell}K_{\ell,i}\neq 0$ for some distinct
$i,j,k,\ell\in[N]$, then

  * (i)

$|K_{i,j}K_{k,\ell}|\neq|K_{j,k}K_{\ell,i}|$;

  * (ii)

For each $\phi_{1},\phi_{2},\phi_{3}\in\\{-1,1\\}$,

$\phi_{1}K_{i,j}K_{j,k}K_{k,\ell}K_{\ell,i}+\phi_{2}K_{i,j}K_{j,\ell}K_{\ell,k}K_{k,i}+\phi_{3}K_{i,k}K_{k,j}K_{j,\ell}K_{\ell,i}\neq
0.$

The first part of Condition 1 implies that the three terms (corresponding to
the three distinct cycles on four vertices) in the second part are all
distinct in magnitude; the second part strengthens this requirement. Condition
1 can be thought of as a no-cancellation requirement for four-cycles of
principal minors of order four. As we will see, this condition is quite
important for the recovery of a magnitude-symmetric matrix from its principal
minors. Though, the results of this section, slightly modified, hold under
slightly weaker conditions than Condition 1, albeit at the cost of simplicity.
If $G_{K}$ is two-connected, Condition 1 implies that $K$ is HL-
indecomposable. This condition rules out dense matrices with an extremely high
degree of symmetry, as well as the large majority of rank one matrices, but
this condition is satisfied for almost all matrices.

We denote the set of $N\times N$ magnitude-symmetric matrices satisfying
Condition 1 by $\mathcal{K}_{N}$, and, when the dimension is clear from
context, we often simply write $\mathcal{K}$. We note that if
$K\in\mathcal{K}$, then any matrix $K^{\prime}$ satisfying
$|K^{\prime}_{i,j}|=|K_{i,j}|$, $i,j\in[N]$, is also in $\mathcal{K}$. In this
work, we are interested in the following problems/questions.

(PMA1) Given $K\in\mathcal{K}$, what is the minimal $\ell$ such that any
$K^{\prime}\in\mathcal{K}$ with $\Delta_{S}(K)=\Delta_{S}(K^{\prime})$ for all
$|S|\leq\ell$ also satisfies $\Delta_{S}(K)=\Delta_{S}(K^{\prime})$ for all
$S\subseteq[N]$? (PMA2) Given $K\in\mathcal{K}$, what is the set of
$K^{\prime}\in\mathcal{K}$ that satisfy $\Delta_{S}(K^{\prime})=\Delta_{S}(K)$
for all $S\subseteq[N]$? (PMA3) Given principal minors
$\\{\Delta_{S}(K)\\}_{S\subset[N]}$ of an unknown matrix $K\in\mathcal{K}$,
$\displaystyle\text{find a matrix $K^{\prime}\in\mathcal{K}$ that satisfies
}\Delta_{S}(K^{\prime})=\Delta_{S}(K)\text{ for all $S\subseteq[N]$.}$

(PMA1) asks for the smallest $\ell$ such that the principal minors of order at
most $\ell$ uniquely determine principal minors of all orders. Using
properties of $\mathcal{C}^{+}(G)$ (treated in Section 3), in Section 4
(Theorem 1), we show that the answer depends only on $(\Delta_{S})_{|S|\leq
2}$ and is the simple cycle sparsity $\ell_{+}$ of $\mathcal{C}^{+}(G)$. In
Section 5, we build on this analysis, and produce a polynomial-time algorithm
for recovering a matrix in $\mathcal{K}$ with prescribed principal minors
(possibly given up to some error term), hence treating (PMA3). The polynomial-
time algorithm (of Subsection 5.3) for recovery given perturbed principal
minors has key connections to learning signed DPPs.

(PMA2) asks to which extent we can hope to recover a matrix in $\mathcal{K}$
from its principal minors. For instance, the transpose operation $K^{T}$ and
the similarity transformation $DKD$, where $D$ is an involutory diagonal
matrix (i.e., $\pm 1$’s on the diagonal), both clearly preserve principal
minors. In fact, these two operations suitably combined completely define this
set. Even though [15, Theorem 1] already provides an answer to (PMA2) in a
more general setting (see Section 1 for details), we give, in Proposition 3,
an alternate proof that is tailored to our framework and reveals insights for
the algorithmic aspect of the problem (which we treat in Section 5).

To answer (PMA1), we study properties of certain bases of the space
$\mathcal{C}^{+}(G)$, where $G$ is the charged sparsity graph of $K$. We can
make a number of observations regarding the connectivity of $G$ and resulting
properties of the principal minors of $K$. If $G$ is disconnected, with
connected components given by vertex sets $V_{1},...,V_{k}$, then any
principal minor $\Delta_{S}$ satisfies

(1) $\Delta_{S}=\prod_{j=1}^{k}\Delta_{S\cap V_{j}}.$

In addition, if $G$ has a cut vertex $i$, whose removal results in connected
components with vertex sets $V_{1},...,V_{k}$, then any principal minor
$\Delta_{S}$ satisfies

(2) $\Delta_{S}=\sum_{j_{1}=1}^{k}\Delta_{[\\{i\\}\cup V_{j_{1}}]\cap
S}\prod_{j_{2}\neq j_{1}}\Delta_{V_{j_{2}}\cap S}-(k-1)\Delta_{\\{i\\}\cap
S}\prod_{j=1}^{k}\Delta_{V_{j}\cap S}.$

This implies that the principal minors of $K$ are uniquely determined by
principal minors corresponding to subsets of blocks of $G$. Given this
property, we focus on matrices $K$ without an articulation point, i.e. $G$ is
two-connected. Given results for matrices without an articulation point and
Equations (1) and (2), we can then answer (PMA1) in the more general case.

Next, we make an important observation regarding the contribution of certain
terms in the Leibniz expansion of a principal minor. Recall that the Leibniz
expansion of the determinant is given by

$\det(K)=\sum_{\sigma\in\mathcal{S}_{N}}\text{sgn}(\sigma)\prod_{i=1}^{N}K_{i,\sigma(i)},$

where $\text{sgn}(\sigma)$ is multiplicative over the (disjoint) cycles
forming the permutation, and is preserved when taking the inverse of the
permutation, or of any cycle therein. Consider now an arbitrary, possibly non-
induced, negative ($\epsilon(C)=-1$) simple cycle $C$ (in the graph-theoretic
sense) of the sparsity graph $G$, without loss of generality given by
$C=1\;2\;...\;k\;1$. Consider the sum of all terms in the Leibniz expansion
that contains either the cycle $(1\;2\;...\;k)$ or its inverse
$(k\;k-1\;...\;1)$ in the associated permutation. Because $\epsilon(C)=-1$,

$K_{k,1}\prod_{i=1}^{k-1}K_{i,i+1}+K_{1,k}\prod_{i=2}^{k}K_{i,i-1}=0,$

and the sum over all permutations containing the cyclic permutations
$(k\;k-1\;...\;1)$ or $(1\;2\;...\;k)$ is zero. Therefore, terms associated
with permutations containing negative cycles do not contribute to principal
minors.

To illustrate the additional information contained in higher order principal
minors $\Delta_{S}$, $|S|>2$, we first consider principal minors of order
three and four. Consider the principal minor $\Delta_{1,2,3}$, given by

$\Delta_{1,2,3}=\Delta_{1}\Delta_{2,3}+\Delta_{2}\Delta_{1,3}+\Delta_{3}\Delta_{1,2}-2\Delta_{1}\Delta_{2}\Delta_{3}+\big{[}1+\epsilon_{1,2}\epsilon_{2,3}\epsilon_{3,1}\big{]}K_{1,2}K_{2,3}K_{3,1}.$

If the corresponding graph $G[\\{1,2,3\\}]$ is not a cycle
($K_{1,2}K_{2,3}K_{3,1}=0$), or if the cycle is negative
($\epsilon_{1,2}\epsilon_{2,3}\epsilon_{3,1}=-1$), then $\Delta_{1,2,3}$ can
be written in terms of principal minors of order at most two, and contains no
additional information about $K$. If $G[\\{1,2,3\\}]$ is a positive cycle,
then we can write $K_{1,2}K_{2,3}K_{3,1}$ as a function of principal minors of
order at most three,

(3)
$K_{1,2}K_{2,3}K_{3,1}=\Delta_{1}\Delta_{2}\Delta_{3}-\frac{1}{2}\big{[}\Delta_{1}\Delta_{2,3}+\Delta_{2}\Delta_{1,3}+\Delta_{3}\Delta_{1,2}\big{]}+\frac{1}{2}\Delta_{1,2,3},$

which allows us to compute $\text{sgn}(K_{1,2}K_{2,3}K_{3,1})$. This same
procedure holds for a positive induced simple cycle of any order. In
particular, for a positive induced cycle $C=1\;2\;...\;k\;1$, we can compute
$\text{sgn}\big{(}K_{k,1}\prod_{i=1}^{k-1}K_{i,i+1}\big{)}$ efficiently (in
$O(k^{3})$ time) using only $\Delta_{[k]}$ and principal minors of order one
and two (see [21, Equation 1 & Subsection 2.3] for details). However, when a
simple cycle is not induced, further analysis is required. To illustrate some
of the potential issues for a non-induced positive simple cycle, we consider
principal minors of order four.

Consider the principal minor $\Delta_{1,2,3,4}$. By our previous analysis, all
terms in the Leibniz expansion of $\Delta_{1,2,3,4}$ corresponding to
permutations with cycles of length at most three can be written in terms of
principal minors of size at most three. What remains is to consider the sum of
the terms in the Leibniz expansion corresponding to permutations containing a
cycle of length four (which there are three pairs of, each pair corresponding
to the two orientations of a cycle of length four in the graph sense), which
we denote by

(4) $\displaystyle Z$
$\displaystyle=-K_{1,2}K_{2,3}K_{3,4}K_{4,1}-K_{1,2}K_{2,4}K_{4,3}K_{3,1}-K_{1,3}K_{3,2}K_{2,4}K_{4,1}$
$\displaystyle\quad-
K_{4,3}K_{3,2}K_{2,1}K_{1,4}-K_{4,2}K_{2,1}K_{1,3}K_{3,4}-K_{4,2}K_{2,3}K_{3,1}K_{1,4}.$

If $G[\\{1,2,3,4\\}]$ does not contain a positive simple cycle of length four,
then $Z=0$ and $\Delta_{1,2,3,4}$ can be written in terms of principal minors
of order at most three. If $G[\\{1,2,3,4\\}]$ has exactly one positive cycle
of length four, without loss of generality given by $C:=1\;2\;3\;4\;1$, then

(5)
$Z=-\big{[}1+\epsilon(C)\big{]}K_{1,2}K_{2,3}K_{3,4}K_{4,1}=-2K_{1,2}K_{2,3}K_{3,4}K_{4,1},$

and we can write $K_{1,2}K_{2,3}K_{3,4}K_{4,1}$ as a function of principal
minors of order at most four, which allows us to compute
$\text{sgn}(K_{1,2}K_{2,3}K_{3,4}K_{4,1})$. If there is more than one positive
simple cycle of length four, this implies that all simple cycles of length
four are positive and $Z$ is given by

(6)
$Z=-2\big{[}K_{1,2}K_{2,3}K_{3,4}K_{4,1}+K_{1,2}K_{2,4}K_{4,3}K_{3,1}+K_{1,3}K_{3,2}K_{2,4}K_{4,1}\big{]}.\\\
$

By Condition 1, the magnitude of each of these three terms is distinct, $Z\neq
0$, and we can compute the sign of each of these terms, as there is a unique
choice of $\phi_{1},\phi_{2},\phi_{3}\in\\{-1,+1\\}$ satisfying

(7)
$\phi_{1}|K_{1,2}K_{2,3}K_{3,4}K_{4,1}|+\phi_{2}|K_{1,2}K_{2,4}K_{4,3}K_{3,1}|+\phi_{3}|K_{1,3}K_{3,2}K_{2,4}K_{4,1}|=-\frac{Z}{2}.$

This completes the analysis of principal minors of order at most four. In
order to better understand the behavior of principal minors of order greater
than four, we study a number of properties of $\mathcal{C}^{+}(G)$ in the
following section.

##  3\. Properties of Minimal Cycle Bases of $\mathcal{C}^{+}(G)$

In this section we consider $\mathcal{C}^{+}(G)$, the set of incidence vectors
corresponding to positive cycles, and aim to prove a number of results
regarding bases consisting of incidence vectors corresponding to simple
cycles. The study of various properties of cycle bases of graphs is of broad
interest, with wide-ranging applications, and the work in this section, though
necessary for our application, is also of independent interest. We refer the
reader to [12] for a fantastic survey of the subject. In the following two
propositions, we compute the dimension of $\mathcal{C}^{+}(G)$ and note that,
when $G$ is two-connected, this space is indeed spanned by incidence vectors
corresponding to positive simple cycles.

######  Proposition 1.

Let $G=([N],E,\epsilon)$. Then $\dim(\mathcal{C}^{+}(G))=\nu-1$ if $G$
contains at least one negative cycle, and equals $\nu$ otherwise.

###### Proof.

Consider a basis $\\{x_{1},...,x_{\nu}\\}$ for $\mathcal{C}(G)$. If all
associated cycles are positive, then $\dim(\mathcal{C}^{+}(G))=\nu$ and we are
done. If $G$ has a negative cycle, then, by the linearity of $\epsilon$, at
least one element of $\\{x_{1},...,x_{\nu}\\}$ must be the incidence vector of
a negative cycle. Without loss of generality, suppose that $x_{1},...,x_{i}$
are incidence vectors of negative cycles. Then
$x_{1}+x_{2},...,x_{1}+x_{i},x_{i+1},...,x_{\nu}$ is a linearly independent
set of incidence vectors of positive cycles. Therefore,
$\dim(\mathcal{C}^{+}(G))\geq\nu-1$. However, $x_{1}$ is the incidence vector
of a negative cycle, and so cannot be in $\mathcal{C}^{+}(G)$. ∎

######  Proposition 2.

Let $G=([N],E,\epsilon)$ be two-connected. Then

$\mathcal{C}^{+}(G)=\text{span}\\{\chi_{C}\,|\,C\text{ is a simple cycle of
}G,\epsilon(C)=+1\\}.$

###### Proof.

If $G$ does not contain a negative cycle, then the result follows immediately,
as then $\mathcal{C}^{+}(G)=\mathcal{C}(G)$. Suppose then that $G$ has at
least one negative cycle. Decomposing this negative cycle into the union of
edge-disjoint simple cycles, we note that $G$ must also have at least one
negative simple cycle.

Since $G$ is a two-connected graph, it admits a proper (also called open) ear
decomposition with $\nu-1$ proper ears (Whitney [23], see also [13]) starting
from any simple cycle. We choose our initial simple cycle to be a negative
simple cycle denoted by $G_{0}$. Whitney’s proper ear decomposition states
that we can obtain a sequence of graphs $G_{0}$, $G_{1},\cdots,G_{\nu-1}=G$
where $G_{i}$ is obtained from $G_{i-1}$ by adding a path $P_{i}$ between two
distinct vertices $u_{i}$ and $v_{i}$ of $V(G_{i-1})$ with its internal
vertices not belonging to $V(G_{i-1})$ (a proper or open ear). By
construction, $P_{i}$ is also a path between $u_{i}$ and $v_{i}$ in $G_{i}$.

We will prove a stronger statement by induction on $i$, namely that for
suitably constructed positive simple cycles $C_{j}$, $j=1,...,\nu-1$, we have
that, for every $i=0,1,...,\nu-1$:

  1. (i)

$\mathcal{C}^{+}(G_{i})=\text{span}\\{\chi_{C_{j}}:1\leq j\leq i\\}$,

  2. (ii)

for every pair of distinct vertices $u,v\in V(G_{i})$, there exists both a
positive path in $G_{i}$ between $u$ and $v$ and a negative path in $G_{i}$
between $u$ and $v$.

For $i=0$, (i) is clear and (ii) follows from the fact that the two paths
between $u$ and $v$ in the cycle $G_{0}$ must have opposite charge since their
sum is $G_{0}$ and $\epsilon(G_{0})=-1$. For $i>0$, we assume that we have
constructed $C_{1},\cdots,C_{i-1}$ satisfying (i) and (ii) for values less
than $i$. To construct $C_{i}$, we take the path $P_{i}$ between $u_{i}$ and
$v_{i}$ and complete it with a path of charge $\epsilon(P_{i})$ between
$u_{i}$ and $v_{i}$ in $G_{i-1}$. The existence of this latter path follows
from (ii), and these two paths together form a simple cycle $C_{i}$ with
$\epsilon(C_{i})=+1$. It is clear that this $C_{i}$ is linearly independent
from all the previously constructed cycles $C_{j}$ since $C_{i}$ contains
$P_{i}$ but $P_{i}$ was not even part of $G_{i-1}$. This implies (i) for $i$.

To show (ii) for $G_{i}$, we need to consider three cases for $u\neq v$. If
$u,v\in V(G_{i-1})$, we can use the corresponding positive and negative paths
in $G_{i-1}$ (whose existence follows from (ii) for $i-1$). If $u,v\in
V(P_{i})$, one of the paths can be the subpath $P_{uv}$ of $P_{i}$ between $u$
and $v$ and the other path can be $P_{i}\setminus P_{uv}$ together with a path
in $G_{i-1}$ between $u_{i}$ and $v_{i}$ of charge equal to $-\epsilon(P_{i})$
(so that together they form a negative cycle). Otherwise, we must have $u\in
V(P_{i})\setminus\\{u_{i},v_{i}\\}$ and $v\in
V(G_{i-1})\setminus\\{u_{i},v_{i}\\}$ (or vice versa), and we can select the
paths to be the path in $P_{i}$ from $u$ to $u_{i}$ together with two
oppositely charged paths in $G_{i-1}$ between $u_{i}$ and $v$. In all these
cases, we have shown property (ii) holds for $G_{i}$. ∎

For the remainder of the analysis in this section, we generally assume that
$G$ contains a negative cycle, otherwise $\mathcal{C}^{+}(G)=\mathcal{C}(G)$
and we inherit all of the desirable properties of $\mathcal{C}(G)$. Next, we
study the properties of simple cycle bases (bases consisting of incidence
vectors of simple cycles) of $\mathcal{C}^{+}(G)$, $G$ two-connected, that are
minimal in some sense. We say that a simple cycle basis
$\\{\chi_{C_{1}},...,\chi_{C_{\nu-1}}\\}$ for $\mathcal{C}^{+}(G)$ is
lexicographically minimal if it lexicographically minimizes
$(|C_{1}|,|C_{2}|,...,|C_{\nu-1}|)$, i.e., minimizes $|C_{1}|$, minimizes
$|C_{2}|$ conditional on $|C_{1}|$ being minimal, etc. Any lexicographical
minimal basis also minimizes $\sum|C_{i}|$ and $\max|C_{i}|$ (by optimality of
the greedy algorithm for (linear) matroids). For brevity, we will simply refer
to such a basis as “minimal.” One complicating issue is that, while a minimal
cycle basis for $\mathcal{C}(G)$ always consists of induced simple cycles,
this is no longer the case for $\mathcal{C}^{+}(G)$. This for example can
happen for an appropriately constructed graph with only two negative, short
simple cycles, far away from each other; a minimal (not necessarily simple)
cycle basis for $\mathcal{C}^{+}(G)$ then contains a cycle consisting of the
union of these two negative simple cycles. Computing a minimal cycle basis for
$\mathcal{C}(G)$ is a well-studied problem, with a number of efficient
algorithms to do so (see [12] for details). In contrast, the complexity of
computing a minimal simple cycle basis for $\mathcal{C}^{+}(G)$ is not known.
Computing the shortest positive simple cycle can be reduced to the computation
of the shortest even cycle in a graph, which can be done efficiently (see [19,
Subsection 29.11e] for details). The complexity of extending this cycle to a
basis is not clear.

However, we can make a number of statements regarding chords of simple cycles
corresponding to elements of a minimal simple cycle basis of
$\mathcal{C}^{+}(G)$. In the following lemma, we show that a minimal simple
cycle basis satisfies a number of desirable properties. Before we do so, we
introduce some useful notation. Given a simple cycle $C$, it is convenient to
fix an orientation, say, $C=i_{1}\;i_{2}\;...\;i_{k}\;i_{1}$. Given an
orientation and any chord $\\{i_{k_{1}},i_{k_{2}}\\}\in\gamma(C)$,
$k_{1}<k_{2}$, we denote the two cycles created by this chord by

$C(k_{1},k_{2})=i_{k_{1}}\;i_{k_{1}+1}\;...\;i_{k_{2}}\;i_{k_{1}}\quad\text{and}\quad
C(k_{2},k_{1})=i_{k_{2}}\;i_{k_{2}+1}\;...\;i_{k}\;i_{1}\;...\;i_{k_{1}}\;i_{k_{2}}.$

We have the following result.

######  Lemma 1.

Let $G=([N],E,\epsilon)$ be two-connected and
$C:=i_{1}\;i_{2}\;...\;i_{k}\;i_{1}$ be a cycle corresponding to an incidence
vector of an element of a minimal simple cycle basis
$\\{x_{1},...,x_{\nu-1}\\}$ of $\mathcal{C}^{+}(G)$. Then

  1. (i)

$\epsilon\big{(}C(k_{1},k_{2})\big{)}=\epsilon\big{(}C(k_{2},k_{1})\big{)}=-1$
for all $\\{i_{k_{1}},i_{k_{2}}\\}\in\gamma(C)$,

  2. (ii)

if $\\{i_{k_{1}},i_{k_{2}}\\},\\{i_{k_{3}},i_{k_{4}}\\}\in\gamma(C)$ satisfy
$k_{1}<k_{3}<k_{2}<k_{4}$ (crossing chords), then either
$k_{3}-k_{1}=k_{4}-k_{2}=1$ or $k_{1}=1$, $k_{2}-k_{3}=1$, $k_{4}=k$, i.e.
these two chords form a four-cycle with two edges of the cycle,

  3. (iii)

there does not exist
$\\{i_{k_{1}},i_{k_{2}}\\},\\{i_{k_{3}},i_{k_{4}}\\},\\{i_{k_{5}},i_{k_{6}}\\}\in\gamma(C)$
satisfying either $k_{1}<k_{2}\leq k_{3}<k_{4}\leq k_{5}<k_{6}$ or $k_{6}\leq
k_{1}<k_{2}\leq k_{3}<k_{4}\leq k_{5}$.

###### Proof.

Without loss of generality, suppose that $C=1\;2\;...\;k\;1$. Given a chord
$\\{k_{1},k_{2}\\}$, $C(k_{1},k_{2})+C(k_{2},k_{1})=C$, and so
$\epsilon(C)=+1$ implies that
$\epsilon\big{(}C(k_{1},k_{2})\big{)}=\epsilon\big{(}C(k_{2},k_{1})\big{)}$.
If both these cycles were positive, then this would contradict the minimality
of the basis, as $|C(k_{1},k_{2})|,|C(k_{2},k_{1})|<k$. This completes the
proof of Property (i).

Given two chords $\\{k_{1},k_{2}\\}$ and $\\{k_{3},k_{4}\\}$ satisfying
$k_{1}<k_{3}<k_{2}<k_{4}$, we consider the cycles

$\displaystyle C_{1}$ $\displaystyle:=C(k_{1},k_{2})+C(k_{3},k_{4}),$
$\displaystyle C_{2}$ $\displaystyle:=C(k_{1},k_{2})+C(k_{4},k_{3}).$

By Property (i), $\epsilon(C_{1})=\epsilon(C_{2})=+1$. In addition,
$C_{1}+C_{2}=C$, and $|C_{1}|,|C_{2}|\leq|C|$. By the minimality of the basis,
either $|C_{1}|=|C|$ or $|C_{2}|=|C|$, which implies that either $|C_{1}|=4$
or $|C_{2}|=4$ (or both). This completes the proof of Property (ii).

Given three non-crossing chords $\\{k_{1},k_{2}\\}$, $\\{k_{3},k_{4}\\}$, and
$\\{k_{5},k_{6}\\}$, with $k_{1}<k_{2}\leq k_{3}<k_{4}\leq k_{5}<k_{6}$ (the
other case is identical, up to rotation), we consider the cycles

$\displaystyle C_{1}$ $\displaystyle:=C(k_{3},k_{4})+C(k_{5},k_{6})+C,$
$\displaystyle C_{2}$ $\displaystyle:=C(k_{1},k_{2})+C(k_{5},k_{6})+C,$
$\displaystyle C_{3}$ $\displaystyle:=C(k_{1},k_{2})+C(k_{3},k_{4})+C.$

By Property (i), $\epsilon(C_{1})=\epsilon(C_{2})=\epsilon(C_{3})=+1$. In
addition, $C_{1}+C_{2}+C_{3}=C$ and $|C_{1}|,|C_{2}|,|C_{3}|<|C|$, a
contradiction to the minimality of the basis. This completes the proof of
Property (iii). ∎

The proof of the above lemma is algorithmic in nature; in fact, given any
simple cycle basis of $\mathcal{C}^{+}(G)$, one can efficiently derive a basis
that satisfies Properties (i)-(iii). We make use of this fact in the
algorithms of Section 5 and Appendix A. Lemma 1 tells us that in a minimal
simple cycle basis for $\mathcal{C}^{+}(G)$, in each cycle two crossing chords
always form a positive cycle of length four (and thus any chord has at most
one other crossing chord), and there doesn’t exist three non-crossing chords
without one chord in between the other two. As we will see in the following
lemma, any cycle that satisfies these three properties has quite a rigid
structure.

######  Lemma 2.

Let $C$ be a positive simple cycle of $G=([N],E,\epsilon)$ with
$V(C)=\\{i_{1},i_{2},\cdots,i_{k}\\}$ whose chords $\gamma(C)$ satisfy
Properties (i)-(iii) of Lemma 1. Then there exist two edges of
$C:=i_{1}\;i_{2}\;...\;i_{k}\;i_{1}$, say, $\\{i_{1},i_{k}\\}$ and
$\\{i_{\ell},i_{\ell+1}\\}$, such that

  1. (i)

all chords $\\{i_{p},i_{q}\\}\in\gamma(C)$, $p<q$, satisfy $p\leq\ell<q$,

  2. (ii)

any positive simple cycle in $G[V(C)]$ containing $\\{i_{1},i_{k}\\}$ spans
$V(C)$ and contains only edges in $E(C)$ and pairs of crossed chords.

###### Proof.

We first note that Property (i) of Lemma 1 implies that the charge of a cycle
$C^{\prime}\subseteq G[V(C)]$ corresponds to the parity of
$E(C^{\prime})\cap\gamma(C)$, i.e., if $C^{\prime}$ contains an even number of
chords then $\epsilon(C^{\prime})=+1$, otherwise $\epsilon(C^{\prime})=-1$.
This follows from constructing a cycle basis for
$\mathcal{C}\big{(}G[V(C)]\big{)}$ consisting of incidence vectors
corresponding to $C$ and $C(i,j)$ for every chord $\\{i,j\\}\in\gamma(C)$.

Let the cycle $C(i,j)$ be a shortest cycle in $G[V(C)]$ containing exactly one
chord of $C$. If $\\{i,j\\}$ is a non-crossed chord, then we take an arbitrary
edge in $E(C(i,j))\backslash\\{i,j\\}$ to be $\\{i_{1},i_{k}\\}$. If this
chord crosses another, denoted by $\\{i^{\prime},j^{\prime}\\}$, then either
$C(i^{\prime},j^{\prime})$ or $C(j^{\prime},i^{\prime})$ is also a shortest
cycle (possibly both are). If $C(i^{\prime},j^{\prime})$ and
$C(j^{\prime},i^{\prime})$ are both shortest cycles, then $\gamma(C)$ consists
only of the pair of crossing chords $\\{i,j\\}$ and
$\\{i^{\prime},j^{\prime}\\}$, and the result follows immediately. If only one
is a shortest cycle, w.l.o.g. $C(i^{\prime},j^{\prime})$, then we take an
arbitrary edge in $E(C(i,j))\cap E(C(i^{\prime},j^{\prime}))$. Because of
Property (iii) of Lemma 1, there exists $\ell$ such that all chords
$\\{i_{p},i_{q}\\}\in\gamma(C)$, $p<q$, satisfy $p\leq\ell<q$. This completes
the proof of Property (i).

Next, consider an arbitrary positive simple cycle $C^{\prime}$ in $G[V(C)]$
containing $\\{i_{1},i_{k}\\}$. We aim to show that this cycle contains only
edges in $E(G)$ and pairs of crossed chords, from which the equality
$V(C^{\prime})=V(C)$ immediately follows. Since $C^{\prime}$ is positive, it
contains an even number of chords $\gamma(C)$, and either all the chords
$\gamma(C)\cap E(C^{\prime})$ are pairs of crossed chords or there exist two
chords $\\{i_{p_{1}},i_{q_{1}}\\},\\{i_{p_{2}},i_{q_{2}}\\}\in\gamma(C)\cap
E(C^{\prime})$, w.l.o.g. $p_{1}\leq p_{2}\leq\ell<q_{2}<q_{1}$ (we can simply
reverse the orientation if $q_{1}=q_{2}$), that do not cross any other chord
in $\gamma(C)\cap E(C^{\prime})$. In this case, there would be a
$i_{1}-i{q_{2}}$ path in $C^{\prime}$ neither containing $i_{p_{1}}$ nor
$i_{q_{1}}$ (as $\\{i_{p_{1}},i_{q_{1}}\\}$ would be along the other path
between $i_{1}$ and $i_{q_{2}}$ in $C^{\prime}$ and $q_{1}\neq q_{2}$).
However, this is a contradiction as no such path exists in $C^{\prime}$, since
$\\{i_{p_{1}},i_{q_{1}}\\}$ does not cross any chord in $\gamma(C)\cap
E(C^{\prime})$. Therefore, the chords $\gamma(C)\cap E(C^{\prime})$ are all
pairs of crossed chords. Furthermore, since all pairs of crossed chords must
define cycles of length four, we have $V(C^{\prime})=V(C)$. This completes the
proof of Property (ii). ∎

Although this is not needed in what follows, observe that, in the above Lemma
2, $\\{i_{\ell},i_{\ell+1}\\}$ also plays the same role as $\\{i_{1},i_{k}\\}$
in the sense that any positive simple cycle containing
$\\{i_{\ell},i_{\ell+1}\\}$ also spans $V(C)$ and contains only pairs of
crossed chords and edges in $E(C)$. In the following section, we make use of
the key structural properties (in Lemma 2) of minimal cycle bases to answer
(PMA1).

##  4\. Identifying a Matrix using Principal Minors of Minimal Order

In this section, using a simple cycle basis of $\mathcal{C}^{+}(G)$ that
satisfies the properties of Lemma 1, we aim to show that the principal minors
of order at most the length of the longest cycle in the basis uniquely
determine the principal minors of all orders, thus answering (PMA1). For a
cycle $C$, let

$s(C):=\prod_{\begin{subarray}{c}\\{i,j\\}\in E(C),\\\
i<j\end{subarray}}\text{sgn}\big{(}K_{i,j}\big{)}.$

As previously illustrated, when $C$ is a positive simple cycle of length at
most four, $s(C)$ can be computed efficiently using only principal minors
corresponding to subsets of $V(C)$. In a series of two lemmas, we aim to show
that, for an arbitrary cycle $C$ in our basis, we can compute $s(C)$ using
$\Delta_{V(C)}$, $(\Delta_{S})_{|S|\leq 2}$, $s(C^{\prime})$ for simple
positive cycles $|C^{\prime}|\leq 4$, and at most eight other principal minors
of subsets of $V(C)$. Once we have computed $s(C_{i})$ for every simple cycle
in our basis, we can compute $s(C)$ for any simple positive cycle by writing
$C$ as a sum of some subset of the simple cycles $C_{1},...,C_{\nu-1}$
corresponding to incidence vectors in our basis, and taking the product of
$s(C_{i})$ for all indices $i$ in the aforementioned sum. As we will later see
(in Theorem 1), this is enough to recover $K$ (up to some equivalence class
defined in Proposition 3). To this end, we prove the following two lemmas.

######  Lemma 3.

Let $K\in\mathcal{K}$ have charged sparsity graph $G=([N],E,\epsilon)$, and
$C=i_{1}\;...\;i_{k}\;i_{1}$ be a positive simple cycle of $G$ whose chords
$\gamma(C)$ satisfy Properties (i)-(iii) of Lemma 1, and with vertices ordered
as in Lemma 2. Then the principal minor corresponding to $S=V(C)$ is given by

$\displaystyle\Delta_{S}$ $\displaystyle=\Delta_{i_{1}}\Delta_{S\backslash
i_{1}}+\Delta_{i_{k}}\Delta_{S\backslash
i_{k}}+\big{[}\Delta_{i_{1},i_{k}}-2\Delta_{i_{1}}\Delta_{i_{k}}\big{]}\Delta_{S\backslash
i_{1},i_{k}}$
$\displaystyle\quad-2K_{i_{1},i_{k-1}}K_{i_{k-1},i_{k}}K_{i_{k},i_{2}}K_{i_{2},i_{1}}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}$
$\displaystyle\quad+\big{[}\Delta_{i_{1},i_{k-1}}-\Delta_{i_{1}}\Delta_{i_{k-1}}\big{]}\big{[}\Delta_{i_{2},i_{k}}-\Delta_{i_{2}}\Delta_{i_{k}}\big{]}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}$
$\displaystyle\quad+\big{[}\Delta_{i_{1},i_{2}}-\Delta_{i_{1}}\Delta_{i_{2}}\big{]}\big{[}\Delta_{S\backslash
i_{1},i_{2}}-\Delta_{i_{k}}\Delta_{S\backslash i_{1},i_{2},i_{k}}\big{]}$
$\displaystyle\quad+\big{[}\Delta_{i_{k-1},i_{k}}-\Delta_{i_{k-1}}\Delta_{i_{k}}\big{]}\big{[}\Delta_{S\backslash
i_{k-1},i_{k}}-\Delta_{i_{1}}\Delta_{S\backslash i_{1},i_{k-1},i_{k}}\big{]}$
$\displaystyle\quad-\big{[}\Delta_{i_{1},i_{2}}-\Delta_{i_{1}}\Delta_{i_{2}}\big{]}\big{[}\Delta_{i_{k-1},i_{k}}-\Delta_{i_{k-1}}\Delta_{i_{k}}\big{]}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}$ $\displaystyle\quad+Z.$

where $Z$ is the sum of terms in the Leibniz expansion of $\Delta_{S}$
corresponding to permutations where $\sigma(i_{1})=i_{k}$ or
$\sigma(i_{k})=i_{1}$, but not both.

###### Proof.

Without loss of generality, suppose that $C=1\;2\;...\;k\;1$. Each term in
$\Delta_{S}$ corresponds to a partition of $S=V(C)$ into a disjoint collection
of vertices, pairs corresponding to edges of $G[S]$, and simple cycles $C_{i}$
of $G[S]$ which can be assumed to be positive. We can decompose the Leibniz
expansion of $\Delta_{S}$ into seven sums of terms, based on how the
associated permutation for each term treats the elements $1$ and $k$. Let
$X_{j_{1},j_{2}}$, $j_{1},j_{2}\in\\{1,k,*\\}$, equal the sum of terms
corresponding to permutations where $\sigma(1)=j_{1}$ and $\sigma(k)=j_{2}$,
where $*$ denotes any element in $\\{2,...,k-1\\}$. The case
$\sigma(1)=\sigma(k)$ obviously cannot occur (i.e., $X_{1,1}=X_{k,k}=0$), and
so

$\Delta_{S}=X_{1,k}+X_{1,*}+X_{*,k}+X_{k,1}+X_{k,*}+X_{*,1}+X_{*,*}.$

By definition, $Z=X_{k,*}+X_{*,1}$. What remains is to compute the remaining
five terms. We have

$\displaystyle X_{k,1}$ $\displaystyle=-K_{1,k}K_{k,1}\Delta_{S\backslash
1,k}=\big{[}\Delta_{1,k}-\Delta_{1}\Delta_{k}\big{]}\Delta_{S\backslash 1,k},$
$\displaystyle X_{1,k}$ $\displaystyle=\Delta_{1}\Delta_{k}\Delta_{S\backslash
1,k},$ $\displaystyle X_{1,k}+X_{1,*}$
$\displaystyle=\Delta_{1}\Delta_{S\backslash 1},$ $\displaystyle
X_{1,k}+X_{*,k}$ $\displaystyle=\Delta_{k}\Delta_{S\backslash k},$

and so

$\Delta_{S}=\Delta_{1}\Delta_{S\backslash 1}+\Delta_{k}\Delta_{S\backslash
k}+\big{[}\Delta_{1,k}-2\Delta_{1}\Delta_{k}\big{]}\Delta_{S\backslash
1,k}+X_{*,*}+Z.$

The sum $X_{*,*}$ corresponds to permutations where $\sigma(1)\notin\\{1,k\\}$
and $\sigma(k)\notin\\{1,k\\}$. We note that, by Property (ii) of Lemma 1,
either both $1$ and $k$ contain exactly one chord incident to them, and these
two chords are $\\{1,k-1\\}$ and $\\{2,k\\}$, or at most one of $1$ and $k$
contains a chord incident to them. We first show that the only permutations
that satisfy these two properties take the form $\sigma^{2}(1)=1$ or
$\sigma^{2}(k)=k$ (or both), or contain both $1$ and $k$ in the same cycle.
Suppose to the contrary, that there exists some permutation where $1$ and $k$
are not in the same cycle, and both are in cycles of length at least three.
Then in $G[S]$ both vertices $1$ and $k$ contain a chord emanating from them.
Therefore, each has exactly one chord and these chords are $\\{1,k-1\\}$ and
$\\{2,k\\}$. The cycle containing $1$ must also contain $2$ and $k-1$, and the
cycle containing $k$ must also contain $2$ and $k-1$, a contradiction.

In addition, we note that, by the above analysis, the only cycles (of a
permutation) that can contain both $1$ and $k$ without having $\sigma(1)=k$ or
$\sigma(k)=1$ are given by $(1\;2\;k\;k-1)$ and $(1\;k-1\;k\;2)$. Furthermore,
if $1$ and $k$ are not in the same cycle, then $(1\;2)$ and $(k-1\;k)$, or
$(1\;k-1)$ and $(2\;k)$ are in the permutation. Therefore, we can decompose
$X_{*,*}$ further into the sum of five terms. Let

  * •

$Y_{1}$ equal the sum of terms corresponding to permutations containing
$(1\;2\;k\;k-1)$ or $(1\;k-1\;k\;2)$,

  * •

$Y_{2}$ equal the sum of terms corresponding to permutations containing
$(1\;k-1)$ and $(2\;k)$,

  * •

$Y_{3}$ equal the sum of terms corresponding to permutations containing
$(1\;2)$ and $(k-1\;k)$,

  * •

$Y_{4}$ equal the sum of terms corresponding to permutations containing
$(1\;2)$ and not containing $(k-1\;k)$ or $(k)$,

  * •

$Y_{5}$ equal the sum of terms corresponding to permutations containing
$(k-1\;k)$ and not containing $(1\;2)$ or $(1)$.

$Y_{1}$ and $Y_{2}$ are only non-zero if $\\{1,k-1\\}$ and $\\{2,k\\}$ are
both chords of $C$, in which case these are the only chords adjacent to $1$ or
$k$ and so $Y_{4}=Y_{5}=0$. In general, $Y_{4}$ is only non-zero if there is a
chord (other than possibly $\\{2,k\\}$) incident to $k$, and $Y_{5}$ is only
non-zero if there is a chord (other than possibly $\\{1,k-1\\}$) incident to
$1$. We have $X_{*,*}=Y_{1}+Y_{2}+Y_{3}+Y_{4}+Y_{5}$, and

$\displaystyle Y_{1}$
$\displaystyle=-2K_{1,k-1}K_{k-1,k}K_{k,2}K_{2,1}\Delta_{S\backslash
1,2,k-1,k},$ $\displaystyle Y_{2}$
$\displaystyle=K_{1,k-1}K_{k-1,1}K_{2,k}K_{k,2}\Delta_{S\backslash 1,2,k-1,k}$
$\displaystyle=\big{[}\Delta_{1,k-1}-\Delta_{1}\Delta_{k-1}\big{]}\big{[}\Delta_{2,k}-\Delta_{2}\Delta_{k}\big{]}\Delta_{S\backslash
1,2,k-1,k},$ $\displaystyle Y_{3}$
$\displaystyle=K_{1,2}K_{2,1}K_{k-1,k}K_{k,k-1}\Delta_{S\backslash 1,2,k-1,k}$
$\displaystyle=\big{[}\Delta_{1,2}-\Delta_{1}\Delta_{2}\big{]}\big{[}\Delta_{k-1,k}-\Delta_{k-1}\Delta_{k}\big{]}\Delta_{S\backslash
1,2,k-1,k},$ $\displaystyle Y_{3}+Y_{4}$
$\displaystyle=-K_{1,2}K_{2,1}\big{[}\Delta_{S\backslash
1,2}-\Delta_{k}\Delta_{S\backslash 1,2,k}\big{]}$
$\displaystyle=\big{[}\Delta_{1,2}-\Delta_{1}\Delta_{2}\big{]}\big{[}\Delta_{S\backslash
1,2}-\Delta_{k}\Delta_{S\backslash 1,2,k}\big{]},$ $\displaystyle Y_{3}+Y_{5}$
$\displaystyle=-K_{k-1,k}K_{k,k-1}\big{[}\Delta_{S\backslash
k-1,k}-\Delta_{1}\Delta_{S\backslash 1,k-1,k}\big{]}$
$\displaystyle=\big{[}\Delta_{k-1,k}-\Delta_{k-1}\Delta_{k}\big{]}\big{[}\Delta_{S\backslash
k-1,k}-\Delta_{1}\Delta_{S\backslash 1,k-1,k}\big{]}.$

Combining all of these terms gives us

$\displaystyle X_{*,*}$
$\displaystyle=-2K_{1,k-1}K_{k-1,k}K_{k,2}K_{2,1}\Delta_{S\backslash
1,2,k-1,k}$
$\displaystyle\quad+\big{[}\Delta_{1,k-1}-\Delta_{1}\Delta_{k-1}\big{]}\big{[}\Delta_{2,k}-\Delta_{2}\Delta_{k}\big{]}\Delta_{S\backslash
1,2,k-1,k}$
$\displaystyle\quad+\big{[}\Delta_{1,2}-\Delta_{1}\Delta_{2}\big{]}\big{[}\Delta_{S\backslash
1,2}-\Delta_{k}\Delta_{S\backslash 1,2,k}\big{]}$
$\displaystyle\quad+\big{[}\Delta_{k-1,k}-\Delta_{k-1}\Delta_{k}\big{]}\big{[}\Delta_{S\backslash
k-1,k}-\Delta_{1}\Delta_{S\backslash 1,k-1,k}\big{]}$
$\displaystyle\quad-\big{[}\Delta_{1,2}-\Delta_{1}\Delta_{2}\big{]}\big{[}\Delta_{k-1,k}-\Delta_{k-1}\Delta_{k}\big{]}\Delta_{S\backslash
1,2,k-1,k}.$

Combining our formula for $X_{*,*}$ with our formula for $\Delta_{S}$ leads to
the desired result. ∎

######  Lemma 4.

Let $K\in\mathcal{K}$ have charged sparsity graph $G=([N],E,\epsilon)$, and
$C=i_{1}\;...\;i_{k}\;i_{1}$ be a positive simple cycle of $G$ whose chords
$\gamma(C)$ satisfy Properties (i)-(iii) of Lemma 1, with vertices ordered as
in Lemma 2. Let $Z$ equal the sum of terms in the Leibniz expansion of
$\Delta_{S}$, $S=V(C)$, corresponding to permutations where
$\sigma(i_{1})=i_{k}$ or $\sigma(i_{k})=i_{1}$, but not both (i.e., as in
Lemma 3). Let $U\subseteq S^{2}$ be the set of pairs $(a,b)$, $a<b$, for which
$\\{i_{a},i_{b-1}\\},\\{i_{a+1},i_{b}\\}\in\gamma(C)$, i.e., cycle edges
$\\{i_{a},i_{a+1}\\}$ and $\\{i_{b-1},i_{b}\\}$ have a pair of crossed chords
between them. Then

$Z=2\,(-1)^{k+1}\,K_{i_{k},i_{1}}\prod_{j=1}^{k-1}K_{i_{j},i_{j+1}}\prod_{(a,b)\in
U}\left[1-\frac{\epsilon_{i_{a},i_{a+1}}K_{i_{b-1},i_{a}}K_{i_{a+1},i_{b}}}{K_{i_{a},i_{a+1}}K_{i_{b-1},i_{b}}}\right].$

###### Proof.

Without loss of generality, suppose that $G$ is labelled so that
$C=1\;2\;...\;k\;1$ and edge $\\{1,k\\}$ satisfies Property (ii) of Lemma 2,
and so every positive simple cycle of $G[S]$ containing $\\{1,k\\}$ spans $S$
and contains only edges in $E(C)$ and pairs of crossing chords. Therefore, we
may assume without loss of generality that $G[S]$ contains $p$ pairs of
crossing chords, and no other chords. If $p=0$, then $C$ is an induced cycle
and the result follows immediately.

There are $2^{p}$ Hamiltonian paths in $G[S]$ joining $1$ and $k$,
corresponding to the $p$ binary choices of whether to use each pair of
crossing chords or not. Let us denote these paths from $1$ to $k$ by
$P^{1,k}_{\theta}$, where $\theta\in\\{0,1\\}^{p}$, and $\theta_{i}$ equals
one if the $i^{th}$ crossing is used in the path (ordered based on increasing
distance to $\\{1,k\\}$), and zero otherwise. In particular, $P^{1,k}_{0}$
corresponds to the path $=1\;2\;...\;k$. We only consider paths with the
orientation $1\rightarrow k$, as all cycles under consideration are positive,
and the opposite orientation has the same sum. Denoting the product of the
terms of $K$ corresponding to the path
$P^{1,k}_{\theta}=\ell_{1}\;\ell_{2}\;...\;\ell_{k}$, where $\ell_{1}=1$ and
$\ell_{k}=k$, by

$K\big{(}P^{1,k}_{\theta}\big{)}=\prod_{j=1}^{k-1}K_{\ell_{j},\ell_{j+1}},$

we have

$Z=2\,(-1)^{k+1}\,K_{k,1}K\big{(}P^{1,k}_{0}\big{)}\sum_{\theta\in\mathbb{Z}_{2}^{p}}\frac{K\big{(}P^{1,k}_{\theta}\big{)}}{K\big{(}P^{1,k}_{0}\big{)}}.$

Suppose that the first possible crossing occurs at cycle edges $\\{a,a+1\\}$
and $\\{b-1,b\\}$, $a<b$, i.e., $\\{a,b-1\\}$ and $\\{a+1,b\\}$ are crossing
chords. Then

$Z=2\,(-1)^{k+1}\,K_{k,1}K\big{(}P^{1,k}_{0}\big{)}\sum_{\theta\in\mathbb{Z}_{2}^{p}}\frac{K\big{(}P^{a,b}_{\theta}\big{)}}{K\big{(}P^{a,b}_{0}\big{)}}.$

We have

$\sum_{\theta\in\mathbb{Z}_{2}^{p}}K\big{(}P^{a,b}_{\theta}\big{)}=\sum_{\theta_{1}=0}K\big{(}P^{a,b}_{\theta}\big{)}+\sum_{\theta_{1}=1}K\big{(}P^{a,b}_{\theta}\big{)},$

and

$\displaystyle\sum_{\theta_{1}=0}K\big{(}P^{a,b}_{\theta}\big{)}$
$\displaystyle=K_{a,a+1}K_{b-1,b}\sum_{\theta^{\prime}\in\mathbb{Z}_{2}^{p-1}}K\big{(}P^{a+1,b-1}_{\theta^{\prime}}\big{)},$
$\displaystyle\sum_{\theta_{1}=1}K\big{(}P^{a,b}_{\theta}\big{)}$
$\displaystyle=K_{a,b-1}K_{a+1,b}\sum_{\theta^{\prime}\in\mathbb{Z}_{2}^{p-1}}K\big{(}P^{b-1,a+1}_{\theta^{\prime}}\big{)}$
$\displaystyle=K_{a,b-1}K_{a+1,b}\sum_{\theta^{\prime}\in\mathbb{Z}_{2}^{p-1}}K\big{(}P^{a+1,b-1}_{\theta^{\prime}}\big{)}\epsilon\big{(}P^{a+1,b-1}_{\theta^{\prime}}\big{)}.$

By Property (i) of Lemma 1, $\epsilon\big{(}C(a,b-1)\big{)}=-1$, and so

$\epsilon\big{(}P^{a+1,b-1}_{\theta^{\prime}}\big{)}=-\epsilon_{b-1,a}\epsilon_{a,a+1}\quad\text{and}\quad
K_{a,b-1}\epsilon\big{(}P^{a+1,b-1}_{\theta^{\prime}}\big{)}=-\epsilon_{a,a+1}K_{b-1,a}.$

This implies that

$\displaystyle\sum_{\theta\in\mathbb{Z}_{2}^{p}}K\big{(}P^{a,b}_{\theta}\big{)}$
$\displaystyle=\big{(}K_{a,a+1}K_{b-1,b}-\epsilon_{a,a+1}K_{b-1,a}K_{a+1,b}\big{)}\sum_{\theta^{\prime}\in\mathbb{Z}_{2}^{p-1}}K\big{(}P^{a+1,b-1}_{\theta^{\prime}}\big{)},$

and that

$\sum_{\theta\in\mathbb{Z}_{2}^{p}}\frac{K\big{(}P^{a,b}_{\theta}\big{)}}{K\big{(}P^{a,b}_{0}\big{)}}=\left(1-\frac{\epsilon_{a,a+1}K_{b-1,a}K_{a+1,b}}{K_{a,a+1}K_{b-1,b}}\right)\sum_{\theta^{\prime}\in\mathbb{Z}_{2}^{p-1}}\frac{K\big{(}P^{a+1,b-1}_{\theta^{\prime}}\big{)}}{K\big{(}P^{a+1,b-1}_{0}\big{)}}.$

Repeating the above procedure for the remaining $p-1$ crossings completes the
proof. ∎

Equipped with Lemmas 1, 2, 3, and 4, we can now make a key observation.
Suppose that we have a simple cycle basis $\\{x_{1},...,x_{\nu-1}\\}$ for
$\mathcal{C}^{+}(G)$ whose corresponding cycles all satisfy Properties
(i)-(iii) of Lemma 1. Of course, a minimal simple cycle basis satisfies this,
but in Section 5 we will consider alternate bases that also satisfy these
conditions and may be easier to compute in practice. For cycles $C$ of length
at most four, we have already detailed how to compute $s(C)$, and this
computation requires only principal minors corresponding to subsets of $V(C)$.
When $C$ is of length greater than four, by Lemmas 3 and 4, we can also
compute $s(C)$, using only principal minors corresponding to subsets of
$V(C)$, as the quantity
$\text{sgn}(K_{i_{1},i_{k-1}}K_{i_{k-1},i_{k}}K_{i_{k},i_{2}}K_{i_{2},i_{1}})$
in Lemma 3 corresponds to a positive four-cycle, and in Lemma 4 the quantity

$\text{sgn}\bigg{(}1-\frac{\epsilon_{i_{a},i_{a+1}}K_{i_{b-1},i_{a}}K_{i_{a+1},i_{b}}}{K_{i_{a},i_{a+1}}K_{i_{b-1},i_{b}}}\bigg{)}$

equals $+1$ if
$|K_{i_{a},i_{a+1}}K_{i_{b-1},i_{b}}|>|K_{i_{b-1},i_{a}}K_{i_{a+1},i_{b}}|$
and equals

$-\epsilon_{i_{a},i_{a+1}}\epsilon_{i_{b-1},i_{b}}\,\text{sgn}\big{(}K_{i_{a},i_{a+1}}K_{i_{a+1},i_{b}}K_{i_{b},i_{b-1}}K_{i_{b-1},i_{a}}\big{)}$

if
$|K_{i_{a},i_{a+1}}K_{i_{b-1},i_{b}}|<|K_{i_{b-1},i_{a}}K_{i_{a+1},i_{b}}|$.
By Condition 1, we have
$|K_{i_{a},i_{a+1}}K_{i_{b-1},i_{b}}|\neq|K_{i_{b-1},i_{a}}K_{i_{a+1},i_{b}}|$.
Therefore, given a simple cycle basis $\\{x_{1},...,x_{\nu-1}\\}$ whose
corresponding cycles satisfy Properties (i)-(iii) of Lemma 1, we can compute
$s(C)$ for every such cycle in the basis using only principal minors of size
at most the length of the longest cycle in the basis. Given this fact, we are
now prepared to answer (PMA1) (in Theorem 1) and provide an alternate proof
for (PMA2) (in Proposition 3) through the following proposition and theorem.

######  Proposition 3.

Let $K\in\mathcal{K}$, with charged sparsity graph $G=([N],E,\epsilon)$. The
set of $K^{\prime}\in\mathcal{K}$ that satisfy
$\Delta_{S}(K)=\Delta_{S}(K^{\prime})$ for all $S\subseteq[N]$ is exactly the
set generated by $K$ and the operations

  1. $\mathcal{D}_{N}$-similarity:

$K\rightarrow DKD$, where $D\in\mathbb{R}^{N\times N}$ is an arbitrary
involutory diagonal matrix, i.e., $D$ has entries $\pm 1$ on the diagonal, and

  2. block transpose:

$K\rightarrow K^{\prime}$, where $K^{\prime}_{i,j}=K_{j,i}$ for all $i,j\in
V(H)$ for some block $H$ of $G$, and $K^{\prime}_{i,j}=K_{i,j}$ otherwise.

###### Proof.

We first verify that the $\mathcal{D}_{N}$-similarity and block transpose
operations both preserve principal minors. The determinant is multiplicative,
and so principal minors are immediately preserved under
$\mathcal{D}_{N}$-similarity, as the principal submatrix of $DKD$
corresponding to $S$ is equal to the product of the principal submatrices
corresponding to $S$ of the three matrices $D$, $K$, $D$, and so
$\Delta_{S}(DKD)=\Delta_{S}(D)\Delta_{S}(K)\Delta_{S}(D)=\Delta_{S}(K)$. For
the block transpose operation, we note that the transpose leaves the
determinant unchanged. By Equation (2), the principal minors of a matrix are
uniquely determined by the principal minors of the matrices corresponding to
the blocks of $G$. As the transpose of any block also leaves the principal
minors corresponding to subsets of other blocks unchanged, principal minors
are preserved under block transpose.

What remains is to show that if $K^{\prime}$ satisfies
$\Delta_{S}(K)=\Delta_{S}(K^{\prime})$ for all $S\subseteq[N]$, then
$K^{\prime}$ is generated by $K$ and the above two operations. Without loss of
generality, we may suppose that the shared charged sparsity graph
$G=([N],E,\epsilon)$ of $K$ and $K^{\prime}$ is two-connected, as the general
case follows from this one. We will transform $K^{\prime}$ to $K$ by first
making them agree for entries corresponding to a spanning tree and a negative
edge of $G$, and then observing that by Lemmas 3 and 4, this property implies
that all entries agree.

Let $C^{\prime}$ be an arbitrary negative simple cycle of $G$, $e\in
E(C^{\prime})$ be a negative edge in $C^{\prime}$, and $T$ be a spanning tree
of $G$ containing the edges $E(C^{\prime})\,\backslash\,e$. By applying
$\mathcal{D}_{N}$-similarity and block transpose to $K^{\prime}$, we can
produce a matrix that agrees with $K$ for all entries corresponding to edges
in $E(T)\cup e$. We perform this procedure in three steps, first by making
$K^{\prime}$ agree with $K$ for edges in $E(T)$, then for edge $e$, and then
finally fixing any edges in $E(T)$ for which the matrices no longer agree.

First, we make $K^{\prime}$ and $K$ agree for edges in $E(T)$. Suppose that
$K^{\prime}_{p,q}=-K_{p,q}$ for some $\\{p,q\\}\in E(T)$. Let $U\subseteq[N]$
be the set of vertices connected to $p$ in the forest
$T\,\backslash\,\\{p,q\\}$ (the removal of edge $\\{p,q\\}$ from $T$), and
$\hat{D}$ be the diagonal matrix with $\hat{D}_{i,i}=+1$ if $i\in U$ and
$\hat{D}_{i,i}=-1$ if $i\not\in U$. The matrix $\hat{D}K^{\prime}\hat{D}$
satisfies

$\big{[}\hat{D}K^{\prime}\hat{D}\big{]}_{p,q}=\hat{D}_{p,p}K^{\prime}_{p,q}\hat{D}_{q,q}=-K^{\prime}_{p,q}=K_{p,q},$

and $\big{[}\hat{D}K^{\prime}\hat{D}\big{]}_{i,j}=K^{\prime}_{i,j}$ for any
$i,j$ either both in $U$ or neither in $U$ (and therefore for all edges
$\\{i,j\\}\in E(T)\,\backslash\,\\{p,q\\}$). Repeating this procedure for
every edge $\\{p,q\\}\in E(T)$ for which $K^{\prime}_{p,q}=-K_{p,q}$ results
in a matrix that agrees with $K$ for all entries corresponding to edges in
$E(T)$.

Next, we make our matrix and $K$ agree for the edge $e$. If our matrix already
agrees for edge $e$, then we are done with this part of the proof, and we
denote the resulting matrix by $\hat{K}$. If it does not agree, then, by
taking the transpose of this matrix, we have a new matrix that now agrees with
$K$ for all edges $E(T)\cup e$, except for negative edges in $E(T)$. By
repeating the $\mathcal{D}_{N}$-similarity operation again on negative edges
of $E(T)$, we again obtain a matrix that agrees with $K$ on the edges of
$E(T)$, but now also agrees on the edge $e$, as there is an even number of
negative edges in the path between the vertices of $e$ in the tree $T$. We now
have a matrix that agrees with $K$ for all entries corresponding to edges in
$E(T)\cup e$, and we denote this matrix by $\hat{K}$.

Finally, we aim to show that agreement on the edges $E(T)\cup e$ already
implies that $\hat{K}=K$. Let $\\{i,j\\}$ be an arbitrary edge not in
$E(T)\cup e$, and $\hat{C}$ be the simple cycle containing edge $\\{i,j\\}$
and the unique $i-j$ path in the tree $T$. By Lemmas 3 and 4, the value of
$s_{K}(C)$ can be computed for every cycle corresponding to an incidence
vector in a minimal simple cycle basis of $\mathcal{C}^{+}(G)$ using only
principal minors. Then $s_{K}(\hat{C})$ can be computed using principal minors
and $s_{K}(C^{\prime})$, as the incidence vector for $C^{\prime}$ combined
with a minimal positive simple cycle basis forms a basis for $\mathcal{C}(G)$.
By assumption, $\Delta_{S}(K)=\Delta_{S}(\hat{K})$ for all $S\subseteq[N]$,
and, by construction, $s_{K}(C^{\prime})=s_{\hat{K}}(C^{\prime})$. Therefore,
$s_{K}(\hat{C})=s_{\hat{K}}(\hat{C})$ for all $\\{i,j\\}$ not in $E(T)\cup e$,
and so $\hat{K}=K$. ∎

######  Theorem 1.

Let $K\in\mathcal{K}$, with charged sparsity graph $G=([N],E,\epsilon)$. Let
$\ell_{+}\geq 3$ be the simple cycle sparsity of $\mathcal{C}^{+}(G)$. Then
any matrix $K^{\prime}\in\mathcal{K}$ with
$\Delta_{S}(K)=\Delta_{S}(K^{\prime})$ for all $|S|\leq\ell_{+}$ also
satisfies $\Delta_{S}(K)=\Delta_{S}(K^{\prime})$ for all $S\subseteq[N]$, and
there exists a matrix $\hat{K}\in\mathcal{K}$ with
$\Delta_{S}(\hat{K})=\Delta_{S}(K)$ for all $|S|<\ell_{+}$ but
$\Delta_{S}(\hat{K})\neq\Delta_{S}(K)$ for some $|S|=\ell_{+}$.

###### Proof.

The first part of theorem follows almost immediately from Lemmas 3 and 4. It
suffices to consider a matrix $K\in\mathcal{K}$ with a two-connected charged
sparsity graph $G=([N],E,\epsilon)$, as the more general case follows from
this one. By Lemmas 3, and 4, the quantity $s(C)$ is computable for all simple
cycles $C$ in a minimal cycle basis for $\mathcal{C}^{+}(G)$ (and therefore
for all positive simple cycles), using only principal minors of size at most
the length of the longest cycle in the basis, which in this case is the simple
cycle sparsity $\ell_{+}$ of $\mathcal{C}^{+}(G)$. The values $s(C)$ for
positive simple cycles combined with the magnitude of the entries of $K$ and
the charge function $\epsilon$ uniquely determines all principal minors, as
each term in the Leibniz expansion of some $\Delta_{S}(K)$ corresponds to a
partitioning of $S$ into a disjoint collection of vertices, pairs
corresponding to edges, and oriented versions of positive simple cycles of
$E(S)$. This completes the first portion of the proof.

Next, we explicitly construct a matrix $\hat{K}$ that agrees with $K$ in the
first $\ell_{+}-1$ principal minors ($\ell_{+}\geq 3$), but disagrees on a
principal minor of order $\ell_{+}$. To do so, we consider a minimal simple
cycle basis $\big{\\{}\chi_{C_{1}},...,\chi_{C_{\nu-1}}\big{\\}}$ of
$\mathcal{C}^{+}(G)$, ordered so that
$|C_{1}|\geq|C_{2}|\geq...\geq|C_{\nu-1}|$. By definition, $\ell_{+}=|C_{1}|$.
Let $\hat{K}$ be a matrix satisfying

$\hat{K}_{i,i}=K_{i,i}\text{ for
}i\in[N],\qquad\hat{K}_{i,j}\hat{K}_{j,i}=K_{i,j}K_{j,i}\text{ for
}i,j\in[N],$

and

$s_{\hat{K}}(C_{i})=\begin{cases}\text{ }s_{K}(C_{i})&\text{if }i>1\\\
-s_{K}(C_{i})&\text{if }i=1\end{cases}.$

The matrices $\hat{K}$ and $K$ agree on all principal minors of order at most
$\ell_{+}-1$, for if there was a principal minor where they disagreed, this
would imply that there is a positive simple cycle of length less than
$\ell_{+}$ whose incidence vector is not in the span of
$\\{\chi_{C_{2}},...,\chi_{C_{\nu-1}}\\}$, a contradiction. To complete the
proof, it suffices to show that
$\Delta_{V(C_{1})}(\hat{K})\neq\Delta_{V(C_{1})}(K)$.

To do so, we consider three different cases, depending on the length of
$C_{1}$. If $C_{1}$ is a three-cycle, then $C_{1}$ is an induced cycle and the
result follows immediately. If $C_{1}$ is a four-cycle, $G[V(C_{1})]$ may
possibly have multiple positive four-cycles. However, in this case the
quantity $Z$ from Equation (6) is distinct for $\hat{K}$ and $K$, as
$K\in\mathcal{K}$. Finally, we consider the general case when $|C_{1}|>4$. By
Lemma 3, all terms of $\Delta_{V(C)}(K)$ (and $\Delta_{V(C)}(\hat{K})$) except
for $Z$ depend only on principal minors of order at most $\ell_{+}-1$. We
denote the quantity $Z$ from Lemma 3 for $K$ and $\hat{K}$ by $Z$ and
$\hat{Z}$ respectively. By Lemma 4, the magnitude of $Z$ and $\hat{Z}$ depend
only on principal minors of order at most four, and so $|Z|=|\hat{Z}|$. In
addition, because $K\in\mathcal{K}$, $Z\neq 0$. The quantities $Z$ and
$\hat{Z}$ are equal in sign if and only if $s_{\hat{K}}(C_{1})=s_{K}(C_{1})$,
and therefore $\Delta_{V(C_{1})}(\hat{K})\neq\Delta_{V(C_{1})}(K)$. ∎

##  5\. Efficiently Recovering a Matrix from its Principal Minors

In Section 4, we characterized the set of magnitude-symmetric matrices in
$\mathcal{K}$ that share a given set of principal minors, and noted that
principal minors of order $\leq\ell_{+}$ uniquely determine principal minors
of all orders, where $\ell_{+}$ is the simple cycle sparsity of
$\mathcal{C}^{+}(G)$ and is computable using principal minors of order one and
two. In this section, we make use of a number of theoretical results of
Sections 3 and 4 to formally describe a polynomial-time algorithm to produce a
magnitude-symmetric matrix $K$ with prescribed principal minors. We provide a
high-level description and discussion of this algorithm in Subsection 5.1, and
save the description of a key subroutine for computing a positive simple cycle
basis for Subsection 5.2. In addition, in Subsection 5.3, we consider the more
general setting in which principal minors are only approximately known up to
some bounded additive error.

###  5.1. An Efficient Algorithm

Our algorithm proceeds by completing a number of tasks which we describe
below. This procedure is very similar in nature to the algorithm implicitly
described and used in the proofs of Proposition 3 and Theorem 1. The main
difference between the procedure alluded to in Section 4 and our algorithm is
the computation of a positive simple cycle basis. Unlike $\mathcal{C}(G)$,
there is no known polynomial-time algorithm to compute a minimal simple cycle
basis for $\mathcal{C}^{+}(G)$, and a decision version of this problem may
indeed be NP-hard. Our algorithm, which we denote by
RecoverK$\big{(}(\Delta_{S})_{S\subseteq[N]}\big{)}$, proceeds in five main
steps:

Step 1: Compute $K_{i,i}$, $i\in[N]$, $|K_{i,j}|$, $i\neq j$, and
$G_{K}=([N],E,\epsilon)$.

We recall that $K_{i,i}=\Delta_{i}$ and
$|K_{i,j}|=|K_{j,i}|=\sqrt{|\Delta_{i}\Delta_{j}-\Delta_{i,j}|}$. The edges
$\\{i,j\\}\in E(G)$ correspond to non-zero off-diagonal entries $|K_{i,j}|\neq
0$, and the function $\epsilon$ is given by
$\epsilon_{i,j}=\text{sgn}(\Delta_{i}\Delta_{j}-\Delta_{i,j})$.

Step 2: For every block $H$ of $G$, compute a simple cycle basis
$\\{x_{1},...,x_{k}\\}$ of $\mathcal{C}^{+}(H)$.

In the proof of Proposition 2, we defined an efficient algorithm to compute a
simple cycle basis of $\mathcal{C}^{+}(H)$ for any two-connected graph $H$.
This algorithm makes use of the property that every two-connected graph has an
open ear decomposition. Unfortunately, this algorithm has no provable
guarantees on the length of the longest cycle in the basis. For this reason,
we introduce an alternate efficient algorithm in Subsection 5.2 that computes
a simple cycle basis of $\mathcal{C}^{+}(H)$ consisting of cycles all of
length at most $3\phi_{H}$, where $\phi_{H}$ is the maximum length of a
shortest cycle between any two edges in $H$, i.e.,

$\phi_{H}:=\max_{e,e^{\prime}\in E(H)}\;\min_{\begin{subarray}{c}\text{simple
cycle }C\\\ s.t.\,e,e^{\prime}\in E(C)\end{subarray}}\;|C|$

with $\phi_{H}:=2$ if $H$ is acyclic. We define $\phi_{G}$ to be the maximum
of $\phi_{H}$ over all blocks $H$ of $G$, and $\phi_{G}:=2$ if $G$ has no
blocks. The existence of a simple cycle through any two edges of a non-trivial
two-connected graph can be deduced from the existence of two vertex-disjoint
paths between newly added midpoints of these two edges. The simple cycle basis
constructed in Subsection 5.2 also maximizes the number of three- and four-
cycles it contains. This is a key property which allows us to limit the number
of principal minors that we query.

Step 3: For every block $H$ of $G$, convert $\\{x_{1},...,x_{k}\\}$ into a
simple cycle basis satisfying Properties (i)-(iii) of Lemma 1.

If there was an efficient algorithm for computing a minimal simple cycle basis
for $\mathcal{C}^{+}(H)$, by Lemma 1, we would be done (and there would be no
need for this step). However, there is currently no known algorithm for this,
and a decision version of this problem may be NP-hard. By using the simple
cycle basis from Step 2 and iteratively removing chords, we can create a basis
that satisfies the same three key properties (in Lemma 1) that a minimal
simple cycle basis does. In addition, the lengths of the cycles in this basis
are no larger than those of Step 2, i.e., no procedure in Step 3 ever
increases the length of a cycle.

The procedure for this is quite intuitive. Given a cycle $C$ in the basis, we
efficiently check that $\gamma(C)$ satisfies Properties (i)-(iii) of Lemma 1.
If all properties hold, we are done, and check another cycle in the basis,
until all cycles satisfy the desired properties. In each case, if a given
property does not hold, then, by the proof of Lemma 1, we can efficiently
compute an alternate cycle $C^{\prime}$, $|C^{\prime}|<|C|$, that can replace
$C$ in the simple cycle basis for $\mathcal{C}^{+}(H)$, decreasing the sum of
cycle lengths in the basis by at least one. Because of this, the described
procedure is a polynomial-time algorithm.

Step 4: For every block $H$ of $G$, compute $s(C)$ for every cycle $C$ in the
basis.

This calculation relies heavily on the results of Section 4. The simple cycle
basis for $\mathcal{C}^{+}(H)$ satisfies Properties (i)-(iii) of Lemma 1, and
so we may apply Lemmas 3 and 4. We compute the quantities $s(C)$ iteratively
based on cycle length, beginning with the shortest cycle in the basis and
finishing with the longest. By the analysis in Section 2, we recall that when
$C$ is a three- or four-cycle, $s(C)$ can be computed efficiently using $O(1)$
principal minors, all corresponding to subsets of $V(C)$. When $|C|>4$, by
Lemma 3, the quantity $Z$ (defined in Lemma 3) can be computed efficiently
using $O(1)$ principal minors, all corresponding to subsets of $V(C)$. By
Lemma 4, the quantity $s(C)$ can be computed efficiently using $Z$,
$s(C^{\prime})$ for positive four-cycles $C^{\prime}\subseteq G[V(C)]$, and
$O(1)$ principal minors all corresponding to subsets of $V(C)$. Because our
basis maximizes the number of three- and four-cycles it contains, any such
four-cycle $C^{\prime}$ is either in the basis (and so $s(C^{\prime})$ has
already been computed) or is a linear combination of three- and four-cycles in
the basis, in which case $s(C^{\prime})$ can be computed using Gaussian
elimination, without any additional querying of principal minors.

Step 5: Output a matrix $K$ satisfying $\Delta_{S}(K)=\Delta_{S}$ for all
$S\subseteq[N]$.

The procedure for producing this matrix is quite similar to the proof of
Proposition 3. It suffices to fix the signs of the upper triangular entries of
$K$, as the lower triangular entries can be computed using $\epsilon$. For
each block $H$, we find a negative simple cycle $C$ (if one exists), fix a
negative edge $e\in E(C)$, and extend $E(C)\backslash e$ to a spanning tree
$T$ of $H$, i.e., $\big{[}E(C)\backslash e\big{]}\subseteq E(T)$. We give the
entries $K_{i,j}$, $i<j$, $\\{i,j\\}\in E(T)\cup e$ an arbitrary sign, and
note our choice of $s_{K}(C)$. We extend the simple cycle basis for
$\mathcal{C}^{+}(H)$ to a basis for $\mathcal{C}(H)$ by adding $C$. On the
other hand, if no negative cycle exists, then we simply fix an arbitrary
spanning tree $T$, and give the entries $K_{i,j}$, $i<j$, $\\{i,j\\}\in E(T)$
an arbitrary sign. In both cases, we have a basis for $\mathcal{C}(H)$
consisting of cycles $C_{i}$ for which we have computed $s(C_{i})$. For each
edge $\\{i,j\\}\in E(H)$ corresponding to an entry $K_{i,j}$ for which we have
not fixed the sign of, we consider the cycle $C^{\prime}$ consisting of the
edge $\\{i,j\\}$ and the unique $i-j$ path in $T$. Using Gaussian elimination,
we can write $C^{\prime}$ as a sum of a subset of the cycles in our basis. As
noted in Section 4, the quantity $s(C^{\prime})$ is simply the product of the
quantities $s(C_{i})$ for cycles $C_{i}$ in this sum.

A few comments are in order. Conditional on the analysis of Step 2, the above
algorithm runs in time polynomial in $N$. Of course, the set
$(\Delta_{S})_{S\subseteq[N]}$ is not polynomial in $N$, but rather than take
the entire set as input, we assume the existence of some querying operation in
which the value of any principal minor can be queried/computed in polynomial
time. Combining the analysis of each step, we can give the following guarantee
for the RecoverK$\left((\Delta_{S})_{S\subseteq[N]}\right)$ algorithm.

######  Theorem 2.

Let $K\in\mathcal{K}$ and let $\Delta_{S}=\Delta_{S}(K)$, for all
$S\subseteq[N]$.

  * •

The algorithm RecoverK$\big{(}(\Delta_{S})_{S\subseteq[N]}\big{)}$ computes a
matrix $K^{\prime}\in\mathcal{K}$ satisfying
$\Delta_{S}(K^{\prime})=\Delta_{S}$ for all $S\subseteq[N]$. This algorithm
runs in time polynomial in $N$ and queries at most $O(N^{2})$ principal
minors, all of order at most $3\,\phi_{G}$, where $G$ is the sparsity graph of
$K$.

  * •

In addition, there exists a matrix $\tilde{K}\in\mathcal{K}$, with
$|\tilde{K}_{i,j}|=|K_{i,j}|$ for all $i,j\in[N]$, such that any algorithm
that computes a matrix with principal minors
$(\Delta_{S}(\tilde{K}))_{S\subset[N]}$ must query a principal minor of order
at least $\phi_{G}$.

The first part of this theorem provides an upper bound for the complexity of
solving (PMA3). The second part asserts that given any $K\in\mathcal{K}$, one
can change the charges of $K$ such that any algorithm that solves (PMA3) given
the principal minors of the new matrix needs to query a principal minor of
high order - namely, of order at least $\phi_{G}$.

###### Proof.

Conditional on the existence of the algorithm described in Step 2, i.e., an
efficient algorithm to compute a simple cycle basis for $\mathcal{C}^{+}(H)$
consisting of cycles of length at most $3\phi_{H}$ that maximizes the number
of three- and four-cycles it contains, by the above analysis we already have
shown that the RecoverK$\big{(}(\Delta_{S})\big{)}$ algorithm runs in time
polynomial in $N$ and queries at most $O(N^{2})$ principal minors.

To construct $K^{\prime}$, we first consider the uncharged sparsity graph
$G=([N],E)$ of $K$, and let $e,e^{\prime}\in E(G)$ be a pair of edges for
which the quantity $\phi_{G}$ is achieved (if $\phi_{G}=2$, we are done). We
aim to define an alternate charge function for $G$, show that the simple cycle
sparsity of $\mathcal{C}^{+}(G)$ is at least $\phi_{G}$, find a matrix
$K^{\prime}$ that has this charged sparsity graph, and then make use of
Theorem 1. Consider the charge function $\epsilon$ satisfying
$\epsilon(e)=\epsilon(e^{\prime})=-1$, and equal to $+1$ otherwise. Any
positive simple cycle basis for the block containing $e,e^{\prime}$ must have
a simple cycle containing both edges $e,e^{\prime}$. By definition, the length
of this cycle is at least $\phi_{G}$, and so the simple cycle sparsity of
$\mathcal{C}^{+}(G)$ is at least $\phi_{G}$. Next, let $K^{\prime}$ be an
arbitrary matrix with $|K^{\prime}_{i,j}|=|K_{i,j}|$, $i,j\in[N]$, and charged
sparsity graph $G=([N],E,\epsilon)$, with $\epsilon$ as defined above.
$K\in\mathcal{K}$, and so $K^{\prime}\in\mathcal{K}$, and therefore, by
Theorem 1, any algorithm that computes a matrix with principal minors
$(\Delta_{S}(K^{\prime}))_{S\subset[N]}$ must query a principal minor of order
at least $\ell_{+}\geq\phi_{G}$. ∎

###  5.2. Computing a Simple Cycle Basis with Provable Guarantees

Let $H=([N],E,\varepsilon)$ be a two-connected charged graph. We now describe
an efficient algorithm to compute a simple cycle basis for
$\mathcal{C}^{+}(H)$ consisting of cycles of length at most $3\phi_{H}$. We
first compute a minimal cycle basis $\\{\chi_{C_{1}},...,\chi_{C_{\nu}}\\}$ of
$\mathcal{C}(H)$, where each $C_{i}$ is an induced simple cycle (as argued
previously, any lexicographically minimal basis for $\mathcal{C}(H)$ consists
only of induced simple cycles). Without loss of generality, suppose that
$C_{1}$ is the shortest negative cycle in the basis (if no negative cycle
exists, we are done). The set of incidence vectors
$\chi_{C_{1}}+\chi_{C_{i}}$, $\epsilon(C_{i})=-1$, combined with vectors
$\chi_{C_{j}}$, $\epsilon(C_{j})=+1$, forms a basis for $\mathcal{C}^{+}(H)$,
which we denote by $\mathcal{B}$. We will build a simple cycle basis for
$\mathcal{C}^{+}(H)$ by iteratively choosing incidence vectors of the form
$\chi_{C_{1}}+\chi_{C_{i}}$, $\epsilon(C_{i})=-1$, replacing each of them with
an incidence vector $\chi_{\widetilde{C}_{i}}$ corresponding to a positive
simple cycle $\widetilde{C}_{i}$, and iteratively updating $\mathcal{B}$.

Let $C:=C_{1}+C_{i}$ be a positive cycle in our basis $\mathcal{B}$. If $C$ is
a simple cycle, we are done, otherwise $C$ is the union of edge-disjoint
simple cycles $F_{1},...,F_{p}$ for some $p>1$. If one of these simple cycles
is positive and satisfies

$\chi_{F_{j}}\not\in\text{span}\big{\\{}\mathcal{B}\backslash\\{\chi_{C_{1}}+\chi_{C_{i}}\\}\big{\\}},$

we simply replace $C$ with $F_{j}$ and we are done. Otherwise, one of
$F_{1},\ldots,F_{p}$ must be a negative simple cycle. Indeed, if all $F_{j}$’s
were positive, then
$\chi_{F_{j}}\in\text{span}\big{\\{}\mathcal{B}\backslash\\{\chi_{C_{1}}+\chi_{C_{i}}\\}\big{\\}}$
for all $j=1,\ldots,p$, yielding that
$\chi_{C}=\chi_{F_{1}}+\ldots+\chi_{F_{p}}\in\text{span}\big{\\{}\mathcal{B}\backslash\\{\chi_{C_{1}}+\chi_{C_{i}}\\}\big{\\}}$,
which is impossible. Without loss of generality, assume that $F_{1}$ is a
negative cycle. We can construct a set of $p-1$ positive cycles by taking
$F_{1}+F_{j}$ for all $j=1,\ldots,p$ with $\varepsilon(F_{j})=-1$ and keeping
all positive $F_{j}$’s, and at least one of these cycles is not in
$\text{span}\big{\\{}\mathcal{B}\backslash\\{\chi_{C_{1}}+\chi_{C_{i}}\\}\big{\\}}$.
We now have a positive cycle not in this span, given by the sum of two edge-
disjoint negative simple cycles $F_{1}$ and $F_{j}$. These two cycles satisfy,
by construction, $|F_{1}|+|F_{j}|\leq|C|\leq 2\ell$, where $\ell$ is the cycle
sparsity of $\mathcal{C}(H)$. If $|V(F_{1})\cap V(F_{j})|>1$, then $F_{1}\cup
F_{j}$ is two-connected, and we may compute a simple cycle basis for
$\mathcal{C}^{+}(F_{1}\cup F_{j})$ using the ear decomposition approach of
Proposition 2. At least one positive simple cycle in this basis satisfies our
desired condition, and the length of this positive simple cycle is at most
$|E(F_{1}\cup F_{j})|\leq 2\ell$. If $F_{1}\cup F_{j}$ is not two-connected,
then we compute a shortest cycle $\widetilde{C}$ in $E(H)$ containing both an
edge in $E(F_{1})$ and $E(F_{j})$ (computed using Suurballe’s algorithm, see
[20] for details). The graph

$H^{\prime}=\big{(}V(F_{1})\cup V(F_{j})\cup V(\widetilde{C}),E(F_{1})\cup
E(F_{j})\cup E(\widetilde{C})\big{)}$

is two-connected, and we can repeat the same procedure as above for
$H^{\prime}$, where, in this case, the resulting cycle is of length at most
$|E(H^{\prime})|\leq 2\ell+\phi_{H}$. The additional guarantee for maximizing
the number of three- and four-cycles can be obtained easily by simply listing
all positive simple cycles of length three and four, combining them with the
computed basis, and performing a greedy algorithm. What remains is to note
that $\ell\leq\phi_{H}$. This follows quickly from the observation that for
any vertex $u$ in any simple cycle $C$ of a minimal cycle basis for
$\mathcal{C}(H)$, there exists an edge $\\{v,w\\}\in E(C)$ such that $C$ is
the disjoint union of a shortest $u-v$ path, shortest $u-w$ path, and
$\\{v,w\\}$ [10, Theorem 3].

###  5.3. An Algorithm for Principal Minors with Noise

So far, we have exclusively considered the situation in which principal minors
are known (or can be queried) exactly. In applications related to this work,
this is often not the case. A key application of a large part of this work is
signed determinantal point processes, and the algorithmic question of learning
the kernel of a signed DPP from some set of samples. Here, for the sake of
readability, we focus on a non-probabilistic setting. When principal minors
are approximated by random samples from a DPP, the below results can be easily
converted to high probability guarantees via a union bound. Given some unknown
matrix $K\in\mathcal{K}$ with all principal minors satisfying
$|\Delta_{S}(K)|\leq 1,S\subseteq[N]$, each $\Delta_{S}(K)$ can be
queried/estimated up to some absolute error term $0<\delta<1$, i.e., we have
access to a collection $(\hat{\Delta}_{S})_{S\subseteq[N]}$, satisfying

$\big{|}\hat{\Delta}_{S}-\Delta_{S}(K)\big{|}\leq\delta\qquad\text{for all
}S\subseteq[N].$

Our goal is to compute a matrix $K^{\prime}$ with small error, measured by the
quantity

$\rho(K,K^{\prime}):=\;\min\big{\\{}|\hat{K}-K^{\prime}|_{\infty}\quad\text{s.t.}\quad\hat{K}\in\mathcal{K},\;\Delta_{S}(\hat{K})=\Delta_{S}(K)\text{
for all }S\subseteq[N]\big{\\}},$

where $|K-K^{\prime}|_{\infty}:=\max_{1\leq i,j\leq
N}|K_{i,j}-K^{\prime}_{i,j}|$. We note that because $|\Delta_{S}(K)|\leq 1$,
for all $S\subseteq[N]$, we may always assume that $|\hat{\Delta}_{S}|\leq 1$
as well, for if it is not, then we may safely replace it with
$\text{sgn}(\hat{\Delta}_{S})$. In this setting, we require both a separation
condition for the entries of $K$ and a stronger version of Condition 1. Let
$\alpha,\beta,\gamma\in(0,1]$.

######  Condition 2.

For all $i,j\in[N]$ with $i\neq j$, either $|K_{i,j}|=0$ or
$|K_{i,j}|\geq\alpha$ and if $K_{i,j}K_{j,k}K_{k,\ell}K_{\ell,i}\neq 0$ for
some distinct $i,j,k,\ell\in[N]$, then

  * (i)

$\big{|}|K_{i,j}K_{k,\ell}|-|K_{j,k}K_{\ell,i}|\big{|}\geq\beta$;

  * (ii)

For each $\phi_{1},\phi_{2},\phi_{3}\in\\{-1,1\\}$,

$\big{|}\phi_{1}\,K_{i,j}K_{j,k}K_{k,\ell}K_{\ell,i}+\phi_{2}K_{i,j}K_{j,\ell}K_{\ell,k}K_{k,i}+\phi_{3}K_{i,k}K_{k,j}K_{j,\ell}K_{\ell,i}\big{|}\geq\gamma.$

We denote by $\mathcal{K}_{N}(\alpha,\beta,\gamma)$ the set of matrices
$K\in\mathcal{K}_{N}$ satisfying Condition 2 and such that
$|\Delta_{S}(K)|\leq 1$ for all $S\subseteq[N]$. Condition 2 is a stronger
version of Condition 1 that accounts for the error in principal minors.

The algorithm RecoverK, slightly modified, performs well for this more general
problem. In Appendix A, we define a natural modification, called RecoverK≈.
The following theorem illustrates that for $\delta$ sufficiently small (with
respect to $\alpha,\beta,\gamma$) our algorithm performs well.

######  Theorem 3.

Let $K\in\mathcal{K}_{N}(\alpha,\beta,\gamma)$ and
$\\{\hat{\Delta}_{S}\\}_{S\subseteq[N]}$ satisfy
$|\hat{\Delta}_{S}-\Delta_{S}(K)|\leq\delta$ for all $S\subseteq[N]$, for some

$\delta<\alpha\min\\{\alpha^{3\phi_{G}},\beta^{3\phi_{G}/2},\gamma\\}/100,$

where $G$ is the sparsity graph of $K$. The
RecoverK≈$\big{(}\\{\hat{\Delta}_{S}\\},\,\delta\big{)}$ algorithm outputs a
matrix $K^{\prime}$ satisfying

$\rho(K,K^{\prime})\leq 3\delta/2\alpha.$

This algorithm runs in time polynomial in $N$, and queries at most $O(N^{2})$
principal minors, all of order at most $3\,\phi_{G}$.

The formal description of the RecoverK≈ algorithm, as well as the proof of
Theorem 3, adds little insight to the problem itself, and is reserved for
Appendix A. The following example illustrates why the requirement on $\delta$
in Theorem 3 cannot be improved in general (up to multiplicative constants in
the exponent) for any algorithm. In the below example,
$\delta=O(\min(\alpha^{\phi_{G}},\beta^{\phi_{G}/2}))$, and there are two
possible choices for $K$ for which any output matrix has
$\rho(\cdot,K^{\prime})\geq\alpha$ for at least one of these two choices.

######  Example 1.

Let $G=([N],E,\epsilon)$, where $N>4$ and even,

$E=\\{1,N\\}\cup\big{\\{}\\{i,i+1\\}\big{\\}}_{i=1}^{N-1}\cup\big{\\{}\\{i,N-i\\},\\{i+1,N-i+1\\}\big{\\}}_{i=1}^{N/2-1},$

and

$\epsilon(e)=\begin{cases}-1&\text{for }e=\\{1,N\\},\\{N/2,N/2+1\\},\\\
+1&\text{otherwise}\end{cases}.$

This graph can be thought of as an $N$ vertex cycle $C:=1\;2\;...\;N\;1$ with
$N/2-1$ pairs of crossing chords between edges $\\{i,i+1\\}$ and
$\\{N-i,N-i+1\\}$, $i=1,...,N/2-1$. One key property of this graph is that any
positive simple cycle containing $\\{1,N\\}$ or $\\{N/2,N/2+1\\}$ must contain
both and span $[N]$. Consider
$K,\hat{K}\in\mathcal{K}_{n}(\alpha,\alpha^{2},2\alpha^{4})$ with charged
sparsity graph $G$, with

$K_{i,j}=\begin{cases}\sqrt{2}\alpha&\text{for
}\\{i,j\\}\in\big{\\{}\\{i,N-i\\},\\{i+1,N-i+1\\}\big{\\}}_{i=1}^{N/2-1}\\\
\alpha&\text{for }i\equiv j-1\mod N.\end{cases},$

i.e., $K$ equals $\sqrt{2}\alpha$ on the crossing chords, and $\alpha$ on the
cycle $C$, with the exception of $K_{1,N}=K_{N/2+1,N/2}=-\alpha$, and

$\hat{K}_{i,j}=\begin{cases}-K_{i,j}&\text{for }\\{i,j\\}=\\{1,N\\}\\\
K_{i,j}&\text{otherwise}\end{cases}.$

Any positive simple cycle containing $\\{1,N\\}$ is of length $N$, and so $K$
and $\hat{K}$ agree on all principal minors of order less than $N$. Using
Lemmas 3 and 4, we note that for $\Delta_{[N]}$, $K$ and $\hat{K}$ agree
everywhere except for the value of $Z$. Because $s_{K}(C)=-s_{\hat{K}}(C)$,
$Z_{K}=-Z_{\hat{K}}$, and

$\big{|}\Delta_{[N]}(K)-\Delta_{[N]}(\hat{K})\big{|}=2|Z_{K}|=4\alpha^{N}.$

Taking $\delta=2\alpha^{N}$, and setting

$\hat{\Delta}_{S}=\begin{cases}\Delta_{S}(K)&S\neq[N]\\\
(\Delta_{[N]}(K)+\Delta_{[N]}(\hat{K}))/2&S=[N]\end{cases},$

any matrix $K^{\prime}$ output from the input $\\{\hat{\Delta}_{S}\\}$ has
either $\rho(K,K^{\prime})\geq\alpha$ or $\rho(\hat{K},K^{\prime})\geq\alpha$.

## Acknowledgements

The work of J. Urschel was supported in part by ONR Research Contract
N00014-17-1-2177. This material is based upon work supported by the Institute
for Advanced Study and the National Science Foundation under Grant No.
DMS-1926686. The second author would like to thank Michel Goemans for many
interesting conversations on the subject. An earlier draft of this work
appeared in the second author’s PhD thesis [22]. The authors are grateful to
Louisa Thomas for greatly improving the style of presentation.

## References

  * [1] Nima Anari and Thuy-Duong Vuong.  Simple and near-optimal map inference for nonsymmetric dpps.  arXiv preprint arXiv:2102.05347, 2021.
  * [2] Julius Borcea, Petter Brändén, and Thomas Liggett.  Negative dependence and the geometry of polynomials.  Journal of the American Mathematical Society, 22(2):521–567, 2009\.
  * [3] Alexei Borodin.  Determinantal point processes.  arXiv preprint arXiv:0911.1153, 2009.
  * [4] Abderrahim Boussaïri and Brahim Chergui.  Skew-symmetric matrices and their principal minors.  Linear Algebra and its Applications, 485:47–57, 2015.
  * [5] Victor-Emmanuel Brunel.  Learning signed determinantal point processes through the principal minor assignment problem.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [6] Mike Gartrell, Victor-Emmanuel Brunel, Elvis Dohmatob, and Syrine Krichene.  Learning nonsymmetric determinantal point processes.  arXiv preprint arXiv:1905.12962, 2019.
  * [7] Mike Gartrell, Ulrich Paquet, and Noam Koenigstein.  Low-rank factorization of determinantal point processes.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
  * [8] Kent Griffin and Michael J Tsatsomeros.  Principal minors, part ii: The principal minor assignment problem.  Linear Algebra and its applications, 419(1):125–171, 2006.
  * [9] DJ Hartfiel and R Leowy.  On matrices having equal corresponding principal minors.  Linear algebra and its applications, 58:147–167, 1984.
  * [10] Joseph Douglas Horton.  A polynomial-time algorithm to find the shortest cycle basis of a graph.  SIAM Journal on Computing, 16(2):358–366, 1987.
  * [11] Charles R Johnson and Michael J Tsatsomeros.  Convex sets of nonsingular and P-matrices.  Linear and Multilinear Algebra, 38(3):233–239, 1995.
  * [12] Telikepalli Kavitha, Christian Liebchen, Kurt Mehlhorn, Dimitrios Michail, Romeo Rizzi, Torsten Ueckerdt, and Katharina A Zweig.  Cycle bases in graphs characterization, algorithms, complexity, and applications.  Computer Science Review, 3(4):199–243, 2009.
  * [13] B. Korte and J. Vygen.  Combinatorial Optimization: Theory and Algorithms.  Springer, 2011.
  * [14] Alex Kulesza and Ben Taskar.  Determinantal point processes for machine learning.  arXiv preprint arXiv:1207.6083, 2012.
  * [15] Raphael Loewy.  Principal minors and diagonal similarity of matrices.  Linear algebra and its applications, 78:23–64, 1986.
  * [16] Luke Oeding.  Set-theoretic defining equations of the variety of principal minors of symmetric matrices.  Algebra & Number Theory, 5(1):75–109, 2011.
  * [17] Jack Poulson.  High-performance sampling of generic determinantal point processes.  Philosophical Transactions of the Royal Society A, 378(2166):20190059, 2020.
  * [18] Justin Rising, Alex Kulesza, and Ben Taskar.  An efficient algorithm for the symmetric principal minor assignment problem.  Linear Algebra and its Applications, 473:126–144, 2015.
  * [19] Alexander Schrijver et al.  Combinatorial optimization: polyhedra and efficiency, volume 24.  Springer, 2003.
  * [20] JW Suurballe.  Disjoint paths in a network.  Networks, 4(2):125–145, 1974.
  * [21] John Urschel, Victor-Emmanuel Brunel, Ankur Moitra, and Philippe Rigollet.  Learning determinantal point processes with moments and cycles.  In International Conference on Machine Learning, pages 3511–3520. PMLR, 2017.
  * [22] John C Urschel.  Graphs, Principal Minors, and Eigenvalue Problems.  PhD thesis, Massachusetts Institute of Technology, 2021.
  * [23] H. Whitney.  Non-separable and planar graphs.  Transactions of the American Mathematical Society, 34:339–362, 1932\.

##  Appendix A The RecoverK≈ Algorithm and a Proof of Theorem 3

This Appendix consists of two parts: in Subsection A.1 we define the RecoverK≈
algorithm, and in Subsection A.2 we prove Theorem 3.

###  A.1. The RecoverK≈ Algorithm

The algorithm to compute a $K^{\prime}$ sufficiently close to $K$, denoted by
RecoverK≈ $\big{(}\\{\hat{\Delta}_{S}\\};\delta\big{)}$, proceeds in three
main steps:

Step 1: Compute $K^{\prime}_{i,i}$, $i\in[N]$, $|K^{\prime}_{i,j}|$, $i\neq
j$, and $G_{K^{\prime}}=([N],E,\epsilon)$.

We define $K^{\prime}_{i,i}=\hat{\Delta}_{i}$. The difference between the
quantities $K_{i,j}K_{j,i}=\Delta_{i}\Delta_{j}-\Delta_{i,j}$ and
$\hat{\Delta}_{i}\hat{\Delta}_{j}-\hat{\Delta}_{i,j}$ are at most

(8)
$\big{|}K_{i,j}K_{j,i}-(\hat{\Delta}_{i}\hat{\Delta}_{j}-\hat{\Delta}_{i,j})\big{|}\leq\big{|}\hat{\Delta}_{i}\big{|}\big{|}\Delta_{j}-\hat{\Delta}_{j}\big{|}+\big{|}\Delta_{j}\big{|}\big{|}\Delta_{i}-\hat{\Delta}_{i}\big{|}+\big{|}\Delta_{i,j}-\hat{\Delta}_{i,j}\big{|}\leq
3\delta,$

and so we impose

$K^{\prime}_{i,j}K^{\prime}_{j,i}:=\begin{cases}\hat{\Delta}_{i}\hat{\Delta}_{j}-\hat{\Delta}_{i,j}&\text{if}\quad|\hat{\Delta}_{i}\hat{\Delta}_{j}-\hat{\Delta}_{i,j}|>3\delta\\\
\qquad 0&\text{otherwise}\end{cases}.$

The edges $\\{i,j\\}\in E(G_{K^{\prime}})$ correspond to non-zero off-diagonal
entries $|K^{\prime}_{i,j}|\neq 0$, and the function $\epsilon$ is given by
$\epsilon_{i,j}=\text{sgn}(K^{\prime}_{i,j}K^{\prime}_{j,i})$. By
construction, $G_{K^{\prime}}$ is a subgraph of $G_{K}$, i.e., all edges of
$G_{K^{\prime}}$ are in $G_{K}$ and agree in sign.

Step 2: For every block $H$ of $G_{K^{\prime}}$, compute a simple cycle basis
$\\{x_{1},...,x_{k}\\}$ of $\mathcal{C}^{+}(H)$ satisfying Properties
(i)-(iii) of Lemma 1, and define $s_{K^{\prime}}(C)$ for every cycle $C$ in
the basis.

The computation of the simple cycle basis depends only on the graph, and so is
identical to Steps 1 and 2 of the RecoverK algorithm. The simple cycle basis
for $\mathcal{C}^{+}(H)$ satisfies Properties (i)-(iii) of Lemma 1, and so we
can apply Lemmas 3 and 4. We define the quantities $s_{K^{\prime}}(C)$, for
each cycle $C$ in our basis, iteratively based on cycle length, beginning with
the shortest cycle. Each definition is inspired by the corresponding equations
for the exact case.

Case I: $|C|=3$.

Let $C=i\,j\,k\,i$, $i<j<k$. Based on Equation (3) for
$K_{i,j}K_{j,k}K_{k,i}$, we define

$s_{K^{\prime}}(C):=\epsilon_{i,k}\;\text{sgn}\big{(}\hat{\Delta}_{i}\hat{\Delta}_{j}\hat{\Delta}_{k}-\big{[}\hat{\Delta}_{i}\hat{\Delta}_{j,k}+\hat{\Delta}_{j}\hat{\Delta}_{i,k}+\hat{\Delta}_{k}\hat{\Delta}_{i,j}\big{]}/2+\hat{\Delta}_{i,j,k}/2\big{)}.$

Case II: $|C|=4$.

Let $C=i\,j\,k\,\ell\,i$, $i<j<k<\ell$. We note that

$\displaystyle\Delta_{i,j,k,\ell}$
$\displaystyle=\Delta_{i,j}\Delta_{k,\ell}+\Delta_{i,k}\Delta_{j,\ell}+\Delta_{i,\ell}\Delta_{j,k}+\Delta_{i}\Delta_{j,k,\ell}+\Delta_{j}\Delta_{i,k,\ell}+\Delta_{k}\Delta_{i,j,\ell}$
$\displaystyle\quad+\Delta_{\ell}\Delta_{i,j,k}-2\Delta_{i}\Delta_{j}\Delta_{k,\ell}-2\Delta_{i}\Delta_{k}\Delta_{j,\ell}-2\Delta_{i}\Delta_{\ell}\Delta_{j,k}-2\Delta_{j}\Delta_{k}\Delta_{i,\ell}$
$\displaystyle\quad-2\Delta_{j}\Delta_{\ell}\Delta_{i,k}-2\Delta_{k}\Delta_{\ell}\Delta_{i,j}+6\Delta_{i}\Delta_{j}\Delta_{k}\Delta_{\ell}+Z,$

where $Z$ is the sum of the terms in the Leibniz expansion of
$\Delta_{i,j,k,\ell}$ corresponding to four-cycles (defined in Equation (4)).
For this reason, we define

$\displaystyle\hat{Z}$
$\displaystyle=\hat{\Delta}_{i,j,k,\ell}-\hat{\Delta}_{i,j}\hat{\Delta}_{k,\ell}-\hat{\Delta}_{i,k}\hat{\Delta}_{j,\ell}-\hat{\Delta}_{i,\ell}\hat{\Delta}_{j,k}-\hat{\Delta}_{i}\hat{\Delta}_{j,k,\ell}-\hat{\Delta}_{j}\hat{\Delta}_{i,k,\ell}$
$\displaystyle\quad-\hat{\Delta}_{k}\hat{\Delta}_{i,j,\ell}-\hat{\Delta}_{\ell}\hat{\Delta}_{i,j,k}+2\hat{\Delta}_{i}\hat{\Delta}_{j}\hat{\Delta}_{k,\ell}+2\hat{\Delta}_{i}\hat{\Delta}_{k}\hat{\Delta}_{j,\ell}+2\hat{\Delta}_{i}\hat{\Delta}_{\ell}\hat{\Delta}_{j,k}$
$\displaystyle\quad+2\hat{\Delta}_{j}\hat{\Delta}_{k}\hat{\Delta}_{i,\ell}+2\hat{\Delta}_{j}\hat{\Delta}_{\ell}\hat{\Delta}_{i,k}+2\hat{\Delta}_{k}\hat{\Delta}_{\ell}\hat{\Delta}_{i,j}-6\hat{\Delta}_{i}\hat{\Delta}_{j}\hat{\Delta}_{k}\hat{\Delta}_{\ell}.$

We consider two cases, depending on the number of positive four-cycles in
$G_{K^{\prime}}[\\{i,j,k,\ell\\}]$. If $C$ is the only positive four-cycle in
$G_{K^{\prime}}[\\{i,j,k,\ell\\}]$, then, based on Equation (5), we define

$\displaystyle s_{K^{\prime}}(C)$
$\displaystyle=\epsilon_{i,\ell}\;\text{sgn}(-\hat{Z}).$

If there is more than one positive four-cycle in
$G_{K^{\prime}}[\\{i,j,k,\ell\\}]$, then, based on Equations (6) and (7), we
compute an assignment of values $\phi_{1},\phi_{2},\phi_{3}\in\\{-1,+1\\}$
that minimizes (not necessarily uniquely) the quantity

$\bigg{|}\hat{Z}/2+\phi_{1}\big{|}\hat{K}_{i,j}\hat{K}_{j,k}\hat{K}_{k,\ell}\hat{K}_{\ell,i}\big{|}+\phi_{2}\big{|}\hat{K}_{i,j}\hat{K}_{j,\ell}\hat{K}_{\ell,k}\hat{K}_{k,i}\big{|}+\phi_{3}\big{|}\hat{K}_{i,k}\hat{K}_{k,j}\hat{K}_{j,\ell}\hat{K}_{\ell,i}\big{|}\bigg{|},$

and define $s_{K^{\prime}}(C)=\epsilon_{i,\ell}\;\phi_{1}$ in this case. In
addition, if any other cycle in $G[\\{i,j,k,\ell\\}]$ is in our basis and
$s_{K^{\prime}}(\cdot)$ is not yet defined, we now assign this quantity to be
consistent with $C$ (i.e., to be $\epsilon_{k,\ell}\epsilon_{i,k}\phi_{2}$ for
$i\;j\;\ell\;k\;i$ and $\epsilon_{j,k}\epsilon_{i,\ell}\phi_{3}$ for
$i\;k\;j\;\ell\;i$).

Case III: $|C|>4$.

Let $C=i_{1}\,...\,i_{k}\,i_{1}$, $k>4$, with vertices ordered to match the
ordering of Lemma 3, and define $S=\\{i_{1},...,i_{k}\\}$. Based on Lemma 3,
we define $\hat{Z}$ to equal

$\displaystyle\hat{Z}$
$\displaystyle=\hat{\Delta}_{S}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{S\backslash
i_{1}}-\hat{\Delta}_{i_{k}}\hat{\Delta}_{S\backslash
i_{k}}-\big{[}\hat{\Delta}_{i_{1},i_{k}}-2\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{k}}\big{]}\hat{\Delta}_{S\backslash
i_{1},i_{k}}$
$\displaystyle\quad+2K^{\prime}_{i_{1},i_{k-1}}K^{\prime}_{i_{k-1},i_{k}}K^{\prime}_{i_{k},i_{2}}K^{\prime}_{i_{2},i_{1}}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}$
$\displaystyle\quad-\big{[}\hat{\Delta}_{i_{1},i_{k-1}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{k-1}}\big{]}\big{[}\hat{\Delta}_{i_{2},i_{k}}-\hat{\Delta}_{i_{2}}\hat{\Delta}_{i_{k}}\big{]}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}$
$\displaystyle\quad-\big{[}\hat{\Delta}_{i_{1},i_{2}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{2}}\big{]}\big{[}\hat{\Delta}_{S\backslash
i_{1},i_{2}}-\hat{\Delta}_{i_{k}}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k}}\big{]}$
$\displaystyle\quad-\big{[}\hat{\Delta}_{i_{k-1},i_{k}}-\hat{\Delta}_{i_{k-1}}\hat{\Delta}_{i_{k}}\big{]}\big{[}\hat{\Delta}_{S\backslash
i_{k-1},i_{k}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{S\backslash
i_{1},i_{k-1},i_{k}}\big{]}$
$\displaystyle\quad+\big{[}\hat{\Delta}_{i_{1},i_{2}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{2}}\big{]}\big{[}\hat{\Delta}_{i_{k-1},i_{k}}-\hat{\Delta}_{i_{k-1}}\hat{\Delta}_{i_{k}}\big{]}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}},$

and note that the quantity

$\text{sgn}(K^{\prime}_{i_{1},i_{k-1}}K^{\prime}_{i_{k-1},i_{k}}K^{\prime}_{i_{k},i_{2}}K^{\prime}_{i_{2},i_{1}})$

is, by construction, computable using the signs of three- and four-cycles in
our basis. Based on Lemma 4, we set

$\displaystyle\text{sgn}\bigg{(}2\,(-1)^{k+1}\,K^{\prime}_{i_{k},i_{1}}\prod_{j=1}^{k-1}K^{\prime}_{i_{j},i_{j+1}}\prod_{(a,b)\in
U}\left[1-\frac{\epsilon_{i_{a},i_{a+1}}K^{\prime}_{i_{b-1},i_{a}}K^{\prime}_{i_{a+1},i_{b}}}{K^{\prime}_{i_{a},i_{a+1}}K^{\prime}_{i_{b-1},i_{b}}}\right]\bigg{)}=\text{sgn}(\hat{Z}),$

with the set $U$ defined as in Lemma 4. From this equation, we can compute
$s_{K^{\prime}}(C)$, as the quantity

$\text{sgn}\left[1-\frac{\epsilon_{i_{a},i_{a+1}}K^{\prime}_{i_{b-1},i_{a}}K^{\prime}_{i_{a+1},i_{b}}}{K^{\prime}_{i_{a},i_{a+1}}K^{\prime}_{i_{b-1},i_{b}}}\right]$

is computable using the signs of three- and four-cycles in our basis (see
Section 4 for details). In the case of $|C|>4$, we note that
$s_{K^{\prime}}(C)$ was defined using $O(1)$ principal minors, all
corresponding to subsets of $V(C)$, and previously computed information
regarding three- and four-cycles (which requires no additional querying).

Step 3: Define $K^{\prime}$.

We have already computed $K^{\prime}_{i,i}$, $i\in[N]$, $|K^{\prime}_{i,j}|$,
$i\neq j$, and $s_{K^{\prime}}(C)$ for every cycle in a simple cycle basis.
The procedure for producing this matrix is identical to Step 5 of the RecoverK
algorithm.

###  A.2. A Proof of Theorem 3

In this subsection, we prove the following theorem.

######  Theorem 4 (Restatement of Theorem 3).

Let $K\in\mathcal{K}_{N}(\alpha,\beta,\gamma)$ and
$\\{\hat{\Delta}_{S}\\}_{S\subseteq[N]}$ satisfy
$|\hat{\Delta}_{S}-\Delta_{S}(K)|\leq\delta$ for all $S\subseteq[N]$, for some

$\delta<\alpha\min\\{\alpha^{3\phi_{G}},\beta^{3\phi_{G}/2},\gamma\\}/100,$

where $G$ is the sparsity graph of $(\Delta_{S})_{|S|\leq 2}$. The
RecoverK≈$\big{(}\\{\hat{\Delta}_{S}\\},\,\delta\big{)}$ algorithm outputs a
matrix $K^{\prime}$ satisfying

$\rho(K,K^{\prime})\leq 3\delta/2\alpha.$

This algorithm runs in time polynomial in $N$, and queries at most $O(N^{2})$
principal minors, all of order at most $3\,\phi_{G}$.

The proof of this theorem adds little insight and consists primarily of
verifying that $\delta$ is small enough so that $K$ and $K^{\prime}$ have the
same charged sparsity graph and $s(\cdot)$ agrees for $K$ and $K^{\prime}$ on
all cycles in our basis. The bound that we make repeated use of is that,
because $|\Delta_{S}|,|\hat{\Delta}_{S}|\leq 1$, $S\subseteq[N]$, and
$0<\delta<1$,

(9)
$\big{|}\Delta_{S_{1}}...\Delta_{S_{k}}-\hat{\Delta}_{S_{1}}...\hat{\Delta}_{S_{k}}\big{|}\leq
1-(1-\delta)^{k}\leq k\delta$

for any $S_{1},...,S_{k}\subseteq[N]$, where $k\leq 5$. We begin by computing
element-wise errors. For diagonal entries $K^{\prime}_{i,i}$,

$|K^{\prime}_{i,i}-K_{i,i}|=|\hat{\Delta}_{i}-\Delta_{i}|\leq\delta\quad\text{for
all }i\in[N].$

For off-diagonal entries $K^{\prime}_{i,j}$, $i\neq j$, we note that

$|K_{i,j}K_{j,i}|\geq\alpha^{2}>6\delta\quad\text{for all }i\neq j,$

and so, by Step 1 of the algorithm (see Inequality (8)),
$\text{sgn}(K^{\prime}_{i,j}K^{\prime}_{j,i})=\text{sgn}(K_{i,j}K_{j,i})$ for
all $i\neq j$, and $G_{K}=G_{K^{\prime}}$. In addition, by Inequality (8),

(10)
$\big{|}|K_{i,j}|-|K^{\prime}_{i,j}|\big{|}=\frac{\big{|}|K_{i,j}K_{j,i}|-|K^{\prime}_{i,j}K^{\prime}_{j,i}|\big{|}}{|K_{i,j}|+|K^{\prime}_{i,j}|}\leq\frac{3\delta}{2\alpha}\quad\text{for
all }i\neq j.$

Using Inequality (10), we can produce a version of Inequality (9) for products
of off-diagonal entries, i.e., because
$|K_{i,j}|,|K^{\prime}_{i,j}|\leq\sqrt{2}$ and
$\big{|}|K_{i,j}|-|K^{\prime}_{i,j}|\big{|}\leq 3\delta/2\alpha<\sqrt{2}$,

(11)
$\big{|}|K_{i_{1},j_{1}}...K_{i_{k},j_{k}}|-|K^{\prime}_{i_{1},j_{1}}...K^{\prime}_{i_{k},j_{k}}|\big{|}\leq
2^{k/2}\bigg{(}1-\bigg{[}1-\frac{3\delta}{2\sqrt{2}\alpha}\bigg{]}^{k}\bigg{)}\leq
2^{\tfrac{k-3}{2}}\,\frac{3\,k\,\delta}{\alpha}$

for any $i_{1}\neq j_{1},i_{2}\neq j_{2},...,i_{k}\neq j_{k}$, where $k\leq
5$. To complete the proof, it suffices to verify that $s_{K}(C)$ and
$s_{K^{\prime}}(C)$ agree for all cycles in our basis. Similar to Step 2 of
our algorithm, we will investigate cycles of length three, then four, and then
of length greater than four.

Case I: $|C|=3$.

Let $C=i\,j\,k\,i$, $i<j<k$. Using Condition 2 and Inequality (9), we have
$|K_{i,j}K_{j,k}K_{k,i}|\geq\alpha^{3}$ and

$\displaystyle\big{|}K_{i,j}K_{j,k}K_{k,i}-\big{[}\hat{\Delta}_{i}\hat{\Delta}_{j}\hat{\Delta}_{k}-\big{[}\hat{\Delta}_{i}\hat{\Delta}_{j,k}+\hat{\Delta}_{j}\hat{\Delta}_{i,k}+\hat{\Delta}_{k}\hat{\Delta}_{i,j}\big{]}/2+\hat{\Delta}_{i,j,k}/2\big{]}\big{|}$
$\displaystyle\qquad\qquad\leq\big{|}\Delta_{i}\Delta_{j}\Delta_{k}-\hat{\Delta}_{i}\hat{\Delta}_{j}\hat{\Delta}_{k}\big{|}+\big{|}\Delta_{i}\Delta_{j,k}-\hat{\Delta}_{i}\hat{\Delta}_{j,k}\big{|}/2+\big{|}\Delta_{j}\Delta_{i,k}-\hat{\Delta}_{j}\hat{\Delta}_{i,k}\big{|}/2$
$\displaystyle\qquad\qquad\quad+\big{|}\Delta_{k}\Delta_{i,j}-\hat{\Delta}_{k}\hat{\Delta}_{i,j}\big{|}/2+\big{|}\Delta_{i,j,k}-\hat{\Delta}_{i,j,k}\big{|}/2$
$\displaystyle\qquad\qquad\leq
3\delta+3\times(2\delta)/2+\delta/2<7\delta<\alpha^{3},$

and so $s_{K^{\prime}}(C)=s_{K}(C)$. This completes the case $|C|=3$.

Case II: $|C|=4$.

Now, let $C=i\,j\,k\,\ell\,i$, $i<j<k<\ell$. Using Condition 2 and Inequality
(9), we have $Z\geq 2\gamma$ ($Z$ defined in Equation (4)) and

$\displaystyle\big{|}Z-\hat{Z}\big{|}$
$\displaystyle\leq\big{|}\Delta_{i,j,k,\ell}-\hat{\Delta}_{i,j,k,\ell}\big{|}+\big{|}\Delta_{i,j}\Delta_{k,\ell}-\hat{\Delta}_{i,j}\hat{\Delta}_{k,\ell}\big{|}+\big{|}\Delta_{i,k}\Delta_{j,\ell}-\hat{\Delta}_{i,k}\hat{\Delta}_{j,\ell}\big{|}$
$\displaystyle\quad+\big{|}\Delta_{i,\ell}\Delta_{j,k}-\hat{\Delta}_{i,\ell}\hat{\Delta}_{j,k}\big{|}+\big{|}\Delta_{i}\Delta_{j,k,\ell}-\hat{\Delta}_{i}\hat{\Delta}_{j,k,\ell}\big{|}+\big{|}\Delta_{j}\Delta_{i,k,\ell}-\hat{\Delta}_{j}\hat{\Delta}_{i,k,\ell}\big{|}$
$\displaystyle\quad+\big{|}\Delta_{k}\Delta_{i,j,\ell}-\hat{\Delta}_{k}\hat{\Delta}_{i,j,\ell}\big{|}+\big{|}\Delta_{\ell}\Delta_{i,j,k}-\hat{\Delta}_{\ell}\hat{\Delta}_{i,j,k}\big{|}+2\big{|}\Delta_{i}\Delta_{j}\Delta_{k,\ell}-\hat{\Delta}_{i}\hat{\Delta}_{j}\hat{\Delta}_{k,\ell}\big{|}$
$\displaystyle\quad+2\big{|}\Delta_{i}\Delta_{k}\Delta_{j,\ell}-\hat{\Delta}_{i}\hat{\Delta}_{k}\hat{\Delta}_{j,\ell}\big{|}+2\big{|}\Delta_{i}\Delta_{\ell}\Delta_{j,k}-\hat{\Delta}_{i}\hat{\Delta}_{\ell}\hat{\Delta}_{j,k}\big{|}$
$\displaystyle\quad+2\big{|}\Delta_{j}\Delta_{k}\Delta_{i,\ell}-\hat{\Delta}_{j}\hat{\Delta}_{k}\hat{\Delta}_{i,\ell}\big{|}+2\big{|}\Delta_{j}\Delta_{\ell}\Delta_{i,k}-\hat{\Delta}_{j}\hat{\Delta}_{\ell}\hat{\Delta}_{i,k}\big{|}$
$\displaystyle\quad+2\big{|}\Delta_{k}\Delta_{\ell}\Delta_{i,j}-\hat{\Delta}_{k}\hat{\Delta}_{\ell}\hat{\Delta}_{i,j}\big{|}+6\big{|}\Delta_{i}\Delta_{j}\Delta_{k}\Delta_{\ell}-\hat{\Delta}_{i}\hat{\Delta}_{j}\hat{\Delta}_{k}\hat{\Delta}_{\ell}\big{|}$
$\displaystyle\leq\delta+7\times 2\delta+6\times[2\times 3\delta]+6\times
4\delta=75\delta<2\gamma,$

and so $\text{sgn}(Z)=\text{sgn}(\hat{Z})$. If $C$ is the only positive four
cycle of $G[\\{i,j,k,\ell\\}]$, then $s_{K^{\prime}}(C)=s_{K}(C)$. If
$G[\\{i,j,k,\ell\\}]$ has more than one positive four cycle, then there exists
a unique choice of $\phi_{1},\phi_{2},\phi_{3}$ such that Equation (7) holds,
and any other choice $\phi_{1}^{\prime},\phi_{2}^{\prime},\phi_{3}^{\prime}$
satisfies

$\displaystyle\big{|}\phi_{1}^{\prime}|K_{i,j}K_{j,k}K_{k,\ell}K_{\ell,i}|+\phi_{2}^{\prime}|K_{i,j}K_{j,\ell}K_{\ell,k}K_{k,i}|+\phi_{3}^{\prime}|K_{i,k}K_{k,j}K_{j,\ell}K_{\ell,i}|+Z/2\big{|}$
$\displaystyle\qquad\qquad\geq\min\\{2\alpha^{4},\,2\alpha^{2}\beta,\,2\gamma\\},$

where the lower bound $2\alpha^{4}$ applies when
$(\phi_{1}^{\prime},\phi_{2}^{\prime},\phi_{3}^{\prime})$ and
$(\phi_{1},\phi_{2},\phi_{3})$ disagree in one variable, $2\alpha^{2}\beta$
applies when they disagree in two, and $2\gamma$ applies when they disagree in
three (i.e., are negations of each other). We also must bound the error due to
approximately computed entries $|\hat{K}_{i,j}|$. Using Inequality (11), we
have

$\displaystyle\bigg{|}\phi_{1}|K_{i,j}K_{j,k}K_{k,\ell}K_{\ell,i}|+\phi_{2}|K_{i,j}K_{j,\ell}K_{\ell,k}K_{k,i}|+\phi_{3}|K_{i,k}K_{k,j}K_{j,\ell}K_{\ell,i}|$
$\displaystyle\qquad-\big{[}\phi_{1}|K^{\prime}_{i,j}K^{\prime}_{j,k}K^{\prime}_{k,\ell}K^{\prime}_{\ell,i}|+\phi_{2}|K^{\prime}_{i,j}K^{\prime}_{j,\ell}K^{\prime}_{\ell,k}K^{\prime}_{k,i}|+\phi_{3}|K^{\prime}_{i,k}K^{\prime}_{k,j}K^{\prime}_{j,\ell}K^{\prime}_{\ell,i}|\big{]}\bigg{|}\leq\frac{36\,\sqrt{2}\,\delta}{\alpha}$

for any $\phi_{1},\phi_{2},\phi_{3}\in\\{-1,+1\\}$. We now have two upper
bounds, one for $|Z-\hat{Z}|$ and one for the error in sums of four cycles
between $K$ and $\hat{K}$, and a lower bound for the gap between $Z$ and any
choice of $(\phi_{1},\phi_{2},\phi_{3})$ not equal to $Z$. At this point, we
can now conclude that $s_{K^{\prime}}(C)=s_{K}(C)$, as the lower bound for the
gap is at least twice as large as the sum of the two upper bounds (properly
normalized), i.e.,

$|Z/2-\hat{Z}/2|+\frac{36\,\sqrt{2}\,\delta}{\alpha}\leq\frac{75\,\delta}{2}+\frac{36\,\sqrt{2}\,\delta}{\alpha}<\min\\{\alpha^{4},\,\alpha^{2}\beta,\,\gamma\\}.$

Here we have used the fact that $\phi_{G}\geq 3$ in this case.

Case III: $|C|>4$.

Finally, let $C=i_{1}\,...\,i_{k}\,i_{1}$, $k>4$, with vertices ordered to
match the ordering of Lemma 3, and define $S=\\{i_{1},...,i_{k}\\}$. We note
that we have already shown that $K$ and $K^{\prime}$ agree in sign for three-
and four-cycles. Using Lemma 4 and Condition 2,

$|Z|=2|K_{i_{k},i_{1}}|\prod_{j=1}^{k-1}|K_{i_{j},i_{j+1}}|\prod_{(a,b)\in
U}\bigg{|}\left[1-\frac{\epsilon_{i_{a},i_{a+1}}K_{i_{b-1},i_{a}}K_{i_{a+1},i_{b}}}{K_{i_{a},i_{a+1}}K_{i_{b-1},i_{b}}}\right]\bigg{|}\geq
2\alpha^{k-2|U|}\beta^{|U|}.$

In addition, we can bound the difference between $Z$ and $\hat{Z}$ using a
number of lengthy inequalities. In particular, we have

$\displaystyle\big{|}\Delta_{S}-\hat{\Delta}_{S}\big{|}$
$\displaystyle\leq\delta,$
$\displaystyle\big{|}\Delta_{i_{1}}\Delta_{S\backslash
i_{1}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{S\backslash i_{1}}\big{|}$
$\displaystyle\leq 2\delta,$
$\displaystyle\big{|}\Delta_{i_{k}}\Delta_{S\backslash
i_{k}}-\hat{\Delta}_{i_{k}}\hat{\Delta}_{S\backslash i_{k}}\big{|}$
$\displaystyle\leq 2\delta,$
$\displaystyle\big{|}\big{[}\Delta_{i_{1},i_{k}}-2\Delta_{i_{1}}\Delta_{i_{k}}\big{]}\Delta_{S\backslash
i_{1},i_{k}}-\big{[}\hat{\Delta}_{i_{1},i_{k}}-2\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{k}}\big{]}\hat{\Delta}_{S\backslash
i_{1},i_{k}}\big{|}$
$\displaystyle\qquad\leq\big{|}\Delta_{i_{1},i_{k}}\Delta_{S\backslash
i_{1},i_{k}}-\hat{\Delta}_{i_{1},i_{k}}\hat{\Delta}_{S\backslash
i_{1},i_{k}}\big{|}+2\big{|}\Delta_{i_{1}}\Delta_{i_{k}}\Delta_{S\backslash
i_{1},i_{k}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{k}}\hat{\Delta}_{S\backslash
i_{1},i_{k}}\big{|}\leq 8\delta,$ $\displaystyle
2\big{|}K_{i_{1},i_{k-1}}K_{i_{k-1},i_{k}}K_{i_{k},i_{2}}K_{i_{2},i_{1}}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}-K^{\prime}_{i_{1},i_{k-1}}K^{\prime}_{i_{k-1},i_{k}}K^{\prime}_{i_{k},i_{2}}K^{\prime}_{i_{2},i_{1}}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}\big{|}$ $\displaystyle\qquad\leq
2\big{|}K_{i_{1},i_{k-1}}K_{i_{k-1},i_{k}}K_{i_{k},i_{2}}K_{i_{2},i_{1}}-K^{\prime}_{i_{1},i_{k-1}}K^{\prime}_{i_{k-1},i_{k}}K^{\prime}_{i_{k},i_{2}}K^{\prime}_{i_{2},i_{1}}\big{|}\big{|}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}\big{|}$
$\displaystyle\qquad\quad+2\big{|}K^{\prime}_{i_{1},i_{k-1}}K^{\prime}_{i_{k-1},i_{k}}K^{\prime}_{i_{k},i_{2}}K^{\prime}_{i_{2},i_{1}}\big{|}\big{|}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}-\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}\big{|}$ $\displaystyle\qquad\leq
24\sqrt{2}\delta/\alpha+8\delta,$
$\displaystyle\big{|}\big{[}\Delta_{i_{1},i_{k-1}}-\Delta_{i_{1}}\Delta_{i_{k-1}}\big{]}\big{[}\Delta_{i_{2},i_{k}}-\Delta_{i_{2}}\Delta_{i_{k}}\big{]}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}$
$\displaystyle\quad-\big{[}\hat{\Delta}_{i_{1},i_{k-1}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{k-1}}\big{]}\big{[}\hat{\Delta}_{i_{2},i_{k}}-\hat{\Delta}_{i_{2}}\hat{\Delta}_{i_{k}}\big{]}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}\big{|}$
$\displaystyle\qquad\leq\big{|}\Delta_{i_{1},i_{k-1}}\Delta_{i_{2},i_{k}}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}-\hat{\Delta}_{i_{1},i_{k-1}}\hat{\Delta}_{i_{2},i_{k}}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}\big{|}$
$\displaystyle\qquad\quad+\big{|}\Delta_{i_{1},i_{k-1}}\Delta_{i_{2}}\Delta_{i_{k}}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}-\hat{\Delta}_{i_{1},i_{k-1}}\hat{\Delta}_{i_{2}}\hat{\Delta}_{i_{k}}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}\big{|}$
$\displaystyle\qquad\quad+\big{|}\Delta_{i_{1}}\Delta_{i_{k-1}}\Delta_{i_{2},i_{k}}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{k-1}}\hat{\Delta}_{i_{2},i_{k}}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}\big{|}$
$\displaystyle\qquad\quad+\big{|}\Delta_{i_{1}}\Delta_{i_{k-1}}\Delta_{i_{2}}\Delta_{i_{k}}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{k-1}}\hat{\Delta}_{i_{2}}\hat{\Delta}_{i_{k}}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}\big{|}$ $\displaystyle\qquad\leq 16\delta,$

$\displaystyle\big{|}\big{[}\Delta_{i_{1},i_{2}}-\Delta_{i_{1}}\Delta_{i_{2}}\big{]}\big{[}\Delta_{S\backslash
i_{1},i_{2}}-\Delta_{i_{k}}\Delta_{S\backslash
i_{1},i_{2},i_{k}}\big{]}-\big{[}\hat{\Delta}_{i_{1},i_{2}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{2}}\big{]}\big{[}\hat{\Delta}_{S\backslash
i_{1},i_{2}}-\hat{\Delta}_{i_{k}}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k}}\big{]}\big{|}$
$\displaystyle\qquad\leq\big{|}\Delta_{i_{1},i_{2}}\Delta_{S\backslash
i_{1},i_{2}}-\hat{\Delta}_{i_{1},i_{2}}\hat{\Delta}_{S\backslash
i_{1},i_{2}}\big{|}+\big{|}\Delta_{i_{1},i_{2}}\Delta_{i_{k}}\Delta_{S\backslash
i_{1},i_{2},i_{k}}-\hat{\Delta}_{i_{1},i_{2}}\hat{\Delta}_{i_{k}}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k}}\big{|}$
$\displaystyle\qquad\quad+\big{|}\Delta_{i_{1}}\Delta_{i_{2}}\Delta_{S\backslash
i_{1},i_{2}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{2}}\hat{\Delta}_{S\backslash
i_{1},i_{2}}\big{|}+\big{|}\Delta_{i_{1}}\Delta_{i_{2}}\Delta_{i_{k}}\Delta_{S\backslash
i_{1},i_{2},i_{k}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{2}}\hat{\Delta}_{i_{k}}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k}}\big{|}$ $\displaystyle\qquad\leq 12\delta,$

and, similarly,

$\displaystyle\big{|}\big{[}\Delta_{i_{k-1},i_{k}}-\Delta_{i_{k-1}}\Delta_{i_{k}}\big{]}\big{[}\Delta_{S\backslash
i_{k-1},i_{k}}-\Delta_{i_{1}}\Delta_{S\backslash i_{1},i_{k-1},i_{k}}\big{]}$
$\displaystyle\quad-\big{[}\hat{\Delta}_{i_{k-1},i_{k}}-\hat{\Delta}_{i_{k-1}}\hat{\Delta}_{i_{k}}\big{]}\big{[}\hat{\Delta}_{S\backslash
i_{k-1},i_{k}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{S\backslash
i_{1},i_{k-1},i_{k}}\big{]}\big{|}\leq 12\delta,$

and

$\displaystyle\big{|}\big{[}\Delta_{i_{1},i_{2}}-\Delta_{i_{1}}\Delta_{i_{2}}\big{]}\big{[}\Delta_{i_{k-1},i_{k}}-\Delta_{i_{k-1}}\Delta_{i_{k}}\big{]}\Delta_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}$
$\displaystyle\quad-\big{[}\hat{\Delta}_{i_{1},i_{2}}-\hat{\Delta}_{i_{1}}\hat{\Delta}_{i_{2}}\big{]}\big{[}\hat{\Delta}_{i_{k-1},i_{k}}-\hat{\Delta}_{i_{k-1}}\hat{\Delta}_{i_{k}}\big{]}\hat{\Delta}_{S\backslash
i_{1},i_{2},i_{k-1},i_{k}}\big{|}\leq 16\delta.$

Summing all of the above estimates, we have

$\big{|}Z-\hat{Z}\big{|}\leq
77\delta+24\sqrt{2}\delta/\alpha<2\alpha^{k-2|U|}\beta^{|U|},$

and so $Z$ and $\hat{Z}$ agree in sign. In addition, by Condition 2,

$\big{|}K_{i_{a},i_{a+1}}K_{i_{b-1},i_{b}}-\epsilon_{i_{a},i_{a+1}}K_{i_{b-1},i_{a}}K_{i_{a+1},i_{b}}\big{|}\geq\beta,$

and, by Inequality (11),

$\big{|}\big{[}K_{i_{a},i_{a+1}}K_{i_{b-1},i_{b}}-\epsilon_{i_{a},i_{a+1}}K_{i_{b-1},i_{a}}K_{i_{a+1},i_{b}}\big{]}-\big{[}K^{\prime}_{i_{a},i_{a+1}}K^{\prime}_{i_{b-1},i_{b}}-\epsilon_{i_{a},i_{a+1}}K^{\prime}_{i_{b-1},i_{a}}K^{\prime}_{i_{a+1},i_{b}}\big{]}\big{|}\leq
6\sqrt{2}\delta/\alpha$

for all $(a,b)\in U$, and so

$\text{sgn}\big{(}K_{i_{a},i_{a+1}}K_{i_{b-1},i_{b}}-\epsilon_{i_{a},i_{a+1}}K_{i_{b-1},i_{a}}K_{i_{a+1},i_{b}}\big{)}=\text{sgn}\big{(}K^{\prime}_{i_{a},i_{a+1}}K^{\prime}_{i_{b-1},i_{b}}-\epsilon_{i_{a},i_{a+1}}K^{\prime}_{i_{b-1},i_{a}}K^{\prime}_{i_{a+1},i_{b}}\big{)}.$

Therefore, $s_{K^{\prime}}(C)=s_{K}(C)$. This completes the analysis of the
final case, and implies that $\rho(K,K^{\prime})$ is given by
$\max_{i,j}\big{|}|K_{i,j}|-|K^{\prime}_{i,j}|\big{|}\leq 3\delta/(2\alpha)$.