# Difficulty in understanding the proof of the lemma : "Matroids exhibit the optimal-substructure property"

I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma I give a brief description of the possible prerequisites for the lemma.

Let $$M=(S,\ell)$$ be a weighted matroid where $$S$$ is the ground set and $$\ell$$ is the family of subsets of $$S$$ called the independent subsets of $$S$$. Let $$w:S\rightarrow\mathbb{R}$$ be the corresponding weight function ($$w$$ is strictly positive).

Let us have an algorithm which finds an optimal subset of $$M$$ using greedy method as:

$$\text{G}{\scriptstyle{\text{REEDY}}}(M,w):$$

$$1\quad A\leftarrow\phi$$

$$2\quad \text{sort S[M] into monotonically decreasing order by weight w}$$

$$3\quad \text{for each x\in S[M], taken in monotonically decreasing order by weight w(x)}$$

$$4\quad\quad \text{do if A\cup\{x\} \in \ell[M]}$$

$$5\quad\quad\quad\text{then A\leftarrow A\cup \{x\}}$$

$$6\quad \text{return A}$$

I was having a problem in understanding a step in the proof of the lemma below.

Lemma: (Matroids exhibit the optimal-substructure property)

Let $$x$$ be the first element of $$S$$ chosen by $$\text{G}{\scriptstyle{\text{REEDY}}}$$ for the weighted matroid $$M = (S, \ell)$$. The remaining problem of finding a maximum-weight independent subset containing $$x$$ reduces to finding a maximum-weight independent subset of the weighted matroid $$M' = (S', \ell')$$, where

$$S' = \{y\in S:\{x,y\}\in \ell\}$$ ,

$$\ell' = \{В \subseteq S - \{x\} : В \cup \{x\} \in \ell\}$$ ,

and the weight function for $$M'$$ is the weight function for $$M$$, restricted to $$S'$$. (We call $$M'$$ the contraction of $$M$$ by the element $$x$$.)

Proof:

1. If $$A$$ is any maximum-weight independent subset of $$M$$ containing $$x$$, then $$A' = A - \{x\}$$ is an independent subset of $$M'$$.

2. Conversely, any independent subset $$A'$$ of $$M'$$ yields an independent subset $$A = A'\cup\{x\}$$ of $$M$$.

3. We have in both cases $$w(A) = w(A') + w(x)$$.

4. Since we have in both cases that $$w(A) = w(A') + w(x)$$, a maximum-weight solution in $$M$$ containing $$x$$ yields a maximum-weight solution in $$M'$$, and vice versa.

I could understand $$(1),(2),(3)$$. But I could not get how the line $$(4)$$ was arrived in the proof from $$(1),(2),(3)$$, especially the part in bold-italics. Could anyone please make it clear to me?

The adjective "maximum-weight" should not appear in item (1) in that proof of the lemma. This is a minor bug of that famous book.

To be fully clear, item (1) should have been the following.

1. If $$A$$ is any independent subset of $$M$$ containing $$x$$, then $$A' = A - \{x\}$$ is an independent subset of $$M'$$.

With item (1) corrected, item (4) follows naturally from item (1), (2) and (3). Here is more detail.

"A maximum-weight solution in $$M$$ containing $$x$$ yields a maximum-weight solution in $$M'$$."

Note that "solution" is just a shorthand for "independent set". Let us prove the proposition above.

Suppose $$A$$ is a maximum-weight solution in $$M$$. Then $$A$$ yields $$A'=A-\{x\}$$, which is a solution in $$M'$$ according to item (1). (The previous version of item (1) works as well.)

Given any solution $$B'$$ in $$M'$$, let $$B=B'\cup\{x\}$$, which is a solution in $$M$$ according to item (2).

Item (3) tells us $$w(A)=w(A')+w(x),$$ and $$w(B)=w(B')+w(x).$$ Since $$A$$ has maximum weight in $$M$$, we have $$w(A)\ge w(B)$$, i.e., $$w(A')+w(x)\ge w(B')+w(x).$$ Cancelling $$w(x)$$ from both sides, we obtain $$w(A')\ge w(B'),$$ which says $$A'$$ is a maximum-weight solution in $$M'$$. $$\checkmark$$

A maximum-weight solution in $$M'$$ yields a maximum-weight solution in $$M$$ containing $$x$$.

The other direction, as stated above, can be proved similarly. Here is the proof.

Suppose $$B'$$ is a maximum-weight solution in $$M'$$. Then $$B'$$ yields $$B=B'\cup\{x\}$$, which is a solution in $$M$$ according to item (2).

Given any solution $$A$$ in $$M$$, let $$A'=A-\{x\}$$, which is a solution in $$M'$$ according to (the corrected version of) item (1).

Since $$B'$$ has maximum weight in $$M'$$, we have $$w(B')\ge w(A')$$. Adding $$w(x)$$ to both sides, we obtain, $$w(B')+w(x)\ge w(A')+w(x).$$

Item (3) tells us $$w(A)=w(A')+w(x),$$ and $$w(B)=w(B')+w(x).$$ So the inequality above is the same as $$w(B)\ge w(A),$$

which says $$B$$ is a maximum-weight solution in $$M$$. $$\checkmark$$

• Can you please tell me the meaning of the convention about "yielding rule" :$B'\mapsto B'\cup\{x\}$ (and $A\mapsto A-\{x\}$) which you have mentioned in the last part. (I understood from your way of answering the first direction, as how to symmetrically work in the other direction, we shall assume a max-weight independent set $A'$ of $M'$ and again an arbitrary independent set $B'$ of $M'$ and then proceed in a similar manner to show $w(A)\geq w(B)$ ) Jul 7, 2020 at 14:24
• @AbhishekGhosh Please check my update. Jul 7, 2020 at 14:51
• thank you for you help... Jul 7, 2020 at 14:55
• @AbhishekGhosh Apparently the other answer in its second case is proving something different from the lemma. There is no need to read that part. Jul 7, 2020 at 15:22
• Okay thanks for the guidance as well. Jul 7, 2020 at 16:06

For convenience:

$$W(P) = \sum_{p\in P} \omega (p)$$

First case: $$A$$ is max. independent set of $$M$$

Now let's assume $$A'$$ wasn't the max. independent set of $$M'$$. Thus another max. independent set $$H\in l'$$ must exist. $$W(A') < W(H)$$ Since every independent set in $$l'$$ has a corresponding set in $$l$$ including $$x$$ we can conclude $$H\cup\{x\}\in l$$ and hence: $$W(A') + \omega(x)< W(H)+\omega(x) \Rightarrow W(A'\cup\{x\}) < W(H\cup\{x\})$$ But $$A'\cup\{x\} = A$$ which is a contradiction since $$A$$ is the max. independent set of $$M$$.

The other way around is a bit trickier.
Second case: $$A'$$ is max. independent set of $$M'$$.

Now we assume $$A$$ wasn't the max. independent set of M. This would imply the existence of a set $$H\in l$$ with $$W(H) > W(A)$$. Now we can apply the hereditary property to $$A$$ and conclude that $$\{x\}\in l$$. To $$H$$ and $$Z = \{x\}$$ we can now apply the independent set exchange property repeatedly to augment $$Z$$ to $$Z'$$ until it contains all elements in $$H$$ except its smallest. Thus
$$Z' = Z \cup H - \{\text{argmin}_{h\in H}\{\omega(h)\}\}$$ $$W(Z') \geq W(H)$$. Since $$Z'$$ contains $$x$$ and $$W(Z')>W(A) \Rightarrow W(Z'-\{x\}) > W(A')$$ we have a contradiction (we assumed A' was max. set of M').