Find the first eigenvalue and eigenvector of adjacency matrix without calculation of $\rho$

Question

I have a graph $G=(V,E)$ which has the following adjacency matrix: $$ A=\begin{bmatrix}0 & 1 & 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix} $$ The question asks to find the first eigenvalue and eigenvector. The solution contains the $\vec{v}_1=\boldsymbol{1}\in\mathbb{R}^6$ eigenvector and the eigenvalue $\lambda_1=3$. Now I know that: $$ A\boldsymbol{1}=\begin{bmatrix}0 & 1 & 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix}\begin{bmatrix}1\\ 1\\ 1\\ 1\\ 1\\ 1 \end{bmatrix}=\begin{bmatrix}0\cdot1+1\cdot1+1\cdot1+1\cdot1+0\cdot1+0\cdot1\\ 1\cdot1+0\cdot1+1\cdot1+0\cdot1+1\cdot1+0\cdot1\\ 1\cdot1+1\cdot1+0\cdot1+0\cdot1+0\cdot1+1\cdot1\\ 1\cdot1+0\cdot1+0\cdot1+0\cdot1+1\cdot1+1\cdot1\\ 0\cdot1+1\cdot1+0\cdot1+1\cdot1+0\cdot1+1\cdot1\\ 0\cdot1+0\cdot1+1\cdot1+1\cdot1+1\cdot1+0\cdot1 \end{bmatrix}=\begin{bmatrix}3\\ 3\\ 3\\ 3\\ 3\\ 3 \end{bmatrix}=3\cdot\boldsymbol{1} $$ But how did I know that $\boldsymbol{1}$ would be an eigenvector without actually calculating the $\rho=\det(A-\lambda I)$? Is it related to the structure of $A$? Also, even if I found out that $A\boldsymbol{1}=3\cdot\boldsymbol{1}$, why $\lambda_1=3$ and not $\lambda_{i}=3$ for some $i\geq 2$ (why is it the biggest)?

Answer 1

In general, the largest eigenvalue of the adjacency matrix is bounded above by the maximum degree, $\Delta(G)$. To see this, take an arbitrary eigenvector $\mathbf x$ with eigenvalue $\lambda$, and suppose $x_i$ is its largest entry. Then $(A \mathbf x)_i$ (the corresponding entry of $A\mathbf x$ is equal to $\sum_{j \sim i} x_j$, where the sum ranges over all vertices $j$ adjacent to vertex $i$. In particular, this is a sum of at most $\Delta(G)$ values, each of which is at most $x_i$; therefore $(A\mathbf x)_i \le \Delta(G) x_i$. Since by definition $A\mathbf x = \lambda \mathbf x$, we conclude $\lambda \le \Delta(G)$.

For connected graphs $G$, equality is achieved exactly when the graph is a regular graph, which is another case we should be on the lookout for when dealing with eigenvalues. To see this, we think about how $(A\mathbf x)_i \le \Delta(G) x_i$ can become $(A\mathbf x)_i = \Delta(G) x_i$. This requires that the degree of vertex $i$ is in fact $\Delta(G)$, and that all vertices $j$ adjacent to $i$ have $x_j = x_i$: those entries of $\mathbf x$ are also largest entries. Applying the same argument to those entries, we see that the degree of every neighbor of $i$ is also $\Delta(G)$, and that all adjacent entries of $\mathbf x$ are also equal to $x_i$.

Repeating this, by induction we get that all degrees must be equal to $\Delta(G)$, and all components of $\mathbf x$ must be equal to $x_i$. In other words, the graph is a regular graph, and $\mathbf x$ is a multiple of $\mathbf 1$.

(We need connectedness to reach all vertices of $G$ in the induction step. If $G$ is not connected, it's enough to have a connected component of $G$ which is $\Delta(G)$-regular...)

Anyway, in your case, the graph is a $3$-regular graph. This tells us that all eigenvalues are at most $3$, and that the eigenvalue $3$ can be achieved by taking the eigenvector $\mathbf 1$.

Answer 2

As far as I see it, you just have to "see" that $\mathbf 1$ is an eigenvector, which in this case can be seen by the fact that each row of the matrix has $3$ as the sum of its entries/ the sum of all columns is $3 \cdot \mathbf 1$ - taking the sum of all columns is equivalent to multiplying by $\mathbf 1$.

For the question on the biggest eigenvalue I would suggest using Gershgorin circles (see e.g. https://en.wikipedia.org/wiki/Gershgorin_circle_theorem). The statement is that each eigenvalue lies in one of the discs centered at a diagonal element $a_{jj}$ of the matrix with radius $\sum_{i \ne j} |a_{ij}|$. In this case all six diagonal elements are $0$ and for each $j$ the expression $\sum_{i \ne j} |a_{ij}|$ equals $3$. Therefore all eigenvalues lie in the "circle" $[-3,3]$. Since we found out that $3$ is indeed an eigenvalue it automatically has to be the biggest one because of that.