Type of function in linear algebra
In linear algebra, a sublinear function (or functional as is more often used in functional analysis), also called a quasi-seminorm or a Banach functional, on a vector space
is a real-valued function with only some of the properties of a seminorm. Unlike seminorms, a sublinear function does not have to be nonnegative-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 except that it is not required to map non-zero vectors to non-zero values.
In functional analysis the name Banach functional is sometimes used, reflecting that they are most commonly used when applying a general formulation of the Hahn–Banach theorem. The notion of a sublinear function was introduced by Stefan Banach when he proved his version of the Hahn-Banach theorem.
There is also a different notion in computer science, described below, that also goes by the name "sublinear function."
Definitions
Let
be a vector space over a field
where
is either the real numbers
or complex numbers
A real-valued function
on
is called a sublinear function (or a sublinear functional if
), and also sometimes called a quasi-seminorm or a Banach functional, if it has these two properties:
- Positive homogeneity/Nonnegative homogeneity:
for all real
and all
- This condition holds if and only if
for all positive real
and all ![{\displaystyle x\in X.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0deab6a01578b5b543b772df12dc0d2c593cc924)
- Subadditivity/Triangle inequality:
for all
- This subadditivity condition requires
to be real-valued.
A function
is called positive or nonnegative if
for all
although some authors define positive to instead mean that
whenever
these definitions are not equivalent. It is a symmetric function if
for all
Every subadditive symmetric function is necessarily nonnegative.[proof 1] A sublinear function on a real vector space is symmetric if and only if it is a seminorm. A sublinear function on a real or complex vector space is a seminorm if and only if it is a balanced function or equivalently, if and only if
for every unit length 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 minimal if it is a minimal element of
under this order. A sublinear function is minimal if and only if it is a real linear functional.
Examples and sufficient conditions
Every norm, seminorm, and real linear functional is a sublinear function. The identity function
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
![{\displaystyle {\begin{alignedat}{4}S_{a,b}:\;&&\mathbb {R} &&\;\to \;&\mathbb {R} \\[0.3ex]&&x&&\;\mapsto \;&{\begin{cases}ax&{\text{ if }}x\leq 0\\bx&{\text{ if }}x\geq 0\\\end{cases}}\\\end{alignedat}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa0c7c79cb32985fd21df85d8bd5e5f95309754c)
is a sublinear function on
![{\displaystyle X:=\mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/90d9c278ab99543cfeec30ab45f03df268799dd1)
and moreover, every sublinear function
![{\displaystyle p:\mathbb {R} \to \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbba0b0a051e6ebd646440a50eb872aaad992b47)
is of this form; specifically, if
![{\displaystyle a:=-p(-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e12c9263fff11f5f2dd708266f5df13d929f96f)
and
![{\displaystyle b:=p(1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aec094141b30e694173948e92115cef7bc23eb60)
then
![{\displaystyle a\leq b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41558abc50886fdf38817495b243958d7b3dd39b)
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, 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: For
![{\displaystyle {\begin{alignedat}{3}p(tx+(1-t)y)&\leq p(tx)+p((1-t)y)&&\quad {\text{ subadditivity}}\\&=tp(x)+(1-t)p(y)&&\quad {\text{ nonnegative homogeneity}}\\\end{alignedat}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bac5cb41911c936e656be9b9ece441dc922d8b37)
If
is a sublinear function on a vector space
then[proof 2]
![{\displaystyle p(0)~=~0~\leq ~p(x)+p(-x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afe83d4e9c617906edabd328bbad6f15040a103f)
for every
![{\displaystyle x\in X,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3ebdb0a09f0721ccdd0b779e0a21caf386be82a)
which implies that at least one of
![{\displaystyle p(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8cb7afced134ef75572e5314a5d278c2d644f438)
and
![{\displaystyle p(-x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d7a0e9a08052f4fd6d6be18b649540b06022429)
must be nonnegative; that is, for every
![{\displaystyle 0~\leq ~\max\{p(x),p(-x)\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ecf605bfbc5c2a21b11d0ccd77641b814686781)
Moreover, when
![{\displaystyle p:X\to \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8540db038c97641c58fdf2dbe344cc730d8b441)
is a sublinear function on a real vector space then the map
![{\displaystyle q:X\to \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/5282517967c6a6ce35ffdc26ae00b590333dfb12)
defined by
![{\displaystyle q(x)~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\max\{p(x),p(-x)\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c90330d3c4282d0c7b14c28a5f8c91f6f9a0ded4)
is a seminorm.
Subadditivity of
guarantees that for all vectors
[proof 3]
![{\displaystyle p(x)-p(y)~\leq ~p(x-y),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0edb484efeab2424f858e844748bc6ea5e9efd39)
![{\displaystyle -p(x)~\leq ~p(-x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63dcfb059792a81e7e4057387bc4fcdb0c2b2fda)
so if
![{\displaystyle p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
is also
symmetric then the
reverse triangle inequality will hold for all vectors
![{\displaystyle |p(x)-p(y)|~\leq ~p(x-y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07d976b9a90fe26c8aad4456223726ad86934884)
Defining
then subadditivity also guarantees that for all
the value of
on the set
is constant and equal to
[proof 4] 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
![{\displaystyle p(x)+ac+bc~<~\inf _{}p(x+aK)+bc~\leq ~p(x+a\mathbf {z} )+bc~<~\inf _{}p(x+a\mathbf {z} +bK)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03c6041102571822d199656f02efd186911511bc)
which yields many more inequalities, including, for instance,
![{\displaystyle p(x)+ac+bc~<~p(x+a\mathbf {z} )+bc~<~p(x+a\mathbf {z} +b\mathbf {z} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a05df229198a78a16cf7a2d0f111ca894ef2fd3)
in which an expression on one side of a strict inequality
![{\displaystyle \,<\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5ebb5b330e53c9b9af8e7d7c8e0590d3a5f631e)
can be obtained from the other by replacing the symbol
![{\displaystyle c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86a67b81c2de995bd608d5b2df50cd8cd7d92455)
with
![{\displaystyle \mathbf {z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/82eca5d0928078d5a61b9e7e98cc73db31070909)
(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 on the real vector space
called the seminorm associated with
A sublinear function
on a real or complex vector space is a symmetric function if and only if
where
as before.
More generally, if
is a real-valued sublinear function on a (real or complex) vector space
then
![{\displaystyle q(x)~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\sup _{|u|=1}p(ux)~=~\sup\{p(ux):u{\text{ is a unit scalar }}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c24a7b7c1e083def4fd6892c3e82996afd3a1c35)
will define a
seminorm on
![{\displaystyle X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
if this supremum is always a real number (that is, never equal to
![{\displaystyle \infty }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c26c105004f30c27aa7c2a9c601550a4183b1f21)
).
Relation to linear functionals
If
is a sublinear function on a real vector space
then the following are equivalent:
is a linear functional. - for every
![{\displaystyle p(x)+p(-x)\leq 0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9799e5495c1d28d586e528ece50f6df05d7b046)
- for every
![{\displaystyle p(x)+p(-x)=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f286058e39c800609daf8bef7eb27ab43d76d9d1)
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 dominated by a sublinear function
if
for every
that belongs to the domain of
If
is a real linear functional on
then
is dominated by
(that is,
) if and only if
![{\displaystyle -p(-x)\leq f(x)\leq p(x)\quad {\text{ for every }}x\in X.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d0e4f50c6170d19bc895bf99c47e350daa6937a)
Moreover, if
![{\displaystyle p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
is a seminorm or some other
symmetric map (which by definition means that
![{\displaystyle p(-x)=p(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e25594f5a6ea3ae62f0545ad97ff30419766102)
holds for all
![{\displaystyle x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
) then
![{\displaystyle f\leq p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee9272a49329da37ca0bfb7823b92172188c0d17)
if and only if
Continuity
Suppose
is a topological vector space (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 ![{\displaystyle X.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ba76c5a460c4a0bb1639a193bc1830f0a773e03)
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
Theorem — Suppose that
is a topological vector space (not necessarily locally convex or Hausdorff) over the real or complex numbers. Then the open convex subsets of
are exactly those that are of the form
![{\displaystyle z+\{x\in X:p(x)<1\}=\{x\in X:p(x-z)<1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9054271e1441af1a5d24550fa18db6d62dc580f1)
for some
![{\displaystyle z\in X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dff47a41328065a0e15e3a7089cfd392ee954e36)
and some positive continuous sublinear function
![{\displaystyle p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
on
Proof Let
be an open convex subset of
If
then let
and otherwise let
be arbitrary. Let
be the Minkowski functional of
which is a continuous sublinear function on
since
is convex, absorbing, and open (
however is not necessarily a seminorm since
was not assumed to be balanced). From
it follows that
![{\displaystyle z+\{x\in X:p(x)<1\}=\{x\in X:p(x-z)<1\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/568a8a7258b36d0e290b0329b6f8a333399392b3)
It will be shown that
![{\displaystyle V=z+\{x\in X:p(x)<1\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cae7ff5dd8971989d4e44d01b8611e3d9334d437)
which will complete the proof. One of the known
properties of Minkowski functionals guarantees
![{\textstyle \{x\in X:p(x)<1\}=(0,1)(V-z),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2e14ba6b44f8c22acf6de479c51ebd63decc5e4)
where
![{\displaystyle (0,1)(V-z)\;{\stackrel {\scriptscriptstyle {\text{def}}}{=}}\;\{tx:0<t<1,x\in V-z\}=V-z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce77c101fa3a36679425c76ef0da5ebbe7343a58)
since
![{\displaystyle V-z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d49a7aeadff801a8e764c34c9c78986f753ea458)
is convex and contains the origin. Thus
![{\displaystyle V-z=\{x\in X:p(x)<1\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c90e936e59231373a4d3fb3f4e507871799ac266)
as desired.
Operators
The concept can be extended to operators that are homogeneous and subadditive. This requires only that the codomain be, say, an ordered vector space to make sense of the conditions.
Computer science definition
In computer science, a function
is called sublinear if
or
in asymptotic notation (notice the small
). Formally,
if and only if, for any given
there exists an
such that
for
[8] That is,
grows slower than any linear function. The two meanings should not be confused: while a Banach functional is convex, almost the opposite is true for functions of sublinear growth: every function
can be upper-bounded by a concave function of sublinear growth.[9]
See also
- Asymmetric norm – Generalization of the concept of a norm
- Auxiliary normed space
- Hahn-Banach theorem – Theorem on extension of bounded linear functionalsPages displaying short descriptions of redirect targets
- Linear functional – Linear map from a vector space to its field of scalarsPages displaying short descriptions of redirect targets
- Minkowski functional – Function made from a set
- Norm (mathematics) – Length in a vector space
- Seminorm – nonnegative-real-valued function on a real or complex vector space that satisfies the triangle inequality and is absolutely homogenousPages displaying wikidata descriptions as a fallback
- Superadditivity
Notes
Proofs
- ^ Let
The triangle inequality and symmetry imply
Substituting
for
and then subtracting
from both sides proves that
Thus
which implies
- ^ If
and
then nonnegative homogeneity implies that
Consequently,
which is only possible if
- ^
which happens if and only if
Substituting
and gives
which implies
(positive homogeneity is not needed; the triangle inequality suffices).
- ^ Let
and
It remains to show that
The triangle inequality implies
Since
as desired.
References
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "3.1". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 47–48. ISBN 0-262-03293-7.
{{cite book}}
: CS1 maint: multiple names: authors list (link) - ^ Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (2017-06-29). Groups, graphs, and random walks. Cambridge. Lemma 5.17. ISBN 9781316604403. OCLC 948670194.
{{cite book}}
: CS1 maint: location missing publisher (link)
Bibliography
- Kubrusly, Carlos S. (2011). The Elements of Operator Theory (Second ed.). Boston: Birkhäuser. ISBN 978-0-8176-4998-2. OCLC 710154895.
- Rudin, Walter (1991). Functional Analysis. International Series in Pure and Applied Mathematics. Vol. 8 (Second ed.). New York, NY: McGraw-Hill Science/Engineering/Math. ISBN 978-0-07-054236-5. OCLC 21163277.
- Narici, Lawrence; Beckenstein, Edward (2011). Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834.
- Schaefer, Helmut H.; Wolff, Manfred P. (1999). Topological Vector Spaces. GTM. Vol. 8 (Second ed.). New York, NY: Springer New York Imprint Springer. ISBN 978-1-4612-7155-0. OCLC 840278135.
- Schechter, Eric (1996). Handbook of Analysis and Its Foundations. San Diego, CA: Academic Press. ISBN 978-0-12-622760-4. OCLC 175294365.
- Trèves, François (2006) [1967]. Topological Vector Spaces, Distributions and Kernels. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-45352-1. OCLC 853623322.
Spaces | |
---|
Theorems | |
---|
Operators | |
---|
Algebras | |
---|
Open problems | |
---|
Applications | |
---|
Advanced topics | |
---|
Category |
|
---|
Basic concepts | |
---|
Main results | |
---|
Maps | |
---|
Types of sets | |
---|
Set operations | |
---|
Types of TVSs | |
---|
Category |