Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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)
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.
