Minimum EigenValue

Question

From Rayleigh Equation, we know for symmetric $n\times n$ matrix $A$ $$\min_{x\in \mathbb{R}^n\setminus \{0\}}\frac{x^TAx}{x^Tx} = \lambda_{\min}(A)$$

My question is does the same equation hold for the following scenario $$\inf_{x\in \mathbb{S}^{n-1}\setminus\{x^*\}}\frac{(x-x^*)^TA(x-x^*)}{(x-x^*)^T(x-x^*)} = \lambda_{\min}(A)$$

where $\mathbb{S}^{n-1}$ is the unit sphere in $n$ dimensions and $x^*$ is a fixed element in $\mathbb{S}^{n-1}$.

Further, it seems that the minimum can be achieved if $x^*$ is orthogonal to the eigenvector corresponding to the minimum eigen value. Can this also be proved formally/

Answer 1

There's a few nice ways to do this but I focus on the technique of (1) make the minimum eigenvalue 0, i.e. all associated eigenvectors for the minimum eigenvalue $\in \ker A$. Note this implies $A\succeq \mathbf 0$.

We do this by translation: considering $A_\gamma := A + \gamma I$ for $\gamma := -\lambda_\min$
$\dfrac{\mathbf x^T A_\gamma \mathbf x}{\mathbf x^T\mathbf x} = \dfrac{\mathbf x^T A \mathbf x}{\mathbf x^T\mathbf x}+\gamma$
which is precisely the amount that all eigenvalues shift by in $A\mapsto A_\gamma$.
And the same preservation occurs when we consider $\dfrac{\big(\mathbf x - \mathbf x^*\big)^T A_\gamma \big(\mathbf x - \mathbf x^*\big)}{\big(\mathbf x - \mathbf x^*\big)^T \big(\mathbf x - \mathbf x^*\big)}=\dfrac{\big(\mathbf x - \mathbf x^*\big)^T A\big(\mathbf x - \mathbf x^*\big)}{\big(\mathbf x - \mathbf x^*\big)^T \big(\mathbf x - \mathbf x^*\big)} + \gamma$ for any $\mathbf x \neq \mathbf x^*$

So we can assume WLOG (1) is true.

To verify the lower bound: for any $\mathbf x \neq \mathbf x^*$ we have
$\big(\mathbf x - \mathbf x^*\big)^T A \big(\mathbf x - \mathbf x^*\big)\cdot \big \Vert\mathbf x - \mathbf x^*\big \Vert_2^{-2} \cdot\geq 0$
because $A$ is PSD

To show that the bound is tight
$W:=\ker\big( A\big)$ and split into two cases

(i) $\mathbf x^*\notin W^\perp$ (infimum is attained)
then $\mathbf x^* = \alpha' \mathbf w + \beta'\mathbf v$ for some unit length vectors $\mathbf w \in W$ and $\mathbf v\in W^\perp$ where $\alpha'\neq 0$ and of course $(\alpha')^2 + (\beta')^2 =1$
Then $\mathbf x:= -\alpha' \mathbf w + \beta'\mathbf v$ meets the lower bound with equality since $\mathbf 0 \neq \mathbf x - \mathbf x^* = -2\alpha'\cdot \mathbf w \in \ker A$

(ii) $\mathbf x^*\in W^\perp$ (infimum not attained)
for some $\mathbf w \in W$ with length 1
in this case write $\mathbf x \in \mathbb S^{n-1}-\big\{\mathbf x^*\big\}$ as

$\mathbf x = \alpha \mathbf w + \beta\mathbf x^*$ where $\alpha^2 + \beta^2 =1 $ and note $(\mathbf x^*)^TA\mathbf x^* =\eta \in \mathbb R_{\gt 0}$

consider this sequentially using $\mathbf x_k$ with $\beta_k:=1-\big(\frac{1}{2}\big)^k=\frac{2^k-1}{2^k} $ which implies $\alpha_k^2 = \frac{2^{k+1}-1}{4^k}$ $\big(\mathbf x_k - \mathbf x^*\big) = \big(\alpha_k \mathbf w + (\beta_k-1) \mathbf x^*\big)\implies \big(\mathbf x_k - \mathbf x^*\big)^T A \big(\mathbf x_k - \mathbf x^*\big) = \eta (1-\beta_k)^2$ and
$\big \Vert\mathbf x_k - \mathbf x^*\big \Vert_2^{-2} = \Big(\alpha_k^2 +\big(1-\beta_k\big)^2\Big)^{-1} $ and we have

$\implies \big(\mathbf x - \mathbf x^*\big)^T A \big(\mathbf x - \mathbf x^*\big)\cdot \big \Vert\mathbf x - \mathbf x^*\big \Vert_2^{-2} = \eta \cdot \dfrac{(1-\beta_k)^2}{\alpha_k^2 +\big(1-\beta_k\big)^2}= \eta \cdot \dfrac{\frac{1}{4^k}}{\frac{2^{k+1}-1}{4^k} +\frac{1}{4^k}}$
$= \eta \cdot \dfrac{1}{2^{k+1}-1}\lt \eta \cdot \dfrac{1}{2^{k}}$

which has modulus $\lt \epsilon$ for any $\epsilon \gt 0$ by selecting $k$ large enough. This shows that the lower bound is in fact the infimum.

Answer 2

Proof of $m_r=\min_{x\in \mathbb{R}^n \setminus \{0\}}\frac{x^TAx}{x^Tx} =\inf_{x\in \mathbb{S}^{n-1} \setminus\{x^*\}}\frac{(x-x^*)^TA(x-x^*)}{(x-x^*)^T(x-x^*)} = m_s$

As $\mathbb S^{n-1} \subseteq \mathbb R^n$, we have

$$m_r=\inf_{x\in \mathbb{R}^n \setminus \{0\}}\frac{x^TAx}{x^Tx} \le \inf_{x\in \mathbb{S}^{n-1} \setminus\{x^*\}}\frac{(x-x^*)^TA(x-x^*)}{(x-x^*)^T(x-x^*)} = m_s$$

Now for any $y \in \mathbb R^n \setminus \{0\}$, we have

$$\frac{y^TAy}{y^Ty} = \frac{y_1^TAy_1}{y_1^Ty_1}$$ where $y_1 = \frac{y}{\Vert y \Vert}$. So we can suppose that $\Vert y \Vert = 1$. If $y$ is not orthogonal to $x^*$, we can write

$$\lambda y=x-x^*$$ where $-x$ is the symmetric of $x^*$ with regard to the line generated by $y$ and $\lambda $ a scalar. In that case, we get $$y^TAy=\frac{y^TAy}{y^Ty}= \frac{(\lambda x)^TA(\lambda x)}{(\lambda x)^T(\lambda x)} = \frac{(x-x^*)^TA(x-x^*)}{(x-x^*)^T(x-x^*)} \ge m_s .$$

If $y \perp x^*$, we can find a sequence $\{y_n\}$ of $\mathbb S^{n-1}$ converging to $y$ such that $y_n$ is not perpendicular to $x^*$ for all $n \in \mathbb N$. According to what has just been proven, we have for all $n \in \mathbb N$

$$y_n^TAy_n=\frac{y_n^TAy_n}{y_n^Ty_n} \ge m_s.$$ And as the map $z \to z^TAz$ is continuous, we also get that $$y^TAy=\frac{y^TAy}{y^Ty} \ge m_s.$$

This concludes the proof that $m_r=m_s$.

Is the minimum attained?

The minimum may not be attained if $x^*$ is orthogonal to the eigenvector of the minimum eigenvalue. Take

$$A=\begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}, x^*=\begin{pmatrix} 1\\ 0 \end{pmatrix} $$ for $x =\begin{pmatrix} \cos \theta\\ \sin \theta \end{pmatrix} \in \mathbb S\setminus \{x^*\}$ the numerator of $$\frac{(x-x^*)^TA(x-x^*)}{(x-x^*)^T(x-x^*)}$$ will never vanish while the minimum eigenvalue is zero.

Answer 3

We may use the properties of the usual real-vlaued inner product on $\mathbb{R}^{n}$: We have that

$$\frac{x^T Ax}{x^Tx}=\frac{\langle x,Ax \rangle}{\langle x,x \rangle}= \frac{\langle x,Ax \rangle}{\|x\|^2}=\langle \frac{x}{\|x\|},A \frac{x}{\|x\|} \rangle$$

So we actually have that

$$\lambda_{\text{min}}=\min_{\|x\|=1}\langle x,A x \rangle.$$

Now apply the same argument to see that

$$\min_{x\in \mathbb{S}^n\setminus\{x^*\}} \frac{(x-x^*)^T A (x-x^*)}{(x-x^*)^T A (x-x^*)}= \min_{y\in \mathbb{S}^n\setminus\{0\}} \frac{y^T A y}{y^T A y} =\min_{\|x\|=1}\langle x,A x \rangle$$