Mathematics

Introduction to Adjacency Matrices

The formal mathematical definition of a graph is a set of points, or nodes, with specified connections between them. An economic model, for example, is a graph with different industries as the nodes and direct economic ties as the connections. The computer software industry is connected to the computer hardware industry, which, in turn, is connected to the semiconductor industry, and so on.

This definition of a graph lends itself to matrix representation. The adjacency matrix of an undirected graph is a matrix whose (i,j)th and (j,i)th entries are 1 if node i is connected to node j, and 0 otherwise. For example, the adjacency matrix for a diamond-shaped graph looks like

Since most graphs have relatively few connections per node, most adjacency matrices are sparse. The actual locations of the nonzero elements depend on how the nodes are numbered. A change in the numbering leads to permutation of the rows and columns of the adjacency matrix, which can have a significant effect on both the time and storage requirements for sparse matrix computations.

Example: Adjacency Matrices and Graphs

Graphing Using Adjacency Matrices