How many different $2n$-block $A_i$ can we construct such that $|A_i\cap A_j|=n$?

43 Views Asked by At

I hope I can explain my problem properly. sorry if it is ambiguous or is not well defined.

Suppose $A_0=\mathsf{aa\dots a bb\dots b}$ which each $\mathsf{a}$ and $\mathsf{b}$ repeated $n$-times. By changing places of $\mathsf{a}$ or $\mathsf{b}$ we can construct a new block but again with $n$ times $\mathsf{a}$ and $n$ times $\mathsf{b}$. for example $A_1=\mathsf{baa\dots a bb\dots ba}$. and by intersection of two blocks we mean entries with same entry and same place. i.e. $A_j\cap A_i=\{(s,(A_i)_s)\ |\ (A_j)_s=(A_i)_s \}$ My question is how many different $2n$-block $A_i$ can we construct such that $|A_i\cap A_j|=n$ for all $i,j$?

For $n=1$, we can have only one block $A_1=\mathsf{ba}$ other that given block $A_0=\mathsf{ab}$ but $|A_0\cap A_1|=0$ so it is not acceptable so we have one block.

For $n=2$, I think $A_0=\mathsf{aabb}$, $A_1=\mathsf{abab}$ and $A_2=\mathsf{abba}$ are one possible blocks with required properties and I think this is the extrema case so we have three blocks.

1

There are 1 best solutions below

0
On BEST ANSWER

First of all, when $n$ is odd, you can have at most one vector. This is because two vectors with $n$ A's and $n$ B's will always agree in an even number of places, so if two vectors agree in $n$ places, $n$ must be even.

You certainly cannot construct more than $2n-1$ such vectors. Instead of $a$ and $b$, let us use $+1$ and $-1$, and think of these as vectors in $\mathbb R^{2n}$. With this modification, the condition that two vectors $\newcommand{\v}[1]{\mathbf{#1}}\v v$ and $\v w$ agree in exactly $n$ places is equivalent to saying that $\v v\cdot \v w=0$. This means your vectors are pairwise orthogonal, and therefore linearly independent. Since the vectors all lie in the subspace $$\{(v_1,\dots,v_{2n})\mid v_1+\dots+v_{2n}=0\}$$ of dimension $2n-1$, there are at most $2n-1$ vectors.

This upper bound is attainable whenever a Hadamard matrix of order $2n$ exists; simply throw out the all-ones row. It is conjectured that a Hadamard matrix of order $m$ exists whenever $m$ is a multiple of $4$, so as long as $n$ is even, it is conjectured you can attain this upper bound of $2n-1$ vectors. The Wikipedia article has more information about constructing Hadamard matrices.