2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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$) $\endgroup$
    – glS
    Mar 13, 2023 at 13:57
  • $\begingroup$ @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$. $\endgroup$
    – Sooraj S
    Mar 13, 2023 at 20:18
  • $\begingroup$ @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 ? $\endgroup$
    – Sooraj S
    Mar 13, 2023 at 20:21
  • $\begingroup$ 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$ $\endgroup$
    – glS
    Mar 13, 2023 at 20:22
  • $\begingroup$ @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}$. $\endgroup$
    – Sooraj S
    Mar 13, 2023 at 23:06

1 Answer 1

2
$\begingroup$

The short answer is that there are two problems with your argument:

  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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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