Skip to content

16.4 Matroids and greedy methods

16.4-1

Show that $(S, \mathcal I_k)$ is a matroid, where $S$ is any finite set and $\mathcal I_k$ is the set of all subsets of $S$ of size at most $k$, where $k \le |S|$.

The first condition that $S$ is a finite set is a given. To prove the second condition we assume that $k \ge 0$, this gets us that $\mathcal I_k$ is nonempty. Also, to prove the hereditary property, suppose $A \in \mathcal I_k$ this means that $|A| \le k$. Then, if $B \subseteq A$, this means that $|B| \le |A| \le k$, so $B \in \mathcal I_k$. Lastly, we prove the exchange property by letting $A, B \in \mathcal I_k$ be such that $|A| < |B|$. Then, we can pick any element $x \in B \backslash A$, then,

$$|A \cup {x}| = |A| + 1 \le |B| \le k,$$

so, we can extend $A$ to $A \cup \{x\} \in \mathcal I_k$.

16.4-2 $\star$

Given an $m \times n$ matrix $T$ over some field (such as the reals), show that $(S, \mathcal I)$ is a matroid, where $S$ is the set of columns of $T$ and $A \in \mathcal I$ if and only if the columns in $A$ are linearly independent.

We need to show three things to prove that $(S, \mathcal I)$ is a matroid:

  1. $S$ is finite. That's because $S$ is the set of $m$ columns of matrix $T$.
  2. $\mathcal I$ is hereditary. That's because if $B \in \mathcal I$, then the colums in $B$ are linearly independent. If $A \subseteq B$, then the columns of $A$ must also be linearly independent, and so $A \in I$.
  3. $(S, \mathcal I)$ satisfies the exchange property. To see why, let us suppose that $A, B \in \mathcal I$ and $|A| < |B|$.

    We will use the following properties of matrices:

    • The rank of a matrix is the number of columns in a maximal set of linearly independent columns. The rank is also equal to the dimension of the column space of the matrix.
    • If the column space of matrix $B$ is a subspace of the column space of matrix $A$, then $\text{rank}(B) \le \text{rank}(A)$.

    Because the columns in $A$ are linearly independent, if we take just these columns as a matrix $A$, we have that $\text{rank}(A) = |A|$. Similarly, if we take the columns of $B$ as a matrix $B$, we have $\text{rank}(B) = |B|$. Since $|A| < |B|$, we have $\text{rank}(A) < \text{rank}(B)$.

    We shall show that there is some column $b \in B$ that is not a linear combination of the columns in $A$, and so $A \cup \{b\}$ is linearly independent. The proof proceeds by contradiction. Assume that each column in $B$ is a linear combination of the columns of $A$. That means that any vector that is a linear combination of the columns of $B$ is also a linear combination of the columns of $A$, and so, treating the columns of $A$ and $B$ as matrices, the column space of $B$ is a subspace of the column space of $A$. By the second property above, we have $\text{rank}(B) \le \text{rank}(A)$. But we have already shown that $\text{rank}(A) < \text{rank}(B)$ a contradiction. Therefore, some column in $B$ is not a linear combination of the columns of $A$, and $(S, \mathcal I)$ satisfies the exchange property.

16.4-3 $\star$

Show that if $(S, \mathcal I)$ is a matroid, then $(S, \mathcal I')$ is a matroid, where

$\mathcal I' = \{A': S - A'$ contains some maximal $A \in \mathcal I\}$.

That is, the maximal independent sets of $(S, \mathcal I')$ are just the complements of the maximal independent sets of $(S, \mathcal I)$.

[This exercise defines what is commonly known as the dual of a matroid, and it asks to prove that the dual of a matroid is itself a matroid. The literature contains simpler proofs of this fact, but they depend on other (equivalent) definitions of a matroid. The proof given here is more complicated, but it relies only on the definition given in the text.]

We need to show three things to prove that $(S, \mathcal I')$ is a matroid:

  1. $S$ is finite. We are given that.
  2. $\mathcal I'$ is hereditary. Suppose that $B' \in \mathcal I'$ and $A' \subseteq B'$ . Since $B' \in \mathcal I'$, there is some maximal set $B \in \mathcal I$ such that $B \subseteq S - B'$ . But $A' \subseteq B'$ implies that $S - B' \subseteq S - A'$, and so $B \subseteq S - B' \subseteq S - A'$. Thus, there exists a maximal set $B \in \mathcal I$ such that $B \subseteq S - A'$, proving that $A' \in \mathcal I'$.
  3. $(S, \mathcal I')$ satisfies the exchange property. We start with two preliminary facts about sets. The proofs of these facts are omitted.
    • Fact 1: $|X - Y| = |X| - |X \cap Y|$.
    • Fact 2: Let $S$ be the universe of elements. If $X - Y \subseteq Z$ and $Z \subseteq S - Y$, then $|X \cap Z| = |X| - |X \cap Y|$.

To show that $(S, \mathcal I')$ satisfies the exchange property, let us assume that $A' \in \mathcal I', B' \in \mathcal I'$, and that $|A'| < |B'|$. We need to show that there exists some $x \in B' - A'$ such that $A' \cup \{x\} \in \mathcal I'$. Because $A' \in \mathcal I'$ and $B' \in \mathcal I'$, there are maximal sets $A \subseteq S - A'$ and $B \subseteq S - B'$ such that $A \in \mathcal I$ and $B \in \mathcal I$.

Define the set $X = B' - A' - A$, so that $X$ consists of elements in $B'$ but not in $A'$ or $A$.

If $X$ is nonempty, then let $x$ be any element of $X$. By how we defined set $X$, we know that $x \in B'$ and $x \notin A'$, so that $x \in B' - A'$. Since $x \notin A$, we also have that $A \subseteq S - A' - \{x\} = S - (A' \cup \{x\})$, and so $A' \cup \{x\} \in \mathcal I'$.

If $X$ is empty, the situation is more complicated. Because$|A'| < |B'|$, we have that $B' - A' \ne \emptyset$, and so $X$ being empty means that $B' - A' \subseteq A$.

Claim

There is an element $y \in B - A'$ such that $(A - B') \cup \{y\} \in \mathcal I$.

Proof

First, observe that because $A - B' \subseteq A$ and $A \in \mathcal I$, we have that $A - B' \in \mathcal I$. Similarly, $B - A' \subseteq B$ and $B \in \mathcal I$, and so $B - A' \in \mathcal I$. If we show that $|A - B'| < |B - A'|$, the assumption that $(S, \mathcal I)$ is a matroid proves the existence of $y$.

Because $B' - A' \subseteq A$ and $A \subseteq S - A'$, we can apply Fact 2 to conclude that

$$|B' \cap A| = |B'| - |B' \cap A'|.$$

We claim that $|B \cap A'| \le |A' - B'|$. To see why, observe that $A' - B' = A' \cap (S - B')$ and $B \subseteq S - B'$, and so

$$B \cap A' \subseteq (S - B') \cap A' = A' \cap (S - B') = A' - B'.$$

Applying Fact 1, we see that

$$|A' - B'| = |A'| - |A' \cap B'| = |A'| - |B' \cap A'|,$$

and hence

$$|B \cap A'| \le |A'| - |B' \cap A'|.$$

Now, we have

$$ \begin{aligned} |A'| & < |B'| & \text{(by assumption)} \\ |A'| - |B'\cap A'| & < |B'| - |B' \cap A'| & \text{(subtracting same quantity)} \\ |B \cap A'| & < |B'| - |B' \cap A'| & (|B \cap A'| \le |A'| - |B' \cap A'|) \\ |B \cap A'| & < |B' \cap A| & (|B' \cap A| = |B'| - |B' \cap A'|) \\ |B| - |B \cap A'| & > |A| - |B' \cap A| & (|A| = |B|) \\ |B - A'| & > |A - B'| & \text{(Fact 1)} \\ \end{aligned} $$

Now we know there is an element $y \in B - A'$ such that $(A - B') \cup \{y\} \in \mathcal I$. Moreover, we claim that $y \notin A$. To see why, we know that by the exchange property, $y \notin A - B'$. In order for $y$ to be in $A$, it would have to be in $A \cap B'$. But $y \in B$, which means that $y \notin B'$, and hence $y \notin A \cap B'$. Therefore $y \notin A$.

Applying the exchange property, we add elements in $B - A'$ to $A - B'$, maintaining that the set we get, say $C$, is in $\mathcal I$. Then we keep applying the exchange property, adding a new element in $A - C$ to $C$, maintaining that $C$ is in $\mathcal I$, until $|C| = |A|$. Once $|C| = |A|$, there must exist some element $x \in A$ that we have not added into $C$. We know that such an element exists because the element $y$ that we first added into $C$ was not in $A$, and so some element $x$ in $A$ must be left over. Also, we must have $x \in B'$ because all the elements in $A - B'$ are initially in $C$. Therefore, we have $x \in B' - A'$.

The set $C$ so constructed is maximal, because it has the same cardinality as $A$, which is maximal, and $C \in \mathcal I$. All the elements but one in $C$ are also in $A$; the one exceptions is in $B - A'$, and so $C$ contains no elements in $A'$. Because we never added $x$ to $C$, we have that $C \subseteq S - A' - \{x\} = S - (A' \cup \{x\})$. Therefore, $A' \cup \{x\} \in \mathcal I'$, as we needed to show.

16.4-4 $\star$

Let $S$ be a finite set and let $S_1, S_2, \ldots, S_k$ be a partition of $S$ into nonempty disjoint subsets. Define the structure $(S, \mathcal I)$ by the condition that $\mathcal I = \{A: \mid A \cap S_i \mid \le 1$ for $i = 1, 2, \ldots, k\}$. Show that $(S, \mathcal I)$ is a matroid. That is, the set of all sets $A$ that contain at most one member of each subset in the partition determines the independent sets of a matroid.

Suppose $X \subset Y$ and $Y \in \mathcal I$. Then $(X \cap S_i) \subset (Y \cap S_i)$ for all $i$, so

$$|X \cap S_i| \le |Y \cap S_i| \le 1$$

for all $1 \le i \le k$. Therefore $\mathcal M$ is closed under inclusion.

Now Let $A, B \in \mathcal I$ with $|A| = |B| + 1$. Then there must exist some $j$ such that $|A \cap S_j| = 1$ but $|B \cap S_j| = 0$. Let $a = A \cap S_j$. Then $a \ne B$ and $|(B \cup \{a\}) \cap S_j| = 1$. Since

$$|(B \cup \{a\}) \cap S_i| = |B \cap S_i|$$

for all $i \ne j$, we must have $B \cup \{a\} \in \mathcal I$. Therefore $\mathcal M$ is a matroid.

16.4-5

Show how to transform the weight function of a weighted matroid problem, where the desired optimal solution is a minimum-weight maximal independent subset, to make it a standard weighted-matroid problem. Argue carefully that your transformation is correct.

Suppose that $W$ is the largest weight that any one element takes. Then, define the new weight function $w_2(x) = 1 + W - w(x)$. This then assigns a strictly positive weight, and we will show that any independent set that that has maximum weight with respect to $w_2$ will have minimum weight with respect to $w$.

Recall Theorem 16.6 since we will be using it, suppose that for our matriod, all maximal independent sets have size $S$. Then, suppose $M_1$ and $M_2$ are maximal independent sets so that $M_1$ is maximal with respect to $w_2$ and $M_2$ is minimal with respect to $w$. Then, we need to show that $w(M_1) = w(M_2)$. Suppose not to achieve a contradiction, then, by minimality of $M_2$, $w(M_1) > w(M_2)$.

Rewriting both sides in terms of $w_2$, we have

$$w_2(M_2) - (1 + W)S > w_2(M_1) - (1 + W)S,$$

so,

$$w_2(M_2) > w_2(M_1).$$

This however contradicts maximality of $M_1$ with respect to $w_2$. So, we must have that $w(M_1) = w(M_2)$. So, a maximal independent set that has the largest weight with respect to $w_2$ also has the smallest weight with respect to $w$.