In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a matrix norm is a
vector norm
In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is ze ...
in a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
whose elements (vectors) are
matrices
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
(of given dimensions).
Preliminaries
Given a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
of either
real
Real may refer to:
Currencies
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Music Albums
* ''Real'' (L'Arc-en-Ciel album) (2000)
* ''Real'' (Bright album) (2010) ...
or
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s, let
be the -
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
of matrices with
rows and
columns and entries in the field
. A matrix norm is a
norm
Naturally occurring radioactive materials (NORM) and technologically enhanced naturally occurring radioactive materials (TENORM) consist of materials, usually industrial wastes or by-products enriched with radioactive elements found in the envi ...
on
.
This article will always write such norms with
double vertical bars (like so:
). Thus, the matrix norm is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
that must satisfy the following properties:
For all scalars
and matrices
,
*
(''positive-valued'')
*
(''definite'')
*
(''absolutely homogeneous'')
*
(''sub-additive'' or satisfying the ''triangle inequality'')
The only feature distinguishing matrices from rearranged vectors is
multiplication. Matrix norms are particularly useful if they are also sub-multiplicative:
*
[The condition only applies when the product is defined, such as the case of ]square matrices
In mathematics, a square matrix is a matrix with the same number of rows and columns. An ''n''-by-''n'' matrix is known as a square matrix of order Any two square matrices of the same order can be added and multiplied.
Square matrices are often ...
().
Every norm on can be rescaled to be sub-multiplicative; in some books, the terminology ''matrix norm'' is reserved for sub-multiplicative norms.
Matrix norms induced by vector norms
Suppose a
vector norm
In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is ze ...
on
and a vector norm
on
are given. Any
matrix induces a linear operator from
to
with respect to the standard basis, and one defines the corresponding ''induced norm'' or ''
operator norm
In mathematics, the operator norm measures the "size" of certain linear operators by assigning each a real number called its . Formally, it is a norm defined on the space of bounded linear operators between two given normed vector spaces.
Introd ...
'' or ''subordinate norm'' on the space
of all
matrices as follows:
where
denotes the
supremum. This norm measures how much the mapping induced by
can stretch vectors.
Depending on the vector norms
,
used, notation other than
can be used for the operator norm.
Matrix norms induced by vector p-norms
If the
''p''-norm for vectors (
) is used for both spaces
and
, then the corresponding operator norm is:
These induced norms are different from the
"entry-wise" ''p''-norms and the
Schatten ''p''-norms for matrices treated below, which are also usually denoted by
In the special cases of
, the induced matrix norms can be computed or estimated by
which is simply the maximum absolute column sum of the matrix;
which is simply the maximum absolute row sum of the matrix.
For example, for
we have that
In the special case of
(the
Euclidean norm
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean s ...
or
-norm for vectors), the induced matrix norm is the ''spectral norm''. (The two values do ''not'' coincide in infinite dimensions — see
Spectral radius
In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues. More generally, the spectral radius of a bounded linear operator is the supremum of the absolute values of the elements of its spectru ...
for further discussion.) The spectral norm of a matrix
is the largest
singular value In mathematics, in particular functional analysis, the singular values, or ''s''-numbers of a compact operator T: X \rightarrow Y acting between Hilbert spaces X and Y, are the square roots of the (necessarily non-negative) eigenvalues of the self ...
of
(i.e., the square root of the largest
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
of the matrix
, where
denotes the
conjugate transpose
In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \boldsymbol is an n \times m matrix obtained by transposing \boldsymbol and applying complex conjugate on each entry (the complex c ...
of
):
where
represents the largest singular value of matrix
. Also,
since
and similarly
by
singular value decomposition
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is re ...
(SVD). There is another important inequality:
where
is the
Frobenius norm
In mathematics, a matrix norm is a vector norm in a vector space whose elements (vectors) are matrices (of given dimensions).
Preliminaries
Given a field K of either real or complex numbers, let K^ be the -vector space of matrices with m ro ...
. Equality holds if and only if the matrix
is a rank-one matrix or a zero matrix. This inequality can be derived from the fact that the trace of a matrix is equal to the sum of its eigenvalues.
When
we have an equivalent definition for
as
. It can be shown to be equivalent to the above definitions using the
Cauchy–Schwarz inequality
The Cauchy–Schwarz inequality (also called Cauchy–Bunyakovsky–Schwarz inequality) is considered one of the most important and widely used inequalities in mathematics.
The inequality for sums was published by . The corresponding inequality fo ...
.
Properties
Any operator norm is
consistent
In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...
with the vector norms that induce it, giving
Suppose
;
; and
are operator norms induced by the respective pairs of vector norms
;
; and
. Then,
:
this follows from
and
Square matrices
Suppose
is an operator norm on the space of square matrices
induced by vector norms
and
.
Then, the operator norm is a sub-multiplicative matrix norm:
Moreover, any such norm satisfies the inequality
for all positive integers ''r'', where is the
spectral radius
In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues. More generally, the spectral radius of a bounded linear operator is the supremum of the absolute values of the elements of its spectru ...
of . For
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
or
hermitian {{Short description, none
Numerous things are named after the French mathematician Charles Hermite (1822–1901):
Hermite
* Cubic Hermite spline, a type of third-degree spline
* Gauss–Hermite quadrature, an extension of Gaussian quadrature m ...
, we have equality in () for the 2-norm, since in this case the 2-norm ''is'' precisely the spectral radius of . For an arbitrary matrix, we may not have equality for any norm; a counterexample would be
which has vanishing spectral radius. In any case, for any matrix norm, we have the
spectral radius formula
In mathematics, the spectral radius of a matrix (mathematics), square matrix is the maximum of the absolute values of its eigenvalues. More generally, the spectral radius of a bounded linear operator is the supremum of the absolute values of the e ...
:
Consistent and compatible norms
A matrix norm
on
is called ''consistent'' with a vector norm
on
and a vector norm
on
, if:
for all
and all
. In the special case of and
,
is also called ''compatible'' with
.
All induced norms are consistent by definition. Also, any sub-multiplicative matrix norm on
induces a compatible vector norm on
by defining
.
"Entry-wise" matrix norms
These norms treat an
matrix as a vector of size
, and use one of the familiar vector norms. For example, using the ''p''-norm for vectors, , we get:
:
This is a different norm from the induced ''p''-norm (see above) and the Schatten ''p''-norm (see below), but the notation is the same.
The special case ''p'' = 2 is the Frobenius norm, and ''p'' = ∞ yields the maximum norm.
and norms
Let
be the columns of matrix
. From the original definition, the matrix
presents n data points in m-dimensional space. The
norm is the sum of the Euclidean norms of the columns of the matrix:
:
The
norm as an error function is more robust, since the error for each data point (a column) is not squared. It is used in
robust data analysis
Robust statistics are statistics with good performance for data drawn from a wide range of probability distributions, especially for distributions that are not normal. Robust statistical methods have been developed for many common problems, such ...
and
sparse coding
Neural coding (or Neural representation) is a neuroscience field concerned with characterising the hypothetical relationship between the stimulus and the individual or ensemble neuronal responses and the relationship among the electrical activit ...
.
For , the
norm can be generalized to the
norm as follows:
:
Frobenius norm
When for the
norm, it is called the Frobenius norm or the Hilbert–Schmidt norm, though the latter term is used more frequently in the context of operators on (possibly infinite-dimensional)
Hilbert space
In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...
. This norm can be defined in various ways:
:
where
are the
singular value In mathematics, in particular functional analysis, the singular values, or ''s''-numbers of a compact operator T: X \rightarrow Y acting between Hilbert spaces X and Y, are the square roots of the (necessarily non-negative) eigenvalues of the self ...
s of
. Recall that the
trace function
In linear algebra, the trace of a square matrix , denoted , is defined to be the sum of elements on the main diagonal (from the upper left to the lower right) of . The trace is only defined for a square matrix ().
It can be proved that the trace ...
returns the sum of diagonal entries of a square matrix.
The Frobenius norm is an extension of the Euclidean norm to
and comes from the
Frobenius inner product
In mathematics, the Frobenius inner product is a binary operation that takes two matrices and returns a scalar. It is often denoted \langle \mathbf,\mathbf \rangle_\mathrm. The operation is a component-wise inner product of two matrices as though ...
on the space of all matrices.
The Frobenius norm is sub-multiplicative and is very useful for
numerical linear algebra
Numerical linear algebra, sometimes called applied linear algebra, is the study of how matrix operations can be used to create computer algorithms which efficiently and accurately provide approximate answers to questions in continuous mathematic ...
. The sub-multiplicativity of Frobenius norm can be proved using
Cauchy–Schwarz inequality
The Cauchy–Schwarz inequality (also called Cauchy–Bunyakovsky–Schwarz inequality) is considered one of the most important and widely used inequalities in mathematics.
The inequality for sums was published by . The corresponding inequality fo ...
.
Frobenius norm is often easier to compute than induced norms, and has the useful property of being invariant under
rotations (and
unitary
Unitary may refer to:
Mathematics
* Unitary divisor
* Unitary element
* Unitary group
* Unitary matrix
* Unitary morphism
* Unitary operator
* Unitary transformation
* Unitary representation
* Unitarity (physics)
* ''E''-unitary inverse semigrou ...
operations in general). That is,
for any unitary matrix
. This property follows from the cyclic nature of the trace (
):
:
and analogously:
:
where we have used the unitary nature of
(that is,
).
It also satisfies
:
and
:
where
is the
Frobenius inner product
In mathematics, the Frobenius inner product is a binary operation that takes two matrices and returns a scalar. It is often denoted \langle \mathbf,\mathbf \rangle_\mathrm. The operation is a component-wise inner product of two matrices as though ...
, and Re is the real part of a complex number (irrelevant for real matrices)
Max norm
The max norm is the elementwise norm in the limit as goes to infinity:
:
This norm is not
sub-multiplicative.
Note that in some literature (such as
Communication complexity
In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first intro ...
), an alternative definition of max-norm, also called the
-norm, refers to the factorization norm:
:
Schatten norms
The Schatten ''p''-norms arise when applying the ''p''-norm to the vector of
singular values In mathematics, in particular functional analysis, the singular values, or ''s''-numbers of a compact operator T: X \rightarrow Y acting between Hilbert spaces X and Y, are the square roots of the (necessarily non-negative) eigenvalues of the self- ...
of a matrix.
If the singular values of the
matrix
are denoted by ''σ
i'', then the Schatten ''p''-norm is defined by
:
These norms again share the notation with the induced and entry-wise ''p''-norms, but they are different.
All Schatten norms are sub-multiplicative. They are also unitarily invariant, which means that
for all matrices
and all
unitary matrices
In linear algebra, a complex square matrix is unitary if its conjugate transpose is also its inverse, that is, if
U^* U = UU^* = UU^ = I,
where is the identity matrix.
In physics, especially in quantum mechanics, the conjugate transpose ...
and
.
The most familiar cases are ''p'' = 1, 2, ∞. The case ''p'' = 2 yields the Frobenius norm, introduced before. The case ''p'' = ∞ yields the spectral norm, which is the operator norm induced by the vector 2-norm (see above). Finally, ''p'' = 1 yields the nuclear norm (also known as the ''trace norm'', or the
Ky Fan
Ky Fan (樊𰋀, , September 19, 1914 – March 22, 2010) was a Chinese-born American mathematician. He was a professor of mathematics at the University of California, Santa Barbara.
Biography
Fan was born in Hangzhou, the capital of Zhejian ...
'n'-norm), defined as
:
where
denotes a positive semidefinite matrix
such that
. More precisely, since
is a
positive semidefinite matrix, its
square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
E ...
is well-defined. The nuclear norm
is a
convex envelope of the rank function
, so it is often used in
mathematical optimization to search for low rank matrices.
Monotone norms
A matrix norm
is called ''monotone'' if it is monotonic with respect to the
Loewner order In mathematics, Loewner order is the partial order defined by the convex cone of positive semi-definite matrices. This order is usually employed to generalize the definitions of monotone and concave/convex scalar functions to monotone and concav ...
. Thus, a matrix norm is increasing if
:
The Frobenius norm and spectral norm are examples of monotone norms.
Cut norms
Another source of inspiration for matrix norms arises from considering a matrix as the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
of a
weighted
A weight function is a mathematical device used when performing a sum, integral, or average to give some elements more "weight" or influence on the result than other elements in the same set. The result of this application of a weight function is ...
,
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
.
The so-called "cut norm" measures how close the associated graph is to being
bipartite:
where .
[ Note that Lovász rescales to lie in .] Equivalent definitions (up to a constant factor) impose the conditions ; ; or .
The cut-norm is equivalent to the induced operator norm , which is itself equivalent to the another norm, called the
Grothendieck norm.
To define the Grothendieck norm, first note that a linear operator is just a scalar, and thus extends to a linear operator on any . Moreover, given any choice of basis for and , any linear operator extends to a linear operator , by letting each matrix element on elements of via scalar multiplication. The Grothendieck norm is the norm of that extended operator; in symbols:
The Grothendieck norm depends on choice of basis (usually taken to be the
standard basis
In mathematics, the standard basis (also called natural basis or canonical basis) of a coordinate vector space (such as \mathbb^n or \mathbb^n) is the set of vectors whose components are all zero, except one that equals 1. For example, in the c ...
) and .
Equivalence of norms
For any two matrix norms
and
, we have that:
:
for some positive numbers ''r'' and ''s'', for all matrices
. In other words, all norms on
are ''equivalent''; they induce the same
topology
In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
on
. This is true because the vector space
has the finite
dimension
In physics and mathematics, the dimension of a Space (mathematics), mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any Point (geometry), point within it. Thus, a Line (geometry), lin ...
.
Moreover, for every vector norm
on
, there exists a unique positive real number
such that
is a sub-multiplicative matrix norm for every
.
A sub-multiplicative matrix norm
is said to be ''minimal'', if there exists no other sub-multiplicative matrix norm
satisfying
.
Examples of norm equivalence
Let
once again refer to the norm induced by the vector ''p''-norm (as above in the Induced Norm section).
For matrix
of
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* ...
, the following inequalities hold:
[Roger Horn and Charles Johnson. ''Matrix Analysis,'' Chapter 5, Cambridge University Press, 1985. .]
*
*
*
*
*
Another useful inequality between matrix norms is
:
which is a special case of
Hölder's inequality.
See also
*
Dual norm
In functional analysis, the dual norm is a measure of size for a continuous linear function defined on a normed vector space.
Definition
Let X be a normed vector space with norm \, \cdot\, and let X^* denote its continuous dual space. The dual ...
*
Logarithmic norm
Notes
References
{{reflist
Bibliography
*
James W. Demmel, Applied Numerical Linear Algebra, section 1.7, published by SIAM, 1997.
* Carl D. Meyer, Matrix Analysis and Applied Linear Algebra, published by SIAM, 2000
*
John Watrous (computer scientist), John Watrous, Theory of Quantum Information
2.3 Norms of operators lecture notes, University of Waterloo, 2011.
*
Kendall Atkinson, An Introduction to Numerical Analysis, published by John Wiley & Sons, Inc 1989
Norms (mathematics)
Linear algebra