(n.; the plural is ``adjacency matrices''): A table of 0's and 1's that encodes the structure of a graph. The rows and columns are labeled by the vertices; the entry in row r and column c is 1 if and only if (r,c) is an edge of the graph. Thus an adjacency matrix is a square table, which is diagonally symmetrical unless the graph is directed. For example, 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 is an adjacency matrix of a pentagon, and 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 is an adjacency matrix of a directed pentagon. (I write ``an adjacency matrix'' rather than ``the adjacency matrix'' because the table depends on how the vertices are ordered; for instance 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 is also an adjacency matrix of a directed pentagon. What's the total number of different adjacency matrices of this directed graph?)
In mathematics and computer science, the adjacency matrix of a finite directed or undirected graph G on n vertices is the n × n matrix where the nondiagonal entry a_{ij} is the number of edges from vertex i to vertex j, and the diagonal entry a_{ii} is either twice the number of loops at vertex i or just the number of loops (usages differ, depending on the mathematical needs; this article follows the former convention for undirected graphs, though directed graphs always follow the latter). There exists a unique adjacency matrix for each graph (up to permuting rows and columns), and it is not the adjacency matrix of any other graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal.
