One of the students in my class, Undergraduate Seminar on Discrete Mathematics, asks if the exchange property of a matroid can be strengthened to the following, of which I was completely unaware.

Strong basis exchange property. For every pair of bases $B_1, B_2$ and $x_1 \in B_1$, there exists $x_2 \in B_2$ such that both $B_1 - x_1 + x_2$ and $B_2 + x_1 - x_2$ are still bases.

As it turns out, Brualdi proved back in 1969 the strong exchange property (Theorem 2) in Comments on bases in dependence structures.

I record below the proof which showcases the benefit of viewing matroids both graphically and linear-algebraically.

As per Aaron Berger‘s suggestion, we use a graphic matroid to motivate the proof. Suppose $T_1$ and $T_2$ are two spanning trees of a connected graph $G$ and $e_1$ is an edge in $T_1$. Clearly, when the edge $e_1$ is also in $T_2$, we can simply exchange $e_1$ with itself. Assume from now that $e_1$ is not in $T_2$. Note that $T_2 + e_1$ contains a unique cycle $C$, each edge of which can be “traded” to $T_1$. To be more precise, for every $e_2 \in C$, $T_2 + e_1 - e_2$ is still a spanning tree. It is then easy to see that adding back some edge from $C - e_1$ can reconnect the two connected components resulted from removing $e_1$ from $T_1$.

As the unique cycle (or circuit) $C$ plays a central role in the above argument, one can show the same concept is valid in any matroid.

Lemma (Fundamental circuit). For every independent set $I$, if an element $e$ satisfies that $I + e$ is dependent, then $I + e$ contains a unique circuit $C$, called the fundamental circuit. Moreover, for every $f \in C$, $I + e - f$ is independent.

Proof of strong basis exchange property. Without loss of generality, we may assume that $e_1 \not\in B_2$. As $B_2$ is a maximal independent set and $B_2 + e_1$ is dependent, there is a unique circuit $C \subseteq B_2 + e_1$ such that $B_2 + e_1 - e_2$ is independent for every $e_2 \in C$.

Finally we resort to our intuition of representable matroids. Since $e_1 \in \mathrm{span}(C - e_1) \subseteq \mathrm{span}(B_1 + C - e_1)$, we have $\mathrm{span}(B_1 + C - e_1) = \mathrm{span}(B_1 + C)$, hence $B_1 + C - e_1$ contains a basis, say $B_1'$. By the ordinary exchange property for $B_1 - e_1$ and $B_1'$, there is $e_2 \in B_1' - (B_1 - e_1) \subseteq C - e_1$ such that $B_1 - e_1 + e_2$ is independent. □