Murota K. Matrices and Matroids for Systems Analysis

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

70 2. Matrix, Graph, and Matroid

Theorem 2.2.35. Let N =(V,A, γ) be a network with γ : A → R.

(1) There exists p : V → R such that

γ(a)+p(∂

a) − p(∂

−

a) ≥ 0(∀ a ∈ A) (2.57)

if and only if there exists no (directed) cycle of negative length with respect

to γ.Moreover,ifγ is integer-valued, we can take integer-valued p.

(2) There exists p : V → R such that

γ(a)+p(∂

a) − p(∂

−

a)=0 (∀ a ∈ A) (2.58)

if and only if



a∈A

(a)γ(a)=0 (∀ C : circuit in N), (2.59)

where χ

(a)=1or −1 according to whether a ∈ A is contained in C in the

positive or negative direction

(and χ

(a)=0if a ∈ A is not contained in

C). Moreover, if γ is integer-valued, we can take integer-valued p. 2

Next we turn to the weighted bipartite matching problem.LetG =

−

; A) be a bipartite graph and w : A → R be a weight function.

The weight of a matching M is deﬁned to be

w(M)=



a∈M

w(a).

Given a nonnegative integer k,themaximum weight k-matching problem is

to ﬁnd a k-matching M (i.e., a matching M of size k) that maximizes the

weight w(M). A k-matching that attains the maximum weight is called an

optimal k-matching.

This problem can be formulated as the minimum cost ﬂow problem in a

network N

A, c, c,γ) with

V = V

∪ V

−

∪{s

−

A = A ∪{(s

,u) | u ∈ V

}∪{(v, s

−

) | v ∈ V

−

}∪{(s

−

)},

and

c, c, γ given by

c(a) c(a) γ(a)

a ∈ A 0+∞−w(a)

a =(s

,u)(u ∈ V

) −∞ 10

a =(v, s

−

)(v ∈ V

−

) −∞ 10

a =(s

−

) kk 0

Then the optimality criterion for N

is translated into the following theorem

for the weighted matching problem on G =(V

−

; A).

It is understood that a circuit in N (i.e., a circuit of the underlying undirected

graph) is endowed with a direction.

2.3 Matroid 71

Theorem 2.2.36. A k-matching M in G =(V

−

; A) is optimal (maxi-

mum) with respect to w : A → R if and only if there exist a “potential” func-

tion p : V

∪V

−

→ R andascalarq ∈ R such that p(v) ≥ 0(v ∈ V

∪V

−

{v ∈ V

∪ V

−

| p(v) > 0}⊆∂M,and

w(u, v) − p(u) − p(v) − q



=0 ((u, v) ∈ M )

≤ 0((u, v) ∈ A)

(2.60)

where w(u, v) means w(a) for a =(u, v) ∈ A. Moreover, if the weight w is

integer-valued, we can choose p and q to be integer-valued.

Proof. Note ﬁrst that an integral feasible ﬂow in N

corresponds to a k-

matching in G. Let ˜p :

V → R be the potential function in Theorem 2.2.33,

and put p(u)=˜p(u) − ˜p(s

)(u ∈ V

), p(v)=˜p(s

−

) − ˜p(v)(v ∈ V

−

and q =˜p(s

) − ˜p(s

−

). Then (2.54) and (2.55) for ˜p are equivalent to the

conditions on p and q above.

2.3 Matroid

2.3.1 From Matrix to Matroid

As the name shows, the concept of a matroid is a combinatorial abstraction

of matrices with respect to linear independence. The abstract deﬁnition of a

matroid, to be given in §2.3.2, is preceded here by linear algebraic motivations

explained by means of a concrete example.

Take a 3 ×5 matrix

A =

12345

10010

01011

00101

of which the columns are indexed by V = Col(A)={1, ···, 5}, and consider

linear dependence/independence among column vectors, say {a

| v ∈ V }.

A subset I ⊆ V is said to be independent if the corresponding subfamily

| v ∈ I} of column vectors is linearly independent. Denote by I⊆2

the family of independent subsets, i.e.,

I = {I ⊆ V |{a

| v ∈ I} is linearly independent}, (2.61)

where

(I-1) ∅∈I

by convention. For the matrix A above an inspection shows

72 2. Matrix, Graph, and Matroid

I = {∅, {1}, {2}, {3}, {4}, {5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4},

{2, 5}, {3, 4}, {3, 5}, {4, 5}, {1, 2, 3}, {1, 2, 5}, {

1, 3, 4}, {1, 3, 5},

{1, 4, 5}, {2, 3, 4}, {2, 4, 5}, {3, 4, 5}}.

Obviously, it holds that

(I-2) I ⊆ J ∈I =⇒ I ∈I,

since a subset of an independent subset is also independent. A nontrivial

property of I is described by

(I-3) I,J ∈I, |I| < |J| =⇒ I ∪{v}∈Ifor some v ∈ J \I.

For I = {1, 2} and J = {2, 3, 4}, for instance, we can take v = 3 to obtain

I ∪{v} = {1, 2, 3}∈I, whereas v = 4 leads to I ∪{v} = {1, 2, 4} ∈I.Itisa

good exercise in linear algebra (and hence left to the reader) to prove (I-3) in

general, where I is deﬁned by (2.61) for a given matrix A =(a

| v ∈ V ). In

this way a matrix gives rise to a pair (V,I) with the properties (I-1), (I-2),

(I-3).

Since I satisﬁes (I-2), it is redundant to enumerate all the members of I,

and only the maximal members of I (maximal with respect to set inclusion)

suﬃce. In our example, the family B of the maximal members of I is given

B={{1, 2, 3}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 4, 5}, {3, 4, 5}},

which is the family of column bases of the matrix A. The family B satisﬁes

(BM

−

)ForB,B



∈Band for u ∈ B \ B



, there exists v ∈ B



\ B

such that B −u + v ∈B,

where B − u + v is a short-hand notation for (B \{u}) ∪{v}.Thisisa

consequence of the Grassmann–Pl¨ucker identity (see Remark 2.1.8 for (BM

which implies (BM

−

)). For B = {1, 2, 3}, B



= {3, 4, 5} and u =1,for

example, we can take v = 4 to obtain B − u + v = {2, 3, 4}∈B, whereas

v = 5 yields B − u + v = {2, 3, 5} ∈B. Thus a matrix gives rise to a pair

(V,B) with the property (BM

−

The linear independence structure of column vectors can be represented

also by the rank function ρ :2

→ Z deﬁned by

ρ(X)=rankA[Row(A),X],X⊆ V.

The following two properties of ρ are obvious:

(R-1) 0 ≤ ρ(X) ≤|X|,

(R-2) X ⊆ Y =⇒ ρ(X) ≤ ρ(Y ).

The key property of ρ is the submodularity:

(R-3) ρ(X)+ρ(Y ) ≥ ρ(X ∪Y )+ρ(X ∩ Y ),X,Y⊆ V ,

2.3 Matroid 73

which has been shown in Proposition 2.1.9(1). Thus a matrix yields a pair

(V,ρ) with the properties (R-1), (R-2), (R-3).

To sum up, a matrix gives rise to (V, I), (V, B) and (V,ρ), each represent-

ing (some aspects of) the linear independence structure of column vectors.

The conditions (I-1), (I-2), (I-3) for I,(BM

−

)forB, and (R-1), (R-2), (R-3)

for ρ are stated without reference to the original matrix, and are meaningful

by themselves as conditions on a family I⊆2

, a family B⊆2

, and a

set function ρ :2

→ Z, respectively. It turns out that these three abstract

structures, (V,I), (V,B) and (V,ρ), are equivalent (in an appropriate sense),

and therefore deﬁne one and the same combinatorial structure underlying

linear independence. This structure is named a matroid.

We are now ready to formally deﬁne a matroid in terms of abstract axioms.

2.3.2 Basic Concepts

A matroid can be deﬁned in many diﬀerent ways. For our purpose it is con-

venient to feature independent sets, bases, and the rank function. Statements

marked with

((P))

are given proofs at the end of §2.3.2.

A matroid is a pair M =(V,I) of a ﬁnite set V and a collection I of

subsets of V such that

(I-1) ∅∈I,

(I-2) I ⊆ J ∈I =⇒ I ∈I,

(I-3) I,J ∈I, |I| < |J| =⇒ I ∪{v}∈Ifor some v ∈ J \I.

The set V is called the ground set and I ∈Ian independent set; accordingly,

I is the family of independent sets.

Denote by B the family of the maximal members of I (maximal with

respect to set inclusion); namely, B = max I in short. The family B

satisﬁes

((P1))

(BM

−

)ForB,B



∈Band for u ∈ B \ B



, there exists v ∈ B



\ B

such that B −u + v ∈B.

We call (BM

−

)the(one-sided) basis exchange property. A member of B is

called a base. The size of a base is uniquely determined

((P2))

and is called the

rank of M, denoted as rank M; i.e.,

rank M = |B| = max{|I||I ∈I} for B ∈B.

Conversely

((P3))

, a nonempty family B of subsets of V forms the basis family

of a matroid if it satisﬁes the axiom (BM

−

); the matroid M =(V, I) is given

I = {I ⊆ V | I ⊆ B ∈B}. (2.62)

For X ⊆ V ,therank ρ(X)ofX is deﬁned as the uniquely determined

((P4))

cardinality of a maximal independent set contained in X.Thatis,

74 2. Matrix, Graph, and Matroid

ρ(X) = max{|I||I ⊆ X, I ∈I}.

The rank function ρ :2

→ Z satisﬁes

((P5))

the conditions:

(R-1) 0 ≤ ρ(X) ≤|X|,

(R-2) X ⊆ Y =⇒ ρ(X) ≤ ρ(Y ),

(R-3) ρ(X)+ρ(Y ) ≥ ρ(X ∪Y )+ρ(X ∩ Y ),X,Y⊆ V .

The property (R-3) is the submodularity. Conversely

((P6))

, a function ρ :

→ Z satisfying these properties is the rank function of a matroid; the

matroid M =(V, I) is given by

I = {I ⊆ V | ρ(I)=|I|}.

To sum up, a matroid can be deﬁned as (V,I) with (I-1)–(I-3), (V, B)

with (BM

−

), or (V,ρ) with (R-1)–(R-3). Given one of these, we can derive

the other two as follows:

Given Deﬁne

(V,I) ⇒B= max I,ρ(X) = max{|I||I ⊆ X, I ∈I}

(V,B) ⇒I= {I | I ⊆ B ∈B},ρ(X) = max{|X ∩B||B ∈B}

(V,ρ) ⇒I= {I ⊆ V | ρ(I)=|I|}, B = {B ⊆ V | ρ(B)=|B| = ρ(V )}

We use notations M =(V,B, I,ρ), M =(V,B,ρ), etc., whenever convenient.

A subset X ⊆ V not belonging to I is called a dependent set, and a

minimal dependent set (minimal with respect to set inclusion) is a circuit.

We call X ⊆ V a spanning set if it contains a base. For X ⊆ V ,theclosure

cl(X)ofX is deﬁned by

cl(X)={v ∈ V | ρ(X ∪{v})=ρ(X)}. (2.63)

It is also possible to characterize a matroid in terms of the family of dependent

sets, the family of circuits, the family of spanning sets, or the closure function.

An element of V not contained in any base is called a loop, whereas an

element contained in every base is a coloop. A pair of elements of V , neither of

which is a loop, are said to be in parallel, if there exists no base that contains

both of them. A pair of elements of V , neither of which is a coloop, are said

to be in series, if there exists no base that is disjoint from them. The relation

of being in parallel is transitive in that if both {u, v} and {v, w} are parallel

pairs, then {u, w} is also a parallel pair. The relation of being in series is also

transitive.

Given a matroid M =(V, B, I,ρ), we can derive a number of matroids,

as follows.

The dual of M, denoted M

∗

, is a matroid on V of which the basis family

∗

is given by

∗

= {V \ B | B ∈B}.

In fact, B

∗

satisﬁes the exchange property (BM

−

) because (BM

−

)forB

∗

tantamount to the condition

2.3 Matroid 75

(BM

)ForB,B



∈Band for v ∈ B



\ B, there exists u ∈ B \ B



such that B −u + v ∈B,

for B, and it can be shown (cf. Theorem 2.3.14) that (BM

)forB is equivalent

to (BM

−

)forB. Note that (BM

) is not identical with (BM

−

). The rank

function ρ

∗

of M

∗

is given by

∗

(X)=|X| + ρ(V \ X) − ρ(V ),X⊆ V. (2.64)

The restriction of M to U (⊆ V ), denoted as M

, is a matroid on U in

which X (⊆ U) is independent if and only if X is independent in M. We also

say that M

is obtained from M by deleting the elements of V \U. The rank

function ρ

of M

is simply the restriction of ρ to U, i.e., ρ

(X)=ρ(X)for

X ⊆ U.

The contraction of M to U (⊆ V ), denoted as M

, is a matroid on U in

which X (⊆ U ) is independent if and only if X ∪ B is independent in M

for a base B of M

V \U

. We also say that M

is obtained by contracting the

elements of V \U. The rank function ρ

of M

is given by

(X)=ρ(X ∪ (V \ U )) − ρ(V \ U),X⊆ U.

We have (M

)

∗

=(M

∗

)

The truncation of M to k, where k ≤ rank M, is a matroid on V in which

X (⊆ V ) is a base if and only if |X| = k and X is independent in M.The

rank function is given by min(ρ(X),k).

The elongation of M to l, where l ≥ rank M, is a matroid on V in which

X (⊆ V ) is a base if and only if |X| = l and X is spanning in M. The dual

of the truncation of M to k coincides with the elongation of M

∗

to |V |−k,

where k ≤ rank M.

For two matroids M

and M

on disjoint ground sets V

and V

, respec-

tively, their direct sum, denoted as M

⊕ M

, is a matroid on V

∪ V

which X (⊆ V

∪ V

) is independent if and only if X ∩ V

is independent in

for i =1, 2. Besides this rather trivial operation, there is another opera-

tion of “adding” two matroids, called union operation, which will be treated

in §2.3.6.

A matroid M

=(V,ρ

) is said to be a strong quotient of another matroid

=(V,ρ

)if

(X) − ρ

(Y ) ≥ ρ

(X) − ρ

(Y ),X⊇ Y. (2.65)

If this is the case, we write M

→ M

and say that M

→ M

is a strong

map. Obviously, rank M

≥ rank M

if M

→ M

Lemma 2.3.1. If M

→ M

and rank M

=rankM

, then M

= M

Proof. The inequality (2.65) with Y = ∅ gives ρ

(X) ≥ ρ

(X), whereas (2.65)

with X = V yields ρ

(Y ) ≤ ρ

(Y ) since ρ

(V )=ρ

(V ). Hence ρ

= ρ

76 2. Matrix, Graph, and Matroid

Proofs of the Marked Statements. Proofs of the marked statements are

sketched below.

((P1)) For B,B



∈B= max I,wehave|B| = |B



| since |B| < |B



would imply by (I-3) the existence of v ∈ B



\ B such that B ∪{v}∈I,

a contradiction to the maximality of B. Then application of (I-3) to I =

B − u ∈Iand J = B



∈Iyields (BM

−

((P2)) We show (BM

−

) ⇒|B| = |B



|.ForB, B



∈B, put B

= B − u +

v ∈Busing u ∈ B \ B



and v ∈ B



\ B in (BM

−

). Then |B

| = |B| and

\ B



| = |B \ B



|−1. Applying the same argument to (B



) we obtain

∈Bwith |B

| = |B

| = |B| and |B

\ B



| = |B

\ B



|−1=|B \ B



|−2.

Repeating this we can prove |B



| = |B|.

((P3)) (I-1) and (I-2) are obviously satisﬁed by I of (2.62). To show (I-3)

suppose that I ⊆ B

∈B, J ⊆ B

∈Band |I| < |J|, where |B

∩ B

| is

maximized over such B

and B

. Then B

\ I ⊆ B

, since otherwise there

exist u ∈ (B

)\I and v ∈ B

, for which B



= B

−u+v ∈B, I ⊆ B



and |B



∩B

| = |B

∩B

|+ 1 (a contradiction). Since |B

| = |B

| by ((P2)),

it follows from |B

| = |I|+ |B

\I| = |I|−|J|+ |(B

\I) ∩J|+ |(B

\I) ∪J|≤

|I|−|J| + |(B

\ I) ∩ J| + |B

| that |(B

\ I) ∩ J|≥|J|−|I| > 0, i.e.,

∃v ∈ (B

\ I) ∩ J. For this v we have I ∪{v}⊆B

, and hence I ∪{v}∈I.

((P4)) Let I and J be two maximal independent sets contained in X.

If |I| < |J|, then (I-3) implies I ∪{v} is also a maximal independent set

contained in X, a contradiction.

((P5)) (R-1) and (R-2) are obviously satisﬁed. To show (R-3) ﬁrst observe

from ((P4)) that for X

⊆ X

, there exist independent sets I

⊆ X

(i =1, 2, 3) such that I

⊆ I

and |I

| = ρ(X

)(i =1, 2, 3). Applying

this fact to X

= X ∩ Y , X

= X, X

= X ∪ Y we obtain J

, J

such that J

⊆ X ∩ Y , J

⊆ X \ Y , J

⊆ Y \ X, J

∈I, J

∪ J

∈I,

∪J

∈I, |J

| = ρ(X∩Y ), |J

|+|J

| = ρ(X), |J

|+|J

| = ρ(X∪Y ).

Combination of these equalities with an inequality ρ(Y ) ≥|J

| + |J

| yields

the submodularity (R-3).

((P6)) (I-1) is obvious. For (I-2) suppose that I ⊆ J and ρ(J)=|J|.By

(R-1) we have |I|≥ρ(I)and|J \I|≥ρ(J \I). Addition of these, combined by

(R-3), yields |J|≥ρ(I)+ρ(J \ I) ≥ ρ(∅)+ρ(J)=|J|. Hence |I| = ρ(I). For

(I-3) it suﬃces to show [ρ(I ∪{v})=ρ(I) for all v ∈ J \ I ⇒ ρ(J) ≤ ρ(I)]

for I,J ∈I.Let

, ···,v

be the elements of J \I. It follows from (R-2) and

(R-3) that ρ(I) ≤ ρ(I ∪{v

}) ≤ ρ(I ∪{v

})+ρ(I ∪{v

}) − ρ(I)=ρ(I).

Hence ρ(I ∪{v

})=ρ(I). Similarly, ρ(I) ≤ ρ(I ∪{v

}) ≤ ρ(I ∪

})+ρ(I ∪{v

}) − ρ(I)=ρ(I). Continuing in this way, we arrive at

ρ(J) ≤ ρ(I ∪{v

, ···,v

})=ρ(I).

Notes. The concept of a matroid was introduced by Whitney [340] and

the earlier key papers are compiled in Kung [166]. For topics on matroids

and submodular functions not covered in this book, the reader is referred to

Bixby–Cunningham [13], Edmonds [68], Fujishige [82], Lawler [171], Oxley

[259], Topkis [319], Welsh [333], and White [336, 337, 338] for theory, and to

2.3 Matroid 77

Iri [127, 128], Iri–Fujishige [130], Lee–Ryan [172], Murota [204], and Recski

[277] for applications.

2.3.3 Examples

Example 2.3.2 (Free matroid). Let V be a ﬁnite set. Put I =2

and

B = {V }. This is called the free matroid on V , in which every subset of V is

independent. We have ρ(X)=|X| for X ⊆ V . 2

Example 2.3.3 (Uniform matroid). Let V be a ﬁnite set and r ≤|V |

be an integer. Put I = {I ⊆ V ||I|≤r} and B = {B ⊆ V ||B| = r}. This

is called the uniform matroid of rank r. The uniform matroid of rank |V | is

the free matroid, and that of rank zero is called the trivial matroid. 2

Example 2.3.4 (Partition matroid). Let (V

| i ∈ P ) be a partition of a

ﬁnite set V , i.e.,



i∈P

= V and V

∩ V

= ∅ for i = j. Then I = {I ⊆ V |

|I ∩ V

|≤1(∀i ∈ P )} forms the family of independent sets of a matroid on

V , called a partition matroid. 2

Example 2.3.5 (Transversal matroid). For a bipartite graph G =

−

; A)letI be the family of subsets of V

that can be matched

into V

−

; i.e., a subset I of V

belongs to I if and only if there exists a

matching that covers I (see §2.2.3 for matchings). Then I satisﬁes (I-1)–

(I-3), and deﬁnes a matroid on V

. A matroid obtained in this manner

is called a transversal matroid. The uniform matroid of rank r on V is a

transversal matroid deﬁned by a complete bipartite graph with V

= V ,

−

| = r and A = {(v, i) | v ∈ V,i ∈ V

−

}. The partition matroid on V

deﬁned by (V

| i ∈ P ) is a transversal matroid with V

= V , V

−

= P and

A = {(v, i) | v ∈ V

,i∈ P }. 2

Example 2.3.6 (Gammoid). Let G =(W, A; S, T ) be a directed graph

with vertex set W ,arcsetA and disjoint entrance S and exit T (S ⊆ W ,

T ⊆ W ). Denote by I the family of subsets of S that can be linked into T ;

i.e., a subset I of S belongs to I if and only if there exists a Menger-type

(vertex-disjoint) linking of size |I| from I to a subset of T (see §2.2.4 for

linkings). Then I satisﬁes (I-1)–(I-3), and deﬁnes a matroid on S. A matroid

obtained in this manner is called a gammoid.IfG is a bipartite graph, the

gammoid deﬁned by G is a transversal matroid. 2

Example 2.3.7 (Matching matroid). Let G =(V,A) be a graph with

vertex set V and arc set A. Denote by I the family of subsets of V

that can be covered by some matching.

That is, I = {I ⊆ V | I ⊆

∂M for some matching M}. Then I satisﬁes (I-1)–(I-3), and deﬁnes a ma-

troid on V . A matroid obtained in this manner is called a matching matroid.

A matching in a nonbipartite graph is a subset of arcs no two of which share a

common vertex incident to them.

78 2. Matrix, Graph, and Matroid

Example 2.3.8 (Linear matroid). Let A be a matrix over a ﬁeld F ,

and V be the set of the column vectors of A. Linear independence among

the column vectors of A deﬁnes a matroid on V , which will be denoted by

M(A). Namely, I ⊆ V is independent in M(A) if and only if the column

vectors in I are linearly independent. The rank function ρ of M(A) is given

by (2.6). A matroid that can be obtained in this way is called a linear matroid

representable over F . If the matrix A is given explicitly, the matroid is said

to be represented over F .

A linear subspace U of F

deﬁnes a matroid, denoted as M{U },inwhich

I(⊆ V ) is independent if and only if there exists no vector x =(x(v) | v ∈

V ) ∈ U \{0} such that {v ∈ V | x(v) =0}⊆I. This matroid can be linearly

represented by a matrix A such that U =kerA; namely, M{U } = M(A)if

U =kerA. This shows

rank [M{U}] + dim U = |V |.

The orthogonal complement U

⊥

of U (or, more precisely, the subspace of the

dual space of F

consisting of elements that annihilate on U) corresponds to

the matroid dual to M{U }, i.e., M{U

⊥

} = M{U}

∗

. For two nested subspaces

⊆ U

it holds that M{U

}→M{U

}, where “→” denotes a strong map.

To see this we may assume U

=kerA[I

,V]andU

=kerA[I

,V]fora

matrix A and I

⊇ I

. Then Proposition 2.1.9(2) implies (2.65) for ρ

(J)=

rank A[I

,J], i =1, 2. Hence we may interpret the strong map relation as a

combinatorial abstraction of the nesting of linear subspaces. 2

Example 2.3.9 (Graphic matroid). Let G =(V,A) be a graph with

vertex set V and arc set A. Deﬁne I to be the family of subsets of A that

contain no (undirected) cycles in G. Then I satisﬁes (I-1)–(I-3) and deﬁnes

a matroid on A. This matroid coincides with the linear matroid deﬁned by

the incidence matrix of G. A matroid obtained in this way is called a graphic

matroid. 2

Example 2.3.10 (Algebraic matroid). Let F be an extension ﬁeld of a

ﬁeld K,andV a ﬁnite subset of F . Deﬁne I to be the family of subsets of V

that are algebraically independent over K (see §2.1.1 for algebraic indepen-

dence). Then I satisﬁes (I-1)–(I-3) and deﬁnes a matroid on V . A matroid

obtained in this way is called an algebraic matroid. The rank function is given

by the degree of transcendency of the extension ﬁeld K(X)overK:

ρ(X) = dim

K(X),X⊆ V.

2.3.4 Basis Exchange Properties

We consider a number of basis exchange properties in a matroid. First recall

2.3 Matroid 79

(BM

−

)ForB,B



∈Band for u ∈ B \ B



, there exists v ∈ B



\ B

such that B −u + v ∈B,

which characterizes the basis family B of a matroid (see §2.3.2).

We have observed in Remark 2.1.8 that the Grassmann–Pl¨ucker identity

(Proposition 2.1.4) implies a stronger exchange property:

(BM

)ForB,B



∈Band for u ∈ B \ B



, there exists v ∈ B



\ B

such that B −u + v ∈Band B



+ u − v ∈B,

for a linear matroid (cf. Example 2.3.8). The following lemma (Brualdi [23])

claims that (BM

) is implied by (BM

−

) in general, and therefore satisﬁed

by any matroid. (BM

) is often called the simultaneous exchange property.

Lemma 2.3.11. For B⊆2

, (BM

−

)=⇒ (BM

Proof. First note that (BM

−

) implies

(BM

+loc

)ForB,B



∈Bwith |B \ B



| = 2 and for v ∈ B



\ B, there

exists u ∈ B \ B



such that B −u + v ∈B.

Deﬁne

D = {(B,B



) | B,B



∈B, ∃u

∗

∈ B \ B



, ∀v ∈ B



\ B :

B − u

∗

+ v ∈B, or B



+ u

∗

− v ∈B},

which denotes the set of pairs (B, B



) for which the simultaneous exchange

(BM

) fails. We want to show D = ∅.

To the contrary suppose that D = ∅.Take(B, B



) ∈Dsuch that |B \B



is minimum, and let u

∗

∈ B \ B



be as in the deﬁnition of D.Takeany

∈ (B \ B



) \{u

∗

}, which is possible since |B \B



|≥2. Deﬁne

X = {v ∈ B



\ B | B



+ u

∗

− v ∈B},Y= {v ∈ B



\ B | B − u

+ v ∈B},

where Y = ∅ by (BM

−

). If X ∩Y = ∅, take any v

∈ X ∩ Y ; otherwise take

any v

∈ Y .WehaveB

≡ B − u

+ v

∈Bby v

∈ Y .

Claim: (B



) ∈D.

To prove this claim it suﬃces to show



+ u

∗

− v ∈B,v ∈ B



\ B

=⇒ B

≡ B

− u

∗

+ v ∈B.

Note that B − u

∗

+ v ∈Bby the choice of u

∗

.IncaseofX ∩ Y = ∅,we

have B



+ u

∗

− v

∈Bby v

∈ X, and therefore B − u

∗

+ v

∈B. Then

the contraposition of (BM

−

)appliedto(B, B

)showsB

∈B, since B ∈B,

B − u

∗

+ v

∈Band B − u

∗

+ v ∈B. In the remaining case of X ∩ Y = ∅,

since v ∈ X,wehavev ∈ Y , i.e., B −u

+ v ∈B. Then the contraposition of

(BM

+loc

) applied to (B,B

)showsB

∈B, since B ∈B, B −u

+ v ∈Band

B − u

∗

+ v ∈B. Thus the above claim has been proven.