Rank of a matroid ($r_M(A)$)

For a subset $A$ of the ground set, the rank of a matroid on $A$ is the maximum cardinality of a matroid independent set contained in $A$:Thus $r_M(E)$ is the common size of the matroid bases, and $r_M(\varnothing )=0$. The weighted three-vector matroid has $r_M(E)=2$, even though its ground set has three labels.

On a finite ground set $E$, a submodular rank function is a normalised set function $r$ with $r(\varnothing )=0$, a monotone set function, and a submodular set function, such that $r(A\cup \{e\})-r(A)\in \{0,1\}$ for $e\notin A$. Equivalently, require nonnegative integer values, monotonicity, submodularity and $r(\{e\})\le 1$. The diminishing returns characterization of submodularity bounds each marginal by its singleton value. Thus $0\le r(A)\le |A|$.

These functions are precisely the rank functions of matroids. To see the converse direction, define $\mathcal{I}=\{A:r(A)=|A|\}$. It contains the empty set. If $B\subseteq A\in \mathcal{I}$, the unit marginal bounds give $|A|=r(A)\le r(B)+|A\setminus B|$, so $r(B)=|B|$ and heredity holds. For augmentation, suppose $A,B\in \mathcal{I}$ with $|A|<|B|$. If every $e\in B\setminus A$ had zero marginal over $A$, diminishing returns would keep each marginal zero as they are added successively. This would give $r(A\cup B)=r(A)=|A|<|B|=r(B)$, contradicting monotonicity. Some marginal is therefore one, giving an independent augmentation.

Finally any inclusion-maximal $I\subseteq A$ in this independence family has $r(I\cup \{e\})=r(I)$ for every remaining $e\in A\setminus I$. Successively adding them and using diminishing returns shows $r(A)=r(I)=|I|$, so the resulting matroid really has rank $r$. The forward direction is submodularity of matroid rank. These integer increment conditions distinguish matroid ranks from arbitrary real-valued submodular functions.

The rank of a matroid is a normalised set function, a monotone set function, and a submodular set function. Adding one element increases it by at most one.

Proof of submodularity. Choose a maximal matroid independent set $I_0$ in $A\cap B$, extend it to a maximal matroid independent set $I_A$ in $A$, then extend it to one $I_U$ in $A\cup B$. The matroid independence axioms make their sizes $r(A\cap B)$, $r(A)$ and $r(A\cup B)$. Every element of $I_U\setminus I_A$ lies outside $A$, since otherwise it could be added to $I_A$ inside $A$. Hence $I_0\cup (I_U\setminus I_A)$ is an independent subset of $B$, so its size $r(A\cap B)+r(A\cup B)-r(A)$ is at most $r(B)$.

The remaining assertions follow from the definition of the rank of a matroid. The empty set has maximum independent size zero, increasing the available subset cannot reduce that maximum, and deleting a newly added element from an independent subset decreases its size by at most one.