nLab
linearly independent subset

Linearly independent subsets

Idea

A set of vectors is linearly dependent if one can be written as a linear combination of the others, and linearly independent otherwise. In the latter case, the vectors in the set form a basis of their span.

Definitions

Let KK be a rig, and let VV be a (left or right) module over KK. (Often KK is a field so that VV is a vector space, but this is unnecessary.) Let SS be a subset of the underlying set V{|V|} of VV.

Abstractly

By the adjunction between the underlying-set functor and the free functor, the subset inclusion

i S:SV i_S\colon S \to {|V|}

corresponds to a homomorphism

i^ S:K[S]V. \hat{i}_S\colon K[S] \to V .

Although i Si_S is (by hypothesis) a monomorphism in SetSet, i^ S\hat{i}_S need not be a monomorphism in KModK Mod.

Definition

The subset SS is linearly independent if i^ S\hat{i}_S is a monomorphism; otherwise, SS is linearly dependent.

Conversely, if we start with an (abstract!) set SS and a monomorphism from K[S]K[S] to VV, then the corresponding function from SS to V{|V|} must be a monomorphism (because the underlying-set functor is faithful). Thus, our considering only subsets of V{|V|} loses no generality.

Concretely

Given a linear combination

i=1 na iv i, \sum_{i=1}^n a_i v_i ,

this may or may not equal the zero vector? 0 V0_V. Of course, if every a ia_i is the zero scalar 0 K0_K, then the sum must be 0 V0_V.

Definition

The subset SS is linearly independent if, conversely, every a i=0 Ka_i = 0_K whenever the sum

i=1 na iv i=0 V; \sum_{i=1}^n a_i v_i = 0_V ;

otherwise, SS is linearly dependent.

Constructively

In constructive mathematics, the definitions above of linear independence are all right (and still equivalent), but the definition of linear dependence as simply the negation of linear independence is unsatisfying. Furthermore, we sometimes want something stronger than mere linear independence.

If KK is a Heyting field, then the field structure defines a tight apartness relation \ne. Even if KK is not a field, we may still suppose that it is equipped with a tight apartness, or at least some inequality relation \ne. If we restrict attention to modules with a compatible inequality relation and homomorphisms that preserve this, then we also get an inequality relation \ne on the hom-sets of the category KModK Mod. This allows us to define stronger notions of both linear dependence (which we take to be the default notion) and linear independence (to which we give a new name).

Definition

The subset SS is linearly dependent if i^ S\hat{i}_S is non-monic in the strong sense that there exist generalised elements f,g:AK[S]f, g\colon A \to K[S] such that

AgfK[S]V A \overset{f}\underset{g}\rightrightarrows K[S] \to V

are equal but fgf \ne g. Concretely, SS is linearly dependent if some linear combination

i=1 na iv i=0 V \sum_{i = 1}^n a_i v_i = 0_V

but at least one a i0 Ka_i \ne 0_K.

Definition

The subset SS is linearly free if i^ S\hat{i}_S is a regular monomorphism, or equivalently if it is monic in the strong sense that f;i^ Sg;i^ Sf ; \hat{i}_S \ne g ; \hat{i}_S whenever fgf \ne g. Concretely, SS is linearly free if

i=1 na iv i0 V \sum_{i = 1}^n a_i v_i \ne 0_V

whenever at least one a i0 Ka_i \ne 0_K.

Then we have the following implications (assuming that \ne is tight, so that a=ba = b holds iff aba \ne b fails) but not (in general) their unstated converses:

LFLI¬LD; LF \Rightarrow LI \Leftrightarrow \neg{LD} ;
¬LF¬LILD. \neg{LF} \Leftarrow \neg{LI} \Leftarrow LD .

It may also be instructive to look at the logical structure of each condition:

  • LILI: (a,v),av=0i,a i=0\forall (a,v),\; \sum a v = 0 \;\Rightarrow\; \forall i,\; a_i = 0;
  • LDLD: (a,v),av=0i,a i0\exists (a,v),\; \sum a v = 0 \;\wedge\; \exists i,\; a_i \ne 0;
  • LFLF: (a,v),av0i,a i0\forall (a,v),\; \sum a v \ne 0 \;\Leftarrow\; \exists i,\; a_i \ne 0.

Revised on February 12, 2014 13:00:39 by Urs Schreiber (82.113.121.111)