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