most recent 30 from http://mathoverflow.net 2013-05-22T14:41:50Z http://mathoverflow.net/feeds/question/107629 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107629/a-variation-on-the-theory-of-equitable-partitions-for-graphs Delio Mugnolo 2012-09-19T23:31:50Z 2012-11-01T14:11:04Z

<p>Assume you have a graph with an <a href="http://mathoverflow.net/questions/96858/complexity-of-equitable-partitions" rel="nofollow">equitable partition</a> with respect to cells $V_1,\ldots,V_n$. Accordingly, you can take the cellwise average value of a function on the node set - in other words, the projection of the node space onto the susbpace of cellwise constant functions. Let us call $P$ this projector.</p> <p>Then, it is well-known (see e.g. Bollobas' book, Prop. VIII.3.15; or Brouwer-Haemer's book, §2.3) that there is a matrix $C$ such that $P$ intertwines with $A$ and $C$, i.e., $AP=PC$, where $A$ is the adjacency matrix of the graph; in fact, $C$ can be investigated as the adjacency matrix of a certain auxiliary "quotient" graph, with certain nice connections between the spectra of $A$ and $C$.</p> <p>Now, what I'd like to know is what happens if we consider $(I-P)$ instead of $P$, or - if you prefer - the projector onto the null space of $P$, instead of its range. Is there a matrix D such that $(I-P)$ intertwines with $A$ and $D$? Can $D$ be interpreted as the adjacency matrix of a certain auxiliary graph, again? </p> <p>(If necessary, in the above question you can gladly replace the adjacency matrix by the discrete laplacian, the normalized laplacian, or the signless laplacian).</p>

http://mathoverflow.net/questions/107629/a-variation-on-the-theory-of-equitable-partitions-for-graphs/111158#111158 Chris Godsil 2012-11-01T14:11:04Z 2012-11-01T14:11:04Z

<p>The column space of $I-P$ is $A$-invariant and therefore there is a matrix $D$ such that $A(I-P)=(I-P)D$. The difficulty is that $D$ will generally not be non-negative and so it it less useful to interpret it as a weighted adjacency matrix. Additionally, in practice $C$ is small (which is what makes it useful) and so the size of $D$ will be comparable with that of $A$. In which case we might as well work directly with $A$.</p> <p>On the other hand, if the cells of the partition all have size two, then $D$ is a signed adjacency matrix, and so in this case we can have some fun.</p>