Spectral theory of generalized incidence matrices

2013-01-29T02:54:09Z

Given a finite graph $G=(V,E)$, assign orientations to each edge arbitrarily. This is equivalent to assigning one end of each edge a $+1$, and the other end a $-1$. Then the oriented incidence matrix $M$ associated with the particular chosen orientation of edges is the $|E|\times |V|$ matrix whose $(i,j)$ entry is $1$ if the positive end of the $i^{th}$ edge is incident to the $j^{th}$ vertex, $-1$ if the negative end of the $i^{th}$ edge is incident to the $j^{th}$ vertex, and $0$ otherwise.

Given any matrix $M$, call $M$ an incidence matrix if there exists a graph $G$ and a choice of orientations for its edges such that the corresponding incidence matrix is $M$. Then, regardless of the chosen orientations, the Laplacian matrix $\mathcal{L}(G)$ for $G$ is equal to $M^{T}M$. Thus, a wealth of information is known about the spectral theory of any incidence matrix, since we can relate its singular values to graph theoretic properties of the corresponding $G$.

I'm interested in the following generalization of this: Suppose $G=(V,E)$ is a (not necessarily simple) graph $G$, and to either end of each edge, we can assign a $+1$ or a $-1$, independently. That is, unlike in the above setting, it is possible for both ends of an edge to be positive, or both ends negative. Then we can still define a sort of incidence matrix $M$ that captures this structure, whose $(i,j)$ entry is $1$ if a single positive end of the $i^{th}$ edge is incident to the $j^{th}$ vertex (resp. $-1$ if a single negative end is incident to the $j^{th}$ vertex). Note that it is possible to have values of $\pm 2$ as well since we are allowing loops.

Call $M$ a generalized incidence matrix if it is obtained as above for some graph $G$. For instance, one obtains such matrices when considering train tracks on surfaces (see my related question in the geometric topology tag for more details: http://mathoverflow.net/questions/119798/lower-bound-for-spectral-gap-of-train-track-graphs-on-a-genus-g-surface ). In the setting of train tracks, the degree of every vertex is $3$, and only non-zero values of $\pm1$ or $2$ are allowed in the generalized incidence matrix (that is, it is impossible for an edge to form a loop, and for both of its ends to be negative).

My question is: What, if anything, can be said about the singular values of such a generalized incidence matrix $M$? Specifically, are there known lower bounds on the smallest, non-zero eigenvalue of $M^{T}M$ in terms of graph theoretic properties of $G$? What about in the special case of such matrices arising from train tracks?

Thank you for reading, and any ideas you may have!

Spectral theory of generalized incidence matrices - MathOverflow

Spectral theory of generalized incidence matrices