5
$\begingroup$

Let $n$ be a positive integer. The output of the problem is another positive integer $r$ which must be as small as possible.

I want to construct $2n$ binary vectors $x_i\in\{0,1\}^r$ and $y_i\in\{0,1\}^r$, with $i\in\{1,...,n\}$, which must respect the following conditions:

  • $x_i^Ty_i=0$ with $i\in\{1,...,n\}$,
  • $x_{i+1}^Ty_i=0$ with $i\in\{1,...,n-1\}$, and $x_1^Ty_n=0$ (it is cyclic).
  • $x_{j}^Ty_i>0$ with $i\in\{1,...,n-1\}$, $j\in\{1,...,n\}\setminus \{i,i+1\}$.

All the vectors $x_i$ must be distinct and all the vectors $y_i$ must be distinct.

For a given number $n$ of vectors, what is the smallest dimension $r=f(n)$ for which it is possible to construct vectors $x_i,y_i$ respecting the conditions described above?

An obvious upper bound is $f(n)\leq n$. Since the $x_i$ must be distinct, a lower bound is $f(n)\geq \lceil \log_2(n)\rceil$. However, this lower bound seems rather weak.

Example for $n=7$, there is a solution with $r=6$ (but apparently, not with $r=5$):

  • $x_1=\begin{pmatrix}0&0&1&0&1&1\end{pmatrix}^T$ $\hspace{1cm }$ $y_1=\begin{pmatrix}0&1&0&1&0&0\end{pmatrix}^T$.
  • $x_2=\begin{pmatrix}1&0&0&0&1&1\end{pmatrix}^T$ $\hspace{1cm }$ $y_2=\begin{pmatrix}0&1&1&0&0&0\end{pmatrix}^T$.
  • $x_3=\begin{pmatrix}1&0&0&1&0&1\end{pmatrix}^T$ $\hspace{1cm }$ $y_3=\begin{pmatrix}0&1&0&0&1&0\end{pmatrix}^T$.
  • $x_4=\begin{pmatrix}0&0&1&1&0&1\end{pmatrix}^T$ $\hspace{1cm }$ $y_4=\begin{pmatrix}1&0&0&0&1&0\end{pmatrix}^T$.
  • $x_5=\begin{pmatrix}0&1&1&1&0&0\end{pmatrix}^T$ $\hspace{1cm }$ $y_5=\begin{pmatrix}1&0&0&0&0&1\end{pmatrix}^T$.
  • $x_6=\begin{pmatrix}0&1&0&1&1&0\end{pmatrix}^T$ $\hspace{1cm }$ $y_6=\begin{pmatrix}1&0&1&0&0&0\end{pmatrix}^T$.
  • $x_7=\begin{pmatrix}0&1&0&0&1&1\end{pmatrix}^T$ $\hspace{1cm }$ $y_7=\begin{pmatrix}1&0&0&1&0&0\end{pmatrix}^T$.
$\endgroup$
  • 1
    $\begingroup$ what's the motivation/application, if any, for this nice question? $\endgroup$ – kodlu Jan 17 '16 at 22:19
  • $\begingroup$ @kodlu This research question I want to answer is related to the boolean matrix rank of a special matrix. Consider the $x_i$'s and $y_i$'s as columns of the matrices $X$ and $Y$ respectively. When the product $X^TY$ is computed, there must be two adjacent diagonals equal to zero, and everywhere else, the entries must be positive. The goal is to generate such a pattern with the fewest rank-1 factors. $\endgroup$ – Paul Bub. Jan 19 '16 at 10:25
  • $\begingroup$ Bub: thanks for the explanation. the constraints remind me of optical orthogonal code constraints as well... $\endgroup$ – kodlu Jan 19 '16 at 23:00
3
$\begingroup$

The $\log_2 n$ lower bound is actually within a constant factor of optimal for large $n$.

Now let $x_1, \dots, x_n$ be formed by randomly setting each coordinate of each $x_i$ to $1$ with probability $\frac{1}{3}$ (with the events $x_i(k)=1$ independent for all $1 \leq i \leq n$ and $1 \leq k \leq r$). Let the vectors $y_1, \dots, y_n$ be defined by $$y_i(k)=\left\{\begin{array}{cc} 1 & \textrm{ if } x_i(k)=x_{i+1}(k)=0 \\ 0 & \textrm{ otherwise } \end{array} \right.$$ The first two conditions are immediately satisfied by our definition of $y$. What remains to check is that $x_j^T y_i>0$ for $j \notin \{i, i+1\}$.

Note that for these $(i,j)$ the vectors $x_j$ and $y_i$ are independent. So for any $k$, we have $$P(x_j(k)=y_i(k)=1)=\frac{1}{3} \left(\frac{2}{3}\right)^2 = \frac{4}{27}$$ Multiplying over all coordinates and taking the union bound over all pairs $(i,j)$, we have that the probability the third condition is violated is at most $$n^2 \left(\frac{23}{27} \right)^r$$ So if $r=c \log n$ for $c>\log_{27/23} 2 \approx 4.323$ and $n$ is sufficiently large, then the probability some condition is violated tends to $0$, so there's a set of vectors which works.

$\endgroup$
  • $\begingroup$ I note that you ask for each $x_i$ to be (on average) one-third ones, while OP's example for $n=7$ has each $x_i$ exactly one-half ones. But the $y_i$ in OP's example are each exactly one-third ones, and of course there's a symmetry between the $x_i$ and the $y_i$ in the question. $\endgroup$ – Gerry Myerson Jan 19 '16 at 21:57
  • $\begingroup$ The $1/3$ here was essentially chosen just to make $23/27$ as small as possible. You're right that this construction loses the symmetry present in the original problem. I'm curious if this is just an artifact of the proof or if the same thing happens in the actual minimal $r$ case. $\endgroup$ – Kevin P. Costello Jan 19 '16 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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