Adjacency matrix

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. If the graph is undirected (i.e. all of its edges are bidirectional), the adjacency matrix is symmetric. 
The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory.
The adjacency matrix of a graph should be distinguished from its incidence matrix, a different matrix representation whose elements indicate whether vertex–edge pairs are incident or not, and its degree matrix, which contains information about the degree of each vertex.
Definition.
For a simple graph with vertex set }, the adjacency matrix is a square matrix such that its element is one when there is an edge from vertex to vertex , and zero when there is no edge. The diagonal elements of the matrix are all zero, since edges from a vertex to itself (loops) are not allowed in simple graphs. It is also sometimes useful in algebraic graph theory to replace the nonzero elements with algebraic variables. The same concept can be extended to multigraphs and graphs with loops by storing the number of edges between each two vertices in the corresponding matrix element, and by allowing nonzero diagonal elements. Loops may be counted either once (as a single edge) or twice (as two vertex-edge incidences), as long as a consistent convention is followed. Undirected graphs often use the latter convention of counting loops twice, whereas directed graphs typically use the former convention.
Of a bipartite graph.
The adjacency matrix of a bipartite graph whose two parts have and vertices can be written in the form 
where is an matrix, and and represent the and zero matrices. In this case, the smaller matrix uniquely represents the graph, and the remaining parts of can be discarded as redundant. is sometimes called the "biadjacency matrix".
Formally, let be a bipartite graph with parts }, } and edges . The biadjacency matrix is the 0–1 matrix in which if and only if .
If is a bipartite multigraph or weighted graph, then the elements are taken to be the number of edges between the vertices or the weight of the edge , respectively.
The adjacency matrix of a bipartite graph is totally unimodular. This means that the determinant of every square submatrix of it is −1, 0, or +1.
Variations.
An -adjacency matrix of a simple graph has if is an edge, if it is not, and on the diagonal. The Seidel adjacency matrix is a -adjacency matrix. This matrix is used in studying strongly regular graphs and two-graphs.
The distance matrix has in position the distance between vertices and . 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.
Examples.
Undirected graphs.
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. 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.
Directed graphs.
The adjacency matrix of a directed graph can be asymmetric. One can define the adjacency matrix of a directed graph either such that 
The former definition is commonly used in graph theory and social network analysis (e.g., sociology, political science, economics, psychology). The latter is more common in other applied sciences (e.g., dynamical systems, physics, network science) where is sometimes used to describe linear dynamics on graphs.
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.
Trivial graphs.
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.
Properties.
Spectrum.
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. It is common to denote the eigenvalues by formula_2
The greatest eigenvalue formula_3 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 be one eigenvector associated to formula_3 and the component in which has maximum absolute value. Without loss of generality assume is positive since otherwise you simply take the eigenvector formula_5, also associated to formula_3. Then
For -regular graphs, is the first eigenvalue of for the vector (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 , in particular formula_8 for connected graphs. It can be shown that for each eigenvalue formula_9, its opposite formula_10 is also an eigenvalue of if is a bipartite graph. In particular − is an eigenvalue of bipartite graphs.
The difference formula_11 is called the spectral gap and it is related to the expansion of . It is also useful to introduce the spectral radius of formula_12 denoted by formula_13. This number is bounded by formula_14. This bound is tight in the Ramanujan graphs, which have applications in many areas.
Isomorphism and invariants.
Suppose two directed or undirected graphs and with adjacency matrices and are given. and are isomorphic if and only if there exists a permutation matrix such that
In particular, and 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. Such linear operators are said to be isospectral.
Matrix powers.
If is the adjacency matrix of the directed or undirected graph , then the matrix (i.e., the matrix product of copies of ) has an interesting interpretation: the element gives the number of (directed or undirected) walks of length from vertex to vertex . If is the smallest nonnegative integer, such that for some , , the element of is positive, then is the distance between vertex and vertex . This implies, for example, that the number of triangles in an undirected graph is exactly the trace of divided by 6. The adjacency matrix can be used to determine whether or not the graph is connected.
Data structures.
The adjacency matrix may be used as a data structure for the representation of graphs in computer programs for manipulating graphs. The main alternative data structure, also in use for this application, is the adjacency list.
Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only 2/8 bytes to represent a directed graph, or (by using a packed triangular format and only storing the lower triangular part of the matrix) approximately 2/16 bytes to represent an undirected graph. Although slightly more succinct representations are possible, this method gets close to the information-theoretic lower bound for the minimum number of bits needed to represent all -vertex graphs. For storing graphs in text files, fewer bits per byte can be used to ensure that all bytes are text characters, for instance by using a Base64 representation. Besides avoiding wasted space, this compactness encourages locality of reference.
However, for a large sparse graph, adjacency lists require less storage space, because they do not waste any space to represent edges that are "not" present.
An alternative form of adjacency matrix (which, however, requires a larger amount of space) replaces the numbers in each element of the matrix with pointers to edge objects (when edges are present) or null pointers (when there is no edge). It is also possible to store edge weights directly in the elements of an adjacency matrix.
Besides the space tradeoff, the different data structures also facilitate different operations. Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list, and takes time proportional to the number of neighbors. With an adjacency matrix, an entire row must instead be scanned, which takes a larger amount of time, proportional to the number of vertices in the whole graph. On the other hand, testing whether there is an edge between two given vertices can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the two vertices with the adjacency list.