On the structure of stochastic matrices with a subdominant eigenvalue near 1 (Q1379113)

Let \(P\) be an \(n \times n\) stochastic matrix. Define the uncoupling measure \(\sigma(P)\) of \(P\) to be the minimum of \[ \Sigma_{i \in M_1, j \notin M_2} p_{ij} + \Sigma_{i \in M_2, j \notin M_1} p_{ij} \] over pairs \(M_1\) and \(M_2\) of disjoint subsets of \(\{1, \ldots, n\}\). The authors explore the relationship between \(\lambda_2(P)\), the second largest eigenvalue of \(P\) (in absolute value) and \(\sigma(P)\). They prove the easy result that if \(\lambda_2(P)\) is close to \(1\), then \(\sigma(P)\) must be small. The rest of the paper is devoted to examining the relationship between these quantities in specific examples.