Q:

Optimal Matching Distance

I'm stuck on problem II.5.9 from Bhatia's Matrix Analysis.  The problem is as follows:

Let $\left(\lambda_1,\dots,\lambda_n\right)$ and $\left(\mu_1,\dots,\mu_n\right)$ be two $n$-tuples of complex numbers. Let
  $$
d(\lambda,\mu) = \min_\sigma \max_{1 \leq j \leq n}|\lambda_j - \mu_{\sigma(j)}|
$$
  where the minimum is taken over all permutations on $n$ symbols.  This is called the optimal matching distance....
Show that we also have
  $$
d(\lambda,\mu) = \max_{I,J \subset \{1,\dots,n\};|I| + |J| = n+1}
\min _{i \in I, j \in J} |\lambda_i - \mu_j|
$$

I'm not really sure how to approach this. $n=1,n=2$ doesn't yield much general insight, and $n=3$ is a bit too big to analyze effectively.  
I also can't find a good intuition for why minimizing one should maximize the other.  I'm thinking that a clever application of the pigeonhole principle fits in somewhere.
Any nudges in the right direction would be highly appreciated.

A:

The complex numbers and their (Euclidean) distances are a red herring. Here is
the actual theorem we should be proving:

Theorem 1. Let $A$ and $B$ be two finite sets such that $\left\vert
B\right\vert \geq\left\vert A\right\vert > 0$. Let $d_{i,j}$ be a real number
  for each $\left(  i,j\right)  \in A\times B$. Let
  \begin{equation}
m_1 =\min\limits_{\sigma
:A\rightarrow B\text{ injective}}\max\limits_{i\in A}d_{i,\sigma\left(
i\right)  }
\end{equation}
  and
  \begin{equation}
m_2 =\max\limits_{\substack{I\subseteq A;\ J\subseteq
B;\\\left\vert I\right\vert +\left\vert J\right\vert =\left\vert B\right\vert
+1}}\min\limits_{\left(  i,j\right)  \in I\times J}d_{i,j} .
\end{equation}
  Then,
  $m_1 = m_2$.

Our proof of this theorem will use two definitions and three lemmas.
The definitions as well as the first lemma come from basic
graph theory:

Definition. A bipartite graph means a simple graph
  $\left(V, E\right)$ equipped with two subsets $A$ and $B$ of $V$ having
  the following properties:

Each vertex $v \in V$ lies in exactly one of $A$ and $B$.
Each edge $e \in E$ connects a vertex in $A$ with a vertex in $B$.

The two subsets $A$ and $B$ are called the parts of the bipartite
  graph $G$. We usually denote the underlying simple graph
  $\left(V, E\right)$ by $G$ as well.
Definition. Let $G$ be a graph. A matching of $G$ means
  a set of disjoint edges of $E$. If $v$ is a vertex of $G$, and $M$ is
  a matching of $G$, then the vertex $v$ is said to be matched in $M$
  if and only if $v$ is an endpoint of some edge $e \in M$;
  in this case,
  the other endpoint of this edge $e$ is called the neighbor of $v$
  in $M$.
Lemma 2. Let $G$ be a bipartite graph with parts $A$ and $B$. For every
  subset $X$ of $A$, we let $N\left(  X\right)  $ denote the set of all vertices
  $b\in B$ adjacent to at least one vertex in $X$. A matching of $G$ is said to
  be $A$-saturating if each vertex of $A$ is matched. Then, $G$ has an
  $A$-saturating matching if and only if every subset $X$ of $A$ satisfies
  $\left\vert N\left(  X\right)  \right\vert \geq\left\vert X\right\vert $.

Lemma 2 is Hall's Marriage Theorem in its graph-theoretic
formulation,
and various proofs of it are well-known (e.g., one can be found
in Section 1.9 of
my Math 5707 Spring 2017 lecture 16 notes).
$\blacksquare$
The next lemma is a very simple property of real numbers
(but really has nothing to do with real numbers -- we could
state it for elements of any poset):

Lemma 3. Let $m_1$ and $m_2$ be two real numbers.
(a) We have $m_1 \leq m_2 $ if and only if each real number $g$
  satisfies the implication $\left(  m_2 \leq g\right)  \Longrightarrow\left(
m_1 \leq g\right)  $.
(b) We have $m_1 =m_2 $ if and only if each real number $g$ satisfies
  the equivalence $\left(  m_2 \leq g\right)  \Longleftrightarrow\left(
m_1 \leq g\right)  $.

The (essentially trivial) proof of Lemma 3 is left to the reader.
(Lemma 3 can also be viewed as a particular
case of Yoneda's lemma, or more precisely of the claim that the natural
homomorphisms from the functor $\operatorname*{Hom}\left(  M_2 ,-\right)  $
to the functor $\operatorname*{Hom}\left(  M_1 ,-\right)  $ are in bijection
with the morphisms $M_1 \rightarrow M_2$ when $M_1$ and $M_2$ are two
objects of a category. Indeed, the real numbers form a poset with their
usual total order, and you can view this poset as a category in which
$\operatorname{Hom}\left(x, y\right)$ is a $1$-element set whenever
$x \leq y$ and empty otherwise. Applying Yoneda's lemma to this category
yields Lemma 3.) $\blacksquare$
Finally, here is a lemma that connects this all to Theorem 1:

Lemma 4. Let $A$, $B$, $d_{i,j}$, $m_1$ and $m_2$ be as in Theorem 1.
  Assume that the sets $A$ and $B$ are disjoint. Let $g$ be a real number. Let
  $G$ be the bipartite graph with parts $A$ and $B$ whose edges are defined as
  follows: Two vertices $a\in A$ and $b\in B$ are adjacent if and only if
  $d_{a,b}\leq g$.
(a) We have $m_1 \leq g$ if and only if $G$ has an $A$-saturating matching.
(b) We have $m_2 \leq g$ if and only if every subset $X$ of $A$ satisfies
  $\left\vert N\left(  X\right)  \right\vert \geq\left\vert X\right\vert $.

Proof of Lemma 4. (a) First of all, we observe that there
exist injective maps $\sigma : A \to B$ (since $\left|A\right| \leq
\left|B\right|$). Hence, the minimum
$\min\limits_{\sigma
:A\rightarrow B\text{ injective}}\max\limits_{i\in A}d_{i,\sigma\left(
i\right)  }$
is well-defined (being a minimum over a nonempty finite set).
We have the following chain of equivalences:
$\left(  m_1 \leq g\right)  $
$\Longleftrightarrow\ \left(  \min\limits_{\sigma:A\rightarrow B\text{
injective}}\max\limits_{i\in A}d_{i,\sigma\left(  i\right)  }\leq g\right)
$ (since $m_1 =\min\limits_{\sigma:A\rightarrow B\text{ injective}}
\max\limits_{i\in A}d_{i,\sigma\left(  i\right)  }$)
$\Longleftrightarrow\ \left(  \text{there exists some injective }
\sigma:A\rightarrow B\text{ such that }\max\limits_{i\in A}d_{i,\sigma
\left(  i\right)  }\leq g\right)  $
$\Longleftrightarrow\ \left(  \text{there exists some injective }
\sigma:A\rightarrow B\text{ such that each }i\in A\text{ satisfies
}d_{i,\sigma\left(  i\right)  }\leq g\right)  $
(because $\max\limits_{i\in A}d_{i,\sigma\left(  i\right)  }\leq g$ holds if
and only if each $i\in A$ satisfies $d_{i,\sigma\left(  i\right)  }\leq g$)
$\Longleftrightarrow\ \left(  \text{there exists some injective }
\sigma:A\rightarrow B\text{ such that each }i\in A\text{ is adjacent to
}\sigma\left(  i\right)  \right)  $
(because a given vertex $i\in A$ satisfies $d_{i,\sigma\left(  i\right)  }\leq
g$ if and only if it is adjacent to $\sigma\left(  i\right)  $ (by the
definition of the edges of $G$))
$\Longleftrightarrow\ \left(  G\text{ has an }A\text{-saturating
matching}\right)  $.
The last of these equivalences might require some justification: On the one
hand, if there exists some injective $\sigma:A\rightarrow B$ such that each
$i\in A$ is adjacent to $\sigma\left(  i\right)  $, then $G$ has an
$A$-saturating matching (namely, the set $\left\{  \left\{  i,\sigma\left(
i\right)  \right\}  \ \mid\ i\in A\right\}  $ is such a matching). Conversely,
if $G$ has an $A$-saturating matching, then there exists some injective
$\sigma:A\rightarrow B$ such that each $i\in A$ is adjacent to $\sigma\left(
i\right)  $ (namely, we can fix an $A$-saturating matching $M$ of $G$, and let
$\sigma:A\rightarrow B$ be the map sending each $a\in A$ to the neighbor of
$a$ in the matching $M$). These two facts (combined) yield the equivalence in
question. This proves Lemma 4 (a).
(b) First of all, we observe the following technical fact:
If $I\subseteq A$ and $J \subseteq B$ are two subsets satisfying
$\left\vert I\right\vert +\left\vert J\right\vert =\left\vert B\right\vert
+1$, then both $I$ and $J$ are nonempty (since
$\left|I\right| \leq \left|A\right| \leq \left|B\right| <
\left|B\right|+1
= \left\vert I\right\vert +\left\vert J\right\vert$ shows that
$\left|J\right| > 0$, and since
$\left|J\right| \leq \left|B\right| < \left|B\right|+1
= \left\vert I\right\vert +\left\vert J\right\vert$ shows that
$\left|I\right| > 0$), and therefore the minimum
$\min\limits_{\left(  i,j\right)  \in I\times J}d_{i,j}$
is well-defined.
If $I\subseteq A$ and $J\subseteq B$ are two subsets
satisfying
$\left\vert I\right\vert +\left\vert J\right\vert =\left\vert B\right\vert
+1$, then we have the
following chain of equivalences:
$\left(  \min\limits_{\left(  i,j\right)  \in I\times J}d_{i,j}\leq
g\right)  $
$\Longleftrightarrow\ \left(  \text{there exists }\left(  i,j\right)  \in
I\times J\text{ such that }d_{i,j}\leq g\right)  $
$\Longleftrightarrow\ \left(  \text{there exist }i\in I\text{ and }j\in
J\text{ such that }d_{i,j}\leq g\right)  $
$\Longleftrightarrow\ \left(  \text{there exist }i\in I\text{ and }j\in
J\text{ such that }j\text{ is adjacent to }i\right)  $
(because two given vertices $i$ and $j$ of $G$ satisfy $d_{i,j}\leq g$ if and
only if $j$ is adjacent to $i$ (by the definition of the edges of $G$))
$\Longleftrightarrow\ \left(  \text{there exists }j\in J\text{ such that
}\underbrace{\left(  \text{there exists }i\in I\text{ such that }j\text{ is
adjacent to }i\right)  }_{\substack{\Longleftrightarrow\ \left(  \text{the
vertex }j\text{ is adjacent to at least one vertex in }I\right)
\\\Longleftrightarrow\ \left(  j\in N\left(  I\right)  \right)  \\\text{(by
the definition of }N\left(  I\right)  \text{)}}}\right)  $
$\Longleftrightarrow\ \left(  \text{there exists }j\in J\text{ such that }j\in
N\left(  I\right)  \right)  $
$\Longleftrightarrow\ \left(  J\cap N\left(  I\right)  \neq\varnothing\right)
$
$\Longleftrightarrow\ \left(  N\left(  I\right)  \not \subseteq
B\setminus J\right)  $
(since $N\left(I\right) \subseteq B$). Thus, we have proven the
equivalence
\begin{equation}
\left(  \min\limits_{\left(  i,j\right)  \in I\times J}d_{i,j}\leq
g\right)
\Longleftrightarrow\ \left(  N\left(  I\right)  \not \subseteq
B\setminus J\right) .
\label{1} \tag{1}
\end{equation}
On the other hand, for each $I\subseteq A$, we have the following equivalence:
\begin{align}
& \left(  N\left(  I\right)  \not \subseteq J\text{ for each }J\subseteq
B\text{ satisfying }\left\vert J\right\vert =\left\vert I\right\vert
-1\right) \\
\Longleftrightarrow\ & \left(  \left\vert N\left(  I\right)
\right\vert \geq\left\vert I\right\vert \right) .
\label{2} \tag{2}
\end{align}
[Proof of \eqref{2}: Fix $I\subseteq A$. We must prove the equivalence
\eqref{2}. In other words, we must prove the equivalence $\mathcal{A}
\Longleftrightarrow\mathcal{B}$, where $\mathcal{A}$ denotes the statement
$\left(  N\left(  I\right)  \not \subseteq J\text{ for each }J\subseteq
B\text{ satisfying }\left\vert J\right\vert =\left\vert I\right\vert
-1\right)  $, and where $\mathcal{B}$ denotes the statement $\left(
\left\vert N\left(  I\right)  \right\vert \geq\left\vert I\right\vert \right)
$.
We shall verify the $\Longrightarrow$ and $\Longleftarrow$ directions separately:
Proof of $\mathcal{A}\Longrightarrow\mathcal{B}$: Assume that the statement
$\mathcal{A}$ holds. We must prove the statement $\mathcal{B}$.
Assume the contrary. Then, $\left\vert N\left(  I\right)  \right\vert
<\left\vert I\right\vert $, so that $\left\vert N\left(  I\right)  \right\vert
\leq\left\vert I\right\vert -1$. Also, $N\left(I\right) \subseteq B$
(since $I \subseteq A$).
But $I\subseteq A$, so that $\left\vert I\right\vert \leq\left\vert
A\right\vert $ and thus $\left\vert I\right\vert -1\leq\left\vert A\right\vert
-1\leq\left\vert A\right\vert\leq\left\vert B\right\vert$. Recall also that $\left\vert N\left(
I\right)  \right\vert \leq\left\vert I\right\vert -1$. Thus, there exists some
subset $K$ of $B$ such that $\left\vert K\right\vert =\left\vert I\right\vert
-1$ and $N\left(  I\right)  \subseteq K$. (In fact, we can construct $K$ by
starting with the subset $N\left(  I\right)  $ and then adding further
elements of $B$ to it until it grows to size $\left\vert I\right\vert -1$. The
reason why we never run out of elements is that the target size is $\left\vert
I\right\vert -1\leq\left\vert B\right\vert $.) Consider such a subset $K$.
Now, applying statement $\mathcal{A}$ to $J=K$, we obtain $N\left(  I\right)
\not \subseteq K$. This contradicts $N\left(  I\right)  \subseteq K$. Thus, we
have found a contradiction; hence, our assumption was wrong. This proves that
$\mathcal{A}\Longrightarrow\mathcal{B}$.
Proof of $\mathcal{B}\Longrightarrow\mathcal{A}$: Assume that the statement
$\mathcal{B}$ holds. We must prove the statement $\mathcal{A}$.
Let $J\subseteq B$ be such that $\left\vert J\right\vert =\left\vert
I\right\vert -1$. From statement $\mathcal{B}$, we obtain $\left\vert N\left(
I\right)  \right\vert \geq\left\vert I\right\vert >\left\vert I\right\vert
-1=\left\vert J\right\vert $. Hence, $N\left(  I\right)  \not \subseteq J$.
Forget that we fixed $J$. We thus have shown that $N\left(  I\right)
\not \subseteq J$ for each $J\subseteq B$ satisfying $\left\vert J\right\vert
=\left\vert I\right\vert -1$. In other words, statement $\mathcal{A}$ holds.
This proves that $\mathcal{B}\Longrightarrow\mathcal{A}$.
Hence, the proof of the equivalence $\mathcal{A}\Longleftrightarrow
\mathcal{B}$ is complete. In other words, we have proven the equivalence \eqref{2}.]
We now have the following chain of equivalences:
$\left(  m_2 \leq g\right)  $
$\Longleftrightarrow\ \left(  \max\limits_{\substack{I\subseteq
A;\ J\subseteq B;\\\left\vert I\right\vert +\left\vert J\right\vert
=\left\vert B\right\vert +1}}\min\limits_{\left(  i,j\right)  \in I\times
J}d_{i,j}\leq g\right)  $ (since $m_2 =\max\limits_{\substack{I\subseteq
A;\ J\subseteq B;\\\left\vert I\right\vert +\left\vert J\right\vert
=\left\vert B\right\vert +1}}\min\limits_{\left(  i,j\right)  \in I\times
J}d_{i,j}$)
$\Longleftrightarrow\ \left(  \text{for each }I\subseteq A\text{ and
}J\subseteq B\text{ satisfying }\left\vert I\right\vert +\left\vert
J\right\vert =\left\vert B\right\vert +1\text{, we have }\underbrace{\min
\limits_{\left(  i,j\right)  \in I\times J}d_{i,j}\leq g}
_{\substack{\Longleftrightarrow\ \left(  N\left(  I\right)  \not \subseteq
B\setminus J\right)  \\\text{(by \eqref{1})}}}\right)  $
$\Longleftrightarrow\ \left(  \text{for each }I\subseteq A\text{ and
}J\subseteq B\text{ satisfying }\left\vert I\right\vert +\left\vert
J\right\vert =\left\vert B\right\vert +1\text{, we have }N\left(  I\right)
\not \subseteq B\setminus J\right)  $
$\Longleftrightarrow\ \left(  \text{for each }I\subseteq A\text{ and
}J\subseteq B\text{ satisfying }\left\vert I\right\vert
+\underbrace{\left\vert B\setminus J\right\vert }_{=\left\vert B\right\vert
-\left\vert J\right\vert }=\left\vert B\right\vert +1\text{, we have }N\left(
I\right)  \not \subseteq \underbrace{B\setminus\left(  B\setminus J\right)
}_{=J}\right)  $
(here, we have substituted $B\setminus J$ for $J$, since the map $\left\{
\text{subsets of }B\right\}  \rightarrow\left\{  \text{subsets of }B\right\}
,\ J\mapsto B\setminus J$ is a bijection)
$\Longleftrightarrow\ \left(  \text{for each }I\subseteq A\text{ and
}J\subseteq B\text{ satisfying }\underbrace{\left\vert I\right\vert
+\left\vert B\right\vert -\left\vert J\right\vert =\left\vert B\right\vert
+1}_{\Longleftrightarrow\ \left(  \left\vert J\right\vert =\left\vert
I\right\vert -1\right)  }\text{, we have }N\left(  I\right)  \not \subseteq
J\right)  $
$\Longleftrightarrow\ \left(  \text{for each }I\subseteq A\text{ and
}J\subseteq B\text{ satisfying }\left\vert J\right\vert =\left\vert
I\right\vert -1\text{, we have }N\left(  I\right)  \not \subseteq J\right)  $
$\Longleftrightarrow\ \left(  \text{for each }I\subseteq A\text{, we have
}\underbrace{\left(  N\left(  I\right)  \not \subseteq J\text{ for each
}J\subseteq B\text{ satisfying }\left\vert J\right\vert =\left\vert
I\right\vert -1\right)  }_{\substack{\Longleftrightarrow\ \left(  \left\vert
N\left(  I\right)  \right\vert \geq\left\vert I\right\vert \right)
\\\text{(by \eqref{2})}}}\right)  $
$\Longleftrightarrow\ \left(  \text{for each }I\subseteq A\text{, we have
}\left\vert N\left(  I\right)  \right\vert \geq\left\vert I\right\vert
\right)  $
$\Longleftrightarrow\ \left(  \text{for each }X\subseteq A\text{, we have
}\left\vert N\left(  X\right)  \right\vert \geq\left\vert X\right\vert
\right)  $
(here, we have renamed the index $I$ as $X$)
$\Longleftrightarrow\ \left(  \text{every subset }X\text{ of }A\text{
satisfies }\left\vert N\left(  X\right)  \right\vert \geq\left\vert
X\right\vert \right)  $.
This proves Lemma 4 (b). $\blacksquare$
Finally, we can prove Theorem 1.
Proof of Theorem 1. The sets $A$ and $B$ are only used for indexing
purposes. Hence, we can WLOG assume that $A$ and $B$ are disjoint. (For
example, we can achieve this by renaming each $a\in A$ as $\left(  0,a\right)
$, and renaming each $b\in B$ as $\left(  1,b\right)  $.)
Let $g$ be a real number. Define a bipartite graph $G$ as in Lemma 4. Then, we
have the following chain of equivalences:
$\left(  m_1 \leq g\right)  $
$\Longleftrightarrow\ \left(  G\text{ has an }A\text{-saturating
matching}\right)  $
(by Lemma 4 (a))
$\Longleftrightarrow\ \left(  \text{every subset }X\text{ of }A\text{
satisfies }\left\vert N\left(  X\right)  \right\vert \geq\left\vert
X\right\vert \right)  $
(by Lemma 2)
$\Longleftrightarrow\ \left(  m_2 \leq g\right)  $
(by Lemma 4 (b)).
In other words, we have the equivalence $\left(  m_2 \leq g\right)
\Longleftrightarrow\left(  m_1 \leq g\right)  $.
Now, forget that we fixed $g$. We thus have proven that each real number $g$
satisfies the equivalence $\left(  m_2 \leq g\right)  \Longleftrightarrow
\left(  m_1 \leq g\right)  $. According to Lemma 3 (b), this means that
$m_1 =m_2 $. Thus, Theorem 1 is proven. $\blacksquare$

