# Numerical Analysis/Matrix norm
## Definitions

The term Norm is often used without additional qualification to refer to a particular type of norm such as a Matrix norm or a Vector norm. Most commonly the unqualified term Norm refers to flavor of Vector norm technically known as the L2 norm. This norm is variously denoted $\left\|x\right\|_{2}$, $\left\|x\right\|$, or $|x|$ and give the length of an n-vector $x=(x_{1},x_{2},...x_{n}).$
Norms provide vector spaces and their linear operators with measures of size, length and distance more general than those we already use routinely in everyday life.

## Induced Norm

If vector norms on K$^m$ and K$^n$ are given (K is field of real or complex numbers), then one defines the corresponding induced norm or operator norm on the space of m-by-n matrices as the following maxima:
    ${\begin{aligned}\|A\|&=\max\{\|Ax\|:x\in K^{n}{\mbox{ with }}\|x\|=1\}\\&=\max \left\{{\frac {\|Ax\|}{\|x\|}}:x\in K^{n}{\mbox{ with }}x\neq 0\right\}.\end{aligned}}$
If m = n and one uses the same norm on the domain and the range, then the induced operator norm is a sub-multiplicative matrix norm.
The operator norm corresponding to the p-norm for vectors is:
    $\left\|A\right\|_{p}=\max \limits _{x\neq 0}{\frac {\left\|Ax\right\|_{p}}{\left\|x\right\|_{p}}}.$
In the case of $p=1$ and $p=\infty$, the norms can be computed as:
    $\left\|A\right\|_{1}=\max \limits _{1\leq j\leq n}\sum _{i=1}^{m}|a_{ij}|,$ which is simply the maximum absolute column sum of the matrix.
    $\left\|A\right\|_{\infty }=\max \limits _{1\leq i\leq m}\sum _{j=1}^{n}|a_{ij}|,$ which is simply the maximum absolute row sum of the matrix.

### Theorem: Induced Norms are really norms

Proof:
To show $\|A\|=\max _{\|x\|=1}\|Ax\|$ is a matrix norm we need to show several things.
If $A=0$ then $\left\|Ax\right\|=0$ for all vectors x with $\left\|x\right\|=1$ and so $\|A\|=0$.
If $\|A\|=0$ then $\|Ax\|=0$ for all $x$. Using $x=(1,0,...,0)^{t}$, $x=(0,1,0,...,0)^{t},...,$ and $x=(0,...,0,1)^{t}$ successively implies that each column of $A$ is zero. Thus, $\left\|A\right\|=0$ if and only if $A=0.$
Using the definition of Induced norms and the properties of the vector norm we have,
    $\|\alpha A\|=\max \limits _{\left\|x\right\|_{=1}}\|\alpha Ax\|=|\alpha |\max \limits _{\left\|x\right\|_{=1}}\left\|\ Ax\right\|=|\alpha |.\left\|A\right\|\,.$
Again using the definition of Induced norms and the triangle inequality for the vector norm, we have
    $\|A+B\|=\max \limits _{\|x\|=1}\|(A+B)x\|\leq \max \limits _{\|x\|=1}(\|Ax\|+\|Bx\|)\leq \max \limits _{\|x\|=1}\|Ax\|+\max \limits _{\|x\|=1}\|Bx\|=\|A\|+\|B\|\,.$

### Theorem: Induced norms are submultiplicative

Proof:
We want to show $\|AB\|\leq \|A\|\|B\|$. We have
    $\|AB\|=\max \limits _{\|x\|_{=1}}\|(AB)x\|=\max \limits _{\|x\|_{=1}}\|A(Bx)\|\leq \max \limits _{\|x\|=1}\|A\|\|Bx\|=\|A\|\max \limits _{\|x\|=1}\|Bx\|=\|A\|\|B\|$.

## Derivation of A$_∞$ formula

Proof::
First we show that
    $\left\|A\right\|_{\infty }=\max \limits _{\left\|x\right\|_{\infty }=1}\left\|AX\right\|_{\infty }\leq \max \limits _{1\leq i\leq n}\sum _{j=1}^{n}|a_{ij}|.$         ( 1)
Let $x$ be an n-dimensional vector with $1=\left\|x\right\|_{\infty }=\max \limits _{1\leq i\leq n}|{x_{i}}|.$ Since $Ax$ is also an n-dimensional vector,
    $\left\|Ax\right\|_{\infty }=\max \limits _{1\leq i\leq n}|{Ax}_{i}|=\max \limits _{1\leq i\leq n}\left|\sum _{j=1}^{n}a_{ij}x_{j}\right|\leq \max \limits _{1\leq i\leq n}\sum _{j=1}^{n}|a_{ij}|\max \limits _{1\leq i\leq n}|{x_{i}}|.$
But $\max \limits _{1\leq i\leq n}=\left\|x_{j}\right\|=\left\|X\right\|_{\infty }=1,$ so
    $\left\|Ax\right\|_{\infty }\leq \max \limits _{1\leq i\leq n}\sum _{j=1}^{n}|a_{ij}|$
and we have shown (1).
Now we will show the opposite inequality, that
    $\left\|A\right\|_{\infty }=\max \limits _{\left\|x\right\|_{\infty }=1}\left\|AX\right\|_{\infty }\geq \max \limits _{1\leq i\leq n}\sum _{j=1}^{n}|a_{ij}|.$         ( 2)
Let p be an integer with
    $\sum _{j=1}^{n}|a_{pj}|=\max \limits _{1\leq i\leq n}\sum _{j=1}^{n}|a_{ij}|,$
and $x$ be the vector with components
    $x_{j}={\begin{cases}1,&{\text{if}}\qquad a_{pj}\geq 0,\\-1,&{\text{if}}\qquad a_{pj}<0.\end{cases}}$
Then $\|x\|_{\infty }=1$ and $a_{pj}x_{j}=|a_{pj}|,$ for all $j=1,2,...,n,$ so
    $\left\|Ax\right\|_{\infty }=\max \limits _{1\leq i\leq n}\left|\sum _{j=1}^{n}a_{ij}x_{j}\right|\geq \left|\sum _{j=1}^{n}a_{pj}x_{j}\right|=\left|\sum _{j=1}^{n}|a_{pj}|\right|=\max \limits _{1\leq i\leq n}\sum _{j=1}^{n}|a_{ij}|$
and we have shown (2). Together, (1) and (2) yield
    $\left\|A\right\|_{\infty }=\max \limits _{1\leq i\leq n}\sum _{j=1}^{n}|a_{ij}|\,.$

### Example computing A$_∞$

If
    $\mathbf {A} ={\begin{bmatrix}1&2&-1\\0&3&-1\\5&-1&1\\\end{bmatrix}},$
Solution:
    $\sum _{j=1}^{3}|a_{1j}|=|1|+|2|+|-1|=4,\qquad \sum _{j=1}^{3}|a_{2j}|=|0|+|3|+|-1|=4,$
and
    $\sum _{j=1}^{3}|a_{3j}|=|5|+|-1|+|1|=7$
so, $\left\|A\right\|_{\infty }=\max\{4,4,7\}=7.$

## Equivalence Of Norms

Equivalence Of Norms is defined as:
This is true because the vector space $K^{m\times n}$ has the finite dimension $m\times n$.

### Examples of matrix norm equivalence

For matrix $A\in \mathbb {R} ^{m\times n}$ the following inequalities hold
* $\|A\|_{2}\leq \|A\|_{F}\leq {\sqrt {r}}\|A\|_{2}$, where $r$ is the rank of $A$
* $\|A\|_{F}\leq \|A\|_{*}\leq {\sqrt {r}}\|A\|_{F}$, where $r$ is the rank of $A$
* $\|A\|_{\text{max}}\leq \|A\|_{2}\leq {\sqrt {mn}}\|A\|_{\text{max}}$
* ${\frac {1}{\sqrt {n}}}\|A\|_{\infty }\leq \|A\|_{2}\leq {\sqrt {m}}\|A\|_{\infty }$
* ${\frac {1}{\sqrt {m}}}\|A\|_{1}\leq \|A\|_{2}\leq {\sqrt {n}}\|A\|_{1}.$
Here, ||·||$_p$ refers to the matrix norm induced by the vector p-norm.

#### Example

We will show some of these norm equivalences for the matrix
$\mathbf {A} ={\begin{bmatrix}1&-2&3\\-4&5&-6\\7&-8&9\\\end{bmatrix}}$
Solution:
First we compute several norms:
* $\rho (A)\approx |16.1168|=16.1168,$
* $\|A\|_{\infty }=\max\{|1|+|-2|+|3|,|-4|+|5|+|-6|,|7|+|-8|+|9|\}=24,$
* $\|A\|_{1}=\max\{|1|+|-4|+|7|,|-2|+|5|+|-8|,|3|+|-6|+|9|\}=18,$
* $\|A\|_{2}={\sqrt {\rho (AA^{*})}}\approx {\sqrt {283.8585}}\approx 16.8481,$
* ${\sqrt {r}}\|A\|_{2}={\sqrt {r}}{\sqrt {\rho (AA^{*})}}\approx {\sqrt {3}}{\sqrt {283.8585}}\approx 29.1818,$ Where r is the rank of the matrix.
* $\|A\|_{F}={\sqrt {|1|^{2}+|-2|^{2}+|3|^{2}+|-4|^{2}+|5|^{2}+|-6|^{2}+|7|^{2}+|-8|^{2}+|9|^{2}+}}={\sqrt {285}}\approx 16.8819,$
* $\|A\|_{\max }=\max\{|1|,|-2|,|3|,|-4|,|5|,|-6|,|7|,|-8|,|9|\}=|9|.$
We can then verify the norm equivalence
    $\left\|A\right\|_{max}<\rho (A)<\left\|A\right\|_{2}<\left\|A\right\|_{F}<\left\|A\right\|_{1}<\left\|A\right\|_{\infty }<{\sqrt {r}}\|A\|_{2}.$
with our numbers
    $|9|<16.1168<16.8481<16.8819<18<24<29.1818,$
and
    $\|A\|_{2}\leq \|A\|_{F}\leq {\sqrt {r}}\|A\|_{2}$
with our numbers
    $16.8481\leq \ 16.8819\leq \ 29.1818.$