« previous | Thursday, April 10, 2014 | next »
Theorem. [Triangle Inequality] ‖ x + y ‖ 2 ≤ | x | 2 + ‖ y ‖ 2 {\displaystyle \left\|x+y\right\|_{2}\leq \left|x\right|_{2}+\left\|y\right\|_{2}}
Proof. ‖ x + y ‖ 2 = ⟨ x + y , x + y ⟩ ≤ ‖ x ‖ + ‖ y ‖ = ⟨ x , x ⟩ + ⟨ y , y ⟩ {\displaystyle \left\|x+y\right\|_{2}={\sqrt {\left\langle x+y,x+y\right\rangle }}\leq \left\|x\right\|+\left\|y\right\|={\sqrt {\left\langle x,x\right\rangle }}+{\sqrt {\left\langle y,y\right\rangle }}} , so we square both sides.
⟨ x + y , x + y ⟩ ≤ ⟨ x , x ⟩ + ⟨ y , y ⟩ ⟨ x + y , x + y ⟩ ≤ ⟨ x , x ⟩ + 2 ⟨ x , x ⟩ ⟨ y , y ⟩ + ⟨ y , y ⟩ ⟨ x , x ⟩ + 2 ⟨ x , y ⟩ + ⟨ y , y ⟩ ≤ ⟨ x , x ⟩ + 2 ⟨ x , x ⟩ ⟨ y , y ⟩ + ⟨ y , y ⟩ ⟨ x , y ⟩ ≤ ⟨ x , x ⟩ ⟨ y , y ⟩ {\displaystyle {\begin{aligned}{\sqrt {\left\langle x+y,x+y\right\rangle }}&\leq {\sqrt {\left\langle x,x\right\rangle }}+{\sqrt {\left\langle y,y\right\rangle }}\\\left\langle x+y,x+y\right\rangle &\leq \left\langle x,x\right\rangle +2{\sqrt {\left\langle x,x\right\rangle \,\left\langle y,y\right\rangle }}+\left\langle y,y\right\rangle \\\left\langle x,x\right\rangle +2\left\langle x,y\right\rangle +\left\langle y,y\right\rangle &\leq \left\langle x,x\right\rangle +2{\sqrt {\left\langle x,x\right\rangle \,\left\langle y,y\right\rangle }}+\left\langle y,y\right\rangle \\\left\langle x,y\right\rangle &\leq {\sqrt {\left\langle x,x\right\rangle \,\left\langle y,y\right\rangle }}\end{aligned}}}
Hence
This is the Cauchy Inequality
take t ∈ R {\displaystyle t\in \mathbb {R} } . Then
f ( t ) = ‖ x → + t y → ‖ 2 2 ≥ 0 = ⟨ x + t y , x + t y ⟩ = ⟨ x , x ⟩ + ⟨ x , t y ⟩ + ⟨ t y , x ⟩ + ⟨ t y , t y ⟩ = ∑ i = 1 n x i 2 + ( 2 ∑ i = 1 n x i y i ) t + ( ∑ i = 1 n y i 2 ) t 2 = ⟨ y , y ⟩ t 2 + 2 ⟨ x , y ⟩ t + ⟨ x , x ⟩ = a t 2 + b t + c {\displaystyle {\begin{aligned}f(t)&=\left\|{\vec {x}}+t\,{\vec {y}}\right\|_{2}^{2}\geq 0\\&=\left\langle x+t\,y,x+t\,y\right\rangle &=\left\langle x,x\right\rangle +\left\langle x,t\,y\right\rangle +\left\langle t\,y,x\right\rangle +\left\langle t\,y,t\,y\right\rangle \\&=\sum _{i=1}^{n}x_{i}^{2}+\left(2\,\sum _{i=1}^{n}x_{i}\,y_{i}\right)\,t+\left(\sum _{i=1}^{n}y_{i}^{2}\right)\,t^{2}&=\left\langle y,y\right\rangle \,t^{2}+2\left\langle x,y\right\rangle \,t+\left\langle x,x\right\rangle &=a\,t^{2}+b\,t+c\end{aligned}}}
We need this quadratic to be greater than zero for all R {\displaystyle \mathbb {R} } , so we take the discriminant to be less than zero:
0 ≥ b 2 − 4 a c 0 ≥ ( 2 ⟨ x , y ⟩ ) 2 − 4 ⟨ y , y ⟩ ⟨ x , x ⟩ 0 ≥ 4 | ⟨ x , y ⟩ | 2 − 4 ⟨ y , y ⟩ ⟨ x , x ⟩ 0 ≥ | ⟨ x , y ⟩ | 2 − ⟨ y , y ⟩ ⟨ x , x ⟩ | ⟨ x , y ⟩ | 2 ≥ ⟨ y , y ⟩ ⟨ x , x ⟩ {\displaystyle {\begin{aligned}0&\geq b^{2}-4a\,c\\0&\geq \left(2\left\langle x,y\right\rangle \right)^{2}-4\,\left\langle y,y\right\rangle \,\left\langle x,x\right\rangle \\0&\geq 4\left|\left\langle x,y\right\rangle \right|^{2}-4\,\left\langle y,y\right\rangle \,\left\langle x,x\right\rangle \\0&\geq \left|\left\langle x,y\right\rangle \right|^{2}-\left\langle y,y\right\rangle \,\left\langle x,x\right\rangle \\\left|\left\langle x,y\right\rangle \right|^{2}&\geq \left\langle y,y\right\rangle \,\left\langle x,x\right\rangle \end{aligned}}}
Let A {\displaystyle A} be a n × n {\displaystyle n\times n} matrix over R {\displaystyle \mathbb {R} } ( A ∈ M n ( R ) {\displaystyle A\in M_{n}(\mathbb {R} )} ).
We define ‖ A ‖ := max ‖ x = 1 ‖ ‖ A x ‖ = max x ≠ 0 ‖ A x ‖ ‖ x ‖ {\displaystyle \left\|A\right\|:=\max _{\left\|x=1\right\|}{\left\|A\,x\right\|}=\max _{x\neq 0}{\frac {\left\|A\,x\right\|}{\left\|x\right\|}}}
This is called the matrix norm induced by ‖ ⋅ ‖ {\displaystyle \left\|\cdot \right\|} on R n {\displaystyle \mathbb {R} ^{n}} .
In particular, ‖ A ‖ 2 := max ‖ x ‖ p = 1 ‖ A x ‖ p {\displaystyle \left\|A\right\|_{2}:=\max _{\left\|x\right\|_{p}=1}{\left\|A\,x\right\|_{p}}}
Theorem. ‖ A ‖ {\displaystyle \left\|A\right\|} is a norm.
Proof. The first criterion is that ‖ A ‖ ≥ 0 {\displaystyle \left\|A\right\|\geq 0} and ‖ A x ‖ = 0 {\displaystyle \left\|A\,x\right\|=0} only if A {\displaystyle A} is the zero matrix.
Seeking a contradiction, assume that A {\displaystyle A} has a nonzero entry a i j {\displaystyle a_{ij}} . Choose x {\displaystyle x} to be all zeroes except at position j {\displaystyle j} . Then A x {\displaystyle A\,x} will have a nonzero entry at position i {\displaystyle i} equal to a i j {\displaystyle a_{ij}} The norm of this vector must be strictly positive. Contradiction.
Next we prove that ‖ α A ‖ = | α | ‖ A ‖ {\displaystyle \left\|\alpha \,A\right\|=\left|\alpha \right|\,\left\|A\right\|}
By definition, ‖ α A ‖ = max ‖ x ‖ = 1 ‖ α A x ‖ = max ‖ x ‖ = 1 | α | ‖ A x ‖ = | α | ‖ A x ‖ {\displaystyle \left\|\alpha \,A\right\|=\max _{\left\|x\right\|=1}{\left\|\alpha \,A\,x\right\|}=\max _{\left\|x\right\|=1}{\left|\alpha \right|\,\left\|A\,x\right\|}=\left|\alpha \right|\,\left\|A\,x\right\|}
---
Finally, show that ‖ A + B ‖ ≤ ‖ A ‖ + ‖ B ‖ {\displaystyle \left\|A+B\right\|\leq \left\|A\right\|+\left\|B\right\|} .
We have ‖ ( A + B ) x ‖ = ‖ A x + B x ‖ ≤ ‖ A x ‖ + ‖ B x ‖ {\displaystyle \left\|(A+B)\,x\right\|=\left\|A\,x+B\,x\right\|\leq \left\|A\,x\right\|+\left\|B\,x\right\|} .
A = [ 2 0 0 1 ] {\displaystyle A={\begin{bmatrix}2&0\\0&1\end{bmatrix}}}
‖ A ‖ = max ‖ A x ‖ {\displaystyle \left\|A\right\|=\max \left\|A\,x\right\|} , where x {\displaystyle x} is a member of the unit circle.
We have A x = [ 2 x 1 x 2 ] {\displaystyle A\,x={\begin{bmatrix}2\,x_{1}\\x_{2}\end{bmatrix}}} defining an ellipse by transformation.
‖ A ‖ 2 = 2 = largest eigenvalue {\displaystyle \left\|A\right\|_{2}=2={\mbox{largest eigenvalue}}}
We call ρ ( A ) = max i λ i {\displaystyle \rho (A)=\max _{i}{\lambda _{i}}} the spectral radius.
Theorem. if A = A T {\displaystyle A=A^{T}} , then ‖ A 2 ‖ = ρ ( A ) {\displaystyle \left\|A_{2}\right\|=\rho (A)}
Proof. ‖ A 2 ‖ = ρ ( A T A ) = λ ∗ {\displaystyle \left\|A_{2}\right\|={\sqrt {\rho (A^{T}\,A)}}=\lambda ^{*}}
For ‖ A ‖ ∞ {\displaystyle \left\|A\right\|_{\infty }} , we have the set for ‖ x ‖ ∞ = 1 {\displaystyle \left\|x\right\|_{\infty }=1} defining a box circumscribing the unit circle. Performing the same transformation gives a rectangle such that max ‖ A X ‖ = 2 {\displaystyle \max \left\|A\,X\right\|=2}
Theorem. ‖ A ‖ ∞ {\displaystyle \left\|A\right\|_{\infty }} is the max row sum of the matrix d {\displaystyle d} .
Proof. Take x → = ⟨ x 1 , … , x n ⟩ {\displaystyle {\vec {x}}=\left\langle x_{1},\ldots ,x_{n}\right\rangle } such that max i | x i | = 1 {\displaystyle \max _{i}\left|x_{i}\right|=1} . We are going to compute ‖ A x ‖ ∞ {\displaystyle \left\|A\,x\right\|_{\infty }} and take the max entry.
[ a 11 a 12 … a 1 n a 21 a 22 … a 2 n ⋮ ⋱ ⋱ ⋮ a n 1 a n 2 … a n n ] [ x 1 x 2 ⋮ x n ] = ‖ [ a 11 x 1 + ⋯ + a 1 n x n ⋮ a i 1 x 1 + ⋯ + a i n x i ⋮ a n 1 x 1 + ⋯ + a n n x n ] ‖ ∞ = max i | ∑ j = 1 n a i j x j | ≤ max i ∑ j = 1 n | a i j | = d {\displaystyle {\begin{bmatrix}a_{11}&a_{12}&\dots &a_{1n}\\a_{21}&a_{22}&\dots &a_{2n}\\\vdots &\ddots &\ddots &\vdots \\a_{n1}&a_{n2}&\dots &a_{nn}\end{bmatrix}}\,{\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}}=\left\|{\begin{bmatrix}a_{11}\,x_{1}+\dots +a_{1n}\,x_{n}\\\vdots \\a_{i1}\,x_{1}+\dots +a_{in}\,x_{i}\\\vdots \\a_{n1}\,x_{1}+\dots +a_{nn}\,x_{n}\end{bmatrix}}\right\|_{\infty }=\max _{i}\left|\sum _{j=1}^{n}a_{ij}\,x_{j}\right|\leq \max _{i}\sum _{j=1}^{n}\left|a_{ij}\right|=d}
Hence ‖ A ‖ ≤ d {\displaystyle \left\|A\right\|\leq d}
Now we show the symmetric, i.e. ‖ A ‖ ≥ d {\displaystyle \left\|A\right\|\geq d} .
We have max i ∑ j = 1 n | a i j | = | a p 1 | + ⋯ + | a p n | {\displaystyle \max _{i}\sum _{j=1}^{n}\left|a_{ij}\right|=\left|a_{p1}\right|+\dots +\left|a_{pn}\right|} . We take a special Failed to parse (unknown function "\ve"): {\displaystyle \ve{x}^* = \left\langle x_1 , \vdots , x_n \right\rangle} such that x j = { + 1 a p j > 0 − 1 a p j < 0 0 a p j = 0 {\displaystyle x_{j}={\begin{cases}+1&a_{pj}>0\\-1&a_{pj}<0\\0&a_{pj}=0\end{cases}}}
‖ x ∗ ‖ = 1 {\displaystyle \left\|x^{*}\right\|=1} if A {\displaystyle A} is not the zero matrix.
Thus row p {\displaystyle p} will be the largest entry in A x → ∗ {\displaystyle A\,{\vec {x}}^{*}} :
d ≤ ‖ A x ∗ ‖ ∞ ≤ ‖ A ‖ ∞ {\displaystyle d\leq \left\|A\,x^{*}\right\|_{\infty }\leq \left\|A\right\|_{\infty }}
, so we square both sides.
. Then
, so we take the discriminant to be less than zero:
