Inner Product Space #
This file defines inner product spaces and proves its basic properties.
An inner product space is a vector space endowed with an inner product. It generalizes the notion of
dot product in โ^n
and provides the means of defining the length of a vector and the angle between
two vectors. In particular vectors x
and y
are orthogonal if their inner product equals zero.
We define both the real and complex cases at the same time using the is_R_or_C
typeclass.
Main results #
- We define the class
inner_product_space ๐ E
extendingnormed_space ๐ E
with a number of basic properties, most notably the Cauchy-Schwarz inequality. Here๐
is understood to be eitherโ
orโ
, through theis_R_or_C
typeclass. - We show that if
f i
is an inner product space for eachi
, then so isฮ i, f i
- We define
euclidean_space ๐ n
to ben โ ๐
for anyfintype n
, and show that this an inner product space. - Existence of orthogonal projection onto nonempty complete subspace:
Let
u
be a point in an inner product space, and letK
be a nonempty complete subspace. Then there exists a uniquev
inK
that minimizes the distanceโฅu - vโฅ
tou
. The pointv
is usually called the orthogonal projection ofu
ontoK
. - We define
orthonormal
, a predicate on a functionv : ฮน โ E
. We prove the existence of a maximal orthonormal set,exists_maximal_orthonormal
, and also prove that a maximal orthonormal set is a basis (maximal_orthonormal_iff_basis_of_finite_dimensional
), ifE
is finite- dimensional, or in general (maximal_orthonormal_iff_dense_span
) a set whose span is dense (i.e., a Hilbert basis, although we do not make that definition).
Notation #
We globally denote the real and complex inner products by โชยท, ยทโซ_โ
and โชยท, ยทโซ_โ
respectively.
We also provide two notation namespaces: real_inner_product_space
, complex_inner_product_space
,
which respectively introduce the plain notation โชยท, ยทโซ
for the the real and complex inner product.
The orthogonal complement of a submodule K
is denoted by Kแฎ
.
Implementation notes #
We choose the convention that inner products are conjugate linear in the first argument and linear in the second.
TODO #
- Fix the section on the existence of minimizers and orthogonal projections to make sure that it also applies in the complex case.
Tags #
inner product space, norm
References #
- [Clรฉment & Martin, The Lax-Milgram Theorem. A detailed proof to be formalized in Coq]
- [Clรฉment & Martin, A Coq formal proof of the LaxโMilgram theorem]
The Coq code is available at the following address: http://www.lri.fr/~sboldo/elfic/index.html
- inner : E โ E โ ๐
Syntactic typeclass for types endowed with an inner product
- to_normed_group : normed_group E
- to_normed_space : normed_space ๐ E
- to_has_inner : has_inner ๐ E
- norm_sq_eq_inner : โ (x : E), โฅxโฅ ^ 2 = โis_R_or_C.re (inner x x)
- conj_sym : โ (x y : E), โis_R_or_C.conj (inner y x) = inner x y
- add_left : โ (x y z : E), inner (x + y) z = inner x z + inner y z
- smul_left : โ (x y : E) (r : ๐), inner (r โข x) y = (โis_R_or_C.conj r) * inner x y
An inner product space is a vector space with an additional operation called inner product.
The norm could be derived from the inner product, instead we require the existence of a norm and
the fact that โฅxโฅ^2 = re โชx, xโซ
to be able to put instances on ๐
or product
spaces.
To construct a norm from an inner product, see inner_product_space.of_core
.
Constructing a normed space structure from an inner product #
In the definition of an inner product space, we require the existence of a norm, which is equal
(but maybe not defeq) to the square root of the scalar product. This makes it possible to put
an inner product space structure on spaces with a preexisting norm (for instance โ
), with good
properties. However, sometimes, one would like to define the norm starting only from a well-behaved
scalar product. This is what we implement in this paragraph, starting from a structure
inner_product_space.core
stating that we have a nice scalar product.
Our goal here is not to develop a whole theory with all the supporting API, as this will be done
below for inner_product_space
. Instead, we implement the bare minimum to go as directly as
possible to the construction of the norm and the proof of the triangular inequality.
Warning: Do not use this core
structure if the space you are interested in already has a norm
instance defined on it, otherwise this will create a second non-defeq norm instance!
- inner : F โ F โ ๐
- conj_sym : โ (x y : F), โis_R_or_C.conj (c.inner y x) = c.inner x y
- nonneg_re : โ (x : F), 0 โค โis_R_or_C.re (c.inner x x)
- definite : โ (x : F), c.inner x x = 0 โ x = 0
- add_left : โ (x y z : F), c.inner (x + y) z = c.inner x z + c.inner y z
- smul_left : โ (x y : F) (r : ๐), c.inner (r โข x) y = (โis_R_or_C.conj r) * c.inner x y
A structure requiring that a scalar product is positive definite and symmetric, from which one
can construct an inner_product_space
instance in inner_product_space.of_core
.
Inner product defined by the inner_product_space.core
structure.
Equations
The norm squared function for inner_product_space.core
structure.
Equations
CauchyโSchwarz inequality. This proof follows "Proof 2" on Wikipedia.
We need this for the core
structure to prove the triangle inequality below when
showing the core is a normed group.
Norm constructed from a inner_product_space.core
structure, defined to be the square root
of the scalar product.
Equations
- inner_product_space.of_core.to_has_norm = {norm := ฮป (x : F), real.sqrt (โis_R_or_C.re (inner x x))}
CauchyโSchwarz inequality with norm
Normed group structure constructed from an inner_product_space.core
structure
Equations
- inner_product_space.of_core.to_normed_group = normed_group.of_core F inner_product_space.of_core.to_normed_group._proof_1
Normed space structure constructed from a inner_product_space.core
structure
Equations
- inner_product_space.of_core.to_normed_space = {to_module := _inst_3, norm_smul_le := _}
Given a inner_product_space.core
structure on a space, one can use it to turn
the space into an inner product space, constructing the norm out of the inner product
Equations
- inner_product_space.of_core c = let _inst : normed_group F := inner_product_space.of_core.to_normed_group, _inst_4 : normed_space ๐ F := inner_product_space.of_core.to_normed_space in {to_normed_group := _inst, to_normed_space := _inst_4, to_has_inner := {inner := c.inner}, norm_sq_eq_inner := _, conj_sym := _, add_left := _, smul_left := _}
Properties of inner product spaces #
The inner product as a sesquilinear form.
Equations
- sesq_form_of_inner = {sesq := ฮป (x y : E), inner y x, sesq_add_left := _, sesq_smul_left := _, sesq_add_right := _, sesq_smul_right := _}
The real inner product as a bilinear form.
Equations
- bilin_form_of_real_inner = {bilin := inner inner_product_space.to_has_inner, bilin_add_left := _, bilin_smul_left := _, bilin_add_right := _, bilin_smul_right := _}
An inner product with a sum on the left, finsupp
version.
An inner product with a sum on the right, finsupp
version.
CauchyโSchwarz inequality. This proof follows "Proof 2" on Wikipedia.
A family of vectors is linearly independent if they are nonzero and orthogonal.
An orthonormal set of vectors in an inner_product_space
if ... then ... else
characterization of an indexed set of vectors being orthonormal. (Inner
product equals Kronecker delta.)
if ... then ... else
characterization of a set of vectors being orthonormal. (Inner product
equals Kronecker delta.)
The inner product of a linear combination of a set of orthonormal vectors with one of those vectors picks out the coefficient of that vector.
The inner product of a linear combination of a set of orthonormal vectors with one of those vectors picks out the coefficient of that vector.
The inner product of a linear combination of a set of orthonormal vectors with one of those vectors picks out the coefficient of that vector.
The inner product of a linear combination of a set of orthonormal vectors with one of those vectors picks out the coefficient of that vector.
An orthonormal set is linearly independent.
A subfamily of an orthonormal family (i.e., a composition with an injective map) is an orthonormal family.
A linear combination of some subset of an orthonormal set is orthogonal to other members of the set.
Given an orthonormal set v
of vectors in E
, there exists a maximal orthonormal set
containing it.
A family of orthonormal vectors with the correct cardinality forms a basis.
Equations
- basis_of_orthonormal_of_card_eq_finrank hv card_eq = basis_of_linear_independent_of_card_eq_finrank _ card_eq
CauchyโSchwarz inequality with norm
Polarization identity: The real part of the inner product, in terms of the norm.
Polarization identity: The real part of the inner product, in terms of the norm.
Polarization identity: The real part of the inner product, in terms of the norm.
Polarization identity: The imaginary part of the inner product, in terms of the norm.
Polarization identity: The inner product, in terms of the norm.
A linear isometry preserves the inner product.
A linear isometric equivalence preserves the inner product.
A linear map that preserves the inner product is a linear isometry.
Equations
- f.isometry_of_inner h = {to_linear_map := f, norm_map' := _}
A linear equivalence that preserves the inner product is a linear isometric equivalence.
Equations
- f.isometry_of_inner h = {to_linear_equiv := f, norm_map' := _}
The inner product of a nonzero vector with a nonzero multiple of itself, divided by the product of their norms, has absolute value 1.
The inner product of a nonzero vector with a nonzero multiple of itself, divided by the product of their norms, has absolute value 1.
The inner product of a nonzero vector with a positive multiple of itself, divided by the product of their norms, has value 1.
The inner product of a nonzero vector with a negative multiple of itself, divided by the product of their norms, has value -1.
The inner product of two vectors, divided by the product of their norms, has absolute value 1 if and only if they are nonzero and one is a multiple of the other. One form of equality case for Cauchy-Schwarz.
The inner product of two vectors, divided by the product of their norms, has absolute value 1 if and only if they are nonzero and one is a multiple of the other. One form of equality case for Cauchy-Schwarz.
If the inner product of two vectors is equal to the product of their norms, then the two vectors
are multiples of each other. One form of the equality case for Cauchy-Schwarz.
Compare inner_eq_norm_mul_iff
, which takes the stronger hypothesis โชx, yโซ = โฅxโฅ * โฅyโฅ
.
The inner product of two vectors, divided by the product of their norms, has value 1 if and only if they are nonzero and one is a positive multiple of the other.
The inner product of two vectors, divided by the product of their norms, has value -1 if and only if they are nonzero and one is a negative multiple of the other.
If the inner product of two vectors is equal to the product of their norms (i.e.,
โชx, yโซ = โฅxโฅ * โฅyโฅ
), then the two vectors are nonnegative real multiples of each other. One form
of the equality case for Cauchy-Schwarz.
Compare abs_inner_eq_norm_iff
, which takes the weaker hypothesis abs โชx, yโซ = โฅxโฅ * โฅyโฅ
.
If the inner product of two vectors is equal to the product of their norms (i.e.,
โชx, yโซ = โฅxโฅ * โฅyโฅ
), then the two vectors are nonnegative real multiples of each other. One form
of the equality case for Cauchy-Schwarz.
Compare abs_inner_eq_norm_iff
, which takes the weaker hypothesis abs โชx, yโซ = โฅxโฅ * โฅyโฅ
.
If the inner product of two unit vectors is 1
, then the two vectors are equal. One form of
the equality case for Cauchy-Schwarz.
If the inner product of two unit vectors is strictly less than 1
, then the two vectors are
distinct. One form of the equality case for Cauchy-Schwarz.
The inner product of two weighted sums, where the weights in each sum add to 0, in terms of the norms of pairwise differences.
The inner product with a fixed left element, as a continuous linear map. This can be upgraded to a continuous map which is jointly conjugate-linear in the left argument and linear in the right argument, once (TODO) conjugate-linear maps have been defined.
Equations
- inner_right v = {to_fun := ฮป (w : E), inner v w, map_add' := _, map_smul' := _}.mk_continuous โฅvโฅ _
Inner product space structure on product spaces #
Equations
- pi_Lp.inner_product_space f = {to_normed_group := pi_Lp.normed_group 2 one_le_two f (ฮป (i : ฮน), inner_product_space.to_normed_group ๐), to_normed_space := pi_Lp.normed_space 2 one_le_two f ๐ (ฮป (i : ฮน), inner_product_space.to_normed_space), to_has_inner := {inner := ฮป (x y : pi_Lp 2 one_le_two f), โ (i : ฮน), inner (x i) (y i)}, norm_sq_eq_inner := _, conj_sym := _, add_left := _, smul_left := _}
A field ๐
satisfying is_R_or_C
is itself a ๐
-inner product space.
Equations
- is_R_or_C.inner_product_space = {to_normed_group := normed_ring.to_normed_group normed_comm_ring.to_normed_ring, to_normed_space := normed_field.to_normed_space nondiscrete_normed_field.to_normed_field, to_has_inner := {inner := ฮป (x y : ๐), (โis_R_or_C.conj x) * y}, norm_sq_eq_inner := _, conj_sym := _, add_left := _, smul_left := _}
The standard real/complex Euclidean space, functions on a finite type. For an n
-dimensional
space use euclidean_space ๐ (fin n)
.
Equations
- euclidean_space ๐ n = pi_Lp 2 one_le_two (ฮป (i : n), ๐)
Inner product space structure on subspaces #
Induced inner product on a submodule.
Equations
- W.inner_product_space = {to_normed_group := W.normed_group, to_normed_space := {to_module := normed_space.to_module W.normed_space, norm_smul_le := _}, to_has_inner := {inner := ฮป (x y : โฅW), inner โx โy}, norm_sq_eq_inner := _, conj_sym := _, add_left := _, smul_left := _}
A general inner product implies a real inner product. This is not registered as an instance
since it creates problems with the case ๐ = โ
.
Equations
- has_inner.is_R_or_C_to_real ๐ E = {inner := ฮป (x y : E), โis_R_or_C.re (inner x y)}
A general inner product space structure implies a real inner product structure. This is not
registered as an instance since it creates problems with the case ๐ = โ
, but in can be used in a
proof to obtain a real inner product space structure from a given ๐
-inner product space
structure.
Equations
- inner_product_space.is_R_or_C_to_real ๐ E = {to_normed_group := inner_product_space.to_normed_group ๐ _inst_2, to_normed_space := {to_module := normed_space.to_module (normed_space.restrict_scalars โ ๐ E), norm_smul_le := _}, to_has_inner := {inner := inner (has_inner.is_R_or_C_to_real ๐ E)}, norm_sq_eq_inner := _, conj_sym := _, add_left := _, smul_left := _}
A complex inner product implies a real inner product
Derivative of the inner product #
In this section we prove that the inner product and square of the norm in an inner space are
infinitely โ
-smooth. In order to state these results, we need a normed_space โ E
instance. Though we can deduce this structure from inner_product_space ๐ E
, this instance may be
not definitionally equal to some other โnaturalโ instance. So, we assume [normed_space โ E]
and
[is_scalar_tower โ ๐ E]
. In both interesting cases ๐ = โ
and ๐ = โ
we have these instances.
Derivative of the inner product.
Equations
Continuity and measurability of the inner product #
Since the inner product is โ
-smooth, it is continuous. We do not need a [normed_space โ E]
structure to state this fact and its corollaries, so we introduce them in the proof instead.
Equations
- euclidean_space.inner_product_space = pi_Lp.inner_product_space (ฮป (i : ฮน), ๐)
An orthonormal basis on a fintype ฮน
for an inner product space induces an isometry with
euclidean_space ๐ ฮน
.
Equations
โ
is isometric to โยฒ with the Euclidean inner product.
Equations
- complex.isometry_euclidean = complex.basis_one_I.isometry_euclidean_of_orthonormal complex.isometry_euclidean._proof_1
Orthogonal projection in inner product spaces #
Existence of minimizers
Let u
be a point in a real inner product space, and let K
be a nonempty complete convex subset.
Then there exists a (unique) v
in K
that minimizes the distance โฅu - vโฅ
to u
.
Characterization of minimizers for the projection on a convex set in a real inner product space.
Existence of projections on complete subspaces.
Let u
be a point in an inner product space, and let K
be a nonempty complete subspace.
Then there exists a (unique) v
in K
that minimizes the distance โฅu - vโฅ
to u
.
This point v
is usually called the orthogonal projection of u
onto K
.
Characterization of minimizers in the projection on a subspace, in the real case.
Let u
be a point in a real inner product space, and let K
be a nonempty subspace.
Then point v
minimizes the distance โฅu - vโฅ
over points in K
if and only if
for all w โ K
, โชu - v, wโซ = 0
(i.e., u - v
is orthogonal to the subspace K
).
This is superceded by norm_eq_infi_iff_inner_eq_zero
that gives the same conclusion over
any is_R_or_C
field.
Characterization of minimizers in the projection on a subspace.
Let u
be a point in an inner product space, and let K
be a nonempty subspace.
Then point v
minimizes the distance โฅu - vโฅ
over points in K
if and only if
for all w โ K
, โชu - v, wโซ = 0
(i.e., u - v
is orthogonal to the subspace K
)
The orthogonal projection onto a complete subspace, as an
unbundled function. This definition is only intended for use in
setting up the bundled version orthogonal_projection
and should not
be used once that is defined.
Equations
- orthogonal_projection_fn K v = _.some
The unbundled orthogonal projection is in the given subspace. This lemma is only intended for use in setting up the bundled version and should not be used once that is defined.
The characterization of the unbundled orthogonal projection. This lemma is only intended for use in setting up the bundled version and should not be used once that is defined.
The unbundled orthogonal projection is the unique point in K
with the orthogonality property. This lemma is only intended for use
in setting up the bundled version and should not be used once that is
defined.
The orthogonal projection onto a complete subspace.
Equations
- orthogonal_projection K = {to_fun := ฮป (v : E), โจorthogonal_projection_fn K v, _โฉ, map_add' := _, map_smul' := _}.mk_continuous 1 _
The characterization of the orthogonal projection.
The orthogonal projection is the unique point in K
with the
orthogonality property.
The orthogonal projections onto equal subspaces are coerced back to the same point in E
.
The orthogonal projection sends elements of K
to themselves.
The orthogonal projection onto the trivial submodule is the zero map.
The orthogonal projection has norm โค 1
.
Formula for orthogonal projection onto a single vector.
Formula for orthogonal projection onto a single unit vector.
The subspace of vectors orthogonal to a given subspace.
A vector in K
is orthogonal to one in Kแฎ
.
A vector in Kแฎ
is orthogonal to one in K
.
A vector in (๐ โ u)แฎ
is orthogonal to u
.
A vector in (๐ โ u)แฎ
is orthogonal to u
.
K
and Kแฎ
have trivial intersection.
K
and Kแฎ
have trivial intersection.
Kแฎ
can be characterized as the intersection of the kernels of the operations of
inner product with each of the elements of K
.
The orthogonal complement of any submodule K
is closed.
In a complete space, the orthogonal complement of any submodule K
is complete.
submodule.orthogonal
gives a galois_connection
between
submodule ๐ E
and its order_dual
.
submodule.orthogonal
reverses the โค
ordering of two
subspaces.
K
is contained in Kแฎแฎ
.
The inf of an indexed family of orthogonal subspaces equals the subspace orthogonal to the sup.
If Kโ
is complete and contained in Kโ
, Kโ
and Kโแฎ โ Kโ
span Kโ
.
If K
is complete, K
and Kแฎ
span the whole space.
If K
is complete, K
and Kแฎ
span the whole space. Version using complete_space
.
If K
is complete, any v
in E
can be expressed as a sum of elements of K
and Kแฎ
.
If K
is complete, then the orthogonal complement of its orthogonal complement is itself.
If K
is complete, K
and Kแฎ
are complements of each other.
A point in K
with the orthogonality property (here characterized in terms of Kแฎ
) must be the
orthogonal projection.
A point in K
with the orthogonality property (here characterized in terms of Kแฎ
) must be the
orthogonal projection.
The orthogonal projection onto K
of an element of Kแฎ
is zero.
The orthogonal projection onto Kแฎ
of an element of K
is zero.
The orthogonal projection onto (๐ โ v)แฎ
of v
is zero.
In a complete space E
, a vector splits as the sum of its orthogonal projections onto a
complete submodule K
and onto the orthogonal complement of K
.