#20493: Rank of random matrices over GF(2) is bounded (again)
-------------------------+-------------------------------------------------
Reporter: kedlaya | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-7.2
Component: linear | Keywords: random matrices, rank,
algebra | pseudorandom numbers
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: todo |
-------------------------+-------------------------------------------------
This is reproducible:
{{{
sage: [random_matrix(GF(2), 25000, 25000).rank() for i in range(5)]
[19937, 19937, 19937, 19937, 19937]
}}}
A functionally equivalent computation:
{{{
sage: u = MatrixSpace(GF(2), 25000, 25000)(0)
sage: u.randomize()
sage: u.rank()
19937
}}}
The docstring of the `randomize` method provides a clue:
{{{
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]
}}}
So it seems that we simply kicked the can down the road, and now that we
can compute ranks at this size easily using m4ri, we have found the can
again. Volker Braun observed on sage-devel (see
https://groups.google.com/forum/#!topic/sage-devel/gDGM6bRle0A) that the
19937 is probably somehow coming from the Mersenne Twister having a period
of `2^19937 - 1`.
Note that the linear dependence caused by insufficiently pseudorandom
number generation is quite fragile:
{{{
sage: u = MatrixSpace(GF(2), 25000, 25000)(0)
sage: u.randomize(density=0.99)
sage: u.rank()
25000
sage: u = random_matrix(GF(101), 25000, 25000)
sage: u1 = u.change_ring(ZZ)
sage: u2 = u1.change_ring(GF(2))
sage: u2.rank()
24999
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/20493>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
