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!
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ By asymmetric, you mean the automorphism group is trivial? $\endgroup$– Douglas ZareCommented 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$– baronbrixiusCommented Aug 9, 2012 at 6:23
-
$\begingroup$ I'm curious what was the motivation for the question. $\endgroup$– Felix GoldbergCommented Aug 9, 2012 at 12:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ If I entered it correctly into Maple then three of the 12 distinct eigenvalues do have eigenvectors with distinct entries. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented Aug 9, 2012 at 6:29