Linear independence

This file defines linear independence in a module or vector space.

It is inspired by Isabelle/HOL's linear algebra, and hence indirectly by HOL Light.

We define LinearIndependent R v as ker (Finsupp.total ι M R v) = ⊥. Here Finsupp.total is the linear map sending a function f : ι →₀ R with finite support to the linear combination of vectors from v with these coefficients. Then we prove that several other statements are equivalent to this one, including injectivity of Finsupp.total ι M R v and some versions with explicitly written linear combinations.

Main definitions

All definitions are given for families of vectors, i.e. v : ι → M where M is the module or vector space and ι : Type* is an arbitrary indexing type.

• LinearIndependent R v states that the elements of the family v are linearly independent.

• LinearIndependent.repr hv x returns the linear combination representing x : span R (range v) on the linearly independent vectors v, given hv : LinearIndependent R v (using classical choice). LinearIndependent.repr hv is provided as a linear map.

Main statements

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

• Fintype.linearIndependent_iff: if ι is a finite type, then any function f : ι → R has finite support, so we can reformulate the statement using ∑ i : ι, f i • v i instead of a sum over an auxiliary s : Finset ι;
• linearIndependent_empty_type: a family indexed by an empty type is linearly independent;
• linearIndependent_unique_iff: if ι is a singleton, then LinearIndependent K v is equivalent to v default ≠ 0;
• linearIndependent_option, linearIndependent_sum, linearIndependent_fin_cons, linearIndependent_fin_succ: type-specific tests for linear independence of families of vector fields;
• linearIndependent_insert, linearIndependent_union, linearIndependent_pair, linearIndependent_singleton: linear independence tests for set operations.

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.

We also prove that, when working over a division ring, any family of vectors includes a linear independent subfamily spanning the same subspace.

Implementation notes

We use families instead of sets because it allows us to say that two identical vectors are linearly dependent.

If you want to use sets, use the family (fun x ↦ x : s → M) given a set s : Set M. The lemmas LinearIndependent.to_subtype_range and LinearIndependent.of_subtype_range connect those two worlds.

Tags

linearly dependent, linear dependence, linearly independent, linear independence

def LinearIndependent {ι : Type u'} (R : Type u_2) {M : Type u_4} (v : ι → M) [Semiring R] [AddCommMonoid M] [Module R M] : Prop

LinearIndependent R v states the family of vectors v is linearly independent over R.

Equations

• LinearIndependent R v = (LinearMap.ker (Finsupp.total ι M R v) = ⊥)

theorem linearIndependent_iff {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] : LinearIndependent R v ↔ ∀ (l : ι →₀ R), ↑(Finsupp.total ι M R v) l = 0 → l = 0

theorem linearIndependent_iff' {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] : LinearIndependent R v ↔ ∀ (s : Finset ι) (g : ι → R), (Finset.sum s fun i => g i • v i) = 0 → ∀ (i : ι), i ∈ s → g i = 0

theorem linearIndependent_iff'' {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] : LinearIndependent R v ↔ ∀ (s : Finset ι) (g : ι → R), (∀ (i : ι), ¬i ∈ s → g i = 0) → (Finset.sum s fun i => g i • v i) = 0 → ∀ (i : ι), g i = 0

theorem not_linearIndependent_iff {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] : ¬LinearIndependent R v ↔ ∃ s g, (Finset.sum s fun i => g i • v i) = 0 ∧ ∃ i, i ∈ s ∧ g i ≠ 0

theorem Fintype.linearIndependent_iff {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] [Fintype ι] : LinearIndependent R v ↔ ∀ (g : ι → R), (Finset.sum Finset.univ fun i => g i • v i) = 0 → ∀ (i : ι), g i = 0

theorem Fintype.linearIndependent_iff' {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] [Fintype ι] [DecidableEq ι] : LinearIndependent R v ↔ LinearMap.ker (↑(LinearMap.lsum R (fun x => R) ℕ) fun i => LinearMap.smulRight LinearMap.id (v i)) = ⊥

A finite family of vectors v i is linear independent iff the linear map that sends c : ι → R to ∑ i, c i • v i has the trivial kernel.

theorem Fintype.not_linearIndependent_iff {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] [Fintype ι] : ¬LinearIndependent R v ↔ ∃ g, (Finset.sum Finset.univ fun i => g i • v i) = 0 ∧ ∃ i, g i ≠ 0

theorem linearIndependent_empty_type {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] [IsEmpty ι] : LinearIndependent R v

theorem LinearIndependent.ne_zero {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] [Nontrivial R] (i : ι) (hv : LinearIndependent R v) : v i ≠ 0

theorem LinearIndependent.eq_zero_of_pair {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {x : M} {y : M} (h : LinearIndependent R ![x, y]) {s : R} {t : R} (h' : s • x + t • y = 0) : s = 0 ∧ t = 0

theorem LinearIndependent.pair_iff {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {x : M} {y : M} : LinearIndependent R ![x, y] ↔ ∀ (s t : R), s • x + t • y = 0 → s = 0 ∧ t = 0

theorem LinearIndependent.comp {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] (h : LinearIndependent R v) (f : ι' → ι) (hf : Function.Injective f) : LinearIndependent R (v ∘ f)

A subfamily of a linearly independent family (i.e., a composition with an injective map) is a linearly independent family.

theorem LinearIndependent.coe_range {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] (i : LinearIndependent R v) : LinearIndependent R Subtype.val

theorem LinearIndependent.map {ι : 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 : Disjoint (Submodule.span R (Set.range v)) (LinearMap.ker f)) : LinearIndependent R (↑f ∘ v)

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 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)) : Disjoint (Submodule.span R (Set.range v)) (LinearMap.ker f)

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

theorem LinearIndependent.map' {ι : 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 : LinearMap.ker f = ⊥) : LinearIndependent R (↑f ∘ v)

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.of_comp {ι : 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') (hfv : LinearIndependent R (↑f ∘ v)) : LinearIndependent R v

If the image of a family of vectors under a linear map is linearly independent, then so is the original family.

theorem LinearMap.linearIndependent_iff {ι : 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') (hf_inj : LinearMap.ker f = ⊥) : LinearIndependent R (↑f ∘ v) ↔ LinearIndependent R v

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_of_subsingleton {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] [Subsingleton R] : LinearIndependent R v

theorem linearIndependent_equiv {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] (e : ι ≃ ι') {f : ι' → M} : LinearIndependent R (f ∘ ↑e) ↔ LinearIndependent R f

theorem linearIndependent_equiv' {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] (e : ι ≃ ι') {f : ι' → M} {g : ι → M} (h : f ∘ ↑e = g) : LinearIndependent R g ↔ LinearIndependent R f

theorem linearIndependent_subtype_range {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {ι : Type u_8} {f : ι → M} (hf : Function.Injective f) : LinearIndependent R Subtype.val ↔ LinearIndependent R f

theorem LinearIndependent.of_subtype_range {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {ι : Type u_8} {f : ι → M} (hf : Function.Injective f) : LinearIndependent R Subtype.val → LinearIndependent R f

Alias of the forward direction of linearIndependent_subtype_range.

theorem linearIndependent_image {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {ι : Type u_8} {s : Set ι} {f : ι → M} (hf : Set.InjOn f s) : (LinearIndependent R fun x => f ↑x) ↔ LinearIndependent R fun x => ↑x

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 => { val := v i, property := (_ : v i ∈ ↑(Submodule.span R (Set.range v))) }

theorem LinearIndependent.fin_cons' {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {m : ℕ} (x : M) (v : Fin m → M) (hli : LinearIndependent R v) (x_ortho : ∀ (c : R) (y : { x // x ∈ Submodule.span R (Set.range v) }), c • x + ↑y = 0 → c = 0) : LinearIndependent R (Fin.cons x v)

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

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 • 1) (li : LinearIndependent K v) : LinearIndependent R 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. The implementation uses minimal assumptions about the relationship between R, K and M. The version where K is an R-algebra is LinearIndependent.restrict_scalars_algebras.

theorem linearIndependent_finset_map_embedding_subtype {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] (s : Set M) (li : LinearIndependent R Subtype.val) (t : Finset ↑s) : LinearIndependent R Subtype.val

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

theorem linearIndependent_bounded_of_finset_linearIndependent_bounded {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {n : ℕ} (H : ∀ (s : Finset M), (LinearIndependent R fun i => ↑i) → Finset.card s ≤ n) (s : Set M) : LinearIndependent R Subtype.val → Cardinal.mk ↑s ≤ ↑n

If every finite set of linearly independent vectors has cardinality at most n, then the same is true for arbitrary sets of linearly independent vectors.

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

theorem linearIndependent_comp_subtype {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set ι} : LinearIndependent R (v ∘ Subtype.val) ↔ ∀ (l : ι →₀ R), l ∈ Finsupp.supported R R s → ↑(Finsupp.total ι M R v) l = 0 → l = 0

theorem linearDependent_comp_subtype' {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set ι} : ¬LinearIndependent R (v ∘ Subtype.val) ↔ ∃ f, f ∈ Finsupp.supported R R s ∧ ↑(Finsupp.total ι M R v) f = 0 ∧ f ≠ 0

theorem linearDependent_comp_subtype {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set ι} : ¬LinearIndependent R (v ∘ Subtype.val) ↔ ∃ f, f ∈ Finsupp.supported R R s ∧ (Finset.sum f.support fun i => ↑f i • v i) = 0 ∧ f ≠ 0

A version of linearDependent_comp_subtype' with Finsupp.total unfolded.

theorem linearIndependent_subtype {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set M} : (LinearIndependent R fun x => ↑x) ↔ ∀ (l : M →₀ R), l ∈ Finsupp.supported R R s → ↑(Finsupp.total M M R id) l = 0 → l = 0

theorem linearIndependent_comp_subtype_disjoint {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set ι} : LinearIndependent R (v ∘ Subtype.val) ↔ Disjoint (Finsupp.supported R R s) (LinearMap.ker (Finsupp.total ι M R v))

theorem linearIndependent_subtype_disjoint {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set M} : (LinearIndependent R fun x => ↑x) ↔ Disjoint (Finsupp.supported R R s) (LinearMap.ker (Finsupp.total M M R id))

theorem linearIndependent_iff_totalOn {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set M} : (LinearIndependent R fun x => ↑x) ↔ LinearMap.ker (Finsupp.totalOn M M R id s) = ⊥

theorem LinearIndependent.restrict_of_comp_subtype {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set ι} (hs : LinearIndependent R (v ∘ Subtype.val)) : LinearIndependent R (Set.restrict s v)

theorem linearIndependent_empty (R : Type u_2) (M : Type u_4) [Semiring R] [AddCommMonoid M] [Module R M] : LinearIndependent R fun x => ↑x

theorem LinearIndependent.mono {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {t : Set M} {s : Set M} (h : t ⊆ s) : (LinearIndependent R fun x => ↑x) → LinearIndependent R fun x => ↑x

theorem linearIndependent_of_finite {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] (s : Set M) (H : ∀ (t : Set M), t ⊆ s → Set.Finite t → LinearIndependent R fun x => ↑x) : LinearIndependent R fun x => ↑x

theorem linearIndependent_iUnion_of_directed {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {η : Type u_8} {s : η → Set M} (hs : Directed (fun x x_1 => x ⊆ x_1) s) (h : ∀ (i : η), LinearIndependent R fun x => ↑x) : LinearIndependent R fun x => ↑x

theorem linearIndependent_sUnion_of_directed {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {s : Set (Set M)} (hs : DirectedOn (fun x x_1 => x ⊆ x_1) s) (h : ∀ (a : Set M), a ∈ s → LinearIndependent R Subtype.val) : LinearIndependent R fun x => ↑x

theorem linearIndependent_biUnion_of_directed {R : Type u_2} {M : Type u_4} [Semiring R] [AddCommMonoid M] [Module R M] {η : Type u_8} {s : Set η} {t : η → Set M} (hs : DirectedOn (t ⁻¹'o fun x x_1 => x ⊆ x_1) s) (h : ∀ (a : η), a ∈ s → LinearIndependent R fun x => ↑x) : LinearIndependent R fun x => ↑x

Properties which require Ring R

theorem linearIndependent_iff_injective_total {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] : LinearIndependent R v ↔ Function.Injective ↑(Finsupp.total ι M R v)

theorem LinearIndependent.injective_total {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] : LinearIndependent R v → Function.Injective ↑(Finsupp.total ι M R v)

Alias of the forward direction of linearIndependent_iff_injective_total.

theorem LinearIndependent.injective {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] [Nontrivial R] (hv : LinearIndependent R v) : Function.Injective v

theorem LinearIndependent.to_subtype_range {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {ι : Type u_8} {f : ι → M} (hf : LinearIndependent R f) : LinearIndependent R Subtype.val

theorem LinearIndependent.to_subtype_range' {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {ι : Type u_8} {f : ι → M} (hf : LinearIndependent R f) {t : Set M} (ht : Set.range f = t) : LinearIndependent R Subtype.val

theorem LinearIndependent.image_of_comp {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {ι : Type u_8} {ι' : Type u_9} (s : Set ι) (f : ι → ι') (g : ι' → M) (hs : LinearIndependent R fun x => g (f ↑x)) : LinearIndependent R fun x => g ↑x

theorem LinearIndependent.image {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {ι : Type u_8} {s : Set ι} {f : ι → M} (hs : LinearIndependent R fun x => f ↑x) : LinearIndependent R fun x => ↑x

theorem LinearIndependent.group_smul {ι : Type u'} {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {G : Type u_8} [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) : LinearIndependent R (w • v)

theorem LinearIndependent.units_smul {ι : Type u'} {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {v : ι → M} (hv : LinearIndependent R v) (w : ι → Rˣ) : LinearIndependent R (w • v)

theorem LinearIndependent.eq_of_pair {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {x : M} {y : M} (h : LinearIndependent R ![x, y]) {s : R} {t : R} {s' : R} {t' : R} (h' : s • x + t • y = s' • x + t' • y) : s = s' ∧ t = t'

theorem LinearIndependent.eq_zero_of_pair' {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {x : M} {y : M} (h : LinearIndependent R ![x, y]) {s : R} {t : R} (h' : s • x = t • y) : s = 0 ∧ t = 0

theorem LinearIndependent.linear_combination_pair_of_det_ne_zero {R : Type u_8} {M : Type u_9} [CommRing R] [NoZeroDivisors R] [AddCommGroup M] [Module R M] {x : M} {y : M} (h : LinearIndependent R ![x, y]) {a : R} {b : R} {c : R} {d : R} (h' : a * d - b * c ≠ 0) : LinearIndependent R ![a • x + b • y, c • x + d • y]

If two vectors x and y are linearly independent, so are their linear combinations a x + b y and c x + d y provided the determinant a * d - b * c is nonzero.

def LinearIndependent.Maximal {ι : Type w} {R : Type u} [Semiring R] {M : Type v} [AddCommMonoid M] [Module R M] {v : ι → M} (_i : LinearIndependent R v) : Prop

A linearly independent family is maximal if there is no strictly larger linearly independent family.

Equations

• LinearIndependent.Maximal _i = ∀ (s : Set M), LinearIndependent R Subtype.val → Set.range v ≤ s → Set.range v = s

theorem LinearIndependent.maximal_iff {ι : Type w} {R : Type u} [Ring R] [Nontrivial R] {M : Type v} [AddCommGroup M] [Module R M] {v : ι → M} (i : LinearIndependent R v) : LinearIndependent.Maximal i ↔ ∀ (κ : Type v) (w : κ → M), LinearIndependent R w → ∀ (j : ι → κ), w ∘ j = v → Function.Surjective j

An alternative characterization of a maximal linearly independent family, quantifying over types (in the same universe as M) into which the indexing family injects.

theorem LinearIndependent.eq_of_smul_apply_eq_smul_apply {ι : Type u'} {R : Type u_2} [Ring R] {M : Type u_8} [AddCommGroup M] [Module R M] {v : ι → M} (li : LinearIndependent R v) (c : R) (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} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) {s : Set ι} {t : Set ι} (hs : Disjoint s t) : Disjoint (Submodule.span R (v '' s)) (Submodule.span R (v '' t))

theorem LinearIndependent.not_mem_span_image {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] [Nontrivial R] (hv : LinearIndependent R v) {s : Set ι} {x : ι} (h : ¬x ∈ s) : ¬v x ∈ Submodule.span R (v '' s)

theorem LinearIndependent.total_ne_of_not_mem_support {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] [Nontrivial R] (hv : LinearIndependent R v) {x : ι} (f : ι →₀ R) (h : ¬x ∈ f.support) : ↑(Finsupp.total ι M R v) f ≠ v x

theorem linearIndependent_sum {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {v : ι ⊕ ι' → M} : LinearIndependent R v ↔ LinearIndependent R (v ∘ Sum.inl) ∧ LinearIndependent R (v ∘ Sum.inr) ∧ Disjoint (Submodule.span R (Set.range (v ∘ Sum.inl))) (Submodule.span R (Set.range (v ∘ Sum.inr)))

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'))) : LinearIndependent R (Sum.elim v v')

theorem LinearIndependent.union {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {s : Set M} {t : Set M} (hs : LinearIndependent R fun x => ↑x) (ht : LinearIndependent R fun x => ↑x) (hst : Disjoint (Submodule.span R s) (Submodule.span R t)) : LinearIndependent R fun x => ↑x

theorem linearIndependent_iUnion_finite_subtype {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {ι : Type u_8} {f : ι → Set M} (hl : ∀ (i : ι), LinearIndependent R fun x => ↑x) (hd : ∀ (i : ι) (t : Set ι), Set.Finite t → ¬i ∈ t → Disjoint (Submodule.span R (f i)) (⨆ (i : ι) (_ : i ∈ t), Submodule.span R (f i))) : LinearIndependent R fun x => ↑x

theorem linearIndependent_iUnion_finite {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] {η : Type u_8} {ιs : η → Type u_9} {f : (j : η) → ιs j → M} (hindep : ∀ (j : η), LinearIndependent R (f j)) (hd : ∀ (i : η) (t : Set η), Set.Finite t → ¬i ∈ t → Disjoint (Submodule.span R (Set.range (f i))) (⨆ (i : η) (_ : i ∈ t), Submodule.span R (Set.range (f i)))) : LinearIndependent R fun ji => f ji.fst ji.snd

@[simp]

theorem LinearIndependent.totalEquiv_symm_apply {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) : ∀ (a : { x // x ∈ Submodule.span R (Set.range v) }), ↑(LinearEquiv.symm (LinearIndependent.totalEquiv hv)) a = Equiv.invFun ((LinearEquiv.toEquiv (LinearEquiv.ofInjective (LinearMap.codRestrict (Submodule.span R (Set.range v)) (Finsupp.total ι M R v) (_ : ∀ (l : ι →₀ R), ↑(Finsupp.total ι M R v) l ∈ Submodule.span R (Set.range v))) (_ : Function.Injective ↑(LinearMap.codRestrict (Submodule.span R (Set.range v)) (Finsupp.total ι M R v) (_ : ∀ (l : ι →₀ R), ↑(Finsupp.total ι M R v) l ∈ Submodule.span R (Set.range v)))))).trans (LinearEquiv.toEquiv (LinearEquiv.ofTop (LinearMap.range (LinearMap.codRestrict (Submodule.span R (Set.range v)) (Finsupp.total ι M R v) (_ : ∀ (l : ι →₀ R), ↑(Finsupp.total ι M R v) l ∈ Submodule.span R (Set.range v)))) (_ : LinearMap.range (LinearMap.codRestrict (Submodule.span R (Set.range v)) (Finsupp.total ι M R v) (_ : ∀ (l : ι →₀ R), ↑(Finsupp.total ι M R v) l ∈ Submodule.span R (Set.range v))) = ⊤)))) a

def LinearIndependent.totalEquiv {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) : (ι →₀ R) ≃ₗ[R] { x // x ∈ Submodule.span R (Set.range v) }

Canonical isomorphism between linear combinations and the span of linearly independent vectors.

Equations

• One or more equations did not get rendered due to their size.

@[simp]

theorem LinearIndependent.totalEquiv_apply_coe {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) (l : ι →₀ R) : ↑(↑(LinearIndependent.totalEquiv hv) l) = ↑(Finsupp.total ι M R v) l

def LinearIndependent.repr {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) : { x // x ∈ Submodule.span R (Set.range v) } →ₗ[R] ι →₀ R

Linear combination representing a vector in the span of linearly independent vectors.

Given a family of linearly independent vectors, we can represent any vector in their span as a linear combination of these vectors. These are provided by this linear map. It is simply one direction of LinearIndependent.total_equiv.

Equations

• LinearIndependent.repr hv = ↑(LinearEquiv.symm (LinearIndependent.totalEquiv hv))

@[simp]

theorem LinearIndependent.total_repr {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) (x : { x // x ∈ Submodule.span R (Set.range v) }) : ↑(Finsupp.total ι M R v) (↑(LinearIndependent.repr hv) x) = ↑x

theorem LinearIndependent.total_comp_repr {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) : LinearMap.comp (Finsupp.total ι M R v) (LinearIndependent.repr hv) = Submodule.subtype (Submodule.span R (Set.range v))

theorem LinearIndependent.repr_ker {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) : LinearMap.ker (LinearIndependent.repr hv) = ⊥

theorem LinearIndependent.repr_range {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) : LinearMap.range (LinearIndependent.repr hv) = ⊤

theorem LinearIndependent.repr_eq {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) {l : ι →₀ R} {x : { x // x ∈ Submodule.span R (Set.range v) }} (eq : ↑(Finsupp.total ι M R v) l = ↑x) : ↑(LinearIndependent.repr hv) x = l

theorem LinearIndependent.repr_eq_single {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) (i : ι) (x : { x // x ∈ Submodule.span R (Set.range v) }) (hx : ↑x = v i) : ↑(LinearIndependent.repr hv) x = fun₀ | i => 1

theorem LinearIndependent.span_repr_eq {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) [Nontrivial R] (x : { x // x ∈ Submodule.span R (Set.range v) }) : Span.repr R (Set.range v) x = Finsupp.equivMapDomain (Equiv.ofInjective v (_ : Function.Injective v)) (↑(LinearIndependent.repr hv) x)

theorem linearIndependent_iff_not_smul_mem_span {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] : LinearIndependent R v ↔ ∀ (i : ι) (a : R), a • v i ∈ Submodule.span R (v '' (Set.univ \ {i})) → a = 0

theorem LinearIndependent.independent_span_singleton {ι : Type u'} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] (hv : LinearIndependent R v) : CompleteLattice.Independent fun i => Submodule.span R {v i}

See also CompleteLattice.independent_iff_linearIndependent_of_ne_zero.

theorem exists_maximal_independent' {ι : Type u'} (R : Type u_2) {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] (s : ι → M) : ∃ I, (LinearIndependent R fun x => s ↑x) ∧ ∀ (J : Set ι), I ⊆ J → (LinearIndependent R fun x => s ↑x) → I = J

theorem exists_maximal_independent {ι : Type u'} (R : Type u_2) {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] (s : ι → M) : ∃ I, (LinearIndependent R fun x => s ↑x) ∧ ∀ (i : ι), ¬i ∈ I → ∃ a, a ≠ 0 ∧ a • s i ∈ Submodule.span R (s '' I)

theorem surjective_of_linearIndependent_of_span {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {M : Type u_4} {v : ι → M} [Ring R] [AddCommGroup M] [Module R M] [Nontrivial R] (hv : LinearIndependent R v) (f : ι' ↪ ι) (hss : Set.range v ⊆ ↑(Submodule.span R (Set.range (v ∘ ↑f)))) : Function.Surjective ↑f

theorem eq_of_linearIndependent_of_span_subtype {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] [Nontrivial R] {s : Set M} {t : Set M} (hs : LinearIndependent R fun x => ↑x) (h : t ⊆ s) (hst : s ⊆ ↑(Submodule.span R t)) : s = t

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 : LinearIndependent R fun x => ↑x) (hf_inj : Disjoint (Submodule.span R s) (LinearMap.ker f)) : LinearIndependent R fun x => ↑x

theorem LinearIndependent.inl_union_inr {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} {t : Set M'} (hs : LinearIndependent R fun x => ↑x) (ht : LinearIndependent R fun x => ↑x) : LinearIndependent R fun x => ↑x

theorem linearIndependent_inl_union_inr' {ι : Type u'} {ι' : Type u_1} {R : Type u_2} {M : Type u_4} {M' : Type u_5} [Ring R] [AddCommGroup M] [AddCommGroup M'] [Module R M] [Module R M'] {v : ι → M} {v' : ι' → M'} (hv : LinearIndependent R v) (hv' : LinearIndependent R v') : LinearIndependent R (Sum.elim (↑(LinearMap.inl R M M') ∘ v) (↑(LinearMap.inr R M M') ∘ v'))

theorem linearIndependent_monoidHom (G : Type u_8) [Monoid G] (L : Type u_9) [CommRing L] [NoZeroDivisors L] : LinearIndependent L fun f => ↑f

Dedekind's linear independence of characters

theorem le_of_span_le_span {R : Type u_2} {M : Type u_4} [Ring R] [AddCommGroup M] [Module R M] [Nontrivial R] {s : Set M} {t : Set M} {u : Set M} (hl : LinearIndependent R Subtype.val) (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} [Ring R] [AddCommGroup M] [Module R M] [Nontrivial R] {s : Set M} {t : Set M} {u : Set M} (hl : LinearIndependent R Subtype.val) (hsu : s ⊆ u) (htu : t ⊆ u) : Submodule.span R s ≤ Submodule.span R t ↔ s ⊆ t

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 ι] : LinearIndependent R v ↔ v default ≠ 0

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 ι] : v default ≠ 0 → LinearIndependent R v

Alias of the reverse direction of linearIndependent_unique_iff.

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) : LinearIndependent R fun x => ↑x

Properties which require DivisionRing K

These can be considered generalizations of properties of linear independence in vector spaces.

theorem mem_span_insert_exchange {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {x : V} {y : V} : x ∈ Submodule.span K (insert y s) → ¬x ∈ Submodule.span K s → y ∈ Submodule.span K (insert x s)

theorem linearIndependent_iff_not_mem_span {ι : Type u'} {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {v : ι → V} : LinearIndependent K v ↔ ∀ (i : ι), ¬v i ∈ Submodule.span K (v '' (Set.univ \ {i}))

theorem LinearIndependent.insert {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {x : V} (hs : LinearIndependent K fun b => ↑b) (hx : ¬x ∈ Submodule.span K s) : LinearIndependent K fun b => ↑b

theorem linearIndependent_option' {ι : Type u'} {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {v : ι → V} {x : V} : (LinearIndependent K fun o => Option.casesOn' o x v) ↔ LinearIndependent K v ∧ ¬x ∈ Submodule.span K (Set.range v)

theorem LinearIndependent.option {ι : Type u'} {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {v : ι → V} {x : V} (hv : LinearIndependent K v) (hx : ¬x ∈ Submodule.span K (Set.range v)) : LinearIndependent K fun o => Option.casesOn' o x v

theorem linearIndependent_option {ι : Type u'} {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {v : Option ι → V} : LinearIndependent K v ↔ LinearIndependent K (v ∘ some) ∧ ¬v none ∈ Submodule.span K (Set.range (v ∘ some))

theorem linearIndependent_insert' {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {ι : Type u_8} {s : Set ι} {a : ι} {f : ι → V} (has : ¬a ∈ s) : (LinearIndependent K fun x => f ↑x) ↔ (LinearIndependent K fun x => f ↑x) ∧ ¬f a ∈ Submodule.span K (f '' s)

theorem linearIndependent_insert {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {x : V} (hxs : ¬x ∈ s) : (LinearIndependent K fun b => ↑b) ↔ (LinearIndependent K fun b => ↑b) ∧ ¬x ∈ Submodule.span K s

theorem linearIndependent_pair {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {x : V} {y : V} (hx : x ≠ 0) (hy : ∀ (a : K), a • x ≠ y) : LinearIndependent K Subtype.val

theorem linearIndependent_fin_cons {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {x : V} {n : ℕ} {v : Fin n → V} : LinearIndependent K (Fin.cons x v) ↔ LinearIndependent K v ∧ ¬x ∈ Submodule.span K (Set.range v)

theorem linearIndependent_fin_snoc {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {x : V} {n : ℕ} {v : Fin n → V} : LinearIndependent K (Fin.snoc v x) ↔ LinearIndependent K v ∧ ¬x ∈ Submodule.span K (Set.range v)

theorem LinearIndependent.fin_cons {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {x : V} {n : ℕ} {v : Fin n → V} (hv : LinearIndependent K v) (hx : ¬x ∈ Submodule.span K (Set.range v)) : LinearIndependent K (Fin.cons x v)

See LinearIndependent.fin_cons' for an uglier version that works if you only have a module over a semiring.

theorem linearIndependent_fin_succ {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {n : ℕ} {v : Fin (n + 1) → V} : LinearIndependent K v ↔ LinearIndependent K (Fin.tail v) ∧ ¬v 0 ∈ Submodule.span K (Set.range (Fin.tail v))

theorem linearIndependent_fin_succ' {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {n : ℕ} {v : Fin (n + 1) → V} : LinearIndependent K v ↔ LinearIndependent K (Fin.init v) ∧ ¬v (Fin.last n) ∈ Submodule.span K (Set.range (Fin.init v))

theorem linearIndependent_fin2 {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {f : Fin 2 → V} : LinearIndependent K f ↔ f 1 ≠ 0 ∧ ∀ (a : K), a • f 1 ≠ f 0

theorem exists_linearIndependent_extension {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {t : Set V} (hs : LinearIndependent K Subtype.val) (hst : s ⊆ t) : ∃ b x, s ⊆ b ∧ t ⊆ ↑(Submodule.span K b) ∧ LinearIndependent K Subtype.val

theorem exists_linearIndependent (K : Type u_3) {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] (t : Set V) : ∃ b x, Submodule.span K b = Submodule.span K t ∧ LinearIndependent K Subtype.val

noncomputable def LinearIndependent.extend {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {t : Set V} (hs : LinearIndependent K fun x => ↑x) (hst : s ⊆ t) : Set V

LinearIndependent.extend adds vectors to a linear independent set s ⊆ t until it spans all elements of t.

Equations

• LinearIndependent.extend hs hst = Classical.choose (_ : ∃ b x, s ⊆ b ∧ t ⊆ ↑(Submodule.span K b) ∧ LinearIndependent K Subtype.val)

theorem LinearIndependent.extend_subset {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {t : Set V} (hs : LinearIndependent K fun x => ↑x) (hst : s ⊆ t) : LinearIndependent.extend hs hst ⊆ t

theorem LinearIndependent.subset_extend {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {t : Set V} (hs : LinearIndependent K fun x => ↑x) (hst : s ⊆ t) : s ⊆ LinearIndependent.extend hs hst

theorem LinearIndependent.subset_span_extend {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {t : Set V} (hs : LinearIndependent K fun x => ↑x) (hst : s ⊆ t) : t ⊆ ↑(Submodule.span K (LinearIndependent.extend hs hst))

theorem LinearIndependent.linearIndependent_extend {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {t : Set V} (hs : LinearIndependent K fun x => ↑x) (hst : s ⊆ t) : LinearIndependent K Subtype.val

theorem exists_of_linearIndependent_of_finite_span {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {t : Finset V} (hs : LinearIndependent K fun x => ↑x) (hst : s ⊆ ↑(Submodule.span K ↑t)) : ∃ t', ↑t' ⊆ s ∪ ↑t ∧ s ⊆ ↑t' ∧ Finset.card t' = Finset.card t

theorem exists_finite_card_le_of_finite_of_linearIndependent_of_span {K : Type u_3} {V : Type u} [DivisionRing K] [AddCommGroup V] [Module K V] {s : Set V} {t : Set V} (ht : Set.Finite t) (hs : LinearIndependent K fun x => ↑x) (hst : s ⊆ ↑(Submodule.span K t)) : ∃ h, Finset.card (Set.Finite.toFinset h) ≤ Finset.card (Set.Finite.toFinset ht)