Spectral theory of generalized incidence matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T07:49:24Z http://mathoverflow.net/feeds/question/120171 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120171/spectral-theory-of-generalized-incidence-matrices Spectral theory of generalized incidence matrices Anonymous 2013-01-29T02:54:09Z 2013-01-29T02:54:09Z <p>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. </p> <p>Given any matrix $M$, call $M$ an <em>incidence matrix</em> 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$. </p> <p>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. </p> <p>Call $M$ a <em>generalized incidence matrix</em> 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: <a href="http://mathoverflow.net/questions/119798/lower-bound-for-spectral-gap-of-train-track-graphs-on-a-genus-g-surface" rel="nofollow">http://mathoverflow.net/questions/119798/lower-bound-for-spectral-gap-of-train-track-graphs-on-a-genus-g-surface</a> ). <strong>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).</strong> </p> <p><strong>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?</strong></p> <p>Thank you for reading, and any ideas you may have!</p>