6
$\begingroup$

Let $A$ a square real matrix such that the largest singular value $\sigma_\text{max}(A) = \sigma < 1$. I want to find a lower bound on $\langle (I + A)^{-1}x, x\rangle$ where $x$ is a vector of euclidean norm $1$: $\langle x, x\rangle=1$.

I empirically find that a seemingly tight lower bound is $$ \langle (I + A)^{-1}x, x\rangle \geq \frac{1}{1+\sigma} $$ which is reached for $A= \sigma I$. I cannot prove the above result.

Note that it is pretty straightforward to prove that $\sigma_\text{min}((I + A)^{-1}) \geq \frac1{1+\sigma}$ but that does not suffice to conclude, since I do not assume that $A$ is symmetric.

PS: $\sigma_\text{max}$ and $\sigma_\text{min}$ are the largest and smallest singular values: $\sigma_\text{max} = \sqrt{\lambda_\text{max}(AA^T)}$ is the operator norm of $A$.

$\endgroup$
1
  • 1
    $\begingroup$ Suggestions for better question: Explain notation $\sigma_{\text{max}}, \sigma_{\text{min}}$. What norm used for vectors? $\endgroup$ Aug 29 at 13:31
6
$\begingroup$

The map $f(z)=(1+z)^{-1} - (1+\sigma)^{-1}$ maps the disk of radius $\sigma$ into the right half plane as a function of one complex variable.

Therefore, essentially by von Neumann's inequality, we get that $$\frac{f(A)+f(A)^*}{2}=\mathrm{Re }f(A)\geq 0$$ since $\|A\|\leq \sigma.$ Assuming $A$ has real entries, this implies the claim as $$\langle (1+A)^{-1}x,x\rangle = \langle \mathrm{Re} (1+A)^{-1}x,x\rangle.$$

To see the calculation with von Neumann's inequality more explicitly, let $\psi(z) = \frac{z-1}{z+1}.$ Note $\psi$ takes the right half plane to the disk. So, $\psi \circ f$ takes the disk of radius $\sigma$ into the unit disk. Therefore, von Neumann's inequality states that $\|\psi \circ f(A)\|\leq \sup_{z\in \sigma\mathbb{D}} |\psi\circ f(z)| \leq 1.$ Note that $$1-(\psi \circ f(A))^*(\psi \circ f(A)) \geq 0.$$ (Here by $T\geq 0$ we mean that $T$ is positive semi-definite.) Writing out what that means $$1-(f(A)^*+1)^{-1}(f(A)-1)^*(f(A)-1)(f(A)+1)^{-1} \geq 0.$$ So, $$(f(A)^*+1)(f(A)+1)-(f(A)^*-1)(f(A)-1)=2(f(A)+f(A)^*)\geq 0.$$

Results of the above form (positivity of noncommutative rational functions) always have to have "algebraic proofs," many of which can be done algorithmically. See, e. g., Helton, Klep, and McCullough - The convex Positivstellensatz in a free algebra and Pascoe - Positivstellensätze for noncommutative rational expressions.

$\endgroup$
4
  • $\begingroup$ Thanks! I am unfamiliar with von Neumann's inequality: are you talinkg about en.wikipedia.org/wiki/Von_Neumann%27s_inequality ? If so, could you explain how it implies $f(A) + f(A)^T \geq 0$ ? (Sorry I forgot to mention that everything is real here). $\endgroup$
    – PAb
    Aug 29 at 14:01
  • 1
    $\begingroup$ @PAb I added an explanation at the bottom. Hopefully that helps. $\endgroup$ Aug 29 at 14:19
  • 1
    $\begingroup$ @PAb and yes that was the theorem I was talking about. $\endgroup$ Aug 29 at 14:28
  • $\begingroup$ Small typo: $\psi$ rather maps the right half plane to the unit disk. Thanks for the neat trick ! $\endgroup$
    – PAb
    Aug 30 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.