[proofplan] We verify the basis axioms for the family of complements of bases of $M$. The equal-cardinality axiom follows because all bases of $M$ have the same size. For the exchange axiom, we translate an exchange between complements into an exchange between the original bases, and we prove the needed simultaneous exchange by a circuit-elimination argument inside $M$. [/proofplan] [step:Check that all complementary bases have the same cardinality] Let $r(M)$ denote the common cardinality of the bases of $M$. If $B^* \in \mathcal{B}^*(M)$, then there exists a basis $B \in \mathcal{B}(M)$ such that $B^* = E \setminus B$. Since $E$ is finite, the cardinality computation gives $|B^*| = |E \setminus B| = |E| - |B| = |E| - r(M)$. Thus every member of $\mathcal{B}^*(M)$ has the same cardinality. [/step] [step:Prove the simultaneous exchange needed in the original matroid] We use the following exchange fact for $M$. [claim:Strong basis exchange in a finite matroid] Let $A,B \in \mathcal{B}(M)$, and let $e \in B \setminus A$. Then there exists $f \in A \setminus B$ such that both \begin{align*} (A \setminus \{f\}) \cup \{e\} \end{align*} and \begin{align*} (B \setminus \{e\}) \cup \{f\} \end{align*} are bases of $M$. [/claim] [proof] Let $C_A(e)$ denote the unique fundamental circuit contained in $A \cup \{e\}$; this is the fundamental circuit of $e$ with respect to the basis $A$. Since $B$ is independent and $e \in B$, the circuit $C_A(e)$ cannot be contained in $B$. Hence \begin{align*} C_A(e) \cap (A \setminus B) \neq \varnothing. \end{align*} For every $f \in C_A(e) \setminus \{e\}$, the defining property of the fundamental circuit gives that $(A \setminus \{f\}) \cup \{e\}$ is a basis of $M$. It remains to choose such an $f$ for which $(B \setminus \{e\}) \cup \{f\}$ is also a basis. Suppose, toward a contradiction, that no element $f \in C_A(e) \cap (A \setminus B)$ has this property. For each such $f$, let $C_B(f)$ denote the unique fundamental circuit contained in $B \cup \{f\}$. The set $(B \setminus \{e\}) \cup \{f\}$ fails to be a basis exactly when it is dependent, which is equivalent to the fundamental circuit $C_B(f)$ being contained in $(B \setminus \{e\}) \cup \{f\}$. Thus $e \notin C_B(f)$ for every $f \in C_A(e) \cap (A \setminus B)$. Starting with the circuit $C_A(e)$, eliminate one element $f \in C_A(e) \cap (A \setminus B)$ using the circuit $C_B(f)$. Since $f$ belongs to both circuits and $e$ belongs to $C_A(e)$ but not to $C_B(f)$, the circuit elimination axiom produces a circuit contained in $(C_A(e) \cup C_B(f)) \setminus \{f\}$ which still contains $e$. The invariant is that the current circuit contains $e$ and is contained in $B \cup S$, where $S$ is the set of not-yet-eliminated elements of $C_A(e) \cap (A \setminus B)$. When eliminating $f \in S$, the auxiliary circuit satisfies $C_B(f) \subseteq B \cup \{f\}$, so no new element of $A \setminus B$ is introduced, and circuit elimination removes $f$ while preserving $e$. Since $E$ is finite, induction over the finite set $C_A(e) \cap (A \setminus B)$ produces a circuit contained entirely in $B$. This contradicts the independence of the basis $B$. Therefore there exists $f \in C_A(e) \cap (A \setminus B)$ such that $(B \setminus \{e\}) \cup \{f\}$ is a basis. Since $f \in C_A(e) \setminus \{e\}$, the set $(A \setminus \{f\}) \cup \{e\}$ is also a basis. This proves the claim. [/proof] [guided] The issue is that the ordinary basis exchange axiom gives one valid replacement, but for the dual construction we need a replacement that works compatibly on both bases. We prove exactly that compatibility. Let $C_A(e)$ be the fundamental circuit of $e$ with respect to $A$, meaning the unique circuit contained in $A \cup \{e\}$. This circuit exists because $A$ is a basis and $e \notin A$, so $A \cup \{e\}$ is dependent, while every proper subset obtained by deleting a suitable element of the circuit is independent. The fundamental circuit has the key property that, for every $f \in C_A(e) \setminus \{e\}$, \begin{align*} (A \setminus \{f\}) \cup \{e\} \end{align*} is a basis of $M$. We must also make the exchange work in $B$. Since $e \in B$ and $B$ is independent, the circuit $C_A(e)$ cannot be a subset of $B$. Therefore some element of this circuit lies in $A \setminus B$: \begin{align*} C_A(e) \cap (A \setminus B) \neq \varnothing. \end{align*} Now suppose every possible candidate $f \in C_A(e) \cap (A \setminus B)$ fails on the $B$ side. For such an $f$, let $C_B(f)$ be the fundamental circuit of $f$ with respect to $B$, the unique circuit contained in $B \cup \{f\}$. The set \begin{align*} (B \setminus \{e\}) \cup \{f\} \end{align*} is a basis exactly when deleting $e$ from $B \cup \{f\}$ destroys the fundamental circuit $C_B(f)$. Equivalently, it is a basis exactly when $e \in C_B(f)$. By the contradiction assumption, $e \notin C_B(f)$ for every candidate $f$. We now use circuit elimination. The circuits $C_A(e)$ and $C_B(f)$ both contain $f$, while $e$ lies in $C_A(e)$ but not in $C_B(f)$. Circuit elimination produces a new circuit contained in $(C_A(e) \cup C_B(f)) \setminus \{f\}$ and still containing $e$. This removes one offending element of $A \setminus B$ from the circuit without losing $e$. It also introduces no new offending elements: because $C_B(f) \subseteq B \cup \{f\}$, every element added from $C_B(f)$ lies in $B$ once $f$ has been removed. Since $E$ is finite, induction over the finite set of offending elements eliminates all elements of $A \setminus B$ from the current circuit. The resulting circuit is contained in $B$, contradicting that $B$ is independent. Thus at least one $f \in C_A(e) \cap (A \setminus B)$ satisfies $e \in C_B(f)$. For this $f$, the fundamental-circuit criterion gives both that \begin{align*} (A \setminus \{f\}) \cup \{e\} \end{align*} is a basis and that \begin{align*} (B \setminus \{e\}) \cup \{f\} \end{align*} is a basis. This proves the simultaneous exchange claim. [/guided] [/step] [step:Translate ordinary exchange for complements into strong exchange in $M$] Let $B_1^*,B_2^* \in \mathcal{B}^*(M)$, and choose $e \in B_1^* \setminus B_2^*$. By definition of $\mathcal{B}^*(M)$, there exist bases $B_1,B_2 \in \mathcal{B}(M)$ such that \begin{align*} B_1^* = E \setminus B_1 \end{align*} and \begin{align*} B_2^* = E \setminus B_2. \end{align*} The membership $e \in B_1^* \setminus B_2^*$ means precisely that \begin{align*} e \in B_2 \setminus B_1. \end{align*} Applying the strong basis exchange claim to the bases $B_1,B_2$ and the element $e \in B_2 \setminus B_1$, choose $f \in B_1 \setminus B_2$ such that \begin{align*} (B_1 \setminus \{f\}) \cup \{e\} \end{align*} is a basis of $M$. Since $f \in B_1 \setminus B_2$, the complement relation gives \begin{align*} f \in B_2^* \setminus B_1^*. \end{align*} Now compute the complement of the exchanged basis: \begin{align*} E \setminus \bigl((B_1 \setminus \{f\}) \cup \{e\}\bigr) = (E \setminus B_1 \setminus \{e\}) \cup \{f\}. \end{align*} Because $e \in E \setminus B_1 = B_1^*$, this is \begin{align*} (B_1^* \setminus \{e\}) \cup \{f\}. \end{align*} Since $(B_1 \setminus \{f\}) \cup \{e\}$ is a basis of $M$, its complement belongs to $\mathcal{B}^*(M)$. Therefore \begin{align*} (B_1^* \setminus \{e\}) \cup \{f\} \in \mathcal{B}^*(M). \end{align*} [/step] [step:Conclude that the complementary family satisfies the basis axioms] Since $M$ is a matroid on the finite ground set $E$, it has at least one basis $B \in \mathcal{B}(M)$; hence $E \setminus B \in \mathcal{B}^*(M)$, so $\mathcal{B}^*(M)$ is nonempty. We have shown that every member of $\mathcal{B}^*(M)$ has the same cardinality and that for any $B_1^*,B_2^* \in \mathcal{B}^*(M)$ and any $e \in B_1^* \setminus B_2^*$, there exists $f \in B_2^* \setminus B_1^*$ such that \begin{align*} (B_1^* \setminus \{e\}) \cup \{f\} \in \mathcal{B}^*(M). \end{align*} A nonempty family of subsets of a finite set is the family of bases of a matroid precisely when all members have the same cardinality and the stated basis-exchange condition holds. The preceding paragraphs verify those conditions for $\mathcal{B}^*(M)$ on the finite ground set $E$. Hence $\mathcal{B}^*(M)$ is the set of bases of a matroid on $E$. [/step]