Murota K. Matrices and Matroids for Systems Analysis

Подождите немного. Документ загружается.

432 7. Further Topics

Example 7.3.1. Here is a small example of a mixed skew-symmetric matrix

A = Q + T :

⎡

⎢

⎣

0 −11t

1020

−1 −20t

−t

0 −t

⎤

⎥

⎦

⎡

⎢

⎣

0 −110

1020

−1 −200

0000

⎤

⎥

⎦

⎡

⎢

⎣

000t

000 0

000t

−t

0 −t

⎤

⎥

⎦

where T = {t

} is assumed to be algebraically independent over Q. This

is a mixed skew-symmetric matrix with respect to (K, F )forK = Q and

F = Q(t

). 2

The objective of this section is to present major mathematical results on

mixed skew-symmetric matrices and to treat the solvability of electrical net-

works with gyrators using those results. The mathematical analysis of mixed

skew-symmetric matrices leads to an extension of the matroid parity problem,

called the delta-matroid parity problem, introduced by Geelen–Iwata–Murota

[93]. In particular, the rank formula for a mixed skew-symmetric matrix takes

the form of a novel min-max formula for a pair of linear delta-matroids, which

is an extension of the duality result for the linear matroid parity problem due

to Lov´asz [177, 179, 180].

The table below indicates how the combinatorial tools used in the analysis

of mixed matrices are generalized for mixed skew-symmetric matrices.

Mixed matrix Mixed skew-symmetric matrix

T -part bipartite matching nonbipartite matching

Q-part

linear matroid linear delta-matroid

Combination

matroid union/intersection delta-matroid covering/parity

Remark 7.3.2. Given a matroid M =(V,B,ρ) on ground set V with basis

family B and rank function ρ, and also a partition Π of V into pairs, called

lines,thematroid parity problem is to ﬁnd a base containing the maximum

number of lines (or equivalently to ﬁnd a largest independent set consisting

of lines). We denote by ν(M,Π) the optimal value of the matroid parity

problem (the maximum number of lines contained in a base). The matroid

parity problem was introduced by Lawler (cf. Lawler [171], Lov´asz–Plummer

[181]).

The matroid parity problem is polynomially unsolvable in general, as

pointed out by Jensen–Korte [151] and Lov´asz [179]. (This statement is in-

dependent of the P=NP conjecture.) It is solvable, however, if the matroid

in question is represented by a matrix. This special case is called the linear

matroid parity problem.Lov´asz [177, 179, 180] showed a polynomial-time al-

gorithm for ﬁnding an optimal base for the linear matroid parity problem.

This algorithm has been followed by more eﬃcient algorithms: an augmenting

path algorithm of Gabow–Stallmann [83] and an algorithm of Orlin–Vande

Vate [258]. Those algorithms are based on a min-max theorem for ν(M,Π),

7.3 Mixed Skew-symmetric Matrix 433

due to Lov´asz [177, 179, 180], which states that, for a linear matroid M

representable over a ﬁeld F ,wehave

ν(M,Π) = min

M→M

◦

,{V

}

ρ(V ) − ρ

◦

(V )+



◦

)

, (7.44)

where the minimum is taken over all matroids M

◦

=(V,B

◦

,ρ

◦

)thatare

strong quotients of M (see (2.65)) and all partitions {V

} of V that are

compatible with the partition Π (that is, each V

is a union of lines), and the

minimum is attained by a linear matroid M

◦

representable over F . 2

7.3.2 Skew-symmetric Matrix

A matrix A =(A

) over a ﬁeld F is said to be skew-symmetric if A

= −A

for all (i, j)andA

= 0 for all i, where the second condition is implied by

the ﬁrst if the characteristic of F is distinct from two. The deﬁnition of skew-

symmetry presupposes that the row set and the column set of A are indexed

by a common ﬁnite set, say V = {1, ···,n}.Thesupport graph of A is an

undirected graph G =(V, E) with vertex set V and arc set E = {(i, j) |

=0}.ForI ⊆ V , A[I] designates A[I,I], the principal submatrix of A

indexed by I. We also denote by I/J the symmetric diﬀerence of I and J,

namely, I/J =(I ∪J) \ (I ∩ J).

For a skew-symmetric A of an even order the Pfaﬃan of A is deﬁned by

pf A =



, (7.45)

where the summation is taken over all partitions P = {{i

}, ···, {i

}}

(ν = n/2) of V into unordered pairs and

=sgn



12··· 2ν − 12ν

··· i





k=1

Note that a nonzero term a

in the Pfaﬃan corresponds to a perfect matching

in the support graph G, since

k=1

= 0 if and only if (i

) ∈ E for

k =1, ···,ν. We deﬁne pf A =0ifn is odd.

The following fact is well known.

Proposition 7.3.3. For a skew-symmetric A we have det A =(pfA)

Proof.Forn odd, both det A and pf A vanish, since det A = det((−A)

(−1)

det A. The content of this identity lies in the case of even n;seeMuir

[195] for the proof.

Pfaﬃans enjoy an identity similar to the Grassmann–Pl¨ucker identity

for determinants (Proposition 2.1.4). We use the notation pf

, ···,i

)

434 7. Further Topics

for pf(A[{i

, ···,i

}]), where pf

, ···,i

)=−pf

, ···,i

etc., and, in particular, pf

, ···,i

) = 0 if the indices i

, ···,i

are not

distinct. We also use the notation

i for the omission of an index i,thatis,

, ···,

, ···,i

)=(i

, ···,i

k−1

k+1

, ···,i

Proposition 7.3.4 (Grassmann–Pl¨ucker identity for Pfaﬃans). For

a skew-symmetric matrix A, it holds that



l=1

(−1)

· pf

, ···,i

) · pf

, ···,

, ···,j

)



k=1

(−1)

· pf

, ···,

, ···,i

) · pf

, ···,j

)=0. (7.46)

In particular, for i ∈ I/J, it holds that

(I) · pf

(J)=



j∈(IJ)\{i}

· pf

(I/{i, j}) · pf

(J/{i, j}) (7.47)

with appropriately chosen sign σ

= ±1 depending on the ordering of the

elements of I, J,etc.

Proof. By the deﬁnition of the Pfaﬃan we have

, ···,i



k=1

(−1)

k−1

· pf

) · pf

, ···,

, ···,i

, ···,j



l=1

(−1)

l−1

· pf

) · pf

, ···,

, ···,j

as well as pf

)+pf

) = 0. Substitution of these into the left-hand

side of (7.46) establishes the identity. For (7.47), take I = {j

, ···,i

J = {j

, ···,j

}, i = j

in (7.46).

Remark 7.3.5. The Grassmann–Pl¨ucker identity for Pfaﬃans is known to

physicists as Wick’s theorem. The expression (7.47) using symmetric diﬀer-

ence is found in Wenzel [334] and Dress–Wenzel [55]. The present proof of

(7.46) is taken from Ohta [253]. 2

Proposition 7.3.6. The rank of a skew-symmetric matrix is equal to the

maximum size of a nonsingular principal submatrix.

Proof. Let (I,J) be such that rank A =rankA[I,J]=|I| = |J|. Then Propo-

sition 2.1.9(2) with (I

)=(I,I), (I

)=(I ∪ J, I ∪J)shows

2r ≥ rank A[I,I]+rankA[I ∪J, I ∪J] ≥ rank A[I ∪J, I]+rankA[I,I∪J] ≥ 2r,

7.3 Mixed Skew-symmetric Matrix 435

where r =rankA. This implies |I| =rankA[I,I]=rankA.

For a matrix A,apivotal transform means the matrix A



resulting from

the transformation

A =





→ A





−1

−A

−1

− A

−1



for a nonsingular submatrix A

. The pivotal transformation preserves skew-

symmetry. We denote by A ∗ I the pivotal transform of a skew-symmetric

matrix A with respect to a nonsingular principal submatrix A[I]. The follow-

ing is a fundamental identity due to Tucker [321].

Proposition 7.3.7. For a skew-symmetric matrix A and I ⊆ V such that

A[I] is nonsingular we have

det(A ∗ I)[J] = det A[I/J]/ det A[I](J ⊆ V ).

Proof. First note the relation



−1

−A

−1







O A

−1

−A

−1

− A

−1



where I

and I

denote unit matrices and A

= A[I]. The claim can be

proven by considering the determinant of the relevant submatrix.

A skew-symmetric matrix A =(A

) is said to be generic if the set

| A

=0,i < j} of its nonzero entries in the upper-triangular part is

algebraically independent. A generic skew-symmetric matrix is in fact a com-

binatorial object, since it does not carry numerical information. Its structure

is fully represented by the support graph G, and conversely, for any graph

G we may associate a generic skew-symmetric matrix (sometimes called the

Tutte matrix of G) such that its support graph coincides with G.Foragraph

G we denote by ν(G) the maximum size of a matching in G and by odd(G)the

number of odd components of G, where an odd component means a connected

component having an odd number of vertices.

For the rank of a generic skew-symmetric matrix we have the following

graph-theoretic characterizations.

Proposition 7.3.8. The rank of a generic skew-symmetric matrix A is equal

to the maximum size of a matching in the support graph of A.

Proof. The algebraic independence implies that pf A is nonzero if and only if

there exists at least one nonzero term a

in the deﬁnition (7.45). Hence, A

is nonsingular if and only if the support graph of A has a perfect matching.

Application of this argument to principal submatrices establishes the claim

by Proposition 7.3.6.

436 7. Further Topics

Theorem 7.3.9 (Tutte–Berge formula). ForagraphG =(V,E) we

have

2ν(G) = min{|V | + |U|−odd(G \ U) | U ⊆ V }, (7.48)

where G \ U means the graph obtained from G by deleting the vertices of U.

Proof. This will be derived from a more general theorem below. Standard

combinatorial proofs can be found in Lov´asz–Plummer [181] and Cook–

Cunningham–Pulleyblank–Schrijver [40].

The rank of a principal submatrix A[I,I] of a generic skew-symmetric

matrix A can be expressed in terms of matchings by Proposition 7.3.8 above,

and hence Theorem 7.3.9 gives a formula:

rank A[I,I] = min{2|I|−|I



|−odd(G[I



]) | I



⊆ I},

where G[I



] means the subgraph of G induced on I



. This formula can be

generalized for a general submatrix A[I,J] in the following form, which is

ascribed to L. Lov´asz in Cunningham–Geelen [44].

Theorem 7.3.10. For a generic skew-symmetric matrix A we have

rank A[I,J] = min{|I \ I



| + |J \ J



| + |I



∩ J



|−odd(G[I



∩ J



]) |



) ∈ D(I,J)}, (7.49)

where D(I,J)={(I



) | A[I



]=O, A[I



]=O, I



⊆ I,J



⊆ J}.

Proof.

The inequality

rank A[I,J] ≤|I \ I



| + |J \ J



| + |I



∩ J



|−odd(G[I



∩ J



]) (7.50)

is valid for any (I



) ∈ D(I,J), since

rank A[I,J] ≤|I \ I



| + |J \ J



| +rankA[I



rank A[I



]=rankA[I



∩ J



] ≤|I



∩ J



|−odd(G[I



∩ J



]).

By Theorem 2.3.47 there exist I

∗

⊆ I and J

∗

⊆ J such that

(i) |I

∗

| + |J

∗

|−rank A[I

∗

]=|I| + |J|−rank A[I,J],

(ii) rank A[I

∗

\{i},J

∗

\{j}]=rankA[I

∗

], ∀i ∈ I

∗

, ∀j ∈ J

∗

We claim that (ii) implies (I

∗

) ∈ D(I,J). Suppose, to the contrary, that

= 0 for some (i, j) with i ∈ I

∗

\ J

∗

, j ∈ J

∗

or i ∈ I

∗

, j ∈ J

∗

\ I

∗

Since rank A[I

∗

\{i},J

∗

\{j}]=rankA[I

∗

](=:r), there exist I



⊆

∗

\{i} and J



⊆ J

∗

\{j} such that rank A[I



]=|I



| = |J



| = r.

Consider the Laplace expansion of det A[I



∪{i},J



∪{j}]. It contains a

nonvanishing term A

·det A[I



], which is not cancelled out by virtue of

This proof as well as the derivation of Theorem 7.3.9 from this theorem is taken

from Geelen [90]. Compare this proof with Remark 4.2.15.

7.3 Mixed Skew-symmetric Matrix 437

the unique occurrence of the variable A

. This implies a contradiction that

r =rankA[I

∗

] ≥ rank A[I



∪{i},J



∪{j}]=|I



| +1=r +1.

Since (I

∗

) ∈ D(I,J), we have rank A[I

∗

]=rankA[I

∗

∩ J

∗

], and

also rank A[I

∗

∩ J

∗

]=rankA[(I

∗

∩ J

∗

) \{i}] for all i ∈ I

∗

∩ J

∗

by (ii). The

latter implies, by Gallai’s lemma below, that rank A[I

∗

∩ J

∗

]=|I

∗

∩ J

∗

|−

odd(G[I

∗

∩ J

∗

]). Substitution of these into (i) shows that (7.50) holds with

equality for (I



)=(I

∗

The following fundamental fact, used in the proof above, deserves to be

stated as a theorem.

Theorem 7.3.11 (Gallai’s lemma). Let G =(V,E) be a connected graph.

If ν(G \{v})=ν(G) for all v ∈ V , then 2ν(G \{v})=|V |−1 for all v ∈ V .

Proof.

Let M be the matching matroid (see Example 2.3.7) deﬁned by G.

The assumption means that M has no coloops. If (u, v) is an arc, then there

is no maximum matching missing both u and v,thatis,u and v areinseries.

Since series pairs are transitive (cf. §2.3.2) and G is connected, every pair of

vertices is in series. This implies that a maximum matching misses just one

vertex, i.e., 2ν(G)=|V |−1. Hence, 2ν(G \{v})=2ν(G)=|V |−1 for all

v ∈ V .

Theorem 7.3.9 is now proven from Theorem 7.3.10. For a minimizer

∗

) ∈ D(V,V ) in (7.49) we have

rank A = |V \ I

∗

| + |V \J

∗

| + |I

∗

∩ J

∗

|−odd(G[I

∗

∩ J

∗

])

≥|V | + |V \(I

∗

∪ J

∗

)|−odd(G[I

∗

∪ J

∗

]).

On the other hand, for any U ⊆ V it holds that

rank A ≤ rank A[V \ U]+rankA[U, V \U]+rankA[V,U]

≤ (|V \ U|−odd(G \ U )) + |U| + |U|.

Hence follows (7.48), since rank A =2ν(G).

Remark 7.3.12. It is shown by Cunningham–Geelen [44] that the rank of a

general submatrix A[I,J] can be characterized in terms of “path-matching”

(a generalization of matching) and that it can be computed in polynomial

time, though the algorithm is not really combinatorial. 2

Remark 7.3.13. For a numerically speciﬁed skew-symmetric matrix, the

maximum size of a matching in the support graph is only an upper bound on

the rank (due to accidental numerical cancellation). A systematic procedure

has been given by Geelen [91] that assigns integers in the range of {1, ···,n}

(n: the size of the matrix) to the nonzero entries of a generic skew-symmetric

matrix so that the rank of the resulting (numerical) skew-symmetric matrix

attains this upper bound. 2

This proof, communicated by J. Geelen, reveals the matroid-theoretic nature of

the proof given in Lov´asz–Plummer [181].

438 7. Further Topics

Remark 7.3.14. A canonical decomposition representing the structure of

maximum matchings of nonbipartite graphs is known as the Gallai–Edmonds

decomposition (see Lov´asz–Plummer [181]). As a reﬁnement of this decom-

position, a canonical block-triangularization of skew-symmetric matrices is

given by Iwata [140]. This is a generalization of the Dulmage–Mendelsohn

decomposition expounded in §2.2.3. 2

7.3.3 Delta-matroid

The concept of a delta-matroid was introduced by Bouchet [15] as a gen-

eralization of a matroid. Essentially equivalent combinatorial structures

were proposed independently by Chandrasekaran–Kabadi [30] and by Dress–

Havel [50]; see also Bouchet–Cunningham [19] and Bouchet–Dress–Havel [20].

A delta-matroid is a pair (V,F) of a ﬁnite set V and a nonempty family F

of its subsets, called feasible sets, that satisfy the symmetric exchange axiom:

(DM) For F, F



∈Fand u ∈ F /F



, there exists v ∈ F /F



such

that F /{u, v}∈F.

A delta-matroid is said to be an even delta-matroid if |F/F



| is even for all

F, F



∈F. As is easily seen, (V,F) is an even delta-matroid if and only if it

satisﬁes

(DM

even

)ForF, F



∈Fand u ∈ F /F



, there exists v ∈ (F /F



) \

{u} such that F /{u, v}∈F.

It is also known (cf. Wenzel [335], Duchamp [58]) that an even delta-matroid is

characterized by a stronger exchange axiom (simultaneous exchange axiom):

(DM

)ForF, F



∈Fand u ∈ F /F



, there exists v ∈ (F /F



) \{u}

such that F /{u, v}∈Fand F



/{u, v}∈F.

A number of operations can be deﬁned for a delta-matroid M =(V,F)

with respect to a subset X ⊆ V .Thetwisting of M by X is a delta-matroid

M/X =(V,F/X), where F/X = {F /X | F ∈F}. Two delta-matroids

are said to be equivalent if they are transformed to each other by twisting.

The delta-matroid M

∗

= M/V is called the dual of M.Thedeletion of

X from M means a delta-matroid M \ X =(V \ X, F\X) deﬁned by

F\X = {F | F ∈F,F⊆ V \X}, where F\X is assumed to be nonempty.

The contraction of M by X, denoted M/X, is deﬁned as (M/X) \ X. Note

that these operations preserve evenness.

A skew-symmetric matrix deﬁnes an even delta-matroid (Bouchet [16]).

Let A be a skew-symmetric matrix over a ﬁeld and V be its row/column set.

The family of the nonsingular principal submatrices

F(A)={X ⊆ V | rank A[X]=|X|}

satisﬁes the simultaneous exchange axiom (DM

) by (7.47) in Proposition

7.3.4, and hence M(A)=(V,F(A)) forms an even delta-matroid, in which

7.3 Mixed Skew-symmetric Matrix 439

the empty set is feasible. A delta-matroid M that can be expressed as M =

M(A)/X for some skew-symmetric matrix A over a ﬁeld F and a subset

X ⊆ V (not necessarily feasible in M(A)) is called a linear delta-matroid

representable over F . If the matrix A and the subset X are given explicitly,

M is said to be represented over F .IncaseX is feasible in M(A), we have

M(A)/X = M(A ∗ X) by Proposition 7.3.7.

A matroid M =(V, B) given in terms of the basis family B is an even

delta-matroid, since (BM

)in§2.3.4 implies (DM

) (or alternatively, since

(BM

) and (BM

−

) together imply (DM

even

)). Moreover, a linear matroid is

a linear delta-matroid, as follows. Let M =(V, B) be represented by a matrix

with column set V in the sense that B is the family of column bases of the

matrix (see Example 2.3.8). For any base B of M we may assume that the

matrix is in the following form:

BV\ B

BI D

where I is an identity matrix. Deﬁne a skew-symmetric matrix A by

A =



BV\ B

BOD

V \ B −D



. (7.51)

Then, for X ⊆ V , A[X/B] is nonsingular if and only if D[B \ X, X \ B]

is nonsingular, which in turn is equivalent to X ∈B. Hence we have M =

M(A)/B, which shows that M is indeed a linear delta-matroid.

For a pair of delta-matroids M

=(V

, F

)andM

=(V

, F

) with

∩V

= ∅, their direct sum M

⊕M

=(V

∪V

, F

⊕F

) is a delta-matroid

with

⊕F

= {F

∪ F

| F

∈F

If M

= M(A

)/X

and M

= M(A

)/X

,wehaveM

⊕M

= M(A)/X

for X = X

∪ X

and

A =





For a pair of delta-matroids M

=(V, F

)andM

=(V, F

), we deﬁne

their union by M

∨ M

=(V,F

∨F

) with

∨F

= {F

∪ F

| F

∩ F

= ∅,F

∈F

}. (7.52)

It is known (Bouchet [17]) that M

∨ M

is a delta-matroid.

The delta-covering problem, posed by Bouchet [18], is to ﬁnd F

∈F

and

∈F

maximizing |F

| for a given pair of delta-matroids M

=(V,F

)

and M

=(V,F

). The delta-covering problem contains the following decision

problems as special cases:

440 7. Further Topics

[Partition problem]

Given a pair of delta-matroids M

=(V,F

)andM

=(V,F

), does

there exist a partition (F

)ofV such that F

∈F

and F

∈F

[Intersection problem]

Given a pair of delta-matroids M

and M

,doesthereexistacom-

mon feasible set?

Note that the intersection problem for M

and M

is the partition problem

for M

and M

∗

The following is an observation, to be used in §7.3.4, that the optimal value

of the delta-covering problem is equal to the maximum size of a feasible set

in the sum M

∨ M

if the empty set is feasible in one of the given delta-

matroids.

Lemma 7.3.15. For a pair of delta-matroids M

=(V,F

) and M

(V,F

) such that ∅∈F

, it holds that

max{|F

||F

∈F

}

= max{|F

∪ F

||F

∩ F

= ∅,F

∈F

Proof.TakeF

∈F

and F

∈F

with maximum |F

|.Foru ∈ F

∩ F

if any, there exists v ∈ F

= F

/∅ such that F



= F

\{u, v}∈F

.The

maximality of |F

| implies v ∈ F

\ F

. Hence |F



| = |F

| and



∩F

| = |F

∩F

|−1. Repeated transformation from (F

)to(F



)

leads to a disjoint pair (F

A min-max relation is known for the delta-covering problem in the case

of linear delta-matroids. The min-max relation refers to a distance between

two delta-matroids and the number of odd components with respect to a pair

of even delta-matroids.

The distance between two delta-matroids M =(V, F)andM

◦

=(V,F

◦

denoted dist(M, M

◦

), is deﬁned to be the minimum cardinality of Z such that

M = M

\Z and M

◦

= M

/Z for some delta-matroid M

=(V ∪ Z, F

where dist(M, M

◦

)=+∞ if no such M

exists. Note that dist(M, M

◦

dist(M

◦

, M) since M

\ Z =(M

/Z)/Z and M

/Z =(M

/Z) \ Z.

For a pair of even delta-matroids M

=(V,F

)andM

=(V,F

), let

, ···,V

) be the ﬁnest partition of V that simultaneously gives direct-sum

decompositions of both M

and M

. We say that V

is an odd component

with respect to (M

, M

)if|F

∩ V

| + |F

∩ V

|−|V

| is odd for F

∈F

and F

∈F

. Denoting by odd(M

, M

) the number of odd components with

respect to (M

, M

), we have |F

|≤|V |−odd(M

, M

) for any F

∈F

and F

∈F

The min-max relation, due to Geelen–Iwata–Murota [93], reads as follows.

Theorem 7.3.16. For a pair of linear delta-matroids M

=(V, F

) and

=(V,F

) representable over ﬁelds F

and F

, respectively, we have

7.3 Mixed Skew-symmetric Matrix 441

max{|F

||F

∈F

}

= min{dist(M

, M

◦

) + dist(M

, M

◦

) − odd(M

◦

, M

◦

)

| M

◦

, M

◦

: even delta-matroids} + |V |,

and the minimum is attained by M

◦

and M

◦

representable over F

and F

respectively. 2

The delta-matroid parity problem (or delta-parity problem) has been in-

troduced by Geelen–Iwata–Murota [93] as a natural generalization of the

matroid parity problem (see Remark 7.3.2 for the matroid parity problem).

Let M =(V,F) be a delta-matroid on V with |V | even, and Π be a partition

of V into pairs, called lines.ForF ⊆ V , we denote by δ

(F ) the number of

lines exactly one element of which belongs to F . In other words,

(F )=|{v ∈ V | v ∈ F, ¯v ∈ V \F }|, (7.53)

where, for v ∈ V ,¯v denotes the element such that {v, ¯v} is a line. The delta-

parity problem is to ﬁnd a feasible set F ∈Fthat minimizes δ

(F ). We

denote by δ(M,Π) the optimal value of this problem, that is,

δ(M,Π) = min{δ

(F ) | F ∈F}. (7.54)

An obvious lower bound exists on δ(M,Π) in the case of an even delta-

matroid M.LetM = M

⊕···⊕M

be the ﬁnest direct sum decomposition

of M which is compatible with the partition Π (that is, the ground set of

each M

is a union of lines). Then each component M

is also an even delta-

matroid. A component M

is called an odd component if every feasible set of

is of odd cardinality. Denoting the number of such odd components by

odd(M,Π), we have δ(M,Π) ≥ odd(M,Π).

In the linear case, we can tighten this lower bound by considering another

delta-matroid M

◦

as follows (Geelen–Iwata–Murota [93]).

Theorem 7.3.17. For a linear delta-matroid M representable over a ﬁeld

F , we have

δ(M,Π) = max{odd(M

◦

,Π) − dist(M, M

◦

) | M

◦

: even delta-matroid},

and the maximum is attained by M

◦

representable over F . 2

Remark 7.3.18. The delta-parity problem and the delta-covering problem

are equivalent. Given an instance of the delta-parity problem, M =(V,F)

and Π,letL denote the family of subsets of V that can be represented

as a union of lines. Then M

=(V, L) forms an even delta-matroid, and

(F )=|V |−max{|F /L||L ∈L}holds for F ⊆ V . Hence the delta-

parity problem is a delta-covering problem for (M, M

). Conversely, given

a pair of delta-matroids (V, F

) and (V, F

) for the delta-covering problem,

denote their copies by M

=(V

, F



)andM

=(V

, F



), respectively. Let