Murota K. Matrices and Matroids for Systems Analysis

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

90 2. Matrix, Graph, and Matroid

The following two lemmas justify the above algorithm. The former shows

that the independence of ∂

M and ∂

−

M in the respective matroids is main-

tained, whereas the latter guarantees that the independent matching at the

termination of the algorithm is of the maximum size.

Lemma 2.3.31. ∂

M ∈I

and ∂

−

M ∈I

−

Proof.Letv

∈ S

be the starting vertex of P and put {(u

) | i =

1, ···,l} = P ∩ A

, where l = |P ∩ A

| and the indices are chosen so that

, ···,u

represents the order in which they appear on P .

Then

∂

M = ∂

M −{u

, ···,u

} + {v

, ···,v

Since P is a shortest path, Lemma 2.3.22 guarantees ∂

M ∈I

. The other

claim can be proven similarly.

Lemma 2.3.32. Let U ⊆

V be the set of vertices reachable from S

at the termination of the algorithm, and put U

= V

\U and U

−

= V

−

∩U .

Then (U

−

) is a cover for the independent matching problem and |M| =

)+ρ

−

). Therefore, M is a maximum independent matching.

Proof. By the deﬁnition there is no a ∈

A with ∂

a ∈ U and ∂

−

a ∈

V \ U.

In particular, there is no a ∈ A with ∂

a ∈ V

\ U

and ∂

−

a ∈ V

−

\ U

−

namely, (U

−

)isacover.

Put I

= ∂

M, J

= I

∩ U

,andI

\ J

= {u

, ···,u

}.Foreach

v ∈ U

⊆ cl

)\I

,wehaveρ

+v−u

) ≤|I

|−1fori =1, ···,m,

since there is no arc going out of U. The submodularity of ρ

implies that

+v−{u

}) ≤ ρ

+v−u

)+ρ

+v−u

)−ρ

+v) ≤|I

|−2.

Repeating such process, we obtain

+ v)=ρ

+ v −{u

, ···,u

}) ≤|I

|−m = |J

Hence, for v, v



∈ U

\ J

with v = v



+ {v, v



}) ≤ ρ

+ v)+ρ

+ v



) − ρ

) ≤|J

Repeating this we obtain ρ

) ≤|J

|, and hence ρ

)=|J

Symmetrically, put I

−

= ∂

−

M, J

−

= I

−

∩U

−

.Foreachv ∈ U

−

and

u ∈ I

−

there is no arc (v, u), and hence ρ

−

+ v −u) ≤|I

−

|−1. By a

similar argument using the submodularity of ρ

−

we obtain ρ

−

)=|J

−

Then |M| = |J

| + |J

−

| = ρ

)+ρ

−

), where the ﬁrst equality

follows from the fact that {∂

a, ∂

−

a}⊆U or {∂

a, ∂

−

a}⊆

V \ U for each

a ∈ M. Finally, we recall Lemma 2.3.26 to conclude that M is a maximum

independent matching.

To sum up, we obtain the following optimality criterion in terms of the

auxiliary graph.

2.3 Matroid 91

Theorem 2.3.33. An independent matching M is maximum if and only if

there exists no directed path from S

to S

−

A; S

−

). 2

Example 2.3.34 (Continued from Example 2.3.30). In Fig. 2.10, there ex-

ists no path from S

to S

−

. This means, by Theorem 2.3.33, that M is

a maximum independent matching. A minimum cover (U

−

)canbe

constructed as in Lemma 2.3.32. The set of vertices reachable from S

is given by U = {x

},andU

= V

\ U = {x

} and

−

= V

−

∩U = {y

} satisfy ρ

)=1andρ

−

) = 2, adding up

to |

M| =3. 2

The auxiliary graph

is useful to capture the family of all minimum

covers. A pair (U

−

) is a minimum cover if and only if U =(V

)∪U

−

gives the minimum cut capacity κ deﬁned in (2.71). Namely, the family of all

minimum covers is expressed as

{(U

−

) | U

= V

\ U, U

−

= V

−

∩ U, U ∈L

min

(κ)} (2.76)

in terms of the family of all minimum cuts

min

(κ)={U ⊆ V

∪ V

−

| κ(U ) ≤ κ(W ), ∀W ⊆ V

∪ V

−

The family L

min

(κ) forms a lattice due to the submodularity of κ (cf. Theorem

2.2.5), and by Birkhoﬀ’s representation theorem (Theorem 2.2.10) it can be

represented as a pair of a partition {V

; V

, ···,V

; V

∞

} of V

∪ V

−

and a

partial order  on {V

, ···,V

}. Let us call ({V

; V

, ···,V

; V

∞

}, )themin-

cut decomposition for the independent matching problem. This decomposition

can be computed from the auxiliary graph

on the basis of the following

fact.

Lemma 2.3.35. Let

A; S

−

) be the auxiliary graph associated

with a maximum independent matching M. The family of the minimum cuts

min

(κ) is represented in terms of

min

(κ)={U ⊆

V | S

⊆ U ⊆

V \S

−

; ∃a ∈

A : ∂

a ∈ U, ∂

−

a ∈ U}. (2.77)

Proof.ForU ⊆

V deﬁne (U

−

)=(V

\ U, V

−

∩ U ), (I

−

(∂

M,∂

−

M), and (J

−

)=(I

∩U

−

∩U

−

). By deﬁnition, κ(U) < +∞

⇐⇒ ∃a ∈ A : ∂

a ∈ U, ∂

−

a ∈ U.ForsuchU ,wehaveU ∈L

min

(κ) ⇐⇒

(i) |M| = |J

| + |J

−

|, (ii) |J

| = ρ

), and (iii) |J

−

| = ρ

−

), since

|M|≤|J

|+ |J

−

|≤ρ

)+ρ

−

). Denote by L



the right hand side of

(2.77). The proof of Lemma 2.3.32 shows L

min

(κ) ⊇L



. Conversely, suppose

U ∈L

min

(κ). The following claims show U ∈L



Claim 1: S

⊆ U ⊆

V \ S

−

.IfS

⊆ U, there exists v ∈ U

∩ S

. Then

+v ∈I

, which implies ρ

) ≥ ρ

+v)=|J

|+1, a contradiction

to (ii) above. Similarly, S

−

∩ U = ∅ contradicts (iii).

Claim 2: ∃a ∈ M

◦

: ∂

a ∈ U, ∂

−

a ∈ U. This follows from (i).

92 2. Matrix, Graph, and Matroid

Claim 3: ∃a ∈ A

: ∂

a ∈ U, ∂

−

a ∈ U. If there is a =(u, v) ∈ A

with

u ∈ U, v ∈ U, then J

+ v ⊆ I

+ v − u ∈I

, leading to a contradiction to

(ii).

Claim 4: ∃a ∈ A

−

: ∂

a ∈ U, ∂

−

a ∈ U. This is proven similarly.

The min-cut decomposition for the independent matching problem can

be found by the following procedure. It diﬀers from the one for the DM-

decomposition only in the ﬁrst step. Recall the notation

∗

−→ for the reacha-

bility by a directed path.

Algorithm for min-cut decomposition of an independent matching

problem

1. Find a maximum independent matching M.

2. Let V

= {v ∈ V

∪ V

−

| w

∗

−→ v on

for some w ∈ S

3. Let V

∞

= {v ∈ V

∪ V

−

| v

∗

−→ w on

for some w ∈ S

−

4. Let



denote the graph obtained from

by deleting the vertices V

∪

∞

(and arcs incident thereto).

5. Let V

(k =1, ···,b) be the strong components of



6. Deﬁne a partial order  on {V

| k =1, ···,b} as follows:

 V

⇐⇒ v

∗

−→ v



for some v

∈ V

and v

∈ V

Example 2.3.36. The min-cut decomposition for the independent match-

ing problem in Example 2.3.25 is obtained from the auxiliary graph

in Fig. 2.10. According to the notation in the algorithm, we have V

} and V

∞

= ∅. The subgraph



, having vertex set

} and arc set {(x

), (x

), (y

)}, is decomposed into two

strong components, V

= {y

} and V

= {x

} with V

 V

. The min-

cut decomposition is given by ({V

; V

∞

}, ). We have L

min

(κ)=

∪ V

}, with which the family of all minimum covers

is obtained as (2.76). Thus we can enumerate all the minimum covers as

−

)=({x

}, {y

}), ({x

}, {y

}), (∅, {y

}).

Remark 2.3.37. The independent matching problem is closely related to

the rank of a triple matrix product, as is pointed out by Tomizawa–Iri [317].

Consider a triple matrix product P = Q

, where T is a generic matrix

(cf. §2.1.3) and Q

(i =1, 2) are numerical matrices. Put R

=Row(Q

= Col(Q

), and ﬁrst suppose |R

| = |C

| = k. By the Cauchy–Binet

formula (Proposition 2.1.6) we have

det P =



|I|=|J|=k

±det Q

,I] · det T [I,J] · det Q

[J, C

There is no numerical cancellation in the summation above by virtue of the

assumed algebraic independence of the nonzero entries of T , and hence P is

2.3 Matroid 93

nonsingular if and only if Q

,I], T [I,J], and Q

[J, C

] are all nonsingular

for some I and J. By applying the above argument to square submatrices of

P for a general P = Q

, we see that

rank P = max{|I||rank Q

,I]=|I|

=rankT [I,J]=|J| =rankQ

[J, C

]}.

We deﬁne an independent matching problem as follows. The vertex sets V

and V

−

are the row set and the column set of T , respectively, and the arc set

A = {(i, j) | T

=0}. The matroids M

and M

−

attached to V

and V

−

respectively are the linear matroids deﬁned by Q

and the transpose of Q

Then we see from the above expression that rank P is equal to the maximum

size of an independent matching. Namely,

rank (Q

) = max{|M||M: independent matching}. (2.78)

If Q

(i =1, 2) are identity matrices, this expression reduces to (2.10). 2

The weighted version of the independent matching problem as well as the

weighted matroid intersection problem will be treated in the framework of

valuated matroids in §5.2.

2.3.6 Union

Given a bipartite graph G =(V

−

; A) and a matroid M

=(V

, I

,ρ

we can induce another matroid through matchings. Deﬁne

I⊆2

−

and

˜ρ :2

−

→ Z by

I = {∂

−

M | M: matching with ∂

M ∈I

˜ρ(X) = max{|I||I ∈

I,I ⊆ X},X⊆ V

−

It follows from the Rado–Perfect theorem (2.75) that

˜ρ(X) = min{ρ

(Γ (X



)) + |X \ X



||X



⊆ X},X⊆ V

−

. (2.79)

Theorem 2.3.38.

M =(V

−

I, ˜ρ) is a matroid with the family of indepen-

dent sets

I and the rank function ˜ρ.

Proof. We show that ˜ρ in (2.79) satisﬁes the rank axiom of a matroid. Obvi-

ously, 0 ≤ ˜ρ(X) ≤|X| and ˜ρ(X) ≤ ˜ρ(Y )forX ⊆ Y . For the submodularity

of ˜ρ we see

˜ρ(X)+˜ρ(Y ) = min



⊆X,Y



⊆Y



(Γ (X



)) + ρ

(Γ (Y



)) + |X \ X



| + |Y \Y



into which we substitute

94 2. Matrix, Graph, and Matroid

(Γ (X



)) + ρ

(Γ (Y



)) ≥ ρ

(Γ (X



) ∪ Γ (Y



)) + ρ

(Γ (X



) ∩ Γ (Y



))

≥ ρ

(Γ (X



∪ Y



)) + ρ

(Γ (X



∩ Y



))

to obtain

˜ρ(X)+˜ρ(Y ) ≥ min



⊆X,Y



⊆Y



(Γ (X



∪ Y



)) + |(X ∪ Y ) \ (X



∪ Y



+ρ

(Γ (X



∩ Y



)) + |(X ∩ Y ) \ (X



∩ Y



≥ min



⊆X∪Y



(Γ (Z



)) + |(X ∪ Y ) \ Z



+ min



⊆X∩Y



(Γ (Z



)) + |(X ∩ Y ) \ Z



=˜ρ(X ∪Y )+˜ρ(X ∩Y ).

(Itisalsopossibletoshowthat

I satisﬁes the axiom of independent sets of

a matroid by a slight modiﬁcation of the argument in the proof of Lemma

2.3.31. Remark 5.2.19 gives yet another alternative proof.)

Given two matroids M

=(V,I

,ρ

)andM

=(V,I

,ρ

) with the same

ground set V , we can deﬁne another matroid called the union of M

and M

denoted as M

∨ M

=(V,I

∨I

,ρ

∨ ρ

). The family of independent sets

∨I

is deﬁned by

∨I

= {I

∪I

| I

∈I

} = {I

∪I

| I

∈I

∩I

= ∅}

and the rank function ρ

∨ ρ

→ Z is given by

(ρ

∨ ρ

)(X) = min{ρ

(Y )+ρ

(Y )+|X \Y ||Y ⊆ X},X⊆ V. (2.80)

This construction is a special case of the induction of a matroid by a

bipartite graph explained above. Let V

and V

be disjoint copies of V and

put V

= V

∪ V

and V

−

= V . Regarding M

as being deﬁned on V

(i =1, 2), we consider M

= M

⊕ M

(direct sum) deﬁned on V

. Deﬁne

A = {(v

,v), (v

,v) | v ∈ V }, where v

∈ V

and v

∈ V

denote the copies of

v ∈ V (see Fig. 2.11). The matroid induced on V

−

from M

by the bipartite

graph (V

−

; A) coincides with (is isomorphic to) M

∨M

. The expression

(2.79) with ρ

(Γ (X



)) = ρ



)+ρ



) yields (2.80).

The rank of the union is closely related to the maximum size of a common

independent set of M

and M

∗

=(V,I

∗

,ρ

∗

) (the dual of M

). Namely,

rank (M

∨ M

) = max{|I||I ∈I

∩I

∗

} +rank(M

). (2.81)

This relation follows from (2.80) combined with Theorem 2.3.28 and (2.64).

The union operation extends to a ﬁnite number of matroids M

(V,I

,ρ

)(i ∈ T ) in an obvious way. The family of independent sets of their

union is given by

{



i∈T

| I

∈I

(i ∈ T )} = {



i∈T

| I

∈I

(i ∈ T ),I

∩ I

= ∅ (i = j)}

2.3 Matroid 95

∨ M

−

Fig. 2.11. Bipartite graph for union operation

and the rank function

i∈T

→ Z by



i∈T



(X) = min{



i∈T

(Y )+|X \Y ||Y ⊆ X},X⊆ V. (2.82)

In this connection we mention the following facts observed in Murota

[206].

Proposition 2.3.39. For a ﬁnite family of matroids M

=(V,ρ

)(i ∈ T )

on a common ground set V with rank functions ρ

, deﬁne λ(K, X) to be the

rank of X ⊆ V in the union of the partial family {M

| i ∈ K}, i.e.,

λ(K, X)=



i∈K



(X),K⊆ T,X ⊆ V.

Then it holds that

λ(K, X)+λ(L, Y ) ≥ λ(K ∪L, X ∩Y )+λ(K ∩L, X ∪Y ),K,L⊆ T ; X, Y ⊆ V.

Proof. From (2.82) we have

λ(K, X)+λ(L, Y )

= min



⊆X,Y



⊆Y



i∈K





i∈L



)+|X \ X



| + |Y \Y



Into this expression we substitute



i∈K





i∈L



)



i∈K\L





i∈K∩L

[ρ



)+ρ



)] +



i∈L\K



)

96 2. Matrix, Graph, and Matroid

≥



i∈K\L



∩ Y





i∈K∩L

[ρ



∪ Y



)+ρ



∩ Y



)] +



i∈L\K



∩ Y



)



i∈K∪L



∩ Y





i∈K∩L



∪ Y



)

to obtain

λ(K, X)+λ(L, Y ) ≥ min



⊆X,Y



⊆Y



i∈K∪L



∩ Y



)+|(X ∩ Y ) \ (X



∩ Y





i∈K∩L



∪ Y



)+|(X ∪ Y ) \ (X



∪ Y



≥ min



⊆X∩Y



i∈K∪L



)+|(X ∩ Y ) \ Z



+ min



⊆X∪Y



i∈K∩L



)+|(X ∪ Y ) \ Z



= λ(K ∪ L, X ∩ Y )+λ(K ∩ L, X ∪ Y ).

Proposition 2.3.40. For three matroids M

(i =1, 2, 3) it holds that

rank (M

∨ M

) + rank (M

) ≤ rank (M

∨ M

) + rank (M

∨ M

Proof.TakeX = V and T = {1, 2, 3} in Proposition 2.3.39. An alternative

proof is to make use of the fact that there exist disjoint I

⊆ V such

that B

is a base of M

, I

∪B

is a base of M

∨M

,andI

∪B

∪I

is a

base of M

∨ M

. Then we have rank (M

∨ M

) ≥|B

| + |I

As another application of Proposition 2.3.39 we mention the following

observation of Kung [168].

Theorem 2.3.41. For two matroids M

and M

it holds that M

∨ M

→

,where“→” means a strong map.

Proof. In Proposition 2.3.39, take K = {1, 2} and L = {1} to obtain

(ρ

∨ ρ

)(X)+ρ

(Y ) ≥ (ρ

∨ ρ

)(X ∩ Y )+ρ

(X ∪ Y ).

If X ⊇ Y , this means (ρ

∨ ρ

)(X) − (ρ

∨ ρ

)(Y ) ≥ ρ

(X) − ρ

(Y ), the

deﬁnition (2.65) of a strong map.

Remark 2.3.42. In Example 2.3.8 we have deﬁned the matroid M{U} as-

sociated with a linear subspace U . For two subspaces U

=kerA

(i =1, 2),

we have

2.3 Matroid 97

∩ U

=ker





This implies

M{U

∩ U

} = M{U

}∨M{U

}

when U

and U

are in the “general position” (in an appropriate sense). See

§4.2 for more precise accounts. 2

2.3.7 Bimatroid (Linking System)

The notion of a bimatroid was introduced ﬁrst by Schrijver [290, 291] under

the name of a linking system, and later by Kung [165] under the name bima-

troid. Just as a matroid can be deﬁned either by the basis family or by the

rank function, a bimatroid can be deﬁned either as a triple L =(S, T, Λ)of

disjoint ﬁnite sets S, T and Λ ⊆ 2

×2

(family of “linked pairs”), or equiva-

lently as a triple L =(S, T, λ) of disjoint ﬁnite sets S, T and λ :2

×2

→ Z

(“birank function”). Unless otherwise indicated, the reader is referred to

Schrijver [290, 291] for proofs not included here.

A canonical example of a bimatroid arises from a matrix. Let A be a

matrix over a ﬁeld F , and put S =Row(A)andT = Col(A). Deﬁne Λ to

be the family of all pairs (X, Y ) such that |X| = |Y | and the corresponding

submatrix A[X, Y ] is nonsingular. It is an exercise in linear algebra to show

that Λ has the following properties:

(L-1) If (X, Y ) ∈ Λ and x ∈ X, then ∃y ∈ Y such that (X \{x},Y \

{y}) ∈ Λ;

(L-2) If (X, Y ) ∈ Λ and y ∈ Y , then ∃x ∈ X such that (X \{x},Y \

{y}) ∈ Λ;

(L-3) If (X

) ∈ Λ (i =1, 2), then ∃X ⊆ S, ∃Y ⊆ T such that

(X, Y ) ∈ Λ, X

⊆ X ⊆ X

∪ X

, Y

⊆ Y ⊆ Y

∪ Y

The rank function for submatrices, deﬁned by λ(X, Y )=rankA[X, Y ]for

X ⊆ S, Y ⊆ T , has the following properties (cf. Proposition 2.1.9 for (B-3)):

(B-1) 0 ≤ λ(X, Y ) ≤ min{|X|, |Y |} for X ⊆ S and Y ⊆ T ;

(B-2) λ(X



) ≤ λ(X, Y )forX



⊆ X ⊆ S and Y



⊆ Y ⊆ T ;

(B-3) λ(X, Y )+λ(X



) ≥ λ(X ∪X



,Y ∩Y



)+λ(X ∩X



,Y ∪Y



)

for X, X



⊆ S and Y, Y



⊆ T .

The family Λ and the function λ determine each other by

λ(X, Y ) = max{|X



||(X



) ∈ Λ, X



⊆ X, Y



⊆ Y },

X ⊆ S, Y ⊆ T, (2.83)

Λ = {(X, Y ) | λ(X, Y )=|X| = |Y |,X⊆ S, Y ⊆ T }. (2.84)

With this example in mind we start a formal description of bimatroids.

98 2. Matrix, Graph, and Matroid

A bimatroid (or linking system) is a triple L =(S, T, Λ), where S and

T are disjoint ﬁnite sets, and Λ is a nonempty subset of 2

× 2

such that

(L-1)–(L-3) above are satisﬁed. We call S the row set (or exit set)andT the

column set (or entrance set)ofL, and write S =Row(L)andT = Col(L). A

member (X, Y )ofΛ is called a linked pair.

For a bimatroid L =(S, T, Λ)thebirank function (or linking function)

λ :2

×2

→ Z is deﬁned by (2.83). It can be proven that λ satisﬁes (B-1)–

(B-3) above. Conversely, a function λ :2

× 2

→ Z satisfying (B-1)–(B-3)

determines a bimatroid by (2.84). Namely, (L-1)–(L-3) for Λ ⊆ 2

× 2

are

equivalent to (B-1)–(B-3) for λ :2

×2

→ Z. Thus, a bimatroid L is deﬁned

by a triple (S, T, Λ) with the properties (L-1)–(L-3) or equivalently by a triple

(S, T, λ) with the properties (B-1)–(B-3).

It follows from (L-1) and (L-2) that |X| = |Y | if (X, Y ) ∈ Λ. A linked

pair can be enlarged monotonically, i.e.,

) ∈ Λ, |X

|≤λ(X, Y ),X

⊆ X, Y

⊆ Y

=⇒∃(X

) ∈ Λ, |X

| = λ(X, Y ),X

⊆ X

⊆ X, Y

⊆ Y

⊆ Y. (2.85)

The maximum size of a linked pair in L is referred to as the rank of L,

i.e., rank L = λ(S, T ). A bimatroid L is called trivial if rank L =0,and

nonsingular if rank L = |S| = |T |.

Example 2.3.43. Besides the canonical example from a matrix, another

example of a bimatroid is obtained from linkings/matchings in a graph. Let

G =(V,A; S, T ) be a directed graph with S and T being disjoint subsets of

V . With reference to Menger-type linkings from S to T , deﬁne Λ ⊆ 2

× 2

as follows: (X, Y ) ∈ Λ if and only if there exists a Menger-type linking of size

|X| = |Y | from X to Y . Then L =(S, T, Λ) is a bimatroid, satisfying the

conditions (L-1)–(L-3). 2

As the name suggests, bimatroids are closely related to matroids. Given

a bimatroid L =(S, T, Λ), deﬁne B⊆2

S∪T

B = {(S \ X) ∪ Y | (X, Y ) ∈ Λ}. (2.86)

Then B is the basis family of a matroid on S ∪ T with BS. See Fig. 2.12

for this correspondence in the case of a matrix, where the left submatrix with

column set S is an identity matrix. The rank function ρ :2

S∪T

→ Z of the

matroid is expressed as

ρ(X ∪ Y )=λ(S \ X, Y )+|X|,X⊆ S, Y ⊆ T

using the birank function λ. Conversely, if (S ∪T,B) is a matroid with BS

and S ∩ T = ∅, then

Λ = {(X, Y ) | X ⊆ S, Y ⊆ T,(S \ X) ∪ Y ∈B}

2.3 Matroid 99



-

[I | A]=

YS \ X



(X, Y ) ∈ Λ ⇐⇒ B ∈B

Fig. 2.12. Matroid associated with a bimatroid

is the family of linked pairs of a bimatroid. As such, the concept of bimatroids

can be regarded as a variant of matroids. Matroids are more convenient in

some cases and bimatroids are more natural in other cases.

The restriction of the associated matroid (S ∪ T,B)toT = Col(L)is

called the column matroid of L, denoted CM(L). By deﬁnition, Y ⊆ T is

independent in CM(L) if and only if (X, Y ) ∈ Λ for some X ⊆ S. Similarly,

the row matroid RM(L) is the restriction to S =Row(L) of the dual of

(S ∪T,B). Namely, X ⊆ S is independent in RM(L) if and only if (X, Y ) ∈ Λ

for some Y ⊆ T .

The underlying bipartite graph of a bimatroid L =(S, T, Λ) is a bipartite

graph G(L)=(S, T, Δ) with vertex set S ∪ T and arc set Δ ⊆ S × T such

that

(x, y)

∈ Δ ⇐⇒ ({x}, {y}) ∈ Λ.

The information represented in the underlying bipartite graph is only partial

in the sense that diﬀerent bimatroids can have the same underlying bipartite

graph. Still it carries some crucial portion of the combinatorial structure, as

pointed out by Schrijver [290, 291].

Theorem 2.3.44. Let L =(S, T, Λ) be a bimatroid and G(L)=(S, T, Δ) be

its underlying bipartite graph.

(1) If (X, Y ) ∈ Λ, there exists a perfect matching between X and Y in

G(L)=(S, T, Δ).

(2) If there exists a unique perfect matching between X and Y in G(L)=

(S, T, Δ), then (X, Y ) ∈ Λ.

Proof. When translated to statements for the matroid associated with L =

(S, T, Λ), these claims reduce respectively to the perfect-matching lemma

(Lemma 2.3.16) and the unique matching lemma (Lemma 2.3.18).