mathlib documentation

linear_algebra.dimension

Dimension of modules and vector spaces #

Main definitions #

Although this definition works for any module over a (semi)ring, for now we quickly specialize to division rings and then to fields. There's lots of generalization still to be done.

Main statements #

Implementation notes #

Many theorems in this file are not universe-generic when they relate dimensions in different universes. They should be as general as they can be without inserting lifts. The types V, V', ... all live in different universes, and V₁, V₂, ... all live in the same universe.

def module.rank (K : Type u) (V : Type v) [semiring K] [add_comm_monoid V] [module K V] :

The rank of a module, defined as a term of type cardinal.

We define this as the supremum of the cardinalities of linearly independent subsets.

In a vector space, this is the same as the dimension of the space (i.e. the cardinality of any basis).

The definition is marked as protected to avoid conflicts with _root_.rank, the rank of a linear map.

Equations
theorem basis.le_span {K : Type u} {V : Type v} {ι : Type w} [division_ring K] [add_comm_group V] [module K V] {J : set V} (v : basis ι K V) (hJ : submodule.span K J = ) :
theorem mk_eq_mk_of_basis {K : Type u} {V : Type v} {ι : Type w} {ι' : Type w'} [division_ring K] [add_comm_group V] [module K V] (v : basis ι K V) (v' : basis ι' K V) :
(# ι).lift = (# ι').lift

The dimension theorem: if v and v' are two bases, their index types have the same cardinalities.

theorem mk_eq_mk_of_basis' {K : Type u} {V : Type v} {ι : Type w} [division_ring K] [add_comm_group V] [module K V] {ι' : Type w} (v : basis ι K V) (v' : basis ι' K V) :
# ι = # ι'
theorem basis.mk_eq_dim'' {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] {ι : Type v} (v : basis ι K V) :
# ι = module.rank K V
theorem basis.mk_range_eq_dim {K : Type u} {V : Type v} {ι : Type w} [division_ring K] [add_comm_group V] [module K V] (v : basis ι K V) :
theorem basis.mk_eq_dim {K : Type u} {V : Type v} {ι : Type w} [division_ring K] [add_comm_group V] [module K V] (v : basis ι K V) :
(# ι).lift = (module.rank K V).lift
theorem basis.mk_eq_dim' {K : Type u} {V : Type v} {ι : Type w} [division_ring K] [add_comm_group V] [module K V] (v : basis ι K V) :
(# ι).lift = (module.rank K V).lift
theorem dim_le {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] {n : } (H : ∀ (s : finset V), linear_independent K (λ (i : s), i)s.card n) :
theorem basis.nonempty_fintype_index_of_dim_lt_omega {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] {ι : Type u_1} (b : basis ι K V) (h : module.rank K V < cardinal.omega) :

If a vector space has a finite dimension, all bases are indexed by a finite type.

def basis.fintype_index_of_dim_lt_omega {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] {ι : Type u_1} (b : basis ι K V) (h : module.rank K V < cardinal.omega) :

If a vector space has a finite dimension, all bases are indexed by a finite type.

Equations
theorem basis.finite_index_of_dim_lt_omega {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] {ι : Type u_1} {s : set ι} (b : basis s K V) (h : module.rank K V < cardinal.omega) :

If a vector space has a finite dimension, all bases are indexed by a finite set.

If a vector space has a finite dimension, the index set of basis.of_vector_space is finite.

theorem linear_equiv.lift_dim_eq {K : Type u} {V : Type v} {V' : Type v'} [division_ring K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] (f : V ≃ₗ[K] V') :

Two linearly equivalent vector spaces have the same dimension, a version with different universes.

theorem linear_equiv.dim_eq {K : Type u} {V V₁ : Type v} [division_ring K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (f : V ≃ₗ[K] V₁) :

Two linearly equivalent vector spaces have the same dimension.

theorem nonempty_linear_equiv_of_lift_dim_eq {K : Type u} {V : Type v} {V' : Type v'} [division_ring K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] (cond : (module.rank K V).lift = (module.rank K V').lift) :

Two vector spaces are isomorphic if they have the same dimension.

theorem nonempty_linear_equiv_of_dim_eq {K : Type u} {V V₁ : Type v} [division_ring K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (cond : module.rank K V = module.rank K V₁) :
nonempty (V ≃ₗ[K] V₁)

Two vector spaces are isomorphic if they have the same dimension.

def linear_equiv.of_lift_dim_eq {K : Type u} (V : Type v) (V' : Type v') [division_ring K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] (cond : (module.rank K V).lift = (module.rank K V').lift) :
V ≃ₗ[K] V'

Two vector spaces are isomorphic if they have the same dimension.

Equations
def linear_equiv.of_dim_eq {K : Type u} (V V₁ : Type v) [division_ring K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (cond : module.rank K V = module.rank K V₁) :
V ≃ₗ[K] V₁

Two vector spaces are isomorphic if they have the same dimension.

Equations
theorem linear_equiv.nonempty_equiv_iff_lift_dim_eq {K : Type u} {V : Type v} {V' : Type v'} [division_ring K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] :

Two vector spaces are isomorphic if and only if they have the same dimension.

theorem linear_equiv.nonempty_equiv_iff_dim_eq {K : Type u} {V V₁ : Type v} [division_ring K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] :

Two vector spaces are isomorphic if and only if they have the same dimension.

@[simp]
theorem dim_bot {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] :
@[simp]
theorem dim_top {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] :
theorem dim_of_field (K : Type u_1) [field K] :
theorem dim_span {K : Type u} {V : Type v} {ι : Type w} [division_ring K] [add_comm_group V] [module K V] {v : ι → V} (hv : linear_independent K v) :
theorem dim_span_set {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] {s : set V} (hs : linear_independent K (λ (x : s), x)) :
theorem cardinal_lift_le_dim_of_linear_independent {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] {ι : Type w} {v : ι → V} (hv : linear_independent K v) :
theorem cardinal_le_dim_of_linear_independent {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] {ι : Type v} {v : ι → V} (hv : linear_independent K v) :
theorem cardinal_le_dim_of_linear_independent' {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] {s : set V} (hs : linear_independent K (λ (x : s), x)) :
theorem dim_span_le {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] (s : set V) :
theorem dim_span_of_finset {K : Type u} {V : Type v} [division_ring K] [add_comm_group V] [module K V] (s : finset V) :
theorem dim_prod {K : Type u} {V V₁ : Type v} [division_ring K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] :
module.rank K (V × V₁) = module.rank K V + module.rank K V₁
theorem dim_quotient_add_dim {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] (p : submodule K V) :
theorem dim_quotient_le {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] (p : submodule K V) :
theorem dim_range_add_dim_ker {K : Type u} {V V₁ : Type v} [field K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (f : V →ₗ[K] V₁) :

rank-nullity theorem

theorem dim_range_le {K : Type u} {V V₁ : Type v} [field K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (f : V →ₗ[K] V₁) :
theorem dim_map_le {K : Type u} {V V₁ : Type v} [field K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (f : V →ₗ[K] V₁) (p : submodule K V) :
theorem dim_range_of_surjective {K : Type u} {V : Type v} {V' : Type v'} [field K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] (f : V →ₗ[K] V') (h : function.surjective f) :
theorem dim_eq_of_surjective {K : Type u} {V V₁ : Type v} [field K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (f : V →ₗ[K] V₁) (h : function.surjective f) :
theorem dim_le_of_surjective {K : Type u} {V V₁ : Type v} [field K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (f : V →ₗ[K] V₁) (h : function.surjective f) :
theorem dim_eq_of_injective {K : Type u} {V V₁ : Type v} [field K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (f : V →ₗ[K] V₁) (h : function.injective f) :
theorem dim_submodule_le {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] (s : submodule K V) :
theorem dim_le_of_injective {K : Type u} {V V₁ : Type v} [field K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (f : V →ₗ[K] V₁) (h : function.injective f) :
theorem dim_le_of_submodule {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] (s t : submodule K V) (h : s t) :
theorem linear_independent_le_dim {K : Type u} {V : Type v} {ι : Type w} [field K] [add_comm_group V] [module K V] {v : ι → V} (hv : linear_independent K v) :
theorem linear_independent_le_dim' {K : Type u} {V : Type v} {ι : Type w} [field K] [add_comm_group V] [module K V] {v : ι → V} (hs : linear_independent K v) :
theorem dim_add_dim_split {K : Type u} {V V₁ V₂ V₃ : Type v} [field K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] [add_comm_group V₂] [module K V₂] [add_comm_group V₃] [module K V₃] (db : V₂ →ₗ[K] V) (eb : V₃ →ₗ[K] V) (cd : V₁ →ₗ[K] V₂) (ce : V₁ →ₗ[K] V₃) (hde : db.range eb.range) (hgd : cd.ker = ) (eq : db.comp cd = eb.comp ce) (eq₂ : ∀ (d : V₂) (e : V₃), db d = eb e(∃ (c : V₁), cd c = d ce c = e)) :

This is mostly an auxiliary lemma for dim_sup_add_dim_inf_eq.

theorem dim_sup_add_dim_inf_eq {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] (s t : submodule K V) :
theorem dim_add_le_dim_add_dim {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] (s t : submodule K V) :
theorem dim_pi {K : Type u} {η : Type u₁'} {φ : η → Type u_1} [field K] [fintype η] [Π (i : η), add_comm_group (φ i)] [Π (i : η), module K (φ i)] :
module.rank K (Π (i : η), φ i) = cardinal.sum (λ (i : η), module.rank K (φ i))
theorem dim_fun {K : Type u} [field K] {V η : Type u} [fintype η] [add_comm_group V] [module K V] :
module.rank K (η → V) = ((fintype.card η)) * module.rank K V
theorem dim_fun_eq_lift_mul {K : Type u} {V : Type v} {η : Type u₁'} [field K] [add_comm_group V] [module K V] [fintype η] :
module.rank K (η → V) = ((fintype.card η)) * (module.rank K V).lift
theorem dim_fun' {K : Type u} {η : Type u₁'} [field K] [fintype η] :
module.rank K (η → K) = (fintype.card η)
theorem dim_fin_fun {K : Type u} [field K] (n : ) :
module.rank K (fin n → K) = n
theorem exists_mem_ne_zero_of_ne_bot {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] {s : submodule K V} (h : s ) :
∃ (b : V), b s b 0
theorem exists_mem_ne_zero_of_dim_pos {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] {s : submodule K V} (h : 0 < module.rank K s) :
∃ (b : V), b s b 0
def rank {K : Type u} {V : Type v} {V' : Type v'} [field K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] (f : V →ₗ[K] V') :

rank f is the rank of a linear_map f, defined as the dimension of f.range.

Equations
theorem rank_le_domain {K : Type u} {V V₁ : Type v} [field K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (f : V →ₗ[K] V₁) :
theorem rank_le_range {K : Type u} {V V₁ : Type v} [field K] [add_comm_group V] [module K V] [add_comm_group V₁] [module K V₁] (f : V →ₗ[K] V₁) :
theorem rank_add_le {K : Type u} {V : Type v} {V' : Type v'} [field K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] (f g : V →ₗ[K] V') :
rank (f + g) rank f + rank g
@[simp]
theorem rank_zero {K : Type u} {V : Type v} {V' : Type v'} [field K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] :
rank 0 = 0
theorem rank_finset_sum_le {K : Type u} {V : Type v} {V' : Type v'} [field K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] {η : Type u_1} (s : finset η) (f : η → (V →ₗ[K] V')) :
rank (∑ (d : η) in s, f d) ∑ (d : η) in s, rank (f d)
theorem rank_comp_le1 {K : Type u} {V : Type v} {V' : Type v'} {V'' : Type v''} [field K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] [add_comm_group V''] [module K V''] (g : V →ₗ[K] V') (f : V' →ₗ[K] V'') :
rank (f.comp g) rank f
theorem rank_comp_le2 {K : Type u} {V : Type v} {V' V'₁ : Type v'} [field K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] [add_comm_group V'₁] [module K V'₁] (g : V →ₗ[K] V') (f : V' →ₗ[K] V'₁) :
rank (f.comp g) rank g
theorem dim_zero_iff_forall_zero {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] :
module.rank K V = 0 ∀ (x : V), x = 0
theorem dim_zero_iff {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] :
def basis.of_dim_eq_zero {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] {ι : Type u_1} [is_empty ι] (hV : module.rank K V = 0) :
basis ι K V

The ι indexed basis on V, where ι is an empty type and V is zero-dimensional.

See also finite_dimensional.fin_basis.

Equations
@[simp]
theorem basis.of_dim_eq_zero_apply {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] {ι : Type u_1} [is_empty ι] (hV : module.rank K V = 0) (i : ι) :
theorem dim_pos_iff_exists_ne_zero {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] :
0 < module.rank K V ∃ (x : V), x 0
theorem dim_pos_iff_nontrivial {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] :
theorem dim_pos {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] [h : nontrivial V] :
theorem le_dim_iff_exists_linear_independent {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] {c : cardinal} :
c module.rank K V ∃ (s : set V), # s = c linear_independent K coe
theorem le_dim_iff_exists_linear_independent_finset {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] {n : } :
theorem le_rank_iff_exists_linear_independent {K : Type u} {V : Type v} {V' : Type v'} [field K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] {c : cardinal} {f : V →ₗ[K] V'} :
c rank f ∃ (s : set V), (# s).lift = c.lift linear_independent K (λ (x : s), f x)
theorem le_rank_iff_exists_linear_independent_finset {K : Type u} {V : Type v} {V' : Type v'} [field K] [add_comm_group V] [module K V] [add_comm_group V'] [module K V'] {n : } {f : V →ₗ[K] V'} :
n rank f ∃ (s : finset V), s.card = n linear_independent K (λ (x : s), f x)
theorem dim_le_one_iff {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] :
module.rank K V 1 ∃ (v₀ : V), ∀ (v : V), ∃ (r : K), r v₀ = v

A vector space has dimension at most 1 if and only if there is a single vector of which all vectors are multiples.

theorem dim_submodule_le_one_iff {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] (s : submodule K V) :
module.rank K s 1 ∃ (v₀ : V) (H : v₀ s), s submodule.span K {v₀}

A submodule has dimension at most 1 if and only if there is a single vector in the submodule such that the submodule is contained in its span.

theorem dim_submodule_le_one_iff' {K : Type u} {V : Type v} [field K] [add_comm_group V] [module K V] (s : submodule K V) :
module.rank K s 1 ∃ (v₀ : V), s submodule.span K {v₀}

A submodule has dimension at most 1 if and only if there is a single vector, not necessarily in the submodule, such that the submodule is contained in its span.

theorem linear_equiv.dim_eq_lift {K : Type u} {V : Type v} {E : Type v'} [division_ring K] [add_comm_group V] [module K V] [add_comm_group E] [module K E] (f : V ≃ₗ[K] E) :

Version of linear_equiv.dim_eq without universe constraints.