How to prove the following inequality: $(A f(x) - A f(y))^T(x - y) \geq \lambda_{min}(A)(f(x) - f(y))^T(x - y) $

Question

Let $x,y \in \mathbb{R}^n$, $f: \mathbb{R}^n \to \mathbb{R}^n$ a continuous map.

(Per comment) Let $A$ be an symmetric, positive definite matrix.

I wish to prove that:

$(A f(x) - A f(y))^T(x - y) \geq \lambda_{min}(A)(f(x) - f(y))^T(x - y) $

$\lambda_{min}$ being the smallest eigenvalue of $A$. Can anyone see what principle is used such that the inequality is true?

Answer 1

The question simplifies to:

suppose $A$ is positive definite and $x^Ty \geq 0$, show that $(Ax)^T y \geq \lambda_{min}(A) x^T y$

Writing $A = \sum_i \lambda_i v_i v_i^T$, we need to show $$\sum_i \lambda_i x^T v_i v_i^T y \geq \lambda_{min}(A) x^T y$$

This is not necessarily true. Take $n=2$, $\lambda_1 = 1$, $\lambda_2 = 0.5$, $$ x = \begin{pmatrix}1\\0\end{pmatrix}, y = \begin{pmatrix}0\\1\end{pmatrix}, v_1 = \begin{pmatrix}\sqrt{2}/2 \\ -\sqrt{2}/2\end{pmatrix}, v_2 = \begin{pmatrix}\sqrt{2}/2 \\ \sqrt{2}/2\end{pmatrix}. $$ The statement is now $-0.5 \geq 0$, which is clearly not true. Returning to your original formulation, the function $f(x) = \begin{pmatrix}x_2 \\ x_1\end{pmatrix}$, the points $x=\begin{pmatrix}1 \\ 1\end{pmatrix}$, $y=\begin{pmatrix}1 \\ 0\end{pmatrix}$, and $A=\begin{pmatrix}0.75 & 0.75 \\ -0.25 & -0.25\end{pmatrix}$ are a counterexample.

For the statement to hold, you need $x^T v_i v_i^T y \geq 0$. In that case: $$\sum_i \lambda_i x^T v_i v_i^T y \geq \sum_i \lambda_{min}(A) x^T v_i v_i^T y = \lambda_{min}(A) x^T \left(\sum_i v_i v_i^T \right) y = \lambda_{min}(A) x^Ty$$