Exercise 8.18 in Algebraic Graph Theory by Godsil and Royle

479 Views Asked by At

This is at page 190 of Algebraic Graph Theory by Chris Godsil and Gordon Royle.

Let $\mathbf B$ be the submatrix of the symmetric matrix $\mathbf A$ obtained by deleting the $i$th row and column of $\mathbf A.$

Problem 1: Show that if $\mathbf x$ is an eigenvector for $\mathbf A$ such that $x_i=0$, then the vector $\mathbf y$ we get by deleting the $i$th coordinate from $\mathbf x$ is an eigenvector for $\mathbf B$.

We call $\mathbf y$ the restriction of $\mathbf x$, and $\mathbf x$ the extension of $\mathbf y$.

Now, suppose that $\theta$ is a common eigenvalue of $\mathbf A$ and $\mathbf B$, and that its multiplicity as an eigenvalue of $\mathbf A$ is $m$.

Problem 2: If the multiplicity of $\theta$ as an eigenvalue of $\mathbf B$ is $m-1$, show that each $\theta$-eigenvectors of $\mathbf B$ extends to an eigenvector for $\mathbf A$.

(It also has the third question, but I didn't copy it.)


The first problem is a direct consequence of the definition of the eigenvector that $\mathbf A \mathbf x = \theta \mathbf x$. But I have no idea on how to prove the second problem. How can I prove it?

1

There are 1 best solutions below

2
On BEST ANSWER

Consider the map $P:\Bbb R^n \to \Bbb R^{n-1}$ that deletes the $i$th entry of a vector (that is, take $P$ to be the identity matrix with its $i$th row deleted). Note that $\dim \ker P = 1$.

Consider the restriction of $P$ to the $m$-dimensional $\theta$-eigenspace of $A$. Note that, by part a, the image of this restriction is contained within the $\theta$-eigenspace of $B$. The kernel of the restriction has dimension at most $1$. By the rank-nullity theorem, the image of the restriction is of dimension at least $(m-1)$.

The eigenspace for $B$ contains the image of the restriction above, but it is of dimension $(m-1)$. Thus, the image of the restriction is the entire subspace, which is to say that the restricted map between eigenspaces is onto. Thus, for every eigenvector $x$ of $B$ associated with $\theta$, there is an eigenvector $y$ of $A$ for which $Py = x$.