Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
    
This is math.stackexchange.com/questions/19480/… with an extra constraint, so that might be a useful starting point for algorithm development. –  Peter Taylor Jan 30 '11 at 16:53

1 Answer 1

It's not possible for $N$ divisible by 4, because the vectors with an even number of 1's form a proper subspace of ${\rm GF}(2)^N$. For $N=6$ there are many examples, such as

$$\begin{pmatrix}1&1&1&0&0&0\\1&1&0&1&0&0\\0&0&1&1&0&1\\1&0&0&0&1&1\\0&1&0&0&1&1\\ 0&0&1&1&1&0\end{pmatrix}$$

share|improve this answer
    
Is there a known algorithm to build such matrices for bigger values of N? –  CAFxX Jan 30 '11 at 13:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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