## Definition

### For a finite undirected graph

Suppose  is a finite undirected graph. Let  be the size of the vertex set . Fix a bijective correspondence . The adjacency matrix of  is defined as the  matrix whose  entry is:

• 0 if there is no edge between  and 
• 1 if there is an edge between  and 

Note that this matrix is well defined only after we fix the bijection . Changing the bijection has the effect of conjugating the adjacency matrix by a permutation matrix obtained by composing one bijection with the inverse of the other. In other words, we re-label the rows and re-label the columns in the same manner. In particular, the characteristic polynomial as well as the multiset of eigenvalues do not depend on the choice of ordering of vertices.

### For a finite undirected graph allowing parallel edges, loops, and weights

• If we allow loops (but no parallel edges or weights), the definition does not change, but it may now be possible to have 1s on the diagonals at the entries corresponding to loops.
• If we allow parallel edges, then the  entry is taken to be the number of edges between  and .
• If we allow weights, we could use the weighted adjacency matrix instead.

### For a finite directed graph

Suppose  is a finite undirected graph. Let  be the size of the vertex set . Fix a bijective correspondence . The adjacency matrix of  is defined as the  matrix whose  entry is:

• 0 if there is no edge from  to 
• 1 if there is an edge from  to 

### For a finite directed graph allowing parallel edges, loops, and weights

• If we allow loops (but no parallel edges or weights), the definition does not change, but it may now be possible to have 1s on the diagonals at the entries corresponding to loops.
• If we allow parallel edges, then the  entry is taken to be the number of edges from  and .
• If we allow weights, we could use the weighted adjacency matrix instead.

## Facts

• The adjacency matrix of a finite undirected graph is a symmetric matrix. This remains true even if we allow loops and parallel edges.
• The adjacency matrix of a finite undirected graph has entries only 0s and 1s. This remains true even if we allow loops but is no longer true if we allow parallel edges.
• The adjacency matrix of a finite undirected graph has 0s throughout the diagonal. This remains true even if we allow parallel edges but is no longer true if we allow loops.