Skip to main content
MathOverflow

Return to Answer

Streamlined the proof.
Source Link
Hans
Hans
  • 2.2k
  • 15
  • 29

It is a simple and repeated application of $\min$ and $\max$ operators.

$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op},\,\forall v\in R^n\wedge |v|=1.$$ Given $V$ where $\dim(V)=i$, $$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op},\,\forall v\in V\wedge |v|=1,$$ and $$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ Thenthen $$\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$$$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op}$$ and $$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$$$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ In other words $$\lambda_i(A+B)\le\lambda_i(A)+\|B\|_{op}.$$ Similarly, we can prove $\lambda_i(A)-\|B\|_{op}\le\lambda_i(A+B)$ and reach the desired inequality.

It is a simple and repeated application of $\min$ and $\max$ operators.

$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op},\,\forall v\in R^n\wedge |v|=1.$$ Given $V$ where $\dim(V)=i$, $$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op},\,\forall v\in V\wedge |v|=1,$$ and $$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ Then $$\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ and $$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ In other words $$\lambda_i(A+B)\le\lambda_i(A)+\|B\|_{op}.$$ Similarly, we can prove $\lambda_i(A)-\|B\|_{op}\le\lambda_i(A+B)$ and reach the desired inequality.

It is a simple and repeated application of $\min$ and $\max$ operators.

$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op},\,\forall v\in R^n\wedge |v|=1.$$ Given $V$ where $\dim(V)=i$, $$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op},\,\forall v\in V\wedge |v|=1,$$ then $$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op}$$ and $$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ In other words $$\lambda_i(A+B)\le\lambda_i(A)+\|B\|_{op}.$$ Similarly, we can prove $\lambda_i(A)-\|B\|_{op}\le\lambda_i(A+B)$ and reach the desired inequality.

Added the constraint $v$ norm being $1$ in the first inequality.
Source Link
Hans
Hans
  • 2.2k
  • 15
  • 29

It is a simple and repeated application of $\min$ and $\max$ operators.

$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op}, \forall v\in R^n.$$$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op},\,\forall v\in R^n\wedge |v|=1.$$ Given $V$ where $\dim(V)=i$, $$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op}, \forall v\in V,$$$$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op},\,\forall v\in V\wedge |v|=1,$$ and $$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ Then $$\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ and $$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ In other words $$\lambda_i(A+B)\le\lambda_i(A)+\|B\|_{op}.$$ Similarly, we can prove $\lambda_i(A)-\|B\|_{op}\le\lambda_i(A+B)$ and reach the desired inequality.

It is a simple and repeated application of $\min$ and $\max$ operators.

$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op}, \forall v\in R^n.$$ Given $V$ where $\dim(V)=i$, $$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op}, \forall v\in V,$$ and $$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ Then $$\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ and $$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ In other words $$\lambda_i(A+B)\le\lambda_i(A)+\|B\|_{op}.$$ Similarly, we can prove $\lambda_i(A)-\|B\|_{op}\le\lambda_i(A+B)$ and reach the desired inequality.

It is a simple and repeated application of $\min$ and $\max$ operators.

$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op},\,\forall v\in R^n\wedge |v|=1.$$ Given $V$ where $\dim(V)=i$, $$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op},\,\forall v\in V\wedge |v|=1,$$ and $$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ Then $$\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ and $$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ In other words $$\lambda_i(A+B)\le\lambda_i(A)+\|B\|_{op}.$$ Similarly, we can prove $\lambda_i(A)-\|B\|_{op}\le\lambda_i(A+B)$ and reach the desired inequality.

deleted 2 characters in body
Source Link
Hans
Hans
  • 2.2k
  • 15
  • 29

It is a simple and repeated application of $\min$ and $\max$ operators.

$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op}, \forall v\in R^n.$$ Given $V$ where $\dim(V)=i$, $$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op}, \forall v\in V,$$ and $$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ Then $$\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ and $$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ In other words $$\lambda_i(A+B)\le\lambda_i(A)+\|B\|_{op}.$$ Similarly, we can prove $\lambda_i(A)-|B|_{op}\le\lambda_i(A+B),$$$\lambda_i(A)-\|B\|_{op}\le\lambda_i(A+B)$ and reach the desired inequality.

It is a simple and repeated application of $\min$ and $\max$ operators.

$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op}, \forall v\in R^n.$$ Given $V$ where $\dim(V)=i$, $$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op}, \forall v\in V,$$ and $$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ Then $$\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ and $$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ In other words $$\lambda_i(A+B)\le\lambda_i(A)+\|B\|_{op}.$$ Similarly, we can prove $\lambda_i(A)-|B|_{op}\le\lambda_i(A+B),$$ and reach the desired inequality.

It is a simple and repeated application of $\min$ and $\max$ operators.

$$v^*(A+B)v=v^*Av+v^*Bv\le v^*Av+\|B\|_{op}, \forall v\in R^n.$$ Given $V$ where $\dim(V)=i$, $$\min_{u\in V,|u|=1}u^*(A+B)u\le v^*(A+B)v\le v^*Av+\|B\|_{op}, \forall v\in V,$$ and $$\min_{u\in V,|u|=1}u^*(A+B)u\le \min_{v\in V,|v|=1}v^*Av+\|B\|_{op}.$$ Then $$\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ and $$\max_{\dim(U)=i}\min_{u\in V,|u|=1}u^*(A+B)u\le \max_{\dim(V)=i}\min_{v\in V,|v|=1}v^*Av+\|B\|_{op},$$ In other words $$\lambda_i(A+B)\le\lambda_i(A)+\|B\|_{op}.$$ Similarly, we can prove $\lambda_i(A)-\|B\|_{op}\le\lambda_i(A+B)$ and reach the desired inequality.

Added the gist of the proof.
Source Link
Hans
Hans
  • 2.2k
  • 15
  • 29
Source Link
Hans
Hans
  • 2.2k
  • 15
  • 29