Dear all,
How to generate a matrix whose columns have fixed hamming weight in the finite field GF(2) ?
I hope for a fast method for a huge matrix, for example, rows 150000, columns 4000, weight 250.
Thanks all!
Here is a solution that may work for some practical purposes. It uses numpy to have a quick vectorialized way to get a "big" array with 2D.
NROWS, NCOLS, WEIGHT = 24, 10, 5
z = np.zeros((NROWS - WEIGHT, NCOLS), dtype=np.int8)
u = np.ones (( WEIGHT, NCOLS), dtype=np.int8)
a = np.concatenate((z, u), axis=0)
rng = np.random.default_rng()
b = rng.permuted(a, axis=0)
This initializes a matrix a with wanted blocks of zeros and ones,
sage: a
array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]], dtype=int8)
and we only need to scramble the columns. This can be done by using np.random.shuffle, but the simpler solution is to use the permuted method of the Generator type that came in one of the last versions of numpy (two or three years ago, i think).
And this time i've got for b:
sage: b
array([[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 1, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 1, 1, 0],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[0, 1, 0, 1, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 1, 1, 0, 1, 0],
[0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 1, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], dtype=int8)
Thanks! This is a clever method. But it takes about 40 seconds for NROWS, NCOLS, WEIGHT = 150000, 4000, 250. I found a faster method as follows.
def generate_fixed_hamming_weight_matrix(field_size, rows, cols, weight):
F.<b> = GF(field_size, modulus='primitive')
matrix = zero_matrix(GF(field_size),rows, cols)
for col in range(cols):
non_zero_indices = random.sample(range(rows), k=weight)
for i in non_zero_indices:
matrix[i, col] = b^randint(0,field_size-2)
return matrix
q=2; n=150000; ell = 4000; w_E = 250
%time E_Trans = generate_fixed_hamming_weight_matrix(q, n, ell, w_E)
This method takes about 3 seconds. I hope for an optimization from you.
Asked: 2024-04-29 04:47:42 +0100
Seen: 152 times
Last updated: Apr 29
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
Random matrix?
No random matrix! A matrix of size 150000 \times 4000, whose each column has a fixed hamming weight of 250. If using the random matrix, each column would have a fixed hamming weight of about 150000/2.
I mean random under the given constraints. If it is not random, then what particular columns with the given hamming weight you want to include in the matrix?
Thanks！It is better if such a matrix is random. I have found a method that costs about 3s.