Skip to main content
1 of 2
alex
  • 976
  • 4
  • 14
  • 26

Here is a simple proof.

Suppose $Ax = x$. Consider the entry of $x$ with the largest absolute value; lets use $x_k$ to denote this entry (e.g. if $x=[1,2,-4,3]^T$, then $k=3, x_k=-4$). Consider the $k$'th row of the equation $Ax=x$; it's telling you that $x_k$ is a convex combination of the $x_i$'s of its neighbors $i$ in the graph $G$. This immediately implies that $x_k=x_i$ for all neighbors $i$ of $k$ in $G$.

Now you iterate this argument and apply it to each neighbor $i$ of $k$. Using connectivity of $G$, eventually you get the conclusion that every $x$ equals $x_k$. Thus the only solutions to $Ax=x$ are multiples of the all ones vector.

Observe that some of the conditions you imposed were not used: the above proof did not use the fact that $A$ is symmetric or that the graph is regular.

alex
  • 976
  • 4
  • 14
  • 26