Adjacency matrix

The adjacency matrix A of a bipartite graph whose two parts have r and s vertices can be written in the form

${\displaystyle A={\begin{pmatrix}0_{r,r}&B\\B^{\mathsf {T}}&0_{s,s}\end{pmatrix}},}$

where B is an r × s matrix, and 0_r,r and 0_s,s represent the r × r and s × s zero matrices. In this case, the smaller matrix B uniquely represents the graph, and the remaining parts of A can be discarded as redundant. B is sometimes called the biadjacency matrix.

Formally, let G = (U, V, E) be a bipartite graph with parts U = {u₁, ..., u_r}, V = {v₁, ..., v_s} and edges E. The biadjacency matrix is the r × s 0–1 matrix B in which b_i,j = 1 if and only if (u_i, v_j) ∈ E.

If G is a bipartite multigraph or weighted graph, then the elements b_i,j are taken to be the number of edges between the vertices or the weight of the edge (u_i, v_j), respectively.

An (a, b, c)-adjacency matrix A of a simple graph has A_i,j = a if (i, j) is an edge, b if it is not, and c on the diagonal. The Seidel adjacency matrix is a (−1, 1, 0)-adjacency matrix. This matrix is used in studying strongly regular graphs and two-graphs.[3]

The distance matrix has in position (i, j) the distance between vertices v_i and v_j. The distance is the length of a shortest path connecting the vertices. Unless lengths of edges are explicitly provided, the length of a path is the number of edges in it. The distance matrix resembles a high power of the adjacency matrix, but instead of telling only whether or not two vertices are connected (i.e., the connection matrix, which contains boolean values), it gives the exact distance between them.

The convention followed here (for undirected graphs) is that each edge adds 1 to the appropriate cell in the matrix, and each loop adds 2.[4] This allows the degree of a vertex to be easily found by taking the sum of the values in either its respective row or column in the adjacency matrix.

Labeled graph	Adjacency matrix
	${\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{pmatrix}}}$ Coordinates are 1–6.
Nauru graph	Coordinates are 0–23. White fields are zeros, colored fields are ones.

The adjacency matrix of a directed graph can be asymmetric. One can define the adjacency matrix of a directed graph either such that

1. a non-zero element A_ij indicates an edge from i to j or
2. it indicates an edge from j to i.

The former definition is commonly used in graph theory and social network analysis (e.g., sociology, political science, economics, psychology).[5] The latter is more common in other applied sciences (e.g., dynamical systems, physics, network science) where A is sometimes used to describe linear dynamics on graphs.[6]

Using the first definition, the in-degrees of a vertex can be computed by summing the entries of the corresponding column and the out-degree of vertex by summing the entries of the corresponding row. When using the second definition, the in-degree of a vertex is given by the corresponding row sum and the out-degree is given by the corresponding column sum.

Labeled graph	Adjacency matrix
Directed Cayley graph of S4	Coordinates are 0–23. As the graph is directed, the matrix is not necessarily symmetric.

The adjacency matrix of a complete graph contains all ones except along the diagonal where there are only zeros. The adjacency matrix of an empty graph is a zero matrix.

The adjacency matrix of an undirected simple graph is symmetric, and therefore has a complete set of real eigenvalues and an orthogonal eigenvector basis. The set of eigenvalues of a graph is the spectrum of the graph.[7] It is common to denote the eigenvalues by ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}.}$

The greatest eigenvalue ${\displaystyle \lambda _{1}}$ 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 v be one eigenvector associated to ${\displaystyle \lambda _{1}}$ and x the component in which v has maximum absolute value. Without loss of generality assume v_x is positive since otherwise you simply take the eigenvector ${\displaystyle -v}$, also associated to ${\displaystyle \lambda _{1}}$. Then

${\displaystyle \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).}$

For d-regular graphs, d is the first eigenvalue of A for the vector 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 G, in particular ${\displaystyle \lambda _{1}>\lambda _{2}}$ for connected graphs. It can be shown that for each eigenvalue ${\displaystyle \lambda _{i}}$, its opposite ${\displaystyle -\lambda _{i}=\lambda _{n+1-i}}$ is also an eigenvalue of A if G is a bipartite graph.[8] In particular −d is an eigenvalue of any d-regular bipartite graph.

The difference ${\displaystyle \lambda _{1}-\lambda _{2}}$ is called the spectral gap and it is related to the expansion of G. It is also useful to introduce the spectral radius of ${\displaystyle A}$ denoted by ${\displaystyle \lambda (G)=\max _{\left|\lambda _{i}\right|<d}|\lambda _{i}|}$. This number is bounded by ${\displaystyle \lambda (G)\geq 2{\sqrt {d-1}}-o(1)}$. This bound is tight in the Ramanujan graphs, which have applications in many areas.

Suppose two directed or undirected graphs G₁ and G₂ with adjacency matrices A₁ and A₂ are given. G₁ and G₂ are isomorphic if and only if there exists a permutation matrix P such that

${\displaystyle PA_{1}P^{-1}=A_{2}.}$

In particular, A₁ and A₂ are similar and therefore have the same minimal polynomial, characteristic polynomial, eigenvalues, determinant and trace. These can therefore serve as isomorphism invariants of graphs. However, two graphs may possess the same set of eigenvalues but not be isomorphic.[9] Such linear operators are said to be isospectral.

If A is the adjacency matrix of the directed or undirected graph G, then the matrix Aⁿ (i.e., the matrix product of n copies of A) has an interesting interpretation: the element (i, j) gives the number of (directed or undirected) walks of length n from vertex i to vertex j. If n is the smallest nonnegative integer, such that for some i, j, the element (i, j) of Aⁿ is positive, then n is the distance between vertex i and vertex j. A great example of how this is useful is in counting the number of triangles in an undirected graph G, which is exactly the trace of A³ divided by 6. We divide by 6 to compensate for the overcounting of each triangle (3! = 6 times). The adjacency matrix can be used to determine whether or not the graph is connected.