[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*}[/step]

[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: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]