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 '12 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 '12 at 6:23
  • $\begingroup$ I'm curious what was the motivation for the question. $\endgroup$ Aug 9 '12 at 12:42
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 '12 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 '12 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 '12 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 '12 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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