This repository has been archived by the owner on Jan 30, 2023. It is now read-only.
-
-
Notifications
You must be signed in to change notification settings - Fork 7
/
free_module.py
6813 lines (5502 loc) · 218 KB
/
free_module.py
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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
r"""
Free modules
Sage supports computation with free modules over an arbitrary commutative ring.
Nontrivial functionality is available over `\ZZ`, fields, and some principal
ideal domains (e.g. `\QQ[x]` and rings of integers of number fields). All free
modules over an integral domain are equipped with an embedding in an ambient
vector space and an inner product, which you can specify and change.
Create the free module of rank `n` over an arbitrary commutative ring `R` using
the command ``FreeModule(R,n)``. Equivalently, ``R^n`` also creates that free
module.
The following example illustrates the creation of both a vector space and a
free module over the integers and a submodule of it. Use the functions
``FreeModule``, ``span`` and member functions of free modules to create free
modules. *Do not use the FreeModule_xxx constructors directly.*
EXAMPLES::
sage: V = VectorSpace(QQ,3)
sage: W = V.subspace([[1,2,7], [1,1,0]])
sage: W
Vector space of degree 3 and dimension 2 over Rational Field
Basis matrix:
[ 1 0 -7]
[ 0 1 7]
sage: C = VectorSpaces(FiniteField(7))
sage: C
Category of vector spaces over Finite Field of size 7
sage: C(W)
Vector space of degree 3 and dimension 2 over Finite Field of size 7
Basis matrix:
[1 0 0]
[0 1 0]
::
sage: M = ZZ^3
sage: C = VectorSpaces(FiniteField(7))
sage: C(M)
Vector space of dimension 3 over Finite Field of size 7
sage: W = M.submodule([[1,2,7], [8,8,0]])
sage: C(W)
Vector space of degree 3 and dimension 2 over Finite Field of size 7
Basis matrix:
[1 0 0]
[0 1 0]
We illustrate the exponent notation for creation of free modules.
::
sage: ZZ^4
Ambient free module of rank 4 over the principal ideal domain Integer Ring
sage: QQ^2
Vector space of dimension 2 over Rational Field
sage: RR^3
Vector space of dimension 3 over Real Field with 53 bits of precision
Base ring::
sage: R.<x,y> = QQ[]
sage: M = FreeModule(R,2)
sage: M.base_ring()
Multivariate Polynomial Ring in x, y over Rational Field
::
sage: VectorSpace(QQ, 10).base_ring()
Rational Field
TESTS:
We intersect a zero-dimensional vector space with a
1-dimension submodule.
::
sage: V = (QQ^1).span([])
sage: W = ZZ^1
sage: V.intersection(W)
Free module of degree 1 and rank 0 over Integer Ring
Echelon basis matrix:
[]
We construct subspaces of real and complex double vector spaces and
verify that the element types are correct::
sage: V = FreeModule(RDF, 3); V
Vector space of dimension 3 over Real Double Field
sage: V.0
(1.0, 0.0, 0.0)
sage: type(V.0)
<type 'sage.modules.vector_real_double_dense.Vector_real_double_dense'>
sage: W = V.span([V.0]); W
Vector space of degree 3 and dimension 1 over Real Double Field
Basis matrix:
[1.0 0.0 0.0]
sage: type(W.0)
<type 'sage.modules.vector_real_double_dense.Vector_real_double_dense'>
sage: V = FreeModule(CDF, 3); V
Vector space of dimension 3 over Complex Double Field
sage: type(V.0)
<type 'sage.modules.vector_complex_double_dense.Vector_complex_double_dense'>
sage: W = V.span_of_basis([CDF.0 * V.1]); W
Vector space of degree 3 and dimension 1 over Complex Double Field
User basis matrix:
[ 0.0 1.0*I 0.0]
sage: type(W.0)
<type 'sage.modules.vector_complex_double_dense.Vector_complex_double_dense'>
Basis vectors are immutable::
sage: A = span([[1,2,3], [4,5,6]], ZZ)
sage: A.0
(1, 2, 3)
sage: A.0[0] = 5
Traceback (most recent call last):
...
ValueError: vector is immutable; please change a copy instead (use copy())
Among other things, this tests that we can save and load submodules
and elements::
sage: M = ZZ^3
sage: TestSuite(M).run()
sage: W = M.span_of_basis([[1,2,3],[4,5,19]])
sage: TestSuite(W).run()
sage: v = W.0 + W.1
sage: TestSuite(v).run()
AUTHORS:
- William Stein (2005, 2007)
- David Kohel (2007, 2008)
- Niles Johnson (2010-08): (:trac:`3893`) ``random_element()`` should pass on ``*args`` and ``**kwds``.
- Simon King (2010-12):
:trac:`8800` : Fixing a bug in ``denominator()``.
- Simon King (2010-12), Peter Bruin (June 2014):
:trac:`10513` : New coercion model and category framework.
"""
###########################################################################
# Copyright (C) 2005, 2007 William Stein <wstein@gmail.com>
# Copyright (C) 2007, 2008 David Kohel <kohel@iml.univ-mrs.fr>
#
# Distributed under the terms of the GNU General Public License (GPL)
#
# This code is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# General Public License for more details.
#
# The full text of the GPL is available at:
#
# http://www.gnu.org/licenses/
###########################################################################
from __future__ import print_function, absolute_import
from . import free_module_element
import sage.matrix.matrix_space
import sage.misc.latex as latex
from sage.modules.module import Module
import sage.rings.finite_rings.finite_field_constructor as finite_field
import sage.rings.ring as ring
import sage.rings.integer_ring
import sage.rings.rational_field
import sage.rings.finite_rings.integer_mod_ring
import sage.rings.infinity
import sage.rings.integer
from sage.categories.principal_ideal_domains import PrincipalIdealDomains
from sage.misc.randstate import current_randstate
from sage.structure.sequence import Sequence
from sage.misc.cachefunc import cached_method
from warnings import warn
###############################################################################
#
# Constructor functions
#
###############################################################################
from sage.structure.factory import UniqueFactory
class FreeModuleFactory(UniqueFactory):
r"""
Create the free module over the given commutative ring of the given
rank.
INPUT:
- ``base_ring`` - a commutative ring
- ``rank`` - a nonnegative integer
- ``sparse`` - bool; (default False)
- ``inner_product_matrix`` - the inner product
matrix (default None)
OUTPUT: a free module
.. note::
In Sage it is the case that there is only one dense and one
sparse free ambient module of rank `n` over `R`.
EXAMPLES:
First we illustrate creating free modules over various base fields.
The base field affects the free module that is created. For
example, free modules over a field are vector spaces, and free
modules over a principal ideal domain are special in that more
functionality is available for them than for completely general
free modules.
::
sage: FreeModule(Integers(8),10)
Ambient free module of rank 10 over Ring of integers modulo 8
sage: FreeModule(QQ,10)
Vector space of dimension 10 over Rational Field
sage: FreeModule(ZZ,10)
Ambient free module of rank 10 over the principal ideal domain Integer Ring
sage: FreeModule(FiniteField(5),10)
Vector space of dimension 10 over Finite Field of size 5
sage: FreeModule(Integers(7),10)
Vector space of dimension 10 over Ring of integers modulo 7
sage: FreeModule(PolynomialRing(QQ,'x'),5)
Ambient free module of rank 5 over the principal ideal domain Univariate Polynomial Ring in x over Rational Field
sage: FreeModule(PolynomialRing(ZZ,'x'),5)
Ambient free module of rank 5 over the integral domain Univariate Polynomial Ring in x over Integer Ring
Of course we can make rank 0 free modules::
sage: FreeModule(RealField(100),0)
Vector space of dimension 0 over Real Field with 100 bits of precision
Next we create a free module with sparse representation of
elements. Functionality with sparse modules is *identical* to dense
modules, but they may use less memory and arithmetic may be faster
(or slower!).
::
sage: M = FreeModule(ZZ,200,sparse=True)
sage: M.is_sparse()
True
sage: type(M.0)
<type 'sage.modules.free_module_element.FreeModuleElement_generic_sparse'>
The default is dense.
::
sage: M = ZZ^200
sage: type(M.0)
<type 'sage.modules.vector_integer_dense.Vector_integer_dense'>
Note that matrices associated in some way to sparse free modules
are sparse by default::
sage: M = FreeModule(Integers(8), 2)
sage: A = M.basis_matrix()
sage: A.is_sparse()
False
sage: Ms = FreeModule(Integers(8), 2, sparse=True)
sage: M == Ms # as mathematical objects they are equal
True
sage: Ms.basis_matrix().is_sparse()
True
We can also specify an inner product matrix, which is used when
computing inner products of elements.
::
sage: A = MatrixSpace(ZZ,2)([[1,0],[0,-1]])
sage: M = FreeModule(ZZ,2,inner_product_matrix=A)
sage: v, w = M.gens()
sage: v.inner_product(w)
0
sage: v.inner_product(v)
1
sage: w.inner_product(w)
-1
sage: (v+2*w).inner_product(w)
-2
You can also specify the inner product matrix by giving anything
that coerces to an appropriate matrix. This is only useful if the
inner product matrix takes values in the base ring.
::
sage: FreeModule(ZZ,2,inner_product_matrix=1).inner_product_matrix()
[1 0]
[0 1]
sage: FreeModule(ZZ,2,inner_product_matrix=[1,2,3,4]).inner_product_matrix()
[1 2]
[3 4]
sage: FreeModule(ZZ,2,inner_product_matrix=[[1,2],[3,4]]).inner_product_matrix()
[1 2]
[3 4]
.. todo::
Refactor modules such that it only counts what category the base
ring belongs to, but not what is its Python class.
"""
def create_key(self, base_ring, rank, sparse=False, inner_product_matrix=None):
"""
TESTS::
sage: loads(dumps(ZZ^6)) is ZZ^6
True
sage: loads(dumps(RDF^3)) is RDF^3
True
TODO: replace the above by ``TestSuite(...).run()``, once
:meth:`_test_pickling` will test unique representation and not
only equality.
"""
rank = int(sage.rings.integer.Integer(rank))
if not (inner_product_matrix is None):
inner_product_matrix = sage.matrix.matrix_space.MatrixSpace(base_ring, rank)(inner_product_matrix)
inner_product_matrix.set_immutable()
return (base_ring, rank, sparse, inner_product_matrix)
def create_object(self, version, key):
base_ring, rank, sparse, inner_product_matrix = key
if inner_product_matrix is not None:
from .free_quadratic_module import FreeQuadraticModule
return FreeQuadraticModule(base_ring, rank, inner_product_matrix=inner_product_matrix, sparse=sparse)
if not isinstance(sparse,bool):
raise TypeError("Argument sparse (= %s) must be True or False" % sparse)
if not (hasattr(base_ring,'is_commutative') and base_ring.is_commutative()):
warn("""You are constructing a free module
over a noncommutative ring. Sage does not have a concept
of left/right and both sided modules, so be careful.
It's also not guaranteed that all multiplications are
done from the right side.""")
# raise TypeError, "The base_ring must be a commutative ring."
try:
if not sparse and isinstance(base_ring,sage.rings.real_double.RealDoubleField_class):
return RealDoubleVectorSpace_class(rank)
elif not sparse and isinstance(base_ring,sage.rings.complex_double.ComplexDoubleField_class):
return ComplexDoubleVectorSpace_class(rank)
elif base_ring.is_field():
return FreeModule_ambient_field(base_ring, rank, sparse=sparse)
elif base_ring in PrincipalIdealDomains():
return FreeModule_ambient_pid(base_ring, rank, sparse=sparse)
elif isinstance(base_ring, sage.rings.number_field.order.Order) \
and base_ring.is_maximal() and base_ring.class_number() == 1:
return FreeModule_ambient_pid(base_ring, rank, sparse=sparse)
elif isinstance(base_ring, ring.IntegralDomain) or base_ring.is_integral_domain():
return FreeModule_ambient_domain(base_ring, rank, sparse=sparse)
else:
return FreeModule_ambient(base_ring, rank, sparse=sparse)
except NotImplementedError:
return FreeModule_ambient(base_ring, rank, sparse=sparse)
FreeModule = FreeModuleFactory("FreeModule")
def VectorSpace(K, dimension, sparse=False, inner_product_matrix=None):
"""
EXAMPLES:
The base can be complicated, as long as it is a field.
::
sage: V = VectorSpace(FractionField(PolynomialRing(ZZ,'x')),3)
sage: V
Vector space of dimension 3 over Fraction Field of Univariate Polynomial Ring in x over Integer Ring
sage: V.basis()
[
(1, 0, 0),
(0, 1, 0),
(0, 0, 1)
]
The base must be a field or a ``TypeError`` is raised.
::
sage: VectorSpace(ZZ,5)
Traceback (most recent call last):
...
TypeError: Argument K (= Integer Ring) must be a field.
"""
if not K.is_field():
raise TypeError("Argument K (= %s) must be a field." % K)
if not sparse in (True,False):
raise TypeError("Argument sparse (= %s) must be a boolean."%sparse)
return FreeModule(K, rank=dimension, sparse=sparse, inner_product_matrix=inner_product_matrix)
###############################################################################
#
# The span of vectors
#
###############################################################################
def span(gens, base_ring=None, check=True, already_echelonized=False):
r"""
Return the span of the vectors in ``gens`` using scalars from ``base_ring``.
INPUT:
- ``gens`` - a list of either vectors or lists of ring elements
used to generate the span
- ``base_ring`` - default: ``None`` - a principal ideal domain
for the ring of scalars
- ``check`` - default: ``True`` - passed to the ``span()`` method
of the ambient module
- ``already_echelonized`` - default: ``False`` - set to ``True``
if the vectors form the rows of a matrix in echelon form, in
order to skip the computation of an echelonized basis for the
span.
OUTPUT:
A module (or vector space) that is all the linear combinations of the
free module elements (or vectors) with scalars from the
ring (or field) given by ``base_ring``. See the examples below
describing behavior when the base ring is not specified and/or
the module elements are given as lists that do not carry
explicit base ring information.
EXAMPLES:
The vectors in the list of generators can be given as
lists, provided a base ring is specified and the elements of the list
are in the ring (or the fraction field of the ring). If the
base ring is a field, the span is a vector space. ::
sage: V = span([[1,2,5], [2,2,2]], QQ); V
Vector space of degree 3 and dimension 2 over Rational Field
Basis matrix:
[ 1 0 -3]
[ 0 1 4]
sage: span([V.gen(0)], QuadraticField(-7,'a'))
Vector space of degree 3 and dimension 1 over Number Field in a with defining polynomial x^2 + 7
Basis matrix:
[ 1 0 -3]
sage: span([[1,2,3], [2,2,2], [1,2,5]], GF(2))
Vector space of degree 3 and dimension 1 over Finite Field of size 2
Basis matrix:
[1 0 1]
If the base ring is not a field, then a module is created.
The entries of the vectors can lie outside the ring, if they
are in the fraction field of the ring. ::
sage: span([[1,2,5], [2,2,2]], ZZ)
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1 0 -3]
[ 0 2 8]
sage: span([[1,1,1], [1,1/2,1]], ZZ)
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1 0 1]
[ 0 1/2 0]
sage: R.<x> = QQ[]
sage: M= span( [[x, x^2+1], [1/x, x^3]], R); M
Free module of degree 2 and rank 2 over
Univariate Polynomial Ring in x over Rational Field
Echelon basis matrix:
[ 1/x x^3]
[ 0 x^5 - x^2 - 1]
sage: M.basis()[0][0].parent()
Fraction Field of Univariate Polynomial Ring in x over Rational Field
A base ring can be inferred if the generators are given as a
list of vectors. ::
sage: span([vector(QQ, [1,2,3]), vector(QQ, [4,5,6])])
Vector space of degree 3 and dimension 2 over Rational Field
Basis matrix:
[ 1 0 -1]
[ 0 1 2]
sage: span([vector(QQ, [1,2,3]), vector(ZZ, [4,5,6])])
Vector space of degree 3 and dimension 2 over Rational Field
Basis matrix:
[ 1 0 -1]
[ 0 1 2]
sage: span([vector(ZZ, [1,2,3]), vector(ZZ, [4,5,6])])
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[1 2 3]
[0 3 6]
TESTS::
sage: span([[1,2,3], [2,2,2], [1,2/3,5]], ZZ)
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[ 1 0 13]
[ 0 2/3 6]
[ 0 0 14]
sage: span([[1,2,3], [2,2,2], [1,2,QQ['x'].gen()]], ZZ)
Traceback (most recent call last):
...
ValueError: The elements of gens (= [[1, 2, 3], [2, 2, 2], [1, 2, x]]) must be defined over base_ring (= Integer Ring) or its field of fractions.
For backwards compatibility one can also give the base ring as the
first argument. ::
sage: span(QQ,[[1,2],[3,4]])
Vector space of degree 2 and dimension 2 over Rational Field
Basis matrix:
[1 0]
[0 1]
The base ring must be a principal ideal domain (PID). ::
sage: span([[1,2,3]], Integers(6))
Traceback (most recent call last):
...
TypeError: The base_ring (= Ring of integers modulo 6)
must be a principal ideal domain.
Fix :trac:`5575`::
sage: V = QQ^3
sage: span([V.0, V.1])
Vector space of degree 3 and dimension 2 over Rational Field
Basis matrix:
[1 0 0]
[0 1 0]
Improve error message from :trac:`12541`::
sage: span({0:vector([0,1])}, QQ)
Traceback (most recent call last):
...
TypeError: generators must be lists of ring elements
or free module elements!
"""
if ring.is_Ring(gens):
# we allow the old input format with first input the base_ring.
# Do we want to deprecate it?..
base_ring, gens = gens, base_ring
try:
if base_ring is None:
gens = Sequence(gens)
R = gens.universe().base_ring()
else:
gens = list(gens)
R = base_ring
except TypeError:
raise TypeError("generators must be given as an iterable structure!")
if R not in PrincipalIdealDomains():
raise TypeError("The base_ring (= %s) must be a principal ideal "
"domain." % R)
if len(gens) == 0:
return FreeModule(R, 0)
else:
x = gens[0]
if free_module_element.is_FreeModuleElement(x):
M = x.parent()
else:
try:
x = list(x)
except TypeError:
raise TypeError("generators must be lists of ring elements or "
"free module elements!")
M = FreeModule(R, len(x))
try:
gens = [M(_) for _ in gens]
except TypeError:
R = R.fraction_field()
M = FreeModule(R, len(x))
try:
gens = [M(_) for _ in gens]
except TypeError:
raise ValueError("The elements of gens (= %s) must be "
"defined over base_ring (= %s) or its "
"field of fractions." % (gens, base_ring))
return M.span(gens=gens, base_ring=base_ring, check=check,
already_echelonized=already_echelonized)
###############################################################################
#
# Base class for all free modules
#
###############################################################################
def is_FreeModule(M):
"""
Return True if M inherits from FreeModule_generic.
EXAMPLES::
sage: from sage.modules.free_module import is_FreeModule
sage: V = ZZ^3
sage: is_FreeModule(V)
True
sage: W = V.span([ V.random_element() for i in range(2) ])
sage: is_FreeModule(W)
True
"""
return isinstance(M, FreeModule_generic)
class FreeModule_generic(Module):
"""
Base class for all free modules.
TESTS:
Check that :trac:`17576` is fixed::
sage: V = VectorSpace(RDF, 3)
sage: v = vector(RDF, [1, 2, 3, 4])
sage: v in V
False
"""
def __init__(self, base_ring, rank, degree, sparse=False,
coordinate_ring=None, category=None):
"""
Create the free module of given rank ``rank`` over the given base
ring ``base_ring``.
INPUT:
- ``base_ring`` -- a commutative ring
- ``rank`` -- a non-negative integer
- ``degree`` -- a non-negative integer
- ``sparse`` -- bool (default: False)
- ``coordinate_ring`` -- a ring containing ``base_ring``
(default: equal to ``base_ring``)
- ``category`` -- category (default: None)
If ``base_ring`` is a field, then the default category is the
category of finite-dimensional vector spaces over that field;
otherwise it is the category of finite-dimensional free modules
over that ring. In addition, the category is intersected with the
category of finite enumerated sets if the ring is finite or the
rank is 0.
EXAMPLES::
sage: PolynomialRing(QQ,3,'x')^3
Ambient free module of rank 3 over the integral domain Multivariate Polynomial Ring in x0, x1, x2 over Rational Field
sage: FreeModule(GF(7),3).category()
Category of finite enumerated finite dimensional vector spaces with basis over
(finite enumerated fields and subquotients of monoids and quotients of semigroups)
sage: V = QQ^4; V.category()
Category of finite dimensional vector spaces with basis over
(quotient fields and metric spaces)
sage: V = GF(5)**20; V.category()
Category of finite enumerated finite dimensional vector spaces with basis over (finite enumerated fields and subquotients of monoids and quotients of semigroups)
sage: FreeModule(ZZ,3).category()
Category of finite dimensional modules with basis over
(euclidean domains and infinite enumerated sets
and metric spaces)
sage: (QQ^0).category()
Category of finite enumerated finite dimensional vector spaces with basis over (quotient fields and metric spaces)
TESTS::
sage: M = FreeModule(ZZ,20,sparse=False)
sage: x = M.random_element()
sage: type(x)
<type 'sage.modules.vector_integer_dense.Vector_integer_dense'>
sage: M.element_class
<type 'sage.modules.vector_integer_dense.Vector_integer_dense'>
sage: N = FreeModule(ZZ,20,sparse=True)
sage: y = N.random_element()
sage: type(y)
<type 'sage.modules.free_module_element.FreeModuleElement_generic_sparse'>
sage: N.element_class
<type 'sage.modules.free_module_element.FreeModuleElement_generic_sparse'>
"""
if not base_ring.is_commutative():
warn("""You are constructing a free module
over a noncommutative ring. Sage does not have a concept
of left/right and both sided modules, so be careful.
It's also not guaranteed that all multiplications are
done from the right side.""")
if coordinate_ring is None:
coordinate_ring = base_ring
if not hasattr(self, 'Element'):
self.Element = element_class(coordinate_ring, sparse)
rank = sage.rings.integer.Integer(rank)
if rank < 0:
raise ValueError("rank (=%s) must be nonnegative"%rank)
degree = sage.rings.integer.Integer(degree)
if degree < 0:
raise ValueError("degree (=%s) must be nonnegative"%degree)
if category is None:
from sage.categories.all import FreeModules
category = FreeModules(base_ring.category()).FiniteDimensional()
try:
if base_ring.is_finite() or rank == 0:
category = category.Enumerated().Finite()
except:
pass
super(FreeModule_generic, self).__init__(base_ring, category=category)
self.__coordinate_ring = coordinate_ring
self.__uses_ambient_inner_product = True
self.__rank = rank
self.__degree = degree
self.__is_sparse = sparse
self._gram_matrix = None
def construction(self):
"""
The construction functor and base ring for self.
EXAMPLES::
sage: R = PolynomialRing(QQ,3,'x')
sage: V = R^5
sage: V.construction()
(VectorFunctor, Multivariate Polynomial Ring in x0, x1, x2 over Rational Field)
"""
from sage.categories.pushout import VectorFunctor
if hasattr(self,'_inner_product_matrix'):
return VectorFunctor(self.rank(), self.is_sparse(),self.inner_product_matrix()), self.base_ring()
return VectorFunctor(self.rank(), self.is_sparse()), self.base_ring()
# FIXME: what's the level of generality of FreeModuleHomspace?
# Should there be a category for free modules accepting it as hom space?
# See similar method for FreeModule_generic_field class
def _Hom_(self, Y, category):
from .free_module_homspace import FreeModuleHomspace
return FreeModuleHomspace(self, Y, category)
def dense_module(self):
"""
Return corresponding dense module.
EXAMPLES:
We first illustrate conversion with ambient spaces::
sage: M = FreeModule(QQ,3)
sage: S = FreeModule(QQ,3, sparse=True)
sage: M.sparse_module()
Sparse vector space of dimension 3 over Rational Field
sage: S.dense_module()
Vector space of dimension 3 over Rational Field
sage: M.sparse_module() == S
True
sage: S.dense_module() == M
True
sage: M.dense_module() == M
True
sage: S.sparse_module() == S
True
Next we create a subspace::
sage: M = FreeModule(QQ,3, sparse=True)
sage: V = M.span([ [1,2,3] ] ); V
Sparse vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[1 2 3]
sage: V.sparse_module()
Sparse vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[1 2 3]
"""
if self.is_sparse():
return self._dense_module()
return self
def _dense_module(self):
"""
Creates a dense module with the same defining data as self.
N.B. This function is for internal use only! See dense_module for
use.
EXAMPLES::
sage: M = FreeModule(Integers(8),3)
sage: S = FreeModule(Integers(8),3, sparse=True)
sage: M is S._dense_module()
True
"""
A = self.ambient_module().dense_module()
return A.span(self.basis())
def sparse_module(self):
"""
Return the corresponding sparse module with the same defining
data.
EXAMPLES:
We first illustrate conversion with ambient spaces::
sage: M = FreeModule(Integers(8),3)
sage: S = FreeModule(Integers(8),3, sparse=True)
sage: M.sparse_module()
Ambient sparse free module of rank 3 over Ring of integers modulo 8
sage: S.dense_module()
Ambient free module of rank 3 over Ring of integers modulo 8
sage: M.sparse_module() is S
True
sage: S.dense_module() is M
True
sage: M.dense_module() is M
True
sage: S.sparse_module() is S
True
Next we convert a subspace::
sage: M = FreeModule(QQ,3)
sage: V = M.span([ [1,2,3] ] ); V
Vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[1 2 3]
sage: V.sparse_module()
Sparse vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[1 2 3]
"""
if self.is_sparse():
return self
return self._sparse_module()
def _sparse_module(self):
"""
Creates a sparse module with the same defining data as self.
N.B. This function is for internal use only! See sparse_module for
use.
EXAMPLES::
sage: M = FreeModule(Integers(8),3)
sage: S = FreeModule(Integers(8),3, sparse=True)
sage: M._sparse_module() is S
True
"""
A = self.ambient_module().sparse_module()
return A.span(self.basis())
def _an_element_(self):
"""
Returns an arbitrary element of a free module.
EXAMPLES::
sage: V = VectorSpace(QQ,2)
sage: V._an_element_()
(1, 0)
sage: U = V.submodule([[1,0]])
sage: U._an_element_()
(1, 0)
sage: W = V.submodule([])
sage: W._an_element_()
(0, 0)
"""
try:
return self.gen(0)
except ValueError:
return self(0)
def some_elements(self):
r"""
Return some elements of this free module.
See :class:`TestSuite` for a typical use case.
OUTPUT:
An iterator.
EXAMPLES::
sage: F = FreeModule(ZZ, 2)
sage: tuple(F.some_elements())
((1, 0),
(1, 1),
(0, 1),
(-1, 2),
(-2, 3),
...
(-49, 50))
sage: F = FreeModule(QQ, 3)
sage: tuple(F.some_elements())
((1, 0, 0),
(1/2, 1/2, 1/2),
(1/2, -1/2, 2),
(-2, 0, 1),
(-1, 42, 2/3),
(-2/3, 3/2, -3/2),
(4/5, -4/5, 5/4),
...
(46/103823, -46/103823, 103823/46))
sage: F = FreeModule(SR, 2)
sage: tuple(F.some_elements())
((1, 0), (some_variable, some_variable))
"""
from itertools import islice
yield self.an_element()
yield self.base().an_element() * sum(self.gens())
some_elements_base = iter(self.base().some_elements())
n = self.degree()
while True:
L = list(islice(some_elements_base, n))
if len(L) != n:
return
try:
yield self(L)
except (TypeError, ValueError):
pass
def _element_constructor_(self, x, coerce=True, copy=True, check=True):
r"""
Create an element of this free module from ``x``.
The ``coerce`` and ``copy`` arguments are
passed on to the underlying element constructor. If
``check`` is ``True``, confirm that the
element specified by x does in fact lie in self.
.. note::
In the case of an inexact base ring (i.e. RDF), we don't
verify that the element is in the subspace, even when
``check=True``, to account for numerical instability
issues.
EXAMPLE::
sage: M = ZZ^4
sage: M([1,-1,0,1]) #indirect doctest
(1, -1, 0, 1)
sage: M(0)
(0, 0, 0, 0)
::
sage: N = M.submodule([[1,0,0,0], [0,1,1,0]])
sage: N([1,1,1,0])
(1, 1, 1, 0)
sage: N((3,-2,-2,0))
(3, -2, -2, 0)
sage: N((0,0,0,1))
Traceback (most recent call last):
...