Can some one tell me what is the special of product of the incidence matrix and its transpose for an undirected graph ?. I try get product of a incidence matrix and its transpose for an undirected graph with three vertices, two edges but i don't get any clue
[Math] the special of product of the incidence matrix and its transpose for an undirected graph
graph theory
Best Answer
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.