Adjacency matrix

Construction

This note is under construction.

TODO

This note has things to do.

In graph theory, the adjacency matrix ^[1][2] of a graph is a square matrix indexed by the vertex set of $G$, whose entries record which pairs of vertices are adjacent. Together with the incidence matrix, it is one of the standard matrix representations of a graph.

Definition

---

Definition 1 (Adjacency matrix)

Let $G=(V,E)$ be a graph with vertex set $V=\{v_1,\dots ,v_n\}$. The adjacency matrix of $G$ is the $n\times n$ matrix $A=(a_{ij})$ given by

$$a_{ij}=\{\begin{array}{ll}1& \text{if }\{v_i,v_j\}\in E\\ 0& \text{otherwise}\end{array}$$

Properties

---

• If $G$ is an undirected graph, $A$ is symmetric, since $\{v_i,v_j\}\in E$ iff $\{v_j,v_i\}\in E$.
• If $G$ is a directed graph, $a_{ij}=1$ iff the directed edge $(v_i,v_j)$ is in $E$, and $A$ need not be symmetric.
• The $(i,j)$ entry of $A^k$ counts the number of walks of length $k$ from $v_i$ to $v_j$.

References

1. [1]

   “Adjacency matrix”, Wikipedia, Available: https://en.wikipedia.org/wiki/Adjacency_matrix, Accessed: 2026-07-15 ↩

2. [2]

   “Adjacency Matrix”, Wolfram MathWorld, Available: https://mathworld.wolfram.com/AdjacencyMatrix.html, Accessed: 2026-07-15 ↩