4
$\begingroup$

As per the title, I'm looking for the name and for a way to construct a ${\rm GF}(2)$ square matrix of size $N$ with the following properties:

  1. All rows/columns should be linearly independent
  2. On each row and each column there should be $N/2$ ones and zeros

Can anybody provide some pointers? It doesn't have to be a general solution (i.e. for all $N$) as long as it works for some $N$ it will be ok.

edit: It has been pointed out that if N is a multiple of 4 the two conditions above are incompatible. Let me relax number 2) by allowing, when N is a multiple of 4, the rows and columns to be (minimally) unbalanced.

edit2: Bonus points for pointing out a way to build matrices as the ones above, with the added constraint that the conditions above should be valid also for their inverse (obviously number 1 is implied).

  • 0
    This is http://math.stackexchange.com/questions/19480/dynamic-programming-a-type-of-balanced-0-1-matrix with an extra constraint, so that might be a useful starting point for algorithm development.2011-01-30

1 Answers 1