On the second eigenvalue of random Markov matrices: a question of Bordenave, Caputo and Chafaï, and a golden-ratio crossing for softmax operators

Normalise the rows of an N × N matrix with independent, identically distributed, nonnegative entries of mean m, variance σ² and finite fourth moment, so that each row sums to one, and let λ₂ be the eigenvalue of second largest modulus of the resulting random Markov matrix. We prove that √N |λ₂| → σ/m almost surely. This answers a question raised by Bordenave, Caputo and Chafaï in 2008, and conjectured by Chafaï in 2007 for the Dirichlet Markov ensemble. No density is assumed, so lattice laws are included: for Bernoulli(p) weights, the random walk on the dense directed Erdős–Rényi graph, √N |λ₂| → √((1−p)/p). The upper bound comes from an exact reduction of the Markov normalisation to an i.i.d. matrix deformed by a random rank-one term, which is controlled through a null-vector lemma. The lower bound rests on a new almost-sure polynomial bound for the smallest singular value of √N P − z. Testing each row against a normal vector of the other rows, shifted by a multiple of the all-ones vector, removes the random diagonal created by the row sums. The nonnegativity of the weights makes the net approximation deterministic, and the inverse Littlewood–Offord theorem of Tao and Vu then applies. As a consequence, the circular law for √N P holds almost surely for every such law; it was previously known only under a bounded density. Combined with a uniform law of large numbers for the row entropies, the result gives the almost-sure limit of |λ₂| eh/2, where h is the entropy rate of the chain. This measures the second eigenvalue against the scale e−h/2, the upper bound known for random regular digraphs. For softmax operators P_ij ∝ eβ g_ij with independent standard Gaussian scores, the limit is √(eβ² − 1) e−β²/4, which crosses 1 exactly at β = √(2 ln φ) ≈ 0.9810, where φ is the golden ratio. For general scores the limit is an explicit function of the cumulant generating function. For walks with Porter–Thomas weights, the statistics of compound-nucleus couplings, the limit is 2eγ/2−1 ≈ 0.9819 (directed), and the same constant holds for |λ₂| eh/2/2 (reversible), where γ is Euler’s constant. The deterministic lemmas are verified in Lean 4 with Mathlib (32 declarations, no sorry). These include Brauer’s theorem, the null-vector lemma, the norm estimates and the counting steps of the singular-value argument.