3
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ By asymmetric, you mean the automorphism group is trivial? $\endgroup$ Aug 8, 2012 at 18:44
  • $\begingroup$ Yes, the graph has a trivial automorphism group. And yes I'm assuming a connected graph. I edited the question to reflect this. $\endgroup$ Aug 9, 2012 at 6:23
  • $\begingroup$ I'm curious what was the motivation for the question. $\endgroup$ Aug 9, 2012 at 12:42

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ If I entered it correctly into Maple then three of the 12 distinct eigenvalues do have eigenvectors with distinct entries. $\endgroup$ Aug 9, 2012 at 2:21
  • $\begingroup$ I cut and pasted the above matrix into Mathematica and it seems that all eigenvectors have repeated entries. $\endgroup$ Aug 9, 2012 at 3:06
  • $\begingroup$ Ok, I agree.I think I got fooled when Maple took equal but not identically written algebraic integers and evaluated them slightly differently numerically. $\endgroup$ Aug 9, 2012 at 4:55
  • $\begingroup$ 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. $\endgroup$ Aug 9, 2012 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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