  The classic graphical Cheeger inequalities state that if $M$ is an $n\times
n$ symmetric doubly stochastic matrix, then \[
\frac{1-\lambda_{2}(M)}{2}\leq\phi(M)\leq\sqrt{2\cdot(1-\lambda_{2}(M))} \]
where $\phi(M)=\min_{S\subseteq[n],|S|\leq n/2}\left(\frac{1}{|S|}\sum_{i\in
S,j\not\in S}M_{i,j}\right)$ is the edge expansion of $M$, and $\lambda_{2}(M)$
is the second largest eigenvalue of $M$. We study the relationship between
$\phi(A)$ and the spectral gap $1-\text{Re}\lambda_{2}(A)$ for any doubly
stochastic matrix $A$ (not necessarily symmetric), where $\lambda_{2}(A)$ is a
nontrivial eigenvalue of $A$ with maximum real part. Fiedler showed that the
upper bound on $\phi(A)$ is unaffected, i.e.,
$\phi(A)\leq\sqrt{2\cdot(1-\text{Re}\lambda_{2}(A))}$. With regards to the
lower bound on $\phi(A)$, there are known constructions with \[
\phi(A)\in\Theta\left(\frac{1-\text{Re}\lambda_{2}(A)}{\log n}\right), \]
indicating that at least a mild dependence on $n$ is necessary to lower bound
$\phi(A)$.
  In our first result, we provide an exponentially better construction of
$n\times n$ doubly stochastic matrices $A_{n}$, for which
\[\phi(A_{n})\leq\frac{1-\text{Re}\lambda_{2}(A_{n})}{\sqrt{n}}.\] In fact, all
nontrivial eigenvalues of our matrices are $0$, even though the matrices are
highly nonexpanding. We further show that this bound is in the correct range
(up to the exponent of $n$), by showing that for any doubly stochastic matrix
$A$, \[\phi(A)\geq\frac{1-\text{Re}\lambda_{2}(A)}{35\cdot n}.\]
  Our second result extends these bounds to general nonnegative matrices $R$,
obtaining a two-sided quantitative refinement of the Perron-Frobenius theorem
in which the edge expansion $\phi(R)$ (appropriately defined), a quantitative
measure of the irreducibility of $R$, controls the gap between the
Perron-Frobenius eigenvalue and the next-largest real part of any eigenvalue.
