  We prove that there is a universal constant $C>0$ with the following
property. Suppose that $n\in \mathbb{N}$ and that $\mathsf{A}=(a_{ij})\in
M_n(\mathbb{R})$ is a symmetric stochastic matrix. Denote the second-largest
eigenvalue of $\mathsf{A}$ by $\lambda_2(\mathsf{A})$. Then for $\mathrm{\it
any}$ finite-dimensional normed space $(X,\|\cdot\|)$ we have $$ \forall\,
x_1,\ldots,x_n\in X,\qquad \mathrm{dim}(X)\ge \frac12
\exp\left(C\frac{1-\lambda_2(\mathsf{A})}{\sqrt{n}}\bigg(\frac{\sum_{i=1}^n\sum_{j=1}^n\|x_i-x_j\|^2}{\sum_{i=1}^n\sum_{j=1}^na_{ij}\|x_i-x_j\|^2}\bigg)^{\frac12}\right).
$$ This implies that if an $n$-vertex $O(1)$-expander embeds with average
distortion $D\ge 1$ into $X$, then necessarily $\mathrm{dim}(X)\gtrsim n^{c/D}$
for some universal constant $c>0$, thus improving over the previously
best-known estimate $\mathrm{dim}(X)\gtrsim (\log n)^2/D^2$ of Linial, London
and Rabinovich, strengthening a theorem of Matou\v{s}ek, and answering a
question of Andoni, Nikolov, Razenshteyn and Waingarten.
