MATH 417 Lecture 22

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

Norms

Triangle and Cauchy/Schartz

Theorem. [Triangle Inequality] 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 \left\| x + y \right\|_2 \le \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.

---

Next we prove that $\left\|\alpha \,A\right\|=\left|\alpha \right|\,\left\|A\right\|$

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

---

Finally, show that $\left\|A+B\right\|\leq \left\|A\right\|+\left\|B\right\|$.

We have $\left\|(A+B)\,x\right\|=\left\|A\,x+B\,x\right\|\leq \left\|A\,x\right\|+\left\|B\,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 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 d} .

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 \left\| A \right\|_\infty = d = \max_{i} \sum_{j = 1}^n \left| a_{ij} \right|}

Proof. Take 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 \vec{x} = \left\langle x_1, \ldots, x_n \right\rangle} such that 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 \max_{i} \left| x_i \right| = 1} . We are going to compute 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 \left\| A \, x \right\|_\infty} and take the max entry.

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 \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| \le \max_{i} \sum_{j=1}^n \left| a_{ij} \right| = d}

Hence 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 \left\| A \right\| \le d}

Now we show the symmetric, i.e. 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 \left\| A \right\| \ge d} .

We have 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 \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 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 x_{j} = \begin{cases} +1 & a_{pj} > 0 \\ -1 & a_{pj} < 0 \\ 0 & a_{pj} = 0 \end{cases}}

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 \left\| x^* \right\| = 1} if 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 A} is not the zero matrix.

Thus row 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 p} will be the largest entry in 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 A \, \vec{x}^*} :

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 d \le \left\| A \, x^* \right\|_\infty \le \left\| A \right\|_{\infty}}

quod erat demonstrandum