Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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^T=(x_1^T,x_2^T,\ldots,x_k^T)^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 on 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}$)?

share|improve this question
    
For those who are wondering, it seems that an equitable partition is one for which the condition also holds when $i=j$ (so that the parts induce regular subgraphs). –  Ben Barber Feb 21 '13 at 11:00

3 Answers 3

up vote 1 down vote accepted

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.


share|improve this answer
1  
We can form the characteristic matrix of a partition - the matrix whose columns are the characteristic vectors of the cells of the partition. The partition is equitable if and only if its column space is invariant under the adjacency matrix. It is almost equitable if it's invariant under the Laplacian. Since a subspace is invariant under a symmetric real matrix if and only if it has a basis of eigenvectors of the matrix, your claim holds. –  Chris Godsil Nov 7 '11 at 5:07
    
I was uncertain what to say because there seems to be a mild ambiguity with the definitions. Does the definition of almost equitable given in the question assume that $i \ne j?$ I suppose that would correspond to the Laplacian rather than the Adjacency matrix and explain the "almost." Also: consider the all ones vector $j$. It is an eigenvector of the Laplacian but the subspace with basis $\lbrace j \rbrace$ is not invariant under the Laplacian. –  Aaron Meyerowitz Nov 7 '11 at 15:48
1  
The definition of almost equitable should have i≠j. Cardoso, Delorme and Rama have a paper ``Laplacian eigenvectors and eigenvalues and almost equitable partitions'' and there is a clearly stated definition there. For regular graphs, almost equitable and equitable mean the same thing. I'd have said that the span of the all-ones vector is Laplacian invariant; the partition with one cell is always an almost equitable partition –  Chris Godsil Nov 9 '11 at 1:18
    
The paper by Cardoso et al. motivated my original question. They show that a sufficient condition for the existence of such vectors is that the graph has an almost equitable partition. I am looking for a necessary condition. Consider the Laplacian $\begin{pmatrix}3&-1&-1&0&0&0&-1&0\\-1&4&0&0&-1&-1&0&-1\\-1&0&2&0&-1&0&0&0\\0&0&0&3‌​&0&-1&-1&-1\\0&-1&-1&0&4&-1&0&-1\\0&-1&0&-1&-1&3&0&0\\-1&0&0&-1&0&0&2&0\\0&-1&0&-1&-1‌​&0&0&3\end{pmatrix}$, one of its eigenvectors is given by $(a,a,-a,-a,0,0,0,0)$, with eigenvalue 3 (of multiplicity 2). But the partition implied by this is not almost equitable. –  Anna Nov 9 '11 at 11:43

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.

alt text alt text

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.

share|improve this answer
    
Aaron, I think your counter-examples are computed with the adjacency matrix. The Laplacian has the eigenvectors of form $(c1,c2,c3,c2,c1)$, and that is indeed an almost equitable partition. I haven't been able to construct a counter-example with your second suggestion either. However, neither can I find proof for my assumption (myself or in the literature). Assuming that my assumption is wrong, what information do recurring eigenvector elements of the Laplaican contain? If an eigenvector is of the form $x$ as above, what information does it contain about the graph? –  Anna Nov 3 '11 at 10:37
    
You are right about my example. I am used to regular graphs where the Laplacian and incidence matrix have the same eigenvectors. I erred in trying to make it simple .I'll think about it later. I believe that the partitions you describe are called equitable (rather than merely almost equitable).You might say that for an (almost) equitable partition it can happen that there are eigenvectors which happen to take the same value on different parts so maybe a refinement of the partition induced by an eigenvector is equitable. But the partition into one vertex sets is equitable so that is true. –  Aaron Meyerowitz Nov 3 '11 at 22:19

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

share|improve this answer
    
It is ot clear to me what your question is now. –  Chris Godsil Nov 5 '11 at 13:56
    
Given an undirected graph, what are the necessary conditions that its Laplacian has an eigenvector with $k<n$ distinct entries corresponding to a nonzero eigenvalue. –  Anna Nov 9 '11 at 11:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.