[proofplan] We express the rank of $A$ in the dual matroid by maximizing the size of $A$ inside a [dual basis](/theorems/414). Since the bases of $M^*$ are precisely complements of bases of $M$, this becomes a minimization problem for $|A \cap B|$ over bases $B$ of $M$. The lower bound comes from the fact that $B \cap (E\setminus A)$ is independent in the restriction to $E\setminus A$, and equality is obtained by extending a basis of that restriction to a basis of $M$. [/proofplan]

[step:Rewrite dual rank as a minimization over bases of $M$]Let $\mathcal{B}(M)$ denote the set of bases of $M$, and let $\mathcal{B}(M^*)$ denote the set of bases of $M^*$. By definition of the dual matroid, the bases of $M^*$ are exactly the complements $E\setminus B$ with $B \in \mathcal{B}(M)$. The rank $r^*(A)$ is the largest size of an independent subset of $A$ in $M^*$. We claim that this largest size is obtained by intersecting $A$ with bases of $M^*$. Indeed, if $J\subset A$ is independent in $M^*$, then the Matroid Basis [Extension Theorem](/theorems/59) applies because $M^*$ is a matroid on the finite ground set $E$, so there exists $B^* \in \mathcal{B}(M^*)$ with $J\subset B^*$. Hence $|J|\le |A\cap B^*|$. Conversely, for every $B^*\in\mathcal{B}(M^*)$, the set $A\cap B^*$ is independent in $M^*$ because every subset of a basis is independent. Therefore \begin{align*} r^*(A)=\max_{B^* \in \mathcal{B}(M^*)}|A\cap B^*|. \end{align*} Substituting $B^*=E\setminus B$ with $B \in \mathcal{B}(M)$ gives \begin{align*} r^*(A)=\max_{B \in \mathcal{B}(M)}|A\cap(E\setminus B)|. \end{align*} Since $A\cap(E\setminus B)=A\setminus B$, we have \begin{align*} |A\cap(E\setminus B)|=|A\setminus B|=|A|-|A\cap B|. \end{align*} Therefore \begin{align*} r^*(A)=|A|-\min_{B \in \mathcal{B}(M)}|A\cap B|. \end{align*}[/step]

[guided]Let $\mathcal{B}(M)$ be the set of bases of $M$, and let $\mathcal{B}(M^*)$ be the set of bases of the dual matroid $M^*$. The defining feature of the dual matroid is that its bases are complements of bases of the original matroid: \begin{align*} \mathcal{B}(M^*)=\{E\setminus B : B \in \mathcal{B}(M)\}. \end{align*} We want to compute $r^*(A)$, the rank of $A$ in $M^*$. By definition, $r^*(A)$ is the largest cardinality of an independent subset of $A$ in $M^*$. Why may we replace independent subsets of $A$ by intersections with bases? First let $J\subset A$ be independent in $M^*$. The Matroid Basis Extension Theorem says that every independent set in a finite matroid extends to a basis. Since $E$ is finite and $M^*$ is a matroid on $E$, the theorem applies to $J$ in $M^*$, giving a basis $B^*\in\mathcal{B}(M^*)$ with $J\subset B^*$. Thus $J\subset A\cap B^*$ and $|J|\le |A\cap B^*|$. Conversely, if $B^*\in\mathcal{B}(M^*)$, then every subset of $B^*$ is independent in $M^*$, so $A\cap B^*$ is an independent subset of $A$. These two directions give \begin{align*} r^*(A)=\max_{B^* \in \mathcal{B}(M^*)}|A\cap B^*|. \end{align*} Now substitute the description of dual bases. Every $B^* \in \mathcal{B}(M^*)$ has the form $B^*=E\setminus B$ for a unique basis $B \in \mathcal{B}(M)$, so \begin{align*} r^*(A)=\max_{B \in \mathcal{B}(M)}|A\cap(E\setminus B)|. \end{align*} The set $A\cap(E\setminus B)$ is exactly $A\setminus B$, so it consists of the elements of $A$ not chosen by the basis $B$ of $M$. Therefore \begin{align*} |A\cap(E\setminus B)|=|A\setminus B|=|A|-|A\cap B|. \end{align*} Maximizing $|A|-|A\cap B|$ over all bases $B$ is the same as minimizing $|A\cap B|$ over all bases $B$, because $|A|$ is fixed. Hence \begin{align*} r^*(A)=|A|-\min_{B \in \mathcal{B}(M)}|A\cap B|. \end{align*} This reduces the dual rank formula to one concrete task: compute the smallest possible number of elements of $A$ contained in a basis of $M$.[/guided]

[step:Bound the intersection of $A$ with any basis from below] Set $F:=E\setminus A$. Let $M|F$ denote the restriction of the matroid $M$ to the subset $F\subset E$; its independent sets are precisely the independent sets of $M$ contained in $F$, and its rank function is the restriction of $r$ to subsets of $F$. Let $B \in \mathcal{B}(M)$ be arbitrary. Since $B$ is independent in $M$, the subset $B\cap F$ is independent in the restriction $M|F$. Therefore its cardinality is at most the rank of $F$: \begin{align*} |B\cap F|\le r(F)=r(E\setminus A). \end{align*} Because $B$ is a basis of $M$, $|B|=r(E)$. Also $B$ is the disjoint union of $A\cap B$ and $F\cap B$, since $E=A\sqcup F$. Hence \begin{align*} |A\cap B|=|B|-|F\cap B|=r(E)-|F\cap B|\ge r(E)-r(E\setminus A). \end{align*} Since $B$ was arbitrary, \begin{align*} \min_{B \in \mathcal{B}(M)}|A\cap B|\ge r(E)-r(E\setminus A). \end{align*} [/step]

[step:Choose a basis attaining the lower bound] Let $I \subset F$ be a basis of the restriction $M|F$. Then $I$ is independent in $M$, and \begin{align*} |I|=r(F)=r(E\setminus A). \end{align*} By the Matroid Basis Extension Theorem, applied to the independent set $I$ in the finite matroid $M$ on ground set $E$, extend $I$ to a basis $B_0 \in \mathcal{B}(M)$ of $M$. Since $B_0\cap F$ is independent in $M|F$ and contains $I$, while $I$ is maximal independent in $M|F$, we must have \begin{align*} B_0\cap F=I. \end{align*} Using again the disjoint decomposition $E=A\sqcup F$, we get \begin{align*} |A\cap B_0|=|B_0|-|F\cap B_0|=r(E)-r(E\setminus A). \end{align*} Therefore \begin{align*} \min_{B \in \mathcal{B}(M)}|A\cap B|=r(E)-r(E\setminus A). \end{align*} [/step]

[step:Substitute the minimum into the dual rank expression] From the first step, \begin{align*} r^*(A)=|A|-\min_{B \in \mathcal{B}(M)}|A\cap B|. \end{align*} Substituting the minimum computed above gives \begin{align*} r^*(A)=|A|-\bigl(r(E)-r(E\setminus A)\bigr)=|A|-r(E)+r(E\setminus A). \end{align*} This holds for every subset $A\subset E$, completing the proof. [/step]