[Math] What does the multiplication of incidence matrices mean in terms of graph theory

graph theorymatrices

Let $A$ be the incidence matrix (not adjacency matrix!) of an undirected graph $G=(V,E)$. What does the matrix product $AA^T$ represent in terms of graphs? What about $A^TA$?

Best Answer

The $(i,j)$ element of $AA^T$ is the dot product of rows $i$ and $j$ of $A$, which is simply the number of edges that are incident at both vertex $v_i$ and vertex $v_j$.

  • If $i=j$, and the graph has no loops, it’s $\deg v_i$.
  • If $i=j$, and the graph has $\ell$ loops at vertex $i$, it’s $\deg v_i-\ell$, since a loop is counted only once in the dot product but contributes $2$ to the degree of the vertex.
  • If $i\ne j$, it’s the number of edges between vertices $v_i$ and $v_j$. In particular, if the graph is simple, it’s one if $v_i$ and $v_j$ are adjacent, and $0$ otherwise.
Related Question