Edge Expansion and Spectral Gap of Nonnegative Matrices
Jenish C. Mehta Leonard J. Schulman



Edge Expansion and Spectral Gap of Nonnegative Matrices
    Jenish C. Mehta 
 California Institute of Technology 
 jenishc@gmail.com Leonard J. Schulman 
 California Institute of Technology 
 schulman@caltech.edu
    December 30, 2023
============================================================================================================================================================


The classic graphical Cheeger inequalities state that if M is an
n× n symmetric doubly stochastic matrix, then 

    1-λ_2(M)/2≤ϕ(M)≤√(2·(1-λ_2(M)))

where ϕ(M)=min_S⊆[n],|S|≤ n/2(1/|S|∑_i∈ S,j∉SM_i,j)
is the edge expansion of M, and λ_2(M) is the second
largest eigenvalue of M. We study the relationship between ϕ(A)
and the spectral gap 1-λ_2(A) for any doubly
stochastic matrix A (not necessarily symmetric), where λ_2(A)
is a nontrivial eigenvalue of A with maximum real part. Fiedler
showed that the upper bound on ϕ(A) is unaffected, i.e., ϕ(A)≤√(2·(1-λ_2(A))).
With regards to the lower bound on ϕ(A), there are known constructions
with 

    ϕ(A)∈Θ(1-λ_2(A)/log n),

indicating that at least a mild dependence on n is necessary to
lower bound ϕ(A).

In our first result, we provide an exponentially better construction
of n× n doubly stochastic matrices A_n, for which


    ϕ(A_n)≤1-λ_2(A_n)/√(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, 

    ϕ(A)≥1-λ_2(A)/35· n.

As a consequence, unlike the symmetric case, there is a (necessary)
loss of a factor of n^α for 1/2≤α≤1
in lower bounding ϕ by the spectral gap in the nonsymmetric
setting.

Our second result extends these bounds to general matrices R with
nonnegative entries, to obtain a two-sided gapped refinement
of the Perron-Frobenius theorem. Recall from the Perron-Frobenius
theorem that for such R, there is a nonnegative eigenvalue r
such that all eigenvalues of R lie within the closed disk of radius
r about 0. Further, if R is irreducible, which means ϕ(R)>0
(for suitably defined ϕ), then r is positive and all other
eigenvalues lie within the open disk, so (with eigenvalues
sorted by real part), λ_2(R)<r. An extension of Fiedler's
result provides an upper bound and our result provides the corresponding
lower bound on ϕ(R) in terms of r-λ_2(R), obtaining
a two-sided quantitative version of the Perron-Frobenius theorem. 





§ INTRODUCTION




 §.§ Motivation and main result


We study the relationship between edge expansion and second eigenvalue
of nonnegative matrices. We restrict to doubly stochastic matrices
for exposition in the introduction, since the definitions are simpler
and it captures most of the key ideas. The extension to general nonnegative
matrices is treated in Section <ref>. Let A
be an n× n doubly stochastic matrix, equivalently interpreted
as a bi-regular weighted digraph. The edge expansion of A,
denoted as ϕ(A), is defined as


    ϕ(A)=min_S⊆[n],|S|≤ n/2∑ _i∈ S,j∉SA_i,j/|S|.

The fact that A is doubly stochastic implies that ϕ(A)=ϕ(A^T).
ϕ is a measure of how much the graph would have to be
modified for it to lose strong-connectedness; it also lower bounds
how frequently, in steady state, the associated Markov chain
switches between the blocks of any bi-partition; thus, it fundamentally
expresses the extent to which the graph is connected.

The connection between edge expansion and the second eigenvalue has
been of central importance in the case of symmetric doubly
stochastic matrices M (equivalently, reversible Markov chains with
uniform stationary distribution). For such M, let the eigenvalues
be 1=λ_1≥λ_2≥…≥λ_n≥-1.
The Cheeger inequalities give two-sided bounds between the edge expansion
ϕ(M) and the spectral gap 1-λ_2(M). 

<cit.> (Cheeger's
inequalities for symmetric doubly stochastic matrices) Let M be
a symmetric doubly stochastic matrix, then 

    1-λ_2(M)/2 ≤ ϕ(M) ≤ √(2·(1-λ_2(M))).



This is closely related to earlier versions for Riemannian manifolds
<cit.>. Notably, the inequalities in Theorem <ref>
do not depend on n. Further, they are tight up to constants –
the upper bound on ϕ is achieved by the cycle and the lower
bound by the hypercube.

The key question we address in this work is whether or to what extent
the Cheeger inequalities survive for nonsymmetric doubly
stochastic matrices (the question was already asked, for e.g., in
<cit.>). Let A be a doubly stochastic matrix, not necessarily
symmetric. The eigenvalues of A lie in the unit disk around the
origin in the complex plane, with an eigenvalue 1 called the trivial
or stochastic eigenvalue corresponding to the eigenvector 1
(the all 1's vector), and all other eigenvalues considered nontrivial.
Let the eigenvalues of A be ordered so that 1=λ_1≥λ_2≥…≥λ_n≥-1.
The spectral gap will be defined as 1-λ_2(A). There
are three motivations for this definition: first, the continuous-time
Markov chain based on A is exp(t·(A-I)), and this spectral
gap specifies the largest norm of any of the latter's nontrivial eigenvalues;
second, λ_2(A)=1 if and only if ϕ=0 (i.e., if
the matrix is reducible); finally, this gap lower bounds the distance
(in the complex plane) between the trivial and any nontrivial eigenvalue.

It was noted by Fiedler <cit.> that the upper
bound on ϕ in Cheeger's inequality (Theorem <ref>)
carries over easily to general doubly stochastic matrices, because
for M=(A+A^T)/2, ϕ(A)=ϕ(M) and λ_2(A)≤λ_2(M).
(In fact, Fiedler made a slightly different conclusion with these
observations, but they immediately give the upper bound on ϕ,
see Appendix <ref> for an extension and proof). 

 (Fiedler <cit.>) Let
A be any n× n doubly stochastic matrix, then 

    ϕ(A)≤√(2·(1-λ_2(A))).



It remained to investigate the other direction, i.e., the lower bound
on ϕ(A) in terms of the spectral gap 1-λ_2(A).
Towards this end, we define the function 

 Γ(n)=min{ϕ(A)1-λ_2(A): A is an  doubly stochastic matrix} . 


For symmetric doubly stochastic matrices this minimum is no less than
1/2. However, for doubly stochastic matrices A that are not
necessarily symmetric, there are known (but perhaps not widely known)
examples demonstrating that it is impossible to have a function Γ
entirely independent of n. These examples, discussed in Section
<ref>, show that 

    Γ(n)≤1log n.


One reason that ϕ and 1-λ_2 are important is their
connection to mixing time τ – the number of steps after which
a random walk starting at any vertex converges to the uniform distribution
over the vertices. For the case of symmetric doubly stochastic matrices
– or in general reversible Markov chains – it is simple to show
that τ∈ O(log n/1-λ_2), and by
Cheeger's inequality (Theorem <ref>), it further gives
τ∈ O(log n/ϕ^2) where n is the
number of vertices. For the case of general doubly stochastic matrices
– or in general not-necessarily-reversible Markov chains – it
still holds that τ∈ O(log n/ϕ^2)
by a result of Mihail (<cit.>, and see <cit.>).
Depending on the situation, either λ_2 or ϕ may
be easier to estimate. Most often, one is interested in concisely-specified
chains on exponential-size sets, i.e., the number of vertices is n
but the complexity parameter is log n. In this case, either ϕ
or λ_2 (for the reversible case) can be used to estimate
τ. However, if the matrix or chain is given explicitly, then
one reason the Cheeger inequalites are useful is because it is simpler
to estimate τ using λ_2 which is computable in P
while computing ϕ is NP-hard <cit.>.

From the point of view of applications to Markov Chain Monte Carlo
(MCMC) algorithms, a log n loss in the relation between ϕ
and 1-λ_2 as implied by (<ref>),
is not a large factor. For MCMC algorithms, since “n” is the
size of the state space being sampled or counted and the underlying
complexity parameter is log n, if it were true that Γ(n)≥log^-cn
for some constant c, then the loss in mixing time estimates would
be polynomial in the complexity parameter, and thus, the quantity
1-λ_2 could still be used to obtain a reasonable estimate
of the mixing time even in the case of nonsymmetric doubly stochastic
matrices.

However, the truth is much different. Our main result is that Γ(n)
does not scale as log^-cn, but is exponentially smaller. 

 (Bounds on Γ) 

    135· n≤Γ(n)≤1√(n).



We give an explicit construction of doubly stochastic matrices
A_n for the upper bound on Γ. This construction of highly
nonexpanding doubly stochastic matrices has, in addition, the surprising
property that every nontrivial eigenvalue is 0. Thus, for
non-reversible Markov chains, the connection between ϕ and λ_2
breaks down substantially, in that the upper bound on mixing time
obtained by lower bounding ϕ by the spectral gap 1-λ_2
can be be exponentially weaker (when the complexity parameter is log n)
than the actual mixing time, whereas for reversible chains there is
at worst a quadratic loss.

This theorem has a very natural extension to general nonnegative matrices,
as we next describe.



 §.§ General nonnegative matrices and a two-sided
quantitative refinement of the Perron-Frobenius theorem


We extend our results to general nonnegative matrices R. By the
Perron-Frobenius theorem (see Theorem <ref>),
since R is nonnegative, it has a nonnegative eigenvalue r (called
the PF eigenvalue) that is also largest in magnitude amongst all eigenvalues,
and the corresponding left and right eigenvectors u and v have
all nonnegative entries. Further, if R is irreducible, i.e., the
underlying weighted digraph on edges with positive weight is strongly
connected (for every (i,j) there is a k such that R^k(i,j)>0),
then r is a simple eigenvalue, and u and v have all positive
entries. We henceforth assume that nonzero nonnegative R has been
scaled (to 1/rR) so that r=1. Thus we can again write
the eigenvalues of R as 1=λ_1(R)≥λ_2(R)≥⋯≥λ_n(R)≥-1.
Scaling changes the spectrum but not the edge expansion (which we
define next), so this canonical scaling is necessary before the two
quantities can be compared.

Defining the edge expansion of R is slightly delicate so we explain
the reasoning after Definition <ref>, and
present only the final definition (see Definition <ref>)
here. Consider u and v as left and right eigenvectors for eigenvalue
1 of R. If every such pair (u,v) for R has some i
such that u(i)=0 or v(i)=0, then define ϕ(R)=0. Otherwise,
let u and v be some positive eigenvectors for eigenvalue 1 of
R, normalized so that ⟨ u,v⟩=1, and define the edge
expansion of R as 

    ϕ(R)=min_S⊆[n],∑_i∈ Su_i· v_i≤1/2∑ _i∈ S,j∈SR_i,j· u_i· v_j∑ _i∈ Su_i· v_i.

Given this definition of ϕ(R), we show the following. 

Let R be a nonnegative matrix with
PF eigenvalue 1, and let u and v be any corresponding left
and right eigenvectors. Let κ=min_iu_i· v_i, and
if κ>0, let u and v be normalized so that ⟨ u,v⟩=1.
Then

    1/30·1-λ_2(R)n+ln(1/κ) ≤ ϕ(R) ≤ √(2·(1-λ_2(R))).



The upper bound in Theorem <ref> is a straightforward extension
of Fiedler's bound (Lemma <ref>) based on the above mentioned
definition of ϕ (Definition <ref>).
Also note that the lower bound in Theorem <ref> can be obtained
by setting κ=1/n in Theorem <ref>.
The upper bound is proven in Appendix <ref>
and the lower bound is shown in Section <ref>.

Since Theorem <ref> gives a two-sided relation
between the second eigenvalue of nonnegative matrices and their
edge expansion, it gives a two-sided quantitative refinement of the
Perron-Frobenius theorem. Although the Perron-Frobenius theorem implies
that the nontrivial eigenvalues of an irreducible nonnegative matrix
R with PF eigenvalue 1 have real part strictly less than 1,
it does not give any concrete separation. Further, it also does not
provide a qualitative (or quantitative) implication in the other direction
– whether a nonnegative matrix R with all nontrivial eigenvalues
having real part strictly less than 1 implies that R is
irreducible. Theorem <ref> comes to remedy this
by giving a lower and upper bound on the spectral gap in terms of
ϕ, a quantitative measure of the irreducibility of R. We
are not aware of any previous result of this form.



 §.§ Mixing time


The third quantity we study is the mixing time of general nonnegative
matrices, and we relate it to their singular values, edge expansion,
and spectral gap. This helps us obtain new bounds on mixing time,
and also obtain elementary proofs for known results. These results
are treated in detail in the second part of the paper, in Section
<ref>.



 §.§ Perspectives




  §.§.§ Matrix perturbations


Let A be a nonnegative matrix with PF eigenvalue 1 and corresponding
positive left and right eigenvector w with ⟨ w,w⟩=1,
and let κ=min_iw_i^2. Given such A, it is certainly
easier to calculate its spectrum than its edge expansion. However,
in other cases, e.g., if the matrix is implicit in a nicely structured
randomized algorithm (as in the canonical paths method <cit.>),
the edge expansion may actually be easier to bound. From this point
of view, a lower bound on ϕ(A) in terms of the spectral gap
is an eigenvalue perturbation bound. Specifically, one might
write a nonnegative matrix A with small edge expansion ϕ(A)
as a perturbation of another nonnegative matrix A_0, i.e., 

    A=A_0+δ· B

where A_0 has disconnected components S,S^c (for S achieving
ϕ(A)), and B is a matrix such that B_2≤1, Bw=0
and B^Tw=0. Due to the conditions on A and B, A_0
has PF eigenvalue 1 with left and right eigenvector w, and since
BD_w1=0, writing 1_S=1-1_S,
we have, 

    |⟨1_S,D_wBD_w1_S⟩/⟨1_S,D_wD_w1_S⟩|=|⟨1_S,D_wBD_w1_S⟩/⟨1_S,D_wD_w1_S⟩|=|⟨ D_w1_S,BD_w1_S⟩/⟨ D_w1_S,D_w1_S⟩|≤B_2≤1,

and it follows then that ϕ(R_0)-δ≤ϕ(R)≤ϕ(R_0)+δ,
and since in this case ϕ(R_0)=0, so ϕ(A)≤δ.
Edge expansion is therefore stable with respect to perturbation by
B. What about the spectral gap?

A_0 has (at least) a double eigenvalue at 1, and A retains
a simple eigenvalue at 1, so it is natural to try to apply eigenvalue
stability results, specifically Bauer-Fike (<cit.>,
<cit.> VIII), to obtain an upper bound on |1-λ_2(A)|
(and therefore also on 1-λ_2(A)). However, Bauer-Fike
requires A_0 to be diagonalizable, and the quality of the bound
depends upon the condition number of the diagonalizing change of basis[The condition number is inf(B·B^-1) over B such
that BAB^-1 is diagonal, with · being operator norm.]. There are extensions of Bauer-Fike which do not require diagonalizability,
but deteriorate exponentially in the size of the Jordan block, and
the bound still depends on the condition number of the (now Jordan-izing)
change of basis (<cit.> Corollary 3.2). Since there is no
a priori (i.e., function of n) bound on these condition numbers,
these tools unfortunately do not imply any, even weak, result analogous
to Theorem <ref>.

In summary, the lower bound in Theorem <ref> should be viewed
as a new eigenvalue perturbation bound: 

    1-λ_2(A)≤30·δ·(n+ln(1/κ)).

A novel aspect of this bound, in comparison with the prior literature
on eigenvalue perturbations, is that it does not depend on the condition
number (or even the diagonalizability) of A or of A_0.



  §.§.§ Relating eigenvalues of a nonnegative matrix and its additive symmetrization


Let A be any nonnegative matrix with PF eigenvalue 1, and corresponding
positive left and right eigenvector w. Our result helps to give
the following bounds between the second eigenvalue of a nonnegative
matrix A and that of its additive symmetrization 1/2(A+A^T). 

Let A be any nonnegative matrix
with PF eigenvalue 1 and corresponding positive left and right eigenvector
w, let κ=min_iw_i^2 and M=1/2(A+A^T).Then

    1/1800(1-λ_2(A)/n+ln(1/κ))^2≤1-λ_2(M)≤1-λ_2(A).



The bounds immediately follows from Theorem <ref>
and the fact that ϕ is unchanged by additive symmetrization.
We remark that any improved lower bound on 1-λ_2(M) in
terms of 1-λ_2(A) will help to improve the lower bound
in Theorem <ref>. As a consequence of Lemma <ref>,
any bound based on the second eigenvalue of symmetric nonnegative
matrices can be applied, with dimension-dependent loss, to nonnegative
matrices that have identical left and right eigenvector for the PF
eigenvalue.

An example application of Lemma <ref>
is the following. For some doubly stochastic A (not necessarily
symmetric), consider the continuous time Markov Chain associated with
it, exp(t·(A-I)). It is well-known (for instance, <cit.>)
that for any standard basis vector x_i,


    ‖exp(t·(A-I))x_i-1/n1‖ _1^2≤ n·exp(-2·(1-λ_2(M))· t).

Thus, using Lemma <ref>, we immediately
get the bound in terms of the second eigenvalue of A itself (instead
of its additive symmetrization), 

    ‖exp(t·(A-I))x_i-1/n1‖ _1^2≤ n·exp(-1/1800(1-λ_2(A)/n+ln(1/κ))^2· t).





  §.§.§ The role of singular values


Although in the symmetric case singular values are simply the absolute
values of the eigenvalues, the two sets can be much less related in
the nonsymmetric case. It is not difficult to show the following (see
Appendix <ref>). 

 Let A be a nonnegative matrix with
PF eigenvalue 1, and let w be the positive vector such that Aw=w
and A^Tw=w. Then 

    1-σ_2(A)/2≤ϕ(A),

where σ_2(A) is the second largest singular value of A. 



The proof is given in Appendix <ref>. 

Despite appearances, this tells us little about edge expansion[Lazy-fying does not help since it can change singular values of nonsymmetric
matrices sharply (unlike eigenvalues), so it would not be possible
to obtain an estimate on ϕ in terms of the singular values of
the original matrix A.]. To see this, consider the directed cycle on n vertices, for
which every singular value (and in particular σ_2) is 1,
so Lemma <ref> gives a lower bound of 0 for ϕ,
although ϕ=2/n. A meaningful lower bound should be 0 if and
only if the graph is disconnected, i.e. it should be continuous in
ϕ. An even more striking example is that of de Bruijn graphs
(described in Section <ref>), for which
half the singular values are 1, although ϕ=Θ(1/log n).
Eigenvalues, on the other hand, are more informative, since a nonnegative
matrix with PF eigenvalue 1 has a multiple eigenvalue at 1
if and only if, as a weighted graph, it is disconnected.

Despite these observations, singular values can be useful to infer
information about mixing time, and can be used to recover all known
upper bounds on mixing time using ϕ, as discussed in Section
<ref> and Lemma <ref>. 


Outline: We state the preliminary definitions, theorems, and notations
in Section <ref>. We give the construction for
the upper bound on Γ in Theorem <ref> in Section
<ref>, and the lower bound on Γ
will follow from the general lower bound on ϕ in Theorem <ref>.
We show the upper bound on ϕ in Theorem <ref>
in Appendix <ref>, and show the lower bound
on ϕ in Section <ref>. We relate
mixing time to singular values, edge expansion, and the spectral gap
in Section <ref> respectively. We defer all proofs to the
Appendix.



§ PRELIMINARIES


We consider doubly stochastic matrices A∈ℝ^n× n
which are nonnegative matrices with entries in every row and column
summing to 1. We also consider general nonnegative matrices R,
and say that R is strongly connected or irreducible,
if there is a path from s to t for every pair (s,t) of vertices
in the underlying digraph on edges with positive weight, i.e. for
every (s,t) there exists k>0 such that R^k(s,t)>0. We say
R is weakly connected, if there is a pair of vertices (s,t)
such that there is a path from s to t but no path from t
to s in the underlying digraph (on edges with positive weight).
We restate the Perron-Frobenius theorem for convenience. 

(Perron-Frobenius theorem <cit.>)
Let R∈ℝ^n× n be a nonnegative matrix. Then the
following hold for R. 


  * R has some nonnegative eigenvalue r, such that all other eigenvalues
have magnitude at most r, and R has nonnegative left and right
eigenvectors u and v for r. 

  * If R has some positive left and right eigenvectors u
and v for some eigenvalue λ, then λ=r. 

  * If R is irreducible, then r is positive and simple (unique),
u and v are positive and unique, and all other eigenvalues have
real part strictly less than r. 



We denote the all 1's vector by 1, and note that
for a doubly stochastic matrix A, 1 is both the
left and right eigenvector with eigenvalue 1. We say that 1 is
the trivial (or stochastic) eigenvalue, and 1
is the trivial (or stochastic) eigenvector, of A. All other
eigenvalues of A (corresponding to eigenvectors that are not trivial)
will be called nontrivial (or nonstochastic) eigenvalues
of A. Similarly, by Perron-Frobenius (Theorem <ref>,
part 1), a nonnegative matrix R will have a simple nonnegative
eigenvalue r such that all eigenvalues have magnitude at most r,
and it will be called the trivial or PF eigenvalue of R,
and all other eigenvalues of R will be called nontrivial.
 The left and right eigenvectors corresponding to r will be called
the trivial or PF left eigenvector and trivial or PF
right eigenvector. This leads us to the following definition. 

(Second eigenvalue) If A is a doubly stochastic matrix,
then λ_2(A) is the nontrivial eigenvalue of A with the
maximum real part, and λ_m(A) is the nontrivial eigenvalue
that is largest in magnitude. Similarly, if R is any general nonnegative
matrix with PF eigenvalue 1, then λ_2(R) is the nontrivial
eigenvalue with the maximum real part, i.e., 1=λ_1(R)≥λ_2(R)≥⋯≥λ_n(R)≥-1,
and λ_m(R) is the nontrivial eigenvalue that is largest
in magnitude. 


We will also consider singular values of nonnegative matrices A
with identical positive left and right eigenvector w for PF eigenvalue
1, and denote them as 1=σ_1(A)≥σ_2(A)≥⋯≥σ_n(A)≥0
(see Lemma <ref> for proof of σ_1(A)=1).
We denote (i,j)'th entry of M∈ℂ^n× n by M(i,j)
or M_i,j depending on the importance of indices in context, denote
the conjugate-transpose of M as M^* and the transpose of M
as M^T. Any M∈ℂ^n× n has a Schur decomposition
(see, e.g., <cit.>) M=UTU^* where T is an upper triangular
matrix whose diagonal entries are the eigenvalues of M, and U
is a unitary matrix. When we write “vector” we mean by default
a column vector. For a vector v, we write v(i) or v_i to
denote its i'th entry. For any two vectors x,y∈ℂ^n,
we use the standard inner product ⟨ x,y⟩=∑_i=1^nx_i^*· y_i
defining the norm x_2=√(⟨ x,x⟩). We write
u⊥ v to indicate that ⟨ u,v⟩=0. Note that ⟨ x,My⟩=⟨ M^*x,y⟩.
We denote the operator norm of M by M_2=max_u:u_2=1Mu_2,
and recall that the operator norm is at most the Frobenius norm, i.e.,
M_2≤√(∑_i,j|M_i,j|^2). We write D_u
for the diagonal matrix whose diagonal contains the vector u. Recall
the Courant-Fischer variational characterization of eigenvalues for
symmetric real matrices, applied to the second eigenvalue: 

    max_u⊥ v_1⟨ u,Mu⟩/⟨ u,u⟩=λ_2(M),

where v_1 is the eigenvector for the largest eigenvalue of M.
We will use the symbol J for the all 1's matrix divided by n,
i.e., J=1/n1·1^T.

We say that any subset S⊆[n] is a cut, denote its
complement by S, and denote the characteristic
vector of a cut as 1_S, where 1_S(i)=1
if i∈ S and 0 otherwise. 

(Edge expansion of doubly stochastic
matrices) For a doubly stochastic matrix A, the edge expansion
of the cut S is defined as 

    ϕ_S(A):=⟨1_S,A1_S⟩min{⟨1_S,A1⟩,⟨1_S,A1⟩}

and the edge expansion of A is defined as 

    ϕ(A)=min_S⊆[n]ϕ_S(A)=min_S⊆[n]⟨1_S,A1_S⟩min{⟨1_S,A1⟩,⟨1_S,A1⟩}=min_S,|S|≤ n/2∑ _i∈ S,j∈SA_i,j/|S|.



We wish to extend these notions to general nonnegative matrices R.
Since eigenvalues and singular values of real matrices remain unchanged
whether we consider R or R^T, the same should hold of a meaningful
definition of edge expansion. However, note that Definition <ref>
has this independence only if the matrix is Eulerian, i.e., R1=R^T1.
Thus, to define edge expansion for general matrices, we transform
R using its left and right eigenvectors u and v for eigenvalue
1 to obtain D_uRD_v, which is indeed Eulerian, since 

    D_uRD_v1=D_uRv=D_uv=D_uD_v1=D_vD_u1=D_vu=D_vR^Tu=D_vR^TD_u1.

Since D_uRD_v is Eulerian, we can define the edge expansion
of R similar to that for doubly stochastic matrices:

 (Edge expansion of nonnegative
matrices) Let R∈ℝ^n× n be a nonnegative matrix
with PF eigenvalue 1. If there are no positive (i.e., everywhere
positive) left and right eigenvectors u and v for eigenvalue
1, then define the edge expansion ϕ(R)=0. Else, let u and
v be any (see Lemma <ref> for justification) positive
left and right eigenvectors for eigenvalue 1, normalized so that ⟨ u,v⟩=1.
The edge expansion of the cut S is defined as 

    ϕ_S(R):=⟨1_S,D_uRD_v1_S⟩min{⟨1_S,D_uRD_v1⟩,⟨1_S,D_uRD_v1⟩}

and the edge expansion of R is defined as 

    ϕ(R)=min_S⊆[n]ϕ_S(R)=min_S⊆[n],∑_i∈ Su_i· v_i≤1/2⟨1_S,D_uRD_v1_S⟩⟨1_S,D_uD_v1⟩=min_S⊆[n],∑_i∈ Su_i· v_i≤1/2∑ _i∈ S,j∈SR_i,j· u_i· v_j∑ _i∈ Su_i· v_i.




Let R∈ℝ^n× n be a nonnegative
matrix with PF eigenvalue 1. Then the value of ϕ(R) according
to Definition <ref> is independent of the
choice of the specific (left and right) eigenvectors u and v
for eigenvalue 1 of R. 



Let G be the underlying unweighted directed graph for R, where
there is an edge (u,v) in G if and only if R_u,v>0. We
prove the lemma based on the structure of G. Let G be maximally
partitioned into k weakly connected components. 


  * If G has some weakly connected component which does not
have a 1 eigenvalue, then for any pair of left and right eigenvectors
u and v for eigenvalue 1, there will be at least one entry i
such that u_i=0 or v_i=0. For such matrices R, from Definition
<ref>, ϕ(R)=0. 

  * If all weakly connected components of G have eigenvalue 1, but
there is some weakly connected component S that is not strongly
connected, then there is no positive pair of eigenvectors u and
v for R, or even for S. Observe that S=[[ A B; 0 C ]] with B≠0, else G is not maximally partitioned. For the
sake of contradiction, let x and y be positive left and right
eigenvectors for eigenvalue 1 of S. From Sy=y and S^Tx=x,
we get that Ay_1+By_2=y_1 and A^Tx_1=x_1 with x
and y partitioned into x_1,x_2 and y_1,y_2 based
on the sizes of A,B,C. Thus, 

    ⟨ x_1,y_1⟩=⟨ x_1,Ay_1+By_2⟩=⟨ A^Tx_1,y_1⟩+⟨ x_1,By_2⟩=⟨ x_1,y_1⟩+⟨ x_1,By_2⟩

implying ⟨ x_1,By_2⟩=0 which is a contradiction
since x_1 and y_1 are positive and there is some entry in
B which is not 0. Thus, since every pair of eigenvectors x and
y for eigenvalue 1 of S has some entry i with x_i=0
or y_i=0, every pair of (left and right) eigenvectors u and
v for R (for eigenvalue 1) has some entry i which is 0, and
so by Definition <ref>, ϕ(R)=0. 

  * If G consists of one strongly connected component (i.e.,
k=1), then by Perron-Frobenius (Theorem <ref>,
part 3), there is a unique (up to scaling) pair of positive
eigenvectors u and and v for eigenvalue 1.

  * The remaining case is that G has k≥2 strongly connected components
each with eigenvalue 1. By Perron-Frobenius (Theorem <ref>),
there is some pair of positive left and right eigenvectors u and
v for eigenvalue 1 (obtained by concatenating the positive left
and right eigenvectors for each component individually). Choose the
set S to be one of the components (the one for which the denominator
of equation (<ref>) is at most 1/2), then the numerator
of equation (<ref>) will be 0, and thus ϕ(R)=0 even
in this case, corresponding to the existence of a strict subset of
vertices with no expansion. 

Thus, Definition <ref> for ϕ(R) does
not depend on the specific choice of u and v. 

The Perron-Frobenius theorem (Theorem <ref>,
part 3) can now be restated in terms of ϕ(R) and λ_2(R)
as follows. 

(Perron-Frobenius, part 3 of Theorem
<ref>, restated) Let R be a nonnegative
matrix with PF eigenvalue 1. If ϕ(R)>0, then λ_2(R)<1. 


Further, we obtain the following converse of Lemma <ref>. 

(Converse of Lemma <ref>)
Let R be a nonnegative matrix with PF eigenvalue 1. If λ_2(R)<1,
and there exists a pair of positive left and right eigenvectors
u and v for eigenvalue 1 of R, then ϕ(R)>0. 



We show the contrapositive. Let R be as stated and let ϕ(R)=0.
From Definition <ref>, if there are no positive
eigenvectors u and v for eigenvalue 1, the lemma holds. So assume
there are some positive u and v for eigenvalue 1 of R. Since
ϕ(R)=0, there is some set S for which ϕ_S(R)=0, or
∑_i∈ S,j∈SR_i,j· u_i· v_j=0.
But since u_i>0 and v_i>0 for each i, and since R
is nonnegative, it implies that for each i∈ S,j∈S,
R_i,j=0. Further, since D_uRD_v is Eulerian, i.e. D_uRD_v1=D_vR^TD_u1,
it implies that ∑_i∈S,j∈ SR_i,j· u_i· v_j=0,
further implying that R_i,j=0 for each i∈S,j∈ S.
As a consequence, v can be rewritten as two vectors v_S and
v_S, where v_S(i)=v(i) if i∈ S and v_S(i)=0
otherwise, and similarly v_S. Similarly, split u
into u_S and u_S. Note that v_S and v_S
are linearly independent (in fact, orthogonal), and both are right
eigenvectors for eigenvalue 1 (similarly u_S and u_S
as left eigenvectors). Thus, this implies that eigenvalue 1 for R
has multiplicity at least 2, and thus λ_2(R)=1, as required. 

The upper and lower bounds on ϕ(R) in Theorem <ref>
are quantitative versions of Lemmas <ref>
and <ref> respectively.

We note that Cheeger's inequalities hold not only for any symmetric
doubly stochastic matrix, but also for any nonnegative matrix R
which satisfies detailed balance. We say that a nonnegative matrix
R with positive left and right eigenvectors u and v for PF
eigenvalue 1 satisfies detailed balance if D_uRD_v is
symmetric, which generalizes the usual definition of detailed balance
(or reversibility) for stochastic matrices. We first note that if
R satisfies the condition of detailed balance, then R has all
real eigenvalues. To see this, let W=D_u^1/2D_v^-1/2
where the inverses are well-defined since we assume u and v
are positive (else ϕ=0 by definition), and A=WRW^-1 where
A has same eigenvalues as R. For w=D_u^1/2D_v^1/21
which is both the left and right eigenvector of A for eigenvalue
1, the detailed balance condition translates to D_wAD_w=D_wA^TD_w,
which implies A=A^T, which further implies that all eigenvalues
of A (and R) are real. We can thus state Cheeger inequalities
for nonnegative matrices satisfying detailed balance. 

(Cheeger's inequalities
for nonnegative matrices satisfying detailed balance) Let R be
a nonnegative matrix with PF eigenvalue 1 and positive left and right
eigenvectors u and v (else ϕ(R)=0 by definition), and
let R satisfy the condition of detailed balance, i.e. D_uRD_v=D_vR^TD_u.
Then 

    1-λ_2(R)/2≤ϕ(R)≤√(2·(1-λ_2(R))).






§ CONSTRUCTION OF DOUBLY
STOCHASTIC MATRICES WITH SMALL EDGE EXPANSION AND LARGE SPECTRAL GAP


As discussed, it might have been tempting to think that Γ(n)
(see Definition <ref>) should be independent of the matrix
size n, since this holds for the symmetric case, and also for the
upper bound on ϕ for the general nonsymmetric doubly stochastic
case (Lemma <ref>). However, two known examples showed that
a mild dependence on n cannot be avoided.



 §.§ Known Constructions


Klawe-Vazirani construction: The first is a construction
of Klawe <cit.> – these families of d-regular
undirected graphs have edge expansion (log n)^-γ for various
0<γ<1. However, there is a natural way in which to direct
the edges of these graphs and obtain a (d/2)-in, (d/2)-out -regular
graph, and it was noted by U. Vazirani <cit.> in the
1980s that for this digraph A, which shares the same edge expansion
as Klawe's, all eigenvalues (except the stochastic eigenvalue) have
norm ≤1/2. Specifically, one construction is as follows: let
n be an odd prime, and create the graph on n vertices with in-degree
and out-degree 2 by connecting every vertex v∈ℤ/n to
two vertices, 1+v and 2v. Dividing the adjacency matrix of the
graph by 2 gives a doubly stochastic matrix A_KV. It is simple
to see (by transforming to the Fourier basis over ℤ/n)
that the characteristic polynomial of A_KV is x(x-1)((2x)^n-1-1)/(2x-1),
so apart from the trivial eigenvalue 1, A_KV has n-2 nontrivial
eigenvalues λ such that |λ|=1/2 and one
eigenvalue 0, and thus, λ_2(A_KV)≤1/2.
Further, upper bounding the edge expansion ϕ by the vertex expansion
bound (Theorem 2.1 in <cit.>), it follows that
for some constant c, 

    Γ(n)≤ϕ(A_KV)/1-λ_2(A_KV)≤ c·(loglog n/log n)^1/5.


de Bruijn construction: A second example is the
de Bruijn digraph <cit.>. This is if anything
even more striking: the doubly stochastic matrix (again representing
random walk along an Eulerian digraph) has edge expansion Θ(1/log n)
<cit.>, yet all the nontrivial eigenvalues
are 0. More specifically, define a special case of de Bruijn <cit.>
graphs as follows: Let n=2^k for some integer k, and create
the graph of degree 2 on n vertices by directing edges from each
vertex v=(v_1,v_2,…,v_k)∈{0,1}^k to two vertices,
(v_2,v_3,…,v_k,0) and (v_2,v_3,…,v_k,1).
Dividing the adjacency matrix of the graph by 2 gives a doubly stochastic
matrix A_dB. Since this random walk completely forgets its starting
point after k steps, every nontrivial eigenvalue of A_dB is
0 (and each of its Jordan blocks is of dimension at most k). Further,
it was shown in <cit.> that ϕ(A_dB)∈Θ(1/k),
and thus, 

    Γ(n)≤ϕ(A_dB)/1-λ_2(A_dB)≤1/k=1/log n.


Other literature – Feng-Li construction: We round
out this discussion by recalling that Alon and Boppana <cit.>
showed that for any infinite family of d-regular undirected graphs,
the adjacency matrices, normalized to be doubly stochastic and with
eigenvalues 1=λ_1≥λ_2≥…≥-1, have
λ_2≥2√(d-1)/d-o(1). Feng and Li <cit.>
showed that undirectedness is essential to this bound: they provide
a construction of cyclically-directed r-partite (r≥2) d-regular
digraphs (with n=kr vertices for k>d, (k,d)=1), whose
normalized adjacency matrices have (apart from r “trivial”
eigenvalues), only eigenvalues of norm ≤1/d. The construction
is of an affine-linear nature quite similar to the preceding two,
and to our knowledge does not give an upper bound on Γ any
stronger than those.



 §.§ A new construction


To achieve the upper bound in Theorem <ref>, we need a construction
that is exponentially better than known examples. We give an
explicit construction of n× n doubly stochastic matrices A_n
(for every n) that are highly nonexpanding, since they contain
sets with edge expansion less than 1/√(n), even though every
nontrivial eigenvalue is 0. The construction might seem nonintuitive,
but in Appendix <ref> we give
some explanation of how to arrive at it. 

Let m=√(n),


    a_n    =m^2+m-1m·(m+2),     b_n    =m+1m·(m+2),     c_n    =1m·(m+1),
    
    
    d_n    =m^3+2m^2+m+1m·(m+1)·(m+2),     e_n    =1m·(m+1)·(m+2),     f_n    =2m+3m·(m+1)·(m+2),


and define the n× n matrix


    A_n=[[ a_n b_n   0   0   0   0   0   ⋯   0;   0 c_n d_n e_n e_n e_n e_n   ⋯ e_n;   0 c_n e_n d_n e_n e_n e_n   ⋯ e_n;   0 c_n e_n e_n d_n e_n e_n   ⋯ e_n;   0 c_n e_n e_n e_n d_n e_n   ⋯ e_n;   0 c_n e_n e_n e_n e_n d_n   ⋯ e_n;   ⋮   ⋮   ⋮   ⋮   ⋮   ⋮   ⋮   ⋱   ⋮;   0 c_n e_n e_n e_n e_n e_n   … d_n; b_n f_n c_n c_n c_n c_n c_n   ⋯ c_n ]].

Then the following hold for A_n: 


  * A_n is doubly stochastic. 

  * Every nontrivial eigenvalue of A_n is 0. 

  * The edge expansion is bounded as 

    16√(n)≤ϕ(A_n)≤1√(n).


  * As a consequence of 1,2,3, 

    ϕ(A_n)≤1-λ_2(A_n)√(n)

and thus 

    Γ(n)≤1√(n).





The proof is given in Appendix <ref>. 

This completes the proof of the upper bound in Theorem <ref>.
We remark that for the matrices A_n constructed in Theorem <ref>,
it holds that 

    ϕ(A_n)≤1-|λ_i(A)|/√(n)

for any i≠1, giving a stronger guarantee than that required
for Theorem <ref>.

We also remark that it would be unlikely to arrive at such a construction
by algorithmic simulation, since the eigenvalues of the matrices A_n
are extremely sensitive. Although λ_2(A_n)=0, if we shift
only O(1/√(n)) of the mass in the matrix A_n to create
a matrix A'_n, by replacing a_n with a'_n=a_n+b_n,
b_n with b'_n=0, f_n with f'_n=f_n+b_n and
keeping c_n,d_n,e_n the same, then λ_2(A'_n)=1.
Thus, since perturbations of O(1/√(n)) (which is tiny for large
n) cause the second eigenvalue to jump from 0 to 1 (and the spectral
gap from 1 to 0), it would not be possible to make tiny changes to
random matrices to arrive at a construction satisfying the required
properties in Theorem <ref>.



§ LOWER BOUND ON THE EDGE EXPANSION
Φ IN TERMS OF THE SPECTRAL GAP


In this section, we prove the lower bound on ϕ in Theorem <ref>,
and the lower bound on ϕ in Theorem <ref> will follow
as a special case. The proof is a result of a sequence of lemmas that
we state next. The first lemma states that ϕ is sub-multiplicative
in the following sense. 

 Let R∈ℝ^n× n be a nonnegative
matrix with left and right eigenvectors u and v for the PF eigenvalue
1. Then 

    ϕ(R^k)≤ k·ϕ(R).




The proof is given in Appendix <ref>. 

For the case of symmetric doubly stochastic matrices R, Lemma <ref>
follows from a theorem of Blakley and Roy <cit.>. (It
does not fall into the framework of an extension of that result to
the nonsymmetric case <cit.>). Lemma <ref>
helps to lower bound ϕ(R) by taking powers of R, which is
useful since we can take sufficient powers in order to make the matrix
simple enough that its edge expansion is easily calculated. The next
two lemmas follow by technical calculations. 

 Let T∈ℂ^n× n be an
upper triangular matrix with T_2=σ and for every i,
|T_i,i|≤β. Then 

    T^k_2≤ n·σ^n·k+n  n·β^k-n.




The proof is given in Appendix <ref>. 

Using Lemma <ref>, we can show the following lemma
for the special case of upper triangular matrices with operator norm
at most 1. 

 Let T∈ℂ^n× n be an
upper triangular matrix with T_2≤1 and |T_i,i|≤α<1
for every i. Then T^k≤ϵ for 

    k≥4n+2ln(n/ϵ)1-α.




The proof is given in Appendix <ref>. 

Given lemmas <ref> and <ref>, we
can lower bound ϕ(R) in terms of 1-|λ_m(R)| (where
λ_m is the nontrivial eigenvalue that is maximum in magnitude).
Our aim is to lower bound ϕ(R) by ϕ(R^k), but since
the norm of R^k increases by powering, we cannot use the lemmas
directly, since we do not want a dependence on σ(R) in the
final bound. To handle this, we transform R to A, such that
ϕ(R)=ϕ(A), the eigenvalues of R and A are the same,
but σ(A)=A_2=1 irrespective of the norm of R. 

 Let R be a nonnegative matrix with positive
(left and right) eigenvectors u and v for the PF eigenvalue
1, normalized so that ⟨ u,v⟩=1. Define A=D_u^1/2D_v^-1/2RD_u^-1/2D_v^1/2.
Then the following hold for A: 


  * ϕ(A)=ϕ(R). 

  * For every i, λ_i(A)=λ_i(R). 

  * A_2=1. 




The proof is given in Appendix <ref>. 

Given Lemma <ref>, we lower bound ϕ(A) using
ϕ(A^k) in terms of 1-|λ_m(A)|, to obtain the corresponding
bounds for R. 

Let R be a nonnegative matrix with
positive (left and right) eigenvectors u and v for the PF eigenvalue
1, normalized so that ⟨ u,v⟩=1. Let λ_m
be the nontrivial eigenvalue of R that is maximum in magnitude
and let κ=min_iu_i· v_i. Then 

    1/20·1-|λ_m|/n+ln(1κ)≤ϕ(R).




The proof is given in Appendix <ref>. 

Given Lemma <ref>, we use the trick of lazy
random walks to get a bound on 1-λ_2(R) from a bound
on 1-|λ_m(R)|.

 Let R be a nonnegative matrix with
positive (left and right) eigenvectors u and v for the PF eigenvalue
1, normalized so that ⟨ u,v⟩=1. Let κ=min_iu_i· v_i.
Then 

    1/30·1-λ_2(R)n+ln(1/κ)≤ϕ(R).

For any doubly stochastic matrix A, 

    1-λ_2(A)35· n≤ϕ(A),

and thus 

    135· n≤Γ(n).




The proof is given in Appendix <ref>. 

This completes the proof of the lower bound on ϕ in Theorem
<ref>, and the upper bound on ϕ in Theorem
<ref> is shown in Appendix <ref>.
Combined with Theorem <ref>, this also completes
the proof of Theorem <ref>.



§ MIXING TIME


We now study the mixing time of nonnegative matrices, and relate it
to all the quantities we have studied so far. To motivate the definition
of mixing time for general nonnegative matrices, we first consider
the mixing time of doubly stochastic matrices. The mixing time of
a doubly stochastic matrix A (i.e., of the underlying Markov chain)
is the worst-case number of steps required for a random walk starting
at any vertex to reach a distribution approximately uniform over the
vertices. To avoid complications of periodic chains, we assume that
A is 1/2-lazy, meaning that for every i, A_i,i≥1/2.
Given any doubly stochastic matrix A, it can be easily converted
to the lazy random walk 1/2I+1/2A. This is still
doubly stochastic and in the conversion both ϕ(A) and the spectral
gap are halved. The mixing time will be finite provided only that
the chain is connected. Consider the indicator vector 1_{i}
for any vertex i. We want to find the smallest τ such that
A^τ1_{i}≈1/n1 or A^τ1_{i}-1/n1≈0,
which can further be written as (A^τ-1/n1·1^T)1_{i}≈0.
Concretely, for any ϵ, we want to find τ=τ_ϵ(A)
such that for any i, 

    ‖(A^τ-1/n1·1^T)1_{i}‖ _1≤ϵ.

Given such a value of τ, for any vector x such that x_1=1,
we get 

    ‖(A^τ-1/n1·1^T)x‖ _1=‖∑ _i(A^τ-1/n1·1^T)x_i1_{i}‖ _1≤∑ _i|x_i|‖(A^τ-1/n1·1^T)1_{i}‖ _1≤∑ _i|x_i|·ϵ=ϵ.

Thus, the mixing time τ_ϵ(A) is the number τ
for which ‖ (A^τ-J)· x‖ _1≤ϵ
for any x such that x_1=1.

We want to extend this definition to any nonnegative matrix R with
PF eigenvalue 1 and corresponding positive left and right eigenvectors
u and v. Note that if R is reducible (i.e., ϕ(R)=0),
then the mixing time is infinite. Further, if R is periodic, then
mixing time is again ill-defined. Thus, we again assume that R
is irreducible and 1/2-lazy, i.e. R_i,i≥1/2
for every i. Let x be any nonnegative vector for the sake of
exposition, although our final definition will not require nonnegativity
and will hold for any x. We want to find τ such that R^τx
about the same as the component of x along the direction of v.
Further, since we are right-multiplying and want convergence to the
right eigenvector v, we will define the ℓ_1-norm using
the left eigenvector u. Thus, for the starting vector x, instead
of requiring x_1=1 as in the doubly stochastic case, we will
require D_ux_1=1. Since x is nonnegative, D_ux_1=⟨ u,x⟩=1.
Thus, we want to find τ such that R^τx≈ v, or
(R^τ-v· u^T)x≈0. Since we measured
the norm of the starting vector x with respect to u, we will
also measure the norm of the final vector (R^τ-v· u^T)x
with respect to u. Thus we arrive at the following definition. 

(Mixing time of general nonnegative matrices
R) Let R be a 1/2-lazy, irreducible nonnegative matrix
with PF eigenvalue 1 with u and v as the corresponding positive
left and right eigenvectors, where u and v are normalized so
that ⟨ u,v⟩=D_uv_1=1. Then the mixing time
τ_ϵ(R) is the smallest number τ such that ‖ D_u(R^τ-v· u^T)x‖ _1≤ϵ
for every vector x with D_ux_1=1. 


We remark that similar to the doubly stochastic case, using the triangle
inequality, it is sufficient to find mixing time of standard basis
vectors 1_{i}. Let y_i=1_{i}/D_u1_{i}_1,
then y_i is nonnegative, D_uy_i_1=⟨ u,y_i⟩=1,
then for any x, such that D_ux_1=1, we can write 

    x=∑ _ic_i1_{i}=∑_ic_iD_u1_{i}_1y_i

with 

    D_ux_1=‖ D_u∑ _ic_i1_{i}‖ _1=∑ _i|c_i|D_u1_{i}_1=1.

Thus, if for every i, ‖ D_u(R^τ-v· u^T)y_i‖ _1≤ϵ,
then 

    ‖ D_u(R^τ-v· u^T)x‖ _1=‖ D_u(R^τ-v· u^T)∑ _ic_iD_u1_{i}_1y_i‖ _1≤∑ _ic_iD_u1_{i}_1‖ D_u(R^τ-v· u^T)y_i‖ _1≤ϵ.

Thus, it is sufficient to find mixing time for every nonnegative x
with D_ux_1=⟨ u,x⟩=1, and it will hold for
all x.

For the case of reversible nonnegative matrices M with PF
eigenvalue 1, the mixing time is well-understood, and it is easily
shown that 

    τ_ϵ(M)≤ln(n/κ·ϵ)1-λ_2(M)(Theorem <ref>)≤2·ln(n/κ·ϵ)ϕ^2(M).

We will give corresponding bounds for the mixing time of general nonnegative
matrices.



 §.§ Mixing time and singular values


We first show a simple lemma relating the mixing time of nonnegative
matrices to the second singular value. This lemma is powerful enough
to recover the bounds obtained by Fill <cit.>
and Mihail <cit.> in an elementary way. Since
the largest singular value of any general nonnegative matrix R
with PF eigenvalue 1 could be much larger than 1, the relation between
mixing time and second singular value makes sense only for nonnegative
matrices with the same left and right eigenvector for eigenvalue 1,
which have largest singular value 1 by Lemma <ref>. 

 (Mixing time and second singular value)
Let A be a nonnegative matrix (not necessarily lazy) with PF eigenvalue
1, such that Aw=w and A^Tw=w for some w with ⟨ w,w⟩=1,
and let κ=min_iw_i^2. Then for every c>0, 

    τ_ϵ(A) ≤ c·ln(√(n)/√(κ)·ϵ)1-σ_2^c(A) ≤ c·ln(n/κ·ϵ)1-σ_2^c(A).




The proof is given in Appendix <ref>. 

For the case of c=2, Lemma <ref> was obtained
by Fill <cit.>, but we find our proof simpler.



 §.§ Mixing time and edge expansion


We now relate the mixing time of general nonnegative matrices R
to its edge expansion ϕ(R). The upper bound for row stochastic
matrices R in terms of ϕ(R) were obtained by Mihail <cit.>
and simplified by Fill <cit.> using Lemma <ref>
for c=2. Thus, the following lemma is not new, but we prove it
in Appendix <ref> for completeness, since
our proof is simpler and holds for any nonnegative matrix R. 

(Mixing time and edge expansion) Let τ_ϵ(R)
be the mixing time of a 1/2-lazy nonnegative matrix R
with PF eigenvalue 1 and corresponding positive left and right eigenvectors
u and v, and let κ=min_iu_i· v_i. Then 

    1/2-ϵ/ϕ(R) ≤ τ_ϵ(R)    ≤ 4·ln(n/κ·ϵ)ϕ^2(R).




The proof is given in Appendix <ref>. 




 §.§ Mixing time and spectral gap


We obtain bounds for the mixing time of nonnegative matrices in terms
of the spectral gap, using methods similar to the ones used to obtain
the upper bound on ϕ in Theorem <ref>. 

 (Mixing time and spectral gap) Let τ_ϵ(R)
be the mixing time of a 1/2-lazy nonnegative matrix R
with PF eigenvalue 1 and corresponding positive left and right eigenvectors
u and v, and let κ=min_iu_i· v_i. Then 

    1/2-ϵ/√(2·(1-λ_2(R))) ≤ τ_ϵ(R)    ≤ 20·n+ln(1κ·ϵ)/1-λ_2(R).




The proof is given in Appendix <ref> 

We remark that there is only additive and not multiplicative
dependence on ln(n/κ·ϵ). Further,
our construction for the upper bound in Theorem <ref> also
shows that the upper bound on τ using λ_2 in Lemma
<ref> is also (almost) tight. For the construction
of A_n in Theorem <ref>, letting the columns of U_n
be u_1,…,u_n, for x=u_2, (A_n^k-J)u_2=(1-(2+√(n))^-1)^ku_3,
and so for k=O(√(n)), the triangular block of A^O(√(n))
has norm about 1/e, which further becomes less than ϵ
after about ln(n/ϵ) powers. Thus for
the matrices A_n, τ_ϵ(A_n)∈ O(√(n)·ln(n/ϵ)).
This shows Lemma <ref> is also (almost) tight since
λ_2(A_n)=0.



 §.§ Mixing time of a nonnegative matrix and its additive symmetrization


We can also bound the mixing time of a nonnegative matrix A with
the same left and right eigenvector w for PF eigenvalue 1, with
the mixing time of its additive symmetrization M=1/2(A+A^T).
Note that we obtained a similar bound on the spectral gaps of A
and M in Lemma <ref>. Since ϕ(A)=ϕ(M),
we can bound τ_ϵ(A) and τ_ϵ(M) using
the two sided bounds between edge expansion and mixing time in Lemma
<ref>. For the lower bound, we get γ_1·√(τ_ϵ(M))≤τ_ϵ(A),
and for the upper bound, we get 

    τ_ϵ(A)≤γ_2·τ_ϵ^2(M),

where γ_1 and γ_2 are some functions polylogarithmic
in n,κ,1/ϵ. However, by bounding the appropriate
operator, we can show a tighter upper bound on τ_ϵ(A),
with only a linear instead of quadratic dependence on τ_ϵ(M). 

Let A be a 1/2-lazy nonnegative
matrix with positive left and right eigenvector w for PF eigenvalue
1, let M=1/2(A+A^T), and κ=min_iw_i^2.
Then 

    1-2ϵ/4·ln^1/2(n/κ·ϵ)·τ_ϵ^1/2(M) ≤ τ_ϵ(A) ≤ 2·ln(n/κ·ϵ)/ln(1/ϵ)·τ_ϵ(M).




The proof is given in Appendix <ref>. 

One example application of Lemma <ref> is the following:
given any undirected graph G such that each vertex has degree d,
any manner of orienting the edges of G to obtain a graph
in which every vertex has in-degree and out-degree d/2 cannot increase
the mixing time of a random walk (up to a factor of ln(n/κ·ϵ)).



 §.§ Mixing time of the continuous operator


Let R be a nonnegative matrix with PF eigenvalue 1 and associated
positive left and right eigenvectors u and v. The continuous
time operator associated with R is defined as exp(t·(R-I)),
where for any matrix M, we formally define exp(M)=∑_i=01/i!M^i.
The reason this operator is considered continuous, is that starting
with any vector x_0, the vector x_t at time t∈ℝ_≥0
is defined as x_t=exp(t·(R-I))x_0.
Since 

    exp(t·(R-I))=exp(t· R)·exp(-t· I)=e^-t∑_i=0^∞1/i!t^iR^i

where we split the operator into two terms since R and I commute,
it follows that exp(t·(R-I)) is nonnegative,
and if λ is any eigenvalue of R for eigenvector y,
then e^t(λ-1) is an eigenvalue of exp(t·(R-I))
for the same eigenvector y. Thus, it further follows that u
and v are the left and right eigenvectors for exp(t·(R-I))
with PF eigenvalue 1. The mixing time of exp(t·(R-I)),
is the value of t for which 

    ‖ D_u(exp(t·(R-I))-v· u^T)v_0‖ _1≤ϵ

for every v_0 such that D_uv_0_1=1, and thus, it
is exactly same as considering the mixing time of exp(R-I) in
the sense of Definition <ref>. 

Let R be a nonnegative matrix (not necessarily
lazy) with positive left and right eigenvectors u and v for
PF eigenvalue 1, normalized so that ⟨ u,v⟩=1 and let
κ=min_iu_i· v_i. Then the mixing time of exp(t·(R-I)),
or τ_ϵ(exp(R-I)) is bounded as 

    1/2-ϵ/ϕ(R) ≤ τ_ϵ(exp(R-I)) ≤ 100·ln(n/κ·ϵ)/ϕ^2(R).




The proof is given in Appendix <ref>. 




 §.§ Bounds using the canonical paths method


For the case of symmetric nonnegative matrices M with PF eigenvalue
1, as stated earlier in this section in equation <ref>,
since τ varies inversely with 1-λ_2 (up to a loss
of a factor of ln(n/κ·ϵ)), it follows
that any lower bound on the spectral gap can be used to upper bound
τ_ϵ(M). Further, since 1-λ_2 can be written
as a minimization problem for symmetric matrices (see Section <ref>),
any relaxation of the optimization problem can be used to obtain a
lower bound on 1-λ_2, and inequalities obtained thus are
referred to as Poincare inequalities. One such method is to
use canonical paths <cit.> in the underlying
weighted graph, which helps to bound mixing time in certain cases
in which computing λ_2 or ϕ is infeasible. However,
since it is possible to define canonical paths in many different ways,
it leads to multiple relaxations to bound 1-λ_2, each useful
in a different context. We remark one particular definition and lemma
here, since it is relevant to our construction in Theorem <ref>,
after suitably modifying it for the doubly stochastic case. 

<cit.> Let M represent
a symmetric doubly stochastic matrix. Let W be a set of paths in
M, one between every pair of vertices. For any path γ_u,v∈ S
between vertices (u,v) where γ_u,v is simply a set of
edges between u and v, let the number of edges or the (unweighted)
length of the path be |γ_u,v|. Let 

    ρ_W(M)=max_e=(x,y)∑ _(u,v):e∈γ_u,v|γ_u,v|n· M_x,y.

Then for any W, 

    1-λ_2(M)≥1/ρ_W(M)

and thus, 

    τ_ϵ(M)≤ρ_W(M)·ln(n/ϵ).




Combining Lemma <ref>
and Lemma <ref>, it follows that for any doubly
stochastic matrix A, and any set W of paths in the underlying
graph of AA^T, 

    τ_ϵ(A)≤2·ln(n/ϵ)1-σ_2^2(A)=2·ln(n/ϵ)1-λ_2(AA^T)≤2·ρ_W(AA^T)·ln(n/ϵ).



Consider the example A_n in Theorem <ref>. It
is not difficult to see that 

    τ_ϵ(A_n)∈ O(√(n)·ln(n/ϵ)).

This follows since the factor of √(n) ensures that the only
non zero entries in the triangular matrix T_n (see Appendix <ref>)
in the Schur form of A^⌈√(n)⌉ are about e^-1,
and the factor of ln(n/ϵ) further converts
these entries to have magnitude at most ϵ/n in A^τ.
Thus, the operator norm becomes about ϵ/n, and the
ℓ_1 norm gets upper bounded by ϵ. However, from
Theorem <ref>, since ϕ(A_n)≥1/6√(n),
it follows from Lemma <ref> that τ_ϵ(A_n)∈ O(n·ln(n/ϵ)),
about a quadratic factor off from the actual upper bound in equation
<ref>. Further, from Theorem <ref>,
the second eigenvalue of A_n is 0, and even employing Lemma
<ref> leads to a quadratic factor loss from the
actual bound. However, Lemma <ref> and Corollary
<ref> do give correct bounds. Since σ_2(A_n)=1-1/√(n)+2
from Theorem <ref> (see the proof in Appendix <ref>),
it follows from Lemma <ref> for c=1 that τ_ϵ(A_n)∈ O(√(n)·ln(n/ϵ)),
matching the bound in equation <ref>. Now to see the
bound given by canonical paths and corollary <ref>,
consider the matrix M=A_nA_n^T. Every entry of M turns
out to be positive, and the set W is thus chosen so that the path
between any pair of vertices is simply the edge between the vertices.
Further for r_n,α_n,β_n defined in the proof (Appendix
<ref>) of Theorem <ref>,
M=J+r_n^2B, where 

    B_1,1=n-2/n,  B_n,n=(n-2)·β_n^2,  B_i,i=α_n^2+(n-3)·β_n^2,  B_1,n=B_n,1=n-2/√(n)·β_n,


    B_n,j=B_j,n=α_n·β_n+(n-3)·β_n^2,  B_1,j=B_j,1=1/√(n)·(α_n+(n-3)·β_n),  B_i,j=2·α_n·β_n+(n-4)·β_n^2,

and 2≤ i,j≤ n-1. It follows that any entry of the matrix
M is at least c· n^-3/2 (for some constant c),
and from Corollary <ref>, we get that τ_ϵ(A_n)∈ O(√(n)·ln(n/ϵ)),
matching the bound in equation <ref>.



§ ACKNOWLEDGEMENTS


We thank Shanghua Teng, Ori Parzanchevski and Umesh Vazirani for illuminating
conversations. JCM would like to thank Luca Trevisan for his course
“Graph Partitioning and Expanders” on VentureLabs, which got the
author interested in Spectral Graph Theory. Research was supported
by NSF grants 1319745, 
1553477, 
1618795, and 1909972; 
BSF grant 2012333; and, during a residency of LJS at the Israel Institute
for Advanced Studies, by a EURIAS Senior Fellowship co-funded by the
Marie Skłodowska-Curie Actions under the 7th Framework Programme.



 alpha








§ PROOF OF LEMMA <REF>


Let w be the left and right eigenvector of A for eigenvalue
1. Then note from part (3) of Lemma <ref>, we have
that A_2=1. We first note that since the left and right eigenvectors
for eigenvalue 1 are the same, 

    max_v⊥ wAv_2/v_2≤σ_2(A).


To see this, let W be a unitary matrix with first column w,
then since Aw=w and A^*w=A^Tw=w, W^*AW has two blocks,
a 1×1 block containing the entry 1, and an n-1× n-1
block, and let the second block's singular value decomposition be
PDQ with n-1× n-1 unitaries P and Q and diagonal
D. Then 

    A=W[ 1 0; 0 P ][ 1 0; 0 D ][ 1 0; 0 Q ]W^*,

giving a singular value decomposition for A. Thus, for any v⊥ w
with v_2=1, W^*v has 0 as the first entry, and thus

    Av_2≤W_2P_2D_2Q_2W^*_2v_2=D_2=σ_2(A).


Thus we have, 

    ϕ(A)=min_S:∑_i∈ Sw_i^2≤1/2⟨1_S,D_wAD_w(1-1_S)⟩/⟨1_s,D_w^21⟩=1-max_S:∑_i∈ Sw_i^2≤1/2⟨1_S,D_wAD_w1_S⟩/⟨1_s,D_w^21⟩

where the second equality used the fact that AD_w1=Aw=w=D_w1.
Let D_w1_S=c· w+v, where ⟨ w,v⟩=0.
Then 

    c=⟨ w,D_w1_S⟩=⟨1_s,D_w^21⟩=∑_i∈ Sw_i^2

and 

    v_2^2    =⟨ v,D_w1_S-c· w⟩
        =⟨ v,D_w1_S⟩
        =⟨ D_w1_S-c· w,D_w1_S⟩
        =⟨ D_w1_S,D_w1_S⟩-c·⟨ D_w1_S,w⟩
        =c·(1-c).

Thus, 

    max_S:∑_i∈ Sw_i^2≤1/2⟨1_S,D_wAD_w1_S⟩/⟨1_s,D_w^21⟩    =⟨ c· w+v,A(c· w+v)⟩/c
           [since  is diagonal and so ]
        =c^2+⟨ v,Av⟩/c
           [since  and ]
       ≤c^2+v_2Av_2/c
       ≤c^2+v_2σ_2(A)v_2/c
           [from equation <ref> since ]
        =c+σ_2(A)·(1-c)
           [using equation <ref>]
        =σ_2(A)+(1-σ_2(A))· c
       ≤1+σ_2(A)/2
           [since ]

which completes the proof after replacing the above upper bound in
equation <ref>.

A simple extension (and alternate proof) is the following. Let H=AA^T,
then H is a nonnegative matrix that has w as the left and right
eigenvector for eigenvalue 1. For any integer k, we know that H^k
is nonnegative, and since λ_2(H)=σ_2^2(A), we
get 

    1-σ_2^2· k(A)/2=1-λ_2^k(H)/2≤ϕ(H^k)≤ k·ϕ(H)≤ k·(2·ϕ(A))

where the first inequality used Cheeger's inequality (Theorem <ref>)
and the second and third inequalities were obtained by <ref>
and its proof in Appendix <ref>. Thus, we
get that for any integer c≥2, 

    1-σ_2^c(A)/2· c≤ϕ(A).





§ PROOF OF THE MAIN CONSTRUCTION
IN THEOREM <REF>


The following calculations are easy to check, to see that A_n
is a doubly stochastic matrix: 


  * a_n≥0, b_n≥0, c_n≥0, d_n≥0, e_n≥0,
f_n≥0. 

  * a_n+b_n=1. 

  * c_n+d_n+(n-3)e_n=1. 

  * b_n+f_n+(n-2)c_n=1. 

This completes the proof of (1).

A_n is triangularized as T_n by the unitary U_n, i.e.

    A_n=U_nT_nU_n^*,

with T_n and U_n defined as follows. Recall that m=√(n).
Let 

    r_n=1-1m+2,



    α_n    =-n^2+2n-√(n)n·(n-1)=-1+1/m·(m+1),


    β_n    =n-√(n)n·(n-1)=1/m·(m+1),


    T_n=[   1   0   0   0   0   0   0   0   0;   0   0 r_n   0   0   0   0   ⋯   0;   0   0   0 r_n   0   0   0   ⋯   0;   0   0   0   0 r_n   0   0   ⋯   0;   0   0   0   0   0 r_n   0   ⋯   0;   0   0   0   0   0   0 r_n   ⋯   0;   ⋮   ⋮   ⋮   ⋮   ⋮   ⋮   ⋱   ⋱   ⋮;   0   0   0   0   0   0   ⋯   0 r_n;   0   0   0   0   0   0   0   0   0 ],

and 

    U_n=[ 1/√(n) 1/√(n) 1/√(n) 1/√(n) 1/√(n) 1/√(n)      ⋯ 1/√(n) 1/√(n); 1/√(n)    α_n    β_n    β_n    β_n    β_n      ⋯    β_n    β_n; 1/√(n)    β_n    α_n    β_n    β_n    β_n      ⋯    β_n    β_n; 1/√(n)    β_n    β_n    α_n    β_n    β_n      ⋯    β_n    β_n; 1/√(n)    β_n    β_n    β_n    α_n    β_n      ⋯    β_n    β_n; 1/√(n)    β_n    β_n    β_n    β_n    α_n      ⋯    β_n    β_n;      ⋮      ⋮      ⋮      ⋮      ⋮      ⋮      ⋱      ⋮      ⋮; 1/√(n)    β_n    β_n    β_n    β_n    β_n      ⋯    α_n    β_n; 1/√(n)    β_n    β_n    β_n    β_n    β_n      ⋯    β_n    α_n ].

To show that U_n is a unitary, the following calculations can
be easily checked: 


  * 1/n+α_n^2+(n-2)·β_n^2=1. 

  * 1/√(n)+α_n+(n-2)·β_n=0. 

  * 1/n+2·α_n·β_n+(n-3)·β_n^2=0. 

Also, to see that A_n=U_nT_nU_n^*, the following calculations
are again easy to check: 


  * 
    A_n(1,1)=a_n=⟨ u_1,Tu_1⟩=1/n+1/n·(n-2)· r_n.


  * 
    A_n(1,2)=b_n=⟨ u_1,Tu_2⟩=1/n+1/√(n)·(n-2)· r_n·β_n.


  * 
    A_n(n,1)=b_n=⟨ u_n,Tu_1⟩=1/n+1/√(n)·(n-2)· r_n·β_n.


  * For 3≤ j≤ n, 

    A_n(1,j)=0=⟨ u_1,Tu_j⟩=1/n+1/√(n)·α_n· r_n+(n-3)·1/√(n)·β_n· r_n.


  * For 2≤ i≤ n-1, 

    A_n(i,1)=0=⟨ u_i,Tu_1⟩=1/n+1/√(n)·α_n· r_n+1/√(n)·(n-3)·β_n· r_n.


  * For 2≤ i≤ n-1, 

    A_n(i,2)=c_n=⟨ u_i,Tu_2⟩=1/n+α_n·β_n· r_n+(n-3)·β_n^2· r_n.


  * For 3≤ j≤ n, 

    A_n(n,j)=c_n=⟨ u_n,Tu_j⟩=1/n+α_n·β_n· r_n+(n-3)·β_n^2· r_n.


  * For 2≤ i≤ n-1, 

    A_n(i,i+1)=d_n=⟨ u_i,Tu_i+1⟩=1/n+α_n^2· r_n+(n-3)·β_n^2· r_n.


  * For 2≤ i≤ n-2, 3≤ j≤ n, i+1≠j, 

    A_n(i,j)=e_n=⟨ u_i,Tu_j⟩=1/n+2·α_n·β_n· r_n+(n-4)·β_n^2· r_n.


  * 
    A_n(n,2)=f_n=⟨ u_n,Tu_2⟩=1/n+(n-2)· r_n·β_n^2.


We thus get a Schur decomposition for A_n, and since the diagonal
of T_n contains only zeros except the trivial eigenvalue 1, we
get that all nontrivial eigenvalues of A_n are zero. This completes
the proof of (2).

If we let the set S={1}, then we get that 

    ϕ(A_n)≤ϕ_S(A_n)=b_n<1/√(n).

Further, since T_n can be written as Π_nD_n, where D_n(1,1)=1,
D_n(i,i)=r_n for i=2 to n-1, and D_n(n,n)=0 for
some permutation Π_n, we get that A_n=(U_nΠ_n)D_nU_n^*
which gives a singular value decomposition for A_n since U_nΠ_n
and U_n^* are unitaries. Thus, A_n has exactly one singular
value that is 1, n-2 singular values that are r_n, and one
singular value that is 0. Thus, from Lemma <ref>,
we get that 

    ϕ(A)≥1-r_n/2=1/2·(√(n)+2)≥1/6√(n)

and this completes the proof of (3). 




§ PROOF OF THE UPPER BOUND ON Φ
IN THEOREM <REF>


Let R be the nonnegative matrix as described, and let u and
v be the eigenvectors corresponding to the eigenvalue λ_1=1.
Let κ=min_iu_i· v_i. If κ=0, ϕ(R)=0
by Definition <ref> and the upper bound on
ϕ(R) in the lemma trivially holds. If κ>0, then both
u and v are positive, and we normalize them so that ⟨ u,v⟩=1,
and define 

    A=D_u^1/2D_v^-1/2RD_u^-1/2D_v^1/2

and 

    w=D_u^1/2D_v^1/21,

where we use positive square roots for the entries in the diagonal
matrices. Further, from Lemma <ref>, the edge expansion
and eigenvalues of R and A are the same, and A_2=1.
We will show the bound for A and the bound for R will follow.
Since A has w as both the left and right eigenvector for eigenvalue
1, so does M=A+A^T/2.

As explained before Definition <ref> for edge
expansion of general nonnegative matrices, D_wAD_w is Eulerian,
since D_wAD_w1=D_wAw=D_ww=D_w^21=D_ww=D_wA^Tw=D_wA^TD_w1.
Thus, for any S, 

    ⟨1_S,D_wAD_w1_S⟩=⟨1_S,D_wAD_w1_S⟩=⟨1_S,D_wA^TD_w1_S⟩,

and thus for any set S for which ∑_i∈ Sw_i^2≤1/2,

    ϕ_S(A)=⟨1_S,D_wAD_w1_S⟩/⟨1_S,D_wAD_w1⟩=1/2·⟨1_S,D_wAD_w1_S⟩+⟨1_S,D_wA^TD_w1_S⟩/⟨1_S,D_wAD_w1⟩=ϕ_S(M)

and thus 

    ϕ(A)=ϕ(M).

For any matrix H, let 

    R_H(x)=⟨ x,Hx⟩/⟨ x,x⟩.

For every x∈ℂ^n, 

    ReR_A(x)=R_M(x),

since A and ⟨ x,x⟩ are nonnegative and we can write

    R_M(x)     =1/2⟨ x,Ax⟩/⟨ x,x⟩+1/2⟨ x,A^*x⟩/⟨ x,x⟩=1/2⟨ x,Ax⟩/⟨ x,x⟩+1/2⟨ Ax,x⟩/⟨ x,x⟩=1/2⟨ x,Ax⟩/⟨ x,x⟩+1/2⟨ x,Ax⟩^*/⟨ x,x⟩=ReR_A(x).

Also, 

    Reλ_2(A)≤λ_2(M).

To see this, first note that if λ_2(A)=1, since there exists
some positive u and v for PF eigenvalue 1, then from Lemma <ref>,
the underlying graph of A has multiply strongly connected components
each with eigenvalue 1, and so does M, and thus λ_2(M)=1.
If λ_2(A)≠1, then let v be the eigenvector corresponding
to λ_2(A). Then since Aw=w, we have that 

    Av=λ_2(A)v⇒⟨ w,Av⟩=⟨ w,λ_2(A)v⟩⇔⟨ A^Tw,v⟩=λ_2(A)⟨ w,v⟩⇔(1-λ_2(A))⟨ w,v⟩=0

which implies that v⊥ w. Thus, we have that 

    Reλ_2(A)=Re⟨ v,Av⟩/⟨ v,v⟩=⟨ v,Mv⟩/⟨ v,v⟩≤max_u⊥ w⟨ u,Mu⟩/⟨ u,u⟩=λ_2(M)

where the second equality uses equation <ref>, and the last
equality follows from the variational characterization of eigenvalues
stated in the Preliminaries (Appendix <ref>). Thus,
using equation <ref>, equation <ref> and Cheeger's
inequality for M (Theorem <ref>),
we get 

    ϕ(A)=ϕ(M)≤√(2·(1-λ_2(M)))≤√(2·(1-Reλ_2(A)))

as required. 




§ PROOFS FOR THE LOWER BOUND ON Φ IN THEOREM <REF>




 §.§ Proof of Lemma <ref>


For any cut S and non negative R as defined, let G_R=D_uRD_v,
and note that G_R is Eulerian, since G_R1=G_R^T1.
Let 

    γ_S(R)     =⟨1_S,G_R1_S⟩+⟨1_S,G_R1_S⟩
        =⟨1_S,D_uRD_v1_S⟩+⟨1_S,D_uRD_v1_S⟩

for any matrix R with left and right eigenvectors u and v.
We will show that if R and B are non negative matrices that
have the same left and right eigenvectors u and v for eigenvalue
1, then for every cut S, 

    γ_S(RB)≤γ_S(R+B)=γ_S(R)+γ_S(B).


Fix any cut S. Assume R=[[ P Q; H V ]] and B=[[ X Y; Z W ]] naturally divided based on cut S. For any vector u, let D_u
be the diagonal matrix with u on the diagonal. Since Rv=v,R^Tu=u,Bv=v,B^Tu=u,
we have


    P^TD_u_S1+H^TD_u_S1=D_u_S1,


    ZD_v_S1+WD_v_S1=D_v_S1,


    XD_v_S1+YD_v_S1=D_v_S1,


    Q^TD_u_S1+V^TD_u_S1=D_u_S1,

where u is divided into u_S and u_S and v
into v_S and v_S naturally based on the cut S.
Further, in the equations above and in what follows, the vector 1
is the all 1's vector with dimension either |S| or |S|
which should be clear from the context of the equations, and we avoid
using different vectors to keep the notation simpler. Then we have
from equation <ref>,


    γ_S(R)     =⟨1_S,D_uRD_v1_S⟩+⟨1_S,D_uRD_v1_S⟩
        =⟨1,D_u_SQD_v_S1⟩+⟨1,D_u_SHD_v_S1⟩

and similarly 

    γ_S(B)=⟨1,D_u_SYD_v_S1⟩+⟨1,D_u_SZD_v_S1⟩.

The matrix RB also has u and v as the left and right eigenvectors
for eigenvalue 1 respectively, and thus,


    γ_S(RB)     =⟨1,D_u_SPYD_v_S1⟩+⟨1,D_u_SQWD_v_S1⟩+⟨1,D_u_SHXD_v_S1⟩+⟨1,D_u_SVZD_v_S1⟩
        =⟨ P^TD_u_S1,YD_v_S1⟩+⟨1,D_u_SQWD_v_S1⟩+⟨1,D_u_SHXD_v_S1⟩+⟨ V^TD_u_S1,ZD_v_S1⟩
        =⟨ D_u_S1-H^TD_u_S1,YD_v_S1⟩+⟨1,D_u_SQ(D_v_S1-ZD_v_S1)⟩
            +⟨1,D_u_SH(D_v_S1-YD_v_S1⟩+⟨ D_u_S1-Q^TD_u_S1,ZD_v_S1⟩
                             [from equations <ref>, <ref>, <ref>, <ref> above]
        =⟨ D_u_S1,YD_v_S1⟩+⟨1,D_u_SQD_v_S1⟩-⟨ H^TD_u_S1,YD_v_S1⟩-⟨1,D_u_SQZD_v_S1⟩
            +⟨1,D_u_SHD_v_S1⟩+⟨ D_u_S1,ZD_v_S1⟩-⟨1,D_u_SHYD_v_S1⟩-⟨ Q^TD_u_S1,ZD_v_S1⟩
       ≤⟨ D_u_S1,YD_v_S1⟩+⟨1,D_u_SQD_v_S1⟩+⟨1,D_u_SHD_v_S1⟩+⟨ D_u_S1,ZD_v_S1⟩
                             [since every entry of the matrices is nonnegative, and thus each of the terms above]
        =γ_S(R)+γ_S(B)

Thus, noting that R^k has u and v as left and right eigenvectors
for any k, we inductively get using inequality <ref>
that 

    γ_S(R^k)≤γ_S(R)+γ_S(R^k-1)≤γ_S(R)+(k-1)·γ_S(R)=k·γ_S(R).

Note that for any fixed set S, the denominator in the definition
of ϕ_S(R) is independent of the matrix R and depends only
on the set S, and since the numerator is exactly γ_S(R)/2,
i.e. 

    ϕ_S(R)=γ_S(R)/2·∑_i∈ Su_i· v_i

we get by letting S be the set that minimizes ϕ(R), that

    ϕ(R^k)≤ k·ϕ(R).





 §.§ Proof of Lemma <ref>


Let g_r(k) denote the maximum of the absolute value of entries
at distance r from the diagonal in T^k, where the diagonal
is at distance 0 from the diagonal, the off-diagonal is at distance
1 from the diagonal and so on. More formally, 

    g_r(k)=max_i|T^k(i,i+r)|.


We will inductively show that for α≤1, and r≥1, 

    g_r(k)≤k+r  r·α^k-r·σ^r,

where σ=T_2. First note that for r=0, since T
is upper triangular, the diagonal of T^k is α^k, and
thus the hypothesis holds for r=0 and all k≥1. Further, for
k=1, if r=0, then g_0(1)≤α and if r≥1, then
g_r(1)≤T_2≤σ and the inductive hypothesis holds
also in this case, since r≥ k and α^k-r≥1. For
the inductive step, assume that for all r≥1 and all j≤ k-1,
g_r(j)≤j+r  r·α^j-r·σ^r. We
will show the calculation for g_r(k).

Since |a+b|≤|a|+|b|, 

    g_r(k)    ≤∑_i=0^rg_r-i(1)· g_i(k-1)
        =g_0(1)· g_r(k-1)+∑_i=0^r-1g_r-i(1)· g_i(k-1).

The first term can be written as, 

    g_0(1)· g_r(k-1)     =α·k-1+r  r·α^k-1-r·σ^r
               [using that  and the inductive hypothesis for the second term]
       ≤α^k-r·σ^r·k+r  r·k-1+r  rk+r  r
       ≤k/k+r·k+r  r·α^k-r·σ^r

and the second term as 

    g_r(k)    ≤∑_i=0^r-1g_r-i(1)· g_i(k-1)
       ≤σ·∑_i=0^r-1k-1+i  i·α^k-1-i·σ^i
            [using  and the inductive hypothesis for the second term]
       ≤σ^r·α^k-r·k+r  r·∑_i=0^r-1·k-1+i  ik+r  r·α^r-1-i
            [using  since  and ]
       ≤σ^r·α^k-r·k+r  r·∑_i=0^r-1·k-1+i  ik+r  r
            [using  and ]

We will now show that the quantity inside the summation is at most
r/k+r. Inductively, for r=1, the statement is true,
and assume that for any other r, 

    ∑_i=0^r-1k-1+i  i/k+r  r≤r/k+r.

Then we have 

    ∑_i=0^rk-1+i  i/k+r+1  r+1    =k+r  r/k+r+1  r+1·∑_i=0^r-1k-1+i  i/k+r  r+k-1+r  k-1/k+r+1  k
       ≤r+1/k+r+1·r/k+r+(r+1)· k/(k+r+1)·(k+r)
        =r+1/k+r+1

Thus we get that the second term is at most σ^r·α^k-r·k+r  r·r/k+r,
and combining it with the first term (equation <ref>),
it completes the inductive hypothesis. Noting that the operator norm
is at most the Frobenius norm, and since g_r(k) is increasing
in r and the maximum value of r is n, we get using equation
<ref>, 

    T^k_2   ≤√(∑_i,j|T^k(i,j)|^2)
       ≤ n·σ^n·α^k-n·k+n  n

as required. 




 §.§ Proof of Lemma <ref>


Let X=T^k_1, where k_1=c_1/1-α for α<1.
Then X_2≤T_2^k_1≤1, and for every i, 

    |X_i,i|≤|T_i,i|^k_1≤|λ_m|^c_1/(1-α)≤ e^-c_1.

Using Lemma <ref> for X with σ=1 and
β=e^-c_1, we get that for k_2=c_2· n, 

    X^k_2   ≤ n·k_2+n  n· e^-c_1(k_2-n)
       ≤ n· e^n·(c_2+1)^n· e^-c_1(c_2-1)n
              [using ]
        =exp(n·(ln n/n+ln(c_2+1)+1+c_1-c_1c_2))

and to have this quantity less than ϵ, we require 

    exp(n·(ln n/n+ln(c_2+1)+1+c_1-c_1c_2))≤ϵ
    ⇔   (1/ϵ)^1/n≤exp(-1·(ln n/n+ln(c_2+1)+1+c_1-c_1c_2))
    ⇔   1/nlnn/ϵ+1+c_1+ln(c_2+1)≤ c_1c_2

and we set 

    c_1=1+1/2.51·1/nln(n/ϵ)

and c_2=3.51 which always satisfies inequality <ref>.
As a consequence, for 

    k     =k_1· k_2
        =c_1· c_2· n/1-α
        =3.51· n+1.385·ln(n/ϵ)1-α

we get, 

    T^k_2≤X^k_2≤ϵ

as required. 




 §.§ Proof of Lemma <ref>


Let the matrix A be as defined, and let w=D_u^1/2D_v^1/21.
Then it is easily checked that Aw=w and A^Tw=w. Further, 

    ⟨ w,w⟩=⟨ D_u^1/2D_v^1/21,D_u^1/2D_v^1/21⟩=⟨ D_u1,D_v1⟩=⟨ u,v⟩=1

where we used the fact that the matrices D_u^1/2 and
D_v^1/2 are diagonal, and so they commute, and are
unchanged by taking transposes. Let S be any set. The condition
∑_i∈ Su_i· v_i≤1/2 translates to ∑_i∈ Sw_i^2≤1/2
since u_i· v_i=w_i^2. Thus, for any set S for which
∑_i∈ Su_i· v_i=∑_i∈ Sw_i^2≤1/2,

    ϕ_S(R)     =⟨1_S,D_uRD_v1_S⟩/⟨1_S,D_uD_v1_S⟩
        =⟨1_S,D_uD_u^-1/2D_v^1/2AD_u^1/2D_v^-1/2D_v1_S⟩/⟨1_S,D_u^1/2D_v^1/2D_u^1/2D_v^1/21_S⟩
        =⟨1_S,D_u^1/2D_v^1/2AD_u^1/2D_v^1/21_S⟩/⟨1_S,D_u^1/2D_v^1/2D_u^1/2D_v^1/21_S⟩
        =⟨1_S,D_wAD_w1_S⟩/⟨1_S,D_w^21_S⟩
        =ϕ_S(A)

and (1) holds. Further, since A is a similarity transform of R,
all eigenvalues are preserved and (2) holds. For (3), consider the
matrix H=A^TA. Since w is the positive left and right eigenvector
for A, i.e. Aw=w and A^Tw=w, we have Hw=w. But since
A was nonnegative, so is H, and since it has a positive eigenvector
w for eigenvalue 1, by Perron-Frobenius (Theorem <ref>,
part 2), H has PF eigenvalue 1. But λ_i(H)=σ_i^2(A),
where σ_i(A) is the i'th largest singular value of A.
Thus, we get σ_1^2(A)=λ_1(H)=1, and thus A_2=1. 




 §.§ Proof of Lemma <ref>


From the given R with positive left and right eigenvectors u
and v for eigenvalue 1 as stated, let A=D_u^1/2D_v^-1/2RD_u^-1/2D_v^1/2
and w=D_u^1/2D_v^1/21 as in Lemma
<ref>. Note that w is positive, and 

    ⟨ w,w⟩=⟨ D_u^1/2D_v^1/21,D_u^1/2D_v^1/21⟩=⟨ u,v⟩=1.

Further, Aw=w and A^Tw=w.

Let A=w· w^T+B. Since (w· w^T)^2=w· w^T
and Bw· w^T=w· w^TB=0, we get 

    A^k=w· w^T+B^k.

Let B=UTU^* be the Schur decomposition of B, where the diagonal
of T contains all but the stochastic eigenvalue of A, which
is replaced by 0, since w is both the left and right eigenvector
for eigenvalue 1 of A, and that space is removed in w· w^T.
Further, the maximum diagonal entry of T is at most |λ_m|
where λ_m is the nontrivial eigenvalue of A (or R)
that is maximum in magnitude. Note that if |λ_m|=1, then
the lemma is trivially true since ϕ(R)≥0, and thus assume
that |λ_m|<1. Since w· w^TB=Bw· w^T=0 and
A_2≤1 from Lemma <ref>, we have that B_2≤1.

Thus, using Lemma <ref> (in fact, the last lines
in the proof of Lemma <ref> in Appendix <ref>
above), for 

    k≥3.51· n+1.385·ln(n/ϵ)1-|λ_m|,

we get that 

    B^k_2=T^k_2≤ϵ,

and for e_i being the vector with 1 at position i and zeros
elsewhere, we get using Cauchy-Schwarz 

    |B^k(i,j)|=|⟨ e_i,B^ke_j⟩|≤e_i_2B_2e_j_2≤ϵ.

Thus, for any set S for which ∑_i∈ Sw_i^2≤1/2,
let 

    ϵ=c·κ=c·min_iu_i· v_i=c·min_iw_i^2≤ c· w_i· w_j

for any i,j, where c is some constant to be set later. Then

    ϕ_S(A^k)     =⟨1_S,D_wA^kD_w1_S⟩/⟨1_S,D_wD_w1⟩
        =∑_i∈ S,j∈SA^k(i,j)· w_i· w_j/∑_i∈ Sw_i^2
        =∑_i∈ S,j∈S(w· w^T(i,j)+B^k(i,j))· w_i· w_j/∑_i∈ Sw_i^2
       ≥∑_i∈ S,j∈S(w_i· w_j-ϵ)· w_i· w_j/∑_i∈ Sw_i^2
       ≥(1-c)∑_i∈ Sw_i^2∑_j∈Sw_j^2/∑_i∈ Sw_i^2
       ≥1/2(1-c)

since ∑_i∈Sw_i^2≥1/2. Thus, we
get that for 

    k≥3.51n+1.385·ln(c· n/κ)1-|λ_m|

the edge expansion 

    ϕ(A^k)≥1/2(1-c),

and thus using Lemma <ref>, we get that 

    ϕ(A)    ≥1/k·ϕ(A^k)≥1-c/2·1-|λ_m|/3.51· n+1.385·ln(c· n)+1.385·ln(1/κ)

and setting c=1/1.4· e, and using ln(e· x)≤ x,we
get that 

    ϕ(A)    ≥1-|λ_m|/15· n+2·ln(1/κ)
       ≥1/15·1-|λ_m|/n+ln(1/κ)





 §.§ Proof of Lemma <ref>


Let R be a nonnegative matrix with PF eigenvalue 1, and let some
eigenvalue λ_r(R)=α+iβ, and letting the gap g=1-α,
we can rewrite 

    λ_r=(1-g)+iβ

with (1-g)^2+β^2≤1, or 

    g^2+β^2≤2g.

Consider the lazy random walk R̃=pI+(1-p)R for some 0≤ p≤1,
the eigenvalue modifies as 

    λ_r(R̃)     =p+(1-p)(1-g)+i(1-p)β
        =1-g(1-p)+iβ(1-p)

and for any set S, since ϕ_S(I)=0, we have 

    ϕ_S(R̃)=(1-p)ϕ_S(R)

or 

    ϕ(R̃)=(1-p)ϕ(R).

Further, 

    1-|λ_r(R̃)|     =1-√((1-g(1-p))^2+(β(1-p))^2)
        =1-√(1+(g^2+β^2)(1-p)^2-2g(1-p))
       ≥1-√(1+2g(1-p)^2-2g(1-p))
            [using inequality <ref>]
        =1-√(1-2gp(1-p))
       ≥1-e^-gp(1-p)
            [using ]
       ≥1-(1-1/2gp(1-p))
            [using  for ]
        =1/2gp(1-p).

Thus, we have that, 

    (1-Reλ_2(R))· p(1-p)    ≤(1-Reλ_m(R))· p(1-p)
            [since both  and  are nontrivial eigenvalues]
       ≤2·(1-|λ_m(R̃)|)
            [using inequality <ref>]
       ≤2·15·(n+ln(1/κ))·ϕ(R̃)
            [using Lemma <ref> for ]
       ≤2·15·(n+ln(1/κ))·(1-p)ϕ(R)
            [from equation <ref>]

and taking the limit as p→1, we get that 

    1/30·1-Reλ_2(R)/n+ln(1/κ)≤ϕ(A).

Further, if A is doubly stochastic, then κ=1/n,
and using ln(en)≤ n and the last equations at the end of the
proof of Lemma <ref> in Appendix <ref>
above, we get using the same calculations that 

    1/35·1-Reλ_2(R)/n≤ϕ(A)

as required. 




§ PROOFS OF BOUNDS ON MIXING TIME




 §.§ Proof of Lemma <ref>


Writing τ as shorthand for τ_ϵ(A) and since A=w· w^T+B
with Bw=0 and B^Tw=0, we have that A^τ=w· w^T+B^τ.
Let x be a nonnegative vector such that ⟨ w,x⟩=D_wx_1=1.
As discussed after Definition <ref>, this is
sufficient for bounding mixing time for all x. Then we have 

    D_w(A^τ-w· w^T)x_1    =D_wB^τx_1=D_wB^τD_w^-1y_1≤D_w_1B^τ_1D_w^-1_1y_1

where y=D_wx and y_1=1. Further, since w_2=1
and κ=min_iw_i^2, we have D_w_1≤1 and
D_w^-1_1≤1/√(κ), and using these
bounds to continue the inequalities above, we get 

    D_w(A^τ-w· w^T)x_1≤1/√(κ)B^τ_1≤√(n)/√(κ)B^τ_2≤√(n)/√(κ)B_2^τ≤√(n)/√(κ)(σ_2(A))^τ=√(n)/√(κ)(σ_2^c(A))^τ/c≤ϵ

where the second inequality is Cauchy-Schwarz, the fourth inequality
used B_2≤σ_2(A) as shown in the proof (in Appendix
<ref>) of Lemma <ref>,
and the last inequality was obtained by setting τ=τ_ϵ(A)=c·ln(√(n)/√(κ)·ϵ)1-σ_2^c(A). 




 §.§ Proof of Lemma <ref>


We first show that the mixing time of R and A=D_u^1/2D_v^-1/2RD_u^-1/2D_v^1/2
are the same. Let w=D_u^1/2D_v^1/21,
the left and right eigenvector of A for eigenvalue 1. We will show
that for every x for which D_ux_1=1, there exists some
y with D_wy_1=1 such that 

    D_u(R^τ-v· u^T)x_1=D_w(A^τ-w· w^T)y_1

which would imply that τ_ϵ(R)=τ_ϵ(A) by
definition.

Let x be a vector with D_ux_1=1 and let y=D_u^1/2D_v^-1/2x.
Then since D_w=D_u^1/2D_v^1/2, we get
D_wy_1=D_ux_1=1. Let R=v· u^T+B_R and
A=w· w^T+B_A where B_A=D_u^1/2D_v^-1/2B_RD_u^-1/2D_v^1/2
and B_A^τ=D_u^1/2D_v^-1/2B_R^τD_u^-1/2D_v^1/2.
Then 

    D_u(R^τ-v· u^T)x     =D_uB_R^τx
        =D_u(D_u^-1/2D_v^1/2B_A^τD_u^1/2D_v^-1/2)x
        =D_wB_A^τy
        =D_w(A^τ-w· w^T)y

as required. Further, from Lemma <ref>, we have that
ϕ(R)=ϕ(A). Thus, we show the bound for τ_ϵ(A)
and ϕ(A), and the bound for R will follow. Note that if R
is 1/2-lazy, then A is also 1/2-lazy, since
if R=1/2I+1/2C where C is nonnegative, then

    A=1/2D_u^1/2D_v^-1/2ID_u^-1/2D_v^1/2+D_u^1/2D_v^-1/2CD_u^-1/2D_v^1/2=1/2I+D_u^1/2D_v^-1/2CD_u^-1/2D_v^1/2.


We first lower bound τ_ϵ(A) using ϕ, showing
the lower bound on mixing time in terms of the edge expansion. We
will show the bound for nonnegative vectors x, and by Definition
<ref> and the discussion after, it will hold
for all x. By definition of mixing time, we have that for any nonnegative
x such that D_wx_1=⟨ w,x⟩=1, since A^τ=w· w^T+B^τ,

    D_w(A^τ-w· w^T)x_1=D_wB^τx_1≤ϵ

and letting y=D_wx, we get that for any nonnegative y with
y_1=1, we have 

    D_wB^τD_w^-1y_1≤ϵ.

Plugging the standard basis vectors for i, we get that for every
i, 

    ∑_j|1/w(i)· B^τ(j,i)· w(j)|=1/w(i)·∑_j|B^τ(j,i)|· w(j)≤ϵ.

Thus, for any set S, 

    ∑_i∈ Sw(i)^2·1/w(i)·∑_j|B^τ(j,i)|· w(j)=∑_i∈ S∑_jw(i)·|B^τ(j,i)|· w(j)≤∑_i∈ Sw(i)^2·ϵ.

Thus, for any set S for which ∑_i∈ Sw_i^2≤1/2,

    ϕ_S(A^τ)     =⟨1_S,D_wA^τD_w1_S⟩/⟨1_S,D_w^21⟩=⟨1_S,D_wA^τD_w1_S⟩/⟨1_S,D_w^21⟩
           [since  is Eulerian, i.e. ]
        =∑_i∈ S∑_j∈SA^τ(j,i)· w(i)· w(j)/∑_i∈ Sw_i^2
        =∑_i∈ S∑_j∈Sw(j)· w(i)· w(i)· w(j)+∑_i∈ S∑_j∈SB^τ(j,i)· w(i)· w(j)/∑_i∈ Sw_i^2
       ≥∑_j∈Sw_j^2-∑_i∈ S∑_j∈S|B^τ(j,i)|· w(i)· w(j)/∑_i∈ Sw_i^2
       ≥∑_j∈Sw_j^2-∑_i∈ S∑_j|B^τ(j,i)|· w(i)· w(j)/∑_i∈ Sw_i^2
       ≥1/2-ϵ
           [since  and , and the second term follows from equation <ref>]

and thus 

    ϕ(A^τ)≥1/2-ϵ,

and using Lemma <ref>, we obtain 

    ϕ(A^τ)≤τ·ϕ(A),

or 

    1/2-ϵ/ϕ(A)≤τ_ϵ(A).


We now upper bound τ_ϵ(A) in terms of ϕ(A). From
Lemma <ref> for c=2, we have that 

    τ_ϵ(A)≤2·ln(n/κ·ϵ)/1-σ_2^2(A)=2·ln(n/κ·ϵ)/1-λ_2(AA^T).

The continuing argument is straightforward, and was shown in Fill
<cit.> (albeit for row-stochastic matrices), and
we reproduce it here for completeness. Since A is 1/2-lazy,
we have that 2A-I is nonnegative, has PF eigenvalue 1, and has
the same left and right eigenvector w for eigenvalue 1 implying
that the PF eigenvalue is 1 by Perron-Frobenius (Theorem <ref>,
part 2), and also that its largest singular value is 1 from Lemma
<ref>. Further, 1/2(A+A^T) also has the
same properties. Thus, for any x, 

    AA^T    =A+A^T/2+(2A-I)(2A^T-I)/4-I/4
    ⇒⟨ x,AA^Tx⟩   ≤⟨ x,A+A^T/2x⟩+x_2(2A-I)_2(2A^T-I)_2/4x_2-x_2^2/4≤⟨ x,A+A^T/2x⟩
    ⇒max_x⊥ w⟨ x,AA^Tx⟩   ≤max_x⊥ w⟨ x,A+A^T/2x⟩.

where the last implication followed by the variational characterization
of eigenvalues since AA^T and 1/2(A+A^T) are symmetric,
and thus 

    λ_2(AA^T)≤λ_2(A+A^T/2)

which from equation <ref>, gives


    τ_ϵ(A)≤2·ln(n/κ·ϵ)/1-σ_2^2(A)=2·ln(n/κ·ϵ)/1-λ_2(AA^T)≤2·ln(n/κ·ϵ)/1-λ_2(A+A^T/2)≤4·ln(n/κ·ϵ)/ϕ^2(A+A^T/2)=4·ln(n/κ·ϵ)/ϕ^2(A)

where the second last inequality follows from Cheeger's inequality
<ref> for the symmetric matrix (A+A^T)/2. 




 §.§ Proof of Lemma <ref>


Since the mixing time (as shown in the proof of Lemma <ref>
in Appendix <ref>), eigenvalues, edge expansion,
and value of κ for R and A=D_u^1/2D_v^-1/2RD_u^-1/2D_v^1/2
are the same, we provide the bounds for A and the bounds for R
follow. We also restrict to nonnegative vectors, the bound for general
vectors follows by the triangle inequality as discussed after Definition
<ref>.

The lower bound on τ_ϵ(R) follows by combining the
lower bound on τ_ϵ(R) in terms of ϕ(R) in Lemma
<ref>, and the upper bound on ϕ(R) in terms
of 1-Reλ_2(R) in Theorem <ref>.
For the upper bound on τ_ϵ(R), similar to the proof
of Lemma <ref>, we have for any nonnegative vector
x with ⟨ w,x⟩=1, for A=w· w^T+B, 

    D_w(A^τ-w· w^T)x_1≤√(n/κ)·B^τ_2

and having 

    B^τ_2≤ϵ√(κ)/√(n)

is sufficient. Let T be the triangular matrix in the Schur form
of B, from the proof of Lemma <ref> in Appendix
<ref>, we have that for 

    k≥3.51n+1.385ln(n/δ)1-|λ_m(A)|,

the norm 

    B^k_2≤δ,

and thus setting δ=ϵ√(κ)/√(n),
we get that 

    τ_ϵ(A)≤3.51n+1.385ln(n·√(n)/√(κ)·ϵ)1-|λ_m(A)|.

Further, since A is 1/2-lazy, 2A-I is also nonnegative,
with the same positive left and right eigenvector w for PF eigenvalue
1, thus having largest singular value 1, and thus every eigenvalue
of 2A-I has magnitude at most 1. Similar to the proof of Lemma
<ref> in Appendix <ref>,
if λ_r=a+i· b is any eigenvalue of A, the corresponding
eigenvalue in 2A-I is 2a-1+i·2b, whose magnitude is at most
1, giving (2a-1)^2+4b^2≤1 or a^2+b^2≤ a. It further
gives that 

    1-|λ_r|=1-√(a^2+b^2)≥1-√(1-(1-a))≥1-e^1/2(1-a)≥1/4(1-a)

or 

    1-|λ_m|≥1/4(1-Reλ_m)≥1/4(1-Reλ_2),

which gives 

    τ_ϵ(A)    ≤4·3.51n+1.385ln(n·√(n)/√(κ)·ϵ)1-Reλ_2(A)
       ≤20·n+ln(1κ·ϵ)/1-Reλ_2(A)

completing the proof. 




 §.§ Proof of Lemma <ref>


Since ϕ(A)=ϕ(M) and each have the same left and right eigenvector
w for PF eigenvalue 1, the lower bound on τ_ϵ(A)
in terms of τ_ϵ(M) follows immediately from Lemma <ref>,
since 

    √(τ_ϵ(M))≤ln^1/2(n/κ·ϵ)·1/ϕ(M)=ln^1/2(n/κ·ϵ)·1/ϕ(A)≤ln^1/2(n/κ·ϵ)·2τ_ϵ(A)/1-2ϵ.


For the upper bound, we first define a new quantity for positive
semidefinite nonnegative matrices M with PF eigenvalue 1 and w
as the corresponding left and right eigenvector. Let T_ϵ(M)
be defined as the smallest number k for which 

    M^k-w· w^T_2=ϵ.


Since M is symmetric, we can write M=w· w^T+UDU^* where
the first column of the unitary U is w, and the diagonal matrix
D contains all eigenvalues of M except the eigenvalue 1 which
is replaced by 0. Further, since M is positive semidefinite, λ_2(M)
is the second largest eigenvalue of M, then for every i>2, 0≤λ_i(M)≤λ_2(M).
Thus we have 

    M^k-w· w^T_2=UD^kU^*_2=D^k_2=λ_2^k(M)

and 

    T_ϵ(M)=ln(1/ϵ)/ln(1/λ_2(M)).

Further, for the eigenvector y of M corresponding to λ_2,
we have for k=T_ϵ(M), 

    (M^k-w· w^T)y=λ_2^k· y=ϵ· y.

Setting x=y/D_wy_1, we have D_wx_1=1,
and we get 

    D_w(M^k-w· w^T)x_1=‖ D_wϵ· y/D_wy_1‖ _1=ϵ,

which implies that 

    τ_ϵ(M)≥ k=T_ϵ(M),

since there is some vector x with D_wx=1 that has D_w(M^k-w· w^T)x_1=ϵ
and for every t<k, it is also the case that D_w(M^t-w· w^T)x_1>ϵ.

Now we observe that since A is 1/2-lazy with PF eigenvalue
1, and the same left and right eigenvector w for eigenvalue 1,
we have that M=1/2(A+A^T) is positive semidefinite. We
continue to bound τ_ϵ(A) similar to the proof method
(in Appendix <ref>) used for Lemma <ref>.
For any t and x with D_wx_1=1, we have that 

    D_w(A^t-w· w^T)x_1≤√(n/κ)σ_2(A)^t=√(n/κ)σ_2^2(A)^t/2

and thus, 

    τ_ϵ(A)≤2·ln(√(n)/√(κ)·ϵ)/ln(1/σ_2^2(A))

and since A is 1/2-lazy, as shown in the proof of Lemma
<ref> in Appendix <ref>,

    σ_2^2(A)=λ_2(AA^T)≤λ_2(M),

giving 

    τ_ϵ(A)≤2·ln(√(n)/√(κ)·ϵ)/ln(1/λ_2(M))=2·ln(√(n)/√(κ)·ϵ)/ln(1/ϵ)·ln(1/ϵ)/ln(1/λ_2(M))=2·ln(√(n)/√(κ)·ϵ)/ln(1/ϵ)· T_ϵ(M)≤2·ln(√(n)/√(κ)·ϵ)/ln(1/ϵ)·τ_ϵ(M)

where the last inequality followed from equation <ref>. 




 §.§ Proof of Lemma <ref>


We will first find the mixing time of the operator exp(R-I/2),
and the mixing time of the operator exp(R-I) will simply be twice
this number. By expansion of the exp function, it follows that
exp(R-I/2) has PF eigenvalue 1, and u and
v as the corresponding left and right eigenvectors. Further,


    exp(R-I/2)=e^-1/2(I+∑_i≥11/i!R^i/2^i)

which is 1/2-lazy due to the first term since e^-1/2≥1/2
and all the other terms are nonnegative. Further, for any set S
for which ∑_i∈ Su_iv_i≤1/2, let δ=1/2,
then 

    ϕ_S(exp(R-I/2))     =e^-δ·⟨1_S,D_uexp(R/2)D_v1_S⟩/⟨1_S,D_uD_v1⟩
        =e^-δ·∑_i≥1δ^i/i!·⟨1_S,D_uR^iD_v1_S⟩/⟨1_S,D_uD_v1⟩
           [since ]
        =e^-δ·∑_i≥1δ^i/i!·ϕ_S(R^i)
           [since  also has  and  as the left and right eigenvectors for eigenvalue 1]
       ≤ e^-δ·∑_i≥1δ^i/i!· i·ϕ_S(R)
           [using Lemma <ref>]
        =e^-δ·δ·ϕ_S(R)∑_i≥1δ^i-1/(i-1)!
        =e^-δ·δ·ϕ_S(R)· e^δ
        =δ·ϕ_S(R)

and thus, 

    ϕ(exp(R-I/2))≤1/2ϕ(R).

Moreover, considering the first term in the expansion, we get 

    ϕ_S(exp(R-I/2))     =e^-δ∑_i≥1δ^i/i!·ϕ_S(R^i)≥ e^-δ·δ·ϕ_S(R)

or 

    ϕ(exp(R-I/2))≥3/10·ϕ(R).

Since exp(R-I/2) has left and right eigenvectors
u and v, and is 1/2-lazy, we get from Lemma <ref>
and equations <ref> and <ref>
that 

    1/2·1/2-ϵ/1/2ϕ(R)≤τ_ϵ(exp(R-I))≤2·4·ln(n/κ·ϵ)/(3/10)^2ϕ^2(R)≤100·ln(n/κ·ϵ)/ϕ^2(R)

giving the result. 




§ INTUITION BEHIND THE
CONSTRUCTION 


The main idea behind the construction in Section <ref>
is to systematically reduce the space of doubly stochastic matrices
under consideration, while ensuring that we still have matrices that
we care about in our space. We explain some of the key ideas that
led to the construction.


All eigenvalues 0. Consider de Bruijn graphs. As
stated in Section <ref>, all their nontrivial
eigenvalues are 0, yet they have small expansion. This suggests the
question whether de Bruijn matrices have the minimum expansion
amongst all doubly stochastic matrices that have eigenvalue
0 (which turned out to be far from the case). As we see in the
first steps in the proof of Lemma <ref> in Appendix
<ref>, if for a doubly stochastic matrix
A, every nontrivial eigenvalue has magnitude at most 1-c for
some constant c, then powering just O(log n) times will make
the diagonal entries inverse polynomially small in magnitude, and
thus it would seem that the matrix should have behavior similar to
matrices with all eigenvalues 0. 

(This leaves to consider matrices with eigenvalues separated
from A but of large norm; however, such eigenvalues are associated
with near-periodicity of the chain, and indeed vanish under lazification,
which is essentially the first step in the proof of Lemma <ref>
or the lower bound in Theorem <ref>) 

 Thus, the starting point of the construction is to consider only
doubly stochastic matrices that have all eigenvalues 0. Note that
this also helps us to restrict to real (i.e., orthogonal) diagonalizing
unitaries U, and real triangular matrices T in the Schur form.



Schur block that looks like a Jordan block. The
next observation again comes from the proof of Lemma <ref>
(in Appendix <ref>). Note that after
writing A=J+B, the main idea was to observe that if B^m≈0,
then ϕ(A^m)≈ϕ(J). Since B^m=UT^mU^* where
T is upper triangular, this is equivalent to requiring that T^m≈0.
As we have assumed that all nontrivial eigenvalues of T are 0,
it means the entire diagonal of T is 0. How large does m have
to be to ensure that T^m≈0? It is shown in Lemma <ref>
that for m≈ O(n), T^m≈0. Observe that for Lemma
<ref>, Ω(n) is indeed necessary, considering
the case of nilpotent T, with all 0 entries, and 1 on every entry
above the diagonal. But can a doubly stochastic matrix have such a
Schur form? Such matrices would at least be sufficient on the outset,
to ensure that Lemma <ref> is tight, hopefully
giving us the kind of bound we need. Thus, our second restriction
is the following: we assume that every entry of T is 0, and every
off-diagonal entry (entries T(i,i+1) for 2≤ i≤ n-1) is
r. We want to maximize r
and still have some unitary that transforms T to a doubly stochastic
matrix. Note that T will have only 0 in the entries
of the first row and column since we have diagonalized-out the projection
onto the stochastic eigenvector (i.e., J). In any upper triangular
matrix T in which the diagonal has zeros, the off-diagonal entries
affect the entries in powers of T the most, since entries
far from the diagonal will become ineffective after a few powers of
T. Thus, choosing T with the non-zeros pattern of a Jordan block
will not be far from optimal. 


Restricting to hermitian unitaries with a uniform
row vector. Next we make several observations about the unitary U,
where A=J+UTU^*. Note that the first column of U is the vector
1/√(n)1, since it is an eigenvector of A.
The choice of U constrains the value of r that we can use in
T since it must lead to A becoming a doubly stochastic matrix.
From considering the optimal 3×3 and 4×4 cases, which
although, clearly, do not give any information about relation between
ϕ and Reλ_2 or Γ (since it could be
off by large constant factors), we note that they do give information
about the unitary U, since it is a rotation and is
not a numeric value like ϕ or Reλ_2. From
these cases, we make the crucial (albeit empirical) observation: the
direction in which r can be maximized (given our constraints)
is such that the first row of U is also 1/√(n)1,
and this is the second constraint we impose on U. Given that the
unitaries have the same vector in the first row and column,
our next observation (again from considering certain specific cases)
is that since the unitary preserves the all 1's eigenvector, and
since T has exactly the same value above the diagonal by
construction and all other entries are 0, U is performing only
2 types of actions on T. This type of feature is provided
by unitaries that are hermitian, and this is the next assumption we
make – we restrict to unitaries that are hermitian. 


Optimizing for ϕ and r. The restrictions
adopted so far on the unitary U and the Schur matrix T imply
a sequence of inequalities to ensure that A=J+UTU^* is doubly
stochastic. Subject to the constraints provided by these inequalities,
we aim to minimize ϕ and maximize r. Due to
our restrictions on U, the cut S={1} in the resulting matrix
A is special, and we aim to minimize the edge expansion
1-A_1,1 of this cut. With the set of possible values that r
can take, we note that a set of extreme points of the resulting optimization
problem of minimizing 1-A_1,1 or maximizing A_1,1 are obtained
if we force the values of all the entries A_1,i for 3≤ i≤ n
to 0. We then maximize r for the resulting matrix (indeed, there
are exactly two possible doubly stochastic matrices at this point),
and the result is the construction given in Section <ref>.
