MATH 417 Lecture 22

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

Norms

Triangle and Cauchy/Schartz

Theorem. [Triangle Inequality] ${\Vert x+y\Vert }_2\le {\left|x\right|}_2+{\Vert y\Vert }_2$

Proof. ${\Vert x+y\Vert }_2=\sqrt{⟨x+y,x+y⟩}\le \Vert x\Vert +\Vert y\Vert =\sqrt{⟨x,x⟩}+\sqrt{⟨y,y⟩}$, so we square both sides.

$\begin{array}{rl}\sqrt{⟨x+y,x+y⟩}& \le \sqrt{⟨x,x⟩}+\sqrt{⟨y,y⟩}\\ ⟨x+y,x+y⟩& \le ⟨x,x⟩+2\sqrt{⟨x,x⟩⟨y,y⟩}+⟨y,y⟩\\ ⟨x,x⟩+2⟨x,y⟩+⟨y,y⟩& \le ⟨x,x⟩+2\sqrt{⟨x,x⟩⟨y,y⟩}+⟨y,y⟩\\ ⟨x,y⟩& \le \sqrt{⟨x,x⟩⟨y,y⟩}\end{array}$

Hence

${\left|⟨x,y⟩\right|}^2\le ⟨x,x⟩⟨y,y⟩$

This is the Cauchy Inequality

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

$\begin{array}{rl}f(t)& ={\Vert \overrightarrow{x}+t\overrightarrow{y}\Vert }_2^2\ge 0\\ & =⟨x+ty,x+ty⟩& =⟨x,x⟩+⟨x,ty⟩+⟨ty,x⟩+⟨ty,ty⟩\\ & =\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& =⟨y,y⟩t^2+2⟨x,y⟩t+⟨x,x⟩& =a{t}^2+bt+c\end{array}$

We need this quadratic to be greater than zero for all $\mathbb{ℝ}$, so we take the discriminant to be less than zero:

$\begin{array}{rl}0& \ge b^2-4ac\\ 0& \ge {\left(2⟨x,y⟩\right)}^2-4⟨y,y⟩⟨x,x⟩\\ 0& \ge 4{\left|⟨x,y⟩\right|}^2-4⟨y,y⟩⟨x,x⟩\\ 0& \ge {\left|⟨x,y⟩\right|}^2-⟨y,y⟩⟨x,x⟩\\ {\left|⟨x,y⟩\right|}^2& \ge ⟨y,y⟩⟨x,x⟩\end{array}$

quod erat demonstrandum

Matrix Norms

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

We define $\Vert A\Vert :=\underset{\Vert x=1\Vert }{\max }\Vert Ax\Vert =\underset{x\ne 0}{\max }\frac{\Vert Ax\Vert }{\Vert x\Vert }$

This is called the matrix norm induced by $\Vert \cdot \Vert$ on ${\mathbb{ℝ}}^n$.

In particular, ${\Vert A\Vert }_2:=\underset{{\Vert x\Vert }_p=1}{\max }{\Vert Ax\Vert }_p$

Theorem. $\Vert A\Vert$ is a norm.

Proof. The first criterion is that $\Vert A\Vert \ge 0$ and $\Vert Ax\Vert =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 $Ax$ 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 $\Vert \alpha A\Vert =\left|\alpha \right|\Vert A\Vert$

By definition, $\Vert \alpha A\Vert =\underset{\Vert x\Vert =1}{\max }\Vert \alpha Ax\Vert =\underset{\Vert x\Vert =1}{\max }\left|\alpha \right|\Vert Ax\Vert =\left|\alpha \right|\Vert Ax\Vert$

---

Finally, show that $\Vert A+B\Vert \le \Vert A\Vert +\Vert B\Vert$.

We have $\Vert (A+B)x\Vert =\Vert Ax+Bx\Vert \le \Vert Ax\Vert +\Vert Bx\Vert$.

quod erat demonstrandum

Example

$A=\left[\begin{array}{cc}2& 0\\ 0& 1\end{array}\right]$

$\Vert A\Vert =\max \Vert Ax\Vert$, where $x$ is a member of the unit circle.

We have $Ax=\left[\begin{array}{c}2x_1\\ x_2\end{array}\right]$ defining an ellipse by transformation.

${\Vert A\Vert }_2=2=\text{largest eigenvalue}$

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

Theorem. if $A=A^T$, then $\Vert A_2\Vert =\rho (A)$

Proof. $\Vert A_2\Vert =\sqrt{\rho (A^{T}A)}={\lambda }^{*}$

quod erat demonstrandum

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

Theorem. ${\Vert A\Vert }_{\mathrm{\infty }}$ is the max row sum of the matrix $d$.

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

Proof. Take $\overrightarrow{x}=⟨x_1,\dots ,x_n⟩$ such that $\underset{i}{\max }\left|x_i\right|=1$. We are going to compute ${\Vert Ax\Vert }_{\mathrm{\infty }}$ and take the max entry.

$\left[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ ⋮& \ddots & \ddots & ⋮\\ a_{n1}& a_{n2}& \dots & a_{nn}\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]={\Vert \left[\begin{array}{c}{a}_{11}{x}_1+\dots +a_{1n}{x}_n\\ ⋮\\ a_{i1}{x}_1+\dots +a_{in}{x}_i\\ ⋮\\ a_{n1}{x}_1+\dots +a_{nn}{x}_n\end{array}\right]\Vert }_{\mathrm{\infty }}=\underset{i}{\max }\left|\sum _{j=1}^n{a}_{ij}{x}_j\right|\le \underset{i}{\max }\sum _{j=1}^n\left|a_{ij}\right|=d$

Hence $\Vert A\Vert \le d$

Now we show the symmetric, i.e. $\Vert A\Vert \ge d$.

We have $\underset{i}{\max }\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=\{\begin{array}{ll}+1& a_{pj}>0\\ -1& a_{pj}<0\\ 0& a_{pj}=0\end{array}$

$\Vert x^{*}\Vert =1$ if $A$ is not the zero matrix.

Thus row $p$ will be the largest entry in $A{\overrightarrow{x}}^{*}$:

$d\le {\Vert A{x}^{*}\Vert }_{\mathrm{\infty }}\le {\Vert A\Vert }_{\mathrm{\infty }}$

quod erat demonstrandum