# Help understand an inequality in a proof

Assume standard inner product and 2-norm. $A$ is any symmetric real-valued $n\times n$ square matrix. $V_k$ is an $n\times k$ matrix whose columns are orthonormal. $T_k$ is a matrix such that it has the following relation with $A$ and $V_k$:

$AV_k=V_kT_k+{\hat v}_{k+1}e_k^T$

where ${\hat v}_{k+1}$ is another vector orthogonal to every column of $V_k$, and $e_k^T = (0,...,0,1)$ is a vector with only the $k$th component being 1. I need to understand the following proof, but got stuck at an inequality. This is a proof about the error bound of Lanczos iteration.

Above proof uses

In order to apply Cauchy-Schwarz, which is $<x,y>\le \|x\|\|y\|$, we need to place absolute value operator on both the LHS and RHS of (10.26), but I have trouble understanding how the LHS of (10.26) becomes the LHS of (10.27). Many thanks!

PS: the whole thing for those who are interested. the theorem in question is the last one.

• Note: we can only break $A$ up into a linear combination of orthogonal projection matrices if $A$ is symmetric. I am guessing this assumption has been forgotten either by you or the author – Omnomnomnom Jul 7 '17 at 14:05
• @Omnomnomnom Yes. That is my fault. I added this assumption. Thanks! – River Jul 7 '17 at 14:08
• Also, the result is certainly believable if $\lambda_i > \lambda$ for all $i$ or if $\lambda_i < \lambda$ for all $i$, but otherwise that step on the LHS requires explanation. – Omnomnomnom Jul 7 '17 at 14:09
• @Omnomnomnom $\left| {\sum\limits_{i = 1}^m {({\lambda _i} - \lambda ){{\left\| {{P_i}({V_k}y)} \right\|}^2}} } \right| \ge \left| {\sum\limits_{i = 1}^m {\min \left| {{\lambda _i} - \lambda } \right|{{\left\| {{P_i}({V_k}y)} \right\|}^2}} } \right| \ge \min \left| {{\lambda _i} - \lambda } \right|\left| {\sum\limits_{i = 1}^m {{{\left\| {{P_i}({V_k}y)} \right\|}^2}} } \right| \ge \min \left| {{\lambda _i} - \lambda } \right|{\left\| {\sum\limits_{i = 1}^m {{P_i}({V_k}y)} } \right\|^2} = \min \left| {{\lambda _i} - \lambda } \right|{\left\| y \right\|^2}$ – River Jul 7 '17 at 14:27
• @River are you still confused about this? It looks like your comment provides the missing step. – jschnei Jul 9 '17 at 15:51

The formula (10.26) says $$\langle (A-\lambda)V_ky,V_ky\rangle = \langle e_k,y\rangle \langle \hat{v}_{k+1},V_ky\rangle$$ Remembering (10.25), the angle between $(A-\lambda)V_ky$ and $V_ky$ is the same as the angle between $\hat{v}_{k+1}$ and $V_ky$, (the book does not say that this is fundamental for deriving (10.27)) so: $$\lVert(A-\lambda)V_ky\rVert \lVert V_ky\rVert = \langle e_k,y\rangle \lVert \hat{v}_{k+1}\rVert\lVert V_ky\rVert$$ For Cauchy-Schwartz applied to the first part of the rhs $$\langle e_k,y\rangle \le \lVert y\rVert$$

As to the lhs, remember that the 2-norm of a symmetric real-valued matrix $A$ is $$\lVert A\rVert=\max\limits_i \lvert \lambda_i\rvert$$ The 2-norm of its inverse, when A is non-singular, is then $$\lVert A^{-1}\rVert=1/\min\limits_i \lvert \lambda_i\rvert$$ So it is (this is an important bound formula, not mentioned in the book, rearranged for our purpose) $$\frac{\lVert(A-\lambda) V_ky\lVert}{\lVert V_ky\rVert} = \frac{\lVert(A-\lambda) V_ky\lVert}{\lVert (A-\lambda)^{-1}(A-\lambda)V_ky\rVert} \ge \frac{\lVert(A-\lambda) V_ky\lVert}{\lVert (A-\lambda)^{-1}\rVert\lVert(A-\lambda)V_ky\rVert} = \min\limits_i \lvert \lambda_i-\lambda\rvert$$ It now follows (10.27), that is $$\min\limits_i \lvert \lambda_i-\lambda\rvert \lVert V_ky\rVert^2 \le \lVert y\rVert \lVert \hat{v}_{k+1}\rVert\lVert V_ky\rVert$$

Let me know whether you need any futher explanation. And don't worry, I will not claim the 500 reputation bounty valid when I first answered.

• Thanks a lot for your help. Sorry for the delay. I was traveling. At a quick look I think you are right. I will comment if I still have question :) – River Jul 16 '17 at 13:27

I think it is a typo and the author meant to use $\max$ instead of $\min$.

$$\sum_\limits{i=1}^m (\lambda_i-\lambda)\vert P_i(V_ky)\vert^2$$ $$\le \sum_\limits{i=1}^m \vert(\lambda_i-\lambda)\vert\vert P_i(V_ky)\vert^2$$ $$\le \sum_\limits{i=1}^m\max\vert\lambda_i-\lambda\vert\vert P_i(V_ky)\vert^2$$ $$= \max_\limits{1\le i \le m}\vert\lambda_i-\lambda\vert\sum_\limits{i=1}^m\vert P_i(V_ky)\vert^2$$ $$\le \max_\limits{1\le i \le m}\vert\lambda_i-\lambda\vert\lVert V_ky\rVert^2$$

This works effortlessly, and any version with $\min$ appears to be false.

• please, consider reading my proof – trying Jul 15 '17 at 15:55