Binary matrix with fixed inner product.

115 Views Asked by At

Suppose that $m,\ n$ are two positive integers such that $m<<n$. Let $a,\ b,\ c$ be the three positive integers such that $a\leq b < c$. Consider a binary matrix $A\in \{0,1\}^{m\times n}$, such that for any two differnt columns $u$ and $v$ of matrix $A$, it is the case that, $$a\leq\langle u ,v \rangle \leq b,$$

and every column should contain at least $c$ numbers of $1's$.

Is it possible to construct such a matrix $A$ given the parameters $m,n, a,b,c$?

2

There are 2 best solutions below

0
On

This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.

If $n > {{m}\choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.

The answer for $n \leq {{m}\choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n \leq {{m}\choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.

However if $n= {{m}\choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.

The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}\choose{c}}$ options which are valid. If $a \leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $\min \{2c-m,0\}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.

Much more than that requires more combinatorics that I can manage.

5
On

Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of $\{1,\ldots,n\}.$

So if row $k$ is $$(a_{k,j})_{1\leq j\leq n}$$ the $k^{th}$ subset contains element $$j \in \{1,\ldots,n\},$$ if and only if $a_{i,j}=1.$

A collection $\cal A$ of subsets of $\{1,\ldots,n\}$ is $L$-intersecting, if for any two sets $A,B:$

$$A\cap B \in L$$ holds. Only the cardinality $s=|L|$ matters. Clearly $L\subset \{1,\ldots,n\}.$

If the intersecting family $\cal A$ is uniform (all its sets have fixed size) then $$ |\cal A| \leq \binom{n}{s} $$ otherwise $$ |\cal A| \leq \sum_{i=0}^s \binom{n}{i}. $$ For you $s=b-a+1.$

See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf

Edit: In general, good lower bounds are much harder to come by.

For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L=\{0,1,\ldots,s-1\},$ for all $k\geq s\geq 1,$ and $n\geq 2k^2,$ there exists a $k-$uniform family $\cal A$ (all sets have cardinality $k$) with $$ |\cal A| \geq (n/2k)^s, $$ on $\{1,\ldots,n\},$ such that $|A\cap B|\leq s-1$ for all distinct pairs $A,B\in {\cal A}.$