Timeline for equitable partitions
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 10, 2012 at 19:16 | comment | added | Aaron Meyerowitz | , if some vector in that eigenspace has a non-zero sum over some cell then the projection is a non-zero eigenvector for the appropriate eigenvalue and supported by the partition. At most $c$ of the $d$ eigenvalues can enjoy such an eigenvector. The largest eigenvalue always does. The question was, under what conditions can we be sure that the smallest eigenvalue does? | |
| May 10, 2012 at 19:10 | comment | added | Aaron Meyerowitz | You remember correctly. Suppose that the adjacency matrix $A$ of a graph with $v$ vertices has $d$ eigenvalues and that we have an equitable partition $P$ with $c$ classes of sizes $v_1\cdots v_c$ Then the vectors constant on each class of $P$ form an invariant subspace $T$ under the action of $A$. The projection of a vector onto $T$ assigns the common value $\frac{s_i}{\sqrt{v_i}}$ to the vertices in cell $i$ where $s_i$ is the sum of the entries in that cell. SInce this projection sends an eigenspace into itself (cont.) | |
| May 9, 2012 at 6:11 | comment | added | Brendan McKay | If I remember correctly (for the adjacency matrix), there is an eigenvector that "works" in this sense exactly unless every eigenvector for that eigenvalue sums to zero in each cell of the partition. | |
| May 8, 2012 at 22:37 | comment | added | Aaron Meyerowitz | I mean that the given partition supports an eigenvector for the chosen eigenvalue. In other words: "the" matrix of the graph (whichever one you chose) has an eigenvector for the chosen eigenvalue with the property that each entry depends only on which class of the partition the corresponding vertex belongs to. | |
| May 8, 2012 at 21:54 | comment | added | Felix Goldberg | Aaron, I'm not sure I understand what you mean by saying that a partition "works". | |
| May 8, 2012 at 13:59 | history | answered | Aaron Meyerowitz | CC BY-SA 3.0 |