Eigenvectors and partitions of graphs

Question

Let G be an undirected graph with the node set $V$ and the Laplacian matrix $L$. Let $N(v)$ denote the neighbors of a node $v$ and $|N(v)|$ its degree. Then a partition $\pi=(V_1, V_2, \ldots, V_k)$ is almost equitable if it holds that $\forall i \ne j\in\{1,\ldots,k\}$ $\forall v, u\in V_i$ $|N(v)\cap V_j|=|N(u)\cap V_j|$, i. e. that the number of neighbors of a node $v$ in $V_i$ in a different component $V_j$ does not depend on the choice of $v$.

It is known that if $\pi$ is an almost equitable partition of $L$, then (after reordering the vertices appropriately) $L$ has an eigenvector of the form $x=(x_1,x_2,\ldots,x_k)^T$, where $x_i\in {\mathbb{R}}^{|V_i|}$ and $x_i=c_i\mathbf{1}$, $c_i\in \mathbb{R}$.

I had previously asked whether the converse was also true. The converse is not true. For example, the graph with the Laplacian $\begin{pmatrix} 2 & -1 & -1 & 0 & 0 & 0\\\ -1 & 3 & -1 & -1 & 0 & 0\\\ -1 & -1 & 3 & -1 & 0 & 0\\\ 0 & -1 & -1 & 4 & -1 & -1\\\ 0 & 0 & 0 & -1 & 1 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\end{pmatrix}$ has an eigenvector $x=(c_1, c_2, c_2, c_2, c_3, c_3)^T$, which does not correspond with an almost equitable partition. However, if you consider the graph structure, you see that each node in a component $V_i$ has either the same amount of edges to a component $V_j$ or no edges to $V_j$. Just from looking at examples, it seems to always be the case if an eigenvector with repeated entries is present in the graph. However, so far, I have not been able to prove this.

Are there any results about this in the literature? Alas I am not very familiar with algebraic graph theory, but all the literature I could find on Laplacian eigenvectors either did not relate the eigenvector to the graph structure (apart from the Perron ev), or only studied graphs that allowed almost equitable partitions.

Are there necessary and sufficient conditions on the graph structure, such that the graph Laplacian does not have eigenvectors of the form $x$ (apart from $\mathbf{1}$)?

---

My original question has led to a different one. I have edited my original question, hoping that this is the right way to proceed?

Answer 1

final thoughts Let us start with a vector (or just specify the distinct entries) and then try to build a graph. With only 2 distinct entries the partition does need to be almost equitable. I think that it is easy to create high irregularity if some entries are 0. Here is an example cobbled up ad hoc (goals three distinct entries, none being zero. every vertex has neighbors with the other two labels, every label showing two types of vertices): Suppose that the entries are $1$,$2$,$-3$ (how many times each to be determined later). We can ignore edges between vertices with the same label. Suppose $u,v$ are two vertices labeled $1$ , that $u$ has $a$ and $b$ neighbors labeled $2$ and $-3$. Then the eigenvalue is $1(a+b)-2a+3b=-a+4b$ I'll pick $a=1$ and $b=5$ giving eigenvalue $19.$ Then $-c+4d=19$ where $c$ and $d$ are the number of edges from $v$ to vertices labelled $2$ and $-3$ I'll say that some have $c=5$ and $d=6$. Similar calculations and choices lead to this possible situation

• $[p;1 \rightarrow 2^1,-3^5]$ meaning $p$ vertices labeled 1 each having 1 neighbor labeled 2 and 5 labeled -3
• $[q;1 \rightarrow 2^5,-3^6]$
• $[r;2 \rightarrow 1^3,-3^7]$
• $[s,2 \rightarrow 1^8,-3^6]$-
• $[t,-3 \rightarrow 1^{13},2^1]$
• $[u,-3 \rightarrow 1^8,2^5]$ meaning $u$ vertices labelled -3 with 8 and 5 neighbors labeled 1 and 2 respectively

Now we have 6 equations in the (positive integer) variables which will need to be satisfied. Counting in two ways edges with ends labelled 1 and -3 gives $5p+6q=13t+8u$ If my calculations are correct then one possible solution is $[p,q,r,s,t,u]=[21m,4m,3m,4m,5m,8m]$ I do not think that there would be any problem (other than tedium) in assigning edges to make that work (say with m=10 or 20). At any rate, the idea is clear.

later thoughts You rephrase your question as (essentially) "what conditions on a graph are necessary for it to have at least one positive eigenvalue (for the Laplacian) with at least one eigenvector with at least one repeated entry?" I don't think that is exactly what you intended but for that question I don't expect a satisfying answer. However many conditions are sufficient.

In your example of $[a,a,-a,-a,0,0,0,0]$ the corresponding graph does have the equitable partition with 6 singleton cells along with $\lbrace6,8\rbrace$ and that partition does support the eigenvector. Every vertex is adjacent to both or neither of $6,8$ so one also has the eigenvector $[0,0,0,0,0,1,0,-1]$ for $3$ (as $6$ and $8$ are not connected and have degree $3$) This means that every eigenvector for other eigenvalues does have equal entries in positions 6 and 8 (as they will be orthogonal to that one).

It turns out that $\lbrace 1,4\rbrace,\lbrace2,3,6,8\rbrace,\lbrace5\rbrace,\lbrace7\rbrace$ is almost equitable. This means that it supports $4$ eigenvalues with eigenvectors. Leaving out the edges inside each part gives a bipartite graph with those same eigenvalues and eigenvectors and a nice structure.

Any time you have an eigenvalue of multiplicity greater than 1 you can arrange for it to have an eigenvector with some repeated entry by taking the right linear combination of two independent eigenvectors. Your graph has $3$ and $\frac{7 \pm \sqrt{17}}{2}$ as eigenvalues of multiplicity $2$ along with $0$ and $4$ of multiplicity $1$.

Given your comments, your question seems to be better put as: What conditions on a partition of the vertices is necessary for it to support an eigenvector for (a positive eigenvalue of) the Laplacian? Perhaps you wish to add the condition that the eigenvector takes distinct values on distinct cells. There i don't know but I still don't expect much.

earlier I am having trouble editing my previous answer so here are later thoughts.

With regard to the Laplacian Matrix:

• For any graph the all $1$'s vector is an eigenvector of the Laplacian matrix although the partition with one class is only equitable if the graph is regular.

• Consider a graph and an eigenvector $v$ of its Laplacian matrix which has a healthy number of repeated values (perhaps due to an underlying equitable partition) now freely add and delete edges joining vertices with the same value. I claim that for the new graph the vector $v$ will still be an eigenvector for the same eigenvalue although the partition need not be especially nicely behaved.

• If one has an equitable partition into $k$ parts then not only does it have an eigenvector of the form you mention but it has $k$ such eigenvectors (with multiplicity). However the same argument as above shows that you can change the graph by arbitrary changes of edges within each part and have the same eigenvectors for the same eigenvalues.

• Consider a graph with $n$ vertices which has an eigenvalue with multiplicity $m>1$ ( say that $W$ is the space of eigenvectors for that value) then for any $p<m$ vertices the space of vectors which take the same value on those $p$ points (call it $U$) has dimension $n-p+1$ contains a subspace (the intersection of $W$ with $U$) of dimension at least $m-p$ of eigenvectors for that eigenvalue. If the $p$ chosen points do not have the same degree, the partition is not equitable.

• start with a graph and an eigenvector for an eigenvalue $\lambda>0$. Partition the vertices into subsets (preferably, many small ones) each with sum of corresponding entries 0. Now assign to each subset a new vertex joined to all its members and getting the weight 0. The new vector is an eigenvaue for the new matrix for eigenvalue $\lambda+1.$

• If an eigenvector has one or more $0$'s then one can hang off of them any structure of further edges and vertices which all get a value of zero and this gives an eigenvector for the new graph.

With regard to the incidence matrix: I think that my argument in the previous answer does show that a partition into $k$ parts is equitable if and only if it supports $k$ linearly independent eigenvectors.

---

Answer 2

I am going to call the partitions you describe simply equitable (am I missing something?) Here is a graph labelled according to an eigenvector. The red nodes are $+1$ the green are $-1$ and the black are $0$ the corresponding partition is not equitable. The second graph is about the same but seems more clearly a counterexample to your revised question.

Here is what I think is true: A partition with $k$ parts is equitable iff it supports $k$ linearily independent eigenvectors (for the adjacency matrix $A$ or the Laplacian matrix $L$). Here is a rough sketch of a proof for the case of $A$ (which looks ok to me, but check for yourself) .

Consider a graph and a partition of the $n$ vertices into $k$ classes. The characteristic vectors of the classes are $k$ $0-1$ vectors $v_1,v_2,\dots,v_k$ with sum the all $1$'s vector. They span a dimension $k$ subspace $V$ of $\mathbb{R}^n.$

The partition is defined to be equitable if there are $k^2$ constants $c_{ij}$ such that $Av_j=\sum c_{ij}v_i.$ Mure succinctly: if $AV=V.$ Note that $n_ic_{ij}=n_jc_{ji}.$ Thus(?) $\mathbb{R}^k$ has a basis of eigenvectors for the matrix $C=\left(c_{ij}\right)$ . These lift to $k$ vectors in $\mathbb{R}^n$ which are eigenvectors for $A$ and a basis for $V.$

Conversely, if $V$ has a basis which are eigenvectors of $A$ then it follows that $AV=V.$

old answer left to explain comments:

No. A path with 5 vertices has eigenvector $[1,1,0,-1,-1]$ but the partition is not almost equitable.

More generally, take two graphs $G_1$ and $G_3$ both regular of degree $d$. In addition take an arbitrary graph $G_2$ and connect each vertex of $u \in G_2$ to $s\alpha_u$ vertices of $G_1$ and $t\alpha_u$ vertices of $G_3$ where $\alpha_u$ can depend on $u$. Then this partition of $G=G_1 \cup G_2 \cup G_3$ supports an eigenvector (for $d$) with values $t,0$ and $-s$ respectively on $G_1,G_2$ and $G_3$ but the graph can be highly irregular.