7
$\begingroup$

For what $n$ does there exist a self-complementary $(2n,4n-2,2n-1,n,n-1)$ balanced incomplete block design?

(All I know is that a self-complementary design with these parameters does exist for all $n$ of the form $2^k$ but doesn't exist for $n=3$.)

Motivating problem: One wants to divide $2n$ players into 2 equal-sized teams in $2n-1$ different ways in such a way that each player is on the same team as each other player exactly $n-1$ times.

For a follow-up question, see More about self-complementary block designs .

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Please clarify what exactly you mean by "self-complementary". That the design admits a polarity? Or is isomorphic to the dual (this would be the usual meaning of self-complementary)? Or something else? Or you just mean to say that the block size is half the number of points? $\endgroup$
    – Dima Pasechnik
    Mar 19, 2016 at 18:25
  • $\begingroup$ I presume by self-complementarity you mean that the complement of each block is a block itself. (Like in the design of hyperplanes of an affine space over $\mathbb{F}_2$.) $\endgroup$
    – Dima Pasechnik
    Mar 19, 2016 at 19:17
  • $\begingroup$ Yes, Dima's surmise about the intended meaning of "self-complementary" is correct. $\endgroup$
    – James Propp
    Mar 20, 2016 at 2:07

2 Answers 2

Reset to default
4
$\begingroup$

These are the parameters for Hadamard 2-designs. Let $H$ be an $n\times n$ Hadamard matrix, where $n=4m$, normalized so that all entries in the first row are equal to 1. Each row apart from the first gives a partition of $\{1,\ldots,n\}$ into two sets of size $n/2$, hence we get $2n-2$ blocks of size $n/2$. The resulting incidence structure is a 2-design: because the columns of $H$ are pairwise orthogonal, any two columns differ in exactly $n/2$ positions and so any two points lie in exactly $(n-2)/2$ blocks.

Also the designs constructed from Hadamard matrices as above are 3-designs, and it can be show that any 3-design with these parameters arises in this way.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It does not look obvious why one would always get a Hadamard matrix from the design: for this one has to show that for any two pairs $P$, $P'$ of complementary blocks, converted into $\pm 1$-vectors $v$, $v'$, one has $\langle v,v'\rangle=0$. $\endgroup$
    – Dima Pasechnik
    Mar 20, 2016 at 16:57
  • $\begingroup$ @DimaPasechnik: It does not look obvious to me now, so I've backed down somewhat. $\endgroup$
    – Chris Godsil
    Mar 20, 2016 at 19:21
  • $\begingroup$ OK, I just proved that you were right, see my edited answer... $\endgroup$
    – Dima Pasechnik
    Mar 20, 2016 at 20:37
3
$\begingroup$

There is an example for $n=6$, a quite exceptional one. It comes from the smallest finite sporadic simple group $G=M_{11}$ of order 7920. $G$ has a permutation representation on 12 points, corresponding to the (left) cosets of a subgroup isomorphic to $PSL_2(11)$. A subgroup isomorphic to $A_6$, the alternating group of degree 6, has 2 orbits on 12 points, both of length 6, and the images of these orbits under $G$ are the 22 blocks of the design.

In general, consider the $(2n\times 2n)$-matrix $H$ with entries $\pm 1$ columns labelled by points, the 1st row of all 1s, and the remaining rows labelled by pairs $b,b'$ of complementary blocks (we can assume w.l.o.g. that $b$ contains the 1st point); we put 1 in the $(b,b'),p$-entry of $H$ if the point $p$ is in $b$, and -1 otherwise. If $q$ is another point then, as the pair $(p,q)$ lies in $n-1$ blocks, the scalar product of $p$th and $q$th columns of $H$ is $1+(n-1)-n=0$. Thus $H$ is a Hadamard matrix. As Chris points out, this also means that the design is a 3-design, known as Hadamard 3-design. (It will be a $3-(2n,n,n/2-1)$-design).

Thus, indeed, we will always have a Hadamard matrix giving us the design in question; in particular $n$ must be even.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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