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.