3
$\begingroup$

If there are m binary arrays (with 0 and 1) of length n, and between any two of these m arrays, there are k and only k same numbers (with the same site index in two different arrays). For example, if m=2, n=3 and k=2, then

      011
      010   

is the case, while

      011
      110

is not (only same at the second site, so k=1).

My question is: how many are the possible conditions of these m arrays (in terms of m, n, k)? Of course, if there is no restriction about k, the number will be 2^(mn).

$\endgroup$
3
  • $\begingroup$ If we think of each array as the indicator vector for a subset of $\{1,\dots,n\}$, where $a_i = 1$ if $i$ is in the subset, then we can phrase this as a collection of sets where each pair has symmetric difference exactly $n-k$. This must be studied in combinatorics... $\endgroup$
    – usul
    Sep 18, 2018 at 19:26
  • $\begingroup$ Indeed, it is related to balanced incomplete block designs. I was writing a post for this linking it to Hadamard matrices when I found that the condition was a little more general. However, making the reduction to the first row being all ones shows that (for an ordered set of rows) there are at least 2^n many examples. Gerhard "Engaged Brain Before Pressing Post" Paseman, 2018.09.18. $\endgroup$ Sep 18, 2018 at 19:50
  • $\begingroup$ @Gerhard Paseman Thanks for your comments. I will visit the "balanced incomplete block designs" for more details. $\endgroup$ Sep 19, 2018 at 4:47

1 Answer 1

2
$\begingroup$

One question is when can you do it at all. The question of how many ways then depends on what you consider as different and, in any case, will be difficult to answer exactly. For any $k$, $m=2$ is possible and the counts are easy. I'll discuss $m=3$ and leave $m=4$ as an exercise. For $m \gt 4$ I think it would be pretty difficult to get counts.

As I understand it, you want for given $n,m,k$ to know if there is an $m \times n$ array filled with two symbols $a,b$ so that each pair of rows agrees in exactly $k$ positions. And, if so, how many "different" ones there are.

You used $0,1$ for the symbols but it turns out that $1,-1$ are nicer (and of course that does not change the problem.) It looks cleaner to use $\overline 1$ to denote $-1$ so I will.

Here in an example with $10,3,4$

$A=\left[ {\begin{array}{cccccccccc}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & \overline 1 & \overline 1 & \overline 1 & \overline 1 & \overline 1 & \overline 1\\1 & \overline 1 & \overline 1 & \overline 1 & 1 & 1 & 1 & \overline 1 & \overline 1 & \overline 1\end{array} } \right]$

Note that $$AA^t=\left[ {\begin{array}{ccc}10 & -2 & -2 \\ -2 & 10 & -2\\ -2 & -2 & 10 &\end{array} } \right].$$ In general one wants an $m \times n$ matrix $A$ filled with $1$ and $\overline 1$ such that the $m \times m$ product $AA^t$ has $n$ on the diagonal and $2k-n$ off it. See if you can figure out why that forces $m \leq n.$

UPDATE That isn't quite correct. It is possible to have $n=m+1$ in a special case. I'll explain at the end.

$A$ would remain an example if the rows and or the columns were permuted in any manner. Also we could swap $1$ and $\overline1$ in any column or columns to get the first row to be as we desire. That does not affect the number or pattern of matches. So for this very small case $10,3,4$ I will say that there must be exactly one column where everything matches and , if I decree that the first row is all $1$ that gives $\frac{10!}{1!3!3!3!}=16800$ possibilities. Multiply by $2^{10}$ if you want arbitrary first row. If you consider row swaps as giving the same thing the counts would, of course, be smaller.

In general $n,3,k$ is possible exactly when $j=\frac{n-k}{3}$ is an integer. Then, with first row all $1$ one would have $n-3j$ columns with three $1$s and each of the other three possible columns with a $1$ on top $j$ times.

If one has an example for $n,m,k$ and deletes some rows one has an example for $n,m',k$ so the question of existence is perhaps:

Given $n,k$ what is the largest $2 \leq m \leq n$ such that there is an $n,m,k$ example?

It would not preserve the example above if we multiplied a row by $-1$. Then it would instead have $n-k$ matches and $k$ non-matches with all the rest.

In the special case that $n=2k$ we can do that so one generally assumes that the first row and first column are all $1$s.

For $n=2k$ one wants $AA^t$ to be an $nI_m.$ For $AA^t=nI_n$ these are called Hadamard matrices. As you can tell, much is know but there are open questions.


I had mistakenly claimed that $m \leq n$ (provided that the rows are distinct). Actually there is this type of example with $m=n+1:$ start with an $m \times m$ Haddamard matrix with first row and column all $1$s and delete the first column to get $n,m,k=2k+1,2k+2,k.$ For example a $12,12,6$ Haddamard matrix turns into a $12 \times 11$ matrix where every pair of rows agrees in 5 positions. Conversely, from an $n,m,k=2k+1,2k+2,k$ we can get a $2k+2,2k+2,k+1$ Haddamard matrix.

Here are examples with $m=2$ and $4$

$\left[ {\begin{array}{c}1 \\ \overline 1 \end{array} } \right]$ and $\left[ {\begin{array}{ccc}1 & 1 & 1 \\ 1 & \overline 1 &\overline 1 \\ \overline 1& 1 & \overline 1 \\ \overline 1 & \overline 1 &1\end{array} } \right].$

Here is my intended proof modified to show that $m \leq n+1$ with $m=n+1$ possible , though only in the case above.

Recall that we seek an $m \times n$ matrix $A$ (entries $1$ and $\overline 1$) so that the $m \times m$ product $B=AA^t$ has $n$ on the diagonal and $j=2k-n$ off it. Since $\operatorname{rank}(A) \leq n$ also the $m \times m$ matrix $B=AA^t$ has $\operatorname{rank}(B) \leq n.$ The eigenvalues of $B$ are $n+(m-1)j$ once and $n-j=2n-2k$ a total of $m-1$ times. This second eigenvalue is non-zero so $m-1 \leq \operatorname{rank}(B) \leq n$ meaning $m-1 \leq n.$ If $m=n+1$ then the first eigenvalue will have to be zero: $n+(m-1)j=n+nj=0$ This means $j=2k-n=-1$ So $n=2k+1=m-1.$

$\endgroup$
3
  • $\begingroup$ Thanks a lot. You recast my question much more gently, and explain the problem in a clear way. I am sorry that I can't figure out why m≤n. Could you give me some hints? Thanks again. $\endgroup$ Sep 19, 2018 at 4:52
  • 1
    $\begingroup$ It doesn't . There is an example with m=4 and n=3. Gerhard "There May Be Larger Examples" Paseman, 2018.09.19. $\endgroup$ Sep 20, 2018 at 5:16
  • $\begingroup$ Right again @Gerhard. One can remove the first column from a Haddamard matrix in standard form to get $m=n+1.$ But otherwise $m \leq n.$ $\endgroup$ Sep 20, 2018 at 8:32

Your Answer

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

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