CoCalc -- matrix_integer

GitHub Repository: sagemath/sagesmc
Path: blob/master/src/sage/matrix/matrix_integer_2x2.pyx
⁸⁸¹⁵ views
1
"""
2
Two by two matrices over the integers.
3
"""
4

5
include "sage/ext/interrupt.pxi"
6
include "sage/ext/stdsage.pxi"
7
from cpython.list cimport *
8
from cpython.number cimport *
9
from cpython.ref cimport *
10

11
from sage.rings.all import polygen, QQ,ZZ
12
from sage.rings.integer cimport Integer
13
from sage.structure.element cimport ModuleElement, Element
14
from sage.structure.mutability cimport Mutability
15

16
cimport matrix_dense
17
import matrix_dense
18

19
cimport matrix
20

21
from matrix_space import MatrixSpace
22
from sage.misc.lazy_attribute import lazy_attribute
23

24
class MatrixSpace_ZZ_2x2_class(MatrixSpace):
25
    """
26
    Return a space of 2x2 matrices over ZZ, whose elements are of
27
    type sage.matrix.matrix_integer_2x2.Matrix_integer_2x2 instead of
28
    sage.matrix.matrix_integer_dense.Matrix_integer_dense.
29

30
    NOTE: This class exists only for quickly creating and testing
31
    elements of this type. Once these become the default for 2x2
32
    matrices over ZZ, this class should be removed.
33

34
    EXAMPLES::
35

36
        sage: sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
37
        Space of 2x2 integer matrices
38

39
    By trac ticket #12290, it is a unique parent::
40

41
        sage: from sage.matrix.matrix_integer_2x2 import MatrixSpace_ZZ_2x2
42
        sage: MatrixSpace_ZZ_2x2() is MatrixSpace_ZZ_2x2()
43
        True
44
        sage: M = MatrixSpace_ZZ_2x2()
45
        sage: loads(dumps(M)) is M
46
        True
47

48
    """
49
    @staticmethod
50
    def __classcall__(cls):
51
        """
52
        EXAMPLES::
53

54
            sage: from sage.matrix.matrix_integer_2x2 import MatrixSpace_ZZ_2x2
55
            sage: MatrixSpace_ZZ_2x2() is MatrixSpace_ZZ_2x2()  # indirect doctest
56
            True
57

58
        """
59
        return super(MatrixSpace,cls).__classcall__(cls)
60

61
    def __init__(self):
62
        """
63
        EXAMPLES::
64

65
            sage: sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
66
            Space of 2x2 integer matrices
67
        """
68
        MatrixSpace.__init__(self, ZZ, 2, 2, False)
69

70
    def _repr_(self):
71
        """
72
        EXAMPLES::
73

74
            sage: sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
75
            Space of 2x2 integer matrices
76
        """
77
        return "Space of 2x2 integer matrices"
78

79
    def _get_matrix_class(self):
80
        """
81
        EXAMPLES::
82

83
            sage: A = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
84
            sage: A._get_matrix_class()
85
            <type 'sage.matrix.matrix_integer_2x2.Matrix_integer_2x2'>
86
        """
87
        return Matrix_integer_2x2
88

89
ZZ_2x2_parent = MatrixSpace_ZZ_2x2_class()
90
def MatrixSpace_ZZ_2x2():
91
    """
92
    Return the space of 2x2 integer matrices. (This function
93
    exists to maintain uniqueness of parents.)
94

95
    EXAMPLES::
96

97
        sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
98
        sage: M
99
        Space of 2x2 integer matrices
100
        sage: M is sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
101
        True
102
    """
103
    return ZZ_2x2_parent
104

105

106
cdef class Matrix_integer_2x2(matrix_dense.Matrix_dense):
107
    r"""
108
    The \class{Matrix_integer_2x2} class derives from
109
    \class{Matrix_dense}, and defines fast functionality for 2x2
110
    matrices over the integers.  Matrices are represented by four gmp
111
    integer fields: a, b, c, and d.
112

113
    EXAMPLES::
114

115
        sage: MS = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
116
        sage: m = MS([1,2,3,4]) ; m
117
        [1 2]
118
        [3 4]
119
        sage: TestSuite(m).run()
120

121
    We check that #13949 is fixed::
122

123
        sage: x = MS([1,2,3,4])
124
        sage: y = MS([4,5,6,7])
125
        sage: z = x * y
126
        sage: z.set_immutable()
127
    """
128
    ########################################################################
129
    # LEVEL 1 functionality
130
    # x * __cinit__
131
    # x * __init__
132
    # x * __dealloc__
133
    # x * set_unsafe
134
    # x * get_unsafe
135
    # x * def _pickle
136
    # x * def _unpickle
137
    ########################################################################
138

139
    def __cinit__(self, parent, entries,copy, coerce):
140
        mpz_init(self.a)
141
        mpz_init(self.b)
142
        mpz_init(self.c)
143
        mpz_init(self.d)
144
        self._entries = &self.a
145
        self._parent = parent
146
        self._base_ring = ZZ
147
        self._nrows = 2
148
        self._ncols = 2
149

150
    def __init__(self, parent, entries, copy, coerce):
151
        """
152
        EXAMPLES::
153

154
            sage: MS = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
155
            sage: MS()
156
            [0 0]
157
            [0 0]
158
            sage: MS(5)
159
            [5 0]
160
            [0 5]
161
            sage: MS([3,4,5,6])
162
            [3 4]
163
            [5 6]
164
            sage: MS([11,3])
165
            Traceback (most recent call last):
166
            ...
167
            TypeError: cannot construct an element of
168
            Space of 2x2 integer matrices from [11, 3]!
169
        """
170
        cdef Py_ssize_t i, n
171

172
        if entries is None:
173
            entries = 0
174

175
        if not isinstance(entries, list):
176
            try:
177
                x = ZZ(entries)
178
                is_list = 0
179
            except TypeError:
180
                if hasattr(entries, "list"):
181
                    entries = entries.list()
182
                    is_list = 1
183
                else:
184
                    try:
185
                        entries = list(entries)
186
                        is_list = 1
187
                    except TypeError:
188
                        raise TypeError("entries must be coercible to a list or the base ring")
189

190
        else:
191
            is_list = 1
192

193
        if is_list:
194

195
            if len(entries) != self._nrows * self._ncols:
196
                raise TypeError("entries has the wrong length")
197

198
            if coerce:
199
                mpz_set(self.a, (<Integer>ZZ(entries[0])).value)
200
                mpz_set(self.b, (<Integer>ZZ(entries[1])).value)
201
                mpz_set(self.c, (<Integer>ZZ(entries[2])).value)
202
                mpz_set(self.d, (<Integer>ZZ(entries[3])).value)
203
            else:
204
                mpz_set(self.a, (<Integer>entries[0]).value)
205
                mpz_set(self.b, (<Integer>entries[1]).value)
206
                mpz_set(self.c, (<Integer>entries[2]).value)
207
                mpz_set(self.d, (<Integer>entries[3]).value)
208

209
        else:
210

211
            mpz_set(self.a, (<Integer>x).value)
212
            mpz_set_si(self.b, 0)
213
            mpz_set_si(self.c, 0)
214
            mpz_set(self.d, (<Integer>x).value)
215

216
    def  __dealloc__(self):
217
        mpz_clear(self.a)
218
        mpz_clear(self.b)
219
        mpz_clear(self.c)
220
        mpz_clear(self.d)
221

222
    def testit(self):
223
        print "testing",self._base_ring
224

225
    cdef set_unsafe(self, Py_ssize_t i, Py_ssize_t j, value):
226
        mpz_set(self._entries[(i << 1) | j], (<Integer>value).value)
227

228
    cdef get_unsafe(self, Py_ssize_t i, Py_ssize_t j):
229
        cdef Integer z
230
        z = Integer.__new__(Integer)
231
        mpz_set(z.value, self._entries[(i << 1) | j])
232
        return z
233

234
    def _pickle(self):
235
        """
236
        EXAMPLES:
237
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
238
            sage: m = M([9,8,7,6])
239
            sage: m == loads(dumps(m))
240
            True
241
        """
242
        return self.list(), 0
243

244
    def _unpickle(self, data, int version):
245
        """
246
        EXAMPLES::
247

248
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
249
            sage: m = M(5)
250
            sage: m == loads(dumps(m))
251
            True
252
        """
253
        if version == 0:
254
            mpz_set(self.a, (<Integer>ZZ(data[0])).value)
255
            mpz_set(self.b, (<Integer>ZZ(data[1])).value)
256
            mpz_set(self.c, (<Integer>ZZ(data[2])).value)
257
            mpz_set(self.d, (<Integer>ZZ(data[3])).value)
258
        else:
259
            raise RuntimeError("unknown matrix version")
260

261
    def __richcmp__(matrix.Matrix self, right, int op):
262
        """
263
        EXAMPLES::
264

265
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
266
            sage: m = M([1,2,3,4])
267
            sage: n = M([-1,2,3,4])
268
            sage: m < n
269
            False
270
            sage: m > n
271
            True
272
            sage: m == m
273
            True
274
        """
275
        return self._richcmp(right, op)
276

277
    def __hash__(self):
278
        """
279
        Return a hash of self.
280

281
        EXAMPLES::
282

283
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
284
            sage: m = M([1,2,3,4])
285
            sage: m.set_immutable()
286
            sage: m.__hash__()
287
            8
288
        """
289
        return self._hash()
290

291
    def __iter__(self):
292
        """
293
        Return an iterator over the entries of self.
294

295
        EXAMPLES::
296

297
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
298
            sage: m = M([1,2,3,4])
299
            sage: m.__iter__()
300
            <listiterator object at ...>
301
        """
302
        return iter(self.list())
303

304
    cdef Matrix_integer_2x2 _new_c(self):
305
        cdef Matrix_integer_2x2 x
306
        x = <Matrix_integer_2x2> Matrix_integer_2x2.__new__(Matrix_integer_2x2, self._parent, None, False, False)
307
        x._parent = self._parent
308
        x._nrows = 2
309
        x._ncols = 2
310
        return x
311

312

313
    ########################################################################
314
    # LEVEL 2 functionality
315
    # x  * cdef _add_
316
    #    * cdef _mul_
317
    #    * cdef _cmp_c_impl
318
    # x  * __neg__
319
    # x  * __invert__
320
    # x  * __copy__
321
    # x  * _multiply_classical
322
    # x  * _list -- copy of the list of underlying elements
323
    #    * _dict -- copy of the sparse dictionary of underlying elements
324
    ########################################################################
325

326
    def __copy__(self):
327
        """
328
        Return a copy of self.
329

330
        EXAMPLES::
331

332
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
333
            sage: m = M([1,3,4,5])
334
            sage: n = copy(m)
335
            sage: n == m
336
            True
337
            sage: n is m
338
            False
339
            sage: m.is_mutable()
340
            True
341
            sage: n.is_mutable()
342
            True
343

344
        The following test against a bug fixed in trac ticket #12290::
345

346
            sage: n.base_ring()
347
            Integer Ring
348

349
        """
350
        cdef Matrix_integer_2x2 x
351
        x = self._new_c()
352
        mpz_set(x.a, self.a)
353
        mpz_set(x.b, self.b)
354
        mpz_set(x.c ,self.c)
355
        mpz_set(x.d, self.d)
356
        x._is_immutable = False
357
        x._base_ring = self._base_ring
358
        if self._subdivisions is not None:
359
            x.subdivide(*self.subdivisions())
360
        return x
361

362
    cpdef ModuleElement _add_(left, ModuleElement right):
363
        """
364
        EXAMPLES::
365

366
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
367
            sage: M([8,7,6,5]) + M([4,5,6,7])
368
            [12 12]
369
            [12 12]
370
        """
371
        cdef Matrix_integer_2x2 A
372
        A = left._new_c()
373
        mpz_add(A.a, left.a, (<Matrix_integer_2x2>right).a)
374
        mpz_add(A.b, left.b, (<Matrix_integer_2x2>right).b)
375
        mpz_add(A.c, left.c, (<Matrix_integer_2x2>right).c)
376
        mpz_add(A.d, left.d, (<Matrix_integer_2x2>right).d)
377
        return A
378

379
    cdef int _cmp_c_impl(left, Element right) except -2:
380
        """
381
        EXAMPLES::
382

383
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
384
            sage: m = M([4,3,7,9])
385
            sage: n = M([3,3,7,9])
386
            sage: m < n
387
            False
388
            sage: m > n
389
            True
390
            sage: m == m
391
            True
392
            sage: m == n
393
            False
394

395
        TEST:
396

397
        Check that :trac:`14688` is fixed::
398

399
            sage: from sage.matrix.matrix_integer_2x2 import MatrixSpace_ZZ_2x2
400
            sage: M2ZSpace = MatrixSpace_ZZ_2x2()
401
            sage: A = M2ZSpace([-5, -3, 7, 4])
402
            sage: B = M2ZSpace([1,0,-2,1])
403
            sage: A < B
404
            True
405
        """
406
        cdef int c = mpz_cmp(left.a, (<Matrix_integer_2x2>right).a) or \
407
                     mpz_cmp(left.b, (<Matrix_integer_2x2>right).b) or \
408
                     mpz_cmp(left.c, (<Matrix_integer_2x2>right).c) or \
409
                     mpz_cmp(left.d, (<Matrix_integer_2x2>right).d)
410
        if c < 0: return -1
411
        if c > 0: return 1
412
        return 0
413

414
    def __neg__(self):
415
        """
416
        Return the additive inverse of self.
417

418
        EXAMPLES::
419

420
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
421
            sage: m = M([1,-1,-1,1])
422
            sage: -m
423
            [-1  1]
424
            [ 1 -1]
425
        """
426
        cdef Matrix_integer_2x2 A
427
        A = self._new_c()
428
        mpz_neg(A.a, self.a)
429
        mpz_neg(A.b, self.b)
430
        mpz_neg(A.c, self.c)
431
        mpz_neg(A.d, self.d)
432
        return A
433

434
    def __invert__(self):
435
        """
436
        Return the inverse of self, as a 2x2 matrix over QQ.
437

438
        EXAMPLES::
439

440
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
441
            sage: m = M([2,0,0,2])
442
            sage: m^-1
443
            [1/2   0]
444
            [  0 1/2]
445
            sage: type(m^-1)
446
            <type 'sage.matrix.matrix_rational_dense.Matrix_rational_dense'>
447
        """
448
        MS = self._matrix_(QQ).parent()
449
        D = self.determinant()
450
        return MS([self.get_unsafe(1,1)/D, -self.get_unsafe(0,1)/D, -self.get_unsafe(1,0)/D, self.get_unsafe(0,0)/D], coerce=False, copy=False)
451

452
    def __invert__unit(self):
453
        """
454
        If self is a unit, i.e. if its determinant is 1 or -1, return
455
        the inverse of self as a 2x2 matrix over ZZ. If not, raise a
456
        ZeroDivisionError.
457

458
        EXAMPLES::
459

460
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
461
            sage: m = M([1,8,3,25])
462
            sage: m.__invert__unit()
463
            [25 -8]
464
            [-3  1]
465
            sage: type(m.__invert__unit())
466
            <type 'sage.matrix.matrix_integer_2x2.Matrix_integer_2x2'>
467
            sage: m^-1
468
            [25 -8]
469
            [-3  1]
470
            sage: type(m^-1)
471
            <type 'sage.matrix.matrix_rational_dense.Matrix_rational_dense'>
472
            sage: m.__invert__unit() == m^-1
473
            True
474
            sage: M([2,0,0,2]).__invert__unit()
475
            Traceback (most recent call last):
476
            ...
477
            ZeroDivisionError: Not a unit!
478
        """
479
        cdef Matrix_integer_2x2 A
480
        cdef Integer D
481
        D = self.determinant()
482
        if D.is_one():
483
            A = self._new_c()
484
            mpz_set(A.a, self.d)
485
            mpz_neg(A.b, self.b)
486
            mpz_neg(A.c, self.c)
487
            mpz_set(A.d, self.a)
488
            return A
489

490
        elif D.is_unit():
491
            A = self._new_c()
492
            mpz_neg(A.a, self.d)
493
            mpz_set(A.b, self.b)
494
            mpz_set(A.c, self.c)
495
            mpz_neg(A.d, self.a)
496
            return A
497

498
        else:
499
            raise ZeroDivisionError("Not a unit!")
500
    _invert_unit = __invert__unit
501

502
    def _multiply_classical(left, matrix.Matrix _right):
503
        """
504
        Multiply the matrices left and right using the classical $O(n^3)$
505
        algorithm.
506

507
        EXAMPLES::
508

509
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
510
            sage: m = M([9,7,6,4])
511
            sage: n = M([7,1,3,0])
512
            sage: m*n
513
            [84  9]
514
            [54  6]
515
            sage: m._multiply_classical(n)
516
            [84  9]
517
            [54  6]
518
        """
519
        cdef Matrix_integer_2x2 A, right
520
        cdef mpz_t tmp
521
        mpz_init(tmp)
522

523
        right  = _right
524
        A = left._new_c()
525

526
        mpz_mul(A.a, left.a, right.a)
527
        mpz_mul(tmp, left.b, right.c)
528
        mpz_add(A.a, A.a, tmp)
529

530
        mpz_mul(A.b, left.a, right.b)
531
        mpz_mul(tmp, left.b, right.d)
532
        mpz_add(A.b, A.b, tmp)
533

534
        mpz_mul(A.c, left.c, right.a)
535
        mpz_mul(tmp, left.d, right.c)
536
        mpz_add(A.c, A.c, tmp)
537

538
        mpz_mul(A.d, left.c, right.b)
539
        mpz_mul(tmp, left.d, right.d)
540
        mpz_add(A.d, A.d, tmp)
541

542
        mpz_clear(tmp)
543
        return A
544

545
    def _list(self):
546
        """
547
        EXAMPLES::
548

549
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
550
            sage: M([8,6,0,8])._list()
551
            [8, 6, 0, 8]
552
        """
553
        return [self.get_unsafe(0,0), self.get_unsafe(0,1),
554
                self.get_unsafe(1,0), self.get_unsafe(1,1)]
555

556
    ########################################################################
557
    # LEVEL 3 functionality (Optional)
558
    # x  * cdef _sub_
559
    # x  * __deepcopy__
560
    #    * Matrix windows -- only if you need strassen for that base
561
    #    * Other functions (list them here):
562
    # x  * determinant
563
    # x  * charpoly
564
    ########################################################################
565

566
    cpdef ModuleElement _sub_(left, ModuleElement right):
567
        """
568
        EXAMPLES::
569

570
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
571
            sage: M([3,4,5,6]) - M([1,2,3,4])
572
            [2 2]
573
            [2 2]
574
        """
575
        cdef Matrix_integer_2x2 A
576
        A = left._new_c()
577
        mpz_sub(A.a, left.a, (<Matrix_integer_2x2>right).a)
578
        mpz_sub(A.b, left.b, (<Matrix_integer_2x2>right).b)
579
        mpz_sub(A.c, left.c, (<Matrix_integer_2x2>right).c)
580
        mpz_sub(A.d, left.d, (<Matrix_integer_2x2>right).d)
581
        return A
582

583
    def determinant(self):
584
        """
585
        Return the determinant of self, which is just ad-bc.
586

587
        EXAMPLES::
588

589
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
590
            sage: M([9,0,8,7]).determinant()
591
            63
592
        """
593
        cdef Integer z
594
        cdef mpz_t tmp
595
        mpz_init(tmp)
596
        z = Integer.__new__(Integer)
597
        mpz_mul(z.value, self.a, self.d)
598
        mpz_mul(tmp, self.b, self.c)
599
        mpz_sub(z.value, z.value, tmp)
600
        mpz_clear(tmp)
601
        return z
602

603
    def trace(self):
604
        """
605
        Return the trace of self, which is just a+d.
606

607
        EXAMPLES::
608

609
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
610
            sage: M([9,0,8,7]).trace()
611
            16
612
        """
613
        cdef Integer z = PY_NEW(Integer)
614
        mpz_add(z.value, self._entries[0], self._entries[3])
615
        return z
616

617
    def charpoly(self, var='x'):
618
        """
619
        Return the charpoly of self as a polynomial in var. Since self
620
        is 2x2, this is just var^2 - self.trace() * var +
621
        self.determinant().
622

623
        EXAMPLES::
624

625
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
626
            sage: M([9,0,8,7]).charpoly()
627
            x^2 - 16*x + 63
628
            sage: M(range(4)).charpoly()
629
            x^2 - 3*x - 2
630
            sage: M(range(4)).charpoly('t')
631
            t^2 - 3*t - 2
632
        """
633
        t = polygen(ZZ,name=var)
634
        return t*t - t*self.trace() + self.determinant()
635

636
    def __deepcopy__(self, *args, **kwds):
637
        """
638
        EXAMPLES::
639

640
            sage: M = sage.matrix.matrix_integer_2x2.MatrixSpace_ZZ_2x2()
641
            sage: m = M([5,5,5,5])
642
            sage: n = deepcopy(m)
643
            sage: n == m
644
            True
645
            sage: n is m
646
            False
647
            sage: m[0,0] == n[0,0]
648
            True
649
            sage: m[0,0] is n[0,0]
650
            False
651
        """
652
        return self.__copy__()
653

654

655
#######################################################################
656

657
Product

Resources

Company
