How to understand eigenvalue equation from inner product point of view?

Question

In equation (14.4) page 429 of scholkopf's Learning with Kernels book, it states that the eigenvalue equation $\lambda v = C v$ is equivalent to $\lambda \langle x_i, v \rangle = \langle x_i, C v \rangle$ for all $i = 1, \dots, m$ where $C$ is given by $\frac{1}{m}\sum_{j=1}^m x_jx_j^\top$.

I'm having difficulty understanding why the necessity holds, that is, why $v$ an eigenvector of $C$ if for all $i = 1, \dots, m$, there's $\lambda$ such that $\lambda \langle x_i, v \rangle = \langle x_i, C v \rangle$.

Any hint is appreciated. Thank you so much!

Answer 1

This looks like $C$ is a sample covariance matrix and hence positive definite. Thus spectral theorem can be applied to find a orthogonal basis consisting of its eigenvectors.

As for how $\lambda \langle x_i, v \rangle = \langle x_i, C v \rangle, $ assuming $ x_i\in \mathbb R^n,$ then $\lambda \langle x_i, v \rangle = \lambda\langle v, x_i\rangle=\langle \lambda v, x_i\rangle= \langle Cv, x_i\rangle=\langle x_i, Cv\rangle.$

Answer 2

It turns out that I misunderstood the equivalence in the book. The book actually means "$v$ is eigenvector of $C$ iff for all $i=1,\dots,m$ $\lambda\langle x_i,v \rangle = \langle x_i,Cv \rangle$ and $v$ lies in the span of $x_1,\dots,x_m$". Taking the second condition into account, $v = \sum_{j=1}^m\alpha_jx_j = X\boldsymbol\alpha$, and it follows that

$$ \begin{aligned} \lambda \langle x_i, v \rangle &= \langle x_i, Cv \rangle\\ \lambda\sum_{j=1}^m\alpha_j\langle x_i,x_j \rangle &= \sum_{j=1}^m\alpha_j\langle x_i,Cx_j \rangle\\ m\lambda\sum_{j=1}^m\alpha_j\langle x_i,x_j \rangle &= \sum_{j=1}^m\alpha_j\left\langle x_i,\sum_{n=1}^mx_n\langle x_n,x_j \rangle\right\rangle\\ m\lambda\sum_{j=1}^m\alpha_j\langle x_i,x_j \rangle &= \sum_{n=1}^m\langle x_i,x_n \rangle\sum_{j=1}^m\alpha_j\langle x_n,x_j \rangle\\ m\lambda X^\top X\boldsymbol\alpha &= (X^\top X)^2\boldsymbol\alpha\\ m\lambda (X^\top v) &= X^\top X(X^\top v)\,\text{.} \end{aligned} $$

Let $u$ be an eigenvector of $XX^\top$. It's self-evident that $X^\top u$ will be an eigenvector of $X^\top X$. Therefore, $v$ is an eigenvector of $XX^\top$, or equivalently, $C$.