Encoding a Network in a Matrix
A network can be described by listing its vertices and the edges that connect them. An adjacency matrix organizes that information in a fixed array: each entry records the edges between one ordered pair of vertices. The order matters. In a directed network, exchanging the row and column indices reverses the direction being recorded, so the convention must be stated before reading or constructing the matrix.
Consider a finite directed network whose vertices are ordered as \(v_1,\dots,v_n\). Each edge has a source, a target, and a real weight. An edge from \(v_i\) to \(v_j\) is directed from \(v_i\) toward \(v_j\). A loop has the same source and target. Multiple edges may have the same source and target; these are called parallel edges. In an unweighted network, each edge is counted as having weight \(1\).
Thus row \(i\) records the edges leaving \(v_i\), while column \(j\) records the edges entering \(v_j\). For a simple directed network, in which there is at most one edge from any vertex to any other and there are no edge weights beyond \(1\), the entries are either \(0\) or \(1\). More general networks can have entries that are larger than \(1\), negative, or non-integer, depending on the edge weights.
A matrix entry records an aggregate, not necessarily every detail of an edge list. In particular, parallel-edge weights are added together. A loop contributes to the diagonal entry for its vertex. If there are several loops there, their weights are added too. Opposite-signed weights can cancel, so an entry of \(0\) does not always mean that there are no edges.
Translating an Edge List
Worked Example: An Unweighted Directed Network
Use the vertex order \(v_1,v_2,v_3\), and suppose the directed edges are \(v_1\to v_2\), \(v_1\to v_3\), \(v_2\to v_1\), \(v_2\to v_3\), \(v_3\to v_2\), and \(v_3\to v_3\). Construct the adjacency matrix using the source-row, target-column convention.
For each listed edge \(v_i\to v_j\), add \(1\) to entry \(a_{ij}\). The edge \(v_1\to v_2\) contributes to \(a_{12}\), and \(v_1\to v_3\) contributes to \(a_{13}\). The edges leaving \(v_2\) contribute to \(a_{21}\) and \(a_{23}\). The edges leaving \(v_3\) contribute to \(a_{32}\) and \(a_{33}\). No other ordered pairs have edges, so their entries are \(0\).
Check: Reading across row 1 gives edges from \(v_1\) to \(v_2\) and \(v_3\); row 2 gives edges from \(v_2\) to \(v_1\) and \(v_3\); row 3 gives edges from \(v_3\) to \(v_2\) and \(v_3\). These are exactly the six listed edges. In particular, \(a_{33}=1\) records the loop at \(v_3\).
The edge list can be recovered from the entries in a simple network with no parallel edges: a nonzero entry \(a_{ij}\) indicates an edge from \(v_i\) to \(v_j\). In a weighted network, the entry also gives its weight when there is just one such edge. With parallel edges, the matrix gives their total weight, rather than the individual weights.
Worked Example: Weights, Parallel Edges, and Loops
Use the order \(v_1,v_2,v_3,v_4\). Suppose the edge list is: two edges from \(v_1\) to \(v_2\), with weights \(2\) and \(-1\); an edge from \(v_1\) to \(v_3\) with weight \(3\); an edge from \(v_2\) to \(v_1\) with weight \(4\); an edge from \(v_2\) to \(v_4\) with weight \(-2\); two loops at \(v_3\), with weights \(5\) and \(-5\); an edge from \(v_4\) to \(v_3\) with weight \(\tfrac12\); and a loop at \(v_4\) with weight \(-3\). Find \(\mathbf{A}\).
The parallel edges from \(v_1\) to \(v_2\) give \(a_{12}=2+(-1)=1\). The edge from \(v_1\) to \(v_3\) gives \(a_{13}=3\). The edges from \(v_2\) give \(a_{21}=4\) and \(a_{24}=-2\). The two loops at \(v_3\) give \(a_{33}=5+(-5)=0\). The edge from \(v_4\) to \(v_3\) gives \(a_{43}=\tfrac12\), and the loop at \(v_4\) gives \(a_{44}=-3\). All unlisted entries are \(0\), so
Check: Row 1 contains the aggregate weights \(1\) and \(3\) of the edges leaving \(v_1\); row 2 contains \(4\) and \(-2\); row 3 is zero because the two loop weights cancel; row 4 contains \(\tfrac12\) and \(-3\). The diagonal entry \(a_{33}=0\) does not mean there are no loops at \(v_3\): their total weight is zero. Each entry agrees with the sum of the edge weights for its ordered pair.
Changing the Direction Convention
Some authors and applications use the opposite convention: row \(i\), column \(j\) records edges from \(v_j\) to \(v_i\). If \(\mathbf{B}\) is the matrix under that convention for the same network, then \(b_{ij}=a_{ji}\). By the definition of transpose, this says \(\mathbf{B}=\mathbf{A}^{\top}\). Neither convention is inherently wrong; using one without saying so can make a correctly transcribed network appear to have all its arrows reversed.
Proof. Fix any ordered pair of vertices \(v_i,v_j\). In the reversed network, the edges from \(v_i\) to \(v_j\) are exactly the original edges from \(v_j\) to \(v_i\), with the same weights. Therefore, the reversed network’s entry in row \(i\), column \(j\) is the original total weight from \(v_j\) to \(v_i\), which is \(a_{ji}\). Since this holds for every \(i,j\), the reversed network’s matrix has entries \(a_{ji}\) and is \(\mathbf{A}^{\top}\). For \(i=j\), reversing a loop leaves its source and target unchanged, and the diagonal entry remains \(a_{ii}\), as the transpose formula also requires. \(\square\)
This result gives a direct convention check. For the first worked example, the edge \(v_1\to v_2\) appears at \(a_{12}\). In the reversed network it becomes \(v_2\to v_1\), which appears at position \((2,1)\) in \(\mathbf{A}^{\top}\). Diagonal entries do not move, because reversing a loop does not change its vertex.
Worked Example: An Undirected Weighted Network
Suppose three vertices are connected by undirected weighted edges: weight \(2\) between \(v_1\) and \(v_2\), weight \(-1\) between \(v_1\) and \(v_3\), and weight \(4\) between \(v_2\) and \(v_3\). There is also a loop at \(v_2\) with weight \(3\). Represent each non-loop undirected edge as an edge in both directions with the same weight, and include the loop once. Find the adjacency matrix.
The edge of weight \(2\) contributes \(a_{12}=2\) and \(a_{21}=2\). The edge of weight \(-1\) contributes \(a_{13}=-1\) and \(a_{31}=-1\). The edge of weight \(4\) contributes \(a_{23}=4\) and \(a_{32}=4\). The loop contributes \(a_{22}=3\). There are no other edges, so
Check: The entries \(a_{12}\) and \(a_{21}\) both equal \(2\); \(a_{13}\) and \(a_{31}\) both equal \(-1\); and \(a_{23}\) and \(a_{32}\) both equal \(4\). The diagonal entry \(a_{22}=3\) records the loop. Thus \(\mathbf{A}=\mathbf{A}^{\top}\), as expected when every non-loop edge is represented in both directions with the same weight.
For an undirected weighted network represented this way, the matrix is symmetric: \(a_{ij}=a_{ji}\). This equality describes the aggregate weights in the two directions. If a network has parallel edges, symmetry of the matrix alone says the total weight in each direction agrees; it does not identify the individual edges that contributed to those totals.
What Row and Column Totals Record
Adding the entries across row \(i\) gives the total weight of all edges leaving \(v_i\). Adding down column \(j\) gives the total weight of all edges entering \(v_j\). These totals can be useful summaries, but with signed weights they can be zero even when edges are present. They are sums of weights, not counts of edges unless the network is unweighted.
Proof. By definition, \(a_{ij}\) is the sum of the weights of all edges from \(v_i\) to \(v_j\). As \(j\) runs from \(1\) to \(n\), every edge leaving \(v_i\) occurs in exactly one of these sums, namely the sum for its target vertex. The targets include every vertex, including \(v_i\) itself for loops. Therefore, \(\sum_{j=1}^{n}a_{ij}\) sums the weights of all edges leaving \(v_i\). For a fixed target \(v_j\), as \(i\) runs from \(1\) to \(n\), every edge entering \(v_j\) occurs exactly once, in the sum for its source vertex. Thus \(\sum_{i=1}^{n}a_{ij}\) is the total weight entering \(v_j\). \(\square\)
Common Mistakes and Information Limits
Reversing row and column indices. Under the convention used here, the edge \(v_1\to v_2\) goes in position \((1,2)\), not \((2,1)\). A wrong calculation might place that edge at \(a_{21}=1\), giving the matrix \(\begin{bmatrix}0&0\\1&0\end{bmatrix}\) for a network with only \(v_1\to v_2\). That matrix instead represents \(v_2\to v_1\) under the source-row, target-column convention. The correction is \(\begin{bmatrix}0&1\\0&0\end{bmatrix}\): first choose the source row, then the target column.
Reading a diagonal zero as “no loop.” A diagonal entry is the sum of the weights of all loops at that vertex. For example, loops at \(v_1\) with weights \(1\) and \(-1\) give \(a_{11}=1+(-1)=0\), despite there being two loops. A single loop with nonzero weight and no other loops at that vertex does give a nonzero diagonal entry, but in general it is the aggregate loop weight that the diagonal records.
Assuming the matrix preserves the whole edge list. If two parallel edges have weights \(2\) and \(5\), their entry is \(a_{ij}=7\). The same entry could come from one edge of weight \(7\). The adjacency matrix alone does not distinguish these edge lists. Likewise, an entry of zero can result from no edges or from cancellation of nonzero weights. Keep the edge list or other network information if those distinctions matter.
Check Your Understanding
For each question, use the source-row, target-column convention and state how you checked the entries.
- For vertices \(v_1,v_2\), the only edges are \(v_1\to v_2\) with weight \(3\) and \(v_2\to v_1\) with weight \(-1\). What is the adjacency matrix?
- Two loops at \(v_2\) have weights \(4\) and \(-4\). What is the diagonal entry \(a_{22}\), and what does it tell you about the loops?
- If \(\mathbf{A}\) is the adjacency matrix of a directed weighted network, what matrix represents the network with every edge reversed and every weight unchanged?
- In an unweighted directed network, what does \(a_{ij}=2\) mean when parallel edges are allowed?
- For an undirected weighted network represented by equal-weight edges in both directions, why must the adjacency matrix be symmetric?
