is called a field if the following holds ∀x,y,z∈E:
K1E together with the addition + is an abelian group.
(Its neutral element is denoted by 0, the inverse element of a∈E by −a; cf. Discrete Mathematics, 5. Algebra, Definitions 5.7 and 5.8: ⟨E;+⟩ is an abelian group):
(i) (associativity) (x+y)+z=x+(y+z)
(ii) (neutral element) ∃e∈E:x+e=e+x=x
(iii) (inverse element) ∃x′∈E:x+x′=x′+x=e
(iv) (abelian ⇔ commutativity) x+y=y+x
K2 Writing E∗:=E∖{0}, for x,y∈E∗ we also have x⋅y∈E∗, and E∗ together with the multiplication obtained this way is an abelian group.
(Its neutral element is denoted by 1, the inverse element of x∈E∗ by x−1 or 1/x. One writes y/x=x−1y=yx−1.
Cf. Discrete Mathematics, 5. Algebra, Definitions 5.7 and 5.8: ⟨E;⋅⟩ is an abelian group)
(cf. Discrete Mathematics, 5. Algebra: Definition 5.26 and Theorem 5.23)
Remark
Most of the time we will work with the fields R or C. Another field that we computer scientists know well is the smallest finite field Z2, which contains only {0,1}.
Definition
A vector spaceV over E (or E-vector space; VS) is a non-empty set V together with two operations:
V1V together with the addition is an abelian (commutative) group (the neutral element is called the zero vector and is denoted by 0, and the negative is denoted by −x; cf. Discrete Mathematics, 5. Algebra: ⟨V;+⟩ is an abelian group):
(i) (associativity) (x+y)+z=x+(y+z)
(ii) (neutral element) ∃e∈V:x+e=e+x=x
(iii) (inverse element) ∃x′∈V:x+x′=x′+x=e
(iv) (abelian ⇔ commutativity) x+y=y+x
V2 Multiplication by scalars must be compatible with the other operations as follows:
(i) (distributivity I) (α+β)x=αx+βx
(ii) (distributivity II) α(x+y)=αx+αy
(iii) (associativity) (αβ)x=α(βx)
(iv) (compatibility with 1) 1x=x
Example 1
n-dimensional vectors form a vector space over E.
m×n matrices form a vector space over E.
Pn:={polynomials in one variable with coefficients in E of degree at most n} form a vector space over E.
Definition
Let V be a vector space, U⊆V,U={}. U is called a subspace (vector subspace, linear subspace) if it is closed under addition and scalar multiplication, i.e. if ∀x,y∈U and ∀α∈E:
U1x+y∈U
U2αx∈U.
Remark
Every subspace U contains the zero vector, i.e.
U00∈U.
Satz
Every subspace is a vector space.
Example 2
To show:W=⎩⎨⎧x1x2x3∈R3x1+x2+x3=0⎭⎬⎫ is a vector space.
Remark
We have two options:
Check whether V1 and V2 of the vector space definition are satisfied
Use the theorem above and only show U1 and U2
Show solutionHide solution
Proof:
We carry out the proof using the second option.
By the theorem it therefore suffices to show that W is a subspace.
Let x=x1x2x3,y=y1y2y3∈W,λ∈E
U0000∈W, since 0+0+0=0, (U0 follows trivially)
U1x+y=x1+y1x2+y2x3+y3∈W,
since (x1+y1)+(x2+y2)+(x3+y3)=x1+x2+x3=0(x1+x2+x3)+y1+y2+y3=0(y1+y2+y3)=0
U2λx=λx1λx2λx3∈W, since λx1+λx2+λx3=λx1+x2+x3=0(x1+x2+x3)=0
Instead of showing U1 and U2 separately, you can also show the "all in one" variant:
U1/U2x−λy=x1−λy1x2−λy2x3−λy3∈W,
since (x1−λy1)+(x2−λy2)+(x3−λy3)=x1+x2+x3=0(x1+x2+x3)−λy1+y2+y3=0(y1+y2+y3)=0□
Bases, Dimensions and Linear (In)dependence
Remark
For this section we assume the following. Let V be a vector space over a field E and (vi)i∈I a family (set) of vectors vi∈V. If I={1,...,r}, you have vectors v1,...,vr.
Definition
Let v1,...,vr∈V be chosen vectors. A vector of the form
x:=λ1v1+...+λrvr=k=1∑rλkvk
with λ1,...,λr∈E is called a linear combination of v1,...,vr.
Definition
For general I one defines
spanE(vi)i∈I
as the set of all v∈V that can be written as a linear combination of a finite subfamily (subset) of (vi)i∈I (depending on v). spanE(vi)i∈I is called the space spanned (or generated) by the family (set). For a finite family (v1,...,vr) one often uses the more suggestive notation:
spanE(v1,...,vr):=Ev1+...+Evn={v∈V∣∃λ1,...,λr∈E with v=λ1v1+...+λrvr}.
Remark
The following notations are equivalent:
spanE(v1,...,vr)⇔spanE{v1,...,vr}⇔⟨v1,...,vr⟩.
Definition
A family B=(vi)i∈I in a vector space V is called a spanning set of V if
V=span(vi)i∈I,
i.e. if every v∈V is a linear combination of finitely many vi.
Remark
If it is clear which field is meant, one writes just span instead of spanE.
Remark
Let V be an E-vector space and (vi)i∈I a family (set) of elements of V with I={1,...,r}. Then:
span(v1,...,vr) is a subspace
If W⊂V is a subspace and vi∈W for all i∈{1,...,r}, then span(v1,...,vr)⊂W.
Example 3
span(1,x,x2,x3)=P3
span(x3+x2,x2−1,x,x−1,1000)=P3
⇒ a spanning set is not unique.
Definition
v1,...,vr∈V are called linearly independent if:
k=1∑rλkvk=λ1v1+...+λrvr=0⇒λ1=...=λr=0
and otherwise they are called linearly dependent.
Remark
v1,...,vr∈V are linearly independent if and only if no vi can be written as a linear combination of the other vj with j=i. (E.g. v1 cannot be written as a linear combination of v2,...,vr).
Example 4
123 is linearly dependent on 246, because 2⋅123=246.
123 is linearly independent of 023.
With componentwise multiplication you never get 0 in the first coordinate if you want to keep 2 and 3.
Definition
Let B=(bi)i∈I⊆V. B is called a basis of V if
VB=span(B)(V is spanned by B)=(bi)i∈I (all bi are mutually linearly independent).
Satz
B is a minimal spanning set, i.e.
span(B)=V, but span(B∖{bi})=V,∀bi∈B.
Satz
B is a maximal linearly independent subset of V, i.e. (bi)i∈I are linearly independent but (bi)i∈I∪{v} are no longer linearly independent, ∀v∈V∖B.
Remark
If B1 and B2 are bases of V, then ∣B1∣=∣B2∣. Every vector space has a basis.
Definition
Let B be a basis of V. Then ∣B∣=dim(V)(=# basis vectors) is the dimension of V, where ∣⋅∣=^ the cardinality of a set.
Remark
If dim(V)=n, then in general:
If k<n, v1,...,vk∈V are not spanning
If k>n, v1,...,vk∈V are spanning and linearly dependent
Satzbasis selection theorem
From every finite spanning set of a vector space you can select a basis. In particular, every finitely generated vector space has a finite basis.
Satzbasis extension theorem
In a finitely generated vector space V, let linearly independent vectors w1,...,wn be given. Then you can find wn+1,...,wr such that
dimR(C)=2 (a basis of C over the field R is e.g. {1,i})
dimC(C)=1 (a basis of C over the field C is e.g. {1})
Definition
In a finite-dimensional vector space V with an inner product, the complementary subspace orthogonal to a proper subspace U is called the orthogonal complement of U and is denoted by U⊥. It is characterised implicitly by the relation
V=U⊕U⊥,U⊥U⊥
or explicitly by
U⊥:={x∈V∣x⊥U}.
We then call V a direct sum of orthogonal complements.
Remarkproperties
(U⊥)⊥=U
dim(U)+dim(U⊥)=dim(V).
Remarkcalculation tricks (for questions about dimension, basis, linear dependence, etc.)
⇒ rank(A)=3 full rank ⇒ the vectors are linearly independent and therefore form a basis of R3. □
Example 7
Is B={1,x,1+x2+x3} a basis of P3?
If yes, prove it; if no, extend it to a basis.
Show solutionHide solution
We know: dim(P3)=4 B cannot be a, because dim(B)=3<4.
Claim: B′={1,x,1+x2+x3,x2} is a basis of P3.
Proof:
1xx2x31+x2+x3=^e1=^e2=^e3=^e4=^e1+e3+e41010010000110010⇝⋯⇝1000010000100001⇒linearly independent, so B′ is a basis of P3□
Change of Basis, Coordinate Transformation (I)
Definition
Let A=(e1,...,en) be the canonical basis of the vector space V and B=(b1,...,bn) another basis of V, described in terms of the canonical basis. Then there exists a change-of-basis matrix with:
TAB=(b1∣⋯∣bn) with bi=TABei,i∈{1,...,n}.VATBAVB
Remark
The following calculation rule holds: TBA=(TAB)−1
With the definition above we therefore obtain: TBAbi=ei,i∈{1,...,n}.