Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
sagemath
GitHub Repository: sagemath/sagelib
Path: blob/master/sage/modules/quotient_module.py
4045 views
1
r"""
2
Quotients of finite rank free modules over a field.
3
"""
4
5
####################################################################################
6
# Copyright (C) 2009 William Stein <[email protected]>
7
#
8
# Distributed under the terms of the GNU General Public License (GPL)
9
#
10
# This code is distributed in the hope that it will be useful,
11
# but WITHOUT ANY WARRANTY; without even the implied warranty of
12
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13
# General Public License for more details.
14
#
15
# The full text of the GPL is available at:
16
#
17
# http://www.gnu.org/licenses/
18
####################################################################################
19
20
from free_module import FreeModule_ambient_field
21
22
class FreeModule_ambient_field_quotient(FreeModule_ambient_field):
23
r"""
24
A quotient V/W of two vector spaces as a vector space.
25
26
To obtain V or W use \code{self.V()} and \code{self.W()}.
27
28
EXAMPLES:
29
sage: k.<i> = QuadraticField(-1)
30
sage: A = k^3; V = A.span([[1,0,i], [2,i,0]])
31
sage: W = A.span([[3,i,i]])
32
sage: U = V/W; U
33
Vector space quotient V/W of dimension 1 over Number Field in i with defining polynomial x^2 + 1 where
34
V: Vector space of degree 3 and dimension 2 over Number Field in i with defining polynomial x^2 + 1
35
Basis matrix:
36
[ 1 0 i]
37
[ 0 1 -2]
38
W: Vector space of degree 3 and dimension 1 over Number Field in i with defining polynomial x^2 + 1
39
Basis matrix:
40
[ 1 1/3*i 1/3*i]
41
sage: U.V()
42
Vector space of degree 3 and dimension 2 over Number Field in i with defining polynomial x^2 + 1
43
Basis matrix:
44
[ 1 0 i]
45
[ 0 1 -2]
46
sage: U.W()
47
Vector space of degree 3 and dimension 1 over Number Field in i with defining polynomial x^2 + 1
48
Basis matrix:
49
[ 1 1/3*i 1/3*i]
50
sage: U.quotient_map()
51
Vector space morphism represented by the matrix:
52
[ 1]
53
[3*i]
54
Domain: Vector space of degree 3 and dimension 2 over Number Field in i with defining polynomial x^2 + 1
55
Basis matrix:
56
[ 1 0 i]
57
[ 0 1 -2]
58
Codomain: Vector space quotient V/W of dimension 1 over Number Field in i with defining polynomial x^2 + 1 where
59
V: Vector space of degree 3 and dimension 2 over Number Field in i with defining polynomial x^2 + 1
60
Basis matrix:
61
[ 1 0 i]
62
[ 0 1 -2]
63
W: Vector space of degree 3 and dimension 1 over Number Field in i with defining polynomial x^2 + 1
64
Basis matrix:
65
[ 1 1/3*i 1/3*i]
66
sage: Z = V.quotient(W)
67
sage: Z == U
68
True
69
70
TESTS::
71
72
sage: A = QQ^0; V = A.span([]) # corner case
73
sage: W = A.span([])
74
sage: U = V/W
75
76
sage: loads(dumps(U)) == U
77
True
78
sage: type(loads(dumps(U)) )
79
<class 'sage.modules.quotient_module.FreeModule_ambient_field_quotient_with_category'>
80
"""
81
def __init__(self, domain, sub, quotient_matrix, lift_matrix, inner_product_matrix = None):
82
"""
83
Create this quotient space, from the given domain, sub-module, and quotient_matrix.
84
85
EXAMPLES:
86
sage: A = QQ^5; V = A.span_of_basis([[1,0,-1,1,1], [1,-1,0,2/3,3/4]]); V
87
Vector space of degree 5 and dimension 2 over Rational Field
88
User basis matrix:
89
[ 1 0 -1 1 1]
90
[ 1 -1 0 2/3 3/4]
91
sage: W = V.span_of_basis([V.0 - 2/3*V.1]); W
92
Vector space of degree 5 and dimension 1 over Rational Field
93
User basis matrix:
94
[1/3 2/3 -1 5/9 1/2]
95
96
This creates a quotient vector space, which calls the init method:
97
sage: Q = V / W
98
99
Behold the type of Q:
100
sage: type(Q)
101
<class 'sage.modules.quotient_module.FreeModule_ambient_field_quotient_with_category'>
102
103
We do some consistency checks on the extra quotient and
104
lifting structure of Q.
105
sage: Q(V.0)
106
(1)
107
sage: Q( V.0 - 2/3*V.1 )
108
(0)
109
sage: v = Q.lift(Q.0); v
110
(1, 0, -1, 1, 1)
111
sage: Q( v )
112
(1)
113
"""
114
base_field = domain.base_field()
115
dimension = quotient_matrix.ncols()
116
sparse = domain.is_sparse()
117
self.__sub = sub
118
self.__domain = domain
119
self.__hash = hash((domain, sub))
120
FreeModule_ambient_field.__init__(self, base_field, dimension, sparse)
121
self.__quo_map = domain.Hom(self)(quotient_matrix)
122
self.__lift_map = self.Hom(domain)(lift_matrix)
123
124
def _repr_(self):
125
"""
126
Return the rather verbose string representation of this quotient space V/W.
127
128
EXAMPLES:
129
We create a quotient vector space over a finite field:
130
sage: k.<a> = GF(9); A = k^3; V = A.span_of_basis([[1,0,a], [a,a,1]]); W = V.span([V.1])
131
sage: Q = V/W
132
133
Note the type:
134
sage: type(Q)
135
<class 'sage.modules.quotient_module.FreeModule_ambient_field_quotient_with_category'>
136
137
The string representation mentions that this is a quotient V/W, that the quotient
138
has dimension 1 and is over a finite field, and also describes V and W:
139
sage: Q._repr_()
140
'Vector space quotient V/W of dimension 1 over Finite Field in a of size 3^2 where\nV: Vector space of degree 3 and dimension 2 over Finite Field in a of size 3^2\nUser basis matrix:\n[1 0 a]\n[a a 1]\nW: Vector space of degree 3 and dimension 1 over Finite Field in a of size 3^2\nBasis matrix:\n[ 1 1 a + 2]'
141
"""
142
return "%s space quotient V/W of dimension %s over %s where\nV: %s\nW: %s"%(
143
"Sparse vector" if self.is_sparse() else "Vector",
144
self.dimension(), self.base_ring(),
145
self.V(), self.W())
146
147
def __hash__(self):
148
"""
149
Return hash of this quotient space V/W, which is by definition the hash of
150
the tuple (V,W).
151
152
EXAMPLES:
153
We compute the hash of a certain 0-dimension quotient vector space:
154
sage: A = QQ^2; V = A.span_of_basis([[1,0], [1,1]]); W = V.span([V.1, V.0])
155
sage: Q = V/W; Q.dimension()
156
0
157
sage: hash(Q)
158
954887582 # 32-bit
159
-5856620741060301410 # 64-bit
160
161
The hash is just got by hashing both V and W.
162
sage: hash((V, W))
163
954887582 # 32-bit
164
-5856620741060301410 # 64-bit
165
"""
166
return self.__hash
167
168
def __cmp__(self, other):
169
"""
170
Compare self and other.
171
172
If other is not a quotient of vector spaces, returns
173
comparison of the underlying types. If it is, return
174
comparison of the pair (V,W) so that self is V/W for each of
175
self and other.
176
177
EXAMPLES:
178
We create three quotient spaces and compare them:
179
sage: A = QQ^2; V = A.span_of_basis([[1,0], [1,1]]);
180
sage: W0 = V.span([V.1, V.0]); W1 = V.span([V.1]); W2 = V.span([V.1])
181
sage: Q0 = V/W0; Q1 = V/W1; Q2 = V/W2
182
sage: cmp(Q0, Q1)
183
1
184
sage: cmp(Q1, Q0)
185
-1
186
sage: cmp(Q1, Q2)
187
0
188
sage: cmp(Q1, 5) != 0
189
True
190
"""
191
if not isinstance(other, FreeModule_ambient_field_quotient):
192
return cmp(type(self), type(other))
193
return cmp((self.V(), self.W()), (other.V(), other.W()))
194
195
def __call__(self, x):
196
"""
197
Coerce an element into this quotient space V/W if there is a way to make
198
sense of it.
199
200
An element coerces in if it can be coerced into V, or if not at least if
201
if it can be made sense of as a list of length the dimension of self.
202
203
EXAMPLES:
204
We create a 2-dimensional quotient of a 3-dimension ambient vector space.
205
sage: M = QQ^3 / [[1,2,3]]
206
207
A list of length 3 coerces into QQ^3, so it coerces into M.
208
sage: M([1,2,4])
209
(-1/3, -2/3)
210
sage: M([1,2,3])
211
(0, 0)
212
213
A list of length 2 at least coerces into M, where here it just gives
214
the corresponding linear combination of the basis for M.
215
sage: M([1,2])
216
(1, 2)
217
sage: M.0 + 2*M.1
218
(1, 2)
219
"""
220
try:
221
if x.parent() is self:
222
return x
223
except AttributeError:
224
pass
225
try:
226
return FreeModule_ambient_field.__call__(self, x)
227
except TypeError:
228
pass
229
return self._coerce_impl(self.__domain(x))
230
231
def _coerce_impl(self, x):
232
"""
233
Canonical coercion into this quotient space V/W.
234
235
Elements canonically coerce into self if they canonically
236
coerce into V.
237
238
EXAMPLES:
239
sage: V = QQ^3; W = V.span([[1,0,0]]); Q = V/W
240
sage: Q._coerce_impl(V.0)
241
(0, 0)
242
sage: Q._coerce_impl(0)
243
(0, 0)
244
sage: Q._coerce_impl(V.1)
245
(1, 0)
246
sage: Q.0
247
(1, 0)
248
sage: Q.0 + V.1
249
(2, 0)
250
251
Here we coerce in something that is over ZZ, so it canonically coerce into V hence self.
252
sage: Q._coerce_impl((ZZ^3)([1,2,3]))
253
(2, 3)
254
255
Here there is no canonical coercion:
256
sage: Q._coerce_impl((GF(17)^3)([1,2,3]))
257
Traceback (most recent call last):
258
...
259
TypeError: Automatic coercion supported only for vectors or 0.
260
"""
261
try:
262
if x.parent() is self:
263
return x
264
except AttributeError:
265
pass
266
return self.__quo_map(self.__domain._coerce_impl(x))
267
268
def quotient_map(self):
269
"""
270
Given this quotient space $Q = V/W$, return the natural quotient map from V to Q.
271
272
EXAMPLES:
273
sage: M = QQ^3 / [[1,2,3]]
274
sage: M.quotient_map()
275
Vector space morphism represented by the matrix:
276
[ 1 0]
277
[ 0 1]
278
[-1/3 -2/3]
279
Domain: Vector space of dimension 3 over Rational Field
280
Codomain: Vector space quotient V/W of dimension 2 over Rational Field where
281
V: Vector space of dimension 3 over Rational Field
282
W: Vector space of degree 3 and dimension 1 over Rational Field
283
Basis matrix:
284
[1 2 3]
285
286
sage: M.quotient_map()( (QQ^3)([1,2,3]) )
287
(0, 0)
288
"""
289
return self.__quo_map
290
291
def lift_map(self):
292
"""
293
Given this quotient space $Q = V/W$, return a fixed choice of linear homomorphism
294
(a section) from Q to V.
295
296
EXAMPLES:
297
sage: M = QQ^3 / [[1,2,3]]
298
sage: M.lift_map()
299
Vector space morphism represented by the matrix:
300
[1 0 0]
301
[0 1 0]
302
Domain: Vector space quotient V/W of dimension 2 over Rational Field where
303
V: Vector space of dimension 3 over Rational Field
304
W: Vector space of degree 3 and dimension 1 over Rational Field
305
Basis matrix:
306
[1 2 3]
307
Codomain: Vector space of dimension 3 over Rational Field
308
"""
309
return self.__lift_map
310
311
def lift(self, x):
312
"""
313
Lift element of this quotient V/W to V by applying the fixed lift homomorphism.
314
315
The lift is a fixed homomorphism.
316
317
EXAMPLES:
318
sage: M = QQ^3 / [[1,2,3]]
319
sage: M.lift(M.0)
320
(1, 0, 0)
321
sage: M.lift(M.1)
322
(0, 1, 0)
323
sage: M.lift(M.0 - 2*M.1)
324
(1, -2, 0)
325
"""
326
return self.__lift_map(x)
327
328
def W(self):
329
"""
330
Given this quotient space $Q = V/W$, return W.
331
332
EXAMPLES:
333
sage: M = QQ^10 / [range(10), range(2,12)]
334
sage: M.W()
335
Vector space of degree 10 and dimension 2 over Rational Field
336
Basis matrix:
337
[ 1 0 -1 -2 -3 -4 -5 -6 -7 -8]
338
[ 0 1 2 3 4 5 6 7 8 9]
339
"""
340
return self.__sub
341
342
def V(self):
343
"""
344
Given this quotient space $Q = V/W$, return $V$.
345
346
EXAMPLES:
347
sage: M = QQ^10 / [range(10), range(2,12)]
348
sage: M.V()
349
Vector space of dimension 10 over Rational Field
350
"""
351
return self.__domain
352
353
def cover(self):
354
"""
355
Given this quotient space $Q = V/W$, return $V$. This is the same as self.V().
356
357
EXAMPLES:
358
sage: M = QQ^10 / [range(10), range(2,12)]
359
sage: M.cover()
360
Vector space of dimension 10 over Rational Field
361
"""
362
return self.V()
363
364
def relations(self):
365
"""
366
Given this quotient space $Q = V/W$, return $W$. This is the same as self.W().
367
368
EXAMPLES:
369
sage: M = QQ^10 / [range(10), range(2,12)]
370
sage: M.relations()
371
Vector space of degree 10 and dimension 2 over Rational Field
372
Basis matrix:
373
[ 1 0 -1 -2 -3 -4 -5 -6 -7 -8]
374
[ 0 1 2 3 4 5 6 7 8 9]
375
"""
376
return self.W()
377
378