Rango de un $n! \times n$ matriz

Question

Esta pregunta trata de demostrar que $n!$ puntos resultantes de aplicar una función (definida a continuación) a las permutaciones de $n$ los números se encuentran en un $n-1$ hiperplano dimensional.

Dejemos que $X=\langle x_1,\cdots,x_n \rangle$ y $Y=\langle y_1,\cdots,y_n \rangle$ sean vectores de reales positivos y que $P=\langle p_1,\cdots,p_n \rangle$ sea una permutación de los números $\{1,\cdots,n\}$ . Déjalo,

$$ y_i=\log\left(1+\frac{x_i}{1+\sum\limits_{p_j<\,p_i}x_j}\right) $$ sea un mapeo desde $X,P$ a $Y$ . Así, para cualquier vector dado $X$ tenemos $n!$ (uno por cada permutación) vectores de salida $Y$ . Dejemos que $Y_P$ denotan un vector resultante de la permutación $P$ . Ahora, para un determinado $X$ crear una matriz $M$ tal que cada fila de la misma es $Y_P-Y_{P_1}$ para un fijo $P_1$ y para todos $P$ .

$$ M=\begin{bmatrix} Y_{P_1}-Y_{P_1} \\ Y_{P_2}-Y_{P_1} \\ \vdots \\ Y_{P_{n!}}-Y_{P_1} \end{bmatrix} $$

Así que, $M$ es un $n! \times n$ matriz. Tengo dos preguntas:

1. Supongo que el rango de $M$ es como máximo $n-1$ Es decir, todo $Y$ se encuentran en un hiperplano de dimensión $n-1$ (Lo he verificado para $n=3$ y $n=4$ ). ¿Es eso cierto o no? ¿Por qué?
2. Para qué tipo de mapeos de $X,P$ a $Y$ ¿la respuesta a la pregunta anterior es positiva?

Edita 3:

Me di cuenta de que para todas las permutaciones, $\sum_i y_i = \log(1+\sum_i x_i)$ y como comenta Chris Culter más abajo, ésta podría ser la solución al problema. La prueba de la desigualdad es larga, pero un ejemplo aclara su corrección: considere $n=3$ y $P=\langle 1, 2, 3 \rangle$ ,

$$ \begin{align} y_1+y_2+y_3&= \log(1+\frac{x_1}{1+x_2+x_3})+ \log(1+\frac{x_2}{1+x_3})+ \log(1+\frac{x_3}{1})\\ &= \log(\frac{1+x_1+x_2+x_3}{1+x_2+x_3})+ \log(\frac{1+x_2+x_3}{1+x_3})+ \log(\frac{1+x_3}{1})\\ &= \log(1+x_1+x_2+x_3). \end{align} $$

Dado que cualquier otra permutación sólo cambia el nombre de $x_1$ , $x_2$ y $x_3$ La salida sigue siendo la misma.

Editar 2:

El problema tiene una estructura específica que puede ayudar a resolverlo: El $n!$ Los puntos consisten en $n$ conjuntos de $(n-1)!$ puntos. Conjunto $i$ consiste en todos los puntos $Y_P$ tal que $i^{th}$ elemento de $P$ es 1. Por lo tanto, todos los puntos del conjunto $i$ tiene el mismo $y_i$ .

Por ejemplo, para $n=3$ , hay 3 conjuntos de 2 puntos (6 puntos en total). Todos los puntos se encuentran en un plano 2D. La siguiente figura muestra un ejemplo en 3D:

Los puntos del mismo conjunto tienen un mismo color. Las etiquetas junto a los puntos denotan la permutación que genera el punto. Así, los puntos 123 y 132 están en el conjunto 1, los puntos 213 y 312 están en el conjunto 2 (1 es el segundo elemento de su permutación), y los puntos 231 y 321 están en el conjunto 3 (1 es el tercer elemento de su permutación).

Para $n=4$ En el caso de los países de la Unión Europea, hay 4 conjuntos de 6 puntos (24 puntos en total). Como todos los puntos en 4D se encuentran en un plano 3D, podemos proyectar los puntos en el espacio 3D. He aquí un ejemplo:

Las dimensiones superiores se construyen recursivamente como se ha descrito anteriormente. Así, para $n=5$ Hay 5 conjuntos de la forma mostrada arriba (en 4D). Este carácter recursivo puede ser útil para resolver el problema.

Edita 3:

• Utilicé Mathematica para verificar mi conjetura para $n=3$ a $8$ y es correcto. Ver mi otra pregunta sobre Mathematica.SE . Para $n>8$ Debido al tiempo de ejecución exponencial del algoritmo, es difícil verificar la conjetura.

• La conjetura anterior también es válida para las siguientes funciones de mapeo:

$$ y_i={x_i}-{\sum\limits_{p_j<\,p_i}x_j} $$

$$ y_i={x_i}^3-{\sum\limits_{p_j<\,p_i}{x_j}^2} $$

• Pero no se cumple para las siguientes funciones:

$$ y_i=\log\left(\frac{x_i}{1+\sum\limits_{p_j<\,p_i}x_j}\right) $$

$$ y_i={x_i}^3-\left(\sum\limits_{p_j<\,p_i}x_j\right)^2 $$

Answer 1

Respuesta a la primera pregunta Como Chris Culter adivinó, la respuesta es SÍ y esto se debe a que $\sum_{i}y_i=\ln(1+\sum_{i} x_i)$ . La La prueba de esta última identidad no es difícil, es básicamente un cambio de índices y un uso cuidadoso de la notación (véase más adelante). Lo que tenemos aquí es una suma telescópica (o producto, según la forma en que se mire), pero dispuesta según un orden aleatorio (dependiendo de la permutación $p$ ).

$$ \begin{array}{lcl} e^{\prod_{i=1}^n y_i} &=&\prod_{i=1}^n e^{y_i} \\ &=& \prod_{i=1}^n \frac{1+x_i+\sum_{p(j)<p(i)}x_j}{1+\sum_{p(j)<p(i)}x_j} \\ &=& \prod_{I=1}^n \frac{1+x_{p^{-1}(I)}+\sum_{J<I}x_{p^{-1}(J)}} {1+\sum_{J<I}x_{p^{-1}(J)}} \ \text{(where we put } I=p(i),J=p(j) \text{)} \\ &=& \prod_{I=1}^n \frac{1+z_I+\sum_{J=1}^{I-1}z_J} {1+\sum_{J=1}^{I-1}z_J} \ \text{(where we put } z_I=x_{p^{-1}(I)} \text{)} \\ &=& \prod_{I=1}^n \frac{t_I} {t_{I-1}} \ \text{(where we put } t_I=1+\sum_{J=1}^{I}z_J \text{)} \\ &=& \frac{t_N} {t_0}=1+x_1+x_2+\ldots +x_n. \end{array} $$

Respuesta parcial a la segunda pregunta

Cuando $y_i$ es de la forma $A(x_i)-\sum_{p(j)<p(i)}B(x_j)$ donde $A$ y $B$ son funciones, su conjetura sigue siendo válida, porque

$$ \sum_{i}B(x_i)y_i=\sum_{i}A(x_i)B(x_i)-\frac{1}{2}\sum_{I\neq J}B(x_I)B(x_J) $$

Cuando $A(x)=x$ y $B(x)=x$ , se obtiene $y_i=x_i-\sum_{p(j)<p(i)}x_j$ .

Cuando $A(x)=x^3$ y $B(x)=x^2$ , se obtiene $y_i=x_i^3-\sum_{p(j)<p(i)}x_j$ .