Editing Adjacency matrix (section)

==Properties==
===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]].

===Isomorphism and invariants===
Suppose two directed or undirected graphs {{math|''G''<sub>1</sub>}} and {{math|''G''<sub>2</sub>}} with adjacency matrices {{math|''A''<sub>1</sub>}} and {{math|''A''<sub>2</sub>}} are given. {{math|''G''<sub>1</sub>}} and {{math|''G''<sub>2</sub>}} are [[graph isomorphism|isomorphic]] if and only if there exists a [[permutation matrix]] {{mvar|P}} such that
: <math>P A_1 P^{-1} = A_2.</math>

In particular, {{math|''A''<sub>1</sub>}} and {{math|''A''<sub>2</sub>}} are [[Similar (linear algebra)|similar]] and therefore have the same [[Minimal polynomial (linear algebra)|minimal polynomial]], [[characteristic polynomial]], [[eigenvalues]], [[determinant]] and [[Trace (matrix)|trace]]. These can therefore serve as isomorphism invariants of graphs. However, two graphs may possess the same set of eigenvalues but not be isomorphic.<ref>[[Godsil, Chris]]; [[Gordon Royle|Royle, Gordon]] ''Algebraic Graph Theory'', Springer (2001), {{ISBN|0-387-95241-1}}, p.164</ref> Such [[linear operator]]s are said to be [[isospectral]].

===Matrix powers===
If {{mvar|A}} is the adjacency matrix of the directed or undirected graph {{mvar|G}}, then the matrix {{math|''A''<sup>''n''</sup>}} (i.e., the [[matrix multiplication|matrix product]] of {{mvar|n}} copies of {{mvar|A}}) has an interesting interpretation: the element {{math|{{nowrap|(''i'', ''j'')}}}} gives the number of (directed or undirected) [[Path (graph theory)|walks]] of length {{mvar|n}} from vertex {{mvar|i}} to vertex {{mvar|j}}. If {{mvar|n}} is the smallest nonnegative integer, such that for some {{mvar|i}}, {{mvar|j}}, the element {{math|{{nowrap|(''i'', ''j'')}}}} of {{math|''A''<sup>''n''</sup>}} is positive, then {{mvar|n}} is the distance between vertex {{mvar|i}} and vertex {{mvar|j}}. A great example of how this is useful is in counting the number of triangles in an undirected graph {{mvar|G}}, which is exactly the [[Trace (linear algebra)|trace]] of {{math|''A''<sup>3</sup>}} divided by 3 or 6 depending on whether the graph is directed or not. We divide by those values to compensate for the overcounting of each triangle. In an undirected graph, each triangle will be counted twice for all three nodes, because the path can be followed clockwise or counterclockwise : ijk or ikj. The adjacency matrix can be used to determine whether or not the graph is [[Connectivity (graph theory)|connected]].

If a directed graph has a [[nilpotent matrix|nilpotent]] adjacency matrix (i.e., if there exists {{mvar|n}} such that {{math|''A''<sup>''n''</sup>}} is the zero matrix), then it is a [[directed acyclic graph]].<ref>{{Cite journal|title=Matrices with Permanent Equal to One |last1=Nicholson |first1=Victor A |year=1975 |journal=Linear Algebra and Its Applications |issue=12 |page=187|url=https://core.ac.uk/download/pdf/82099476.pdf}}</ref>