Exercise 8.18 in Algebraic Graph Theory by Godsil and Royle

Question

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?

Does multiplicity refer to algebraic multiplicity or geometric multiplicity? — angryavian, Jan 01 '17 at 00:19
@angryavian It doesn't matter because they are the same in symmetric matrices. http://math.stackexchange.com/a/393165/19906 — user19906, Jan 01 '17 at 00:24

score 3 · Accepted Answer · answered Jan 01 '17 at 16:49

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

@ChrisGodsil glad to have your endorsement! – Ben Grossmann Jan 02 '17 at 00:01 — Ben Grossmann, Jan 02 '17 at 00:01

Exercise 8.18 in Algebraic Graph Theory by Godsil and Royle

1 Answers1

Linked