# How to prove: $\max_{\left \| x \right \|=1}x^*(\frac{A+A^*}{2})x\geq \max_{\left \| x \right \|=1}(x^*A^*Ax)^{\frac{1}{2}}$?

Problem:

A is an $n\times n$ complex matrix. Let $\lambda _\max(Y)$ and $\sigma _\max(Y)$ denote respectively the largest eigenvalue and the largest singular value of a square matrix $Y$. The question is to prove that: $$\lambda _\max\left(\frac{A+A^*}{2}\right)\leq \sigma _\max (A)$$

I started as follows: Since $A$ is Hermitian, then $(A+A^*)$ is Hermitian as well. Then: $$\lambda_\max\left(\frac{A+A^*}{2}\right)=\max_{\left \| x \right \|=1}x^*\left(\frac{A+A^*}{2}\right)x$$ where $x\in \mathbb{C}^n$

I need to prove the following to finish my proof: $$\max_{\left \| x \right \|=1}x^*\left(\frac{A+A^*}{2}\right)x\geq \max_{\left \| x \right \|=1}(x^*A^*Ax)^{\frac{1}{2}}\tag{1}$$

From the first sight, it looks like I have to use the fact that: $\sqrt{ab}\geq \frac{a+b}{2}$ for $a$ and $b$ positive, but this works only for numbers and not matrices.

I appreciate if someone can prove the inequality $(1)$.

-
Are you sure you need to require that $A$ is hermitian? Because in that case, $(A+A^*)/2=A$. – Martin Argerami Apr 23 '12 at 2:04
And you also need an absolute value in the left-hand side (inside the max); otherwise the inequality is trivially false with $A=-1$. – Martin Argerami Apr 23 '12 at 2:12
@Martin Argerami: You're right. $A$ is not Hermitian. I will edit the original statement. – Boyan Klo Apr 23 '12 at 2:18
If $A$ is allowed to be non-hermitian, the inequality is again false in general. For example, if $A^*=-A$, then the left-hand side is zero, while the right-hand side is not. – Martin Argerami Apr 23 '12 at 3:03

Your inequality is actually a well-known equality (in the case where $A$ is hermitian).
The right-hand side of your inequality is the operator norm of $A$, i.e. $$\max_{\left \| x \right \|=1}(x^*A^*Ax)^{\frac{1}{2}}=\|A\|.$$ For the left-hand side we get, using the Cauchy-Schwarz inequality, $$\max_{\left \| x \right \|=1}\left|x^*(\frac{A+A^*}{2})x\right|\leq\max_{\left \| x \right \|=1}\|x\|\,\left\|\frac{A+A^*}2\right\|\,\|x\|=\left\|\frac{A+A^*}2\right\|\\ \leq\frac{\|A\|+\|A^*\|}2=\frac{\|A\|+\|A\|}2=\|A\|.$$ Note that so far we don't use that $A$ is hermitian. When $A$ is hermitian, however, we can prove the reverse inequality, which requires a little more work.
Let $$s=\max\{|x^*Ax|:\ \|x\|=1\}$$ Now take vectors $x,y$ with $\|x\|=\|y\|=1$. Then $$(x\pm y)^*A(x\pm y)=x^*Ax+y^*Ay\pm2\text{Re}\,y^*Ax.$$ Subtracting one equation from the other we get $$4\text{Re}\,y^*Ax=(x+y)^*A(x+y)-(x-y)^*A(x-y)$$ (this is the real part of what is usually called the polarization identity). Now we get $$4\text{Re}\,y^*Ax\leq s\,\|x+y\|^2+s\,\|x-y\|^2=2s\,(\|x\|^2+\|y\|^2)=2s.$$ Fix $t$ such that $y^*Ax=e^{it}\,|y^*Ax|$. Note that we can do the above process for the vector $e^{-it}x$, and so this shows that $$|y^*Ax|\leq s\ \ \ \ \text{ for any }x,y\text{ with }\|x\|=\|y\|=1.$$ Taking max over $y$ with $\|y\|=1$, we obtain $$\|Ax\|\leq s \ \ \ \text{ for all } x \text{ with } \|x\|=1,$$ and thus $$\|A\|\leq s.$$