Multigraph bijections and matrices

For $R\subseteq A\times B$ on finite ordered sets, $M[a,b]=1$ if $(a,b)\in R$ and 0 otherwise. State the row order A and column order B.

An entry represents a particular ordered pair. A multigraph adjacency matrix may count parallel edges and therefore have entries greater than 1; that is a different convention.

A loop has the same endpoint twice. Parallel edges are distinct edges with the same endpoints. For an undirected multigraph, retain each edge’s identity and endpoint pair.

A simple undirected graph excludes both loops and parallel edges. The degree convention does not by itself specify how a matrix should record loops; state the matrix convention explicitly.

For a finite loop-free undirected multigraph with fixed vertex order, $M_ij$ is the number of edges between vertices i and j. The diagonal is zero and M is symmetric.

For a simple graph entries are 0 or 1. A directed graph uses a row-to-column direction and need not give a symmetric matrix. Loop-diagonal conventions must be stated separately.

For the adjacency matrix of a finite simple graph, $(M^{2})_ij$ counts walks of length two from i to j, summed over possible intermediate vertices k.

These are walks, not necessarily paths: returning to a previous vertex is allowed. More generally $(M^r)_ij$ counts length-r walks for nonnegative integer r; $M^{0}$ is the identity matrix.

For a vertex bijection f from G to H, put $P_uv=1$ when $f(u)=v$ and 0 otherwise, with rows in G order and columns in H order. For the same adjacency convention, $M_H=P$ᵀ$M_GP$ expresses preserved adjacency.

Pᵀ swaps P’s row and column indices. Right multiplication reorders columns and left multiplication by Pᵀ reorders rows. Reversing the convention for P changes the displayed identity; the matrix does not name an edge bijection.