MATH 417 Lecture 22
« previous | Thursday, April 10, 2014 | next »
Norms
Triangle and Cauchy/Schartz
Theorem. [Triangle Inequality]
Proof. , so we square both sides.
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{align} \sqrt{\left\langle x+y, x+y \right\rangle} &\le \sqrt{\left\langle x,x \right\rangle} + \sqrt{\left\langle y,y \right\rangle} \\ \left\langle x+y, x+y \right\rangle &\le \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 &\le \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 &\le \sqrt{ \left\langle x,x \right\rangle \, \left\langle y,y \right\rangle } \end{align}}
Hence
This is the Cauchy Inequality
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 t \in \mathbb{R}} . Then
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{align} f(t) &= \left\| \vec{x} + t \, \vec{y} \right\|_2^2 \ge 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{align}}
We need this quadratic to be greater than zero for all 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 \mathbb{R}} , so we take the discriminant to be less than zero:
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{align} 0 &\ge b^2 - 4a\,c \\ 0 &\ge \left( 2\left\langle x,y \right\rangle \right)^2 - 4 \, \left\langle y,y \right\rangle \, \left\langle x,x \right\rangle \\ 0 &\ge 4 \left| \left\langle x,y \right\rangle \right|^2 - 4 \, \left\langle y,y \right\rangle \, \left\langle x,x \right\rangle \\ 0 &\ge \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 &\ge \left\langle y,y \right\rangle \, \left\langle x,x \right\rangle \end{align}}
Matrix Norms
Let 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} be a 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 n \times n} matrix over 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 \mathbb{R}} ( 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 \in M_n(\mathbb{R})} ).
We define 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\| := \max_{ \left\| x = 1 \right\| }{ \left\| A \, x \right\|} = \max_{x \ne 0} \frac{ \left\| A \, x \right\| }{ \left\| x \right\| }}
This is called the matrix norm induced by 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\| \cdot \right\|} on 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 \mathbb{R}^n} .
In particular, 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\|_2 := \max_{ \left\| x \right\|_p = 1 }{ \left\| A \, x \right\|_p }}
Theorem. 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\|} is a norm.
Proof. The first criterion is 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 \left\| A \right\| \ge 0} and 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\| = 0} only 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 the zero matrix.
Seeking a contradiction, assume 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 A} has a nonzero 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 a_{ij}} . Choose 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} to be all zeroes except at position 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 j} . Then 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 \, x} will have a nonzero entry at position 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 i} equal to 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_{ij}} The norm of this vector must be strictly positive. Contradiction.
Next we prove 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 \left\| \alpha \, A \right\| = \left| \alpha \right| \, \left\| A \right\|}
By definition, 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\| \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 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 + B \right\| \le \left\| A \right\| + \left\| B \right\|} .
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 \left\| (A + B) \, x \right\| = \left\| A \, x + B \, x \right\| \le \left\| A \, x \right\| + \left\| B \, x \right\|} .
Example
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 = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix}}
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\| = \max \left\| A \, x \right\|} , where 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} is a member of the unit circle.
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 A \, x = \begin{bmatrix} 2 \, x_1 \\ x_2 \end{bmatrix}} defining an ellipse by transformation.
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\|_2 = 2 = \mbox{largest eigenvalue}}
We call 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 \rho(A) = \max_i {\lambda_i}} the spectral radius.
Theorem. 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 = A^T} , then 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_2 \right\| = \rho(A)}
Proof. 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_2 \right\| = \sqrt{\rho(A^T \, A)} = \lambda^*}
For 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}
, we have the set for 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\|_\infty = 1}
defining a box circumscribing the unit circle. Performing the same transformation gives a rectangle 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 \left\| A \, X \right\| = 2}
Theorem. 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} 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} .
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}}