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!

Lower bound for spectral gap of train track graphs on a genus g surface?

2013-01-25T00:23:04Z

Let $S_{g}$ be the genus $g$ closed orientable surface, and let $\tau \subset S_{g}$ be a connected, generic train track (all switches are trivalent). Let $\mathcal{B}$ denote the number of branches and $\mathcal{S}$ the number of switches.

Label the switches from $1$ to $\mathcal{S}$, and the branches from $1$ to $\mathcal{B}$. We can identify $\mathbb{R}^{\mathcal{B}}$ with the set of real-valued weights on the branch set of $\tau$. Then there is a linear map $L_{\tau}:\mathbb{R}^{\mathcal{B}}\rightarrow \mathbb{R}^{\mathcal{S}}$ associated to $\tau$ which is defined by, given $u\in \mathbb{R}^{\mathcal{B}}$, the $j^{th}$ coordinate of $L_{\tau}(u)$ is the sum of the weights at the two incoming branches of the $j^{th}$ switch, minus the weight at the outgoing branch at this switch.

The map is defined so that the non-negative vectors in the kernel are precisely the transverse measures on $\tau$.

My question is: What is a lower bound (as a function of $g$) for the smallest, nonzero eigenvalue of $(L_{\tau}L_{\tau}^{T})$?

Remark (1): Such a bound exists, since there are only finitely many homeomorphism types of train tracks on $S_{g}$, and therefore only finitely many such linear maps.

Remark (2): Technically, I'm only interested in the case when $\tau$ is large, i.e., $S_{g}\setminus \tau$ is simple connected.

Remark (3): Thinking of $\tau$ as a graph, $L_{\tau}$ is the oriented edge-vertex matrix, so what I think I am asking for is a lower bound for the spectral gap of such a graph. However, this graph is not simplicial. It may have loops and double edges so there will be more than one zero eigenvalue, so maybe "spectral gap" is not technically the correct term; it's really the smallest nonzero eigenvalue that I'm interested in. Something like Cheeger's inequality might work, but again I'm not sure how to phrase it in the case of non-simple graphs.

Thank you for reading! Any help would be greatly appreciated!

User anonymous - MathOverflow

Spectral theory of generalized incidence matrices

Lower bound for spectral gap of train track graphs on a genus g surface?