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 asymmetric connected graph. Then is it always the case that at least one of the eigenvectors of its adjacency matrix $A$ consists entirely of distinct entries?

Thanks!

share|improve this question
1  
By asymmetric, you mean the automorphism group is trivial? –  Douglas Zare Aug 8 '12 at 18:44
    
Yes, the graph has a trivial automorphism group. And yes I'm assuming a connected graph. I edited the question to reflect this. –  Alexander Farrugia Aug 9 '12 at 6:23
    
I'm curious what was the motivation for the question. –  Felix Goldberg Aug 9 '12 at 12:42

1 Answer 1

up vote 5 down vote accepted

I think the answer is no. Take the Frucht Graph, the simplest nontrivial asymmetric graph. Its adjacency matrix is

\begin{equation*} \left( \begin{array}{cccccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\\\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\\\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \end{array} \right) \end{equation*}

none of whose eigenvectors seems to have distinct entries.

share|improve this answer
    
If I entered it correctly into Maple then three of the 12 distinct eigenvalues do have eigenvectors with distinct entries. –  Aaron Meyerowitz Aug 9 '12 at 2:21
    
I cut and pasted the above matrix into Mathematica and it seems that all eigenvectors have repeated entries. –  Douglas Zare Aug 9 '12 at 3:06
    
Ok, I agree.I think I got fooled when Maple took equal but not identically written algebraic integers and evaluated them slightly differently numerically. –  Aaron Meyerowitz Aug 9 '12 at 4:55
    
Funny that I had checked the Frucht graph before asking this question and hadn't noticed that all eigenvectors' entries were not distinct. Well spotted. –  Alexander Farrugia Aug 9 '12 at 6:29

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.