The question is as framed below

Let G be a graph on $p$ vertices. Let the eigen values be $\lambda_1,...,\lambda_n$. Create a new graph G' from G as follows. Corresponding to each vertex $v$ of G, add a new vertex $v{'}$ such that $v'$ has degree 1 and is connected via an edge to $v$. In all, the new graph G' has $2p$ vertices with $p$ number of edges more than that in $G$. Show that the eigen values of G' are $$\frac{\lambda_i\pm\sqrt{\lambda_i^2+4}}{2}$$

This question is from algebraic combinatorics by Stanley. This is related to number of closed walks of length $l$ but the hint says that an algebraic proof is quicker and better and hence I am trying to find one.

Ordering the vertices as $\{v_1,v_2,...,v_p,v_1',...,v_p'\}$, we get that the adjacency matrix is of the form $$\begin{bmatrix} A & I \\ I & 0 \end{bmatrix}$$ where all matrices in the block matrix are of size $p\times p$ and $A$ is the adjacency matrix of the original graph G

To get the eigen values of this, we use $$det\begin{bmatrix}A&B\\C&D\end{bmatrix}=det(AD)-det(CB)$$ because $A$ and $C$ commute

Thus, we end up with, $$x^p det(A-xI)=1$$ where $x$ is the eigen value of the bigger block matrix.

After this I am stuck. How do I relate $x$ and $\lambda$ ?

  • $\begingroup$ No! You can only get $\det\begin{pmatrix}A&B\\C&D\end{pmatrix}=\det(AD-CB)$ from $AC=CA$. You can easily see $\det(AD-CB)\neq\det(AD)-\det(CB)$ in general. $\endgroup$ Oct 8, 2023 at 8:51

1 Answer 1


Let $(v,w)'$ be an eigenvector of the extended matrix with eigenvalue $\mu$. That is, $$ \begin{bmatrix} A & I \\ I & 0\end{bmatrix} \begin{bmatrix} v \\ w\end{bmatrix} = (Av + w, v)' = \mu (v,w)'$$ Then \begin{cases} Av + w = \mu v \\ v = \mu w. \end{cases}

Substituting $w = v/\mu$ into the first equation

$$ Av + v/\mu = \mu v \iff Av = (\mu - 1/\mu) v$$

so $ \mu - 1/\mu = \lambda$ where $\lambda$ is an eigenvalue of $A$. Solving this equation for $\mu$ gives the desired equation.

Note that this only proves that if an eigenvalue for $G'$ exists then it has the desired form. Therefore there is still a little work to do in order to obtain a full proof of the statement.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .