An eigen problem

Question

$K$ is a symmetric positive semidefefinit matrix. $K1 = 0$ (i.e. The sum of elements in each row is $0$. Or in other words matrix $K$ is centered. From this we conclude the smallest eigenvalue of $K$ is zero. With eigenvector $1$, where $1$ is a vector of all ones. ) Now what is the value of

\begin{equation} \min_{x} \frac{x^TK x}{x^Tx} \end{equation} s.t. $x^T1=0$?

Note: I still did not get why any eigenvector of $K$, nameley $v$, should satisfy the constraint $v^T1=0$?

Answer 1

The quantity $\frac{x^TKx}{x^Tx}$ is called Rayleigh Quotient. we have a principle called Rayleigh Principle: The minimum value of Rayleigh Quotient is the smallest eigen value $\lambda_1$. However the minimum of the quotient subject to $x^T1=0$ is $\lambda_2$ which is second smallest eigen value.

Refernce: Gilbert Strang Book chapter on PSD

Answer 2

Every real symmetric matrix $K$ is orthogonally diagonalizable. That means if $u$ is a unit eigenvector of $K$, you can always extend it to an orthonormal eigenbasis of $\mathbb{R}^n$ that corresponds to the matrix $K$. So, suppose $\lambda_1\ge\ldots\ge\lambda_n$ are the eigenvalues of $K$ and $Ku=\lambda_nu$. Then there is an orthonormal set of eigenvectors $v_1,\ldots,v_n$ such that $Kv_i=\lambda_iv_i$ and $v_n=u$. Hence $K=QDQ^T$ where $Q=(v_1,\ldots,v_n)$ and $D=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)$. Let $e_n=(0,\ldots,0,1)^T$. Then $$ \min_{x\neq0,\,x\perp u=v_n} \frac{x^TK x}{x^Tx} =\min_{y=(Q^Tx)\neq0,\,y\perp e_n} \frac{y^TDy}{y^Ty} =\min_{y\perp e_n} \frac{y^TDy}{y^Ty} =\lambda_{n-1}. $$ This is true regardless of whether $K$ is positive semidefinite or not, and regardless of the choice of $u$ if $\lambda_n$ is a repeated eigenvalue (i.e. the associated eigenspace has dimension $>1$). All we need is that $K$ is real symmetric. More generally, we have $$ \lambda_k =\min_{x\neq0,\,x\perp v_{k+1},\ldots,v_n} \frac{x^TK x}{x^Tx} =\max_{x\neq0,\,x\perp v_1,\ldots,v_{k-1}} \frac{x^TK x}{x^Tx} $$ You may view this as an orthogonal subspace analogue of the Courant-Fischer minimax principle.