Dense matrices over GF(2) using the M4RI library

AUTHOR: Martin Albrecht <malb@informatik.uni-bremen.de>

EXAMPLES:

sage: a = matrix(GF(2),3,range(9),sparse=False); a
[0 1 0]
[1 0 1]
[0 1 0]
sage: a.rank()
2
sage: type(a)
<class 'sage.matrix.matrix_mod2_dense.Matrix_mod2_dense'>
sage: a[0,0] = 1
sage: a.rank()
3
sage: parent(a)
Full MatrixSpace of 3 by 3 dense matrices over Finite Field of size 2

sage: a^2
[0 1 1]
[1 0 0]
[1 0 1]
sage: a+a
[0 0 0]
[0 0 0]
[0 0 0]

sage: b = a.new_matrix(2,3,range(6)); b
[0 1 0]
[1 0 1]

sage: a*b
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for *: 'Full MatrixSpace of 3 by 3 dense matrices over Finite Field of size 2' and 'Full MatrixSpace of 2 by 3 dense matrices over Finite Field of size 2'
sage: b*a
[1 0 1]
[1 0 0]

sage: TestSuite(a).run()
sage: TestSuite(b).run()

sage: a.echelonize(); a
[1 0 0]
[0 1 0]
[0 0 1]
sage: b.echelonize(); b
[1 0 1]
[0 1 0]

>>> from sage.all import *
>>> a = matrix(GF(Integer(2)),Integer(3),range(Integer(9)),sparse=False); a
[0 1 0]
[1 0 1]
[0 1 0]
>>> a.rank()
2
>>> type(a)
<class 'sage.matrix.matrix_mod2_dense.Matrix_mod2_dense'>
>>> a[Integer(0),Integer(0)] = Integer(1)
>>> a.rank()
3
>>> parent(a)
Full MatrixSpace of 3 by 3 dense matrices over Finite Field of size 2

>>> a**Integer(2)
[0 1 1]
[1 0 0]
[1 0 1]
>>> a+a
[0 0 0]
[0 0 0]
[0 0 0]

>>> b = a.new_matrix(Integer(2),Integer(3),range(Integer(6))); b
[0 1 0]
[1 0 1]

>>> a*b
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for *: 'Full MatrixSpace of 3 by 3 dense matrices over Finite Field of size 2' and 'Full MatrixSpace of 2 by 3 dense matrices over Finite Field of size 2'
>>> b*a
[1 0 1]
[1 0 0]

>>> TestSuite(a).run()
>>> TestSuite(b).run()

>>> a.echelonize(); a
[1 0 0]
[0 1 0]
[0 0 1]
>>> b.echelonize(); b
[1 0 1]
[0 1 0]

a = matrix(GF(2),3,range(9),sparse=False); a
a.rank()
type(a)
a[0,0] = 1
a.rank()
parent(a)
a^2
a+a
b = a.new_matrix(2,3,range(6)); b
a*b
b*a
TestSuite(a).run()
TestSuite(b).run()
a.echelonize(); a
b.echelonize(); b

Todo

  • make LinBox frontend and use it

    • charpoly ?

    • minpoly ?

  • make Matrix_modn_frontend and use it (?)

class sage.matrix.matrix_mod2_dense.Matrix_mod2_dense[source]

Bases: Matrix_dense

Dense matrix over GF(2).

augment(right, subdivide=False)[source]

Augments self with right.

EXAMPLES:

sage: MS = MatrixSpace(GF(2),3,3)
sage: A = MS([0, 1, 0, 1, 1, 0, 1, 1, 1]); A
[0 1 0]
[1 1 0]
[1 1 1]
sage: B = A.augment(MS(1)); B
[0 1 0 1 0 0]
[1 1 0 0 1 0]
[1 1 1 0 0 1]
sage: B.echelonize(); B
[1 0 0 1 1 0]
[0 1 0 1 0 0]
[0 0 1 0 1 1]
sage: C = B.matrix_from_columns([3,4,5]); C
[1 1 0]
[1 0 0]
[0 1 1]
sage: C == ~A
True
sage: C*A == MS(1)
True

>>> from sage.all import *
>>> MS = MatrixSpace(GF(Integer(2)),Integer(3),Integer(3))
>>> A = MS([Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(1), Integer(1)]); A
[0 1 0]
[1 1 0]
[1 1 1]
>>> B = A.augment(MS(Integer(1))); B
[0 1 0 1 0 0]
[1 1 0 0 1 0]
[1 1 1 0 0 1]
>>> B.echelonize(); B
[1 0 0 1 1 0]
[0 1 0 1 0 0]
[0 0 1 0 1 1]
>>> C = B.matrix_from_columns([Integer(3),Integer(4),Integer(5)]); C
[1 1 0]
[1 0 0]
[0 1 1]
>>> C == ~A
True
>>> C*A == MS(Integer(1))
True

MS = MatrixSpace(GF(2),3,3)
A = MS([0, 1, 0, 1, 1, 0, 1, 1, 1]); A
B = A.augment(MS(1)); B
B.echelonize(); B
C = B.matrix_from_columns([3,4,5]); C
C == ~A
C*A == MS(1)

A vector may be augmented to a matrix.

sage: A = matrix(GF(2), 3, 4, range(12))
sage: v = vector(GF(2), 3, range(3))
sage: A.augment(v)
[0 1 0 1 0]
[0 1 0 1 1]
[0 1 0 1 0]

>>> from sage.all import *
>>> A = matrix(GF(Integer(2)), Integer(3), Integer(4), range(Integer(12)))
>>> v = vector(GF(Integer(2)), Integer(3), range(Integer(3)))
>>> A.augment(v)
[0 1 0 1 0]
[0 1 0 1 1]
[0 1 0 1 0]

A = matrix(GF(2), 3, 4, range(12))
v = vector(GF(2), 3, range(3))
A.augment(v)

The subdivide option will add a natural subdivision between self and right. For more details about how subdivisions are managed when augmenting, see sage.matrix.matrix1.Matrix.augment().

sage: A = matrix(GF(2), 3, 5, range(15))
sage: B = matrix(GF(2), 3, 3, range(9))
sage: A.augment(B, subdivide=True)
[0 1 0 1 0|0 1 0]
[1 0 1 0 1|1 0 1]
[0 1 0 1 0|0 1 0]

>>> from sage.all import *
>>> A = matrix(GF(Integer(2)), Integer(3), Integer(5), range(Integer(15)))
>>> B = matrix(GF(Integer(2)), Integer(3), Integer(3), range(Integer(9)))
>>> A.augment(B, subdivide=True)
[0 1 0 1 0|0 1 0]
[1 0 1 0 1|1 0 1]
[0 1 0 1 0|0 1 0]

A = matrix(GF(2), 3, 5, range(15))
B = matrix(GF(2), 3, 3, range(9))
A.augment(B, subdivide=True)
columns(copy=True)[source]

Return list of the columns of self.

INPUT:

  • copy – (default: True) if True, return a copy so you can modify it safely

EXAMPLES:

An example with a small 3x3 matrix:

sage: M2 = Matrix(GF(2), [[1, 0, 0], [0, 1, 0], [0, 1, 1]])
sage: M2.columns()
[(1, 0, 0), (0, 1, 1), (0, 0, 1)]

>>> from sage.all import *
>>> M2 = Matrix(GF(Integer(2)), [[Integer(1), Integer(0), Integer(0)], [Integer(0), Integer(1), Integer(0)], [Integer(0), Integer(1), Integer(1)]])
>>> M2.columns()
[(1, 0, 0), (0, 1, 1), (0, 0, 1)]

M2 = Matrix(GF(2), [[1, 0, 0], [0, 1, 0], [0, 1, 1]])
M2.columns()
density(approx=False)[source]

Return the density of this matrix.

By density we understand the ratio of the number of nonzero positions and the self.nrows() * self.ncols(), i.e. the number of possible nonzero positions.

INPUT:

  • approx – return floating point approximation (default: False)

EXAMPLES:

sage: A = random_matrix(GF(2), 1000, 1000)
sage: d = A.density()
sage: float(d) == A.density(approx=True)
True
sage: len(A.nonzero_positions())/1000^2 == d
True

sage: total = 1.0
sage: density_sum = A.density()
sage: while abs(density_sum/total - 0.5) > 0.001:
....:     A = random_matrix(GF(2), 1000, 1000)
....:     total += 1
....:     density_sum += A.density()

>>> from sage.all import *
>>> A = random_matrix(GF(Integer(2)), Integer(1000), Integer(1000))
>>> d = A.density()
>>> float(d) == A.density(approx=True)
True
>>> len(A.nonzero_positions())/Integer(1000)**Integer(2) == d
True

>>> total = RealNumber('1.0')
>>> density_sum = A.density()
>>> while abs(density_sum/total - RealNumber('0.5')) > RealNumber('0.001'):
...     A = random_matrix(GF(Integer(2)), Integer(1000), Integer(1000))
...     total += Integer(1)
...     density_sum += A.density()

A = random_matrix(GF(2), 1000, 1000)
d = A.density()
float(d) == A.density(approx=True)
len(A.nonzero_positions())/1000^2 == d
total = 1.0
density_sum = A.density()
while abs(density_sum/total - 0.5) > 0.001:
    A = random_matrix(GF(2), 1000, 1000)
    total += 1
    density_sum += A.density()
determinant()[source]

Return the determinant of this matrix over GF(2).

EXAMPLES:

sage: matrix(GF(2),2,[1,1,0,1]).determinant()
1
sage: matrix(GF(2),2,[1,1,1,1]).determinant()
0

>>> from sage.all import *
>>> matrix(GF(Integer(2)),Integer(2),[Integer(1),Integer(1),Integer(0),Integer(1)]).determinant()
1
>>> matrix(GF(Integer(2)),Integer(2),[Integer(1),Integer(1),Integer(1),Integer(1)]).determinant()
0

matrix(GF(2),2,[1,1,0,1]).determinant()
matrix(GF(2),2,[1,1,1,1]).determinant()
echelonize(algorithm='heuristic', cutoff=0, reduced=True, **kwds)[source]

Puts self in (reduced) row echelon form.

INPUT:

  • self – a mutable matrix

  • algorithm – string; one of

    • 'heuristic' – uses M4RI and PLUQ (default)

    • 'm4ri' – uses M4RI

    • 'pluq' – uses PLUQ factorization

    • 'classical' – uses classical Gaussian elimination

  • k – the parameter ‘k’ of the M4RI algorithm. It MUST be between 1 and 16 (inclusive). If it is not specified it will be calculated as 3/4 * log_2( min(nrows, ncols) ) as suggested in the M4RI paper.

  • reduced – return reduced row echelon form (default: True)

EXAMPLES:

sage: A = random_matrix(GF(2), 10, 10)
sage: B = A.__copy__(); B.echelonize() # fastest
sage: C = A.__copy__(); C.echelonize(k=2) # force k
sage: E = A.__copy__(); E.echelonize(algorithm='classical') # force Gaussian elimination
sage: B == C == E
True

>>> from sage.all import *
>>> A = random_matrix(GF(Integer(2)), Integer(10), Integer(10))
>>> B = A.__copy__(); B.echelonize() # fastest
>>> C = A.__copy__(); C.echelonize(k=Integer(2)) # force k
>>> E = A.__copy__(); E.echelonize(algorithm='classical') # force Gaussian elimination
>>> B == C == E
True

A = random_matrix(GF(2), 10, 10)
B = A.__copy__(); B.echelonize() # fastest
C = A.__copy__(); C.echelonize(k=2) # force k
E = A.__copy__(); E.echelonize(algorithm='classical') # force Gaussian elimination
B == C == E

ALGORITHM:

Uses M4RI library

REFERENCES:

randomize(density=1, nonzero=False)[source]

Randomize density proportion of the entries of this matrix, leaving the rest unchanged.

INPUT:

  • density – float; proportion (roughly) to be considered for changes

  • nonzero – boolean (default: False); whether the new entries are forced to be nonzero

OUTPUT: None, the matrix is modified in-space

EXAMPLES:

sage: A = matrix(GF(2), 5, 5, 0)
sage: A.randomize(0.5)
sage: A.density() < 0.5
True
sage: expected = 0.5
sage: A = matrix(GF(2), 5, 5, 0)
sage: A.randomize()
sage: density_sum = float(A.density())
sage: total = 1
sage: while abs(density_sum/total - expected) > 0.001:
....:     A = matrix(GF(2), 5, 5, 0)
....:     A.randomize()
....:     density_sum += float(A.density())
....:     total += 1

>>> from sage.all import *
>>> A = matrix(GF(Integer(2)), Integer(5), Integer(5), Integer(0))
>>> A.randomize(RealNumber('0.5'))
>>> A.density() < RealNumber('0.5')
True
>>> expected = RealNumber('0.5')
>>> A = matrix(GF(Integer(2)), Integer(5), Integer(5), Integer(0))
>>> A.randomize()
>>> density_sum = float(A.density())
>>> total = Integer(1)
>>> while abs(density_sum/total - expected) > RealNumber('0.001'):
...     A = matrix(GF(Integer(2)), Integer(5), Integer(5), Integer(0))
...     A.randomize()
...     density_sum += float(A.density())
...     total += Integer(1)

A = matrix(GF(2), 5, 5, 0)
A.randomize(0.5)
A.density() < 0.5
expected = 0.5
A = matrix(GF(2), 5, 5, 0)
A.randomize()
density_sum = float(A.density())
total = 1
while abs(density_sum/total - expected) > 0.001:
    A = matrix(GF(2), 5, 5, 0)
    A.randomize()
    density_sum += float(A.density())
    total += 1
rank(algorithm='ple')[source]

Return the rank of this matrix.

On average ‘ple’ should be faster than ‘m4ri’ and hence it is the default choice. However, for small - i.e. quite few thousand rows & columns - and sparse matrices ‘m4ri’ might be a better choice.

INPUT:

  • algorithm – either “ple” or “m4ri”

EXAMPLES:

sage: while random_matrix(GF(2), 1000, 1000).rank() != 999:
....:     pass

sage: A = matrix(GF(2),10, 0)
sage: A.rank()
0

>>> from sage.all import *
>>> while random_matrix(GF(Integer(2)), Integer(1000), Integer(1000)).rank() != Integer(999):
...     pass

>>> A = matrix(GF(Integer(2)),Integer(10), Integer(0))
>>> A.rank()
0

while random_matrix(GF(2), 1000, 1000).rank() != 999:
    pass
A = matrix(GF(2),10, 0)
A.rank()
row(i, from_list=False)[source]

Return the i-th row of this matrix as a vector.

This row is a dense vector if and only if the matrix is a dense matrix.

INPUT:

  • i – integer

  • from_list – boolean (default: False); if True, returns the i-th element of self.rows() (see rows()), which may be faster, but requires building a list of all rows the first time it is called after an entry of the matrix is changed.

EXAMPLES:

sage: l = [GF(2).random_element() for _ in range(100)]
sage: A = matrix(GF(2), 10, 10 , l)
sage: list(A.row(0)) == l[:10]
True
sage: list(A.row(-1)) == l[-10:]
True

sage: list(A.row(2, from_list=True)) == l[20:30]
True

sage: A = Matrix(GF(2),1,0)
sage: A.row(0)
()

>>> from sage.all import *
>>> l = [GF(Integer(2)).random_element() for _ in range(Integer(100))]
>>> A = matrix(GF(Integer(2)), Integer(10), Integer(10) , l)
>>> list(A.row(Integer(0))) == l[:Integer(10)]
True
>>> list(A.row(-Integer(1))) == l[-Integer(10):]
True

>>> list(A.row(Integer(2), from_list=True)) == l[Integer(20):Integer(30)]
True

>>> A = Matrix(GF(Integer(2)),Integer(1),Integer(0))
>>> A.row(Integer(0))
()

l = [GF(2).random_element() for _ in range(100)]
A = matrix(GF(2), 10, 10 , l)
list(A.row(0)) == l[:10]
list(A.row(-1)) == l[-10:]
list(A.row(2, from_list=True)) == l[20:30]
A = Matrix(GF(2),1,0)
A.row(0)
str(rep_mapping=None, zero=None, plus_one=None, minus_one=None, unicode=False, shape=None, character_art=False, left_border=None, right_border=None, top_border=None, bottom_border=None)[source]

Return a nice string representation of the matrix.

INPUT:

  • rep_mapping – dictionary or callable used to override the usual representation of elements. For a dictionary, keys should be elements of the base ring and values the desired string representation.

  • zero – string (default: None); if not None use the value of zero as the representation of the zero element.

  • plus_one – string (default: None); if not None use the value of plus_one as the representation of the one element.

  • minus_one – ignored. Only for compatibility with generic matrices.

  • unicode – boolean (default: False); whether to use Unicode symbols instead of ASCII symbols for brackets and subdivision lines

  • shape – one of 'square' or 'round' (default: None). Switches between round and square brackets. The default depends on the setting of the unicode keyword argument. For Unicode symbols, the default is round brackets in accordance with the TeX rendering, while the ASCII rendering defaults to square brackets.

  • character_art – boolean (default: False); if True, the result will be of type AsciiArt or UnicodeArt which support line breaking of wide matrices that exceed the window width

  • left_border, right_border – sequence (default: None); if not None, call str() on the elements and use the results as labels for the rows of the matrix. The labels appear outside of the parentheses.

  • top_border, bottom_border – sequence (default: None); if not None, call str() on the elements and use the results as labels for the columns of the matrix. The labels appear outside of the parentheses.

EXAMPLES:

sage: B = matrix(GF(2), 3, 3, [0, 1, 0, 0, 1, 1, 0, 0, 0])
sage: B  # indirect doctest
[0 1 0]
[0 1 1]
[0 0 0]
sage: block_matrix([[B, 1], [0, B]])
[0 1 0|1 0 0]
[0 1 1|0 1 0]
[0 0 0|0 0 1]
[-----+-----]
[0 0 0|0 1 0]
[0 0 0|0 1 1]
[0 0 0|0 0 0]
sage: B.str(zero='.')
'[. 1 .]\n[. 1 1]\n[. . .]'

sage: M = matrix.identity(GF(2), 3)
sage: M.subdivide(None, 2)
sage: print(M.str(unicode=True, shape='square'))
⎡1 0│0⎤
⎢0 1│0⎥
⎣0 0│1⎦
sage: print(unicode_art(M))  # indirect doctest
⎛1 0│0⎞
⎜0 1│0⎟
⎝0 0│1⎠

>>> from sage.all import *
>>> B = matrix(GF(Integer(2)), Integer(3), Integer(3), [Integer(0), Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)])
>>> B  # indirect doctest
[0 1 0]
[0 1 1]
[0 0 0]
>>> block_matrix([[B, Integer(1)], [Integer(0), B]])
[0 1 0|1 0 0]
[0 1 1|0 1 0]
[0 0 0|0 0 1]
[-----+-----]
[0 0 0|0 1 0]
[0 0 0|0 1 1]
[0 0 0|0 0 0]
>>> B.str(zero='.')
'[. 1 .]\n[. 1 1]\n[. . .]'

>>> M = matrix.identity(GF(Integer(2)), Integer(3))
>>> M.subdivide(None, Integer(2))
>>> print(M.str(unicode=True, shape='square'))
⎡1 0│0⎤
⎢0 1│0⎥
⎣0 0│1⎦
>>> print(unicode_art(M))  # indirect doctest
⎛1 0│0⎞
⎜0 1│0⎟
⎝0 0│1⎠

B = matrix(GF(2), 3, 3, [0, 1, 0, 0, 1, 1, 0, 0, 0])
B  # indirect doctest
block_matrix([[B, 1], [0, B]])
B.str(zero='.')
M = matrix.identity(GF(2), 3)
M.subdivide(None, 2)
print(M.str(unicode=True, shape='square'))
print(unicode_art(M))  # indirect doctest
submatrix(row=0, col=0, nrows=-1, ncols=-1)[source]

Return submatrix from the index row, col (inclusive) with dimension nrows x ncols.

INPUT:

  • row – index of start row

  • col – index of start column

  • nrows – number of rows of submatrix

  • ncols – number of columns of submatrix

EXAMPLES:

sage: A = random_matrix(GF(2),200,200)
sage: A[0:2,0:2] == A.submatrix(0,0,2,2)
True
sage: A[0:100,0:100] == A.submatrix(0,0,100,100)
True
sage: A == A.submatrix(0,0,200,200)
True

sage: A[1:3,1:3] == A.submatrix(1,1,2,2)
True
sage: A[1:100,1:100] == A.submatrix(1,1,99,99)
True
sage: A[1:200,1:200] == A.submatrix(1,1,199,199)
True

>>> from sage.all import *
>>> A = random_matrix(GF(Integer(2)),Integer(200),Integer(200))
>>> A[Integer(0):Integer(2),Integer(0):Integer(2)] == A.submatrix(Integer(0),Integer(0),Integer(2),Integer(2))
True
>>> A[Integer(0):Integer(100),Integer(0):Integer(100)] == A.submatrix(Integer(0),Integer(0),Integer(100),Integer(100))
True
>>> A == A.submatrix(Integer(0),Integer(0),Integer(200),Integer(200))
True

>>> A[Integer(1):Integer(3),Integer(1):Integer(3)] == A.submatrix(Integer(1),Integer(1),Integer(2),Integer(2))
True
>>> A[Integer(1):Integer(100),Integer(1):Integer(100)] == A.submatrix(Integer(1),Integer(1),Integer(99),Integer(99))
True
>>> A[Integer(1):Integer(200),Integer(1):Integer(200)] == A.submatrix(Integer(1),Integer(1),Integer(199),Integer(199))
True

A = random_matrix(GF(2),200,200)
A[0:2,0:2] == A.submatrix(0,0,2,2)
A[0:100,0:100] == A.submatrix(0,0,100,100)
A == A.submatrix(0,0,200,200)
A[1:3,1:3] == A.submatrix(1,1,2,2)
A[1:100,1:100] == A.submatrix(1,1,99,99)
A[1:200,1:200] == A.submatrix(1,1,199,199)

TESTS for handling of default arguments (Issue #18761):

sage: A.submatrix(17,15) == A.submatrix(17,15,183,185)
True
sage: A.submatrix(row=100,col=37,nrows=1,ncols=3) == A.submatrix(100,37,1,3)
True

>>> from sage.all import *
>>> A.submatrix(Integer(17),Integer(15)) == A.submatrix(Integer(17),Integer(15),Integer(183),Integer(185))
True
>>> A.submatrix(row=Integer(100),col=Integer(37),nrows=Integer(1),ncols=Integer(3)) == A.submatrix(Integer(100),Integer(37),Integer(1),Integer(3))
True

A.submatrix(17,15) == A.submatrix(17,15,183,185)
A.submatrix(row=100,col=37,nrows=1,ncols=3) == A.submatrix(100,37,1,3)
transpose()[source]

Return transpose of self and leaves self untouched.

EXAMPLES:

sage: A = Matrix(GF(2),3,5,[1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0])
sage: A
[1 0 1 0 0]
[0 1 1 0 0]
[1 1 0 1 0]
sage: B = A.transpose(); B
[1 0 1]
[0 1 1]
[1 1 0]
[0 0 1]
[0 0 0]
sage: B.transpose() == A
True

>>> from sage.all import *
>>> A = Matrix(GF(Integer(2)),Integer(3),Integer(5),[Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0)])
>>> A
[1 0 1 0 0]
[0 1 1 0 0]
[1 1 0 1 0]
>>> B = A.transpose(); B
[1 0 1]
[0 1 1]
[1 1 0]
[0 0 1]
[0 0 0]
>>> B.transpose() == A
True

A = Matrix(GF(2),3,5,[1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0])
A
B = A.transpose(); B
B.transpose() == A

.T is a convenient shortcut for the transpose:

sage: A.T
[1 0 1]
[0 1 1]
[1 1 0]
[0 0 1]
[0 0 0]

>>> from sage.all import *
>>> A.T
[1 0 1]
[0 1 1]
[1 1 0]
[0 0 1]
[0 0 0]

A.T
sage.matrix.matrix_mod2_dense.from_png(filename)[source]

Return a dense matrix over GF(2) from a 1-bit PNG image read from filename. No attempt is made to verify that the filename string actually points to a PNG image.

INPUT:

  • filename – string

EXAMPLES:

sage: from sage.matrix.matrix_mod2_dense import from_png, to_png
sage: A = random_matrix(GF(2),10,10)
sage: fn = tmp_filename()
sage: to_png(A, fn)
sage: B = from_png(fn)
sage: A == B
True

>>> from sage.all import *
>>> from sage.matrix.matrix_mod2_dense import from_png, to_png
>>> A = random_matrix(GF(Integer(2)),Integer(10),Integer(10))
>>> fn = tmp_filename()
>>> to_png(A, fn)
>>> B = from_png(fn)
>>> A == B
True

from sage.matrix.matrix_mod2_dense import from_png, to_png
A = random_matrix(GF(2),10,10)
fn = tmp_filename()
to_png(A, fn)
B = from_png(fn)
A == B
sage.matrix.matrix_mod2_dense.parity(a)[source]

Return the parity of the number of bits in a.

EXAMPLES:

sage: from sage.matrix.matrix_mod2_dense import parity
sage: parity(1)
1
sage: parity(3)
0
sage: parity(0x10000101011)
1

>>> from sage.all import *
>>> from sage.matrix.matrix_mod2_dense import parity
>>> parity(Integer(1))
1
>>> parity(Integer(3))
0
>>> parity(Integer(0x10000101011))
1

from sage.matrix.matrix_mod2_dense import parity
parity(1)
parity(3)
parity(0x10000101011)
sage.matrix.matrix_mod2_dense.ple(A, algorithm='standard', param=0)[source]

Return PLE factorization of A.

INPUT:

  • A – matrix

  • algorithm – string; one of

    • 'standard' asymptotically fast (default)

    • 'russian' M4RI inspired

    • 'naive' naive cubic

  • param – either k for ‘mmpf’ is chosen or matrix multiplication cutoff for ‘standard’ (default: 0)

EXAMPLES:

sage: from sage.matrix.matrix_mod2_dense import ple

sage: A = matrix(GF(2), 4, 4, [0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0])
sage: A
[0 1 0 1]
[0 1 1 1]
[0 0 0 1]
[0 1 1 0]

sage: LU, P, Q = ple(A)
sage: LU
[1 0 0 1]
[1 1 0 0]
[0 0 1 0]
[1 1 1 0]

sage: P
[0, 1, 2, 3]

sage: Q
[1, 2, 3, 3]

sage: A = random_matrix(GF(2),1000,1000)
sage: ple(A) == ple(A,'russian') == ple(A,'naive')
True

>>> from sage.all import *
>>> from sage.matrix.matrix_mod2_dense import ple

>>> A = matrix(GF(Integer(2)), Integer(4), Integer(4), [Integer(0), Integer(1), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(0)])
>>> A
[0 1 0 1]
[0 1 1 1]
[0 0 0 1]
[0 1 1 0]

>>> LU, P, Q = ple(A)
>>> LU
[1 0 0 1]
[1 1 0 0]
[0 0 1 0]
[1 1 1 0]

>>> P
[0, 1, 2, 3]

>>> Q
[1, 2, 3, 3]

>>> A = random_matrix(GF(Integer(2)),Integer(1000),Integer(1000))
>>> ple(A) == ple(A,'russian') == ple(A,'naive')
True

from sage.matrix.matrix_mod2_dense import ple
A = matrix(GF(2), 4, 4, [0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0])
A
LU, P, Q = ple(A)
LU
P
Q
A = random_matrix(GF(2),1000,1000)
ple(A) == ple(A,'russian') == ple(A,'naive')
sage.matrix.matrix_mod2_dense.pluq(A, algorithm='standard', param=0)[source]

Return PLUQ factorization of A.

INPUT:

  • A – matrix

  • algorithm – string; one of

    • 'standard' asymptotically fast (default)

    • 'mmpf' M4RI inspired

    • 'naive' naive cubic

  • param – either k for ‘mmpf’ is chosen or matrix multiplication cutoff for 'standard' (default: 0)

EXAMPLES:

sage: from sage.matrix.matrix_mod2_dense import pluq
sage: A = matrix(GF(2), 4, 4, [0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0])
sage: A
[0 1 0 1]
[0 1 1 1]
[0 0 0 1]
[0 1 1 0]
sage: LU, P, Q = pluq(A)
sage: LU
[1 0 1 0]
[1 1 0 0]
[0 0 1 0]
[1 1 1 0]

sage: P
[0, 1, 2, 3]

sage: Q
[1, 2, 3, 3]

>>> from sage.all import *
>>> from sage.matrix.matrix_mod2_dense import pluq
>>> A = matrix(GF(Integer(2)), Integer(4), Integer(4), [Integer(0), Integer(1), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(0)])
>>> A
[0 1 0 1]
[0 1 1 1]
[0 0 0 1]
[0 1 1 0]
>>> LU, P, Q = pluq(A)
>>> LU
[1 0 1 0]
[1 1 0 0]
[0 0 1 0]
[1 1 1 0]

>>> P
[0, 1, 2, 3]

>>> Q
[1, 2, 3, 3]

from sage.matrix.matrix_mod2_dense import pluq
A = matrix(GF(2), 4, 4, [0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0])
A
LU, P, Q = pluq(A)
LU
P
Q
sage.matrix.matrix_mod2_dense.to_png(A, filename)[source]

Save the matrix A to filename as a 1-bit PNG image.

INPUT:

  • A – a matrix over GF(2)

  • filename – string for a file in a writable position

EXAMPLES:

sage: from sage.matrix.matrix_mod2_dense import from_png, to_png
sage: A = random_matrix(GF(2),10,10)
sage: fn = tmp_filename()
sage: to_png(A, fn)
sage: B = from_png(fn)
sage: A == B
True

>>> from sage.all import *
>>> from sage.matrix.matrix_mod2_dense import from_png, to_png
>>> A = random_matrix(GF(Integer(2)),Integer(10),Integer(10))
>>> fn = tmp_filename()
>>> to_png(A, fn)
>>> B = from_png(fn)
>>> A == B
True

from sage.matrix.matrix_mod2_dense import from_png, to_png
A = random_matrix(GF(2),10,10)
fn = tmp_filename()
to_png(A, fn)
B = from_png(fn)
A == B
sage.matrix.matrix_mod2_dense.unpickle_matrix_mod2_dense_v2(r, c, data, size, immutable=False)[source]

Deserialize a matrix encoded in the string s.

INPUT:

  • r – number of rows of matrix

  • c – number of columns of matrix

  • s – string

  • size – length of the string s

  • immutable – boolean (default: False); whether the matrix is immutable or not

EXAMPLES:

sage: A = random_matrix(GF(2),100,101)
sage: _, (r,c,s,s2,i) = A.__reduce__()
sage: from sage.matrix.matrix_mod2_dense import unpickle_matrix_mod2_dense_v2
sage: unpickle_matrix_mod2_dense_v2(r,c,s,s2,i) == A
True
sage: loads(dumps(A)) == A
True

>>> from sage.all import *
>>> A = random_matrix(GF(Integer(2)),Integer(100),Integer(101))
>>> _, (r,c,s,s2,i) = A.__reduce__()
>>> from sage.matrix.matrix_mod2_dense import unpickle_matrix_mod2_dense_v2
>>> unpickle_matrix_mod2_dense_v2(r,c,s,s2,i) == A
True
>>> loads(dumps(A)) == A
True

A = random_matrix(GF(2),100,101)
_, (r,c,s,s2,i) = A.__reduce__()
from sage.matrix.matrix_mod2_dense import unpickle_matrix_mod2_dense_v2
unpickle_matrix_mod2_dense_v2(r,c,s,s2,i) == A
loads(dumps(A)) == A