I’m reading a textbook about graph theory and its complications ; I just read about Incidence matrix of a graph ; one of the book’s questions which I couldn’t answer was :” What happen when we multiple an Incidence matrix with its transpose (and reverse)?”

$$I(G) I(G)^T$$ And

$$I(G)^T I(G)$$

I know how to find an incidence matrix of a graph and how to transpose a matrix . But how can we answer this question for all possible matrixes? Is it enough to pose an example and solve this question? Can we generalize the answer of a specific matrix for every single matrix ?

The book also mentioned that the answer is a particular kind of matrix because of the shape of it. I can really appreciate a hint on this.

What is Incedence matrix of a graph ? https://en.m.wikipedia.org/wiki/Incidence_matrix

  • $\begingroup$ What is an occurrence matrix? I can't find anything on this by Googling. $\endgroup$
    – saulspatz
    Commented May 5, 2020 at 6:40
  • 1
    $\begingroup$ @saulspatz sorry I’m reading this book in persian and I mistranslate it . It’s called Incidence matrix of a graph . $\endgroup$ Commented May 5, 2020 at 6:47
  • $\begingroup$ No apology is necessary. $\endgroup$
    – saulspatz
    Commented May 5, 2020 at 6:50
  • $\begingroup$ I really suggest that you start by doing an example for some small graphs and see what you get. That may give you an idea what the answer is, and then you can try to prove it. Notice that if the graph has $n$ vertices and $m$ edges, then $T$ is $n\times m$, $I^T$ is $m\times n$ so $T I^T$ is $n\times n$. Similarly, $I^T I$ is $m\times m$. $\endgroup$
    – saulspatz
    Commented May 5, 2020 at 6:55
  • $\begingroup$ The question is a bit vague. Clearly, both $I(G)I(G)^T$ and $I(G)^TI(G)$ are Gramian matrices and hence they are always positive semidefinite. If $G$ is a simple digraph, $I(G)I(G)^T$ is also the graph Laplacian matrix of $G$. $\endgroup$
    – user1551
    Commented May 5, 2020 at 9:32


You must log in to answer this question.

Browse other questions tagged .