Different definitions of Incidence Matrix of a graph?

103 Views Asked by At

Recently, I have been trying to learn some graph theory and matroids. I read from one source that you can build a vector matroid $M[A]$ of a graph $G$, by letting $A$ be the incidence matrix, but the $A$ was defined as a matrix so that each vertex of the graph has a row and each edge of the graph has a column, and there is a $1$ in $A_{i,j}$ if the edge $j$ is connecting vertex $i$. Otherwise, there is a $0$.

This is not how I first learned about incidence matrices: in the first version, we fix an orientation and depending on if the vertex is receiving an edge or not, there will be a $-1$ or $1$. If the edge is not connecting the vertex there will be a $0$ in that spot.

Is there a way to consolidate these two definitions? Do they mean the same thing? The way the author defined it is not as nice, as you do not get the laplacian when you multiply by the transpose, but in the first definition of the incidence matrix, this was the case. Is there anyway I can get the laplacian by using the definition of the author?

1

There are 1 best solutions below

0
On

These two matrices do not necessarily define the same matroid. A simple counterexample is the cycle graph $C_3$. However, over a field of characteristic $2$ (in which case $-1 \equiv 1$) they both define the graphic matroid of $G$. In fact, graphic matroids are representable over every field.

If you use the signless incidence matrix and multiply it by its transpose you will get the signless Laplacian. You can easily read out the regular Laplacian by changing the sign of the elements that are not on the main diagonal.