# The matrix norm $\|A\|=\max_{\langle u|u\rangle=1}|\langle u|A|u\rangle|$ in the proof of Lieb's theorem

In Exercise A6.4, Appendix 6: Proof of Lieb’s theorem, Page 645, Quantum Computation and Quantum Information by Nielsen and Chuang, A matrix norm of $$A$$ is defined as $$\|A\|=\max_{\langle u|u\rangle=1}|\langle u|A|u\rangle|=\max_{u^Tu=1}|u^TAu|$$ If $$A$$ has eigenvalues $$\lambda_i$$ and defining $$\lambda$$ to be the maximum of the set $$|\lambda_i|$$ then

1. $$\|A\|\ge \lambda$$
2. When $$A$$ is hermitian, $$\|A\|=\lambda$$
3. When $$A=\begin{bmatrix}1&0 \\ 1&1\end{bmatrix}$$, $$\|A\|=3/2>1=\lambda$$

For any fixed symmetric matrix $$A\in\mathbb{R}^{n\times n}$$, fixed rectangular matrix $$B\in\mathbb{R}^{m\times n}$$ and fixed vector $$a\in\mathbb{R}^n$$, we can define \begin{align} \frac{\partial}{\partial u}a^Tu=a\quad &\quad \frac{\partial}{\partial u}\|u\|^2=2u\\ \frac{\partial}{\partial u}(u^TAu)=2Au\quad &\quad \frac{\partial}{\partial u}\|Bu|^2=2B^TBu\\ \end{align} We need to find the critical points of the function $$u^TAu$$ subject to the constraint $$|u|^2=u^Tu=1$$.

ie., to find the critical points of the Lagrangian function, $$L(u,\lambda)=u^TAu-\lambda(u^Tu-1)$$ \begin{align} \frac{\partial L}{\partial u}&=\frac{\partial}{\partial u}(u^TAu)-\lambda\frac{\partial}{\partial u}|u|^2\\ &=2Au-\lambda(2u)=0\\ \implies Au&=\lambda u\\ \frac{\partial L}{\partial\lambda}&=|u|^2-1=0\implies |u|^2=1 \end{align} Therefore, $$u,\lambda$$ must be an eigenpair of $$A$$.

$$\therefore$$ the eigenvectors of $$A$$ are the critical points of $$u^TAu$$

$$\therefore$$ $$\max_{u^Tu=1}u^TAu=\lambda_\max$$, the largest eigenvalue of the matrix $$A$$.

So it looks like, $$\|A\|=\max_{\langle u|u\rangle=1}|\langle u|A|u\rangle|=\max_{u^Tu=1}|u^TAu|$$ is the largest eigenvalue of the matrix $$A$$.

My Doubt

If we take $$u$$ to be the eigenvector associated with the largest eigenvalue $$\lambda$$ of the matrix $$A$$ then $$\langle u|A|u\rangle=\lambda\langle u|u\rangle=\lambda$$. And this implies $$\|A\|=\max_{\langle u|u\rangle=1}|\langle u|A|u\rangle|\ge \lambda$$, fine.

But, given that the proof above shows the critical values of $$\langle u|A|u\rangle$$ occur at the unit eigenvectors, how is it possible that we can have $$\|A\|>\lambda$$?

For example, considering the matrix $$\begin{bmatrix}1&0 \\ 1&1\end{bmatrix}$$ which only has $$1$$ as its eigenvalue with eigenvector $$\begin{bmatrix}0\\\frac{1}{\sqrt{2}}\end{bmatrix}$$ is said to have the norm $$\|A\|=\max_{\langle u|u\rangle=1}|\langle u|A|u\rangle|=3/2$$ which obviously not occur at any eigenvector of $$A$$.

Crossposted on math.stack

• seems to have been already answered on math.SE. If $\lambda$ is an eigenvalue then $\langle u,Au\rangle=\lambda$ with $u$ eigenvector of $A$ corresponding to $\lambda$. Thus obviously maximising this quantity over all unit vectors $u$ gives you something larger than $\lambda$. Same goes putting absolute values on both sides (note that the statement should be $\|A\|\ge|\lambda|$, unless you're ensured $\lambda\in\mathbb R$)
– glS
Mar 13, 2023 at 13:57
• @glS I am confused particularly about the possibility that the maximum of $|\langle u,Au\rangle|$ occurs for some unit vector $u$ which is not an eigenvector of $A$, when $A$ is nondiagonalizable such as the example $\begin{bmatrix}1&0\\1&1\end{bmatrix}$, yet the proof shows the critical values of $\langle u,Au\rangle$ occurs at the eigenvectors of $A$. Mar 13, 2023 at 20:18
• @glS The proof seems to show that the critical values of $\langle u,Au\rangle$ occurs at the eigenvectors. Then why do we have $||A||=3/2$ for the given matrix $A=\begin{bmatrix}1&0\\1&1\end{bmatrix}$?How do I justify this ? Mar 13, 2023 at 20:21
• I don't understand the need to mention critical values. $\lambda=\langle u,Au\rangle$ regardless of whether $A$ is diagonalisable are not, and you don't need to discuss critical values or maximisations for it. It's just because the definition of eigenvalue means $Au=\lambda u$
– glS
Mar 13, 2023 at 20:22
• @glS My doubt is, given the proof shows the critical values occur at the eigenvectors, how do I justify the case when $||A||>\lambda$, which corresponds to $u$ which is not an eigenvector, as is the case of $\begin{bmatrix}1&0\\1&1\end{bmatrix}$. Mar 13, 2023 at 23:06

1. The partial derivative of $$u^TAu$$ you state is wrong
2. More gravely, the whole approach is flawed because you're treating $$u$$ as a real vector: one has to allow for complex $$u$$ in the definition of $$\|A\|$$, even if $$A$$ itself is real
To expand upon the first point: the expression $$\frac{\partial}{\partial u}u^TAu=2Au$$ which, as you already suggest, is only valid if $$A$$ is symmetric. The expression for general $$A$$ reads $$\frac{\partial}{\partial u}u^TAu=(A+A^T)u$$ as \begin{align*} \frac{\partial}{\partial u_j}u^TAu&=\frac{\partial}{\partial u_j}\Big(\sum_{k,l}u_kA_{kl}u_l\Big)\\ &=\sum_{l}A_{jl}u_l+\sum_{k}A_{kj}u_k\\ &=\big((A+A^T)u\big)_j\,. \end{align*} In other words, for symmetric $$A$$ your calculation works as intended, but for arbitrary (actually: non-normal) $$A$$ your argument breaks down, and pretty badly at that. This is where we get to the second point:
Using the correct partial derivative your argument suggests that $$\|A\|=|\lambda_{\rm max}(\frac{A+A^T}2)|$$ which, however, is not true in general, even if $$A$$ is real (more precisely: only $$\geq$$ holds). The underlying problem here is that the eigenvalues of a real matrix may be complex; so while this equality does hold for the matrix from your third point because the matrix as well as its eigenvalues are real, let us look at a simple example which highlights why allowing only for real $$u$$ is problematic. Consider $$A=\begin{pmatrix}0&1\\-1&0\end{pmatrix}$$ which has eigenvalues $$\pm i$$. One readily verifies that $$\langle u|A|u\rangle=0$$ for all real vectors $$u$$, but $$\{\langle u|A|u\rangle:u\in\mathbb C^2,\|u\|=1\}=[-i,i]$$ so $$\|A\|=1$$. In fact, this norm is attained on, e.g., $$u=(1,i)^T/\sqrt2$$ which is obviously---and necessarily---not real.
Of course one could modify your approach to instead maximize the correct functional $$\mathbb R^{2n}\simeq\mathbb C^n\ni u\mapsto|\langle u|A|u\rangle|=\sqrt{\Big\langle u\Big|\frac{A+A^*}2\Big|u\Big\rangle^2+\Big\langle u\Big|i\frac{A-A^*}2\Big|u\Big\rangle^2}$$ over the unit sphere using Lagrange multipliers. The calculation is a bit tedious but certainly doable and it yields \begin{align*} \|A\|&=\max_{\phi\in[0,2\pi]}\Big|\lambda_{\rm max}\Big( \cos(\phi)\frac{A+A^*}2+\sin(\phi)i\frac{A-A^*}2 \Big)\Big|\\ &= \max_{\phi\in[0,2\pi]}\Big|\lambda_{\rm max}\Big( \frac{e^{i\phi}A+e^{-i\phi}A^*}2\Big)\Big|\,. \end{align*} This is a corollary of the fact that the boundary of the numerical range $$\{\langle u|A|u\rangle:u\}$$ of $$A$$ is encoded in the largest eigenvalue of the Hermitian part of $$e^{i\phi}A$$, cf. C. Johnson (1978). Numerical Determination of the Field of Values of a General Complex Matrix. SIAM Journal on Numerical Analysis, 15(3), 595–602