Editing Expander graph (section)

===Spectral expansion===
When {{mvar|G}} is [[regular graph|{{mvar|d}}-regular]], a [[linear algebra]]ic definition of expansion is possible based on the [[Eigenvalue#Eigenvalues of matrices|eigenvalues]] of the [[adjacency matrix]] {{math|1=''A'' = ''A''(''G'')}} of {{mvar|G}}, where {{mvar|A{{sub|ij}}}} is the number of edges between vertices {{mvar|i}} and {{mvar|j}}.<ref>cf. Section 2.3 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref> Because {{mvar|A}} is [[symmetric matrix|symmetric]], the [[spectral theorem]] implies that {{mvar|A}} has {{mvar|n}} real-valued eigenvalues {{math|''λ''{{sub|1}} ≥ ''λ''{{sub|2}} ≥ … ≥ ''λ''{{sub|''n''}}}}.  It is known that all these eigenvalues are in {{math|[−''d'', ''d'']}} and more specifically, it is known that {{math|1=''λ''{{sub|''n''}} = −''d''}} if and only if {{mvar|G}} is bipartite.

More formally, we refer to an {{mvar|n}}-vertex, {{mvar|d}}-regular graph with 
:<math>\max_{i \neq 1}|\lambda_i| \leq \lambda</math> 
as an {{math|(''n'', ''d'', ''λ'')}}-''graph''. The bound given by an {{math|(''n'', ''d'', ''λ'')}}-graph on {{math|''λ''{{sub|''i''}}}} for {{math|''i'' ≠ 1}} is useful in many contexts, including the [[expander mixing lemma]].

Spectral expansion can be ''two-sided'', as above, with <math>\max_{i \neq 1}|\lambda_i| \leq \lambda</math>, or it can be ''one-sided'', with <math>\max_{i \neq 1}\lambda_i \leq \lambda</math>. The latter is a weaker notion that holds also for bipartite graphs and is still useful for many applications, such as the Alon–Chung lemma.<ref>N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks. Discrete Math., vol. 72, pp. 15–19, 1988.</ref>

Because {{mvar|G}} is regular, the uniform distribution <math>u\in\R^n</math> with {{math|1=''u{{sub|i}}'' = {{frac|1|''n''}}}} for all {{math|1=''i'' = 1, …, ''n''}} is the [[stationary distribution]] of {{mvar|G}}. That is, we have {{math|1=''Au'' = ''du''}}, and {{mvar|u}} is an [[eigenvector]] of {{mvar|A}} with eigenvalue {{math|1=''λ''{{sub|1}} = ''d''}}, where {{mvar|d}} is the [[degree (graph theory)|degree]] of the vertices of {{mvar|G}}. The ''[[spectral gap]]'' of {{mvar|G}} is defined to be {{math|''d'' − ''λ''{{sub|2}}}}, and it measures the spectral expansion of the graph {{mvar|G}}.<ref>This definition of the spectral gap is from Section 2.3 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>

If we set
:<math>\lambda=\max\{|\lambda_2|, |\lambda_n|\}</math>
as this is the largest eigenvalue corresponding to an eigenvector [[orthogonal]] to {{mvar|u}}, it can be equivalently defined using the [[Rayleigh quotient]]:
:<math>\lambda=\max_{v \perp u , v \neq 0} \frac{\|Av\|_2}{\|v\|_2},</math>
where 
:<math>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}</math> 
is the [[2-norm]] of the vector <math>v\in\R^n</math>.

The normalized versions of these definitions are also widely used and more convenient in stating some results. Here one considers the matrix {{math|{{sfrac|1|''d''}}''A''}}, which is the [[Markov transition matrix]] of the graph {{mvar|G}}. Its eigenvalues are between −1 and 1. For not necessarily regular graphs, the spectrum of a graph can be defined similarly using the eigenvalues of the [[Laplacian matrix]]. For [[directed graph]]s, one considers the [[singular values]] of the adjacency matrix {{mvar|A}}, which are equal to the roots of the eigenvalues of the symmetric matrix {{math|''A''{{sup|T}}''A''}}.