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
‖
x
‖
2
{\displaystyle \left\|x\right\|_{2}}
,
‖
x
‖
{\displaystyle \left\|x\right\|}
, or
|
x
|
{\displaystyle |x|}
and give the length of an n-vector
x
=
(
x
1
,
x
2
,
.
.
.
x
n
)
.
{\displaystyle 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.
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:
‖
A
‖
=
max
{
‖
A
x
‖
:
x
∈
K
n
with
‖
x
‖
=
1
}
=
max
{
‖
A
x
‖
‖
x
‖
:
x
∈
K
n
with
x
≠
0
}
.
{\displaystyle {\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:
‖
A
‖
p
=
max
x
≠
0
‖
A
x
‖
p
‖
x
‖
p
.
{\displaystyle \left\|A\right\|_{p}=\max \limits _{x\neq 0}{\frac {\left\|Ax\right\|_{p}}{\left\|x\right\|_{p}}}.}
In the case of
p
=
1
{\displaystyle p=1}
and
p
=
∞
{\displaystyle p=\infty }
, the norms can be computed as:
‖
A
‖
1
=
max
1
≤
j
≤
n
∑
i
=
1
m
|
a
i
j
|
,
{\displaystyle \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.
‖
A
‖
∞
=
max
1
≤
i
≤
m
∑
j
=
1
n
|
a
i
j
|
,
{\displaystyle \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 [ edit | edit source ]
If
‖
⋅
‖
{\displaystyle \left\|\cdot \right\|}
is a vector norm on
R
,
{\displaystyle \mathbb {R} ,}
then
‖
A
‖
=
max
‖
x
‖
=
1
‖
A
x
‖
{\displaystyle \left\|A\right\|=\max _{\left\|x\right\|=1}\left\|Ax\right\|}
is a matrix norm.
To show
‖
A
‖
=
max
‖
x
‖
=
1
‖
A
x
‖
{\displaystyle \|A\|=\max _{\|x\|=1}\|Ax\|}
is a matrix norm we need to show several things.
‖
A
‖
=
0
{\displaystyle \|A\|=0}
if and only if
A
=
0
{\displaystyle A=0}
.
If
A
=
0
{\displaystyle A=0}
then
‖
A
x
‖
=
0
{\displaystyle \left\|Ax\right\|=0}
for all vectors x with
‖
x
‖
=
1
{\displaystyle \left\|x\right\|=1}
and so
‖
A
‖
=
0
{\displaystyle \|A\|=0}
.
If
‖
A
‖
=
0
{\displaystyle \|A\|=0}
then
‖
A
x
‖
=
0
{\displaystyle \|Ax\|=0}
for all
x
{\displaystyle x}
.
Using
x
=
(
1
,
0
,
.
.
.
,
0
)
t
{\displaystyle x=(1,0,...,0)^{t}}
,
x
=
(
0
,
1
,
0
,
.
.
.
,
0
)
t
,
.
.
.
,
{\displaystyle x=(0,1,0,...,0)^{t},...,}
and
x
=
(
0
,
.
.
.
,
0
,
1
)
t
{\displaystyle x=(0,...,0,1)^{t}}
successively implies that each column of
A
{\displaystyle A}
is zero. Thus,
‖
A
‖
=
0
{\displaystyle \left\|A\right\|=0}
if and only if
A
=
0.
{\displaystyle A=0.}
‖
α
A
‖
=
|
α
|
‖
A
‖
{\displaystyle \|\alpha A\|=|\alpha |\|A\|}
for scalars
α
{\displaystyle \alpha }
Using the definition of Induced norms and the properties of the vector norm we have,
‖
α
A
‖
=
max
‖
x
‖
=
1
‖
α
A
x
‖
=
|
α
|
max
‖
x
‖
=
1
‖
A
x
‖
=
|
α
|
.
‖
A
‖
.
{\displaystyle \|\alpha A\|=\max \limits _{\left\|x\right\|_{=1}}\|\alpha Ax\|=|\alpha |\max \limits _{\left\|x\right\|_{=1}}\left\|\ Ax\right\|=|\alpha |.\left\|A\right\|\,.}
‖
A
+
B
‖
≤
‖
A
‖
+
‖
B
‖
{\displaystyle \|A+B\|\leq \|A\|+\|B\|}
Again using the definition of Induced norms and the triangle inequality for the vector norm, we have
‖
A
+
B
‖
=
max
‖
x
‖
=
1
‖
(
A
+
B
)
x
‖
≤
max
‖
x
‖
=
1
(
‖
A
x
‖
+
‖
B
x
‖
)
≤
max
‖
x
‖
=
1
‖
A
x
‖
+
max
‖
x
‖
=
1
‖
B
x
‖
=
‖
A
‖
+
‖
B
‖
.
{\displaystyle \|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 [ edit | edit source ]
All induced norms are sub-multiplicative.
We want to show
‖
A
B
‖
≤
‖
A
‖
‖
B
‖
{\displaystyle \|AB\|\leq \|A\|\|B\|}
.
We have
‖
A
B
‖
=
max
‖
x
‖
=
1
‖
(
A
B
)
x
‖
=
max
‖
x
‖
=
1
‖
A
(
B
x
)
‖
≤
max
‖
x
‖
=
1
‖
A
‖
‖
B
x
‖
=
‖
A
‖
max
‖
x
‖
=
1
‖
B
x
‖
=
‖
A
‖
‖
B
‖
{\displaystyle \|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
‖
∞
{\displaystyle \|A\|_{\infty }}
formula [ edit | edit source ]
If
A
=
(
a
i
j
)
{\displaystyle A=(a_{ij})}
is an
n
×
n
{\displaystyle {n\times n}}
matrix, then
‖
A
‖
∞
=
max
1
≤
i
≤
n
∑
j
=
1
n
|
a
i
j
|
.
{\displaystyle \left\|A\right\|_{\infty }=\max \limits _{1\leq i\leq n}\sum _{j=1}^{n}|a_{ij}|.}
First we show that
‖
A
‖
∞
=
max
‖
x
‖
∞
=
1
‖
A
X
‖
∞
≤
max
1
≤
i
≤
n
∑
j
=
1
n
|
a
i
j
|
.
{\displaystyle \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
{\displaystyle x}
be an n-dimensional vector with
1
=
‖
x
‖
∞
=
max
1
≤
i
≤
n
|
x
i
|
.
{\displaystyle 1=\left\|x\right\|_{\infty }=\max \limits _{1\leq i\leq n}|{x_{i}}|.}
Since
A
x
{\displaystyle Ax}
is also an n-dimensional vector,
‖
A
x
‖
∞
=
max
1
≤
i
≤
n
|
A
x
i
|
=
max
1
≤
i
≤
n
|
∑
j
=
1
n
a
i
j
x
j
|
≤
max
1
≤
i
≤
n
∑
j
=
1
n
|
a
i
j
|
max
1
≤
i
≤
n
|
x
i
|
.
{\displaystyle \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
1
≤
i
≤
n
=
‖
x
j
‖
=
‖
X
‖
∞
=
1
,
{\displaystyle \max \limits _{1\leq i\leq n}=\left\|x_{j}\right\|=\left\|X\right\|_{\infty }=1,}
so
‖
A
x
‖
∞
≤
max
1
≤
i
≤
n
∑
j
=
1
n
|
a
i
j
|
{\displaystyle \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
‖
A
‖
∞
=
max
‖
x
‖
∞
=
1
‖
A
X
‖
∞
≥
max
1
≤
i
≤
n
∑
j
=
1
n
|
a
i
j
|
.
{\displaystyle \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
∑
j
=
1
n
|
a
p
j
|
=
max
1
≤
i
≤
n
∑
j
=
1
n
|
a
i
j
|
,
{\displaystyle \sum _{j=1}^{n}|a_{pj}|=\max \limits _{1\leq i\leq n}\sum _{j=1}^{n}|a_{ij}|,}
and
x
{\displaystyle x}
be the vector with components
x
j
=
{
1
,
if
a
p
j
≥
0
,
−
1
,
if
a
p
j
<
0.
{\displaystyle x_{j}={\begin{cases}1,&{\text{if}}\qquad a_{pj}\geq 0,\\-1,&{\text{if}}\qquad a_{pj}<0.\end{cases}}}
Then
‖
x
‖
∞
=
1
{\displaystyle \|x\|_{\infty }=1}
and
a
p
j
x
j
=
|
a
p
j
|
,
{\displaystyle a_{pj}x_{j}=|a_{pj}|,}
for all
j
=
1
,
2
,
.
.
.
,
n
,
{\displaystyle j=1,2,...,n,}
so
‖
A
x
‖
∞
=
max
1
≤
i
≤
n
|
∑
j
=
1
n
a
i
j
x
j
|
≥
|
∑
j
=
1
n
a
p
j
x
j
|
=
|
∑
j
=
1
n
|
a
p
j
|
|
=
max
1
≤
i
≤
n
∑
j
=
1
n
|
a
i
j
|
{\displaystyle \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
‖
A
‖
∞
=
max
1
≤
i
≤
n
∑
j
=
1
n
|
a
i
j
|
.
{\displaystyle \left\|A\right\|_{\infty }=\max \limits _{1\leq i\leq n}\sum _{j=1}^{n}|a_{ij}|\,.}
Example computing
‖
A
‖
∞
{\displaystyle \|A\|_{\infty }}
[ edit | edit source ]
If
A
=
[
1
2
−
1
0
3
−
1
5
−
1
1
]
,
{\displaystyle \mathbf {A} ={\begin{bmatrix}1&2&-1\\0&3&-1\\5&-1&1\\\end{bmatrix}},}
∑
j
=
1
3
|
a
1
j
|
=
|
1
|
+
|
2
|
+
|
−
1
|
=
4
,
∑
j
=
1
3
|
a
2
j
|
=
|
0
|
+
|
3
|
+
|
−
1
|
=
4
,
{\displaystyle \sum _{j=1}^{3}|a_{1j}|=|1|+|2|+|-1|=4,\qquad \sum _{j=1}^{3}|a_{2j}|=|0|+|3|+|-1|=4,}
and
∑
j
=
1
3
|
a
3
j
|
=
|
5
|
+
|
−
1
|
+
|
1
|
=
7
{\displaystyle \sum _{j=1}^{3}|a_{3j}|=|5|+|-1|+|1|=7}
so,
‖
A
‖
∞
=
max
{
4
,
4
,
7
}
=
7.
{\displaystyle \left\|A\right\|_{\infty }=\max\{4,4,7\}=7.}
Equivalence Of Norms is defined as:
For any two norms ||·||α and ||·||β , we have
r
‖
A
‖
α
≤
‖
A
‖
β
≤
s
‖
A
‖
α
{\displaystyle r\left\|A\right\|_{\alpha }\leq \left\|A\right\|_{\beta }\leq s\left\|A\right\|_{\alpha }}
for some positive numbers r and s , for all matrices A in
K
m
×
n
{\displaystyle K^{m\times n}}
.
This is true because the vector space
K
m
×
n
{\displaystyle K^{m\times n}}
has the finite dimension
m
×
n
{\displaystyle m\times n}
.
Examples of matrix norm equivalence [ edit | edit source ]
For matrix
A
∈
R
m
×
n
{\displaystyle A\in \mathbb {R} ^{m\times n}}
the following inequalities hold
‖
A
‖
2
≤
‖
A
‖
F
≤
r
‖
A
‖
2
{\displaystyle \|A\|_{2}\leq \|A\|_{F}\leq {\sqrt {r}}\|A\|_{2}}
, where
r
{\displaystyle r}
is the rank of
A
{\displaystyle A}
‖
A
‖
F
≤
‖
A
‖
∗
≤
r
‖
A
‖
F
{\displaystyle \|A\|_{F}\leq \|A\|_{*}\leq {\sqrt {r}}\|A\|_{F}}
, where
r
{\displaystyle r}
is the rank of
A
{\displaystyle A}
‖
A
‖
max
≤
‖
A
‖
2
≤
m
n
‖
A
‖
max
{\displaystyle \|A\|_{\text{max}}\leq \|A\|_{2}\leq {\sqrt {mn}}\|A\|_{\text{max}}}
1
n
‖
A
‖
∞
≤
‖
A
‖
2
≤
m
‖
A
‖
∞
{\displaystyle {\frac {1}{\sqrt {n}}}\|A\|_{\infty }\leq \|A\|_{2}\leq {\sqrt {m}}\|A\|_{\infty }}
1
m
‖
A
‖
1
≤
‖
A
‖
2
≤
n
‖
A
‖
1
.
{\displaystyle {\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.
We will show some of these norm equivalences for the matrix
A
=
[
1
−
2
3
−
4
5
−
6
7
−
8
9
]
{\displaystyle \mathbf {A} ={\begin{bmatrix}1&-2&3\\-4&5&-6\\7&-8&9\\\end{bmatrix}}}
First we compute several norms:
ρ
(
A
)
≈
|
16.1168
|
=
16.1168
,
{\displaystyle \rho (A)\approx |16.1168|=16.1168,}
‖
A
‖
∞
=
max
{
|
1
|
+
|
−
2
|
+
|
3
|
,
|
−
4
|
+
|
5
|
+
|
−
6
|
,
|
7
|
+
|
−
8
|
+
|
9
|
}
=
24
,
{\displaystyle \|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
,
{\displaystyle \|A\|_{1}=\max\{|1|+|-4|+|7|,|-2|+|5|+|-8|,|3|+|-6|+|9|\}=18,}
‖
A
‖
2
=
ρ
(
A
A
∗
)
≈
283.8585
≈
16.8481
,
{\displaystyle \|A\|_{2}={\sqrt {\rho (AA^{*})}}\approx {\sqrt {283.8585}}\approx 16.8481,}
r
‖
A
‖
2
=
r
ρ
(
A
A
∗
)
≈
3
283.8585
≈
29.1818
,
{\displaystyle {\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
=
|
1
|
2
+
|
−
2
|
2
+
|
3
|
2
+
|
−
4
|
2
+
|
5
|
2
+
|
−
6
|
2
+
|
7
|
2
+
|
−
8
|
2
+
|
9
|
2
+
=
285
≈
16.8819
,
{\displaystyle \|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
|
.
{\displaystyle \|A\|_{\max }=\max\{|1|,|-2|,|3|,|-4|,|5|,|-6|,|7|,|-8|,|9|\}=|9|.}
We can then verify the norm equivalence
‖
A
‖
m
a
x
<
ρ
(
A
)
<
‖
A
‖
2
<
‖
A
‖
F
<
‖
A
‖
1
<
‖
A
‖
∞
<
r
‖
A
‖
2
.
{\displaystyle \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
,
{\displaystyle |9|<16.1168<16.8481<16.8819<18<24<29.1818,}
and
‖
A
‖
2
≤
‖
A
‖
F
≤
r
‖
A
‖
2
{\displaystyle \|A\|_{2}\leq \|A\|_{F}\leq {\sqrt {r}}\|A\|_{2}}
with our numbers
16.8481
≤
16.8819
≤
29.1818.
{\displaystyle 16.8481\leq \ 16.8819\leq \ 29.1818.}
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