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)
<type '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]
TESTS:
sage: FF = FiniteField(2)
sage: V = VectorSpace(FF,2)
sage: v = V([0,1]); v
(0, 1)
sage: W = V.subspace([v])
sage: W
Vector space of degree 2 and dimension 1 over Finite Field of size 2
Basis matrix:
[0 1]
sage: v in W
True
sage: M = Matrix(GF(2), [[1,1,0],[0,1,0]])
sage: M.row_space()
Vector space of degree 3 and dimension 2 over Finite Field of size 2
Basis matrix:
[1 0 0]
[0 1 0]
sage: M = Matrix(GF(2), [[1,1,0],[0,0,1]])
sage: M.row_space()
Vector space of degree 3 and dimension 2 over Finite Field of size 2
Basis matrix:
[1 1 0]
[0 0 1]
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
¶ Bases:
sage.matrix.matrix_dense.Matrix_dense
Dense matrix over GF(2).
-
augment
(right, subdivide=False)¶ Augments
self
withright
.EXAMPLE:
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
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]
The
subdivide
option will add a natural subdivision betweenself
andright
. For more details about how subdivisions are managed when augmenting, seesage.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]
TESTS:
sage: A = random_matrix(GF(2),2,3) sage: B = random_matrix(GF(2),2,0) sage: A.augment(B) [0 1 0] [0 1 1] sage: B.augment(A) [0 1 0] [0 1 1] sage: M = Matrix(GF(2), 0, 0, 0) sage: N = Matrix(GF(2), 0, 19, 0) sage: W = M.augment(N) sage: W.ncols() 19 sage: M = Matrix(GF(2), 0, 1, 0) sage: N = Matrix(GF(2), 0, 1, 0) sage: M.augment(N) []
Check that trac ticket #19165 is solved:
sage: m = matrix(GF(2), 2, range(4)) sage: m.augment(matrix(GF(2), 2, range(4), sparse=True)) [0 1 0 1] [0 1 0 1] sage: m.augment(1) Traceback (most recent call last): ... TypeError: right must either be a matrix or a vector. Not <type 'sage.rings.integer.Integer'>
-
density
(approx=False)¶ Return the density of this matrix.
By density we understand the ration 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)
EXAMPLE:
sage: A = random_matrix(GF(2),1000,1000) sage: d = A.density(); d 62483/125000 sage: float(d) 0.499864 sage: A.density(approx=True) 0.499864000... sage: float(len(A.nonzero_positions())/1000^2) 0.499864
-
determinant
()¶ 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
-
echelonize
(algorithm='heuristic', cutoff=0, reduced=True, **kwds)¶ Puts self in (reduced) row echelon form.
INPUT:
self – a mutable matrix
algorithm
- ‘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)
EXAMPLE:
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
TESTS:
sage: VF2 = VectorSpace(GF(2),2) sage: WF2 = VF2.submodule([VF2([1,1])]) sage: WF2 Vector space of degree 2 and dimension 1 over Finite Field of size 2 Basis matrix: [1 1] sage: A2 = matrix(GF(2),2,[1,0,0,1]) sage: A2.kernel() Vector space of degree 2 and dimension 0 over Finite Field of size 2 Basis matrix: []
ALGORITHM:
Uses M4RI library
REFERENCES:
[Bard06] G. Bard. ‘Accelerating Cryptanalysis with the Method of Four Russians’. Cryptography E-Print Archive (http://eprint.iacr.org/2006/251.pdf), 2006.
-
randomize
(density=1, nonzero=False)¶ Randomize
density
proportion of the entries of this matrix, leaving the rest unchanged.INPUT:
density
- float; proportion (roughly) to be considered for changesnonzero
- Bool (default:False
); whether the new entries are forced to be non-zero
OUTPUT:
- None, the matrix is modified in-space
EXAMPLES:
sage: A = matrix(GF(2), 5, 5, 0) sage: A.randomize(0.5); A [0 0 0 1 1] [0 1 0 0 1] [1 0 0 0 0] [0 1 0 0 0] [0 0 0 1 0] sage: A.randomize(); A [0 0 1 1 0] [1 1 0 0 1] [1 1 1 1 0] [1 1 1 1 1] [0 0 1 1 0]
TESTS:
With the libc random number generator random(), we had problems where the ranks of all of these matrices would be the same (and they would all be far too low). This verifies that the problem is gone, with Mersenne Twister:
sage: MS2 = MatrixSpace(GF(2), 1000) sage: [MS2.random_element().rank() for i in range(5)] [999, 998, 1000, 999, 999]
Testing corner case:
sage: A = random_matrix(GF(2),3,0) sage: A []
-
rank
(algorithm='ple')¶ 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”
EXAMPLE:
sage: A = random_matrix(GF(2), 1000, 1000) sage: A.rank() 999 sage: A = matrix(GF(2),10, 0) sage: A.rank() 0
-
row
(i, from_list=False)¶ 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
- integerfrom_list
- bool (default:False
); ifTrue
, returns thei
‘th element ofself.rows()
(seerows()
), 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: A = random_matrix(GF(2),10,10); A [0 1 0 1 1 0 0 0 1 1] [0 1 1 1 0 1 1 0 0 1] [0 0 0 1 0 1 0 0 1 0] [0 1 1 0 0 1 0 1 1 0] [0 0 0 1 1 1 1 0 1 1] [0 0 1 1 1 1 0 0 0 0] [1 1 1 1 0 1 0 1 1 0] [0 0 0 1 1 0 0 0 1 1] [1 0 0 0 1 1 1 0 1 1] [1 0 0 1 1 0 1 0 0 0] sage: A.row(0) (0, 1, 0, 1, 1, 0, 0, 0, 1, 1) sage: A.row(-1) (1, 0, 0, 1, 1, 0, 1, 0, 0, 0) sage: A.row(2,from_list=True) (0, 0, 0, 1, 0, 1, 0, 0, 1, 0) sage: A = Matrix(GF(2),1,0) sage: A.row(0) ()
-
str
(rep_mapping=None, zero=None, plus_one=None, minus_one=None)¶ Return a nice string representation of the matrix.
INPUT:
rep_mapping
- a 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 notNone
use the value ofzero
as the representation of the zero element.plus_one
- string (default:None
); if notNone
use the value ofplus_one
as the representation of the one element.minus_one
- Ignored. Only for compatibility with generic matrices.
EXAMPLE:
sage: B = random_matrix(GF(2),3,3) 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[. . .]'
-
submatrix
(row=0, col=0, nrows=-1, ncols=-1)¶ 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
TESTS for handling of default arguments (trac ticket #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
-
transpose
()¶ Returns transpose of self and leaves self untouched.
EXAMPLE:
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
.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]
TESTS:
sage: A = random_matrix(GF(2),0,40) sage: A.transpose() 40 x 0 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries) sage: A = Matrix(GF(2), [1,0]) sage: B = A.transpose() sage: A[0,0] = 0 sage: B[0,0] 1
-
-
sage.matrix.matrix_mod2_dense.
free_m4ri
()¶ Free global Gray code tables.
-
sage.matrix.matrix_mod2_dense.
from_png
(filename)¶ Returns 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 – a string
EXAMPLE:
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
-
sage.matrix.matrix_mod2_dense.
parity
(a)¶ Returns the parity of the number of bits in a.
EXAMPLES:
sage: from sage.matrix.matrix_mod2_dense import parity sage: parity(1) 1L sage: parity(3) 0L sage: parity(0x10000101011) 1L
-
sage.matrix.matrix_mod2_dense.
ple
(A, algorithm='standard', param=0)¶ Return PLE factorization of A.
INPUT:
- A – matrix
- algorithm
- ‘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)
EXAMPLE:
sage: from sage.matrix.matrix_mod2_dense import ple sage: A = random_matrix(GF(2),4,4); 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
-
sage.matrix.matrix_mod2_dense.
pluq
(A, algorithm='standard', param=0)¶ Return PLUQ factorization of A.
INPUT:
- A – matrix
- algorithm
- ‘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)
EXAMPLE:
sage: from sage.matrix.matrix_mod2_dense import pluq sage: A = random_matrix(GF(2),4,4); 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]
-
sage.matrix.matrix_mod2_dense.
to_png
(A, filename)¶ Saves the matrix
A
to filename as a 1-bit PNG image.INPUT:
A
- a matrix over GF(2)filename
- a string for a file in a writable position
EXAMPLE:
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
-
sage.matrix.matrix_mod2_dense.
unpickle_matrix_mod2_dense_v1
(r, c, data, size)¶ Deserialize a matrix encoded in the string
s
.INPUT:
- r – number of rows of matrix
- c – number of columns of matrix
- s – a string
- size – length of the string s
EXAMPLE:
sage: A = random_matrix(GF(2),100,101) sage: _,(r,c,s,s2) = A.__reduce__() sage: from sage.matrix.matrix_mod2_dense import unpickle_matrix_mod2_dense_v1 sage: unpickle_matrix_mod2_dense_v1(r,c,s,s2) == A True sage: loads(dumps(A)) == A True