¿Cuántas tablas cuyos elementos son 1 y -1?

Question

Intenté resolverlo por inducción pero no tuve éxito. El problema es:

Determinar el número de $(2^n -1) \times (2^n-1)$ tablas con 1 o -1 entradas tales que cada entrada es el producto de las entradas vecinas. (Dos entradas son vecinas si tienen una arista en común)

Answer 1

He aquí una respuesta parcial: hago algunos cálculos que se mantienen para cada $n$ y demuestro que para $n=3$ sólo hay una solución, la trivial (todas las entradas son iguales a $1$ ).

Dejemos que $M=(2^n-1)$ . Está buscando las matrices $(t_{ij})_{1\leq i,j \leq M}$ satisfacer su propiedad.

Es más fácil trabajar de forma aditiva que multiplicativa, por lo que $\phi : \lbrace -1,1 \rbrace \to {\mathbb F}_2$ sea el isomorfismo definido por $\phi(-1)=1$ y $\phi(1)=0$ .

Entonces la matriz $S=(s_{ij})_{1\leq i,j \leq M}$ definido por $s_{ij}=\phi(t_{ij})$ satisface : para cualquier entrada $(i,j)$ , $s_{ij}$ es la suma modulo $2$ de sus vecinos. Si definimos una función $f: {\mathbb Z}^2 \to {\mathbb F}_2$ por $f(i,j)=s_{ij}$ si $1\leq i,j \leq M$ y $0$ en caso contrario, entonces deducimos

$$ 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} $$

Pongamos $g(j)=f(1,j)$ para $j\in {\mathbb Z}$ . Utilizando (1) con $i=2$ tenemos

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

Utilizando (1) con $i=3$ y combinándolo con (2), vemos que

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

Siguiendo así, vemos por inducción que hay para cada $i$ un conjunto $A_i \subseteq \mathbb Z$ tal que para cualquier $j$ , $$ f(i,j)=\sum_{t\in A_i}g(j+t) \tag{4} $$

Aquí hay algunos $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} $$

No hay un patrón obvio por lo que puedo ver. Veamos qué ocurre cuando $n=3,M=7$ : por el valor de $A_8$ arriba, uno tiene

$$ \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} $$

Resolviendo el sistema, vemos que todos los $g(j) (1\leq j \leq 7)$ son cero, por lo que en ese caso sólo existe la solución trivial.