Documentation

Mathlib.LinearAlgebra.LinearIndependent.Basic

Linear independence #

This file collects basic consequences of linear (in)dependence and includes specialized tests for specific families of vectors.

Main statements #

We prove several specialized tests for linear independence of families of vectors and of sets of vectors.

In many cases we additionally provide dot-style operations (e.g., LinearIndependent.union) to make the linear independence tests usable as hv.insert ha etc.

TODO #

Rework proofs to hold in semirings, by avoiding the path through ker (Finsupp.linearCombination R v) = ⊥.

Tags #

linearly dependent, linear dependence, linearly independent, linear independence

theorem LinearIndependent.restrict_scalars {ι : Type u'} {R : Type u_2} {K : Type u_3} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] [Semiring K] [SMulWithZero R K] [Module K M] [IsScalarTower R K M] (hinj : Function.Injective fun (r : R) => r 1) (li : LinearIndependent K v) :

A set of linearly independent vectors in a module M over a semiring K is also linearly independent over a subring R of K.

See also LinearIndependent.restrict_scalars' for a verison with more convenient typeclass assumptions.

TODO : LinearIndepOn version.

theorem Submodule.range_ker_disjoint {ι : Type u'} {R : Type u_2} {M : Type u_4} {M' : Type u_5} {v : ιM} [Semiring R] [AddCommMonoid M] [AddCommMonoid M'] [Module R M] [Module R M'] {f : M →ₗ[R] M'} (hv : LinearIndependent R (f v)) :

If v is an injective family of vectors such that f ∘ v is linearly independent, then v spans a submodule disjoint from the kernel of f. TODO : LinearIndepOn version.

theorem LinearIndependent.map_of_injective_injectiveₛ {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] {R' : Type u_6} {M' : Type u_7} [Semiring R'] [AddCommMonoid M'] [Module R' M'] (hv : LinearIndependent R v) (i : R'R) (j : M →+ M') (hi : Function.Injective i) (hj : Function.Injective j) (hc : ∀ (r : R') (m : M), j (i r m) = r j m) :

If M / R and M' / R' are modules, i : R' → R is a map, j : M →+ M' is a monoid map, such that they are both injective, and compatible with the scalar multiplications on M and M', then j sends linearly independent families of vectors to linearly independent families of vectors. As a special case, taking R = R' it is LinearIndependent.map_injOn. TODO : LinearIndepOn version.

theorem LinearIndependent.map_of_surjective_injectiveₛ {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] {R' : Type u_6} {M' : Type u_7} [Semiring R'] [AddCommMonoid M'] [Module R' M'] (hv : LinearIndependent R v) (i : RR') (j : M →+ M') (hi : Function.Surjective i) (hj : Function.Injective j) (hc : ∀ (r : R) (m : M), j (r m) = i r j m) :

If M / R and M' / R' are modules, i : R → R' is a surjective map, and j : M →+ M' is an injective monoid map, such that the scalar multiplications on M and M' are compatible, then j sends linearly independent families of vectors to linearly independent families of vectors. As a special case, taking R = R' it is LinearIndependent.map_injOn. TODO : LinearIndepOn version.

theorem LinearIndependent.map_injOn {ι : Type u'} {R : Type u_2} {M : Type u_4} {M' : Type u_5} {v : ιM} [Semiring R] [AddCommMonoid M] [AddCommMonoid M'] [Module R M] [Module R M'] (hv : LinearIndependent R v) (f : M →ₗ[R] M') (hf_inj : Set.InjOn f (Submodule.span R (Set.range v))) :

If a linear map is injective on the span of a family of linearly independent vectors, then the family stays linearly independent after composing with the linear map. See LinearIndependent.map for the version with Set.InjOn replaced by Disjoint when working over a ring.

theorem LinearIndepOn.map_injOn {ι : Type u'} {R : Type u_2} {s : Set ι} {M : Type u_4} {M' : Type u_5} {v : ιM} [Semiring R] [AddCommMonoid M] [AddCommMonoid M'] [Module R M] [Module R M'] (hv : LinearIndepOn R v s) (f : M →ₗ[R] M') (hf_inj : Set.InjOn f (Submodule.span R (v '' s))) :
LinearIndepOn R (f v) s
theorem LinearIndepOn.comp_of_image {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set ι'} {f : ι'ι} (h : LinearIndepOn R v (f '' s)) (hf : Set.InjOn f s) :
LinearIndepOn R (v f) s
@[deprecated LinearIndepOn.comp_of_image (since := "2025-02-14")]
theorem LinearIndependent.comp_of_image {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set ι'} {f : ι'ι} (h : LinearIndepOn R v (f '' s)) (hf : Set.InjOn f s) :
LinearIndepOn R (v f) s

Alias of LinearIndepOn.comp_of_image.

theorem LinearIndepOn.image_of_comp {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {s : Set ι} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] (f : ιι') (g : ι'M) (hs : LinearIndepOn R (g f) s) :
LinearIndepOn R g (f '' s)
@[deprecated LinearIndepOn.image_of_comp (since := "2025-02-14")]
theorem LinearIndependent.image_of_comp {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {s : Set ι} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] (f : ιι') (g : ι'M) (hs : LinearIndepOn R (g f) s) :
LinearIndepOn R g (f '' s)

Alias of LinearIndepOn.image_of_comp.

theorem LinearIndepOn.id_image {ι : Type u'} {R : Type u_2} {s : Set ι} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] (hs : LinearIndepOn R v s) :
@[deprecated LinearIndepOn.id_image (since := "2025-02-14")]
theorem LinearIndependent.image {ι : Type u'} {R : Type u_2} {s : Set ι} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] (hs : LinearIndepOn R v s) :

Alias of LinearIndepOn.id_image.

theorem LinearIndependent.group_smul {ι : Type u'} {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {G : Type u_6} [hG : Group G] [DistribMulAction G R] [DistribMulAction G M] [IsScalarTower G R M] [SMulCommClass G R M] {v : ιM} (hv : LinearIndependent R v) (w : ιG) :
@[simp]
theorem LinearIndependent.group_smul_iff {ι : Type u'} {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {G : Type u_6} [hG : Group G] [DistribMulAction G R] [DistribMulAction G M] [IsScalarTower G R M] [SMulCommClass G R M] (v : ιM) (w : ιG) :
theorem LinearIndependent.units_smul {ι : Type u'} {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {v : ιM} (hv : LinearIndependent R v) (w : ιRˣ) :
@[simp]
theorem LinearIndependent.units_smul_iff {ι : Type u'} {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] (v : ιM) (w : ιRˣ) :
theorem linearIndependent_span {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] (hs : LinearIndependent R v) :
LinearIndependent R fun (i : ι) => v i,

Every finite subset of a linearly independent set is linearly independent.

theorem LinearIndepOn.mono {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] {t s : Set ι} (hs : LinearIndepOn R v s) (h : t s) :
@[deprecated LinearIndepOn.mono (since := "2025-02-15")]
theorem LinearIndependent.mono {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] {t s : Set ι} (hs : LinearIndepOn R v s) (h : t s) :

Alias of LinearIndepOn.mono.

theorem linearIndepOn_of_finite {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] (s : Set ι) (H : ts, t.FiniteLinearIndepOn R v t) :
@[deprecated linearIndepOn_of_finite (since := "2025-02-15")]
theorem linearIndependent_of_finite {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] (s : Set ι) (H : ts, t.FiniteLinearIndepOn R v t) :

Alias of linearIndepOn_of_finite.

theorem LinearIndependent.eq_of_smul_apply_eq_smul_apply {ι : Type u'} {R : Type u_2} [Semiring R] {M : Type u_6} [AddCommMonoid M] [Module R M] {v : ιM} (li : LinearIndependent R v) (c d : R) (i j : ι) (hc : c 0) (h : c v i = d v j) :
i = j

Linear independent families are injective, even if you multiply either side.

The following lemmas use the subtype defined by a set in M as the index set ι.

theorem LinearIndependent.disjoint_span_image {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] (hv : LinearIndependent R v) {s t : Set ι} (hs : Disjoint s t) :
theorem LinearIndependent.not_mem_span_image {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] [Nontrivial R] (hv : LinearIndependent R v) {s : Set ι} {x : ι} (h : xs) :
v xSubmodule.span R (v '' s)
theorem LinearIndependent.linearCombination_ne_of_not_mem_support {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] [Nontrivial R] (hv : LinearIndependent R v) {x : ι} (f : ι →₀ R) (h : xf.support) :
theorem LinearIndepOn.id_imageₛ {R : Type u_2} {M : Type u_4} {M' : Type u_5} [Semiring R] [AddCommMonoid M] [AddCommMonoid M'] [Module R M] [Module R M'] {s : Set M} {f : M →ₗ[R] M'} (hs : LinearIndepOn R id s) (hf_inj : Set.InjOn f (Submodule.span R s)) :
LinearIndepOn R id (f '' s)
@[deprecated LinearIndepOn.id_imageₛ (since := "2025-02-14")]
theorem LinearIndependent.image_subtypeₛ {R : Type u_2} {M : Type u_4} {M' : Type u_5} [Semiring R] [AddCommMonoid M] [AddCommMonoid M'] [Module R M] [Module R M'] {s : Set M} {f : M →ₗ[R] M'} (hs : LinearIndepOn R id s) (hf_inj : Set.InjOn f (Submodule.span R s)) :
LinearIndepOn R id (f '' s)

Alias of LinearIndepOn.id_imageₛ.

theorem surjective_of_linearIndependent_of_span {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {M : Type u_4} {v : ιM} [Semiring R] [AddCommMonoid M] [Module R M] [Nontrivial R] (hv : LinearIndependent R v) (f : ι' ι) (hss : Set.range v (Submodule.span R (Set.range (v f)))) :
theorem eq_of_linearIndepOn_id_of_span_subtype {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] [Nontrivial R] {s t : Set M} (hs : LinearIndepOn R id s) (h : t s) (hst : s (Submodule.span R t)) :
s = t
@[deprecated eq_of_linearIndepOn_id_of_span_subtype (since := "2025-02-15")]
theorem eq_of_linearIndependent_of_span_subtype {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] [Nontrivial R] {s t : Set M} (hs : LinearIndepOn R id s) (h : t s) (hst : s (Submodule.span R t)) :
s = t

Alias of eq_of_linearIndepOn_id_of_span_subtype.

theorem le_of_span_le_span {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] [Nontrivial R] {s t u : Set M} (hl : LinearIndepOn R id u) (hsu : s u) (htu : t u) (hst : Submodule.span R s Submodule.span R t) :
s t
theorem span_le_span_iff {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] [Nontrivial R] {s t u : Set M} (hl : LinearIndependent R Subtype.val) (hsu : s u) (htu : t u) :
theorem LinearIndependent.eq_coords_of_eq {ι : Type u'} {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] [Fintype ι] {v : ιM} (hv : LinearIndependent R v) {f g : ιR} (heq : i : ι, f i v i = i : ι, g i v i) (i : ι) :
f i = g i

If ∑ i, f i • v i = ∑ i, g i • v i, then for all i, f i = g i.

theorem LinearIndependent.map {ι : Type u'} {R : Type u_2} {M : Type u_4} {M' : Type u_5} {v : ιM} [Ring R] [AddCommGroup M] [AddCommGroup M'] [Module R M] [Module R M'] (hv : LinearIndependent R v) {f : M →ₗ[R] M'} (hf_inj : Disjoint (Submodule.span R (Set.range v)) (LinearMap.ker f)) :

If v is a linearly independent family of vectors and the kernel of a linear map f is disjoint with the submodule spanned by the vectors of v, then f ∘ v is a linearly independent family of vectors. See also LinearIndependent.map' for a special case assuming ker f = ⊥.

theorem LinearIndependent.map' {ι : Type u'} {R : Type u_2} {M : Type u_4} {M' : Type u_5} {v : ιM} [Ring R] [AddCommGroup M] [AddCommGroup M'] [Module R M] [Module R M'] (hv : LinearIndependent R v) (f : M →ₗ[R] M') (hf_inj : LinearMap.ker f = ) :

An injective linear map sends linearly independent families of vectors to linearly independent families of vectors. See also LinearIndependent.map for a more general statement.

theorem LinearIndependent.map_of_injective_injective {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Ring R] [AddCommGroup M] [Module R M] {R' : Type u_6} {M' : Type u_7} [Ring R'] [AddCommGroup M'] [Module R' M'] (hv : LinearIndependent R v) (i : R'R) (j : M →+ M') (hi : ∀ (r : R'), i r = 0r = 0) (hj : ∀ (m : M), j m = 0m = 0) (hc : ∀ (r : R') (m : M), j (i r m) = r j m) :

If M / R and M' / R' are modules, i : R' → R is a map, j : M →+ M' is a monoid map, such that they send non-zero elements to non-zero elements, and compatible with the scalar multiplications on M and M', then j sends linearly independent families of vectors to linearly independent families of vectors. As a special case, taking R = R' it is LinearIndependent.map'.

theorem LinearIndependent.map_of_surjective_injective {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ιM} [Ring R] [AddCommGroup M] [Module R M] {R' : Type u_6} {M' : Type u_7} [Ring R'] [AddCommGroup M'] [Module R' M'] (hv : LinearIndependent R v) (i : RR') (j : M →+ M') (hi : Function.Surjective i) (hj : ∀ (m : M), j m = 0m = 0) (hc : ∀ (r : R) (m : M), j (r m) = i r j m) :

If M / R and M' / R' are modules, i : R → R' is a surjective map which maps zero to zero, j : M →+ M' is a monoid map which sends non-zero elements to non-zero elements, such that the scalar multiplications on M and M' are compatible, then j sends linearly independent families of vectors to linearly independent families of vectors. As a special case, taking R = R' it is LinearIndependent.map'.

theorem LinearMap.linearIndependent_iff {ι : Type u'} {R : Type u_2} {M : Type u_4} {M' : Type u_5} {v : ιM} [Ring R] [AddCommGroup M] [AddCommGroup M'] [Module R M] [Module R M'] (f : M →ₗ[R] M') (hf_inj : ker f = ) :

If f is an injective linear map, then the family f ∘ v is linearly independent if and only if the family v is linearly independent.

theorem LinearIndependent.fin_cons' {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {m : } (x : M) (v : Fin mM) (hli : LinearIndependent R v) (x_ortho : ∀ (c : R) (y : (Submodule.span R (Set.range v))), c x + y = 0c = 0) :

See LinearIndependent.fin_cons for a family of elements in a vector space.

Properties which require Ring R #

theorem LinearIndependent.sum_type {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {M : Type u_4} {v : ιM} [Ring R] [AddCommGroup M] [Module R M] {v' : ι'M} (hv : LinearIndependent R v) (hv' : LinearIndependent R v') (h : Disjoint (Submodule.span R (Set.range v)) (Submodule.span R (Set.range v'))) :
theorem LinearIndepOn.id_union {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {s t : Set M} (hs : LinearIndepOn R id s) (ht : LinearIndepOn R id t) (hst : Disjoint (Submodule.span R s) (Submodule.span R t)) :
@[deprecated LinearIndepOn.id_union (since := "2025-02-14")]
theorem LinearIndependent.union {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {s t : Set M} (hs : LinearIndepOn R id s) (ht : LinearIndepOn R id t) (hst : Disjoint (Submodule.span R s) (Submodule.span R t)) :

Alias of LinearIndepOn.id_union.

theorem LinearIndepOn.image {R : Type u_2} {M : Type u_4} {M' : Type u_5} [Ring R] [AddCommGroup M] [AddCommGroup M'] [Module R M] [Module R M'] {s : Set M} {f : M →ₗ[R] M'} (hs : LinearIndepOn R id s) (hf_inj : Disjoint (Submodule.span R s) (LinearMap.ker f)) :
LinearIndepOn R id (f '' s)
@[deprecated LinearIndepOn.image (since := "2025-02-15")]
theorem LinearIndependent.image_subtype {R : Type u_2} {M : Type u_4} {M' : Type u_5} [Ring R] [AddCommGroup M] [AddCommGroup M'] [Module R M] [Module R M'] {s : Set M} {f : M →ₗ[R] M'} (hs : LinearIndepOn R id s) (hf_inj : Disjoint (Submodule.span R s) (LinearMap.ker f)) :
LinearIndepOn R id (f '' s)

Alias of LinearIndepOn.image.

theorem linearIndependent_monoidHom (G : Type u_6) [Monoid G] (L : Type u_7) [CommRing L] [NoZeroDivisors L] :
LinearIndependent L fun (f : G →* L) => f

Dedekind's linear independence of characters

Stacks Tag 0CKL

theorem linearIndependent_unique_iff {ι : Type u'} {R : Type u_2} {M : Type u_4} [Ring R] [Nontrivial R] [AddCommGroup M] [Module R M] [NoZeroSMulDivisors R M] (v : ιM) [Unique ι] :
theorem linearIndependent_unique {ι : Type u'} {R : Type u_2} {M : Type u_4} [Ring R] [Nontrivial R] [AddCommGroup M] [Module R M] [NoZeroSMulDivisors R M] (v : ιM) [Unique ι] :

Alias of the reverse direction of linearIndependent_unique_iff.

theorem LinearIndepOn.singleton {ι : Type u'} {R : Type u_2} {M : Type u_4} [Ring R] [Nontrivial R] [AddCommGroup M] [Module R M] [NoZeroSMulDivisors R M] {v : ιM} {i : ι} (hi : v i 0) :
theorem LinearIndepOn.id_singleton (R : Type u_2) {M : Type u_4} [Ring R] [Nontrivial R] [AddCommGroup M] [Module R M] [NoZeroSMulDivisors R M] {x : M} (hx : x 0) :
@[deprecated LinearIndepOn.id_singleton (since := "2025-02-15")]
theorem linearIndependent_singleton (R : Type u_2) {M : Type u_4} [Ring R] [Nontrivial R] [AddCommGroup M] [Module R M] [NoZeroSMulDivisors R M] {x : M} (hx : x 0) :

Alias of LinearIndepOn.id_singleton.

@[simp]
theorem linearIndependent_subsingleton_index_iff {ι : Type u'} {R : Type u_2} {M : Type u_4} [Ring R] [Nontrivial R] [AddCommGroup M] [Module R M] [NoZeroSMulDivisors R M] [Subsingleton ι] (f : ιM) :
LinearIndependent R f ∀ (i : ι), f i 0
@[simp]
theorem linearIndependent_subsingleton_iff {ι : Type u'} {R : Type u_2} {M : Type u_4} [Ring R] [Nontrivial R] [AddCommGroup M] [Module R M] [NoZeroSMulDivisors R M] [Subsingleton M] (f : ιM) :