# Matroids of Gain Signed Graphs

Laura Anderson, Ting Su, and Thomas Zaslavsky  Department of Mathematics
Binghamton University
Binghamton, New York, U.S.A. 13902-6000  Present affiliation of Ting Su:
Changjiang Geophysical Exploration and Testing Co., China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

A signed graph has edge signs. A gain graph has oriented edge gains drawn from
a group. We define the combination of the two for the abelian case, in which
each oriented edge of a signed graph has a gain from an abelian group,
concentrating on the case of the additive group of a field. We develop the
elementary graph properties, the associated matroid, and the vector and
hyperplanar representations.

###### Key words and phrases:

abelian gain signed graph, matroid, affinographic hyperplane arrangement, edge
polytope, adjacency polytope, arc polytope

###### 2010 Mathematics Subject Classification:

Primary 05C22; Secondary 05B35, 52C35.

###### Contents

  1. 1 Introduction
  2. 2 Technical introduction
    1. 2.1 Graphs
    2. 2.2 Signed graphs
    3. 2.3 Orientation
    4. 2.4 Gains
      1. 2.4.1 The gain function
      2. 2.4.2 Walk gains
      3. 2.4.3 Sign-cycle gains
      4. 2.4.4 Gain switching
    5. 2.5 The extra point
  3. 3 The vector model
  4. 4 Matroid: rank
  5. 5 Matroid: closure and flats
  6. 6 Matroid: coatoms and cocircuits
  7. 7 Matroid: independence and bases
  8. 8 Matroid: circuits
  9. 9 Minors
  10. 10 The hyperplane model
    1. 10.1 Affine hyperplanes
    2. 10.2 Projective hyperplanes
    3. 10.3 Regions and polynomials
  11. 11 Abstract abelian gains

##  1\. Introduction

An _arrangement of hyperplanes_ is a finite set of hyperplanes in some linear,
affine, or projective space. Hyperplane arrangements formed a rather obscure
corner of mathematics as recently as Grünbaum’s famous book of 1967 [9], in
which they were the subject of a chapter, but subsequently they have expanded
into many parts of combinatorics, combinatorial geometry, algebraic geometry,
algebra, and even analysis. A fundamental combinatorial object associated to
an arrangement is its intersection semilattice, which consists of all
intersections of subarrangements (excluding empty sets in the affine case).
Valuable information about the arrangement can be extracted from this
semilattice; in particular, through the characteristic polynomial of the
semilattice one obtains the number of regions in the complement of a real
arrangement [21] and the cohomology of the complement of a complex arrangement
[12].

Certain special arrangements were long well known, and have been a basis for
this expansion: the hyperplane arrangements $A_{n-1}^{*}$,
$B_{n}^{*}=C_{n}^{*}$, and $D_{n}^{*}$ dual to the classical root systems.
Greene observed that subarrangements of the first of these correspond to
graphs and their matroids. The hyperplanes have equations of the form
$x_{j}=x_{i}$, and such a hyperplane corresponds to an edge $v_{i}v_{j}$ in
the associated graph [8]. We call such a hyperplane _graphic_. Zaslavsky
extended this notion to subarrangements of $B_{n}^{*}=C_{n}^{*}$ and
$D_{n}^{*}$, developing a matroid and coloring theory of signed graphs—graphs
in which each edge is signed positive or negative [22]—that facilitates the
calculation of the characteristic polynomial of the arrangement [23]. Here
hyperplanes have equations of the forms $x_{j}=\pm x_{i}$ and $x_{i}=0$,
corresponding to signed edges.

As time passed new particular arrangements attracted interest. The Catalan
arrangement (arising from combinatorial geometry) has hyperplanes of the form
$x_{j}-x_{i}=0,\pm 1$ for $i<j$; the Shi arrangement (arising from algebraic
geometry) has hyperplanes of the form $x_{j}-x_{i}=0,1$ and the Linial
arrangement has hyperplanes $x_{j}-x_{i}=1$, both also for $i<j$. These
examples led to the idea of a _deformation_ of a root system arrangement: the
hyperplanes may be translated (in multiple ways); for instance, the Catalan,
Shi, and Linial arrangements are deformations of the $A_{n-1}^{*}$
arrangement. (We call arrangements of hyperplanes of the form $x_{j}-x_{i}=c$
_affinographic_ since they are affine deformations of graphic arrangements.)
The same idea extends to the other classical root system arrangements, with
hyperplanes of the form $x_{j}\pm x_{i}=c$, and there are variations such as
the threshold arrangement with hyperplanes $x_{j}+x_{i}=1$.

To extract such valuable information as mentioned above one has to calculate
the characteristic polynomial. This can be hard. Athanasiadis in a major paper
[2] did that for many examples by using what he called the “finite field
method”. Given an integral deformation of a rational linear arrangement, one
treats it as an arrangement over a finite field of sufficiently large
order—though in practice only prime fields are used. This retains the
intersection semilattice and enables one to compute the characteristic
polynomial by a counting process. Since there are infinitely many large
primes, with sufficient ingenuity one obtains the polynomial for infinitely
many prime arguments, thus determining it.

Meanwhile, Zaslavsky had generalized signed graphs, coloring, their hyperplane
representations by subarrangements of $B_{n}^{*}$, and their matroids, to gain
graphs [25, 26, 27]. In a gain graph, the edges of the graph are labelled by
the elements of a group, invertibly, which means the group element depends on
direction, being inverted when the direction is reversed. Signed graphs are
the case where the group has order 2. A gain graph has a natural matroid, in
fact, two of them, called the frame and lift matroids. Zaslavsky noticed that
the integral affinographic arrangements studied by Athanasiadis—that is,
arrangements with equations $x_{j}-x_{i}=c$ with $c\in\mathbb{Z}$—are
hyperplanar representations of gain graphs with gain group $\mathbb{Z}^{+}$,
the additive integers, and the lattice structure of the arrangement is given
by the lift matroid of the gain graph [28, 4]. Athanasiadis’ finite field
method, which in practice uses only prime fields, is really a modular coloring
method, in which the gain group is the cyclic group $\mathbb{Z}_{m}$ for all
sufficiently large moduli $m$; having a finite group enables the necessary
counting process by way of coloring using color set $\mathbb{Z}_{m}$ [4]. This
simplifies the theory for all integral affinographic arrangements as there is
no need for $m$ to be prime; it also strengthens the conclusions since it is
possible, at least in principle, to determine all valid moduli $m$ by knowing
the gain graph. (These improvements do not reduce the need for ingenuity.)
However, it leaves out Athanasiadis’ examples with hyperplanes of the form
$x_{j}+x_{i}=c$ in [2, Theorems 3.10 _et seq._ and 5.4–5.5], because those
hyperplanes cannot be treated with gain graphs. (We call such arrangements
_signed affinographic_ because they are affine deformations of arrangements
that represent signed graphs.) The problem is that, while $x_{j}-x_{i}=c$
corresponds to an ordinary or positive edge with gain $c$, $x_{j}+x_{i}=c$
corresponds to a negative edge with gain $c$. Neither signed nor gain graphs
alone can handle this; it calls for a combination. How to produce the
necessary combination remained an unsolved problem for some decades.

That is the problem we solve here. However, the immediate inspiration was
different. Ohsugi and Hibi were led by an algebraic question to study the edge
polytope of a graph [11]. This is the convex hull of vectors
$\mathbf{b}_{i}+\mathbf{b}_{j}$, one for each edge $v_{i}v_{j}$ in the graph.
Part of their work involved finding the affine span of a set of such vectors
[11, Proposition 1.3]. It was clear, from the viewpoint of signed graphs, that
the affine span is a signed-graphic property; but what, exactly, is that
property? We quickly realized that it requires a combination of signs and
identically-$1$ gains on the edges of the graph. This gave us the necessary
hint, and from that we produced a successful definition of a gain signed graph
and (the proof of success) a succession of theorems under the assumption that
we have an abelian gain group, such as the additive group of a field. This
paper reports our results. As a demonstration we prove Ohsugi and Hibi’s
proposition in our new way in Example 3.6 and generalize it to bidirected
graphs.

_Terminological note._ Gain signed graphs are not the same as signed gain
graphs. The inverse order of modifiers corresponds grammatically to the order
of structures. A signed gain graph is a gain graph with added signs; the gain-
graph structure does not involve the signs, though the sign structure might
depend on the gains. We believe that trying to define signed gain graphs has
previously been the barrier to a successful combination of signs and gains. It
is the realization that the signs influence the gain structure, so one needs
gains superimposed on a signed graph, that enabled us to succeed.

##  2\. Technical introduction

The object of study is a _gain signed graph_ , which is a triple
$\Upsilon=(\Gamma,\sigma,\varphi)$ where $\Gamma=(V,E)$ is a graph, the
_signature_ or sign function $\sigma$ gives each edge an element of the sign
set $\\{+1,-1\\}$, and the _gain function_ $\varphi$ is an oriented labelling
of edges from a group; that is, inverting the edge inverts the gain. The group
will be the additive group of a field $\mathbf{K}$ until at the end we
retroactively generalize in Section 11. All these terms must be explained
further.

We assume acquaintance with the basics of matroid theory, such as in the
beginning of Oxley [13]. As there are inconsistencies amongst common usage in
graph theory, usage in matroid theory, and our special needs, we summarize
some of our vocabulary here. The definitions will follow in this section.

  1. _Graph_ : it may have links, loops, and half and loose edges, as well as multiple edges. We write $n:=|V|$.

  2. _Circle_ : a connected, 2-regular subgraph or its edge set.

  3. _Circuit_ : a matroid circuit.

  4. _Sign circuit_ : a circuit of the frame matroid $\mathbf{F}(\Gamma,\sigma)$. Similarly for cocircuits.

  5. _Sign cycle_ : a sign circuit oriented to have no source or sink.

  6. $\mathbf{F}(\Sigma)$: the frame matroid of a signed graph $\Sigma$.

  7. A sign circuit is _neutral_ in $\Upsilon$ if it has gain 0.

  8. $\mathbf{M}(\Upsilon)$: the matroid of the gain signed graph $\Upsilon$.

  9. $\mathbf{M}_{\infty}(\Upsilon)$: the extended matroid of $\Upsilon$, with extra element $e_{\infty}$.

  10. _Hypercircuit, hypercocircuit_ : a circuit or cocircuit of the matroid $\mathbf{M}(\Upsilon)$ or $\mathbf{M}_{\infty}(\Upsilon)$, as appropriate.

  11. $\operatorname{Lat}M$: the geometric lattice of a matroid $M$.

###  2.1. Graphs

The graph $\Gamma$ always means $(V,E)$ whose vertex set is
$V=V(\Gamma)=\\{v_{1},v_{2},\ldots,v_{n}\\}$, with $n:=|V|$. Our notion of a
graph is unusual because we allow four kinds of edge: links, loops, half
edges, and loose edges. Multiple edges are allowed. A link or loop has two
_ends_ , each of which is incident with one vertex, called an endpoint of the
edge. (Note that an endpoint is a vertex while an end is part of an edge.) The
edge is a link if these two end vertices are distinct and a loop if they
coincide. A half edge has one end, which is incident with one vertex, and a
loose edge has no ends. In notation we often write $e_{vw}$ or $e_{ij}$ to
indicate the endpoints of a link or loop $e$, $e_{v}$ or $e_{i}$ for a half
edge $e$, and $e_{\varnothing}$ for a loose edge (although this notation does
not distinguish parallel edges, which have the same endpoints). We write
$E^{2}$ for the set of links and loops, $E^{0}$ for that of loose edges, and
$E^{1}$ for that of half edges. For an end of edge $e$ incident with a vertex
$v$ we write $(v,e)$; this notation is technically ambiguous for a loop but
that will rarely cause difficulty. We write $\operatorname{Ends}(\Gamma)$ for
the set of edge ends of $\Gamma$.

A _simple graph_ is a graph that has only links and has no parallel edges.

The _components_ of $\Gamma$ are the usual connected components, not including
loose edges. More precisely, they are the _vertex components_ of $\Gamma$. The
_edge components_ are each loose edge and the vertex components that are not
isolated vertices.

A _circle_ is a connected 2-regular graph, or its edge set (widely known as a
“cycle” or “circuit”, but we have different uses for those names). A
_unicycle_ is a circle or half edge that may have trees attached. A _handcuff_
is a pair of circles with at most one common vertex together with a minimal
connecting path (of length 0 if there is a common vertex).

A _cut_ is a non-empty set that consists of all edges between a subset of $V$
and its complement. A minimal cut is a _bond_. The two components of the bond-
deleted graph that are joined by the bond are its _sides_.

The edge set induced by $X\subseteq V$ is denoted by $E{:}X$; the induced
subgraph is denoted by $\Gamma{:}X$. Suppose $\pi$ is a partition or partial
partition of $V$ (that is, a partition of a subset); then the partition-
induced subgraph is denoted by
$\Gamma{:}\pi=(\bigcup\pi,E{:}\pi):=\bigcup_{B\in\pi}\Gamma{:}B$.

The _restriction_ of $\Gamma$ to an edge set $S$ is the spanning subgraph
$\Gamma|S:=(V,S)$. The partition of $V$ induced by the components of $\Gamma$
is $\pi(\Gamma)$; for an edge set $S\subseteq E$ the induced partition of $V$
is $\pi(S):=\pi(\Gamma|S)=\pi(V,S)$. The number of components of $\Gamma$ is
$c(\Gamma)=|\pi(\Gamma)|$. The set of vertices of edges of $S$ is $V(S)$, and
$c(S)$ is the number of components of the spanning subgraph $\Gamma|S$. The
_cyclomatic number_ of $S$ is

$\xi(S)=|S|-|V|+c(S)=|S|-|V(\Gamma|S)|+c(\Gamma|S).$

It is the number of edges that must be deleted in order to eliminate all
circuits of the graphic matroid; this includes loose edges.

For a walk, say $W=u_{0}e_{1}u_{1}e_{2}\cdots e_{l}u_{l}$ (where the length
$l\geq 0$), we write $W_{ij}$ to denote that part of $W$ beginning at $u_{i}$
and ending at $u_{j}$. The _reverse_ of that partial walk is
$W_{ji}=W_{ij}^{-1}$. In particular, $W=W_{0l}$ and $W^{-1}=W_{l0}$. The
direction of a walk $W$ is indicated by the ordered pair of initial and final
vertices; note that this concept of direction is not the one common in
directed graph theory and is different from the concept of orientation in
Section 2.3.

For sign circuits (to be defined shortly) we sometimes need an extension of
the notion of walk. An _ultrawalk_ is like a walk except that it may begin or
end with a half edge. For example, $W=e_{0}u_{0}e_{1}u_{1}e_{2}\cdots
e_{l}u_{l}$ is an ultrawalk if $e_{0}$ is a half edge incident with $u_{0}$.

###  2.2. Signed graphs

A _signed graph_ $\Sigma=(\Gamma,\sigma)$ consists of a graph $\Gamma$ and a
function $\sigma:E\to\\{+1,-1\\}$, the _signature_ or _sign function_ , that
is defined on all edges (this differs from the convention in previous articles
such as [22]). Links and loops may be positive or negative. Half edges must be
negative and loose edges must be positive. The set of edges with sign
$\varepsilon$ is $E^{\varepsilon}$. A simple graph $\Gamma$ gives rise to a
signed graph in several ways: we may give all edges the same sign
$\varepsilon$ and we write that signed graph $\varepsilon\Gamma$, or we may
double the edges with both signs, which is the graph
$\pm\Gamma=(+\Gamma)\cup(-\Gamma)$, which is the union of two edge-disjoint
signed graphs on the same vertex set $V=V(\Gamma)$.

We apply most graph notations to signed graphs; e.g., the restriction of a
signed graph is $\Sigma|S:=(\Gamma|S,\sigma|_{S})$, more simply
$(\Gamma|S,\sigma)$.

The sign of an edge set $S$ is $\sigma(S):=$ the product of the signs of edges
in $S$. This is important for a circle $C$, which is either positive or
negative. If an edge set $S\subseteq E$ contains no negative circles and no
half edges, it is _sign balanced_ , and similarly for a subgraph. We write
$b_{\Sigma}(S)$ for the number of connected components of $S$, or more
precisely of $\Sigma|S$, that are sign balanced.

A signed graph $\Sigma$ is _sign antibalanced_ if its negative, $-\Sigma$, is
balanced.

The sign of a walk, say $W=u_{0}e_{1}u_{1}e_{2}\cdots e_{l}u_{l}$, is
$\sigma(W):=\prod_{i=1}^{l}\sigma(e_{i})$. Note that the sign of a walk is not
necessarily the same as the sign of its edge set since the walk may repeat
edges; but the two definitions do agree for a circle. The same definition
gives the sign of an ultrawalk: it is the product of the signs of its edges,
accounting for multiplicity (recall that half edges are negative).

The _frame matroid_ $\mathbf{F}(\Sigma)$ ([22, 26]; called the bias matroid in
[26]) is a matroid whose ground set is $E$ and whose circuits are the sign
circuits of $\Sigma$. To define a sign circuit, first we define a _negative
figure_ : it is any negative circle or half edge. A _sign circuit_ is an edge
set that is either a positive circle, or a loose edge, or a pair of negative
figures that have exactly one common vertex (a _tight handcuff_), or a pair of
disjoint negative figures together with a minimal connecting path (a _loose
handcuff_)—minimal in the sense that it intersects the two circles only at its
endpoints; the length is immaterial. (We view a tight handcuff as having a
connecting path of length $0$.) In this definition any negative circle can be
replaced by a half edge; thus we call a _negative figure_ any negative circle
or half edge. The frame matroid’s rank function is
$\operatorname{rk}_{\Sigma}(S)=n-b_{\Sigma}(S)$.

Figure 2.1. The two different varieties of sign circuit. In the first row,
sign balanced, showing a positive circle and a (positive) loose edge. In the
second row, sign unbalanced, showing a handcuff with two negative circles, one
such circle and one (negative) half edge, and two half edges; the connecting
path may have length $0$.

A fundamental operation on signed graphs is _switching_ (which we call _sign
switching_ in the context of gain signed graphs). A _switching function_ ,
briefly _switcher_ , is any vertex function $\zeta:V\to\\{\pm 1\\}$. Switching
$\Sigma$ by $\zeta$ means changing the signs of links and loops:
$\Sigma=(\Gamma,\sigma)$ becomes $\Sigma^{\zeta}=(\Gamma,\sigma^{\zeta})$
whose sign function is $\sigma^{\zeta}(e_{vw}):=\zeta(v)\sigma(e)\zeta(w)$.
The signs of loose and half edges do not change. Switching does not change the
signs of closed walks and, most importantly, of circles. A signed graph is
balanced or antibalanced if and only if it can be sign switched to all
positive or all negative [22].

A switcher can also be regarded as a way of signing edges. We call $\zeta$ a
_sign potential_ for an edge set $S$ if $\sigma(e_{vw})=\zeta(v)^{-1}\zeta(w)$
for every edge in $S$. (The inversion exists to suit the common notion of a
potential, although for signs it is unnecessary.) For a subset $S\subseteq
E^{2}$ this is equivalent to $\sigma^{\zeta}|_{S}$ being identically $+1$.

######  Lemma 2.1 ([22]).

A signed graph is balanced if and only if it switches to all positive.

Note that, by our sign conventions, being all positive implies having no half
edges.

There are two basic ways to make a signed graph $\Sigma$ balanced. One can
delete some edge set $D$ whose complement is balanced—then $D$ is called a
_deletion set_ for $\Sigma$; or one can negate the signs of some edge set $N$
to obtain balance—then $N$ is called a _negation set_. Every negation set is
obviously a deletion set, but not every deletion set is a negation set.
However, the minimal deletion and negation sets are the same. A simple
property of a minimal deletion (or negation) set is this:

######  Lemma 2.2.

Let $\Sigma$ be a connected signed graph. The minimal deletion sets in
$\Sigma$ are the complements of the maximal balanced edge sets. The complement
of a minimal deletion set in $\Sigma$ is connected.

For $S\subseteq E$ define the _sign balance-closure_ :111Not “balanced
closure”; it might be neither balanced nor a closure.

$\operatorname{bcl}_{\Sigma}(S):=S\cup\\{e\notin S:\exists\ \text{positive
circle }C\text{ such that }e\in C\subseteq S\cup\\{e\\}\\}\cup E^{0}.$

We also define the partial partition of $V$ due to $S$,

$\pi_{\text{\rm b}}(S)=\\{V(B):B\text{ is a sign-balanced component of
}\Sigma|S\\},$

whose parts are the vertex sets of sign-balanced components of $\Sigma|S$;

$U_{\Sigma}(S):=V\smallsetminus\bigcup\pi_{\text{\rm b}}(S),$

the set of vertices of sign-unbalanced components of $S$; and for a signature
$\zeta:\bigcup\pi_{\text{\rm b}}(S)\to\\{\pm 1\\}$, the set

$E(\zeta):=\\{e_{vw}\in
E^{2}{:}U_{\Sigma}(S)^{c}:\sigma(e_{vw})=\zeta(v)\zeta(w)\\},$

i.e., the edges for which $\zeta$ is a sign potential. With these notions we
can define the frame matroid $\mathbf{F}(\Sigma)$.

######  Theorem 2.3 (Frame Matroid of a Signed Graph [22, Theorem 5.1]).

In the frame matroid of a signed graph $\Sigma$, consider an edge set $S$.

The rank function is

$\operatorname{rk}_{\Sigma}(S)=n-b_{\Sigma}(S)=|V(S)|-b_{\Sigma}(V(S),S).$

The sign balance-closure of a balanced edge set is given by
$\operatorname{bcl}_{\Sigma}(S)=E(\zeta){:}\pi_{\text{\rm b}}(S)\cup E^{0}$,
where $\zeta$ switches $S$ to all positive. The closure of any edge set is
given by

$\operatorname{clos}_{\Sigma}(S)=[E{:}U_{\Sigma}(S)]\cup\operatorname{bcl}_{\Sigma}(S{:}U_{\Sigma}(S)^{c})=[E{:}U_{\Sigma}(S)]\cup[E(\zeta){:}\pi_{\text{\rm
b}}(S)]\cup E^{0}.$

The closed sets are those of the form

$[E{:}U]\cup[E(\zeta){:}\pi]\cup E^{0},$

where $U\subseteq V$, $\pi$ partitions $U^{c}$, and $\zeta:U^{c}\to\\{\pm
1\\}$.

The cocircuits $D$ are any of the following four types:

  1. (D1)

$D$ is a bond in a balanced component of $\Sigma$.

  2. (D2)

$D$ is a minimal deletion set of an unbalanced component of $\Sigma$.

  3. (D3)

$D$ is a cut in an unbalanced component of $\Sigma$, such that one side is
connected and balanced and the other has no balanced component.

  4. (D4)

$D$ consists of a cut in an unbalanced component of $\Sigma$, such that both
sides are unbalanced, one side is connected and unbalanced, and the other side
has no balanced component, together with a minimal deletion set of the first
side.

Note that (D4) incorporates (D3) if we allow the deletion set in (D4) to be
empty. However, for practical use it seems better to state (D3) separately.

A vector representation of a signed graph is
$\mathbf{x}:E(\Sigma)\to\mathbf{K}^{n}$ defined by

$\displaystyle\mathbf{x}(e_{ij})$
$\displaystyle:=\mathbf{b}_{j}-\sigma(e)\mathbf{b}_{i},$
$\displaystyle\mathbf{x}(e_{i})$ $\displaystyle:=\mathbf{b}_{i},$
$\displaystyle\mathbf{x}(e_{\varnothing})$ $\displaystyle:=\mathbf{0}.$

(A negative loop $e_{ii}$ is represented by $\pm 2\mathbf{b}_{i}$. Recall that
we assume the field $\mathbf{K}$ has characteristic other than 2.)

######  Theorem 2.4 (Representation of Signed Graphs [22, Section 8B]).

The mapping $\mathbf{x}$ is a vector representation of the frame matroid
$\mathbf{F}(\Sigma)$.

###  2.3. Orientation

A signed graph, that is $\Sigma=(\Gamma,\sigma)$, is oriented differently from
an ordinary, unsigned graph. An _orientation_ of $\Sigma$ is a mapping from
edge ends to signs, say $\tau:\operatorname{Ends}\to\\{+1,-1\\}$, such that
for a link or loop $e_{vw}$, $\tau(v,e)\tau(w,e)=-\sigma(e_{vw})$. In diagrams
we interpret an end sign $+1$ as an arrow pointing into the endpoint and sign
$-1$ as an arrow pointing from the endpoint into the edge. With this sign rule
an oriented positive edge is an ordinary directed edge. An oriented negative
edge, on the contrary, does not have a direction; it is either _introverted_ ,
with both ends negative, or _extraverted_ , with both ends positive. A half
edge also has an orientation (at its single end); it is introverted if its end
is negative and extraverted if it is positive. A loose edge has no orientation
(as it has no end). To denote an oriented signed graph and its orientation we
write $\Sigma_{\tau}$. When we do not wish to specify a particular orientation
of an edge we write $e$ for one orientation and $e^{-1}$ for the opposite
orientation.

Figure 2.2. Oriented edges. Top: positive edges with $\tau=+-,\ -+,\ -+$.
Middle: negative edges with $\tau=++,\ --,\ +,\ -$. Bottom: negative loops
with $\tau=++,\ --$.

Orientations switch: if we switch $\Sigma$ by $\zeta$, an orientation $\tau$
becomes $\tau^{\zeta}$ defined by $\tau^{\zeta}(v,e)=\zeta(v)\tau(v,e)$.
Switching of an orientation applies to all edges (and is trivial for loose
edges).

A walk in an oriented signed graph, say $W=u_{0}e_{1}u_{1}e_{2}\cdots
e_{l}u_{l}$, is _coherent_ if the arrows line up at each vertex, that is,
$\tau(u_{i},e_{i})=-\tau(u_{i},e_{i+1})$ for each $i=1,2,\ldots,l-1$. (In any
walk, each intermediate vertex $u_{i}$ is either coherent, if
$\tau(u_{i},e_{i})=-\tau(u_{i},e_{i+1})$, or incoherent. Coherence of a vertex
in a walk is not altered by switching.) The same definition applies to any
ultrawalk if among the intermediate vertices we include any vertex supporting
a half edge. A _closed walk_ , in which $u_{l}=u_{0}$, is _coherent_ if it is
coherently oriented as an open walk and in addition it closes coherently,
i.e., $\tau(u_{l},e_{l})=-\tau(u_{0},e_{1})$; this implies that
$\sigma(W)=+1$. A closed walk is _rooted coherent_ if it is coherent as an
open walk but not as a closed walk; this implies that $\sigma(W)=-1$; the
_root_ is $u_{0}$. To prove those sign statements, we show that a positive
closed walk, however oriented, has an even number of incoherent vertices,
while a negative circle has an odd number. The proof is a simple calculation
(with subscripts modulo $l$):

$\displaystyle\sigma(C)$
$\displaystyle=\prod_{i=1}^{l}\sigma(e_{i})=\prod_{i=1}^{l}[-\tau(u_{i-1},e_{i})\tau(u_{i},e_{i})]$
$\displaystyle=\prod_{i=1}^{l}[-\tau(u_{i},e_{i})\tau(u_{i},e_{i+1})]=\prod_{i=1}^{l}\iota(u_{i}),$

where $\iota(u_{i})=+1$ or $-1$ if the vertex is, respectively, coherent or
incoherent.

A _source_ in an oriented signed graph is a vertex $v$ such that all arrows
point inward, i.e., $\tau(v,e)=+1$ for every edge end $(v,e)$ at $v$. A _sink_
is similar but all arrows point outward, i.e., $\tau(v,e)=-1$ for every edge
end $(v,e)$ at $v$. There are exactly two ways to orient a sign circuit (other
than a loose edge) so that none of its vertices is a source or sink, and they
differ only by reversing the orientations of all the edges. We call such an
edge set in an oriented signed graph a _sign cycle_.

A sign circuit $C$ has one or two minimal covering ultrawalks, up to choice of
direction and starting point, which we call _circuit walks_. The description
can be complicated. For a circle the circuit walk goes once around the circle.
For a tight handcuff whose negative figures are circles, it goes once around
each circle, crossing over at their intersection vertex. For a loose handcuff
whose negative figures are circles, it goes once around each circle and twice
through the connecting path, once in each direction; this reduces to the
circuit walk of a tight handcuff if the connecting path has length zero. For a
handcuff in which one negative figure is a circle and the other is a half edge
$h$, the circuit walk begins at $h$, goes through the connecting path (if any)
to the circle, goes once around the circle, and returns along the connecting
path to end with $h$. In a handcuff whose negative figures are both half
edges, the circuit walk is an ultrawalk that begins with one half edge and
proceeds to the other, where it ends. (The difference of the last type from
the others is due to the fact that negative circles interfere with
unimodularity while half edges do not. This oddity does not affect our theory.
For a treatment of it see [5].)

For all types, if $C$ is oriented, it is a sign cycle if and only if one
(equivalently, each) of these walks is coherent.

Now consider a circle. If it is positive, it can be coherently oriented, and
then it is a sign cycle. If it is negative, it can be coherently oriented
except at one arbitrarily chosen incoherent vertex $v$ with incident edges
$e,f$. Then we call it an _excycle_ _rooted at $v$_ if
$\tau(v,e)=\tau(v,f)=+1$ (i.e., the edge ends at $v$ point towards $v$ and
thus out of the circle) and an _incycle_ if the opposite. An incycle or
excycle is the nearest a negative circle can be to a cycle. We also call an
oriented half edge an incycle or excycle depending whether it is oriented into
or out from its vertex. The orientation of a sign cycle on a loose handcuff is
such that one circle is an incycle, the other is an excycle, and the
connecting path is a coherent path connecting the root of the excycle to the
root of the incycle and, at its endpoints, coherent with the incident circle
edges. For a tight handcuff sign cycle, the two roots are the common vertex
and the incident edges in different circles are coherent with each other.

Figure 2.3. Some sign cycles. Solid edges are positive and dashed edges are
negative. Top row: a positive circle of length 5 and a positive loop. Bottom
rows: sign-unbalanced sign circuits with different kinds of negative figures.

###  2.4. Gains

####  2.4.1. The gain function

The gain function $\varphi$ is a mapping from oriented edges to an abelian
group, written additively, such that the two orientations of the edge, $e$ and
$e^{-1}$, have mutually inverse gains, i.e., $\varphi(e^{-1})=-\varphi(e)$ (so
when we specify a value for the gain $\varphi(e)$, we must also specify the
orientation). For a positive edge or a half edge, this means that the two
directions of the edge have mutually inverse gains; but for a negative edge
there is not a direction in the usual sense. An edge with gain 0 is called
_neutral_. The set of neutral loose edges is written $E^{00}$. Note that all
edges have gains (unlike the definition in [26]).

In a slightly more formal definition, let the set of oriented edges be
$\vec{E}$. The gain function is a mapping $\varphi$ from $\vec{E}$ to an
additive abelian group with the property that $\varphi(e^{-1})=-\varphi(e)$.
(It is important to remember that $e$ and $e^{-1}$ are the same object with
opposite orientations.)

_Reorienting_ an edge in $\Upsilon$ means negating the $\tau$ values of that
edge and inverting the gain of that edge as well. We define sign-switching to
have no effect on gains.

The restriction of a gain signed graph to an edge set $S$ is
$\Upsilon|S:=(\Gamma|S,\sigma|_{S},\varphi|_{S})$, abbreviated as
$(\Gamma|S,\sigma,\varphi)$.

Suppose we treat an unsigned graph as all positive; the pair
$(\Gamma,\varphi)$ is called a _gain graph_. The frame matroid theory of
signed graphs was developed in [22]; that of gain graphs was developed in
[26]. The former is a special case of the latter; but it turns out that this
is the wrong way to look at it, at least for us. A gain signed graph is not a
gain graph: the negative edges cannot be treated as edges of a gain graph. The
reason for our treatment of negative edges will appear when we introduce the
vector model in Section 3.

Our gain group will be the additive group $\mathbf{K}^{+}$ of a field
$\mathbf{K}$ whose characteristic is not equal to 2 (because we need
$1\neq-1$), especially the real or complex numbers. We generalize this to an
arbitrary abelian group in Section 11. The most interesting such groups may be
the additive group of integers and those of the integers modulo a natural
number.

####  2.4.2. Walk gains

We now define a crucial concept: the gain sum of a sign circuit $C$. First we
define that of a walk or ultrawalk $W$. We want a definition that makes the
gain of $W$ invariant under reorientation, that agrees with the gain of a walk
in a gain graph, and that agrees with the vector model in Section 3; this
implies a complicated definition that is not invariant under sign switching.
We choose an orientation $\tau$ of $\Sigma$. Then the gain of a walk
$W=u_{0}e_{1}u_{1}e_{2}\cdots e_{l}u_{l}$ is

(2.1) $\displaystyle\varphi(W)$
$\displaystyle:=-\tau(u_{0},e_{1})\sum_{i=1}^{l}\varphi(e_{i})\prod_{j=1}^{i-1}[-\tau(u_{j},e_{j})\tau(u_{j},e_{j+1})]$
$\displaystyle=-\sum_{i=1}^{l}\varphi(e_{i})\sigma(W_{0,i-1})\tau(u_{i-1},e_{i}),$

where $W_{0,i-1}$ denotes the part of $W$ from $u_{0}$ to $u_{i-1}$. The
factor $[-\tau(u_{0},e_{1})]$ is a general sign correction that is positive if
the first edge leaves $u_{0}$, negative if it enters $u_{0}$. The factors
$[-\tau(u_{j},e_{j})\tau(u_{j},e_{j+1})]$ are positive at a coherent vertex
$u_{j}$ and negative, thus reversing the signs with which following edge gains
are added, at an incoherent vertex. That is, $\varphi(e_{i})$ is added to the
sum if it is preceded by an even number of incoherent vertices and subtracted
if preceded by an odd number of incoherent vertices.

The gain of an ultrawalk is similar but we have to take account of some
extreme cases, such as an ultrawalk that consists only of one half edge. Let
$W=e_{0}u_{0}e_{1}u_{1}e_{2}\cdots e_{l}u_{l}e_{l+1}$ be an ultrawalk, in
which $e_{0}$ and $e_{l+1}$ are half edges. Its gain is given by

(2.2) $\displaystyle\varphi(W)$
$\displaystyle:=\tau(u_{0},e_{0})\varphi(e_{0})+\varphi(W_{0l})-\varphi(e_{l+1})\sigma(W_{0l})\tau(u_{l},e_{l+1}),$

where the first term is omitted if $W$ has no initial half edge and the last
term is omitted if $W$ has no final half edge.

The gain of a walk of length $1$ may not equal the gain of the edge $e_{1}$;
that depends on the orientation of $e_{1}$. Considering the walk
$u_{0}e_{1}u_{1}$, we see that

(2.3) $\varphi(u_{0}e_{1}u_{1})=-\tau(u_{0},e_{1})\varphi(e_{1}).$

Similarly, the gain of an ultrawalk $e_{0}u_{0}$ or $u_{0}e_{1}$ is given
respectively by

(2.4) $\varphi(e_{0}u_{0})=\tau(u_{0},e_{0})\varphi(e_{0})\text{ and
}\varphi(u_{0}e_{1})=-\tau(u_{0},e_{1})\varphi(e_{1}).$

######  Lemma 2.5.

The gain of a walk or ultrawalk is invariant under reorientation and sign
switching, except that it is negated by sign switching the initial vertex.

###### Proof.

Reorienting an edge $e_{i}$ changes the sign of both $\varphi(e_{i})$ and
$\tau(u_{i-1},e_{i})$, so it has no effect on the term of $e_{i}$. For $j>i$
the sign of $W_{0,j-1}$ remains the same. Thus, there is no change to
$\varphi(W)$.

Switching the initial vertex negates $\tau(u_{0},e_{1})$ (and
$\tau(u_{0},e_{0})$ if there is an initial half edge or if $W$ is closed so
$u_{l}=u_{0}$ and we can take $e_{0}=e_{l}$), so it negates the sum in (2.1).
Switching the final vertex has no effect on the sum. Switching an internal
vertex has no effect on coherence, so it does not change the sum. ∎

######  Lemma 2.6.

For a walk or ultrawalk $W$, the gain of $W^{-1}$ is given by
$\varphi(W^{-1})=-\sigma(W)\varphi(W)$.

###### Proof.

We compute for a walk:

$\displaystyle\varphi(W)$
$\displaystyle=-\sum_{i=1}^{l}\varphi(e_{i})\sigma(W_{0,i-1})\tau(u_{i-1},e_{i})$
$\displaystyle=-\sum_{i=1}^{l}\varphi(e_{i})\sigma(W)\sigma(W^{-1}_{l,i})\sigma(e_{i})\tau(u_{i-1},e_{i})$
$\displaystyle=\sigma(W)\sum_{i=1}^{l}\varphi(e_{i})\sigma(W^{-1}_{l,i})[\tau(u_{i},e_{i})]=-\sigma(W)\varphi(W^{-1}).$

For an ultrawalk with half edges at both ends,

$\displaystyle\varphi(W)$
$\displaystyle=\tau(u_{0},e_{0})\varphi(e_{0})+\varphi(W_{0l})-\varphi(e_{l+1})\sigma(W_{0l})\tau(u_{l},i_{l+1})$
$\displaystyle=\sigma(W_{0l})[\sigma(W_{0l})\tau(u_{0},e_{0})\varphi(e_{0})+\sigma(W_{0l})\varphi(W_{0l})-\varphi(e_{l+1})\tau(u_{l},i_{l+1})]$
$\displaystyle=\sigma(W_{0l})[\varphi(e_{l+1})(-\tau(u_{l},i_{l+1})+\varphi(W_{l0})-\sigma(W_{0l})(-\tau(u_{0},e_{0}))\varphi(e_{0})]$
$\displaystyle=-\sigma(W)\varphi(W^{-1})$

by (2.2), because for the formula in the direction of $W^{-1}$, the half-edge
orientations reverse. For an ultrawalk with a half edge at only one end, omit
one term in the preceding expressions. ∎

######  Lemma 2.7.

If $W$ is the concatenation of walks, $W=W_{1}W_{2}$, then
$\varphi(W)=\varphi(W_{1})+\sigma(W_{1})\varphi(W_{2})$. The same holds for
the concatenation of any two ultrawalks $W_{1}$ and $W_{2}$ for which $W_{1}$
ends and $W_{2}$ begins at the same vertex.

###### Proof.

This follows directly from the second form of Equation 2.1, with appropriate
modifications for half edges. ∎

The complicated definitions (2.1) and (2.2) call for explanation. For
simplicity assume $W$ is a path and $\tau(u_{0},e_{0})=+1$ ($e_{0}$ leaves
$u_{0}$). Consider first a path of positive edges, all oriented in the
direction from the beginning at $u_{0}$ to the end at $u_{l}$. Then
$-\tau(u_{i-1},e_{i})=+1=\sigma(W_{0,i-1})$, so
$\varphi(W)=\sum_{i=1}^{l}\varphi(e_{i})$, simply a sum, consistent with an
ordinary gain graph. This consistency is what we want. Suppose, though, that
some of the edges (still all positive) are oriented in reverse; then at a
backward edge we have $-\tau(u_{i-1},e_{i})=-1$ so the gain of $e_{i}$ is
subtracted, not added. Equivalently, we can view this as first reorienting the
backward edges, which negates their gains, and then summing the revised gains
as in the first case. Note that reorienting (say) the first backward edge
$e_{i}$ changes $u_{i-1}$ from incoherent to coherent and reverses the
coherence of $u_{i}$ (this is for $i>1$). Thus, the number of incoherent
vertices before $e_{i}$, and only before $e_{i}$, changes parity, while the
gain changes sign. This implies that the sign we put on $\varphi(e_{i})$ is
determined by the number $p$ of preceding incoherent vertices in $W$ and the
sum should contain $(-1)^{p}\varphi(e_{i})$, exactly as stated after Equation
(2.1).

But what if our path $W$ contains negative edges? We may switch it with a
suitable sign-switching function $\zeta$ to $W^{\zeta}$ which is all positive;
this does not change the gains of edges nor the state of coherence or
incoherence at any vertex. We may choose $\zeta$ not to switch the initial
vertex, i.e., so that $\zeta(u_{0})=+1$. By Lemma 2.5
$\varphi(W^{\zeta})=\varphi(W)$. That is, the sign of $\varphi(e_{i})$ in the
sum is still determined by the number of preceding incoherent vertices.

####  2.4.3. Sign-cycle gains

Consider a positive circle $C$. Its gain $\varphi(C)$ is the sum of its edge
gains after sign switching and reorientation so it is an all-positive sign
cycle. The only uncertainty is the sign of $\varphi(C)$, which depends on the
choice of direction around $C$. There is not much else to say about it.

A handcuff $C$ is a different story. First we need a more elementary concept.

A _rooted negative figure_ $(C_{1},v)$ is a negative figure $C_{1}$ (a circle
or half edge) with a distinguished vertex $v$, the _root_. If $C_{1}$ is a
circle, to compute its gain we orient it as an excycle rooted at $v$, i.e., so
that $\tau(v,e)=-1$ for both edges at $v$. Then the _gain of $(C_{1},v)$_,
written $\varphi(C_{1},v)$, is the gain of a minimal walk around $C$ from $v$
to $v$. By Lemmas 2.5 and 2.6 and since $C$ is negative, $\varphi(C_{1},v)$ is
independent of the particular orientation and choice of direction, except that
it negates if $\tau(v,e)=+1$ for the edges at $v$.

If $C_{1}=\\{e\\}$, consisting of a half edge $e$ at vertex $v$, orient it as
an excycle, that is with $\tau(v,e)=-1$; the gain $\varphi(C_{1},v)$ is the
gain of the excycle $\\{e\\}$ considered as an oriented ultrawalk, which by
(2.4) is $\varphi(e)$ since $(C_{1},v)$ is an excycle.

Now, orient the edges of the handcuff $C$ so it is a sign cycle. If its two
negative figures are circles, choose a circuit walk $W$ around $C$ (which will
necessarily be coherent). The gain of $C$ is $\varphi(C):=\varphi(W)$. If one
negative figure in $C$ is a circle and the other is a half edge $e$, we choose
$W$ to be a circuit ultrawalk that begins and ends with $e$. If both negative
figures are half edges, we choose $W$ to be a circuit ultrawalk that begins at
one half edge and ends at the other (this type is exceptional in that the
connecting path is traversed only once).

For a loose edge $e$, its gain as a sign circuit is its gain as an edge.

In the following proposition we compute the gain of a sign circuit.

######  Proposition 2.8.

The gain of a sign circuit $C$ is well defined up to negation and choice of
circuit walk. For a positive circle $C$, it is the sum of the edge gains when
$C$ is oriented so every vertex is coherent. If $C$ is a handcuff with rooted
negative figures $(C_{1},u_{1})$ and $(C_{2},u_{2})$ where the roots are the
endpoints of the connecting path $P$, and $P$ is oriented out of $u_{1}$, then

$\varphi(C)=\varphi(C_{1},u_{1})-\varphi(C_{2},u_{2})-2\varphi(P_{u_{1}u_{2}})$

(or its negative) if both negative figures are circles,

$\varphi(C)=2\varphi(C_{1},u_{1})-\varphi(C_{2},u_{2})-2\varphi(P_{u_{1}u_{2}})$

(or its negative) if $C_{1}$ is a half edge and $C_{2}$ is a circle, and

$\varphi(C)=\varphi(C_{1},u_{1})-\varphi(C_{2},u_{2})-\varphi(P_{u_{1}u_{2}})$

(or its negative) if both negative figures are half edges.

###### Proof.

If $C$ is a positive circle, this is obvious. Thus, assume $C$ is a handcuff
with connecting path $P=P_{u_{1}u_{2}}$ from $u_{1}$ to $u_{2}$. By sign
switching make $P$ positive. Note that $\varphi(C_{i})$ for a negative circle
is computed by taking a walk on it from $u_{i}$ to $u_{i}$. For a half edge
$\varphi(C_{i})$ is computed by taking a walk from $u_{i}$.

First, consider the case where $C_{1}$ and $C_{2}$ are circles. We apply Lemma
2.7 to $W=C_{1}PC_{2}P^{-1}$ but we have to be careful about signs. We get

$\displaystyle\varphi(W)$
$\displaystyle=\varphi(C_{1})+\sigma(C_{1})\varphi(P)+\sigma(C_{1}P)\varphi(C_{2})+\sigma(C_{1}PC_{2})\varphi(P^{-1})$
$\displaystyle=\varphi(C_{1})-\varphi(P)-\varphi(C_{2})+\varphi(P^{-1})$
$\displaystyle=\varphi(C_{1})-\varphi(C_{2})-2\varphi(P)$

because $\varphi(P^{-1})=-\varphi(P)$ by Lemma 2.6.

If we interchanged the roles of $C_{1}$ and $C_{2}$, taking the walk
$W^{\prime}=C_{2}P^{-1}C_{1}P$, we would get the negated gain
$\varphi(C_{2})-\varphi(P^{-1})-\varphi(C_{1})+\varphi(P)=\varphi(C_{2})-\varphi(C_{1})+2\varphi(P)$;
that explains the ambiguity of negation.

Second, consider the case where $C_{1}=\\{e_{1}\\}$ for a half edge $e_{1}$
and $C_{2}$ is a circle. Take the circuit ultrawalk
$W=C_{1}u_{1}Pu_{2}C_{2}u_{2}P^{-1}u_{1}C_{1}$. We initially walk on $C_{1}$
from $e_{1}$ to $u_{1}$, which is $C_{1}^{-1}$ because $C_{1}$ is an excycle
for computing $\varphi(C_{1})$. The calculation gives

$\displaystyle\varphi(W)$
$\displaystyle=\varphi(C_{1}^{-1})+\sigma(C_{1})\varphi(P)+\sigma(C_{1}P)\varphi(C_{2})$
$\displaystyle\quad+\sigma(C_{1}PC_{2})\varphi(P^{-1})+\sigma(C_{1}PC_{2}P^{-1})\varphi(C_{1})$
$\displaystyle=-\sigma(C_{1})\varphi(C_{1})-\varphi(P)-\varphi(C_{2})+\varphi(P^{-1})+\varphi(C_{1})$
by Lemma 2.6 applied to $C_{1}$,
$\displaystyle=2\varphi(C_{1})-\varphi(C_{2})-2\varphi(P).$

Finally, consider the case where $C_{1}=\\{e_{1}\\}$ and $C_{2}=\\{e_{2}\\}$
are both half-edge figures. Take the circuit ultrawalk
$W=e_{1}u_{1}Pu_{2}e_{2}$. Then

$\displaystyle\varphi(W)$
$\displaystyle=\varphi(C_{1}^{-1})+\sigma(C_{1})\varphi(P)+\sigma(C_{1}P)\varphi(C_{2})$
$\displaystyle=\varphi(C_{1})-\varphi(P)-\varphi(C_{2}).$

Independence of the choice of circuit walk follows from the formulas for
$\varphi(C)$. ∎

Now we can make the key definition.

######  Definition 2.9 (Hyperbalance).

A sign circuit is _neutral_ if its gain is $0$. An arbitrary edge set or
subgraph is _hyperbalanced_ if every sign circuit in it is neutral; otherwise
it is _hyperfrustrated_.

Neutrality is the fundamental fact about an edge set. It is independent of
orientation, because by Lemmas 2.5 and 2.6 neutrality of a sign circuit is
independent of orientation. The list of neutral sign circuits is the essential
datum upon which we base the definition of the matroid of a gain signed graph.

####  2.4.4. Gain switching

Gains can be switched by a gain-switching function, briefly _gain switcher_ ,
which is a function $\theta:V\to\mathbf{K}^{+}$ (until Section 11). The gain
function $\varphi$ switches to $\varphi^{\theta}$ defined on an oriented edge
$e=e_{vw}$ by

$\displaystyle\varphi^{\theta}(e)$
$\displaystyle:=\tau(v,e)\theta(v)+\varphi(e)+\tau(w,e)\theta(w)$
$\displaystyle=\varphi(e)+\tau(v,e)[\theta(v)-\sigma(e)\theta(w)].$

For example, if $\theta$ is a constant, then
$\varphi^{\theta}(e)=\varphi(e)+\tau(v,e)(1-\sigma(e))\theta$. For a half edge
$e=e_{v}$,

$\varphi^{\theta}(e):=\tau(v,e)\theta(v)+\varphi(e).$

Gain switching has no effect on a loose edge.

Very similar is the concept of a _gain potential_ for an edge set $S$, which
is a mapping $\bar{\theta}:V\to\mathbf{K}^{+}$ such that

$\varphi(e_{vw})=\tau(v,e)\bar{\theta}(v)+\tau(w,e)\bar{\theta}(w)$

for every link or loop in $S$, $\varphi(e_{v})=\tau(v,e)\bar{\theta}(v)$ for
every half edge in $S$, and $\varphi(e_{\varnothing})=0$ for every loose edge
in $S$. A gain potential for $S$ is the negative of a gain switcher that
switches $S$ to all neutral gains. For a gain switcher $\theta$ we define

$\displaystyle E(\theta)$ $\displaystyle:=(\varphi^{\theta})^{-1}(0)$
$\displaystyle\,=\\{e_{vw}\in
E:\varphi(e_{vw})=-\tau(v,e)\theta(v)-\tau(w,e)\theta(w)\\}$
$\displaystyle\qquad\cup\\{e_{v}\in E:\varphi(e_{v})=-\tau(v,e)\theta(v)\\}$
$\displaystyle\qquad\cup E^{00},$

i.e., it is the largest edge set such that $-\theta$ is a gain potential for
these edges. Combining gain and sign potentials,
$E(\theta,\zeta):=E(\theta)\cap E(\zeta)$, which is the set of edges with sign
determined by $\zeta$ and gain by $\theta$.

######  Lemma 2.10.

Switching the gains does not change the gain sum of a positive closed walk or
an ultrawalk with a half edge at each end. More generally, switching the gains
on a walk or ultrawalk $W$ from $u_{0}$ to $u_{l}$ ($l\geq 0$) gives switched
gain

$\displaystyle\varphi^{\theta}(u_{0}e_{1}\cdots u_{l})$
$\displaystyle=-\theta(u_{0})+\varphi(W)+\sigma(W)\theta(u_{l}),$
$\displaystyle\varphi^{\theta}(e_{0}u_{0}e_{1}\cdots u_{l})$
$\displaystyle=-\theta(u_{0})+\varphi(W),$
$\displaystyle\varphi^{\theta}(u_{0}e_{1}\cdots u_{l}e_{l+1})$
$\displaystyle=\varphi(W)+\sigma(W_{0l})\theta(u_{l}),$
$\displaystyle\varphi^{\theta}(e_{0}u_{0}e_{1}\cdots u_{l}e_{l+1})$
$\displaystyle=\varphi(W_{0l}),$

###### Proof.

We check by a calculation, which we present for an ultrawalk with a half edge
at each end:

$\displaystyle\varphi^{\theta}(W)$
$\displaystyle=\tau(u_{0},e_{0})[\varphi(e_{0})+\tau(u_{0},e_{0})\theta(u_{0})]$
$\displaystyle\quad-\sum_{i=1}^{l}[\tau(u_{i-1},e_{i})\theta(u_{i-1})+\varphi(e_{i})+\tau(u_{i},e_{i})\theta(u_{i})]\sigma(W_{0,i-1})\tau(u_{i-1},e_{i})$
$\displaystyle\quad-[\tau(u_{l},e_{l+1})\theta(u_{l})+\varphi(e_{l+1})]\sigma(W_{0l})\tau(u_{l},e_{l+1})$
$\displaystyle=\theta(u_{0})-\sum_{i=1}^{l}[\theta(u_{i-1})+\tau(u_{i},e_{i})\tau(u_{i-1},e_{i})\theta(u_{i})]\sigma(W_{0,i-1})$
$\displaystyle\quad-\theta(u_{l})\sigma(W_{0l})+\varphi(W)$
$\displaystyle=\theta(u_{0})-\sum_{i=1}^{l}\theta(u_{i-1})\sigma(W_{0,i-1})+\sum_{i=1}^{l}\theta(u_{i})\sigma(W_{0i})-\theta(u_{l})\sigma(W_{0l})+\varphi(W)$
$\displaystyle=[\theta(u_{0})-\theta(u_{l})\sigma(W_{0l})]-\theta(u_{0})+\theta(u_{l})\sigma(W_{0l})+\varphi(W).$

The two terms in square brackets apply when there is an initial half edge
$e_{0}$ (the first term) or a terminal half edge $e_{l+1}$ (the second term).
The stated formulas follow from this.

Evidently, $\varphi^{\theta}(W)$ equals $\varphi(W)$ when $W$ is closed and
positive and also when it begins and ends with a half edge. ∎

The effect of switching on the gain of a walk does not depend on orientation.

######  Theorem 2.11.

Switching of signs and gains preserves the property of hyperbalance or
hyperunbalance of every edge set.

###### Proof.

For sign switching this is obvious. The gain sum of a sign circuit equals the
gain sum of a circuit walk on it, and by Lemma 2.10 switching preserves that
sum, so a neutral or non-neutral sign circuit remains neutral or non-neutral,
respectively. ∎

For stating the next lemma we define a _pseudotree_ to be a tree or a tree
with an attached half edge. A _pseudoforest_ is a graph whose components are
pseudotrees. If $T$ is a pseudotree with a half edge $e$ at vertex $v$, then
$T_{re}$ denotes the path in $T$ from $r$ ending with $e$.

######  Lemma 2.12.

Let $\Upsilon$ be a gain signed graph and $T$ a pseudoforest. The gains can be
switched to $\Upsilon^{\theta}$ in which $T$ has all gains $0$.

For connected $T$, the gain-switching function is given by
$\theta(v):=\sigma(T_{rv})[\theta_{0}+\varphi(T_{rv})]$, where $r$ is an
arbitrarily fixed root vertex. If $T$ is a tree, $\theta_{0}$ is any element
of $\mathbf{K}$. If $T$ has a half edge $e$ at vertex $v$, then
$\theta_{0}=\varphi(T_{re})$.

###### Proof.

We may assume $\Upsilon$ is connected and the root $r$ is fixed. We prove that
$\theta$ defined in the lemma is a switching function that makes all gains
$0$.

Consider an edge $e_{l}=vw\in T$ whose endpoint farther from the root is $w$,
and let $T_{rw}=u_{0}e_{01}\cdots u_{i-1}e_{i-1,l}u_{l}$ in $T$, where
$r=u_{0}$, $e=e_{l-1,l}$, $v=u_{l-1}$, and $w=u_{l}$). The switched gain is
given by

$\displaystyle
0=\varphi^{\theta}(e)=\tau(u_{l-1},e)\theta(u_{l-1})+\varphi(e)+\tau(u_{l},e)\theta(u_{l}),$

from which it follows that

$\displaystyle\sigma(T_{rw})\theta(w)$
$\displaystyle=\sigma(T_{ru_{l-1}})\theta(u_{l-1})+\sigma(T_{ru_{l-1}})\tau(u_{l-1},e_{l-1,l})\varphi(e_{l-1,l})$
$\displaystyle=\theta(r)+\sum_{i=1}^{l}\sigma(T_{ru_{i-1}})\tau(u_{i-1},e_{i-1,i})\varphi(e_{i-1,i})$
$\displaystyle=\theta(r)-\varphi(T_{rw})$

by (2.1). This gives the value of $\theta(w)$, with an arbitrary constant
$\theta(r)$ that we call $\theta_{0}$, provided there is no half edge in $T$.

If there is a half edge $e$ at vertex $v$, its switched gain is
$0=\varphi^{\theta}(e)=\tau(v,e)\theta(v)+\varphi(e),$ hence
$\theta(v)=-\tau(v,e)\varphi(e).$ Inserting this into the general formula for
$\theta(v)$ gives the value of $\theta_{0}$:

$\theta_{0}=\varphi(T_{rv})-\sigma(T_{rv})\tau(v,e)\varphi(e)=\varphi(T_{re})$

by (2.2). ∎

It is easy to see that, if $T$ has no half edge, any one choice of root gives
all possible switching functions by varying $\theta_{0}$. A similar proof
establishes that the gains on $T$ can be set by gain switching to any desired
values; we omit the details. We mention that if $T$ is all positive and is
oriented as an out-arborescence from $r$, then $\varphi(T_{rv})$ equals the
sum of the gains of edges in $T_{rv}$.

######  Theorem 2.13.

The gain signed graph $\Upsilon$ is hyperbalanced if and only if its gains can
be switched so all edges are neutral.

###### Proof.

Sufficiency is trivial. For necessity, we may assume $\Upsilon$ is connected
and, by suitably switching signs, has an all-positive spanning tree $T$. By
reorientation make all negative edges (including half edges) introverted. By
gain-switching as in Lemma 2.12 we can make all tree gains $0$.

First, we show all positive edges have gain $0$. Let $e$ be such an edge, not
in $T$. The unique circle $C_{T}(e)\subseteq T\cup\\{e\\}$ is all positive,
hence a sign circuit, hence it has gain $0$. From the definition,
$\varphi(C_{T}(e))=\pm\varphi(e)$; that implies $\varphi(e)=0$.

Next, we show all negative links and loops have the same gain. Two such edges,
$e$ and $f$, form circles $C_{T}(e)$ and $C_{T}(f)$, whose intersection may be
either a path of positive length, or at most a single vertex. In the former
case, $C_{T}(e)\cup C_{T}(f)$ is a theta graph in which there is a positive
circle $C$ containing both negative edges. Take a walk $W=u_{0}eu_{1}\cdots
u_{i-1}fu_{i}\cdots u_{0}$ around $C$; then
$\varphi(W)=-\tau(u_{0},e)\varphi(e)-\sigma(W_{0,i-1})\tau(u_{i-1},f)\varphi(f)=\varphi(e)-\varphi(f)$.
As $C$ is hyperbalanced, $\varphi(e)=\varphi(f)$. In the latter case,
$T\cup\\{e,f\\}$ contains a handcuff circuit $C$ in which $e$ and $f$ belong
to opposite circles; by Proposition 2.8 a circuit walk around $C$ gives the
same conclusion that $\varphi(e)=\varphi(f)$.

Consider two half edges, $e$ and $f$. They are joined by a path $P$ of length
$l$ in $T$ with which they make an ultrawalk $W$, which is a circuit walk on
the circuit $C=P\cup\\{e,f\\}$. As in the previous case, by Proposition 2.8
$\varphi(W)=\varphi(e)-\varphi(f)$ so $\varphi(e)=\varphi(f)$ by hyperbalance.
That is, all half edges have the same gain.

Now compare a half edge $e$ to a negative link or loop $f$. $T\cup\\{e,f\\}$
contains a handcuff circuit $C$ in which $f$ belongs to a negative circle and
$\varphi(C)=2\varphi(e)-\varphi(f)=0$. Thus, the gain of a half edge equals
half that of a negative link or loop.

Let the common value of $\varphi(e)$ for all negative links and loops be
$\varphi_{0}$ and switch by the constant switching function
$\theta\equiv\frac{1}{2}\varphi_{0}$; or if there are no such edges, let
$\varphi_{1}$ be the gain of a half edge and switch by the constant function
$\theta\equiv\varphi_{1}$. This reduces the gains of all negative edges to
$0$.

Hyperbalance implies that all loose edges are neutral. Thus, all edges have
gain $0$ after gain switching.

Finally, switch the signs back with the original sign switcher. This does not
change the gains, which remain identically $0$. ∎

Now that we have three separate operations, two switchings and a
reorientation, that preserve essential properties, it is desirable to know how
they commute. Sign and gain switching, on the other hand, do not commute.
Define an action of $\zeta:V\to\\{\pm 1\\}$ on $\theta:V\to\mathbf{K}^{+}$ by
$\theta^{\zeta}(v):=\zeta(v)\theta(v)$.

######  Proposition 2.14 (Commutation of Switching and Reorientation).

The commutation relations among sign switchers $\zeta$, gain switchers
$\theta$, and reorientation functions $\rho$ are
$\zeta\theta=\theta^{\zeta}\zeta$, $\zeta\rho=\rho\zeta$, and
$\theta\rho=\rho\theta$.

###### Proof.

We leave to the reader the proof that reorientation commutes freely with both
switchings. Hint: Define a reorientation function $\rho:E\to\\{\pm 1\\}$ such
that $\varphi^{\rho}(e)=\rho(e)\varphi(e)$ and
$\tau^{\rho}(v,e)=\rho(e)\tau(v,e)$ (assuming $v$ is an endpoint of $e$),
i.e., $\rho$ acts on $\varphi$ and $\tau$ by multiplication.

Under the action of $\zeta$, the orientation $\tau$ required for gain
switching changes to $\tau^{\zeta}:=\zeta\tau$, i.e.,
$\tau^{\zeta}(v,e)=\zeta(v)\tau(v,e)$. The actions of $\theta\zeta$ and
$\zeta\theta$ on $\varphi$ are given by

$\displaystyle\varphi^{\theta\zeta}(e_{vw}):=(\varphi^{\theta})^{\zeta}(e_{vw})$
$\displaystyle=\varphi^{\theta}(e_{vw})$ because sign switching does not
change gains,
$\displaystyle=\tau(v,e)\theta(v)+\varphi(e_{vw})+\tau(w,e)\theta(w)$ for
$e=e_{vw}$, while
$\displaystyle\varphi^{\zeta\theta}(e_{vw}):=(\varphi^{\zeta})^{\theta}(e_{vw})$
$\displaystyle=\tau^{\zeta}(v,e)\theta(v)+\varphi^{\zeta}(e_{vw})+\tau^{\zeta}(w,e)\theta(w)$
$\displaystyle=\zeta(v)\tau(v,e)\theta(v)+\varphi(e_{vw})+\zeta(w)\tau(w,e)\theta(w)$
$\displaystyle=\tau(v,e)\theta^{\zeta}(v)+\varphi(e_{vw})+\tau(w,e)\theta^{\zeta}(w)$
$\displaystyle=\varphi^{\theta^{\zeta}}(e_{vw})=\varphi^{\theta^{\zeta}\zeta}(e_{vw})$

according to the preceding calculation. Note that in
$\varphi^{\theta^{\zeta}\zeta}$, $\zeta$ acts on $\tau$ after $\theta^{\zeta}$
is applied to $\varphi$, while in $\varphi^{\zeta\theta}$, $\zeta$ acts on
$\tau$ before $\theta^{\zeta}$ is applied. The action on $\tau$ is why
$\zeta\theta=\theta^{\zeta}\zeta\neq\theta^{\zeta}$. ∎

Proposition 2.14 suggests that the full switching group, which combines both
kinds of switching, might be a semidirect product
$(\mathbf{K}^{+})^{V}\rtimes\\{+1,-1\\}^{V}$, but it is not; the associative
law fails, as the reader can verify.

###  2.5. The extra point

In Section 4 we will define a matroid on the edge set of $\Upsilon$ that has a
one-point extension by an _extra point_ $e_{\infty}$, which is not part of the
graph. The extension is necessary for a full understanding of the matroid and
its canonical hyperplane representation. (We call it a point because it is a
point in the geometrical interpretation of our matroid; in the projective dual
interpretation of Section 10.2, where matroid points are affine hyperplanes,
$e_{\infty}$ corresponds to the infinite hyperplane.) We write
$E_{\infty}=E\cup\\{e_{\infty}\\}.$ The extra point, not being an edge, does
not have a sign or gain.

##  3\. The vector model

Our definition of the matroid of $\Upsilon$ is modeled on a mental picture of
vectors over a field $\mathbf{K}$, so we begin the main work with that
picture. We are in $\mathbf{K}^{1+n}$ with coordinates
$x_{0},x_{1},\ldots,x_{n}$, the coordinate $x_{i}$ corresponding to the vertex
$v_{i}$. The standard unit basis is
$\\{\mathbf{b}_{0},\mathbf{b}_{1},\ldots,\mathbf{b}_{n}\\}$. The
$x_{0}$-coordinate is special: it contains gains. There is a natural
projection $\pi_{0}:\mathbf{K}^{1+n}\to\mathbf{K}^{n}$ by deleting the
$x_{0}$-coordinate.

Here is the vector associated to an edge $e=e_{v_{i}v_{j}}$. We assume an
orientation $\tau$; reversing the orientation of $e$ negates the vector.

$\mathbf{z}(e)=\mathbf{z}_{\tau}(e):=\varphi(e)\mathbf{b}_{0}+\tau(v_{i},e)\mathbf{b}_{i}+\tau(v_{j},e)\mathbf{b}_{j}=\begin{pmatrix}\varphi(e)\\\
0\\\ \vdots\\\ \tau(v_{i},e)\\\ 0\\\ \vdots\\\ \tau(v_{j},e)\\\ 0\\\
\vdots\end{pmatrix},$

where the nonzero rows are numbered 0, $i$, $j$, respectively. This is for a
link. If $e$ is a loop, so $v_{i}=v_{j}$, the $\tau$ values are added together
in row $i$ of the matrix form. Thus, a positive loop has $x_{i}=0$ and a
negative loop has $x_{i}=\pm 2$. For a half edge $e=e_{v_{i}}$ we define

$\mathbf{z}(e)=\mathbf{z}_{\tau}(e):=\varphi(e)\mathbf{b}_{0}+\tau(v_{i},e)\mathbf{b}_{i}=\begin{pmatrix}\varphi(e)\\\
0\\\ \vdots\\\ \tau(v_{i},e)\\\ 0\\\ \vdots\end{pmatrix}.$

For a loose edge $e=e_{\varnothing}$,

$\mathbf{z}(e)=\mathbf{z}_{\tau}(e):=\varphi(e)\mathbf{b}_{0}=\begin{pmatrix}\varphi(e)\\\
\mathbf{0}\end{pmatrix}$

(which has ambiguous sign if $\varphi(e)\neq 0$, but that will not affect any
of our theory; for linear algebra with the vector of a loose edge, what
matters is only whether the gain is $0$ or not).

This defines a mapping $\mathbf{z}:E\to\mathbf{K}^{1+n}$. We call the vectors
corresponding to the edges of $\Upsilon$ the _standard vector representation_
of $\Upsilon$. Note that $\pi_{0}\mathbf{z}=\mathbf{x}$, the signed-graph
representation mapping of Theorem 2.4.

The extra point $e_{\infty}$ corresponds to the vector
$\mathbf{z}(e_{\infty})=(1,\bf 0)$; that correspondence extends $\mathbf{z}$
to a mapping $\mathbf{z}:E_{\infty}\to\mathbf{K}^{1+n}$.

The _incidence matrix_ of $\Upsilon$ is the $(1+n)\times|E|$ matrix that has a
column for each edge, in which is placed the standard vector $\mathbf{z}(e)$.
The _extended incidence matrix_ has an extra column $\mathbf{z}(e_{\infty})$
for the extra point. We mention incidence matrices because they have many
uses, such as to define flows on the graph, but those uses are outside the
scope of this article.

Given a sign switcher $\zeta$, define the diagonal switching matrix
$D_{\zeta}:=\left(\begin{matrix}1&\mathbf{0}^{\text{\rm T}}\\\
\mathbf{0}&\operatorname{Diag}(\zeta)\end{matrix}\right)$. Evidently, this
matrix is self-inverse.

######  Lemma 3.1.

Some elementary properties of the vector representation are:

  1. (1)

$\mathbf{z}(e^{-1})=-\mathbf{z}(e)$.

  2. (2)

Switching signs by $\zeta$ multiplies vectors by $D_{\zeta}$: that is,
$\mathbf{z}(e)$ becomes $D_{\zeta}\mathbf{z}(e)$.

  3. (3)

Switching gains by $\theta$ changes $\mathbf{z}(e)$ to

$[\tau(v_{i},e)\theta(v_{i})+\tau(v_{j},e)\theta(v_{j})]\mathbf{b}_{0}+\mathbf{z}(e)$

for a loop or link $e=e_{ij}$ and to
$\tau(v_{i},e)\theta(v_{i})\mathbf{b}_{0}+\mathbf{z}(e)$ for a half edge
$e=e_{i}$. It has no effect on a loose edge.

Given an orientation $\tau$ of $\Sigma$ and a walk $W$ from $u_{0}=v_{i}$ to
$u_{l}=v_{j}$, we define

(3.1)
$\mathbf{z}(W):=-\tau(u_{0},e_{1})\sum_{k=1}^{l}\mathbf{z}(e_{k})\prod_{m=1}^{k-1}[-\tau(u_{m},e_{m})\tau(u_{m},e_{m+1})].$

For an ultrawalk $W$, add $\tau(u_{0},e_{0})\mathbf{z}(e_{0})$ if $W$ begins
with a half edge $e_{0}$ and add
$-\tau(u_{l},e_{l+1})\sigma(W_{0l})\mathbf{z}(e_{l+1})$ if $W$ ends with a
half edge $e_{l+1}$.

######  Lemma 3.2.

For an ultrawalk $W=e_{0}u_{0}\cdots u_{l}e_{l+1}$ that begins with a half
edge $e_{0}$ at vertex $u_{0}$ and ends with a half edge $e_{l+1}$ at vertex
$u_{l}$, we have

$\displaystyle\mathbf{z}(W)$
$\displaystyle=\mathbf{z}(e_{0})\tau(u_{0},e_{0})-\sum_{k=1}^{l}\mathbf{z}(e_{k})\sigma(W_{0,k-1})\tau(u_{k-1},e_{k})-\mathbf{z}(e_{l+1})\sigma(W_{0l})\tau(u_{l},e_{l+1})$
$\displaystyle=\mathbf{z}(e_{0})\tau(u_{0},e_{0})+\sum_{k=1}^{l}\mathbf{z}(e_{k})\sigma(W_{0,k})\tau(u_{k},e_{k})-\mathbf{z}(e_{l+1})\sigma(W_{0l})\tau(u_{l},e_{l+1}).$

If the ultrawalk begins at vertex $u_{0}$ (without $e_{0}$), omit the first
term. If it ends at vertex $u_{l}$ (without $e_{l+1}$), omit the last term.

###### Proof.

The expressions for $\mathbf{z}(W)$ equal the definition for the same reason
the two expressions in formula (2.1) are equal. ∎

######  Proposition 3.3.

The vector $\mathbf{z}(W)$ of a positive closed walk or an ultrawalk with
initial and terminal half edges is unchanged by gain switching.

###### Proof.

See Lemma 2.10. ∎

We can state walk vectors in the same form as we have stated edge vectors. To
emphasize the similarity we describe the walk vectors as if they were the
vectors of fictitious edges.

######  Proposition 3.4.

  1. (I)

For a walk $W$ from $v_{i}$ to $v_{j}$, the vector $\mathbf{z}(W)$ equals the
vector
$\mathbf{z}(e_{ij})=\varphi(W)\mathbf{b}_{0}-\mathbf{b}_{i}+\sigma(W)\mathbf{b}_{j}$
of an edge $e_{ij}$ with sign $\sigma(W)$ and gain $\varphi(W)$.

In particular, for a closed walk $W$ from $v_{i}$ to $v_{i}$, the vector
$\mathbf{z}(W)$ equals the vector
$\varphi(W)\mathbf{b}_{0}-(1-\sigma(W))\mathbf{b}_{i}$ of a loop at $v_{i}$
with sign $\sigma(W)$ and gain $\varphi(W)$.

For a circuit walk $W$ on a sign circuit $C$,
$\mathbf{z}(W)=\varphi(C)\mathbf{b}_{0}$.

  2. (II)

For an ultrawalk $W$ from $v_{i}$ to a terminal half edge, the vector
$\mathbf{z}(W)$ equals the vector
$\mathbf{z}(e_{i})=\varphi(W)\mathbf{b}_{0}-\mathbf{b}_{i}$ of an introverted
half edge $e_{i}$ with gain $\varphi(W)$.

  3. (III)

For an ultrawalk $W$ from an initial half edge to $v_{j}$, the vector
$\mathbf{z}(W)$ is $\varphi(W)\mathbf{b}_{0}+\sigma(W)\mathbf{b}_{j}$, which
is the vector $\mathbf{z}(e_{j})$ of a half edge $e_{j}$ with gain
$\varphi(W)$ and which is extraverted or introverted depending on the sign of
$W$.

  4. (IV)

For an ultrawalk $W$ that begins and ends with a half edge, the vector
$\mathbf{z}(W)$ equals $\varphi(W)\mathbf{b}_{0}$, the vector of a loose edge
with gain $\varphi(W)$.

###### Proof.

We prove part (I). Let $W=u_{0}e_{1}u_{1}\cdots e_{l}u_{l}$ where the vertices
are $u_{k}=v_{i_{k}}$, and the edges are $e_{k}=u_{k-1}u_{k}$. Then

$\displaystyle\mathbf{z}(W)$
$\displaystyle=\sum_{k=1}^{l}\mathbf{z}(e_{k})\sigma(W_{0,k})\tau(u_{k},e_{k})$
$\displaystyle=\sum_{k=1}^{l}\big{[}\varphi(e_{k})\mathbf{b}_{0}+\tau(u_{k-1},e_{k})\mathbf{b}_{i_{k-1}}+\tau(u_{k},e_{k})\mathbf{b}_{i_{k}}\big{]}\sigma(W_{0,k})\tau(u_{k},e_{k})$
$\displaystyle=\sum_{k=1}^{l}\varphi(e_{k})\sigma(W_{0,k})\tau(u_{k},e_{k})\mathbf{b}_{0}$
$\displaystyle\qquad+\sum_{k=1}^{l}\sigma(W_{0,k-1})\tau(u_{k-1},e_{k})\tau(u_{k},e_{k})\mathbf{b}_{i_{k-1}}+\sum_{k=1}^{l}\sigma(e_{k})\sigma(W_{0,k-1})\mathbf{b}_{i_{k}}$
$\displaystyle=\varphi(W)\mathbf{b}_{0}-\sum_{k=1}^{l}\sigma(W_{0,k-1})\sigma(e_{k})\mathbf{b}_{i_{k-1}}+\sum_{k=1}^{l}\sigma(e_{k})\sigma(W_{0,k-1})\mathbf{b}_{i_{k}}$
$\displaystyle=\varphi(W)\mathbf{b}_{0}-\mathbf{b}_{i_{0}}+\sigma(W_{0l})\mathbf{b}_{i_{l}}$

because of the definition of $\varphi(W)$ in (2.1) and our convention that
$\tau(u_{0},e_{1})=-1$ for a walk beginning at $u_{0}$.

The proofs of the three other cases are the same except for the extra initial
and final terms, which cancel terms in case (I). The extra term for a terminal
half edge $e_{l+1}$ equals $-\sigma(W)\mathbf{b}_{j}$. The extra term for an
initial half edge $e_{0}$ equals $\mathbf{b}_{i}$. ∎

######  Corollary 3.5.

A sign circuit is a circuit in the vector model if and only if it has gain
$0$. Otherwise, it is linearly independent

By “in the vector model” we mean the vectors that represent the edges of the
sign circuit.

###### Proof.

A proper subset $S$ of a sign circuit $C$ is independent in the frame matroid
$\mathbf{K}(\Sigma)$ and hence the set $\\{\pi_{0}\mathbf{z}(e):e\in S\\}$ of
projected vectors is independent. It follows that $\\{\mathbf{z}(e):e\in S\\}$
is independent.

The linear combination of vectors $\pi_{0}\mathbf{z}(e)$ for $e\in C$ that
yields $\mathbf{0}$ is unique (up to scaling) because the vectors are
minimally dependent. Therefore, the vectors $\mathbf{z}(e)$ can be dependent
only if that linear combination has $x_{0}=0$. The corollary now follows from
Proposition 3.3. ∎

This is a partial solution to finding the circuits of the matroid
$\mathbf{M}(\Upsilon)$. The full answer is complicated, so we turn in the next
section to the simpler question of rank.

######  Example 3.6 (Edge Points of an Edge Polytope [11]).

The example that led us to gains on signed graphs comes from algebra. For an
edge $e_{ij}$ in a graph $\Gamma$ (all of whose edges are links and loops) its
edge point is $\mathbf{b}_{i}+\mathbf{b}_{j}\in\mathbb{A}^{n}(\mathbb{R})$
(which corresponds to the vector
$\mathbf{z}(-e_{ij})=\mathbf{b}_{0}+\mathbf{b}_{i}+\mathbf{b}_{j}\in\mathbb{R}^{1+n}$
of the extraverted orientation of $-e_{ij}$). The convex hull $P$ of the edge
points, known as the _edge polytope_ of $\Gamma$, is related to binomial
ideals. Ohsugi and Hibi found that the affine dimension of the edge polytope
(assuming $\Gamma$ is connected) is $n-2$ if $\Gamma$ is bipartite and $n-1$
if it is not [11, Proposition 1.3]. Restated in terms of signed graphs: the
dimension is $n-2$ if $-\Gamma$ is balanced and 1 greater if it is not. As
affine dimension is 1 less than matroid rank, this corresponds exactly to the
rank of the frame matroid $\mathbf{F}(-\Gamma)$ and should be deducible by
matroid theory. In developing our theory we wanted to generalize to arbitrary
oriented signed graphs, where the edge points of this example correspond to
extraverted edges. For a point in affine space its vector has the extra
coordinate $x_{0}=1$, thus the gains are identically 1. We found it easiest
and most enlightening to allow arbitrary gains (as far as possible). Hence,
gain signed graphs.

We give a matroidal proof of Ohsugi and Hibi’s Proposition 1.3. When all edges
are negative, the sign-balanced circles are those of even length; thus, the
sign circuits are the even circles and the handcuffs with two odd circles.
Taking gains identically 1 implies that every sign circuit is neutral so the
gain signed graph $\Upsilon=(\Gamma,-1,1)$ (that is, all edges being negative
with gain 1) is hyperbalanced. Now we anticipate the rank function of Section
4. Let $b(S)$ be the number of bipartite components of an edge set $S$
(considered as a spanning subgraph). An edge set $S$ has rank $n-b(S)$. For a
connected graph, therefore, $\operatorname{rk}_{\Upsilon}(E)=n-1$ if $\Gamma$
is bipartite and $n$ if not. The rank is the linear dimension of the vectors
in $\mathbb{R}^{n}$, but since the edge vectors
$\mathbf{b}_{i}+\mathbf{b}_{j}$ are contained in the inhomogeneous hyperplane
$\sum x_{i}=2$, their affine dimension is one less; that is, $\dim P=n-2$ if
$\Gamma$ is bipartite and $n-1$ otherwise.

######  Example 3.7 (Edge Points for a Bidirected Graph).

The edge points of Example 3.6 are the columns of the unoriented incidence
matrix of the graph. (To define that matrix, reverse the previous sentence.)
After the edge polytope was introduced, Matsui et al. [10]) considered the
analog for an oriented incidence matrix, which is the incidence matrix of an
all-positive signed graph. (To get that matrix, take an all-positive gain
signed graph and delete the row of gains.) An oriented positive edge is an
ordinary directed edge. Our theory enables us to state the affine dimension of
the points corresponding to directed edges, which may differ from their linear
dimension (see the next example). In fact, we can state a general theorem for
the points obtained from any edges of any bidirected graph. Again, we
anticipate Theorem 4.2.

First we examine coherent and incoherent vertices of a closed walk in a
bidirected graph. Let $W=u_{0}e_{1}u_{1}\cdots e_{l}u_{l}$ be a closed walk;
that is, $u_{0}=u_{l}$. For convenience, define $e_{l+1}=e_{1}$. The sign of
$W$ is

$\sigma(W)=\prod_{i=1}^{l}\sigma(e_{i})=\prod_{i=1}^{l}\big{[}-\tau(u_{i-1},e_{i})\tau(u_{i},e_{i})\big{]}=(-1)^{l}\prod_{i=1}^{l}\tau(u_{i-1})\prod_{i=1}^{l}\tau(u_{i},e_{i}).$

Define the incoherence sign for vertex $u_{i}$ to be $\iota(u_{i})=+1$ if $W$
is coherent at $u_{i}$ and $-1$ if $W$ is incoherent; that includes
$u_{l}=u_{0}$ with edges $e_{l}$ and $e_{l+1}=e_{1}$. Thus,
$\iota(u_{i})=-\tau(u_{i},e_{i})\tau(u_{i},e_{i+1})$. Then the product of all
vertex signs of $W$ is

$\prod_{i=1}^{l}\iota(u_{i})=\prod_{i=1}^{l}\big{[}-\tau(u_{i},e_{i})\tau(u_{i},e_{i+1})\big{]}=(-1)^{l}\prod_{i=1}^{l}\tau(u_{i-1})\prod_{i=1}^{l}\tau(u_{i},e_{i})=\sigma(W).$

In other words:

######  Lemma 3.8.

The number of incoherent vertices in a closed walk $W$ in a bidirected graph
is even if and only if $W$ is positive.

Now we define poise of a closed walk $W$. We assign the edges to two sets, $A$
and $B$. We put $e_{1}$ into set $A$ and for each edge $e_{i}$ in one of the
sets, we put $e_{i+1}$ into the same set if $u_{i}$ is coherent and the
opposite set if it is incoherent. This gives a well-defined bipartition of the
edges of $W$ into sets $A$ and $B$ if and only if both the number of changes
of set, which equals the number of incoherent vertices, is even, i.e., $W$ is
positive, and also a repeated edge is assigned to the same set in every
appearance in $W$. We define $W$ to be _poised_ if the bipartition is well
defined and $|A|=|B|$.

We also define poise for a walk $W$ from a half edge to a half edge (which may
be the same edge). We put the initial half edge into $A$ and apply the same
rule as before. We get a well-defined bipartition of the edges of $W$ if and
only if a repeated edge is assigned to the same set at every appearance. We
say $W$ is _poised_ if the bipartition is well defined and $|A|=|B|$.

Now we can state the theorem about edge points. A sign circuit is poised if
its circuit walk is poised; since a sign circuit walk is either positive or
begins and ends at a half edge, this definition is independent of the choice
of circuit walk.

######  Theorem 3.9 (Dimension of Bidirected Edge Points).

In a bidirected graph $\vec{\Sigma}$ let $S\subseteq E$. The affine dimension
of the point set $\mathbf{x}(S)$ in $\mathbb{A}^{d}(\mathbb{R})$ is
$n-b_{\Sigma}(S)$ if every sign circuit in $S$ is poised and
$n-b_{\Sigma}(S)+1$ if not.

###### Proof.

An affine point $\mathbf{a}\in\mathbb{A}^{n}(\mathbb{R})$ corresponds to the
vector $\mathbf{b}_{0}+\mathbf{a}$ in $\mathbb{R}^{1+n}$. It is well known
that the affine dimension of a set of affine points equals the linear
dimension of the corresponding vectors. Thus, we are assigning gain $1$ to
every edge of $\vec{\Sigma}$, forming a gain signed graph $\Upsilon$. A sign
circuit with these gains is neutral if and only if it is poised. Theorem 4.2
then gives the rank of an edge set:
$\operatorname{rk}_{\Upsilon}(S):=n-b_{\Sigma}(S)+\delta_{\Upsilon}(S)$, where
$\delta_{\Upsilon}(S)=0$ if every sign circuit in $S$ is poised, and otherwise
is $1$. As we observe immediately after Theorem 4.2, the rank of $S$ equals
the dimension of $\mathbf{z}(S)$, which equals the affine dimension of
$\mathbf{x}(S)$ by the relation between affine points and their corresponding
vectors. ∎

######  Example 3.10 (Arc Adjacency Polytope [11, 6]).

As a special case of the previous example, suppose all edges in $\Sigma$ are
positive; i.e., $\vec{\Sigma}$ is a directed graph $\vec{\Gamma}$. The sign
circuits are the circles. A circle is poised if and only if it has equal
numbers of directed edges in each direction. The convex hull of the set
$\mathbf{x}(E)$ of affine points of a symmetric digraph (where for every arc
there is also the opposite arc) has been called its symmetric edge polytope
[10] and also its adjacency polytope (e.g., [6]); as in [6] we generalize this
to the _arc polytope_ of any directed graph (an arc being a directed edge).
Let $c(\Gamma)$ denote the number of connected components of $\vec{\Gamma}$.

######  Corollary 3.11 (Dimension of Arc Polytope).

For a directed graph $\vec{\Gamma}$, the affine dimension of its arc polytope
is $n-c(\Gamma)$ if every circle in $\vec{\Gamma}$ is poised and
$n-c(\Gamma)+1$ if not.

######  Example 3.12 (Double Arc Adjacency Polytope [7]).

There is a second polytope that has been called the adjacency polytope. Again
suppose we have a directed graph $\vec{\Gamma}=(V,E)$. We represent an arc
$(v_{i},v_{j})$ by the point
$(\mathbf{b}_{i},\mathbf{b}_{j})\in\mathbb{A}^{2n}(\mathbb{R})$, thus in twice
the dimension of the adjacency polytope; we call the convex hull of these
_double arc points_ the _double adjacency polytope_ of $\vec{\Gamma}$. Chen
and Mehta [7] introduced this polytope for the special case of a symmetric
digraph (which they regarded as an undirected graph). Note that if we
represent $(v_{i},v_{j})$ by
$f(v_{i},v_{j})=(-\mathbf{b}_{i},\mathbf{b}_{j})$, nothing essential changes
in the structure of the set $f(E)$: dimension and convexity remain the same.
We use $f$ as the representation for the rest of this example.

We determine the dimension of a set of double arc points by a new digraph
$\tilde{\Gamma}$, which is a vertex doubling of $\vec{\Gamma}$. The vertex set
is $\tilde{V}=V_{+}\cup V_{-}$, where $V_{+}$ and $V_{-}$ are disjoint copies
of $V$ whose vertices corresponding to $v\in V$ are respectively $v_{+}$ and
$v_{-}$, and for each arc $(v_{i},v_{j})$ we create an arc $(v_{i-},v_{j+})$
in $\tilde{\Gamma}$. Note that every circle in $\tilde{\Gamma}$ is poised
because its vertices alternate between $V_{+}$ and $V_{-}$, so its arcs
reverse direction at every vertex. Therefore, Corollary 3.11 applies and we
have the following description of dimension:

######  Corollary 3.13 (Dimension of Double Arc Polytope).

The affine dimension of the double arc polytope of a digraph $\vec{\Gamma}$
equals $2n-c(\tilde{\Gamma})$, which is also its linear dimension.

###### Completion of Proof.

The linear dimension is the same as the affine dimension because it equals the
rank of the incidence matrix of $\vec{\Gamma}$, which is
$2n-c(\tilde{\Gamma})$. ∎

Of course, this corollary can be applied to any subset of the arcs.

A special case of particular interest is that in which $\vec{\Gamma}$ is
symmetric and has all loops $(v_{i},v_{i})$. Then
$c(\tilde{\Gamma})=c(\Gamma)$, which is a nice simplification.

##  4\. Matroid: rank

We want a combinatorial description of the matroid obtained by representing
each edge of $\Upsilon$ by a vector as in Section 3. The problem is to
describe the linear dependence matroid of the vectors without reference to
linear algebra. Thus, we want combinatorial formulas for the rank function,
the circuits, the independent sets and bases, the closed sets (or flats), and
the coatoms of the lattice of flats, whose complements are the matroid
cocircuits. We call this the _matroid of $\Upsilon$_ and denote it by
$\mathbf{M}(\Upsilon)$. We base the matroid on its rank function.

The matroid has a natural one-point extension, which we denote by
$\mathbf{M}_{\infty}(\Upsilon)=\mathbf{M}(\Upsilon)\cup\\{e_{\infty}\\}$, to
the extra point. Whereas the ground set of $\mathbf{M}(\Upsilon)$ is
$E=E(\Upsilon)$, that of $\mathbf{M}_{\infty}(\Upsilon)$ is
$E_{\infty}=E\cup\\{e_{\infty}\\}$. We call $\mathbf{M}_{\infty}(\Upsilon)$
the _extended matroid_ of $\Upsilon$. It is a one-point coextension of the
frame matroid $\mathbf{F}(\Sigma)$; that is,
$\mathbf{M}_{\infty}(\Upsilon)/e_{\infty}=\mathbf{F}(\Sigma)$. (One purpose of
the extra point is to implement this property of $\mathbf{M}(\Upsilon)$.) A
subset of $E_{\infty}$ is defined to be hyperfrustrated if it contains
$e_{\infty}$; if not, it is a subset of $E$ whose treatment is as we have
already described. Hence, in the matroid the extra point behaves like a non-
neutral loose edge (and we treat it as such in proofs), although its
significance is different in that it implements the coextension of
$\mathbf{F}(\Sigma)$.

The purpose of the extra point will become clearer in Section 5. For the
present we only mention that, if all edges are positive, so that $\Upsilon$ is
a gain graph $\Phi=(\Gamma,\varphi)$, then $\mathbf{M}(\Upsilon)$ is the lift
matroid $\mathbf{L}(\Phi)$ and $\mathbf{M}_{\infty}(\Upsilon)$ is the extended
lift matroid $\mathbf{L}_{\infty}(\Phi)$ (formerly written $\mathbf{L}_{0}$)
of [26, Section 3].

######  Definition 4.1.

The _rank_ of an extended edge set $S\subseteq E_{\infty}$ is

$\operatorname{rk}_{\Upsilon}(S):=n-b_{\Sigma}(S)+\delta_{\Upsilon}(S),$

where

$\delta_{\Upsilon}(S):=\begin{cases}0&\text{ if $S$ is hyperbalanced,}\\\
1&\text{ if $S$ is hyperfrustrated.}\end{cases}$

We define $\operatorname{rk}(\Upsilon)=\operatorname{rk}_{\Upsilon}(E)$.

For an extended edge set $S$, $\mathbf{z}(S)$ denotes the multiset of vectors
representing $S$, i.e., $\mathbf{z}(S)=\\{\mathbf{z}(e):e\in S\\}$. The
dimension of an arbitrary (multi)set of vectors means the dimension of its
linear span.

######  Theorem 4.2.

The function $\operatorname{rk}_{\Upsilon}$ defines a matroid on ground set
$E_{\infty}$ such that

$\operatorname{rk}_{\Upsilon}(S)=\dim\mathbf{z}(S)$

for every edge set $S$.

That matroid on ground set $E$ is the matroid $\mathbf{M}(\Upsilon)$, and its
extension to $E_{\infty}$ is the extended matroid
$\mathbf{M}_{\infty}(\Upsilon)$. Thus, the vector model, i.e., the function
$\mathbf{z}:E\to\mathbf{K}^{1+n}$, is a vector representation of this matroid.

###### Proof.

The first step is to dispose of the extra point. Observe that
$\mathbf{z}(e_{\infty})$ is a nonzero scalar multiple of $\mathbf{z}(e)$ for
any non-neutral loose edge $e$. Therefore, for the matroid we can treat
$e_{\infty}$ as another non-neutral loose edge.

We prove that $\dim\mathbf{z}(S)$ satisfies Equation (4.1). Then the matroid
exists, because $\dim$ is a matroid rank function, and it is represented by
$\mathbf{z}$.

Because projection cannot increase dimension, for every edge set $S$,

(4.1)
$\dim\mathbf{z}(S)\geq\dim\pi_{0}\mathbf{z}(S)=\operatorname{rk}_{\Sigma}(S)=n-b_{\Sigma}(S)$

by [22, Theorems 8B.1 and 5.1].

_Case 1. $S$ is hyperbalanced._

By the definition of hyperbalance, every sign circuit has gain sum 0. Thus, by
Corollary 3.5 for every sign circuit $C\subseteq S$, $\mathbf{z}(C)$ is a
circuit in the vector model. It follows that $\mathbf{z}(R)$ is dependent for
every subset $R\subseteq S$ that is dependent in the frame matroid
$\mathbf{F}(\Sigma)$. That and (4.1) imply that the vector matroid of
$\mathbf{z}(S)$ is the same as the frame matroid $\mathbf{F}(\Sigma|S)$, so
$\dim\mathbf{z}(S)=\dim\pi_{0}\mathbf{z}(S)=\operatorname{rk}_{\Sigma}(S)=n-b_{\Sigma}(S)$.

_Case 2. $S$ is not hyperbalanced._ By definition, there exists a sign circuit
$C\subseteq S$ with gain sum nonzero. By Corollary 3.5, $\mathbf{z}(C)$ is
independent.

Suppose first that $C=\\{e\\}$, so $e$ is a positive loop or a loose edge.
Then $\mathbf{z}(e)=\varphi(e)\mathbf{b}_{0}\neq\mathbf{0}$. Let $B$ be a
basis for $S$ in $\mathbf{F}(\Sigma)$. No nontrivial linear combination of the
vectors in $\pi_{0}\mathbf{z}(B)$ equals $\mathbf{0}$, so there is no way to
express $\mathbf{z}(e)$ as a linear combination of $\mathbf{z}(B)$. It follows
that
$\dim\mathbf{z}(B\cup\\{e\\})=\dim\pi_{0}\mathbf{z}(B)+1=\operatorname{rk}_{\Sigma}(B)+1=n-b_{\Sigma}(S)+1$.

Now consider the general case, $|C|>1$. Let $e\in C$ and $T=C\smallsetminus
e$. Extend $T$ to a basis $B$ of $\mathbf{F}(\Sigma|S)$; thus,
$\pi_{0}\mathbf{z}(B)$ is independent so $\mathbf{z}(B)$ is independent. We
prove $\mathbf{z}(B\cup\\{e\\})$ is independent.

Suppose by way of contradiction that it is dependent. Then there exists a
unique circuit $\mathbf{z}(A\cup\\{e\\})$ in $\mathbf{z}(B\cup\\{e\\})$. The
projection $\pi_{0}\mathbf{z}(A\cup\\{e\\})$ is therefore dependent, which
means that $A\cup\\{e\\}$ is dependent in $\mathbf{F}(\Sigma)$. It follows
that $A\cup\\{e\\}$ contains the unique sign circuit in $B\cup\\{e\\}$, i.e.,
$C\subseteq A\cup\\{e\\}$. But equality cannot hold because $\mathbf{z}(C)$ is
independent; hence, $A\subset T$.

Because $\mathbf{z}(A\cup\\{e\\})$ is a minimal dependent set, there is a
unique linear combination $\mathbf{z}(e)=\sum_{f\in
A}\alpha_{f}\mathbf{z}(f)$, where all $\alpha_{f}\neq 0$. Because $C$ is a
sign circuit, there is a unique linear combination
$\pi_{0}\mathbf{z}(e)=\sum_{g\in T}\beta_{g}\pi_{0}\mathbf{z}(g)$, where all
$\beta_{g}\neq 0$. So, $\sum_{f\in
A}\alpha_{f}\pi_{0}\mathbf{z}(f)=\pi_{0}\mathbf{z}(e)=\sum_{g\in
T}\beta_{g}\pi_{0}\mathbf{z}(g)$. Now, $A,T\subseteq B$ and
$\pi_{0}\mathbf{z}(B)$ is an independent set in $\mathbf{K}^{n}$; consequently
$A=T$ and all $\alpha_{f}=\beta_{f}$. However, we saw that $A\supset T$. This
contradiction proves that $\mathbf{z}(B\cup\\{e\\})$ is independent, and since
$|B|=\operatorname{rk}_{\Sigma}(S)$, we conclude that
$\dim\mathbf{z}(B\cup\\{e\\})=\operatorname{rk}_{s}(S)+1=n-b_{\Sigma}(S)+1$.

Clearly,
$\dim\mathbf{z}(S)\geq\dim\mathbf{z}(B\cup\\{e\\})=n-b_{\Sigma}(S)+1$. On the
other hand,
$\dim\mathbf{z}(S)\leq\dim\pi_{0}\mathbf{z}(S)+1=\operatorname{rk}_{\Sigma}(S)+1=\operatorname{rk}_{\Sigma}(B)+1=n-b_{\Sigma}(S)+1$.
That proves the formula for $\dim\mathbf{z}(S)$ in Case 2. ∎

##  5\. Matroid: closure and flats

Our next mission is to characterize the closed sets of a matroid of a gain
signed graph. Recall that for a set $S$ of elements of a matroid, the closure
of $S$ is
$\\{e:\operatorname{rk}_{\Upsilon}(S\cup\\{e\\})=\operatorname{rk}_{\Upsilon}(S)\\}$.
Equivalently, the closure of $S$ is $S\cup\\{e:S\cup\\{e\\}\mbox{ contains a
hypercircuit containing $e$}\\}$, but we do not use this characterization
since we have not yet found the hypercircuits.

In the matroids $\mathbf{M}(\Upsilon)$ and $\mathbf{M}_{\infty}(\Upsilon)$ the
closure of $S$ is called the hyperclosure, written
$\operatorname{clos}_{\Upsilon}(S)$ in $\mathbf{M}(\Upsilon)$ and
$\operatorname{clos}_{\infty}$ in $\mathbf{M}_{\infty}(\Upsilon)$. To define
it we use the _gain balance-closure_ operator in $\Upsilon$,
$\operatorname{bcl}_{\Upsilon}$, defined by

$\operatorname{bcl}_{\Upsilon}(S):=S\cup\\{e\notin S:\exists\ \text{a neutral
sign circuit $C$ such that }e\in C\subseteq S\cup\\{e\\}\\}.$

Note that
$\operatorname{bcl}_{\Upsilon}(S)\subseteq\operatorname{clos}_{\Sigma}(S)$.
Also, $\operatorname{bcl}_{\Upsilon}(S)\supseteq E^{00}$ since a loose edge is
a sign circuit. It is easy to prove using a gain potential for $S$ and Theorem
2.13 that:

######  Lemma 5.1.

Let $S\subseteq E$. If $S$ is hyperbalanced, then
$\operatorname{bcl}_{\Upsilon}(S)$ is also hyperbalanced.

######  Theorem 5.2.

Let $S\subseteq E_{\infty}$. If $S$ is hyperbalanced,

(5.1) $\displaystyle\operatorname{clos}_{\Upsilon}(S),$
$\displaystyle=\operatorname{bcl}_{\Upsilon}(S)$
$\displaystyle=[E(\theta){:}U_{\Sigma}(S)]\cup[E(\theta,\zeta){:}\pi_{\text{\rm
b}}(S)]\cup E^{00}.$

where $\zeta$ is a sign potential for $S{:}U_{\Sigma}(S)^{c}$ and $-\theta$ is
a gain potential for $S$. The closure is hyperbalanced and is the same in
$\mathbf{M}(\Upsilon)$ and $\mathbf{M}_{\infty}(\Upsilon)$.

If $S$ is hyperfrustrated, then in $\mathbf{M}(\Upsilon)$

(5.2) $\displaystyle\operatorname{clos}_{\Upsilon}(S)$
$\displaystyle=\operatorname{clos}_{\Sigma}(S)$
$\displaystyle=[E{:}U_{\Sigma}(S)]\cup[E(\zeta){:}\pi_{\text{\rm b}}(S)]\cup
E^{0},$

where $\zeta$ is a sign switcher for $S{:}U_{\Sigma}(S)^{c}$. The closure
$\operatorname{clos}_{\infty}(S)$ in $\mathbf{M}_{\infty}(\Upsilon)$ is the
same with the addition of $e_{\infty}$.

Note that if $X\in\pi_{\text{\rm b}}(S)$ and $E{:}X$ is sign balanced, then
$E(\theta,\zeta){:}X=E(\theta){:}X$ in the first part and $E(\zeta){:}X=E{:}X$
in the second part so $\zeta$ is not necessary for that component of $S$.

###### Proof.

Recall that we can treat $e_{\infty}$ as a non-neutral loose edge, so it need
not be considered separately.

Let us assume $S$ is hyperfrustrated, so that
$\operatorname{rk}_{\Upsilon}(S)=n-b_{\Sigma}(S)+1$. Let $\zeta$ be a sign
switcher that switches $S{:}U_{\Sigma}(S)^{c}$ to all positive. Write
$A:=[E{:}U_{\Sigma}(S)]\cup[E(\zeta){:}\pi_{\text{\rm b}}(S)]\cup E^{0}$. It
is clear that $S\subseteq A$; thus
$\operatorname{clos}_{\Upsilon}(S)\subseteq\operatorname{clos}_{\Upsilon}(A)$
and $\operatorname{rk}_{\Upsilon}(S)\leq\operatorname{rk}_{\Upsilon}(A)$. We
want to show that $A$ is closed and has the same rank as $S$.

For the rank, since $A$ is hyperfrustrated,
$\operatorname{rk}_{\Upsilon}(A)=n-b_{\Sigma}(A)+1$, so we should prove
$b_{\Sigma}(A)=b_{\Sigma}(S)$. Consider $B\in\pi_{\text{\rm b}}(S)$. Then
$E(\zeta){:}B$ is sign balanced, and it is connected because $S{:}B$ is
connected. Therefore, $B$ is contained in a block of $\pi_{\text{\rm b}}(A)$.
But no edge of $A$ connects two different sign-balanced components of $S$, so
$B\in\pi_{\text{\rm b}}(A)$. This proves $b_{\Sigma}(A)\geq b_{\Sigma}(S)$, so
that $\operatorname{rk}_{\Upsilon}(A)\leq\operatorname{rk}_{\Upsilon}(S)$.
That implies equality, so $A\subseteq\operatorname{clos}_{\Upsilon}(S)$ and
also $\pi_{\text{\rm b}}(A)=\pi_{\text{\rm b}}(S)$.

Now we prove that an edge $e\notin A$ is also not in
$\operatorname{clos}_{\Upsilon}(S)$. It is sufficient to prove that
$b_{\Sigma}(A\cup\\{e\\})<b_{\Sigma}(A)$, since both $A$ and $A\cup\\{e\\}$
are hyperfrustrated. If $e$ joins a sign-balanced component of $A$ to another
component, it reduces $b_{\Sigma}$. If it joins vertices in a sign-balanced
component $A{:}B$ or is a half edge in $E{:}B$, then $A{:}B\supseteq
E(\zeta){:}B$ $\implies$ $e\notin E(\zeta)$ $\implies$ $(A\cup\\{e\\}){:}B$ is
sign-unbalanced; then adding $e$ also reduces $b_{\Sigma}$. These are the only
possibilities, because $E{:}U_{\Sigma}(S)\cup E^{0}\subseteq A$. That
completes the proof that $A=\operatorname{clos}_{\Upsilon}(S)$.

If $S$ is hyperbalanced, then we may restrict attention to
$\Upsilon|E(\theta)$ for some gain potential $-\theta$ and either apply the
same reasoning as in the previous case or simply appeal to Lemma 2.3. The
closure is hyperbalanced because it is contained in $E(\theta)$. ∎

######  Theorem 5.3.

The closed sets of $\mathbf{M}(\Upsilon)$ are those of the forms

(5.3) $[E{:}U]\cup[E(\zeta){:}\pi]\cup E^{0},$

where $U\subseteq V$, $\pi$ partitions $U^{c}$, and $\zeta$ is a sign function
on $U^{c}$, and

(5.4) $[E(\theta){:}U]\cup[E(\theta,\zeta){:}\pi]\cup E^{00},$

where $\theta$ is a gain switcher. A closed set of type (5.4) is always
hyperbalanced, and every hyperbalanced closed set has the form (5.4).

The closed sets of $\mathbf{M}_{\infty}(\Upsilon)$ are the same, if the set is
hyperbalanced, but the same with the addition of $e_{\infty}$ if the set is
hyperfrustrated.

The first kind of closed set, (5.3), is the same as the second, hence
hyperbalanced and redundant, if $\Upsilon$ is hyperbalanced, but it is usually
not hyperbalanced if $\Upsilon$ is not hyperbalanced. It will be hyperbalanced
if and only if all loose edges are neutral and $E{:}U$ is hyperbalanced.

Theorems 5.2 and 5.3 demonstrate one function of the extra point $e_{\infty}$:
it expresses hyperbalance in purely matroidal terms because an edge set
$S\subseteq E$ is hyperbalanced if and only if its closure in
$\mathbf{M}_{\infty}(\Upsilon)$ does not contain $e_{\infty}$.

###### Proof.

Theorem 5.2 implies that every closed set has one of these two forms. We prove
the converse.

Let $A$ be the set in (5.3). The partition $\pi(A)$ refines $\pi\cup\\{U\\}$.
Thus, if $B_{A}\in\pi(A)$ is contained in some $B\in\pi$, we have
$E(\zeta){:}B_{A}\subseteq E(\zeta){:}B\subseteq A$. If $B_{A}\subseteq U$,
then $E{:}B_{A}\subseteq E{:}U\subseteq A$. The conclusion is that
$\operatorname{clos}_{\Upsilon}(A)=[E{:}U_{\Sigma}(A)]\cup[E(\zeta){:}\pi(A)]\cup
E^{0}\subseteq A$, from which equality is obvious.

In type (5.4), we can restrict attention to $E(\theta)$, which is
hyperbalanced, so its matroid is that of the signed graph $\Sigma(\theta)$.
Then $A$ is closed by Lemma 2.3. An alternative is to repeat the proof for
type (5.3) with $E(\theta)$ in place of $E$ and $E^{00}$ in place of $E^{0}$.
∎

There is redundancy in Theorem 5.3, inasmuch as a flat $A$ may be
representable with different choices of $U$, $\pi$, $\zeta$, and $\theta$. If
$E{:}U$ has components that are sign balanced, and in (5.4) hyperbalanced,
then $U$ can be made smaller and $\pi$ larger. The smallest possible set $U$
is $U_{\Sigma}(A)$. Once $U$ is chosen, the most refined partition is
$\pi(A{:}U^{c})$, but sometimes $\pi$ may be chosen to combine components of
$A{:}U^{c}$. Then given $U$ and $\pi$, the switching function(s) $\zeta$ and
$\theta$ are determined up to sign (for $\zeta$) and (for $\theta$)
translation on each component of $A{:}U^{c}$ if $U=U_{\Sigma}(A)$ and
$\pi=\pi_{\text{\rm b}}(A)$ but not necessarily with other choices. This
versatility in Theorem 5.3 is sometimes something to be careful about.

The flats of $\mathbf{M}(\Upsilon)$ form a geometric lattice, which we denote
by $\operatorname{Lat}\Upsilon$. There is also the semilattice of
hyperbalanced flats, which we call
$\operatorname{\operatorname{Lat}^{\text{\rm b}}}\Upsilon$; it is a geometric
semilattice that corresponds to the intersection semilattice of the hyperplane
representation of $\Upsilon$, so it is of particular interest; see Section 10.

##  6\. Matroid: coatoms and cocircuits

The coatoms of $\operatorname{Lat}\Upsilon$, the lattice of closed sets, are
of interest, but even more so their complements, the cocircuits of
$\mathbf{M}(\Upsilon)$, and also the hyperbalanced coatoms, which are the
maximal elements of $\operatorname{\operatorname{Lat}^{\text{\rm b}}}\Upsilon$
when $\Upsilon$ is not hyperbalanced. The coatoms and cocircuits are quite
different depending on whether $\Upsilon$ is hyperbalanced or not. On the
whole it is easier to describe the cocircuits (which we may call
hypercocircuits to distinguish them from the sign cocircuits in
$\mathbf{F}(\Sigma)$).

We begin with a pair of lemmas.

######  Lemma 6.1.

Every basis of $\mathbf{F}(\Sigma)$ is hyperbalanced.

###### Proof.

A basis cannot be hyperfrustrated because it does not contain any sign
circuits. ∎

######  Lemma 6.2.

Suppose $\Upsilon$ is hyperfrustrated. Then every maximal hyperbalanced edge
set $A$ is a coatom with $b_{\Sigma}(A)=b_{\Sigma}(E)$ and
$\operatorname{rk}_{\Upsilon}A=\operatorname{rk}(\Upsilon)-1=n-b_{\Sigma}(E)$.

###### Proof.

A maximal hyperbalanced edge set $A$ is closed in $\mathbf{M}(\Upsilon)$,
either by Theorem 5.2, or simply because adding an edge to it makes it
hyperfrustrated, which increases its rank.

By maximality $A$ is connected and spanning in each component of $\Upsilon$.
We use (5.2) to prove that, for any edge $e\notin A$,
$\operatorname{clos}_{\Upsilon}(A\cup e)=E$, by proving that any other edge
$f\notin A\cup e$ is in $\operatorname{clos}_{\Upsilon}(A\cup e)$. If $f\in
E^{0}$, then $f\in\operatorname{clos}_{\Upsilon}(A\cup e)$. Otherwise, $f$ is
in a component $\Upsilon{:}X$. If $(A\cup e){:}X$ is sign unbalanced, then
$X\subseteq U_{\Sigma}(A\cup e)$ so $f\in E{:}U_{\Sigma}(A\cup
e)\subseteq\operatorname{clos}_{\Upsilon}(A\cup e)$. If $(A\cup e){:}X$ is
sign balanced, we prove that $E{:}X$ is sign balanced. By maximality of $A$,
$(A\cup f){:}X$ is hyperfrustrated for $f\in(E\smallsetminus A){:}X$, so $f$
belongs to a non-neutral sign circuit in $A\cup f$, which can only be a
positive circle because $A{:}X$ contains no negative figure. Therefore,
$f\in\operatorname{bcl}_{\Sigma}(A)$. Since $f$ was any edge in
$(E\smallsetminus A){:}X$, it follows that $E{:}X$ is sign balanced.
Therefore, $X\in\pi_{\text{\rm b}}(A\cup e)$ and $E{:}X\subseteq
E{:}\pi_{\text{\rm b}}(A\cup e)\subseteq\operatorname{clos}_{\Upsilon}(A\cup
e)$. ∎

A _hyperbalancing set_ for $\Upsilon$ is an edge set whose deletion results in
hyperbalance.

Note that, since $e_{\infty}$ can be treated as a non-neutral loose edge, the
extended matroid $\mathbf{M}_{\infty}(\Upsilon)$ falls under the
hyperfrustrated case, part (II) of the following theorem.

######  Theorem 6.3.

Let $\Upsilon$ be a gain signed graph with signed graph
$\Sigma=(\Gamma,\sigma)$. The coatoms and cocircuits of $\mathbf{M}(\Upsilon)$
are of the following types.

  1. I.

If $\Upsilon$ is hyperbalanced, they are the coatoms and cocircuits of
$\mathbf{F}(\Sigma)$.

  2. II.

If $\Upsilon$ is hyperfrustrated, it has both hyperbalanced and
hyperfrustrated coatoms.

    1. (A)

For a hyperbalanced set $A$ the following properties are equivalent:

      1. (i)

$A$ is a coatom.

      2. (ii)

$A$ is a maximal hyperbalanced edge set.

      3. (iii)

$A$ is the closure $\operatorname{clos}_{\Upsilon}(F)$ of a basis $F$ of
$\mathbf{F}(\Sigma)$.

      4. (iv)

$A$ is the balance-closure $\operatorname{bcl}_{\Upsilon}(F)$ of a basis $F$
of $\mathbf{F}(\Sigma)$.

The corresponding hypercocircuits are the minimal hyperbalancing sets.

    2. (B)

The hyperfrustrated coatoms are the coatoms of $\mathbf{F}(\Sigma)$ that are
hyperfrustrated. The corresponding hypercocircuits are:

      1. (i)

If $\Gamma{:}X$ is a component such that $\Upsilon\smallsetminus X$ is
hyperfrustrated (this includes the case where $\Upsilon\smallsetminus X$
contains a non-neutral loose edge), any cocircuit of $\mathbf{F}(\Sigma{:}X)$.

      2. (ii)

If $\Gamma{:}X$ is a component such that $\Upsilon\smallsetminus X$ is
hyperbalanced,

        1. (a)

a bond $D$ of $\Gamma{:}X$ such that $[\Upsilon{:}X]\smallsetminus D$ is
hyperfrustrated, if $\Sigma{:}X$ is sign balanced;

        2. (b)

either a minimal deletion set $D$ of $\Sigma{:}X$ such that
$[\Upsilon{:}X]\smallsetminus D$ is hyperfrustrated, or a cut $D$ of
$\Gamma{:}X$ of the types in Theorem 2.3(D2)–(D4) such that
$[\Upsilon{:}X]\smallsetminus D$ is hyperfrustrated, if $\Sigma{:}X$ is sign
unbalanced.

###### Proof.

(I) If $\Upsilon$ is hyperbalanced, its matroid $\mathbf{M}(\Upsilon)$ is the
same as $\mathbf{F}(\Sigma)$; see Theorem 2.3.

(II) Now consider hyperfrustrated $\Upsilon$.

In part (A), it is clear that (i) implies (ii), and (ii) implies (i) by Lemma
6.2.

Parts (iii) and (iv) are equivalent by Theorem 5.2 and Lemma 6.1.

Assume (ii); then
$\operatorname{rk}_{\Sigma}(A)=\operatorname{rk}_{\Upsilon}(E)-1$ (by Lemma
6.2) $=\operatorname{rk}_{\Sigma}(E)$ because $\Upsilon$ is hyperfrustrated.
Now we prove (iii) implies (i). Since $F$ is hyperbalanced by Lemma 6.1,
$\operatorname{rk}_{\Upsilon}(F)=\operatorname{rk}_{\Sigma}(F)=\operatorname{rk}_{\Sigma}(E)=\operatorname{rk}_{\Upsilon}(E)-1$,
which implies that $A=\operatorname{clos}_{\Upsilon}(F)$ is a coatom. By (5.1)
and Lemma 5.1, $A$ is hyperbalanced.

For part (B), suppose $A$ is a hyperfrustrated coatom of
$\mathbf{M}(\Upsilon)$. Then
$\operatorname{rk}_{\Upsilon}A=\operatorname{rk}_{\Upsilon}E-1$, which means
$n-b_{\Sigma}(A)+1=n-b_{\Sigma}(E)$, i.e., $b_{\Sigma}(A)=b_{\Sigma}(E)+1$.
This means $\operatorname{rk}_{\Sigma}A=\operatorname{rk}_{\Sigma}E-1$, so $A$
is contained in a coatom $A^{\prime}$ of $\mathbf{F}(\Sigma)$. But
$A^{\prime}$ is therefore hyperfrustrated and its rank is
$\operatorname{rk}_{\Upsilon}A^{\prime}=\operatorname{rk}_{\Upsilon}E-1$; by
maximality of a coatom, $A=A^{\prime}$.

In this case, a hypercocircuit is a sign cocircuit $D$; they are described in
Theorem 2.3. Each $D$ is contained in a single component $\Upsilon{:}X$. If
$\Upsilon\smallsetminus X$ is hyperfrustrated, then any sign cocircuit is a
hypercocircuit because deleting it does not eliminate hyperbalance. If
$\Upsilon\smallsetminus X$ is hyperbalanced, the sign cocircuit $D$ must be
restricted to those whose deletion does not eliminate hyperbalance; hence by
Theorem 2.3 we get the classification in (I)(B)(ii). ∎

The hyperbalanced coatoms of a hyperfrustrated $\Upsilon$, being the maximal
elements of $\operatorname{\operatorname{Lat}^{\text{\rm b}}}\Upsilon$, are of
prime importance for geometry, as we shall see in Section 10.

##  7\. Matroid: independence and bases

Knowing the rank function of the matroid $\mathbf{M}(\Upsilon)$ we can
determine the independent sets and bases. They are complicated but they can be
fully classified using the matroid invariant _nullity_ , defined as
$\operatorname{nul}_{\Upsilon}S:=|S|-\operatorname{rk}_{\Upsilon}S$ for a set
$S$. In particular, a set is independent if and only if its nullity is 0. For
a gain signed graph nullity has a nice expression in terms of the cyclomatic
number $\xi$ and the quantity $u_{\Sigma}(S)$, the number of sign-unbalanced
components of $S$. (Recall that this does not include loose edges;
$u_{\Sigma}(S)=0$ if $S$ has only loose edges.)

######  Lemma 7.1.

The nullity of an edge set $S$ in $\mathbf{M}(\Upsilon)$ is

$\displaystyle\operatorname{nul}_{\Upsilon}S$
$\displaystyle=\begin{cases}\xi(S)+b_{\Sigma}(S)-c(S)&\text{if $S$ is
hyperbalanced,}\\\ \xi(S)+b_{\Sigma}(S)-c(S)-1&\text{if $S$ is
hyperfrustrated}\end{cases}$
$\displaystyle=\begin{cases}\xi(S)-u_{\Sigma}(S)&\text{if $S$ is
hyperbalanced,}\\\ \xi(S)-u_{\Sigma}(S)-1&\text{if $S$ is
hyperfrustrated}.\end{cases}$

###### Proof.

The formula follows from the definition of nullity, the rank formula (4.1),
and the definition of the cyclomatic number. ∎

The second version of the nullity formula shows that isolated vertices can be
ignored in computing nullity.

We prepare for independence with a lemma.

######  Lemma 7.2.

An edge set that contains two hyperfrustrated edge components is dependent.

###### Proof.

Say $S_{1}$ and $S_{2}$ are hyperfrustrated edge components of $S$. Then

$\operatorname{nul}_{\Upsilon}S=\xi(S)-u_{\Sigma}(S)-1\geq[\xi(S_{1})-u_{\Sigma}(S_{1})]+[\xi(S_{2})-u_{\Sigma}(S_{2})]-1$

since $\xi$ and $u_{\Sigma}$ are additive on components. In order to be
hyperfrustrated a component $S_{i}$ must contain a positive circle, a handcuff
with two negative figures, or a loose edge. In either case,
$\xi(S_{i})-u_{\Sigma}(S_{i})>0$. It follows that
$\operatorname{nul}_{\Upsilon}S>0$. ∎

A _unicycle_ is a circle or a half edge that may have trees attached.

######  Theorem 7.3.

The independent sets of $\mathbf{M}(\Upsilon)$ are the following types of edge
set, considered as spanning subgraphs.

  1. I.

Hyperbalanced: Every component is a tree or a sign-unbalanced unicycle, and it
has no loose edges.

  2. II.

Hyperfrustrated: Every component is a tree or a sign-unbalanced unicycle,
except that there may be one component $S_{0}$ that is either a sign-balanced
unicycle, a loose edge, or a sign-unbalanced theta graph or a handcuff with at
least one negative figure, possibly with attached trees, and in each case the
unique sign circuit in $S_{0}$ is non-neutral.

Figure 7.1. Independent sets. There may be any number of hyperbalanced
components. There may be any number of trees pendant from a component, not
shown except in the top row. Other than that, the figure shows all types of
independent set. Circle signs and gains ($*$ means the gain is not $0$) are
indicated. Top row: Possible hyperbalanced components: two trees and two
neutral negative unicycles. Lower rows: The possible hyperfrustrated component
$S_{0}$. Second row: sign balanced. Bottom rows: sign unbalanced.

###### Proof.

To find independent sets we assume $S$ is independent and examine how
$\operatorname{nul}_{\Upsilon}S$ can equal 0. The equation we have to solve is
$\xi(S)-u_{\Sigma}(S)=0$ or $1$ depending on whether $S$ is or is not
hyperbalanced. By independence, any positive circle or loose edge must be non-
neutral.

In the hyperbalanced case $\xi(S)=u_{\Sigma}(S)$ and $S$ must be independent
in $\mathbf{F}(\Sigma)$. Therefore, there can be no positive circles or loose
edges in $S$. Every sign-balanced component must be acyclic. Each sign-
unbalanced component must have no balanced circles and exactly one negative
figure, so it is a unicycle. This proves part (I).

In the hyperfrustrated case the components are the same except that, because
$\xi(S)=u_{\Sigma}(S)+1$, there is one special component $S_{0}$ that contains
a sign circuit, which must be non-neutral since $S$ is independent; thus
$S_{0}$ is hyperfrustrated. (By Lemma 7.2 there cannot be two such
components.) If $S_{0}$ is sign balanced, it has one circle, which is positive
(and is not neutral), so it is a unicycle, or else it is a non-neutral loose
edge.

If $S_{0}$ is sign unbalanced, it has cyclomatic number 2 and at least one
negative figure. Thus it is either an unbalanced theta graph or an unbalanced
handcuff, with possible pendant trees. In either case it contains exactly one
sign circuit, which must not be neutral. Thus there is an edge $e\in S_{0}$
(in the sign circuit) such that $S\smallsetminus e$ is hyperbalanced. That is,
$S$ is obtained by adding $e$ to a hyperbalanced independent set $I$. If $e$
is added to a tree component of $I$, $S_{0}$ is a unicycle. In order to
contain a sign circuit it must be a sign-balanced unicycle. If $e$ is an
isthmus in $S$, it joins two components of $I$, neither of which can be a tree
because then $S_{0}$ would be hyperbalanced; thus the components must be sign-
unbalanced unicycles and $S_{0}$ contains a handcuff sign circuit. The third
possibility is that $e$ is added to a unicyclic component of $I$ to form
$S_{0}$ with $\xi(S_{0})=2$. A component with cyclomatic number 2 must be,
aside from any pendant trees, a theta graph or a handcuff. Since it is sign
unbalanced, the theta graph must have two negative and one positive circle and
the handcuff must have one or two negative figures.

In every case, $S_{0}$ contains a sign circuit that is the unique sign circuit
in $S$, so it must be non-neutral to make $S$ hyperfrustrated. ∎

######  Corollary 7.4.

Sign and gain switching and edge reorientation in $\Upsilon$ do not change the
matroid $\mathbf{M}(\Upsilon)$ and therefore do not change linearly dependent
subsets among the vectors $\mathbf{z}(E)$.

###### Proof.

The matroid is determined by its independent sets. An independent set is
characterized by its underlying graph, by the signs of its circles, and by the
neutrality of its sign circuits. None of these is affected by switching or
orientation. The only one of those assertions that is not obvious is the one
about neutrality, but Lemma 2.10 says the gain of a sign circuit is not
changed by gain switching.

The dependent vector sets are determined by $\mathbf{M}(\Upsilon)$, according
to Theorem 4.2. ∎

We can characterize the maximal independent sets.

######  Theorem 7.5.

The bases of $\mathbf{M}(\Upsilon)$ are the following types of edge set $B$,
considered as spanning subgraphs.

  1. I.

If $\Upsilon$ is hyperbalanced, then in a sign-balanced component
$\Upsilon_{i}$ of $\Upsilon$, $B\cap E(\Upsilon_{i})$ is a spanning tree; and
in a sign-unbalanced component $\Upsilon_{i}$, $B\cap E(\Upsilon_{i})$ is a
spanning disjoint union of sign-unbalanced unicycles. $B$ contains no loose
edges.

  2. II.

If $\Upsilon$ is hyperfrustrated, $B$ is the same except that either $B$ has
one edge component that is a non-neutral loose edge; or in one sign-balanced
component $\Upsilon_{i}$ that is not a tree, $B\cap E(\Upsilon_{i})$ is a
spanning sign-balanced unicycle whose circle is not neutral; or in one sign-
unbalanced component $\Upsilon_{i}$, one component $B_{0}$ of $B\cap
E(\Upsilon_{i})$ is a theta graph or handcuff with at least one negative
figure, possibly with attached trees, and the unique sign circuit in $B_{0}$
is non-neutral.

###### Proof.

For an independent set $B$ to be maximal, in each sign-balanced component of
$\Upsilon$ it must be a spanning tree or a spanning sign-balanced unicycle.
Also, in each sign-unbalanced component $\Upsilon_{i}$ of $\Upsilon$, $B$
cannot have any tree components so every component of $B\cap E(\Upsilon_{i})$
is either a sign-unbalanced unicycle, or a graph of cyclomatic number 2 as
described in Theorem 7.3. Furthermore, $B$ can have only one component that is
not a tree or a sign-unbalanced unicycle, and none if $\Upsilon$ is
hyperbalanced or if $B$ contains a non-neutral loose edge. ∎

##  8\. Matroid: circuits

Knowing the independent sets, it is finally time to find the circuits. A set
of elements of a matroid is a circuit if and only if it has nullity 1 but
every proper subset has nullity 0. As usual, for $\mathbf{M}_{\infty}$ we can
treat $e_{\infty}$ as if it were a non-neutral loose edge.

######  Theorem 8.1 (Hypercircuits).

The hypercircuits are the following types of edge set.

  1. I.

Hyperbalanced: A neutral sign circuit, as in Figure 8.1.

  2. II.

Hyperfrustrated; in every type, all sign circuits are to be non-neutral:

    1. a.

Disconnected: The union of two disjoint, non-neutral sign circuits, as in
Figure 8.2.

    2. b.

Sign balanced: A theta graph or tight handcuff, as in Figure 8.3.

    3. c.

A subdivision of a sign-antibalanced $K_{4}$ in which all three subdivided
quadrilaterals are non-neutral, as in Figure 8.6(b).

    4. d.

A quadruple path as in Figure 8.6(a).

    5. e.

A linked theta and circle as in Figure 8.4.

    6. f.

Three linked circles as in Figure 8.5.

Figure 8.1. The hyperbalanced hypercircuits. In all these figures the asterisk
$*$ denotes a path of length $\geq 0$. All other paths, including (closed
paths), have length $\geq 1$. An isolated, positive circle may be a loose
edge. A negative circle with one indicated vertex may be a half edge. Figure
8.2. From left to right, the three types of disconnected hypercircuit. The
sign circuits are non-neutral. Figure 8.3. The two types of sign-balanced
hypercircuit. All positive circles are non-neutral. Figure 8.4. The two types
of linked theta-circle hypercircuit. Every contained sign circuit is non-
neutral. Figure 8.5. The four kinds of linked-circle hypercircuit. Each
contained sign circuit is non-neutral. Figure 8.6. Two special hypercircuit
types: a quadruple path and a $K_{4}$ subdivision. Again, each contained sign
circuit is non-neutral.

In the proof we use lollipops. A _lollipop_ is a negative figure (a circle or
half edge) with a path of length $\geq 0$ (the _stick_) connected to it at one
end. The other end of the stick is the _handle_. (If the stick has length $0$,
the handle is on the negative figure.) A lollipop, if attached to another
graph, is always attached at the handle. It is convenient to call a lollipop
_positive_ or _negative_ depending on the sign of the circle or half edge,
irrespective of the stick signs.

###### Proof.

The hyperbalanced hypercircuits $C$ are the neutral sign circuits because the
matroid $\mathbf{M}(\Upsilon|C)=\mathbf{F}(\Sigma|C)$.

For the rest of the proof we examine a hyperfrustrated hypercircuit $F$. The
nullity formula gives

(8.1) $\xi(F)=u_{\Sigma}(F)+2.$

Suppose $F$ has edge components $F_{1},\ldots,F_{k}$. Then
$\xi(F)-u_{\Sigma}(F)=\sum_{i}[\xi(F_{i})-u_{\Sigma}(F_{i})]=2.$ Since
$\xi(F_{i})\geq u_{\Sigma}(F_{i})$, this means $\xi(F_{i})=u_{\Sigma}(F_{i})$
for all edge components but at most two. Deleting those for which
$\xi(F_{i})=u_{\Sigma}(F_{i})$, we still satisfy (8.1), so by minimal
dependency $F$ cannot contain such an edge component. Therefore, $k\leq 2$.

If $F$ does have two edge components, each one satisfies
$\xi(F_{i})=u_{\Sigma}(F_{i})+1$ so is hyperfrustrated. Therefore, $F_{i}$
contains a non-neutral sign circuit $C_{i}$. It follows from Lemma 7.2 that
$C_{1}\cup C_{2}$ is already dependent; by minimality $F\subseteq C_{1}\cup
C_{2}$. Deleting any edge gives an independent set, according to Theorem 7.3,
so equality holds and $F$ has type (IIa).

Now assume $k=1$, so $F$ is a single connected component. Besides nullity 1
for $F$ itself we should have nullity 0 for every proper subset; that is,

$\xi(F\smallsetminus f)=u_{\Sigma}(F\smallsetminus f)+\beta(f)\text{ for every
}f\in F,$

where $\beta(f)=0$ if $F\smallsetminus f$ is hyperbalanced and $1$ if it is
not. In particular, $F$ must be formed by adding one edge, call it $e$, to an
independent set $I$, and by minimal dependency it can have no pendant trees.
These rules allow us to construct candidates from the list in Theorem 7.3.

The nullity of an edge set is not changed by adding or subtracting a pendant
edge. A hypercircuit, therefore, has no tree components or pendant trees.
Suppose we add $e$ to $I$: no trees can remain pendant from $I\cup\\{e\\}$, so
in particular any pendant trees in $I$ must combine with $e$ to form a path
whose endpoints have degree at least 2.

Suppose $e$ joins two components of $I$, $I_{1}$ and $I_{2}$; neither can be a
tree, so (from the structure theorem 7.3) $I_{1}$ must be a negative lollipop.
We can get the same hypercircuit from a different $I$ in which the lollipop’s
negative figure is a circle formed from a path pendant from $I_{2}$. This
proves we may choose $e\in F$ so that $e$ is added to a single component of
$I=F\smallsetminus\\{e\\}$, and as we assume $F$ is connected, so is $I$.

When we add $e$ to $I$, $e$ belongs to a set that is a maximal path whose
interior vertices are divalent, or to a circle with one vertex attaching it to
the rest of $F$, or to a circle that is $F$, or $e$ is a half edge with one
vertex attaching it to the rest of $F$. If $F$ is a circle, the circle must be
positive and neutral since $F$ is dependent, so it falls under type (I). In
the other cases let us call the path or circle or half edge the _$e$ -ear_.
Let $A$ denote the $e$-ear and now let $I$ be the remainder of $F$. $I$ is a
connected independent set that is either a sign-unbalanced unicycle or one of
the special types $S_{0}$ of Theorem 7.3(II), and $\xi(F)=\xi(I)+1$.

_Case 0. $F$ is a tight handcuff with two positive circles._ This case has
$\xi(F)=2=u_{\Sigma}(F)+2$, and deleting any edge gives nullity 1, so it is a
hypercircuit. This case is needed to rule out some examples. In fact, we can
now conclude that:

######  Lemma 8.2.

No hypercircuit can properly contain either a sign-balanced theta graph, or
two positive circles with at most one common vertex.

_Case 1. $I$ is a unicycle._ Then $\xi(F)=2$ so $F$ is either a handcuff or a
theta graph, and (8.1) implies that all circles are positive and there is no
half edge in the handcuff. The handcuff cannot contain a neutral circle, by
minimality, so its two circles are positive and non-neutral; but then omitting
the connecting edges (if any) gives a hypercircuit of type (IIa), so this
gives type (IIa) or (IIb). The theta graph similarly must have three non-
neutral positive circles, which means that the paths $P_{1},P_{2},P_{3}$
between its two trivalent vertices must have distinct gains (computed with the
same initial and final vertices). Deleting any edge gives a positive, non-
neutral circle with up to two pendant paths, which is independent, so this is
a hypercircuit of type (IIb).

_Case 2. $I$ is a theta graph with a single positive circle._ Here $F$ is
dependent since $\xi(F)=3$ and
$\operatorname{nul}_{\Upsilon}F=\xi(F)-u_{\Sigma}(F)-1=1$. The open question
is whether every proper subset is independent.

Let $I$ have trivalent vertices $u,v$ and constituent paths
$P_{1},P_{2},P_{3}$ with positive circle $P_{1}\cup P_{3}$. From Theorem
7.3(II) it is sign-unbalanced and its positive circle is non-neutral.

The $e$-ear $A$ may be a circle or half edge; then we have a theta graph with
a lollipop attached at its handle. Lemma 8.2 implies that the lollipop is
negative. Because $I$ also contains a negative circle, deleting any one edge
either reduces $\xi$ by 1 or, if the edge is in the stick, increases
$u_{\Sigma}$ by 1; in either case we get nullity 0. Thus, any edge set of this
type is a hypercircuit of the kind in Figure 8.4.

The alternative is that $A$ is a path.

Suppose $A$ has endpoints in the interiors of different constituent paths.
This gives a homeomorph of $K_{4}$. To analyze the signs and gains we may
consider it to be $K_{4}$. A signed $K_{4}$ has an even number of positive
triangles, so $I$ has either no or two such triangles. If it has none, we have
a sign-antibalanced $K_{4}$ as in type (IIc). If it has two, it contains a
sign-balanced theta graph which is already a hypercircuit of type (IIb).

Otherwise, the endpoints of $A$ are contained within one constituent path
$P_{i}$. Here we have two subcases. If $A$ has endpoints $u$ and $v$, then $F$
consists of four internally disjoint $uv$-paths and there must be two paths of
each sign to avoid having a balanced theta graph as a proper subgraph, a
violation of Lemma 8.2. This gives the unique $F$ that is a quadruple path. If
the endpoints are not $u$ and $v$, $A$ forms a circle $C$ with all or part of
$P_{i}$. This circle cannot be positive, because if it were, $F$ would
properly contain a configuration forbidden by Lemma 8.2. Thus, $C$ is
negative. Then $F$ is the graph in Figure 8.6(a).

_Case 3. $I$ is a handcuff and $F$ does not contain a theta graph._ (If $F$
contains a theta graph $\Theta$, it falls under type (IIb) if $\Theta$ is sign
balanced and by suitable choice of $e$ it has already been treated under Case
2 if $\Theta$ is sign unbalanced.) The handcuff has one or two negative
figures.

A negative lollipop can be attached anywhere; then $\xi(F)=3=u_{\Sigma}(F)+2$
so this set is dependent. A positive lollipop can only be attached if $I$ has
two negative figures (by Lemma 8.2), but as this duplicated adding a negative
lollipop to a handcuff with one positive circle, we need not consider it
separately. Figure 8.5 shows the possibilities for $F$ and makes it clear that
deleting any edge $f$ makes $F\smallsetminus f$ independent.

The remaining possibility for $F$ is that it is $I$ with a path ear $A$. As
$F$ cannot contain a theta graph, $A$ must have endpoints in the connecting
path of $I$, which means $F$ has three circles or half edges, of which no two
have more than one common vertex and no two can be positive. This case is like
adding a lollipop to a handcuff as was just treated.

That completes the analysis of possible hypercircuits. ∎

The many topological types of hypercircuit make a complicated list so we
classify them in another way. All sign circuits are non-neutral except in type
(1). _Sign contrabalanced_ means without positive circles.

######  Corollary 8.3.

These are the hypercircuits:

  1. (1)

A sign circuit that is neutral.

  2. (2)

A disconnected hypercircuit is the union of two disjoint non-neutral sign
circuits.

  3. (3)

A connected hypercircuit that is not a neutral sign circuit and contains at
most two positive circles.

    1. (A)

If it contains no positive circle, it is either three negative lollipops
joined at their handles, or a negative circle with two negative lollipops
attached at two different vertices.

    2. (B)

If it contains exactly one positive circle, it is either:

      1. (i)

A sign-contrabalanced handcuff with a positive circle attached at one vertex,
or a positive circle with two negative lollipops attached at two different
vertices.

      2. (ii)

A sign-unbalanced theta graph with one negative lollipop attached.

    3. (C)

If it contains two positive circles, it is one of:

      1. (i)

Two positive circles intersecting at exactly one vertex.

      2. (ii)

A sign-unbalanced theta graph with a path ear $Q$ added on a theta path $P$,
with $Q$ signed so the unique circle in $P\cup Q$ is negative.

  4. (4)

A sign-balanced theta graph in which every circle is non-neutral.

  5. (5)

A subdivision of a sign-antibalanced $K_{4}$.

##  9\. Minors

A _minor_ of $\Upsilon$ is the result of deleting and contracting edges. The
important property of minors of a gain signed graph is that they coordinate
with minors of the associated matroid.

Deletion of an edge set $S$, denoted by $\Upsilon\smallsetminus S$, is
obvious. Contracting an edge set involves contraction in a signed graph, so we
first define that.

######  Definition 9.1 (Contraction of a Signed Graph [22]).

Contracting a signed graph $\Sigma$ by an edge set $S$ gives a signed graph
$\Sigma/S$. Its vertex set is $\pi_{\text{\rm b}}(S)$. Its edge set is
$E\smallsetminus S$.

For a vertex $v\in V(\Sigma)$, we denote by $B_{v}$ the block of the partial
partition $\pi_{\text{\rm b}}(S)$ that contains $v$, if there is one, that is,
if $v$ is in a balanced component of $S$. If $v$ is in an unbalanced
component, then no $B_{v}$ exists.

An edge $e\in E\smallsetminus S$ becomes an edge in $\Sigma/S$ with endpoints
determined as follows. First, switch $\Sigma$ so that in every balanced
component all edges are positive.

If $e=e_{vw}$ is a link or loop in $\Sigma$, its endpoints in $\Sigma/S$ are
those of the sets $B_{v},B_{w}\in\pi_{\text{\rm b}}(S)$ that exist; then the
sign of $e$ in $\Sigma/S$ is its sign in the switched graph $\Sigma$. If one
or both do not exist, $e$ has one or no endpoints in the contraction, thus
becoming a half edge or loose edge.

If $e=e_{v}$ is a half edge in $\Sigma$, it is a half edge in $\Sigma/S$ with
endpoint $B_{v}\in\pi_{\text{\rm b}}(S)$ if $B_{v}$ exists, but it is a loose
edge if $B_{v}$ does not exist.

If $e$ is a loose edge in $\Sigma$, it is a loose edge in $\Sigma/S$.

The contraction $\Sigma/S$ is well defined up to switching of signs.

######  Lemma 9.2.

In $\Sigma$, suppose $S\subseteq E$ and $T\subseteq E\smallsetminus S$.

If $S$ is balanced in $\Sigma$, then $T$ is balanced in $\Sigma/S$ if and only
if $S\cup T$ is balanced in $\Sigma$.

If $S$ is unbalanced in $\Sigma$ and $S\cup T$ is connected, then $T$ is
unbalanced in $\Sigma/S$ if $V(S\cup T)\supset U_{\Sigma}(S)$, while $T$
consists of loose edges in $\Sigma/S$ if $V(S\cup T)=U_{\Sigma}(S)$.

For any edge set $S$, $b_{\Sigma}(S\cup T)=b_{\Sigma/S}(T)$.

###### Proof.

The first part is [22, Lemma 4.1]. The formula
$b_{\Sigma/S}(T)=b_{\Sigma}(S\cup T)$ results from applying this to each
component of $S\cup T$.

For the second part, suppose $V(S\cup T)\supset U_{\Sigma}(S)$. Then there is
a link $e$ of $T$ that is not in $S$ and is incident to exactly one vertex of
$U_{\Sigma}(S)$. In the contraction $e$ becomes a half edge; therefore $T$ is
unbalanced in $\Sigma/S$. If however $V(S\cup T)=U_{\Sigma}(S)$, then every
edge of $T$ becomes a loose edge.

For the third part, consider each component $A_{i}$ of $A=S\cup T$ separately.
If $S\cap A_{i}$ is balanced in $\Sigma$, then $b_{\Sigma/S}(T\cap
A_{i})=b_{\Sigma}(A_{i})$ by the first part. If $S\cap A_{i}$ is unbalanced,
then $b_{\Sigma/S}(T\cap A_{i})=0$ by the second part. The general formula
follows by addition over the $A_{i}$. ∎

######  Definition 9.3 (Contraction of a Gain Signed Graph).

The contraction of an edge set $S$ in $\Upsilon$ is a gain signed graph or a
signed graph, in either case denoted by $\Upsilon/S$. These are the two cases.

  1. 1.

If $S$ is hyperbalanced, switch the gains on $\Upsilon$ so every edge in $S$
is neutral; then apply signed-graph contraction by $S$. All edges of
$E\smallsetminus S$ retain their (switched) gains. This contraction is a gain
signed graph.

  2. 2.

If $S$ is hyperfrustrated, erase all gains, leaving only the signed graph
$\Sigma$, and contract $S$ in $\Sigma$. This contraction is a signed graph
without gains (or, it can be viewed as a gain signed graph in which all edges
are neutral).

The contraction $\Upsilon/S$ is well defined up to switching of signs and, in
the first case, of gains.

The first theorem says that minors are independent of the order of operations.
In particular, a minor can be computed by deleting and contracting one edge at
a time.

######  Theorem 9.4.

Suppose $S,T$ are disjoint subsets of $E$. Then $(\Upsilon\smallsetminus
S)\smallsetminus T=\Upsilon\smallsetminus(S\cup T)$,
$(\Upsilon/S)\smallsetminus T=(\Upsilon\smallsetminus T)/S$, and
$(\Upsilon/S)/T=\Upsilon/(S\cup T)=(\Upsilon/T)/S$.

The same theorem for signed graphs is [22, Proposition 4.2]. As in [22],
equality in the contraction formulas has to be interpreted as allowing for
certain name changes, as the vertex set of $\Upsilon/(S\cup T)$ is
$\pi_{\text{\rm b}}(S\cup T)$ in $\Sigma$, while that of $(\Upsilon/S)/T$ is
$\pi_{\text{\rm b}}(T)$ in $\Sigma/S$. We handle this by identifying vertex
sets in the natural way. We use the notation of signed graphs, since the gains
do not affect the vertex sets of contractions. For $v\in V(\Sigma)$, let
$B_{v}(S)$ be the set in $\pi_{\text{\rm b}}(\Sigma,S)$, defined in $\Sigma$,
that contains $v$; similarly, for $B_{v}\in V(\Sigma/S)$ let
$B^{\prime}_{B_{v}}(T)$ be the set in $\pi_{\text{\rm b}}(\Sigma/S,T)$,
defined in $\Sigma/S$, that contains $B_{v}(S)$, and finally, let $B_{v}(S\cup
T)$ be the set in $\pi_{\text{\rm b}}(\Sigma,S\cup T)$ that contains $v$. Then
it is a fact that $B_{v}(S\cup T)=\bigcup B^{\prime}_{B_{v}}(T)$, the union of
all sets $B_{w}(S)\in B^{\prime}_{B_{v}}(T)$, so we can identify the vertex
$B_{v}(S\cup T)$ in $\Sigma/(S\cup T)$ with the vertex $B^{\prime}_{B_{v}}(T)$
in $(\Sigma/S)/T$.

We need a gain analog of Lemma 9.2.

######  Lemma 9.5.

Suppose $S\subseteq E$ is hyperbalanced in $\Upsilon$ and $T\subseteq
E\smallsetminus S$. Then $T$ is hyperbalanced in $\Upsilon/S$ if and only if
$S\cup T$ is hyperbalanced in $\Upsilon$.

###### Proof.

We depend on the fact that contraction of $\Upsilon$ is built upon contraction
in $\Sigma$.

If $S\cup T$ is hyperbalanced, switch so its edges are all neutral.
Contracting $S$ leaves the gains on $T$ neutral, so $T$ is hyperbalanced in
$\Upsilon/S$.

Conversely, suppose $T$ is hyperbalanced in $\Upsilon/S$. Assume the gains in
$\Upsilon$ have been switched so every edge of $S$ is neutral. Now, switch
$\Upsilon/S$ so every edge in $T$ is neutral in $\Upsilon/S$. Switching gains
in $\Upsilon/S$ by $\theta$, to $\varphi^{\theta}$, can be applied to
$\Upsilon$: define $\theta^{\prime}:V\to\mathbf{K}^{+}$ by
$\theta^{\prime}(v)=\theta(B_{v})$, since $B_{v}$ is defined for every vertex
$v\in V$, due to balance of $S$. Switching $\Upsilon$ in this way neutralizes
every edge in $S\cup T$, proving hyperbalance of $S\cup T$, and gives the
contraction the switched gains $\varphi^{\theta}$. ∎

###### Proof of Theorem 9.4.

The parts with deletions are routine. Signed graph minors obey the formulas in
Theorem 9.4 [22, Proposition 4.2]. Contraction of a gain signed graph follows
the rules for signed-graph contraction supplemented by a rule for gains, so
the only question is how the gains behave. If $S\cup T$ is hyperbalanced, we
may assume by gain switching that $\varphi|_{S\cup T}\equiv 0$; then the gains
off $S\cup T$ are never changed in any of the contractions. If $S\cup T$ is
not hyperbalanced, $\Upsilon/(S\cup T)$ has no gains. In $\Upsilon/S$, if $S$
is hyperfrustrated there are no gains, so there are no gains in
$(\Upsilon/S)/T$; while if $S$ is hyperbalanced, Lemma 9.5 tells us that $T$
is hyperfrustrated in $\Upsilon/S$ so there are no gains in $(\Upsilon/S)/T$.
Either way, there are no gains in any of $(\Upsilon/S)/T$, $\Upsilon/(S\cup
T)$, and $(\Upsilon/T)/S$, so they are equal by [22, Proposition 4.2]. ∎

######  Theorem 9.6.

Suppose $S\subseteq E$. Then $\mathbf{M}(\Upsilon\smallsetminus
S)=\mathbf{M}(\Upsilon)\smallsetminus S$ and
$\mathbf{M}(\Upsilon/S)=\mathbf{M}(\Upsilon)/S$.

###### Proof.

We prove the rank functions agree. This is trivial for deletion.

For contraction we compute the ranks in $\mathbf{M}$ and $\mathbf{M}/S$. With
$A\subseteq E\smallsetminus S$, first from the definition of rank in a
contraction matroid:

$\displaystyle\operatorname{rk}_{\mathbf{M}(\Upsilon)/S}A$
$\displaystyle=\operatorname{rk}_{\mathbf{M}}(A\cup
S)-\operatorname{rk}_{\mathbf{M}}(S)$ $\displaystyle=[n-b_{\Sigma}(A\cup
S)+\delta_{\Upsilon}(A\cup S)]-[n-b_{\Sigma}(S)+\delta_{\Upsilon}(S)]$
$\displaystyle=b_{\Sigma}(S)-b_{\Sigma}(A\cup S)+\delta_{\Upsilon}(A\cup
S)-\delta_{\Upsilon}(S),$

and second from rank in the contracted gain signed graph:

$\displaystyle\operatorname{rk}_{\mathbf{M}(\Upsilon/S)}A$
$\displaystyle=|V(\Upsilon/S)|-b_{\Sigma/S}(A)+\delta_{\Upsilon/S}(A)$
$\displaystyle=b_{\Sigma}(S)-b_{\Sigma/S}(A)+\delta_{\Upsilon/S}(A).$

Now we consider two cases.

If $S$ is hyperbalanced, then $\delta_{\Upsilon/S}(A)=\delta_{\Upsilon}(A\cup
S)$ by Lemma 9.5, so

$\operatorname{rk}_{\mathbf{M}(\Upsilon)/S}A=b_{\Sigma}(S)-b_{\Sigma}(A\cup
S)+\delta_{\Upsilon}(A\cup S)$

and

$\operatorname{rk}_{\mathbf{M}(\Upsilon/S)}A=b_{\Sigma}(S)-b_{\Sigma/S}(A)+\delta_{\Upsilon}(A\cup
S).$

By Lemma 9.2 $b_{\Sigma}(A\cup S)=b_{\Sigma/S}(A)$. Therefore, the ranks are
equal.

If $S$ is hyperfrustrated, then $\Upsilon/S=\Sigma/S$ so
$\mathbf{M}(\Upsilon/S)=\mathbf{F}(\Sigma/S)$. The contracted matroid
computation is

$\displaystyle\operatorname{rk}_{\mathbf{M}(\Sigma)/S}A$
$\displaystyle=\operatorname{rk}_{\mathbf{M}}(A\cup
S)-\operatorname{rk}_{\mathbf{M}}(S)$ $\displaystyle=[n-b_{\Sigma}(A\cup
S)]-[n-b_{\Sigma}(S)]$ $\displaystyle=b_{\Sigma}(S)-b_{\Sigma}(A\cup S).$ The
computation in the contracted graph is
$\displaystyle\operatorname{rk}_{\mathbf{M}(\Upsilon/S)}A$
$\displaystyle=|V(\Sigma/S)|-b_{\Sigma/S}(A)$
$\displaystyle=b_{\Sigma}(S)-b_{\Sigma/S}(A).$
$\displaystyle=b_{\Sigma}(S)-b_{\Sigma}(A\cup S)$

by Lemma 9.2. Thus, the ranks are equal in this case as well. ∎

Contraction of a single edge is sufficiently important to merit separate
statement.

######  Corollary 9.7.

For $e\in E$, the contraction $\Upsilon/e$ is described in the following list:

  1. (a)

If $e$ is a link $e_{uv}$, switch signs and gains so it is positive and
neutral, identify $u$ and $v$, and delete $e$. All other edges retain their
switched signs and gains.

  2. (b)

If $e$ is a positive loop or loose edge and is neutral, delete it and retain
all signs. If $e$ is neutral, retain all gains. If not, erase all gains.

  3. (c)

If $e$ is a half edge or negative loop at vertex $v$, delete it and $v$, thus
removing $v$ as an endpoint from any other edge incident with $v$. Retain the
signs of edges that do not become loose or half edges; make loose edges
positive and half edges negative. If $e$ is neutral, retain all gains. If not,
erase all gains.

  4. (d)

If $e$ is the extra point $e_{\infty}$, delete it and erase all gains but
retain signs.

In the extended matroid $\mathbf{M}_{\infty}(\Upsilon)$, when a neutral edge
or a link is contracted the extra point $e_{\infty}$ remains the extra point.
When a non-neutral, non-link edge is contracted, $e_{\infty}$ becomes a
matroid loop; it may be treated as a loose edge in the resulting signed graph.

##  10\. The hyperplane model

The biggest reason for gain signed graphs is that they encode popular
hyperplane arrangements in a more manageable form.

###  10.1. Affine hyperplanes

The hyperplane associated to an edge $e_{ij}$ lies in the affine space
$\mathbb{A}^{n}(\mathbf{K})$ and is given by

$\mathbf{h}(e):\tau(v_{i},e)x_{i}+\tau(v_{j},e)x_{j}=-\varphi(e).$

(The affine space is distinguished from the vector space $\mathbf{K}^{n}$ by