# Eigen values of a block diagonal matrix of a specific form (resulting from an adjacency matrix)

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$$ ?

• 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. Oct 8, 2023 at 8:51

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.