Showing a bound on $x^\intercal A^{-1} x$ using $A$

71 Views Asked by At

Let $A \in \mathbb{R}^{n \times n}$ be symmetric and positive definite and fix vector $x_0 \in S^{n-1}$, which means $\|x_0\|_2 = 1$. We want to show

$$x_0^\intercal A^{-1} x_0 \leq c$$

for a fixed vector $x_0$. We want to convert the problem in such a way to work with the matrix $A$ instead of $A^{-1}$.

One way to do this is the following. If we show that $x^\intercal A^{-1} x \leq c$ for any $x \in S^{n-1}$, then we can conclude $x_0^\intercal A^{-1} x_0 \leq c$. This means that all eigenvalues of $A^{-1}$ are smaller than or equal to $c$ or equivalently, all eigenvalues of $A$ are greater than or equal to $1/c$. In other words,

$$x^\intercal A x \geq 1/c \quad \text{ for all } x \in S^{n-1} \quad \Rightarrow \quad x_0^\intercal A^{-1} x_0 \leq c$$

Question: Showing $x^\intercal A x \geq 1/c$ for $x \in S^{n-1}$ is a much stronger result than $x_0 \in S^{n-1}$. It is possible to specifiy a smaller set $\mathcal{B} \in S^{n-1}$ based on $x_0$ such that

$$x^\intercal A x \geq 1/c \quad \text{ for all } x \in \mathcal{B} \quad \Rightarrow \quad x_0^\intercal A^{-1} x_0 \leq c?$$


My attempt: Eigenvectors of $A$ and $A^{-1}$ are the same. If $x_0$ is an eigenvector of $A$ with eigenvalue $\lambda_0$, then

$$x_0^\intercal A x_0 = \lambda_0 \geq \frac{1}{c} \quad \Rightarrow \quad x_0^\intercal A^{-1} x_0 = \frac{1}{\lambda_0} \leq c$$

So $\mathcal{B} = \{ x_0\}$ works here.

1

There are 1 best solutions below

3
On BEST ANSWER

This isn't quite the lines you were working along, but you might find the following helpful. Using the Schur complement, we find that $c - x_0^\top A^{-1}x_0 \geq 0$ if and only if the matrix $$ M = \pmatrix{A & x_0\\x_0^\top & c} $$ is positive semidefinite. Using the other Schur complement, we see that this in turn holds if and only if the matrix $A - c^{-1}x_0x_0^\top$ is positive semidefinite. This holds if and only if we have $x^\top Ax \geq \frac{(x_0^\top x)^2}{c}$ for all $x \in S^{n-1}.$