Encyclopedia > Adjacency matrix

  Article Content

Adjacency matrix

In mathematics and computer science, a finite graph is often represented by its adjacency matrix. The adjacency matrix of a directed or undirected graph (with n vertices, say) is the n-by-n matrix whose entry in row i and column j gives the number of edges from the i-th to the j-th vertex. (An alternative way to store graphs in computers, especially graphs with few edges, is given by the incidence matrix[?].)

The modified adjacency matrix is generated by replacing all entries greater than 1 in the adjacency matrix by 1.

Examples

The adjacency matrix for the example graph

is
<math>\begin{pmatrix}
0 & 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}</math>

Properties

The adjacency matrix of undirected graphs is always symmetric.

Suppose two directed or undirected graphs G1 and G2 with adjacency matrices A1 and A2 are given. G1 and G2 are isomorphic if and only if there exists a permutation matrix P such that

PA1P −1 = A2.
In particular, A1 and A2 are similar and have therefore the same minimal polynomial, characteristic polynomial, eigenvalues, determinant and trace. These can therefore serve as isomorphism invariants of graphs.

If A is the adjacency matrix of the directed or undirected graph G, then the matrix An (i.e. the matrix product of n copies of A) has an interesting interpretation: the entry in row i and column j gives the number of (directed or undirected) paths of length n from vertex i to vertex j.

The matrix IA (where I denotes the n-by-n identity matrix) is invertible if and only if there are no directed cycles in the graph G. In this case, the inverse (IA)−1 has the following interpretation: the entry in row i and column j gives the number of directed paths from vertex i to vertex j (which is always finite if there are no directed cycles). This can be understood using the geometric series for matrices:

(IA)−1 = I + A + A2 + A3 + ...
corresponding to the fact that the number of paths from i to j equals the number of paths of length 0 plus the number of paths of length 1 plus the number of paths of length 2 etc.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Anna Karenina

... appeared serially in the periodical Ruskii Vestnik ("Russian Messenger"), but Tolstoy clashed with the editor, Mikhail Katkov, over issues that arose in the final ...

 
 
 
This page was created in 40.4 ms