8
$\begingroup$

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

$\endgroup$

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

The product of incidence matrix Q by its transpose is known as Laplacian matrix. The Laplacian matrix has many properties linked to graphs.

The Laplacian Matrix can be obtained with

L=D-A

with D diagonal matrix of degree/valences of nodes, and A the adjacency matrix.

$\endgroup$
2
  • $\begingroup$ Just for the sake of posterity, I'm pretty sure this cannot be true. In particular, the incidence matrix has only nonnegative entries, so so much the product of it with its transpose, while the Laplacian matrix of a graph with at least one edge has a negative component. Notice also that the Laplacian does not fit the description given by Hagen above. $\endgroup$ Commented Sep 16, 2021 at 3:16
  • $\begingroup$ @CadeReinberger It is true. If you use oriented incidence matrix $B$, the $L=B^TB$. Read more at: mbernste.github.io/posts/laplacian_matrix $\endgroup$
    – Blade
    Commented Sep 4, 2022 at 21:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .