What does the multiplication of incidence matrices mean in terms of graph theory? 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$?
 A: 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.

A: Suppose $G$ is a graph with $n$ vertices.
If instead you make A the "signed incidence matrix" (arbitrarily orient the edges of $G$ and put 1 as the $ij^{th}$ entry if there is an edge from $v_i$ to $v_j$. Put $-1$ as the $ij^{th}$ entry if there is an edge from $v_j$ to $v_i$.), then the matrix $L=AA^t$ is called the "Laplacian" of $G$. The laplacian has cool properties. 
For instance, rank($L)=n- \# \{\textrm{connected components of } G\}$.
If $G$ is connected, then $det(\tilde{L}) = \#\{\textrm{ spanning trees of } G\}$. Where $\tilde{L}$ is a matrix obtained from $L$ by deleting the $i^{th}$ row and $j^{th}$ column of $L$ for any $i,j$!
