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 ${\Vert x\Vert }_2$, $\Vert x\Vert$, 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ⁿ 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{array}{cc}\Vert A\Vert & =\max \{\Vert Ax\Vert :x\in K^n\text{ with }\Vert x\Vert =1\}\\ & =\max \{\frac{\Vert Ax\Vert }{\Vert x\Vert }:x\in K^n\text{ with }x\ne 0\}.\end{array}$

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:

${\Vert A\Vert }_p=\max {\mathrm{\backslash limits}}_{x\ne 0}\frac{{\Vert Ax\Vert }_p}{{\Vert x\Vert }_p}.$

In the case of $p=1$ and $p=\mathrm{\infty }$, the norms can be computed as:

${\Vert A\Vert }_1=\max {\mathrm{\backslash limits}}_{1\le j\le n}\sum _{i=1}^m|a_{ij}|,$ which is simply the maximum absolute column sum of the matrix.

${\Vert A\Vert }_{\mathrm{\infty }}=\max {\mathrm{\backslash limits}}_{1\le i\le m}\sum _{j=1}^n|a_{ij}|,$ which is simply the maximum absolute row sum of the matrix.

Theorem: Induced Norms are really norms

If $\Vert \cdot \Vert$ is a vector norm on $ℝ,$ then $\Vert A\Vert =\underset{\Vert x\Vert =1}{\max }\Vert Ax\Vert$ is a matrix norm.

Proof:

To show $\Vert A\Vert =\underset{\Vert x\Vert =1}{\max }\Vert Ax\Vert$ is a matrix norm we need to show several things.

$\Vert A\Vert =0$ if and only if $A=0$.

If $A=0$ then $\Vert Ax\Vert =0$ for all vectors x with $\Vert x\Vert =1$ and so $\Vert A\Vert =0$.

If $\Vert A\Vert =0$ then $\Vert Ax\Vert =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, $\Vert A\Vert =0$ if and only if $A=0.$

$\Vert \alpha A\Vert =|\alpha |\Vert A\Vert$ for scalars $\alpha$

Using the definition of Induced norms and the properties of the vector norm we have,

$\Vert \alpha A\Vert =\max {\mathrm{\backslash limits}}_{{\Vert x\Vert }_{=1}}\Vert \alpha Ax\Vert =|\alpha |\max {\mathrm{\backslash limits}}_{{\Vert x\Vert }_{=1}}\Vert Ax\Vert =|\alpha |.\Vert A\Vert .$

$\Vert A+B\Vert \le \Vert A\Vert +\Vert B\Vert$

Again using the definition of Induced norms and the triangle inequality for the vector norm, we have

$\Vert A+B\Vert =\max {\mathrm{\backslash limits}}_{\Vert x\Vert =1}\Vert (A+B)x\Vert \le \max {\mathrm{\backslash limits}}_{\Vert x\Vert =1}(\Vert Ax\Vert +\Vert Bx\Vert )\le \max {\mathrm{\backslash limits}}_{\Vert x\Vert =1}\Vert Ax\Vert +\max {\mathrm{\backslash limits}}_{\Vert x\Vert =1}\Vert Bx\Vert =\Vert A\Vert +\Vert B\Vert .$

Theorem: Induced norms are submultiplicative

All  induced norms are sub-multiplicative.

Proof:

We want to show $\Vert AB\Vert \le \Vert A\Vert \Vert B\Vert$. We have

$\Vert AB\Vert =\max {\mathrm{\backslash limits}}_{\Vert x{\Vert }_{=1}}\Vert (AB)x\Vert =\max {\mathrm{\backslash limits}}_{\Vert x{\Vert }_{=1}}\Vert A(Bx)\Vert \le \max {\mathrm{\backslash limits}}_{\Vert x\Vert =1}\Vert A\Vert \Vert Bx\Vert =\Vert A\Vert \max {\mathrm{\backslash limits}}_{\Vert x\Vert =1}\Vert Bx\Vert =\Vert A\Vert \Vert B\Vert$.

Derivation of A_∞ formula

If $A=(a_{ij})$ is an $n\times n$ matrix, then ${\Vert A\Vert }_{\mathrm{\infty }}=\max {\mathrm{\backslash limits}}_{1\le i\le n}\sum _{j=1}^n|a_{ij}|.$

Proof::

First we show that Template:NumBlk

Let $x$ be an n-dimensional vector with $1={\Vert x\Vert }_{\mathrm{\infty }}=\max {\mathrm{\backslash limits}}_{1\le i\le n}|x_i|.$ Since $Ax$ is also an n-dimensional vector,

${\Vert Ax\Vert }_{\mathrm{\infty }}=\max {\mathrm{\backslash limits}}_{1\le i\le n}|{Ax}_i|=\max {\mathrm{\backslash limits}}_{1\le i\le n}\left|\sum _{j=1}^n{a}_{ij}{x}_j\right|\le \max {\mathrm{\backslash limits}}_{1\le i\le n}\sum _{j=1}^n|a_{ij}|\max {\mathrm{\backslash limits}}_{1\le i\le n}|x_i|.$

But $\max {\mathrm{\backslash limits}}_{1\le i\le n}=\Vert x_j\Vert ={\Vert X\Vert }_{\mathrm{\infty }}=1,$ so

${\Vert Ax\Vert }_{\mathrm{\infty }}\le \max {\mathrm{\backslash limits}}_{1\le i\le n}\sum _{j=1}^n|a_{ij}|$

and we have shown (Template:EquationNote).

Now we will show the opposite inequality, that Template:NumBlk

Let p be an integer with

$\sum _{j=1}^n|a_{pj}|=\max {\mathrm{\backslash limits}}_{1\le i\le n}\sum _{j=1}^n|a_{ij}|,$

and $x$ be the vector with components

$x_j=\{\begin{array}{cc}1,& \text{if}{a}_{pj}\ge 0,\\ -1,& \text{if}{a}_{pj}<0.\end{array}$

Then $\Vert x{\Vert }_{\mathrm{\infty }}=1$ and $a_{pj}{x}_j=|a_{pj}|,$ for all $j=1,2,...,n,$ so

${\Vert Ax\Vert }_{\mathrm{\infty }}=\max {\mathrm{\backslash limits}}_{1\le i\le n}\left|\sum _{j=1}^n{a}_{ij}{x}_j\right|\ge \left|\sum _{j=1}^n{a}_{pj}{x}_j\right|=|\sum _{j=1}^n|a_{pj}||=\max {\mathrm{\backslash limits}}_{1\le i\le n}\sum _{j=1}^n|a_{ij}|$

and we have shown (Template:EquationNote). Together, (Template:EquationNote) and (Template:EquationNote) yield

${\Vert A\Vert }_{\mathrm{\infty }}=\max {\mathrm{\backslash limits}}_{1\le i\le n}\sum _{j=1}^n|a_{ij}|.$

Example computing A_∞

If

$𝐀=\left[\begin{array}{ccc}1& 2& -1\\ 0& 3& -1\\ 5& -1& 1\end{array}\right],$

<quiz display=simple points="1/1!"> {find $\Vert A{\Vert }_{\mathrm{\infty }}$. |type="{}"} { 7_1 } </quiz>

Solution:

$\sum _{j=1}^3|a_{1j}|=|1|+|2|+|-1|=4,\sum _{j=1}^3|a_{2j}|=|0|+|3|+|-1|=4,$

and

$\sum _{j=1}^3|a_{3j}|=|5|+|-1|+|1|=7$

so, ${\Vert A\Vert }_{\mathrm{\infty }}=\max \{4,4,7\}=7.$

 

Equivalence Of Norms

Equivalence Of Norms is defined as:

For any two norms ||·||α and ||·||β, we have
$r{\Vert A\Vert }_{\alpha }\le {\Vert A\Vert }_{\beta }\le s{\Vert A\Vert }_{\alpha }$
for some positive numbers r and s, for all matrices A in $K^{m\times n}$.  

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 {ℝ}^{m\times n}$ the following inequalities hold

• $\Vert A{\Vert }_2\le \Vert A{\Vert }_F\le \sqrt{r}\Vert A{\Vert }_2$, where $r$ is the rank of $A$
• $\Vert A{\Vert }_F\le \Vert A{\Vert }_{*}\le \sqrt{r}\Vert A{\Vert }_F$, where $r$ is the rank of $A$
• $\Vert A{\Vert }_{\text{max}}\le \Vert A{\Vert }_2\le \sqrt{mn}\Vert A{\Vert }_{\text{max}}$
• $\frac{1}{\sqrt{n}}\Vert A{\Vert }_{\mathrm{\infty }}\le \Vert A{\Vert }_2\le \sqrt{m}\Vert A{\Vert }_{\mathrm{\infty }}$
• $\frac{1}{\sqrt{m}}\Vert A{\Vert }_1\le \Vert A{\Vert }_2\le \sqrt{n}\Vert A{\Vert }_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

$𝐀=\left[\begin{array}{ccc}1& -2& 3\\ -4& 5& -6\\ 7& -8& 9\end{array}\right]$

Solution:

First we compute several norms:

• $\rho (A)\approx |16.1168|=16.1168,$
• $\Vert A{\Vert }_{\mathrm{\infty }}=\max \{|1|+|-2|+|3|,|-4|+|5|+|-6|,|7|+|-8|+|9|\}=24,$
• $\Vert A{\Vert }_1=\max \{|1|+|-4|+|7|,|-2|+|5|+|-8|,|3|+|-6|+|9|\}=18,$
• $\Vert A{\Vert }_2=\sqrt{\rho (A{A}^{*})}\approx \sqrt{283.8585}\approx 16.8481,$
• $\sqrt{r}\Vert A{\Vert }_2=\sqrt{r}\sqrt{\rho (A{A}^{*})}\approx \sqrt{3}\sqrt{283.8585}\approx 29.1818,$ Where r is the rank of the matrix.
• $\Vert A{\Vert }_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,$
• $\Vert A{\Vert }_{\max }=\max \{|1|,|-2|,|3|,|-4|,|5|,|-6|,|7|,|-8|,|9|\}=|9|.$

We can then verify the norm equivalence

${\Vert A\Vert }_{max}<\rho (A)<{\Vert A\Vert }_2<{\Vert A\Vert }_F<{\Vert A\Vert }_1<{\Vert A\Vert }_{\mathrm{\infty }}<\sqrt{r}\Vert A{\Vert }_2.$

with our numbers

$|9|<16.1168<16.8481<16.8819<18<24<29.1818,$

and

$\Vert A{\Vert }_2\le \Vert A{\Vert }_F\le \sqrt{r}\Vert A{\Vert }_2$

with our numbers

$16.8481\le 16.8819\le 29.1818.$

 

Reference

• Numerical Analysis by Richard L. Burden and J. Douglas Faires (EIGHT EDITION)
• Elementary Numerical Analysis by Kendall Atkinson (Second Edition)
• Applied Numerical Analysis by Gerald / Wheatley (Sixth Edition)
• Theory and Problems of Numerical Analysis by Francis Scheid