1
$\begingroup$

Assume you have a graph with an equitable partition 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.

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$.

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?

(If necessary, in the above question you can gladly replace the adjacency matrix by the discrete laplacian, the normalized laplacian, or the signless laplacian).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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$.

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well, your first objection is in fact very relevant. Concerning the second one, that's exactly the advantage: one may hope to interpret $D$ as another adjacency matrix, which in the best case scenario could be again decomposed, and so on and so forth, perhaps iteratively. A natural motivation for this kind construction is given by an infinite binary tree, taken with the equitable partition given by their automorphisms. Then you can begin factoring out radial symmetric functions and get something which is isomorphic to a function on an subtree, and so on - forever. $\endgroup$
    – Delio Mugnolo
    Commented Feb 20, 2013 at 12:25
  • $\begingroup$ I have just seen that the end of Chapter 4 in the old book by Cvetkovic-Doob-Sachs is devoted to exactly this question. An algorithm for factoring (certain classes of) graphs is also presented. $\endgroup$
    – Delio Mugnolo
    Commented Dec 9, 2014 at 13:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .