[proofplan]
We first check that every incidence vector of an independent set satisfies the rank inequalities, so the convex hull of independent-set incidence vectors is contained in $P_I(M)$. For the reverse inclusion, we compare every linear objective on $P_I(M)$ with its maximum over independent sets. After discarding negative weights, we order the elements by weight and use summation by parts to bound $w\cdot x$ by a weighted sum of ranks of prefixes. The greedy independent set attains this upper bound, so the two compact convex sets have the same support function; a finite-dimensional separation argument then forces equality.
[/proofplan]
[step:Place every independent-set incidence vector inside the rank polytope]
Let $r:2^E\to\mathbb N\cup\{0\}$ denote the [matroid rank function](/page/Matroid%20Rank%20Function) of $M$, so $r(A)$ is the maximum cardinality of an [independent set](/page/Independent%20Set) contained in $A$. By definition,
\begin{align*}
P_I(M):=\{x\in\mathbb R^E:\ x_e\geq 0\text{ for every }e\in E,\ \sum_{e\in A}x_e\leq r(A)\text{ for every }A\subset E\}.
\end{align*}
For every subset $A\subset E$, let $\mathbb 1_A\in\mathbb R^E$ denote the incidence vector of $A$, defined coordinatewise as follows: for every $e\in E$, $(\mathbb 1_A)_e=1$ if $e\in A$, and $(\mathbb 1_A)_e=0$ if $e\notin A$.
Let
\begin{align*}
Q:=\operatorname{conv}\{\mathbb 1_I:\ I\in\mathcal I\}\subset\mathbb R^E.
\end{align*}
We prove $Q\subset P_I(M)$. Let $I\in\mathcal I$. For every $e\in E$, the coordinate $(\mathbb 1_I)_e$ is either $0$ or $1$, hence $(\mathbb 1_I)_e\geq 0$. For every subset $A\subset E$,
\begin{align*}
\sum_{e\in A}(\mathbb 1_I)_e=|I\cap A|.
\end{align*}
Since $I\cap A$ is an independent subset of $A$, the definition of the rank function gives $|I\cap A|\leq r(A)$. Therefore
\begin{align*}
\sum_{e\in A}(\mathbb 1_I)_e\leq r(A).
\end{align*}
Thus $\mathbb 1_I\in P_I(M)$ for every $I\in\mathcal I$. Since $P_I(M)$ is convex, because it is an intersection of closed half-spaces in $\mathbb R^E$, it contains the convex hull $Q$.
[/step]
[step:Reduce arbitrary linear objectives to non-negative weights]
Let $w:E\to\mathbb R$ be a weight function, and write $w_e:=w(e)$ for every $e\in E$. Define the positive-part weight function $w_{\operatorname{pos}}:E\to[0,\infty)$ by
\begin{align*}
w_{\operatorname{pos}}(e)=\max\{w_e,0\}\quad\text{for every }e\in E.
\end{align*}
We claim that it is enough to compute the maximum of non-negative weight functions.
For independent sets, negative weights can be removed. Indeed, if $I\in\mathcal I$, define
\begin{align*}
I_{\operatorname{pos}}:=\{e\in I:\ w_e\geq 0\}.
\end{align*}
Since $\mathcal I$ is hereditary, $I_{\operatorname{pos}}\in\mathcal I$, and
\begin{align*}
\sum_{e\in I}w_e\leq \sum_{e\in I_{\operatorname{pos}}}w_e=\sum_{e\in I_{\operatorname{pos}}}w_{\operatorname{pos}}(e).
\end{align*}
Thus
\begin{align*}
\max_{I\in\mathcal I}\sum_{e\in I}w_e
\leq
\max_{I\in\mathcal I}\sum_{e\in I}w_{\operatorname{pos}}(e).
\end{align*}
Conversely, let $J\in\mathcal I$ be arbitrary, and define
\begin{align*}
J_{\operatorname{pos}}:=\{e\in J:\ w_e\geq 0\}.
\end{align*}
Again $J_{\operatorname{pos}}\in\mathcal I$ by heredity, and the elements of $J\setminus J_{\operatorname{pos}}$ contribute zero to the $w_{\operatorname{pos}}$-sum. Hence
\begin{align*}
\sum_{e\in J}w_{\operatorname{pos}}(e)=\sum_{e\in J_{\operatorname{pos}}}w_{\operatorname{pos}}(e)=\sum_{e\in J_{\operatorname{pos}}}w_e\leq \max_{I\in\mathcal I}\sum_{e\in I}w_e.
\end{align*}
Taking the maximum over $J\in\mathcal I$ gives
\begin{align*}
\max_{I\in\mathcal I}\sum_{e\in I}w_e
=
\max_{I\in\mathcal I}\sum_{e\in I}w_{\operatorname{pos}}(e).
\end{align*}
For points of $P_I(M)$, the defining inequalities give $x_e\geq 0$ for every $e\in E$. Therefore, for every $x\in P_I(M)$,
\begin{align*}
\sum_{e\in E}w_e x_e\leq \sum_{e\in E}w_{\operatorname{pos}}(e)x_e.
\end{align*}
Consequently, once the non-negative case is proved,
\begin{align*}
\max_{x\in P_I(M)}\sum_{e\in E}w_ex_e\leq\max_{x\in P_I(M)}\sum_{e\in E}w_{\operatorname{pos}}(e)x_e.
\end{align*}
The non-negative case applied to $w_{\operatorname{pos}}$ gives
\begin{align*}
\max_{x\in P_I(M)}\sum_{e\in E}w_{\operatorname{pos}}(e)x_e=\max_{I\in\mathcal I}\sum_{e\in I}w_{\operatorname{pos}}(e).
\end{align*}
The preceding independent-set reduction gives
\begin{align*}
\max_{I\in\mathcal I}\sum_{e\in I}w_{\operatorname{pos}}(e)=\max_{I\in\mathcal I}\sum_{e\in I}w_e.
\end{align*}
The reverse inequality follows from $Q\subset P_I(M)$, because every $\mathbb 1_I$ lies in $P_I(M)$. Thus it remains to prove equality of maxima for $w_e\geq 0$ for every $e\in E$.
[/step]
[step:Bound a non-negative objective by rank inequalities on weight prefixes]
Assume $w:E\to[0,\infty)$ is non-negative. Since $E$ is finite by hypothesis, write $E=\{e_1,\dots,e_m\}$ in an order satisfying
\begin{align*}
w_{e_1}\geq w_{e_2}\geq \cdots \geq w_{e_m}\geq 0.
\end{align*}
Define $w_{e_{m+1}}:=0$, define $S_0:=\varnothing$, and for $1\leq i\leq m$ define the prefix set
\begin{align*}
S_i:=\{e_1,\dots,e_i\}.
\end{align*}
For $x\in\mathbb R^E$, define the prefix sum
\begin{align*}
x(S_i):=\sum_{e\in S_i}x_e.
\end{align*}
By summation by parts,
\begin{align*}
\sum_{i=1}^{m}w_{e_i}x_{e_i}=\sum_{i=1}^{m}w_{e_i}\bigl(x(S_i)-x(S_{i-1})\bigr).
\end{align*}
Collecting the coefficient of each prefix sum gives
\begin{align*}
\sum_{i=1}^{m}w_{e_i}\bigl(x(S_i)-x(S_{i-1})\bigr)=\sum_{i=1}^{m}(w_{e_i}-w_{e_{i+1}})x(S_i).
\end{align*}
If $x\in P_I(M)$, then the rank inequality for $S_i$ gives
\begin{align*}
x(S_i)\leq r(S_i)
\end{align*}
for every $1\leq i\leq m$. Since every coefficient $w_{e_i}-w_{e_{i+1}}$ is non-negative, we obtain
\begin{align*}
\sum_{e\in E}w_ex_e\leq\sum_{i=1}^{m}(w_{e_i}-w_{e_{i+1}})r(S_i).
\end{align*}
[guided]
The point of ordering the elements by decreasing weight is that the objective can be rewritten using only the prefix sums $x(S_i)$, and those are exactly quantities controlled by the rank inequalities.
Since $E$ is finite by hypothesis, let $E=\{e_1,\dots,e_m\}$ be ordered so that
\begin{align*}
w_{e_1}\geq w_{e_2}\geq \cdots \geq w_{e_m}\geq 0.
\end{align*}
We also set $w_{e_{m+1}}:=0$. For each $1\leq i\leq m$, define
\begin{align*}
S_i:=\{e_1,\dots,e_i\},
\end{align*}
and set $S_0:=\varnothing$. For a vector $x\in\mathbb R^E$, define
\begin{align*}
x(S_i):=\sum_{e\in S_i}x_e.
\end{align*}
Then
\begin{align*}
x_{e_i}=x(S_i)-x(S_{i-1})
\end{align*}
for each $i$. Substituting this into the objective gives
\begin{align*}
\sum_{e\in E}w_ex_e=\sum_{i=1}^{m}w_{e_i}x_{e_i}.
\end{align*}
Therefore
\begin{align*}
\sum_{i=1}^{m}w_{e_i}x_{e_i}=\sum_{i=1}^{m}w_{e_i}\bigl(x(S_i)-x(S_{i-1})\bigr).
\end{align*}
Now collect the coefficient of each prefix sum $x(S_i)$. The term $x(S_i)$ appears with coefficient $w_{e_i}$ from the $i$th summand and with coefficient $-w_{e_{i+1}}$ from the $(i+1)$st summand, with the convention $w_{e_{m+1}}=0$. Hence
\begin{align*}
\sum_{e\in E}w_ex_e=\sum_{i=1}^{m}(w_{e_i}-w_{e_{i+1}})x(S_i).
\end{align*}
This identity is useful because the coefficients are non-negative:
\begin{align*}
w_{e_i}-w_{e_{i+1}}\geq 0
\end{align*}
for every $i$, by the chosen ordering. If $x\in P_I(M)$, then the defining rank inequality applied to the subset $S_i\subset E$ gives
\begin{align*}
x(S_i)=\sum_{e\in S_i}x_e\leq r(S_i).
\end{align*}
Multiplying these inequalities by the non-negative coefficients $w_{e_i}-w_{e_{i+1}}$ and summing over $i$ preserves the inequality. Combining this with the summation-by-parts identity gives
\begin{align*}
\sum_{e\in E}w_ex_e=\sum_{i=1}^{m}(w_{e_i}-w_{e_{i+1}})x(S_i).
\end{align*}
Thus
\begin{align*}
\sum_{e\in E}w_ex_e\leq\sum_{i=1}^{m}(w_{e_i}-w_{e_{i+1}})r(S_i).
\end{align*}
This is the universal upper bound on the objective over $P_I(M)$.
[/guided]
[/step]
[step:Construct a greedy independent set attaining the rank upper bound]
Define a sequence of sets $G_0,G_1,\dots,G_m$ as follows. Set $G_0:=\varnothing$. For $1\leq i\leq m$, if $G_{i-1}\cup\{e_i\}\in\mathcal I$, define
\begin{align*}
G_i:=G_{i-1}\cup\{e_i\}.
\end{align*}
If $G_{i-1}\cup\{e_i\}\notin\mathcal I$, define
\begin{align*}
G_i:=G_{i-1}.
\end{align*}
Let $G:=G_m$. By construction and heredity, each $G_i$ is independent, and $G_i\subset S_i$.
We prove by induction on $i$ that
\begin{align*}
|G_i|=r(S_i)
\end{align*}
for every $0\leq i\leq m$. For $i=0$, both sides are $0$. Assume $1\leq i\leq m$ and $|G_{i-1}|=r(S_{i-1})$. Since $S_i=S_{i-1}\cup\{e_i\}$, every independent subset of $S_i$ either avoids $e_i$ and has size at most $r(S_{i-1})$, or contains $e_i$ and becomes an independent subset of $S_{i-1}$ after removing $e_i$, hence has size at most $r(S_{i-1})+1$. Also $S_{i-1}\subset S_i$, so $r(S_i)\geq r(S_{i-1})$. Therefore
\begin{align*}
r(S_i)\in\{r(S_{i-1}),r(S_{i-1})+1\}.
\end{align*}
If $G_{i-1}\cup\{e_i\}\in\mathcal I$, then $G_i=G_{i-1}\cup\{e_i\}$, so
\begin{align*}
|G_i|=|G_{i-1}|+1=r(S_{i-1})+1.
\end{align*}
The independent set $G_i\subset S_i$ has size $r(S_{i-1})+1$, so $r(S_i)\geq r(S_{i-1})+1$, and hence $r(S_i)=r(S_{i-1})+1=|G_i|$.
If $G_{i-1}\cup\{e_i\}\notin\mathcal I$, then $G_i=G_{i-1}$. Suppose, for contradiction, that $r(S_i)=r(S_{i-1})+1$. Then $S_i$ contains an independent subset $B\subset S_i$ with
\begin{align*}
|B|=r(S_{i-1})+1.
\end{align*}
Since $S_i=S_{i-1}\cup\{e_i\}$ and every independent subset of $S_{i-1}$ has size at most $r(S_{i-1})$, the set $B$ must contain $e_i$. By the induction hypothesis, $G_{i-1}$ is independent and has size $r(S_{i-1})$, while $B$ is independent and has size $r(S_{i-1})+1$. The augmentation axiom in the definition of a [matroid](/page/Matroid) applies to the independent sets $G_{i-1}$ and $B$: since $|G_{i-1}|<|B|$, there exists an element
\begin{align*}
b\in B\setminus G_{i-1}
\end{align*}
such that $G_{i-1}\cup\{b\}\in\mathcal I$. If $b\in S_{i-1}$, then $G_{i-1}\cup\{b\}$ would be an independent subset of $S_{i-1}$ of size $r(S_{i-1})+1$, contradicting the definition of $r(S_{i-1})$ as the maximum size of an independent subset of $S_{i-1}$. Therefore $b\notin S_{i-1}$. Since $B\subset S_i=S_{i-1}\cup\{e_i\}$, this forces $b=e_i$. Hence $G_{i-1}\cup\{e_i\}\in\mathcal I$, contradicting the definition of this case. Therefore $r(S_i)=r(S_{i-1})$, and
\begin{align*}
|G_i|=|G_{i-1}|=r(S_{i-1})=r(S_i).
\end{align*}
The induction is complete.
For the final greedy set $G=G_m$, the equality $|G_i|=r(S_i)$ and the inclusion $G_i=G\cap S_i$ imply
\begin{align*}
\sum_{e\in S_i}(\mathbb 1_G)_e=r(S_i)
\end{align*}
for every $1\leq i\leq m$. Substituting $x=\mathbb 1_G$ into the summation-by-parts identity gives
\begin{align*}
\sum_{e\in G}w_e
=
\sum_{i=1}^{m}(w_{e_i}-w_{e_{i+1}})r(S_i).
\end{align*}
Thus the upper bound from the previous step is attained by the independent set $G$.
[/step]
[step:Separate compact convex sets to force equality]
We have proved that for every weight function $w:E\to\mathbb R$,
\begin{align*}
\max_{x\in P_I(M)}\sum_{e\in E}w_ex_e
=
\max_{I\in\mathcal I}\sum_{e\in I}w_e.
\end{align*}
The right-hand side is also
\begin{align*}
\max_{y\in Q}\sum_{e\in E}w_ey_e,
\end{align*}
because a linear function attains its maximum over the convex hull of finitely many points at one of those points.
Both $P_I(M)$ and $Q$ are compact convex subsets of $\mathbb R^E$. Since $E$ is finite, $\mathbb R^E$ is finite-dimensional. Compactness of $P_I(M)$ follows from the inequalities $0\leq x_e\leq r(\{e\})\leq 1$ for every $e\in E$, together with closedness. Compactness of $Q$ follows because it is the [convex hull](/page/Convex%20Hull) of finitely many points. The set $Q$ is nonempty because the empty set belongs to $\mathcal I$ for every matroid, and hence $\mathbb 1_\varnothing\in Q$.
We now use the standard finite-dimensional projection/separation argument: project a point of $P_I(M)\setminus Q$ to the nearest point of the nonempty compact convex set $Q$, and use the displacement vector as a separating linear functional. Since $Q\subset P_I(M)$, suppose for contradiction that there exists $x_0\in P_I(M)\setminus Q$. The map $Q\to\mathbb R$, $y\mapsto |x_0-y|$, is continuous with respect to the Euclidean topology on $\mathbb R^E$. Because $Q$ is nonempty and compact, the extreme value theorem gives a point $y_0\in Q$ minimizing the Euclidean distance $|x_0-y|$ over $y\in Q$. Define the separating weight function $w:E\to\mathbb R$ by
\begin{align*}
w(e)=(x_0-y_0)_e\quad\text{for every }e\in E,
\end{align*}
and write $w_e:=w(e)$.
For every $y\in Q$ and every $t\in[0,1]$, the point $y_0+t(y-y_0)$ lies in $Q$. Minimality of $y_0$ gives
\begin{align*}
|x_0-y_0|^2\leq |x_0-y_0-t(y-y_0)|^2.
\end{align*}
Expanding the square and dividing by $t>0$, then letting $t\downarrow 0$, yields
\begin{align*}
\sum_{e\in E}w_e(y_e-y_{0,e})\leq 0.
\end{align*}
Hence
\begin{align*}
\sum_{e\in E}w_ey_e\leq \sum_{e\in E}w_ey_{0,e}
\end{align*}
for every $y\in Q$. On the other hand,
\begin{align*}
\sum_{e\in E}w_ex_{0,e}-\sum_{e\in E}w_ey_{0,e}
=
\sum_{e\in E}(x_{0,e}-y_{0,e})^2
=
|x_0-y_0|^2
>0.
\end{align*}
Thus the linear functional determined by $w$ has a strictly larger value at $x_0\in P_I(M)$ than its maximum on $Q$, contradicting equality of the two maxima for every weight function. Therefore $P_I(M)\subset Q$.
Combining $Q\subset P_I(M)$ with $P_I(M)\subset Q$ gives
\begin{align*}
P_I(M)=\operatorname{conv}\{\mathbb 1_I:\ I\in\mathcal I\}.
\end{align*}
This proves the theorem.
[/step]
