[proofplan] We prove the contrapositive of one direction by separating the vertices into those reachable from $S_I$ and those not reachable, then using matroid closure to obtain a rank bound forbidding any larger common independent set. For the converse, a shortest directed path from $S_I$ to $T_I$ gives an alternating exchange sequence. The exchange arcs and the shortest-path no-chord conditions guarantee that the simultaneous symmetric exchange remains independent in both matroids. [/proofplan] [step:Define the exchange digraph and the source and target sets] Throughout the proof, write $M_1=(E,\mathcal I_1)$ and $M_2=(E,\mathcal I_2)$. The exchange digraph $D(I)$ is the directed graph with vertex set $E$ whose arcs are defined as follows: for $x \in I$ and $y \in E \setminus I$, there is an arc $x \to y$ when $(I \setminus \{x\}) \cup \{y\} \in \mathcal I_1$, and there is an arc $y \to x$ when $(I \setminus \{x\}) \cup \{y\} \in \mathcal I_2$. The source and target sets are \begin{align*} S_I := \{y \in E \setminus I : I \cup \{y\} \in \mathcal I_1\} \end{align*} and \begin{align*} T_I := \{y \in E \setminus I : I \cup \{y\} \in \mathcal I_2\}. \end{align*} [/step] [step:Convert absence of an augmenting path into rank bounds on a reachability cut] Let $R \subset E$ be the set of vertices reachable in $D(I)$ from some vertex of $S_I$, and assume that $R \cap T_I = \varnothing$. Define $A := E \setminus R$. Let $r_1:2^E \to \mathbb N \cup \{0\}$ and $r_2:2^E \to \mathbb N \cup \{0\}$ denote the [matroid rank functions](/page/Matroid%20Rank) of $M_1$ and $M_2$, respectively. We first show that \begin{align*} r_1(A) = |I \cap A|. \end{align*} Since $I \cap A$ is independent in $M_1$, $r_1(A) \ge |I \cap A|$. Let $y \in A \setminus I$. Since $y \notin R$, in particular $y \notin S_I$, so $I \cup \{y\}$ is dependent in $M_1$. Because $I$ is independent in $M_1$, there is a unique [fundamental circuit](/page/Fundamental%20Circuit) $C_1(y) \subset I \cup \{y\}$ containing $y$. If $x \in C_1(y) \setminus \{y\}$, then the [circuit exchange property](/page/Circuit%20Exchange) gives \begin{align*} (I \setminus \{x\}) \cup \{y\} \in \mathcal I_1. \end{align*} Hence $x \to y$ is an arc of $D(I)$. If such an $x$ belonged to $R$, then $y$ would also belong to $R$, contradicting $y \in A$. Therefore $C_1(y) \setminus \{y\} \subset I \cap A$, so $y$ is spanned by $I \cap A$ in $M_1$. Thus every element of $A$ is contained in the [matroid closure](/page/Matroid%20Closure) of $I \cap A$ in $M_1$, and therefore $r_1(A) \le |I \cap A|$. This proves $r_1(A)=|I \cap A|$. Similarly, \begin{align*} r_2(R) = |I \cap R|. \end{align*} Since $I \cap R$ is independent in $M_2$, $r_2(R) \ge |I \cap R|$. Let $y \in R \setminus I$. Because $R \cap T_I = \varnothing$, we have $y \notin T_I$, so $I \cup \{y\}$ is dependent in $M_2$. Let $C_2(y) \subset I \cup \{y\}$ be the unique [fundamental circuit](/page/Fundamental%20Circuit) of $y$ over $I$ in $M_2$. If $x \in C_2(y) \setminus \{y\}$, then \begin{align*} (I \setminus \{x\}) \cup \{y\} \in \mathcal I_2, \end{align*} so $y \to x$ is an arc of $D(I)$. Since $y \in R$, reachability gives $x \in R$. Hence $C_2(y) \setminus \{y\} \subset I \cap R$, so $y$ is spanned by $I \cap R$ in $M_2$. Therefore $r_2(R) \le |I \cap R|$, and the reverse inequality was already shown. [guided] The purpose of the reachability set $R$ is to create a cut with no directed arc leaving it. More precisely, if a vertex is reachable from $S_I$, then every out-neighbour of that vertex is also reachable. Thus no directed arc can go from $R$ to $A := E \setminus R$. We prove first that $A$ has no more $M_1$-rank than the part of $I$ lying in $A$. Let $r_1:2^E \to \mathbb N \cup \{0\}$ be the rank function of $M_1$. Since $I$ is independent in $M_1$, the subset $I \cap A$ is independent in $M_1$, so \begin{align*} r_1(A) \ge |I \cap A|. \end{align*} Now take an element $y \in A \setminus I$. Because $y$ is not reachable from $S_I$, it cannot itself lie in $S_I$. Therefore $I \cup \{y\}$ is not independent in $M_1$. Since $I$ is independent, the dependent set $I \cup \{y\}$ contains a unique [fundamental circuit](/page/Fundamental%20Circuit) $C_1(y)$, and this circuit contains $y$. For any element $x \in C_1(y) \setminus \{y\}$, deleting $x$ from the circuit removes the only obstruction to independence inside $I \cup \{y\}$, so \begin{align*} (I \setminus \{x\}) \cup \{y\} \in \mathcal I_1. \end{align*} By the definition of $D(I)$, this means there is a directed arc $x \to y$. If $x$ were in $R$, then this arc would make $y$ reachable from $S_I$, contradicting $y \in A$. Hence every such $x$ lies in $A$, and therefore \begin{align*} C_1(y) \setminus \{y\} \subset I \cap A. \end{align*} This says exactly that $y$ lies in the $M_1$-[closure](/page/Matroid%20Closure) of $I \cap A$. Since every element of $A \setminus I$ is spanned by $I \cap A$, adjoining all of $A \setminus I$ does not increase rank, so \begin{align*} r_1(A) \le |I \cap A|. \end{align*} Combining the two inequalities gives \begin{align*} r_1(A)=|I \cap A|. \end{align*} The proof for $M_2$ is the same cut argument with the arc directions reversed. Let $r_2:2^E \to \mathbb N \cup \{0\}$ be the rank function of $M_2$. Since $I \cap R$ is independent in $M_2$, \begin{align*} r_2(R) \ge |I \cap R|. \end{align*} Let $y \in R \setminus I$. Because no vertex of $T_I$ lies in $R$, we have $y \notin T_I$, so $I \cup \{y\}$ is dependent in $M_2$. Let $C_2(y) \subset I \cup \{y\}$ be the unique [fundamental circuit](/page/Fundamental%20Circuit) of $y$ over $I$ in $M_2$. For each $x \in C_2(y) \setminus \{y\}$, \begin{align*} (I \setminus \{x\}) \cup \{y\} \in \mathcal I_2, \end{align*} so the definition of $D(I)$ gives an arc $y \to x$. Since $y$ is reachable, this arc forces $x$ to be reachable, hence $x \in R$. Thus \begin{align*} C_2(y) \setminus \{y\} \subset I \cap R. \end{align*} Therefore every element of $R \setminus I$ is spanned by $I \cap R$ in $M_2$, and so \begin{align*} r_2(R) \le |I \cap R|. \end{align*} Thus \begin{align*} r_2(R)=|I \cap R|. \end{align*} [/guided] [/step] [step:Use the rank bounds to rule out a larger common independent set] Assume, toward a contradiction, that there exists $J \in \mathcal I_1 \cap \mathcal I_2$ with $|J|=|I|+1$. Since $A$ and $R$ form a partition of $E$, the sets $J \cap A$ and $J \cap R$ form a partition of $J$. Because $J \cap A$ is independent in $M_1$ and contained in $A$, \begin{align*} |J \cap A| \le r_1(A)=|I \cap A|. \end{align*} Because $J \cap R$ is independent in $M_2$ and contained in $R$, \begin{align*} |J \cap R| \le r_2(R)=|I \cap R|. \end{align*} Adding the two inequalities gives the desired contradiction. Since $A$ and $R$ partition $E$, we have \begin{align*} |J| = |J \cap A| + |J \cap R|. \end{align*} The two rank bounds give \begin{align*} |J \cap A| + |J \cap R| \le |I \cap A| + |I \cap R|. \end{align*} Since $A$ and $R$ also partition $I$, this becomes \begin{align*} |J| \le |I|, \end{align*} contradicting $|J|=|I|+1$. Therefore, if a common independent augmentation exists, then some vertex of $T_I$ is reachable from $S_I$, which is exactly the existence of a directed path from $S_I$ to $T_I$. [/step] [step:Choose a shortest augmenting path and record its alternating form] Conversely, suppose there is a directed path in $D(I)$ from a vertex of $S_I$ to a vertex of $T_I$. Choose such a path with the minimum possible number of arcs, and write it as \begin{align*} P=(y_0,x_1,y_1,x_2,y_2,\dots,x_k,y_k), \end{align*} where $k \ge 0$, where $y_i \in E \setminus I$ for $0 \le i \le k$, and where $x_i \in I$ for $1 \le i \le k$. The alternation follows from the definition of the arcs of $D(I)$, since every arc is directed between one element of $I$ and one element of $E \setminus I$. Minimality of $P$ implies that all vertices appearing in $P$ are distinct; otherwise removing the directed cycle between two repeated occurrences would produce a shorter directed path from $S_I$ to $T_I$. The endpoint conditions give \begin{align*} I \cup \{y_0\} \in \mathcal I_1, \qquad I \cup \{y_k\} \in \mathcal I_2. \end{align*} Minimality also gives the no-internal-source and no-internal-target conditions \begin{align*} y_m \notin S_I \quad \text{for } 1 \le m \le k, \qquad y_m \notin T_I \quad \text{for } 0 \le m < k. \end{align*} Indeed, if $y_m \in S_I$ for some $m \ge 1$, the suffix of $P$ from $y_m$ to $y_k$ would be a shorter directed path from $S_I$ to $T_I$. If $y_m \in T_I$ for some $m<k$, the prefix of $P$ from $y_0$ to $y_m$ would be a shorter directed path from $S_I$ to $T_I$. For each $1 \le i \le k$, the arc $x_i \to y_i$ gives \begin{align*} (I \setminus \{x_i\}) \cup \{y_i\} \in \mathcal I_1, \end{align*} and the arc $y_{i-1} \to x_i$ gives \begin{align*} (I \setminus \{x_i\}) \cup \{y_{i-1}\} \in \mathcal I_2. \end{align*} Define $X := \{x_1,\dots,x_k\}$ and $Y := \{y_0,\dots,y_k\}$. Define the exchanged set $I' \subset E$ by \begin{align*} I' := (I \setminus X) \cup Y. \end{align*} Since the vertices of $P$ are distinct, $X \subset I$, $Y \subset E \setminus I$, and $|Y|=|X|+1$. Hence \begin{align*} |I'|=|I|-|X|+|Y|=|I|+1. \end{align*} [/step] [step:Prove the exchanged set is independent in $M_1$] We prove $I' \in \mathcal I_1$. For $0 \le m \le k$, define $X_m := \{x_1,\dots,x_m\}$, $Y_m := \{y_0,\dots,y_m\}$, and $I_m := (I \setminus X_m) \cup Y_m$. We prove by induction on $m$ that $I_m \in \mathcal I_1$. For $m=0$, this is exactly $I \cup \{y_0\} \in \mathcal I_1$, because $y_0 \in S_I$. Assume $1 \le m \le k$ and $I_{m-1} \in \mathcal I_1$. If $I_m$ were dependent, then because $I_{m-1}$ is independent and $I_m = (I_{m-1} \setminus \{x_m\}) \cup \{y_m\}$, there would be an $M_1$-circuit $C \subset I_m$ with $y_m \in C$ and $x_m \notin C$. Since $1 \le m \le k$, the no-internal-source condition gives $y_m \notin S_I$, so $I \cup \{y_m\}$ is dependent in $M_1$. Let $F_m \subset I \cup \{y_m\}$ denote the unique [fundamental circuit](/page/Fundamental%20Circuit) of $y_m$ over $I$ in $M_1$. The arc $x_m \to y_m$ is equivalent to $(I \setminus \{x_m\}) \cup \{y_m\} \in \mathcal I_1$, hence $x_m \in F_m$. We claim that $F_m \cap X_{m-1} \ne \varnothing$. Suppose instead that $F_m \cap X_{m-1}=\varnothing$. The circuits $C$ and $F_m$ both contain $y_m$, and $x_m \in F_m \setminus C$. By the [strong circuit elimination axiom](/page/Strong%20Circuit%20Elimination) for matroids, there exists an $M_1$-circuit $C'\subset (C\cup F_m)\setminus \{y_m\}$ with $x_m\in C'$. Since $C\setminus\{y_m\}\subset (I\setminus X_m)\cup Y_{m-1}$ and $F_m\setminus\{y_m\}\subset I\setminus X_{m-1}$ under the supposition, we get $C'\subset (I\setminus X_{m-1})\cup Y_{m-1}=I_{m-1}$, contradicting $I_{m-1}\in\mathcal I_1$. Thus there is an index $j<m$ with $x_j\in F_m$. By the definition of the $M_1$-arcs of $D(I)$, this gives a shortcut arc $x_j\to y_m$. Following $P$ from $y_0$ to $x_j$, then taking the arc $x_j\to y_m$, and then following the original suffix from $y_m$ to $y_k$ gives a directed path from $S_I$ to $T_I$ with fewer arcs than $P$. This contradicts the choice of $P$ as shortest. Therefore no such circuit $C$ exists, so $I_m \in \mathcal I_1$. Induction gives $I_k=I' \in \mathcal I_1$. [guided] We prove independence in $M_1$ by adding the new elements in the order in which the path supplies them. For $0 \le m \le k$, define $X_m := \{x_1,\dots,x_m\}$, $Y_m := \{y_0,\dots,y_m\}$, and $I_m := (I \setminus X_m) \cup Y_m$. The target is $I_k=I'$. The base case is $m=0$. Since the path starts at $y_0 \in S_I$, the definition of $S_I$ gives \begin{align*} I_0 = I \cup \{y_0\} \in \mathcal I_1. \end{align*} Now assume $I_{m-1} \in \mathcal I_1$ for some $1 \le m \le k$. We must prove that replacing $x_m$ by $y_m$ keeps independence. Suppose instead that $I_m$ is dependent. Since $I_{m-1}$ is independent and $I_m = (I_{m-1} \setminus \{x_m\}) \cup \{y_m\}$, the dependent set $I_m$ contains an $M_1$-circuit $C$ with $y_m \in C$; also $x_m \notin C$, because $x_m$ has been removed from $I_m$. Since $1 \le m \le k$, the no-internal-source condition from the shortest-path step gives $y_m \notin S_I$. Therefore $I \cup \{y_m\}$ is dependent in $M_1$, while $I$ is independent in $M_1$. Hence there is a unique [fundamental circuit](/page/Fundamental%20Circuit) $F_m \subset I \cup \{y_m\}$ of $y_m$ over $I$ in $M_1$. The arc $x_m \to y_m$ means exactly that replacing $x_m$ by $y_m$ in $I$ is independent: \begin{align*} (I \setminus \{x_m\}) \cup \{y_m\} \in \mathcal I_1. \end{align*} For a fundamental circuit, an element $x \in I$ lies in $F_m$ precisely when deleting $x$ destroys the circuit and makes the exchange independent. Hence $x_m \in F_m$. The key point is to show that $F_m$ must also contain some earlier removed element $x_j$ with $j<m$. Suppose it did not, so $F_m \cap X_{m-1}=\varnothing$. The circuits $C$ and $F_m$ both contain $y_m$, while $x_m \in F_m\setminus C$. The [strong circuit elimination axiom](/page/Strong%20Circuit%20Elimination) then gives an $M_1$-circuit \begin{align*} C'\subset (C\cup F_m)\setminus \{y_m\} \end{align*} with $x_m\in C'$. Now $C\setminus\{y_m\}$ is contained in $(I\setminus X_m)\cup Y_{m-1}$, and the assumption $F_m\cap X_{m-1}=\varnothing$ gives $F_m\setminus\{y_m\}\subset I\setminus X_{m-1}$. Therefore \begin{align*} C'\subset (I\setminus X_{m-1})\cup Y_{m-1}=I_{m-1}, \end{align*} contradicting the induction hypothesis $I_{m-1}\in\mathcal I_1$. Thus $F_m$ contains some $x_j$ with $j<m$. By the definition of the $M_1$ exchange arcs, $x_j\in F_m$ gives a directed arc $x_j\to y_m$ in $D(I)$. This arc is a genuine shortcut: follow the original path from $y_0$ to $x_j$, take $x_j\to y_m$, and then follow the original suffix from $y_m$ to $y_k$. Since $j<m$, this skips at least one arc of the original path, producing a directed path from $S_I$ to $T_I$ shorter than $P$. This contradicts the minimal choice of $P$. Hence the assumed circuit $C$ cannot exist, so $I_m \in \mathcal I_1$. By induction over $m=0,1,\dots,k$, we obtain \begin{align*} I' = I_k \in \mathcal I_1. \end{align*} [/guided] [/step] [step:Prove the exchanged set is independent in $M_2$] We prove $I' \in \mathcal I_2$ by the reverse induction. For $0 \le m \le k$, define $X^m := \{x_{m+1},\dots,x_k\}$, $Y^m := \{y_m,\dots,y_k\}$, and $I^m := (I \setminus X^m) \cup Y^m$. The base case $m=k$ is $I^k=I \cup \{y_k\} \in \mathcal I_2$, because $y_k \in T_I$. Assume $0 \le m < k$ and $I^{m+1} \in \mathcal I_2$. If $I^m$ were dependent, then because $I^{m+1}$ is independent and $I^m=(I^{m+1}\setminus\{x_{m+1}\})\cup\{y_m\}$, there would be an $M_2$-circuit $C\subset I^m$ with $y_m\in C$ and $x_{m+1}\notin C$. Since $0 \le m<k$, the no-internal-target condition gives $y_m\notin T_I$, so $I\cup\{y_m\}$ is dependent in $M_2$. Let $F_m\subset I\cup\{y_m\}$ denote the unique [fundamental circuit](/page/Fundamental%20Circuit) of $y_m$ over $I$ in $M_2$. The arc $y_m\to x_{m+1}$ means $(I\setminus\{x_{m+1}\})\cup\{y_m\}\in\mathcal I_2$, hence $x_{m+1}\in F_m$. We claim that $F_m\cap\{x_{m+2},\dots,x_k\}\ne\varnothing$. If not, then applying [strong circuit elimination](/page/Strong%20Circuit%20Elimination) to the circuits $C$ and $F_m$, with common element $y_m$ and distinguished element $x_{m+1}\in F_m\setminus C$, gives an $M_2$-circuit $C'\subset (C\cup F_m)\setminus\{y_m\}$ containing $x_{m+1}$. Since $C\setminus\{y_m\}\subset (I\setminus X^m)\cup\{y_{m+1},\dots,y_k\}$ and $F_m\setminus\{y_m\}\subset I\setminus\{x_{m+2},\dots,x_k\}$ under the supposition, we get $C'\subset I^{m+1}$, contradicting $I^{m+1}\in\mathcal I_2$. Therefore there is an index $j>m+1$ with $x_j\in F_m$. By the definition of the $M_2$-arcs of $D(I)$, this gives a shortcut arc $y_m\to x_j$. Following $P$ from $y_0$ to $y_m$, then taking $y_m\to x_j$, and then following the original suffix from $x_j$ to $y_k$ gives a directed path from $S_I$ to $T_I$ with fewer arcs than $P$, contradicting the shortestness of $P$. Thus no such circuit exists, and reverse induction gives $I^0=I' \in \mathcal I_2$. [guided] The $M_2$ argument is the same shortest-path idea, but the path must be read from the terminal end because the $M_2$ exchange arcs point from new elements to old elements. For $0 \le m \le k$, define $X^m := \{x_{m+1},\dots,x_k\}$, $Y^m := \{y_m,\dots,y_k\}$, and $I^m := (I \setminus X^m) \cup Y^m$. We prove $I^m \in \mathcal I_2$ by descending induction on $m$. The base case is $m=k$. Since $y_k \in T_I$, the definition of $T_I$ gives \begin{align*} I^k = I \cup \{y_k\} \in \mathcal I_2. \end{align*} Now assume $I^{m+1} \in \mathcal I_2$ for some $0 \le m < k$. Suppose for contradiction that $I^m$ is dependent. Since $I^{m+1}$ is independent and $I^m = (I^{m+1} \setminus \{x_{m+1}\}) \cup \{y_m\}$, the dependent set $I^m$ contains an $M_2$-circuit $C$ with $y_m\in C$; also $x_{m+1}\notin C$, because $x_{m+1}$ has been removed from $I^m$. Since $0 \le m<k$, the no-internal-target condition from the shortest-path step gives $y_m\notin T_I$. Therefore $I\cup\{y_m\}$ is dependent in $M_2$, while $I$ is independent in $M_2$. Hence there is a unique [fundamental circuit](/page/Fundamental%20Circuit) $F_m\subset I\cup\{y_m\}$ of $y_m$ over $I$ in $M_2$. The arc $y_m\to x_{m+1}$ means that replacing $x_{m+1}$ by $y_m$ in $I$ is independent: \begin{align*} (I \setminus \{x_{m+1}\}) \cup \{y_m\} \in \mathcal I_2. \end{align*} Thus $x_{m+1}\in F_m$. We now prove that $F_m$ must contain a later removed element. Suppose $F_m\cap\{x_{m+2},\dots,x_k\}=\varnothing$. The circuits $C$ and $F_m$ both contain $y_m$, and $x_{m+1}\in F_m\setminus C$. [Strong circuit elimination](/page/Strong%20Circuit%20Elimination) gives an $M_2$-circuit \begin{align*} C'\subset (C\cup F_m)\setminus\{y_m\} \end{align*} with $x_{m+1}\in C'$. But $C\setminus\{y_m\}\subset (I\setminus X^m)\cup\{y_{m+1},\dots,y_k\}$, while the supposition gives $F_m\setminus\{y_m\}\subset I\setminus\{x_{m+2},\dots,x_k\}$. Hence \begin{align*} C'\subset I^{m+1}, \end{align*} contradicting $I^{m+1}\in\mathcal I_2$. Therefore $F_m$ contains $x_j$ for some $j>m+1$. By the definition of the $M_2$ exchange arcs, $x_j\in F_m$ gives the directed arc $y_m\to x_j$. The original path can then follow $P$ from $y_0$ to $y_m$, take this shortcut arc, and continue along the original suffix from $x_j$ to $y_k$. Since $j>m+1$, this skips part of $P$ and gives a shorter directed path from $S_I$ to $T_I$, contradicting the choice of $P$. Therefore $I^m$ is independent in $M_2$. Descending induction gives \begin{align*} I'=I^0 \in \mathcal I_2. \end{align*} [/guided] [/step] [step:Conclude that the directed path gives a common independent augmentation] We have shown that \begin{align*} I' \in \mathcal I_1 \cap \mathcal I_2. \end{align*} Thus $I'$ is common independent. Also $|I'|=|I|+1$. Therefore the directed path from $S_I$ to $T_I$ produces a common independent set of size $|I|+1$. Combining this with the first direction proves the equivalence. [/step]