5
$\begingroup$

I tried to solve this by induction but wasn't successful. Problem is:

Determine the number of $(2^n -1) \times (2^n-1)$tables with 1 or -1 entries such that each entry is the product of neighboring entries. (Two entries are neighboring if they have an edge in common)

$\endgroup$
4
  • $\begingroup$ Which entries count as neighboring? Those that are adjacent vertically and horizontally? And what happens along the edges? $\endgroup$ – Brian M. Scott Nov 7 '13 at 17:44
  • 2
    $\begingroup$ The phrase "each entry is the product of four neighboring entries" is a little puzzling, since it's not clear what it means for edge or corner elements that don't have four neighboring entries. But we might suppose that these entries are the product of their two or three neighboring entries. Then it seems that the crucial observation is that just over half the entries can be chosen with no constraints at all, and that doing so completely constrains all the remaining entries. $\endgroup$ – MJD Nov 7 '13 at 17:44
  • $\begingroup$ @MJD You are right. "Four neighboring entries" should be replaced by "neighboring entries" as you explained. $\endgroup$ – Hoseyn Heydari Nov 7 '13 at 17:50
  • $\begingroup$ My idea above does not work. $\endgroup$ – MJD Nov 7 '13 at 18:14
1
+50
$\begingroup$

Here is a partial answer : I make some computations that hold for every $n$, and I show that for $n=3$ there is only one solution, the trivial solution (all entries equal to $1$).

Let $M=(2^n-1)$. You are looking for the matrices $(t_{ij})_{1\leq i,j \leq M}$ satisfying your property.

It is easier to work additively than multiplicatively, so let $\phi : \lbrace -1,1 \rbrace \to {\mathbb F}_2$ be the isomorphism defined by $\phi(-1)=1$ and $\phi(1)=0$.

Then the matrix $S=(s_{ij})_{1\leq i,j \leq M}$ defined by $s_{ij}=\phi(t_{ij})$ satifies : for any entry $(i,j)$, $s_{ij}$ is the sum modulo $2$ of its neighbors. If we define a function $f: {\mathbb Z}^2 \to {\mathbb F}_2$ by $f(i,j)=s_{ij}$ if $1\leq i,j \leq M$ and $0$ otherwise, then we deduce

$$ f(i,j)=f(i-2,j)+f(i-1,j-1)+f(i-1,j)+f(i-1,j+1) (i,j \in {\mathbb Z}) \tag{1} $$

Let us put $g(j)=f(1,j)$ for $j\in {\mathbb Z}$. Using (1) with $i=2$, we have

$$ f(2,j)=g(j-1)+g(j)+g(j+1) \ \ (j \in {\mathbb Z}) \tag{2} $$

Using (1) with $i=3$ and combining it with (2), we see that

$$ f(3,j)=g(j-2)+g(j+2) \ \ (j \in {\mathbb Z}) \tag{3} $$

Continuing this way, we see by induction that there is for each $i$ a set $A_i \subseteq \mathbb Z$ such that for any $j$, $$ f(i,j)=\sum_{t\in A_i}g(j+t) \tag{4} $$

Here are some $A_i$’s :

$$ \begin{array}{lcl} A_1 &=& \lbrace 0 \rbrace \\ A_2 &=& \lbrace 0; \pm 1 \rbrace \\ A_3 &=& \lbrace \pm 2 \rbrace \\ A_4 &=& \lbrace 0; \pm 2; \pm 3 \rbrace \\ A_5 &=& \lbrace 0; \pm 2; \pm 4 \rbrace \\ A_6 &=& \lbrace 0; \pm 3; \pm 4; \pm 5 \rbrace \\ A_7 &=& \lbrace 0; \pm 6 \rbrace \\ A_8 &=& \lbrace 0; \pm 1; \pm 3;\pm 4; \pm 6\pm 7 \rbrace \\ \end{array} $$

There is no obvious pattern as far as I can see. Let us look at what happens when $n=3,M=7$ : by the value of $A_8$ above, one has

$$ \begin{array}{lclcl} 0 &=& f(8,1) &=& g(1)+g(2)+g(4)+g(5)+g(7) \\ 0 &=& f(8,2) &=& g(1)+g(2)+g(3)+g(5)+g(6) \\ 0 &=& f(8,3) &=& g(2)+g(3)+g(4)+g(6)+g(7) \\ 0 &=& f(8,4) &=& g(1)+g(3)+g(4)+g(5)+g(7) \\ 0 &=& f(8,5) &=& g(2)+g(4)+g(5)+g(6) \\ 0 &=& f(8,6) &=& g(3)+g(5)+g(6)+g(7) \\ 0 &=& f(8,7) &=& g(1)+g(4)+g(6)+g(7) \\ \end{array} $$

Solving the system, we see that all the $g(j) (1\leq j \leq 7)$ are zero, so that in that case there is only the trivial solution.

$\endgroup$
0

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.