The $n$-Card Problem, Stochastic Matrices, and the Extreme Principle

Abstract

The $n$-card problem is to determine the minimal intervals $[u,v]$ such that for every $n \times n$ stochastic matrix $A$ there is an $n \times n$ permutation matrix $P$ (depending on $A$) such that tr$(PA) \in [u,v]$. This problem is closely related to classical mathematical problems from industry and management, including the linear assignment problem and the travelling salesman problem. The minimal intervals for the $n$-card problem are known only for $n \le 4$.

We introduce a new method of analysis for the $n$-card problem that makes repeated use of the Extreme Principle. We use this method to answer a question posed by Sands (2011), by showing that $[1,2]$ is a solution to the $n$-card problem for all $n \ge 2$. We also show that each closed interval of length $\frac{n}{n-1}$ contained in $[0,2)$ is a solution to the $n$-card problem for all $n \ge 2$.