# How to fast generate a matrix with columns of fixed hamming weight

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!

edit retag close merge delete

Random matrix?

( 2024-04-29 06:11:52 +0200 )edit

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.

( 2024-04-29 06:41:17 +0200 )edit

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?

( 2024-04-29 12:48:36 +0200 )edit

Thanks！It is better if such a matrix is random. I have found a method that costs about 3s.

( 2024-04-29 17:08:12 +0200 )edit

Sort by » oldest newest most voted

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)

more

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.

( 2024-04-29 17:24:43 +0200 )edit