The Node-Arc Incidence Matrix

Let $G = (N, \mathcal{A})$ be a directed graph with $m = |N|$ nodes and $n = |\mathcal{A}|$ arcs. The node-arc incidence matrix of $G$ is the $m \times n$ matrix $A$ whose rows are indexed by the nodes and whose columns are indexed by the arcs.

For each arc $(i, j) \in \mathcal{A}$ (directed from $i$ to $j$), the corresponding column of $A$ is defined by

$$A_{k,\,(i,j)} = \begin{cases} +1 & \text{if } k = i, \\ -1 & \text{if } k = j, \\ \phantom{-}0 & \text{otherwise.}\end{cases}$$

In other words, each column has a $+1$ in the row of its tail node, a $-1$ in the row of its head node, and zeros everywhere else.

For example, consider the directed graph on three nodes with arcs $(1,2)$ and $(2,3)$. We build the matrix column by column:

• Arc $(1,2)$: place $+1$ in row $1$ and $-1$ in row $2$.
• Arc $(2,3)$: place $+1$ in row $2$ and $-1$ in row $3$.

This gives

$$A = \begin{bmatrix} \phantom{-}1 & \phantom{-}0 \\ -1 & \phantom{-}1 \\ \phantom{-}0 & -1 \end{bmatrix}.$$