MATH 417 Lecture 22

« previous | Thursday, April 10, 2014 | next »

Norms

Triangle and Cauchy/Schartz

Theorem. [Triangle Inequality] $\left\|x+y\right\|_{2}\leq \left|x\right|_{2}+\left\|y\right\|_{2}$

Proof. $\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.

${\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

\left|\left\langle x,y\right\rangle \right|^{2}\leq \left\langle x,x\right\rangle \,\left\langle y,y\right\rangle

This is the Cauchy Inequality

take $t\in \mathbb {R}$ . Then

${\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 $\mathbb {R}$ , so we take the discriminant to be less than zero:

${\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}}$

quod erat demonstrandum

Matrix Norms

Let $A$ be a $n\times n$ matrix over $\mathbb {R}$ ( $A\in M_{n}(\mathbb {R} )$ ).

We define $\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 $\left\|\cdot \right\|$ on $\mathbb {R} ^{n}$ .

In particular, $\left\|A\right\|_{2}:=\max _{\left\|x\right\|_{p}=1}{\left\|A\,x\right\|_{p}}$

Theorem. $\left\|A\right\|$ is a norm.

Proof. The first criterion is that $\left\|A\right\|\geq 0$ and $\left\|A\,x\right\|=0$ only if $A$ is the zero matrix.

Seeking a contradiction, assume that $A$ has a nonzero entry $a_{ij}$ . Choose $x$ to be all zeroes except at position $j$ . Then $A\,x$ will have a nonzero entry at position $i$ equal to $a_{ij}$ The norm of this vector must be strictly positive. Contradiction.

By definition, $\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\|$

---

quod erat demonstrandum

Example

$A={\begin{bmatrix}2&0\\0&1\end{bmatrix}}$

$\left\|A\right\|=\max \left\|A\,x\right\|$ , where $x$ is a member of the unit circle.

We have $A\,x={\begin{bmatrix}2\,x_{1}\\x_{2}\end{bmatrix}}$ defining an ellipse by transformation.

$\left\|A\right\|_{2}=2={\mbox{largest eigenvalue}}$

We call $\rho (A)=\max _{i}{\lambda _{i}}$ the spectral radius.

Theorem. if $A=A^{T}$ , then $\left\|A_{2}\right\|=\rho (A)$

Proof. $\left\|A_{2}\right\|={\sqrt {\rho (A^{T}\,A)}}=\lambda ^{*}$

quod erat demonstrandum

For $\left\|A\right\|_{\infty }$ , we have the set for $\left\|x\right\|_{\infty }=1$ defining a box circumscribing the unit circle. Performing the same transformation gives a rectangle such that $\max \left\|A\,X\right\|=2$

Theorem. $\left\|A\right\|_{\infty }$ is the max row sum of the matrix $d$ .

\left\|A\right\|_{\infty }=d=\max _{i}\sum _{j=1}^{n}\left|a_{ij}\right|

Proof. Take ${\vec {x}}=\left\langle x_{1},\ldots ,x_{n}\right\rangle$ such that $\max _{i}\left|x_{i}\right|=1$ . We are going to compute $\left\|A\,x\right\|_{\infty }$ and take the max entry.

${\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 $\left\|A\right\|\leq d$

Now we show the symmetric, i.e. $\left\|A\right\|\geq d$ .

We have $\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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ve{x}^* = \left\langle x_1 , \vdots , x_n \right\rangle} such that $x_{j}={\begin{cases}+1&a_{pj}>0\\-1&a_{pj}<0\\0&a_{pj}=0\end{cases}}$