In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrix (mathemat ...
, a sublinear function (or
functional as is more often used in
functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (for example, Inner product space#Definition, inner product, Norm (mathematics ...
), also called a quasi-seminorm or a Banach functional, on a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
is a
real-valued
function with only some of the properties of a
seminorm
In mathematics, particularly in functional analysis, a seminorm is like a Norm (mathematics), norm but need not be positive definite. Seminorms are intimately connected with convex sets: every seminorm is the Minkowski functional of some Absorbing ...
. Unlike seminorms, a sublinear function does not have to be
nonnegative
In mathematics, the sign of a real number is its property of being either positive, negative, or 0. Depending on local conventions, zero may be considered as having its own unique sign, having no sign, or having both positive and negative sign. ...
-valued and also does not have to be
absolutely homogeneous. Seminorms are themselves abstractions of the more well known notion of
norms, where a seminorm has all the defining properties of a norm that it is not required to map non-zero vectors to non-zero values.
In
functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (for example, Inner product space#Definition, inner product, Norm (mathematics ...
the name Banach functional is sometimes used, reflecting that they are most commonly used when applying a general formulation of the
Hahn–Banach theorem
In functional analysis, the Hahn–Banach theorem is a central result that allows the extension of bounded linear functionals defined on a vector subspace of some vector space to the whole space. The theorem also shows that there are sufficient ...
.
The notion of a sublinear function was introduced by
Stefan Banach
Stefan Banach ( ; 30 March 1892 – 31 August 1945) was a Polish mathematician who is generally considered one of the 20th century's most important and influential mathematicians. He was the founder of modern functional analysis, and an original ...
when he proved his version of the
Hahn-Banach theorem.
There is also a different notion in
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, described below, that also goes by the name "sublinear function."
Definitions
Let
be a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
over a field
where
is either the
real number
In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s
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 for ...
s
A real-valued function
on
is called a ' (or a ' if
), and also sometimes called a ' or a ', if it has these two properties:
- ''
Positive homogeneity
In mathematics, a homogeneous function is a function of several variables such that the following holds: If each of the function's arguments is multiplied by the same scalar, then the function's value is multiplied by some power of this scalar; ...
/ Nonnegative homogeneity'': for all real and all
* This condition holds if and only if for all positive real and all
- ''
Subadditivity
In mathematics, subadditivity is a property of a function that states, roughly, that evaluating the function for the sum of two elements of the domain always returns something less than or equal to the sum of the function's values at each element ...
/Triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.
This statement permits the inclusion of Degeneracy (mathematics)#T ...
'': for all
* This subadditivity condition requires to be real-valued.
A function
is called or if
for all
although some authors define to instead mean that
whenever
these definitions are not equivalent.
It is a if
for all
Every subadditive symmetric function is necessarily nonnegative.
A sublinear function on a real vector space is
symmetric
Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...
if and only if it is a
seminorm
In mathematics, particularly in functional analysis, a seminorm is like a Norm (mathematics), norm but need not be positive definite. Seminorms are intimately connected with convex sets: every seminorm is the Minkowski functional of some Absorbing ...
.
A sublinear function on a real or complex vector space is a seminorm if and only if it is a
balanced function
In linear algebra and related areas of mathematics a balanced set, circled set or disk in a vector space (over a field \mathbb with an absolute value function , \cdot , ) is a set S such that a S \subseteq S for all scalars a satisfying , a, ...
or equivalently, if and only if
for every
unit length
Unit may refer to:
General measurement
* Unit of measurement, a definite magnitude of a physical quantity, defined and adopted by convention or by law
**International System of Units (SI), modern form of the metric system
**English units, histo ...
scalar
(satisfying
) and every
The set of all sublinear functions on
denoted by
can be
partially ordered by declaring
if and only if
for all
A sublinear function is called ' if it is a
minimal element
In mathematics, especially in order theory, a maximal element of a subset S of some preordered set is an element of S that is not smaller than any other element in S. A minimal element of a subset S of some preordered set is defined dually as an ...
of
under this order.
A sublinear function is minimal if and only if it is a real
linear functional
In mathematics, a linear form (also known as a linear functional, a one-form, or a covector) is a linear mapIn some texts the roles are reversed and vectors are defined as linear maps from covectors to scalars from a vector space to its field of ...
.
Examples and sufficient conditions
Every
norm
Norm, the Norm or NORM may refer to:
In academic disciplines
* Normativity, phenomenon of designating things as good or bad
* Norm (geology), an estimate of the idealised mineral content of a rock
* Norm (philosophy), a standard in normative e ...
,
seminorm
In mathematics, particularly in functional analysis, a seminorm is like a Norm (mathematics), norm but need not be positive definite. Seminorms are intimately connected with convex sets: every seminorm is the Minkowski functional of some Absorbing ...
, and real linear functional is a sublinear function.
The
identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, unc ...
on
is an example of a sublinear function (in fact, it is even a linear functional) that is neither positive nor a seminorm; the same is true of this map's negation
More generally, for any real
the map
is a sublinear function on
and moreover, every sublinear function
is of this form; specifically, if
and
then
and
If
and
are sublinear functions on a real vector space
then so is the map
More generally, if
is any non-empty collection of sublinear functionals on a real vector space
and if for all
then
is a sublinear functional on
A function
which is
subadditive,
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytop ...
, and satisfies
is also positively homogeneous (the latter condition
is necessary as the example of
on
shows). If
is positively homogeneous, it is convex if and only if it is subadditive. Therefore, assuming
, any two properties among subadditivity, convexity, and positive homogeneity implies the third.
Properties
Every sublinear function is a
convex function
In mathematics, a real-valued function is called convex if the line segment between any two distinct points on the graph of a function, graph of the function lies above or on the graph between the two points. Equivalently, a function is conve ...
: For
If
is a sublinear function on a vector space
then
for every
which implies that at least one of
and
must be nonnegative; that is, for every
Moreover, when
is a sublinear function on a real vector space then the map
defined by
is a seminorm.
Subadditivity of
guarantees that for all vectors
so if
is also
symmetric
Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...
then the
reverse triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.
This statement permits the inclusion of degenerate triangles, but ...
will hold for all vectors
Defining
then subadditivity also guarantees that for all
the value of
on the set
is constant and equal to
In particular, if
is a vector subspace of
then
and the assignment
which will be denoted by
is a well-defined real-valued sublinear function on the
quotient space that satisfies
If
is a seminorm then
is just the usual canonical norm on the quotient space
Adding
to both sides of the hypothesis
(where
) and combining that with the conclusion gives
which yields many more inequalities, including, for instance,
in which an expression on one side of a strict inequality
can be obtained from the other by replacing the symbol
with
(or vice versa) and moving the closing parenthesis to the right (or left) of an adjacent summand (all other symbols remain fixed and unchanged).
Associated seminorm
If
is a real-valued sublinear function on a real vector space
(or if
is complex, then when it is considered as a real vector space) then the map
defines a
seminorm
In mathematics, particularly in functional analysis, a seminorm is like a Norm (mathematics), norm but need not be positive definite. Seminorms are intimately connected with convex sets: every seminorm is the Minkowski functional of some Absorbing ...
on the real vector space
called the seminorm associated with
A sublinear function
on a real or complex vector space is a
symmetric function
In mathematics, a function of n variables is symmetric if its value is the same no matter the order of its arguments. For example, a function f\left(x_1,x_2\right) of two arguments is a symmetric function if and only if f\left(x_1,x_2\right) = f\ ...
if and only if
where
as before.
More generally, if
is a real-valued sublinear function on a (real or complex) vector space
then
will define a
seminorm
In mathematics, particularly in functional analysis, a seminorm is like a Norm (mathematics), norm but need not be positive definite. Seminorms are intimately connected with convex sets: every seminorm is the Minkowski functional of some Absorbing ...
on
if this supremum is always a real number (that is, never equal to
).
Relation to linear functionals
If
is a sublinear function on a real vector space
then the following are equivalent:
- is a
linear functional
In mathematics, a linear form (also known as a linear functional, a one-form, or a covector) is a linear mapIn some texts the roles are reversed and vectors are defined as linear maps from covectors to scalars from a vector space to its field of ...
.
- for every
- for every
- is a minimal sublinear function.
If
is a sublinear function on a real vector space
then there exists a linear functional
on
such that
If
is a real vector space,
is a linear functional on
and
is a positive sublinear function on
then
on
if and only if
Dominating a linear functional
A real-valued function
defined on a subset of a real or complex vector space
is said to be a sublinear function
if
for every
that belongs to the domain of
If
is a real
linear functional
In mathematics, a linear form (also known as a linear functional, a one-form, or a covector) is a linear mapIn some texts the roles are reversed and vectors are defined as linear maps from covectors to scalars from a vector space to its field of ...
on
then
is dominated by
(that is,
) if and only if
Moreover, if
is a seminorm or some other (which by definition means that
holds for all
) then
if and only if
Continuity
Suppose
is a
topological vector space
In mathematics, a topological vector space (also called a linear topological space and commonly abbreviated TVS or t.v.s.) is one of the basic structures investigated in functional analysis.
A topological vector space is a vector space that is als ...
(TVS) over the real or complex numbers and
is a sublinear function on
Then the following are equivalent:
- is continuous;
- is continuous at 0;
- is uniformly continuous on ;
and if
is positive then this list may be extended to include:
- is open in
If
is a real TVS,
is a linear functional on
and
is a continuous sublinear function on
then
on
implies that
is continuous.
Relation to Minkowski functions and open convex sets
Relation to open convex sets
Operators
The concept can be extended to operators that are homogeneous and subadditive.
This requires only that the
codomain
In mathematics, a codomain, counter-domain, or set of destination of a function is a set into which all of the output of the function is constrained to fall. It is the set in the notation . The term '' range'' is sometimes ambiguously used to ...
be, say, an
ordered vector space
In mathematics, an ordered vector space or partially ordered vector space is a vector space equipped with a partial order that is compatible with the vector space operations.
Definition
Given a vector space X over the real numbers \Reals and a ...
to make sense of the conditions.
Computer science definition
In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a function
is called sublinear if
or
in
asymptotic notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by German mathematicians Pau ...
(notice the small
).
Formally,
if and only if, for any given
there exists an
such that
for
That is,
grows slower than any linear function.
The two meanings should not be confused: while a Banach functional is
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytop ...
, almost the opposite is true for functions of sublinear growth: every function
can be upper-bounded by a
concave function
In mathematics, a concave function is one for which the function value at any convex combination of elements in the domain is greater than or equal to that convex combination of those domain elements. Equivalently, a concave function is any funct ...
of sublinear growth.
See also
*
*
*
*
*
*
*
*
Notes
Proofs
References
Bibliography
*
*
*
*
*
*
{{Topological vector spaces
Articles containing proofs
Functional analysis
Linear algebra
Types of functions