Editing Adjacency matrix (section)

===Spectrum===
The adjacency matrix of an undirected simple graph is [[symmetric matrix|symmetric]], and therefore has a complete set of [[real number|real]] [[eigenvalue]]s and an orthogonal [[eigenvector]] basis. The set of eigenvalues of a graph is the '''spectrum''' of the graph.<ref>{{harvtxt|Biggs|1993}}, Chapter 2 ("The spectrum of a graph"), pp.&nbsp;7–13.</ref> It is common to denote the eigenvalues by <math>\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n.</math>

The greatest eigenvalue <math>\lambda_1</math> is bounded above by the maximum degree. This can be seen as result of the [[Perron–Frobenius theorem]], but it can be proved easily. Let {{mvar|v}} be one eigenvector associated to <math>\lambda_1</math> and {{mvar|x}} the entry in which {{mvar|v}} has maximum absolute value. Without loss of generality assume {{mvar|v<sub>x</sub>}} is positive since otherwise you simply take the eigenvector -{{mvar|v}}, also associated to <math>\lambda_1</math>. Then

: <math>\lambda_1 v_x = (Av)_x = \sum_{y=1}^n A_{x,y}v_y \leq \sum_{y=1}^n A_{x,y} v_x = v_x \deg(x).</math>

For {{mvar|d}}-regular graphs, {{mvar|d}} is the first eigenvalue of {{mvar|A}} for the vector {{math|{{nowrap|''v'' {{=}} (1, ..., 1)}}}} (it is easy to check that it is an eigenvalue and it is the maximum because of the above bound). The multiplicity of this eigenvalue is the number of connected components of {{mvar|G}}, in particular <math>\lambda_1>\lambda_2</math> for connected graphs. It can be shown that for each eigenvalue <math>\lambda_i</math>, its opposite <math>-\lambda_i = \lambda_{n+1-i}</math> is also an eigenvalue of {{mvar|A}} if {{mvar|G}} is a [[bipartite graph]].<ref>{{citation|last1=Brouwer|first1=Andries E.|last2=Haemers|first2=Willem H.|contribution=1.3.6 Bipartite graphs|contribution-url=https://books.google.com/books?id=F98THwYgrXYC&pg=PA6|doi=10.1007/978-1-4614-1939-6|isbn=978-1-4614-1938-9|location=New York|mr=2882891|pages=6–7|publisher=Springer|series=Universitext|title=Spectra of Graphs|year=2012}}</ref> In particular −{{mvar|d}} is an eigenvalue of any {{mvar|d}}-regular bipartite graph.

The difference <math>\lambda_1 - \lambda_2</math> is called the [[spectral gap]] and it is related to the [[Expander graph|expansion]] of {{mvar|G}}. It is also useful to introduce the [[spectral radius]] of <math>A</math> denoted by <math>\lambda(G) = \max_{\left|\lambda_i\right| < d} |\lambda_i|</math>. This number is bounded by <math>\lambda(G) \geq 2\sqrt{d-1} - o(1)</math>. This bound is tight in the [[Ramanujan graphs]].