Un curioso determinante de Hankel

Question

Definir la secuencia $a_{n}$ por $a_{n}=1$ si $n+1=2^k$ para algunos $k$ et $a_{n}=0$ si no.

Los experimentos informáticos sugieren que el determinante de la matriz de Hankel $$H_{n+1}:=\begin{pmatrix} a_{0} & a_{1} & \dots & a_{n}\\ a_{1} & a_{2} & \dots & a_{n+1}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n} & a_{n+1} & \dots & a_{2n} \end{pmatrix}$$ satisface $$\det{H_{n+1}}=(-1)^\binom{n+1}{2}.$$ ¿Hay alguna forma sencilla de demostrarlo?

Edita: Sea $H_{n}=(h(i,j)).$ Para cada $n$ existe una única permutación de ${(0,1,\dots,n-1)}$ tal que el determinante de $H_{n}$ es igual a $h_{0,p(0)}h_{1,p(1)}\dots h_{n-1,p(n-1)}.$

Permítanme mostrar esto en el siguiente ejemplo donde para mayor claridad he puesto $a(n)=x(n)$ si $n+1$ es una potencia de $2.$ $$H_{9}=\begin{pmatrix} x(0) & x(1) & 0 & x(3) & 0 & 0 & 0 & x(7)& 0\\ x(1) & 0 & x(3) & 0 & 0 & 0 & x(7) & 0& 0\\ 0 & x(3) & 0 & 0 & 0 & x(7) & 0 & 0& 0\\ x(3) & 0 & 0 & 0 & x(7) & 0 & 0 & 0& 0\\ 0&0&0&x(7)&0&0&0&0&0\\ 0&0&x(7)&0&0&0&0&0&0\\0&x(7)&0&0&0&0&0&0&0\\ x(7) & 0 & 0 & 0 & 0 & 0 & 0 & 0&x(15)\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & x(15)& 0 \end{pmatrix}$$ Si vamos de derecha a izquierda vemos que $p(8)=7,p(7)=8.$ Entonces $p(6)=1,p(5)=2,p(4)=3,p(3)=4,p(2)=5,p(1)=6.$ Queda $p(0)=0.$ En general, el mismo procedimiento funciona. Así pues, mi pregunta se reduce a una prueba del hecho de que el signo de esta permutación es $(-1)^\binom{n}{2}.$

Answer 1

Sí, la hay pero en realidad no se trata de factores determinantes. Permítanme introducir algunas notaciones y enunciar el resultado principal.

Definición. Sea $\mathbb{N}$ sea el conjunto $\left\{ 0,1,2,\ldots \right\} $ . Para cada $i\in\mathbb{N}$ et $j\in\mathbb{N}$ dejamos que $\left[ i,j\right] $ sea el intervalo $\left\{ i,i+1,\ldots,j\right\} $ o $\mathbb{N}$ (está vacío cuando $i>j$ ).

Para cada $n\in\mathbb{N}$ dejamos que $\left[ n\right] ^{\prime}$ sea el intervalo $\left[ 0,n-1\right] =\left\{ 0,1,\ldots,n-1\right\} $ o $\mathbb{N}$ .

Definición. Sea $n\in\mathbb{N}$ y que $\sigma$ b de $\left[ n\right] ^{\prime}$ . Entonces, $\sigma$ se dice ágil i cada $i\in\left\{ 0,1,\ldots,n-1\right\} $ el número $i+\sigma\left( i\right) +1$ es una potencia de $2$ .

Sí, $1$ cuenta como una potencia de $2$ . El nombre "ágil" alude al juego de Nim (y la adición Nim), pero no tengo tiempo para averiguar la conexión exacta.

He aquí mi afirmación principal (que usted ha conjeturado):

Teorema 1. Sea $n\in\mathbb{N}$ .

(a) Entonces, hay una única permutación ágil $\sigma_{n}$ o $\left[ n\right] ^{\prime}$ .

(b) Esta permutación $\sigma_{n}$ tiene signo $\left( -1\right) ^{\sigma_{n}}=\left( -1\right) ^{n\left( n-1\right) /2}$ .

Esta permutación arroja su conjetura de que $\det\left( H_{n}\right) =\left( -1\right) ^{n\left( n-1\right) /2}$ para cada $n\in\mathbb{N}$ . En efecto, si fijamos $n\in\mathbb{N}$ entonces el determinante de la matriz $H_{n}=\left( a_{i+j}\right) _{i\in\left[ n\right] ^{\prime};\ j\in\left[ n\right] ^{\prime}}$ reescribe como \begin{align*} \det\left( H_{n}\right) & =\sum_{\sigma\text{ is a permutation of }\left[ n\right] ^{\prime}}\left( -1\right) ^{\sigma}\underbrace{a_{0+\sigma\left( 0\right) }a_{1+\sigma\left( 1\right) }\cdots a_{n-1+\sigma\left( n-1\right) }}_{\substack{= \begin{cases} 1, & \text{if }\sigma\text{ is nimble};\\ 0, & \text{if }\sigma\text{ is not nimble} \end{cases} \\\ por la definición del texto es una permutación de izquierda a derecha a la izquierda (-1 derecha) \begin{cases} 1, & \text{if }\sigma\text{ is nimble};\\ 0, & \text{if }\sigma\text{ is not nimble} \end{cases} \\ & = \ es una permutación ágil de izquierda es una permutación ágil de & = izquierda( -1\derecha) ^{n-izquierda( n-1\derecha) /2} {cuadrado-izquierda( \texto{por Teorema 1) . \fin{align*} Así que queda por demostrar el teorema 1.

Comenzamos con lemas sencillos:

Lema 2. Sea $n$ sea un número entero positivo. Sea $k$ b tal que $2^{k-1}<n\leq2^{k}$ . Sea $i\in\left[ n\right] ^{\prime}$ b que $i\geq2^{k}-n$ .

(a) Entonces, ambos números $i$ et $2^{k}-i-1$ son elementos de $\left[ n\right] ^{\prime}$ y al menos uno de ellos es $\geq2^{k-1}$ .

(b) Sea $\sigma$ sea una permutación ágil de $\left[ n\right] ^{\prime}$ . Entonces, $\sigma\left( i\right) =2^{k}-i-1$ .

Demostración del lema 2. (a) En $i\in\left[ n\right] ^{\prime}$ obtenemos $i\leq n-1<n\leq2^{k}$ de modo que $2^{k}-i>0$ y así $2^{k}-i-1\geq0$ . Pero $i\geq2^{k}-n$ de modo que $i+n\geq2^{k}$ y así $2^{k}-i\leq n$ . Así, $\underbrace{2^{k}-i}_{\leq n}-1\leq n-1$ . Combinando esto con $2^{k} -i-1\geq0$ obtenemos $2^{k}-i-1\in\left[ 0,n-1\right] =\left[ n\right] ^{\prime}$ . Así, ambos números $i$ et $2^{k}-i-1$ son elementos de $\left[ n\right] ^{\prime}$ (ya que $i\in\left[ n\right] ^{\prime}$ por suposición). Queda por demostrar que al menos uno de ellos es $\geq2^{k-1}$ .

Supongamos lo contrario. Por lo tanto, ninguno de estos dos números es $\geq2^{k-1}$ . Por lo tanto, ambos son $<2^{k-1}$ . En otras palabras, $i<2^{k-1}$ et $2^{k}-i-1<2^{k-1}$ . En $i<2^{k-1}$ obtenemos $i\leq2^{k-1}-1$ (ya que $i$ et $2^{k-1}$ son enteros). Por lo tanto, \begin{equation} 2^{k}-1=\underbrace{i}_{\leq2^{k-1}-1}+\underbrace{2^{k}-i-1}_{<2^{k-1} }<2^{k-1}-1+2^{k-1}=\underbrace{2\cdot2^{k-1}}_{=2^{k}}-1=2^{k}-1. \end{equation} Esto es absurdo. Esta contradicción demuestra que nuestra suposición era errónea. Por lo tanto, la prueba del Lemma 2 (a) está completo.

(b) Lema 2 (a) muestra que ambos números $i$ et $2^{k}-i-1$ son elementos de $\left[ n\right] ^{\prime}$ y al menos uno de ellos es $\geq2^{k-1}$ . Nos encontramos, pues, en uno de los dos casos siguientes:

Caso 1: Tenemos $i\geq2^{k-1}$ .

Caso 2: Tenemos $2^{k}-i-1\geq2^{k-1}$ .

Consideremos primero el caso 1. En este caso, tenemos $i\geq2^{k-1}$ . Pero la permutación $\sigma$ es ágil. De ahí que el número $i+\sigma\left( i\right) +1$ es una potencia de $2$ (según la definición de "ágil"). En otras palabras, $i+\sigma\left( i\right) +1=2^{m}$ para algunos $m\in\mathbb{N}$ . Considere lo siguiente $m$ .

En $2^{m}=\underbrace{i}_{\geq2^{k-1}}+\underbrace{\sigma\left( i\right) }_{\geq0}+\underbrace{1}_{>0}>2^{k-1}$ obtenemos $m>k-1$ . Así, $m\geq k$ (ya que $m$ et $k$ son números enteros).

Por otro lado, $i\leq n-1$ (ya que $i\in\left[ n\right] ^{\prime}$ ) y $\sigma\left( i\right) \leq n-1$ (ya que $i\in\left[ n\right] ^{\prime}$ ). Por lo tanto, \begin{align*} 2^{m} & =\underbrace{i}_{\leq n-1}+\underbrace{\sigma\left( i\right) }_{\leq n-1}+1\leq\left( n-1\right) +\left( n-1\right) +1=2\underbrace{n} _{\leq2^{k}}-1\\ & \leq2\cdot2^{k}-1<2\cdot2^{k}=2^{k+1}. \end{align*} Por lo tanto, $m<k+1$ de modo que $m\leq k$ (ya que $m$ et $k$ son números enteros). Combinando con $m\geq k$ obtenemos $m=k$ . Por lo tanto, $2^{m}=2^{k}$ de modo que $i+\sigma\left( i\right) +1=2^{m}=2^{k}$ y así $\sigma\left( i\right) =2^{k}-i-1$ . Esto demuestra el lema 2 (b) en el caso 1.

Consideremos ahora el caso 2. En este caso, tenemos $2^{k}-i-1\geq2^{k-1}$ . Pero sabemos que $2^{k}-i-1$ es un elemento de $\left[ n\right] ^{\prime}$ . Por lo tanto, existe alguna $j\in\left[ n\right] ^{\prime}$ tal que $\sigma\left( j\right) =2^{k}-i-1$ (ya que $\sigma$ es una permutación de $\left[ n\right] ^{\prime}$ ). Considere lo siguiente $j$ . Tenemos $\sigma\left( j\right) =2^{k}-i-1\geq2^{k-1}$ . Pero la permutación $\sigma$ es ágil. De ahí que el número $j+\sigma\left( j\right) +1$ es una potencia de $2$ (por el definición de "ágil"). En otras palabras, $j+\sigma\left( j\right) +1=2^{m}$ para algunos $m\in\mathbb{N}$ . Considere lo siguiente $m$ .

En $2^{m}=\underbrace{j}_{\geq2^{k-1}}+\underbrace{\sigma\left( j\right) }_{\geq0}+\underbrace{1}_{>0}>2^{k-1}$ obtenemos $m>k-1$ . Así, $m\geq k$ (ya que $m$ et $k$ son números enteros).

Por otro lado, $j\leq n-1$ (ya que $j\in\left[ n\right] ^{\prime}$ ) y $\sigma\left( j\right) \leq n-1$ (ya que $j\in\left[ n\right] ^{\prime}$ ). Por lo tanto, \begin{align*} 2^{m} & =\underbrace{j}_{\leq n-1}+\underbrace{\sigma\left( j\right) }_{\leq n-1}+1\leq\left( n-1\right) +\left( n-1\right) +1=2\underbrace{n} _{\leq2^{k}}-1\\ & \leq2\cdot2^{k}-1<2\cdot2^{k}=2^{k+1}. \end{align*} Por lo tanto, $m<k+1$ de modo que $m\leq k$ (ya que $m$ et $k$ son números enteros). Combinando con $m\geq k$ obtenemos $m=k$ . Por lo tanto, $2^{m}=2^{k}$ de modo que $j+\sigma\left( j\right) +1=2^{m}=2^{k}$ y así $\sigma\left( j\right) =2^{k}-j-1$ . Comparando esto con $\sigma\left( j\right) =2^{k}-i-1$ encontramos $2^{k}-i-1=2^{k}-j-1$ . Por lo tanto, $i=j$ . Así, $\sigma\left( i\right) =\sigma\left( j\right) =2^{k}-i-1$ . Esto demuestra el lema 2 (b) en el caso 2.

Ahora hemos demostrado el Lemma 2 (b) tanto en el caso 1 como en el 2. Así pues, el lema 2 (b) siempre se mantiene.

Lema 3. Sea $n$ sea un número entero positivo. Sea $k$ b tal que $2^{k-1}<n\leq2^{k}$ . Sea $\sigma$ b $\left[ n\right] ^{\prime}$ .

(a) Tenemos $2^{k}-n<n$ .

(b) El mapa $\sigma$ conserva los dos subconjuntos $\left[ 2^{k} -n\right] ^{\prime}$ et $\left[ 2^{k}-n,n-1\right] $ de $\left[ n\right] ^{\prime}$ (en otras palabras, mapea cada uno de estos dos subconjuntos en sí mismo).

(c) Sea $\alpha$ sea la restricción de $\sigma$ al subconjunto $\left[ 2^{k}-n\right] ^{\prime}$ considerado como un mapa $\left[ 2^{k}-n\right] ^{\prime}\rightarrow\left[ 2^{k}-n\right] ^{\prime}$ . Entonces, $\alpha$ es un ágil permutación de $\left[ 2^{k}-n\right] ^{\prime}$ .

(d) Sea $\beta$ sea la restricción de $\sigma$ al subconjunto $\left[ 2^{k}-n,n-1\right] $ considerado como un mapa $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right] $ . Entonces, $\beta$ i permutación de orden inverso de este subconjunto (es decir, que como mapa).

Demostración del lema 3. (a) Tenemos $2^{k}=2\cdot\underbrace{2^{k-1}} _{<n}<2n=n+n$ de modo que $2^{k}-n<n$ . Esto demuestra el lema 3 (a) .

(b) Sea $i\in\left[ 2^{k}-n,n-1\right] $ . Por lo tanto, $2^{k}-n\leq i\leq n-1$ . Así, $i\in\left[ n\right] ^{\prime}$ et $i\geq2^{k}-n$ . Así pues, el lema 2 (b) muestra que \begin{equation} \sigma\left( i\right) =2^{k}-\underbrace{i}_{\leq n-1}-1\geq2^{k}-\left( n-1\right) -1=2^{k}-n. \end{equation} Combinando esto con $\sigma\left( i\right) =2^{k}-\underbrace{i}_{\geq 2^{k}-n}-1\leq2^{k}-\left( 2^{k}-n\right) -1=n-1$ obtenemos $\sigma\left( i\right) \in\left[ 2^{k}-n,n-1\right] $ .

Ahora, olvida que arreglamos $i$ . Así pues, hemos demostrado que $\sigma\left( i\right) \in\left[ 2^{k}-n,n-1\right] $ para cada $i\in\left[ 2^{k}-n,n-1\right] $ . En otras palabras, el mapa $\sigma$ conserva el subconjunto $\left[ 2^{k}-n,n-1\right] $ de $\left[ n\right] ^{\prime}$ . Desde $\sigma$ es una permutación de $\left[ n\right] ^{\prime}$ concluimos que que $\sigma$ también preserva el subconjunto complementario $\left[ n\right] ^{\prime}\setminus\left[ 2^{k}-n,n-1\right] =\left[ 2^{k}-n\right] ^{\prime}$ de $\left[ n\right] ^{\prime}$ . Así pues, el lema 3 (b) está demostrado.

(c) Lema 3 (b) muestra que la permutación $\sigma$ de $\left[ n\right] ^{\prime}$ conserva el subconjunto $\left[ 2^{k}-n\right] ^{\prime}$ de $\left[ n\right] ^{\prime}$ . Por lo tanto, se restringe a una permutación de este subconjunto $\left[ 2^{k}-n\right] ^{\prime}$ . Así, $\alpha$ es una permutación de $\left[ 2^{k}-n\right] ^{\prime}$ . Queda por demostrar que $\alpha$ es ágil. Pero esto está claro, porque $\alpha$ es una restricción de la permutación ágil $\sigma$ . Así pues, el lema 3 (c) está demostrado.

(d) Lema 3 (b) muestra que la permutación $\sigma$ de $\left[ n\right] ^{\prime}$ conserva el subconjunto $\left[ 2^{k}-n,n-1\right] $ de $\left[ n\right] ^{\prime}$ . Por lo tanto, se restringe a una permutación de este subconjunto $\left[ 2^{k}-n,n-1\right] $ . Así, $\beta$ es una permutación de $\left[ 2^{k}-n,n-1\right] $ . Cada $i\in\left[ 2^{k}-n,n-1\right] $ satisface \begin{align*} \beta\left( i\right) & =\sigma\left( i\right) \qquad\left( \text{since }\beta\text{ is a restriction of }\sigma\right) \\ & =2^{k}-i-1 \end{align*} (según el lema 2 (b) ya que $i\geq2^{k}-n$ ); por lo tanto, $\beta$ es el permutación de $\left[ 2^{k}-n,n-1\right] $ enviando cada $i$ a $2^{k}-i-1$ . En otras palabras, $\beta$ es la única permutación inversa de este subconjunto (es decir, es estrictamente decreciente como mapa). Por tanto, el lema 3 (d) está demostrado.

Definición. Sea $A$ et $B$ sean dos conjuntos disjuntos. Sea $\alpha$ sea un permutación de $A$ . Sea $\beta$ sea una permutación de $B$ . T \begin{equation} A\cup B\rightarrow A\cup B,\qquad x\mapsto \begin{cases} \alpha\left( x\right) , & \text{if }x\in A;\\ \beta\left( x\right) , & \text{if }x\in B \end{cases} \end{equation} es una permutación del conjunto $A\cup B$ . Esta permutación se denomina unión de $\alpha$ et $\beta$ y se denota por $\alpha\cup\beta$ .

Ahora estamos preparados para demostrar el Teorema 1:

Demostración del teorema 1. (a) Demostraremos el Teorema 1 (a) por fuerte sobre $n$ :

Fijar $n\in\mathbb{N}$ . Supongamos (como hipótesis de inducción) que para cada $g\in\mathbb{N}$ satisfaciendo $g<n$ existe una única permutación ágil $\sigma_{g}$ de $\left[ g\right] ^{\prime}$ . Queremos demostrar que existe una única permutación ágil $\sigma_{n}$ de $\left[ n\right] ^{\prime}$ .

Si $n\leq1$ es obvio (porque existe una permutación única de $\left[ n\right] ^{\prime}$ en este caso, y su agilidad es trivialmente trivialmente). Así pues, WLOG supone que $n>1$ . Por lo tanto, existe un único entero $k$ satisfaciendo $2^{k-1}<n\leq2^{k}$ (es decir, este $k$ es el más pequeño entero positivo $\ell$ satisfaciendo $2^{\ell}\geq n$ ). Considere lo siguiente $k$ . Nosotros tenemos $2^{k}-n<n$ (esto se demuestra como en el Lemma 3 (a) ). Por lo tanto, la hipótesis de inducción (aplicada a $g=2^{k}-n$ ) demuestra que existe una única permutación ágil permutación $\sigma_{2^{k}-n}$ de $\left[ 2^{k}-n\right] ^{\prime}$ . Considere lo siguiente $\sigma_{2^{k}-n}$ .

Sea $\gamma$ sea la única permutación inversa de orden del intervalo $\left[ 2^{k}-n,n-1\right] $ (es decir, el único mapa estrictamente decreciente $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right] $ ). Explícitamente, $\gamma$ viene dado por $\gamma\left( i\right) =2^{k}-i-1$ para cada $i\in\left[ 2^{k}-n,n-1\right] $ .

Las permutaciones $\sigma_{2^{k}-n}$ et $\gamma$ son permutaciones de dos subconjuntos complementarios de $\left[ n\right] ^{\prime}$ (es decir, de los subconjuntos $\left[ 2^{k}-n\right] ^{\prime}$ et $\left[ 2^{k}-n,n-1\right] $ , respectivamente). Por lo tanto, su unión $\sigma_{2^{k}-n}\cup\gamma$ es un permutación bien definida de $\left[ n\right] ^{\prime}$ . Además, esta permutación $\sigma_{2^{k}-n}\cup\gamma$ es ágil.

[ Prueba. Sea $i\in\left[ n\right] ^{\prime}$ . Debemos demostrar que el número $i+\left( \sigma_{2^{k}-n}\cup\gamma\right) \left( i\right) +1$ es una potencia de $2$ .

Si $i\in\left[ 2^{k}-n\right] ^{\prime}$ entonces $\left( \sigma_{2^{k}-n} \cup\gamma\right) \left( i\right) =\sigma\left( i\right) $ y así $i+\underbrace{\sigma\left( i\right) }_{=\sigma_{2^{k}-n}\left( i\right) }+1=i+\sigma_{2^{k}-n}\left( i\right) +1$ es una potencia de $2$ (ya que $\sigma_{2^{k}-n}$ es ágil). Así, si $i\in\left[ 2^{k}-n\right] ^{\prime }$ entonces hemos terminado. Por lo tanto, WLOG asume que $i\notin\left[ 2^{k}-n\right] ^{\prime}$ . Por lo tanto, $i\in\left[ n\right] ^{\prime} \setminus\left[ 2^{k}-n\right] ^{\prime}=\left[ 2^{k}-n,n-1\right] $ . Por lo tanto, $\left( \sigma_{2^{k}-n}\cup\gamma\right) \left( i\right) =\gamma\left( i\right) =2^{k}-i-1$ (según la definición de $\gamma$ ), de modo que $i+\left( \sigma_{2^{k}-n}\cup\gamma\right) \left( i\right) +1=2^{k}$ es un poder de $2$ . Esto completa esta prueba].

Por lo tanto, existe al menos una ágil permutación de $\left[ n\right] ^{\prime}$ (a saber, $\sigma_{2^{k}-n}\cup\gamma$ ).

Ahora, dejemos que $\sigma$ sea una permutación ágil de $\left[ n\right] ^{\prime}$ .

Lema 3 (b) muestra que el mapa $\sigma$ conserva los dos subconjuntos $\left[ 2^{k}-n\right] ^{\prime}$ et $\left[ 2^{k}-n,n-1\right] $ de $\left[ n\right] ^{\prime}$ .

Sea $\alpha$ sea la restricción de $\sigma$ al subconjunto $\left[ 2^{k}-n\right] ^{\prime}$ considerado como un mapa $\left[ 2^{k}-n\right] ^{\prime}\rightarrow\left[ 2^{k}-n\right] ^{\prime}$ . LEMA 3 (c) muestra que $\alpha$ es una permutación ágil de $\left[ 2^{k}-n\right] ^{\prime}$ . Así, $\alpha=\sigma_{2^{k}-n}$ (ya que $\sigma_{2^{k}-n}$ es el único ágil permutación $\sigma_{2^{k}-n}$ de $\left[ 2^{k}-n\right] ^{\prime}$ ).

Sea $\beta$ sea la restricción de $\sigma$ al subconjunto $\left[ 2^{k}-n,n-1\right] $ considerado como un mapa $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right] $ . LEMA 3 (d) muestra que $\beta$ es la única permutación inversa de este subconjunto. Por lo tanto, $\beta=\gamma$ (ya que la única permutación inversa de este subconjunto es $\gamma$ ).

La permutación $\sigma$ es la unión de las permutaciones $\alpha$ et $\beta$ (ya que $\alpha$ et $\beta$ son las restricciones de $\sigma$ a dos subconjuntos complementarios). Dicho de otro modo, $\sigma=\alpha\cup\beta$ . En vista de $\alpha=\sigma_{2^{k}-n}$ et $\beta=\gamma$ esto se reescribe como $\sigma =\sigma_{2^{k}-n}\cup\gamma$ .

Ahora, olvida que arreglamos $\sigma$ . Así pues, hemos demostrado que cada permutación $\sigma$ de $\left[ n\right] ^{\prime}$ satisface $\sigma =\sigma_{2^{k}-n}\cup\gamma$ . Por lo tanto, existe como máximo uno ágil permutación de $\left[ n\right] ^{\prime}$ . Como ya sabemos que existe existe al menos una tal permutación, concluimos pues que existe exactamente uno tal permutación. En otras palabras, existe una única permutación $\sigma_{n}$ de $\left[ n\right] ^{\prime}$ . Esto completa la paso de inducción. Por lo tanto, el Teorema 1 (a) está demostrado.

(b) Demostraremos el Teorema 1 (b) por inducción fuerte en $n$ :

Fijar $n\in\mathbb{N}$ . Supongamos (como hipótesis de inducción) que para cada $g\in\mathbb{N}$ satisfaciendo $g<n$ la única permutación ágil $\sigma_{g}$ de $\left[ g\right] ^{\prime}$ tiene signo $\left( -1\right) ^{\sigma_{g} }=\left( -1\right) ^{g\left( g-1\right) /2}$ . Queremos demostrar que el única permutación ágil $\sigma_{n}$ de $\left[ n\right] ^{\prime}$ tiene firmar $\left( -1\right) ^{\sigma_{n}}=\left( -1\right) ^{n\left( n-1\right) /2}$ .

Si $n\leq1$ entonces esto es obvio. Por lo tanto, WLOG supone que $n>1$ . Por lo tanto, existe existe un único número entero positivo $k$ satisfaciendo $2^{k-1}<n\leq2^{k}$ (a saber, este $k$ es el número entero positivo más pequeño $\ell$ satisfaciendo $2^{\ell}\geq n$ ). Considere lo siguiente $k$ . Observe que $k$ es positivo; por lo tanto, $2^{k}$ es par.

Tenemos $2^{k}-n<n$ (esto se demuestra como en el Lemma 3 (a) ). Por lo tanto, la hipótesis de inducción (aplicada a $g=2^{k}-n$ ) muestra que el único ágil permutación $\sigma_{2^{k}-n}$ de $\left[ 2^{k}-n\right] ^{\prime}$ tiene signo \begin{equation} \left( -1\right) ^{\sigma_{2^{k}-n}}=\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2}. \end{equation}

Sea $\gamma$ sea la única permutación inversa de orden del intervalo $\left[ 2^{k}-n,n-1\right] $ (es decir, el único mapa estrictamente decreciente $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right] $ ). Explícitamente, $\gamma$ viene dado por $\gamma\left( i\right) =2^{k}-i-1$ para cada $i\in\left[ 2^{k}-n,n-1\right] $ .

Un hecho bien conocido dice lo siguiente: Si $m\in\mathbb{N}$ y si $M$ es un $m$ -de enteros, entonces la única permutación inversa de orden de del conjunto $M$ tiene signo $\left( -1\right) ^{m\left( m-1\right) /2}$ . Aplicando esto a $m=2n-2^{k}$ et $M=\left[ 2^{k}-n,n-1\right] $ concluimos que la única permutación inversa de orden del conjunto $\left[ 2^{k}-n,n-1\right] $ tiene $\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k} -1\right) /2}$ . Dado que esta permutación es $\gamma$ hemos demostrado que \begin{equation} \left( -1\right) ^{\gamma}=\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}. \end{equation}

En la demostración del teorema 1 (a) hemos demostrado que cada permutación ágil $\sigma$ de $\left[ n\right] ^{\prime}$ satisface $\sigma=\sigma_{2^{k} -n}\cup\gamma$ . Aplicando esto a $\sigma=\sigma_{n}$ concluimos que $\sigma_{n}$ satisface $\sigma_{n}=\sigma_{2^{k}-n}\cup\gamma$ .

Pero si $A$ et $B$ son dos conjuntos finitos disjuntos, y si $\alpha$ et $\beta$ son permutaciones de $A$ et $B$ (respectivamente), entonces la unión $\alpha \cup\beta$ de $\alpha$ et $\beta$ tiene signo $\left( -1\right) ^{\alpha \cup\beta}=\left( -1\right) ^{\alpha}\left( -1\right) ^{\beta}$ . Aplicando esto a $A=\left[ 2^{k}-n\right] ^{\prime}$ , $B=\left[ 2^{k}-n,n-1\right] $ , $\alpha=\sigma_{2^{k}-n}$ et $\beta=\gamma$ concluimos que la unión $\sigma_{2^{k}-n}\cup\gamma$ tiene signo \begin{align*} \left( -1\right) ^{\sigma_{2^{k}-n}\cup\gamma} & =\underbrace{\left( -1\right) ^{\sigma_{2^{k}-n}}}_{=\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2}}\underbrace{\left( -1\right) ^{\gamma} }_{=\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}}\\ & =\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2}\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}\\ & =\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2+\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}\\ & =\left( -1\right) ^{n\left( n-1\right) /2} \end{align*} (ya que \begin{equation} \left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2+\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2\equiv n\left( n-1\right) /2\operatorname{mod}2 \end{equation} (porque \begin{align*} & \left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2+\left( 2n-2^{k} \right) \left( 2n-2^{k}-1\right) /2-n\left( n-1\right) /2\\ & =\left( n-2^{k}\right) \underbrace{\left( 2n-2^{k}\right) }_{\substack{\equiv0\operatorname{mod}2\\\text{(since }2^{k}\text{ is even)} }}\equiv0\operatorname{mod}2 \end{align*} )). Teniendo en cuenta $\sigma_{n}=\sigma_{2^{k}-n}\cup\gamma$ esto se reescribe como $\left( -1\right) ^{\sigma_{n}}=\left( -1\right) ^{n\left( n-1\right) /2}$ . Así que hemos demostrado que la única permutación ágil $\sigma_{n}$ de $\left[ n\right] ^{\prime}$ tiene signo $\left( -1\right) ^{\sigma_{n} }=\left( -1\right) ^{n\left( n-1\right) /2}$ . Esto completa el paso de inducción inducción. Por lo tanto, el Teorema 1 (b) está demostrado.

Observación. Nuestra demostración recursiva del Teorema 1 (a) puede utilizarse para demostrar que la permutación $\sigma_{n}$ es una involución (es decir, es igual a su propia inversa) y no tiene puntos fijos, excepto posiblemente $1$ (porque la permutación $\gamma$ es una permutación de orden inverso de un conjunto de tamaño par, y tales permutaciones nunca tienen puntos fijos). Por lo tanto, el tipo de ciclo de $\sigma_{n}$ es $\left( \underbrace{2,2,\ldots,2}_{n/2\text{ times}}\right) $ cuando $n$ es par, y $\left( \underbrace{2,2,\ldots,2}_{\left(n-1\right)/2\text{ times}},1\right) $ de lo contrario. Esto da otra forma de calcular el signo de $\sigma_{n}$ y por lo tanto de demostrar el Teorema 1 (b) .

Answer 2

Edito: a raíz de nuestro intercambio, modifico la presentación de lo que ahora es un resultado parcial.

Me atendré a sus anotaciones. Por ejemplo $H_8$ es el $2^3 \times 2^3 $ Matriz de Hankel:

$$H_{8}:=\begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1\\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \vdots &\vdots & \vdots & \vdots & \vdots\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Vamos a demostrar una versión restringida de su resultado, es decir, demostraremos que, para $k\geq 2$ :

$$\det(H_{2^k})=1$$

cumplir la fórmula $(-1)^{\binom{2^k}{2}}=(-1)^{\tfrac{2^k(2^k-1)}{2}}=1.$

Pongamos, por conveniencia notacional, $K_n=H_{2^n}$ .

$K_n$ posee una estructura recursiva con la forma :

$$\tag{1}K_{n+1}= \begin{pmatrix}K_{n} & J_{n}\\J_{n} & 0_{n}\end{pmatrix}$$

donde $J_n$ es la matriz antidiagonal (con unos en la diagonal secundaria) y $0_{n}$ es la matriz de todos los ceros, ambas de tamaño $2^n \times 2^n$ .

Ahora (1) permite trabajar por recursión para obtener $\det(K_n)$ utilizando la fórmula de Schur para $2 \times 2$ matrices definidas por bloques :

$$M=\begin{pmatrix}A & B\\C & D\end{pmatrix} \ \ \implies \ \ \det(M)=\det(A)det(D-CA^{-1}B)$$

dando aquí:

$$det(K_{n+1})=\det(K_n)\det(-JK_{n}^{-1}J)=\det(K_n)\det(-I)\det(J)\det(K_{n}^{-1})\det(J)=$$

$$det(-I)det(J_n^2)\det(K_nK_{n}^{-1})=(-1)^{2^n}=\begin{cases}-1 & (n=0)\\+1& (n>0) \end{cases}$$

(donde $I$ denota la matriz identidad con $2^n \times 2^n$ elementos).

Explicaciones: $\det(J_n^2)=\det(I)=1$ et $\det(-I_k)=(-1)^k$ .

---

Un programa Matlab para la generación recursiva de matrices $K_{2^p}$ (aquí con $p=2$ ):

p=2;
K=[1];J=[1];Z=[0];
for k=1:p
   K=[K,J;J,Z]
   J=[Z,J;J,Z];
   Z=[Z,Z;Z,Z];
end;
K

Edición : Me pregunto si no se podría conseguir una solución sencilla utilizando el [Teorema de Lucas] ( https://en.wikipedia.org/wiki/Lucas%27s_theorem )