1
$\begingroup$

I'm using Sage to calculate a bunch of matrix operations over GF(2), using the code below to randomly generate an invertible matrix:

size = 10
MS = MatrixSpace(GF(2), size, size)
while True:
    M = MS.random_element()
    if M.is_invertible():
        break

The problem is that right now, this generates a matrix with average density=0.5 (i.e. since we're taking the matrix over GF(2), half the entries are "0" and half the entries are "1".) I've been wading through Sage manuals and guidelines but still can't figure out how to tweak the density of the matrix.

There is a "density=X" parameter I found, but it claims that it only gives an upper bound, and actually provides no guarantees on the returned matrix, and I can't even figure out which command I should add it to. All the examples just use random_matrix(...) and not a MatrixSpace, which I need in order to preserve the GF(2) operations.

Any thoughts? Thanks in advance!

$\endgroup$
1
$\begingroup$

May I take it that setting density=foo in random_element isn't working for you? See the reference manual. From my experimentation MS.random_element(density=1) definitely gives me the fully non-zero matrix over $\mathbb{F}_2$ every time.

That said, I agree the documentation is not very clear on exactly how to get what density, though

if set to None, all entries of the matrix are randomized

seems to be what is occurring with your example, since None is the default.

(In your particular case, see also the source for this field.)

$\endgroup$
0
$\begingroup$

Well, $0.5$ is the expected density you would get, so you ought to get that as an average. If you need a different expected density and sage doesn't provide a builtin method to do it, you can just sample each bit with different probabilities of being $1$ and being $0$. Of course, the probability of being $1$ is exactly the expected bit density of the matrix.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.