16.4 Matroids and greedy methods
16.41
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.42 $\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:
 $S$ is finite. That's because $S$ is the set of $m$ columns of matrix $T$.
 $\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$.

$(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.43 $\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:
 $S$ is finite. We are given that.
 $\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'$.
 $(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.44 $\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.45
Show how to transform the weight function of a weighted matroid problem, where the desired optimal solution is a minimumweight maximal independent subset, to make it a standard weightedmatroid 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$.