The $i,j$ entry of this matrix product is $$\tag1b_{i,j}=\sum_k a_{i,k}a^T_{k,j}=\sum_ka_{i,k}a_{j,k}.$$ The product $a_{i,k}a_{j,k}$ is $1$ if vertices $i$ and $j$ are both incident with edge $k$, and $0$ otherwise. Thus for $i\ne j$, the entry $b_{i,j}$ counts the number of edges from vertex $i$ to vertex $j$ (so for simple graphs, $b_{i,j}$ is $1$ or $0$, depending on whether there is an edge between the two vertices or not). For $i=j$ something different happens: each edge having vertex $i$ as one of its endpoints contributes $1$ to the sum in $(1)$, hence we see that $b_{i,i}=\rho(i)$ is the degree of vertex $i$.
Note that one needs to be careful: The details depend on how the incidence matrix is defined (does $a_{i,j}$ denote the incidence of vertex $i$ with edge $j$ or that of edge $i$ with vertex $j$?) and likewise whether one computes $AA^T$ or $A^TA$. When doing it "wrong", one obtains that $b_{i,j}$ tells us whether edges $i$ and $j$ have an endpoint in common and $b_{i,i}=2$ for the diagonal entries - a much less interesting result.
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.
Best Answer
Because then one may apply matrix theoretical tools to graph theory problems. One area where it is useful is when you consider flows on a graph, e.g. the flow of current on an electrical circuit and the associated potentials.