We can represent an n-node graph by an n-by-n matrix. Assume the nodes are labeled ${\displaystyle v_{1},\ldots ,v_{n}}$. Then the adjacency matrix ${\displaystyle A}$ is an n by n matrix whose entry ${\displaystyle A_{ij}}$ is defined to be

• 1, if there is an edge from ${\displaystyle v_{i}}$ to ${\displaystyle v_{j}}$
• 0, otherwise.

Note that an undirected graph corresponds to a symmetric matrix.

We could instead put weights on the edges, and define ${\displaystyle A_{ij}}$ to be

• 0, if there is no edge from ${\displaystyle v_{i}}$ to ${\displaystyle v_{j}}$
• ${\displaystyle w}$, if there is an edge, and ${\displaystyle w}$ is its weight.

See Graph Data Structures for another definition of the adjacency matrix.

## Multiplication of the Adjacency Matrix

Note that the entry ${\displaystyle A_{ij}}$ of an unweighted adjacency matrix simply counts the number of paths from ${\displaystyle v_{i}}$ to ${\displaystyle v_{j}}$ 'of length one'. A useful fact is that similarly, the entry ${\displaystyle (A^{k})_{ij}}$ of the ${\displaystyle k}$th power of the adjacency matrix counts the number of paths of length exactly ${\displaystyle k}$ from ${\displaystyle v_{i}}$ to ${\displaystyle v_{j}}$. By using repeated squaring we can sometimes count paths quickly.