Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

r""" 

Tutorial: Using Free Modules and Vector Spaces 

 

.. MODULEAUTHOR:: Jason Bandlow 

 

In this tutorial, we show how to construct and manipulate free modules 

and vector spaces and their elements. 

 

Sage currently provides two implementations of free modules: 

:class:`FreeModule` and :class:`CombinatorialFreeModule`. The 

distinction between the two is mostly an accident in history. The 

latter allows for the basis to be indexed by any kind of objects, 

instead of just `0,1,2,...`. They also differ by feature set and 

efficiency. Eventually, both implementations will be merged under the 

name :class:`FreeModule`. In the mean time, we focus here on 

:class:`CombinatorialFreeModule`. We recommend to start by browsing 

its documentation:: 

 

sage: CombinatorialFreeModule? # not tested 

 

Construction, arithmetic, and basic usage 

========================================= 

 

We begin with a minimal example:: 

 

sage: G = Zmod(5) 

sage: F = CombinatorialFreeModule(ZZ, G) 

sage: F.an_element() 

2*B[0] + 2*B[1] + 3*B[2] 

 

 

`F` is the free module over the ring integers `\ZZ` whose canonical 

basis is indexed by the set of integers modulo 5. 

 

We can use any set, finite or not, to index the basis, as long as its 

elements are immutable. Here are some `\ZZ`-free modules; what is the 

indexing set for the basis in each example below? 

 

:: 

 

sage: F = CombinatorialFreeModule(ZZ, CC); F.an_element() 

B[1.00000000000000*I] 

sage: F = CombinatorialFreeModule(ZZ, Partitions(NonNegativeIntegers(), max_part=3)); F.an_element() 

2*B[[]] + 2*B[[1]] + 3*B[[2]] 

sage: F = CombinatorialFreeModule(ZZ, ['spam', 'eggs', '42']); F.an_element() 

3*B['42'] + 2*B['eggs'] + 2*B['spam'] 

 

Note that we use '42' (and not the number 42) in order to ensure that 

all objects are comparable in a deterministic way, which allows the 

elements to be printed in a predictable manner. It is not mandatory 

that indices have such a stable ordering, but if they do not, then the 

elements may be displayed in some random order. 

 

Lists are not hashable, and thus cannot be used to index the basis; 

instead one can use tuples:: 

 

sage: F = CombinatorialFreeModule(ZZ, ([1],[2],[3])); F.an_element() 

Traceback (most recent call last): 

... 

TypeError: unhashable type: 'list' 

 

sage: F = CombinatorialFreeModule(ZZ, ((1,), (2,), (3,))); F.an_element() 

2*B[(1,)] + 2*B[(2,)] + 3*B[(3,)] 

 

The name of the basis can be customized:: 

 

sage: F = CombinatorialFreeModule(ZZ, Zmod(5), prefix='a'); F.an_element() 

2*a[0] + 2*a[1] + 3*a[2] 

 

Let us do some arithmetic with elements of `A`:: 

 

sage: f = F.an_element(); f 

2*a[0] + 2*a[1] + 3*a[2] 

 

sage: 2*f 

4*a[0] + 4*a[1] + 6*a[2] 

 

sage: 2*f - f 

2*a[0] + 2*a[1] + 3*a[2] 

 

Inputing elements as they are output does not work by default:: 

 

sage: a[0] + 3*a[1] 

Traceback (most recent call last): 

... 

NameError: name 'a' is not defined 

 

To enable this, we must first get the *canonical basis* for the 

module:: 

 

sage: a = F.basis(); a 

Lazy family (Term map from Ring of integers modulo 5 to Free module generated by Ring of integers modulo 5 over Integer Ring(i))_{i in Ring of integers modulo 5} 

 

This gadget models the :class:`family <Family>` `(B_i)_{i \in \ZZ_5}`. 

In particular, one can run through its elements:: 

 

sage: list(a) 

[a[0], a[1], a[2], a[3], a[4]] 

 

recover its indexing set:: 

 

sage: a.keys() 

Ring of integers modulo 5 

 

or construct an element from the corresponding index:: 

 

sage: a[2] 

a[2] 

 

So now we can do:: 

 

sage: a[0] + 3*a[1] 

a[0] + 3*a[1] 

 

which enables copy-pasting outputs as long as the prefix matches the 

name of the basis:: 

 

sage: 2*a[0] + 2*a[1] + 3*a[2] == f 

True 

 

Be careful that the input is currently *not* checked:: 

 

sage: a['is'] + a['this'] + a['a'] + a['bug'] 

a['a'] + a['bug'] + a['is'] + a['this'] 

 

Manipulating free module elements 

================================= 

 

The elements of our module come with many methods for exploring and 

manipulating them:: 

 

sage: f.<tab> # not tested 

 

Some definitions: 

 

* A *monomial* is an element of the basis `B_i`; 

* A *term* is an element of the basis multiplied by a non zero 

*coefficient*: `c B_i`; 

* The support of that term is `i`. 

* The corresponding *item* is the :class:`tuple` ``(i, c)``. 

* The *support* of an element `f` is the collection of indices `i` 

such that `B_i` appears in `f` with non zero coefficient. 

* The *monomials*, *terms*, *items*, and *coefficients* of an element 

`f` are defined accordingly. 

* *Leading*/*trailing* refers to the *greatest*/*least* index. 

Elements are printed starting with the *least* index (for 

lexicographic order by default). 

 

Let us investigate those definitions on our example:: 

 

sage: f 

2*a[0] + 2*a[1] + 3*a[2] 

sage: f.leading_term() 

3*a[2] 

sage: f.leading_monomial() 

a[2] 

sage: f.leading_support() 

2 

sage: f.leading_coefficient() 

3 

sage: f.leading_item() 

(2, 3) 

 

sage: f.support() 

[0, 1, 2] 

sage: f.monomials() 

[a[0], a[1], a[2]] 

sage: f.coefficients() 

[2, 2, 3] 

 

We can iterate through the items of an element:: 

 

sage: for index, coeff in f: 

....: print("The coefficient of a_{%s} is %s"%(index, coeff)) 

The coefficient of a_{0} is 2 

The coefficient of a_{1} is 2 

The coefficient of a_{2} is 3 

 

This element can be thought of as a dictionary index-->coefficient:: 

 

sage: f[0], f[1], f[2] 

(2, 2, 3) 

 

This dictionary can be accessed explicitly with the monomial_coefficients method:: 

 

sage: f.monomial_coefficients() 

{0: 2, 1: 2, 2: 3} 

 

The ``map`` methods are useful to transform elements:: 

 

sage: f 

2*a[0] + 2*a[1] + 3*a[2] 

sage: f.map_support(lambda i: i+1) 

2*a[1] + 2*a[2] + 3*a[3] 

sage: f.map_coefficients(lambda c: c-3) 

-a[0] - a[1] 

sage: f.map_item(lambda i,c: (i+1,c-3)) 

-a[1] - a[2] 

 

Note: this last function should be called ``map_items``! 

 

Manipulating free modules 

========================= 

 

The free module itself (`A` in our example) has several utility 

methods for constructing elements:: 

 

sage: F.zero() 

0 

sage: F.term(1) 

a[1] 

sage: F.sum_of_monomials(i for i in Zmod(5) if i > 2) 

a[3] + a[4] 

sage: F.sum_of_terms((i+1,i) for i in Zmod(5) if i > 2) 

4*a[0] + 3*a[4] 

sage: F.sum(ZZ(i)*a[i+1] for i in Zmod(5) if i > 2) # Note coeff is not (currently) implicitly coerced 

4*a[0] + 3*a[4] 

 

Is safer to use ``F.sum()`` than to use ``sum()``: in case the input 

is an empty iterable, it makes sure the zero of `A` is returned, and 

not a plain `0`:: 

 

sage: F.sum([]), parent(F.sum([])) 

(0, Free module generated by Ring of integers modulo 5 over Integer Ring) 

sage: sum([]), parent(sum([])) 

(0, <... 'int'>) 

 

 

.. TODO:: 

 

Introduce echelon forms, submodules, quotients in the finite dimensional case 

 

Review 

====== 

 

In this tutorial we have seen how to construct vector spaces and free 

modules with a basis indexed by any kind of objects. 

 

To learn how to endow such free modules with additional structure, 

define morphisms, or implement modules with several distinguished 

basis, see the `Implementing Algebraic Structures 

<../../../../../thematic_tutorials/tutorial-implementing-algebraic-structures>`_ 

thematic tutorial. 

"""