La maximización de una suma de productos de interior

Question

Alguien hizo esta pregunta en un francés de matemáticas en el foro de aquí y me llamó la atención.

La pregunta es la siguiente: vamos a $(E, \langle \cdot, \cdot \rangle)$ ser un espacio vectorial Euclídeo. Encontrar los posibles valores mínimo y máximo de la suma de $$\langle u_1, u_2 \rangle + \langle u_2, u_3 \rangle + \dots + \langle u_{n-1}, u_n \rangle + \langle u_n, u_1 \rangle$$ cuando la $u_k$ son de la unidad de vectores cuya suma es cero.

$$ $$ $$ $$

Edit: Vale, ya que no hay ninguna respuesta hasta ahora, permítanme escribir aquí lo que se me ocurrió, tal vez alguien va a saber cómo seguir. Por supuesto, podría ser un enfoque mucho mejor!

Vamos a introducir un par de anotaciones. Deje $E^n$ el valor del $n$veces con espacio en su interior el producto derivado de $E$ (*) y deje $\varphi$ $\psi$ denotar las funciones definidas por: $$ \varphi: \left\{ \begin{array}{ccc} E^n & \rightarrow &\mathbb{R} \\ u = (u_1, \dots, u_n) &\mapsto & \langle u_1, u_2 \rangle + \dots + \langle u_n, u_1 \rangle \end{array} \right.$$ $$ \psi: \left\{ \begin{array}{ccc} E^n & \rightarrow &\mathbb{R}^n \times E \\ u = (u_1, \dots, u_n) &\mapsto & \left((||u_i||^2 - 1)_{k= 1 \dots n}\,,\, \sum_{k=1}^n u_k\right)\\ \end{array} \right.$$

Así que la pregunta es: encuentre los extremos de $\varphi$ en el conjunto de nivel de $K := \{\psi = 0\}$. Tenga en cuenta que $K$ es compacto (NB: se parece a una "rebanada" de una $n$veces producto de hyperspheres, lo que sea) lo $\varphi$ tiene un mínimo y un máximo en $K$ de hecho. Cuáles son sus valores?

Vamos a ver lo que el cálculo diferencial nos dice (**). Deje $u = (u_1, \dots, u_n)$ ser un local del extremo de $\varphi_{|K}$. La derivada de $\varphi$ $u$ debe matar a los vectores de tangentes a $K$, lo que equivale a decir que el $\mathrm{Ker}\, D_u \psi \subset \mathrm{Ker}\, D_u \varphi$. Es muy sencillo para calcular estos derivados y sus núcleos, que están dados por: $$ \mathrm{Ker}\, D_u \varphi = \{v\}^\perp$$ donde $v = (u_n + u_2, u_1 + u_3, \dots, u_{n-1} + u_1) \in E^n$, y $$ \mathrm{Ker}\, D_u \psi = ({L_1}^\perp \times \dots \times {L_n}^\perp) ~ \cap ~ \Delta^\perp$$ donde $L_k$ indica la línea a través de $u_k$ $E$ $\Delta$ denota la diagonal en $E^n$.

La condición de $\mathrm{Ker}\, D_u \psi \subset \mathrm{Ker}\, D_u \varphi$, que equivale a decir que $v \in ({L_1}\times \dots \times {L_n}) ~ + ~ \Delta$.

En conclusión: si $u = (u_1, \dots, u_n)$ es un extremo local de $\varphi$ restringido a $K$, entonces existe escalares $\lambda_1, \dots, \lambda_n$ y un vector $a \in E$ tal forma que: $$\begin{align*} u_n + u_2 &= \lambda_1 u_1 + a \\ u_1 + u_3 &= \lambda_2 u_2 + a \\ & \cdots \\ u_{n-1} + u_1 & = \lambda_n u_n + a \end{align*}$$

¿Qué podemos obtener de esto? En primer lugar, tenga en cuenta que $a$ está dado por $0 = \sum_{k=1}^n \lambda_k u_k + na$ (suma de todas las ecuaciones). Además, el valor de $\varphi$ en este punto $u$ está dado por $\sum_{k=1}^n \lambda_k / 2$. Lo que es más importante, es fácil ver inductivamente que todas las $u_k$ se encuentran en un mismo $3$-dimensiones subespacio de $E$.

Eso es todo lo que yo podría derivar a partir de estas ecuaciones por desgracia. Pero creo que debería ser posible para obligarlos a confesar más, tal vez usando un argumento de simetría. Aquí es lo que sospecho: $a$ debe $0$ y todos los $\lambda_k$ debe ser igual. De ello se desprende que todas las $u_k$ son coplanares y que el ángulo entre el $u_k$ $u_{k+2}$ es constante. Finalmente, en pocas palabras, se rompen en los casos de acuerdo a si $n$ es par o impar. En ambos casos, el máximo es alcanzado cuando el $u_k$ mentira como $n$-th raíces de la unidad en el círculo, y es dado por $n \cos (2\pi / n)$. Al $n$ es incluso, el mínimo es de $-n$ (solo tome $u_1 = u_3 = \dots = u_{n-1} = -u_2 = -u_4 = \dots = -u_n$) y al $n$ es impar, $-n \cos(2\pi/n)$ (no totalmente seguro de esto último).

Wow, esto es mucho más de lo que esperaba, espero no aburrir demasiado a muchas personas a la muerte.

$$ $$ $$ $$

(*) Es dado por $\langle u, v \rangle = \sum_{k=1}^n \langle u_k, v_k \rangle$.

(**) en lo que sigue, puedo recuperar alguna versión de multiplicador de Lagrange "manualmente". Usted puede saltar esa parte y saltar a la del conjunto de ecuaciones lineales si no te gusta lo que ves :)

Answer 1

Para $d={\rm dim}(E)\ge2$ $n\ge2$ tenemos límites $$ L_n\le\langle u_1,u_2\rangle+\langle u_2,u_3\rangle+\cdots+\langle u_n,u_1\rangle\le U_n $$ donde $$ \begin{align} L_n&=\begin{cases} -n,&{\rm for\ }n{\rm\ even},\\ -n\cos(\pi/n),&{\rm for\ }n{\rm\ odd} \end{casos} \cr\cr U_n&=n\cos(2\pi/n). \end{align} $$ Para su comodidad, usaré $Q(u)$ para denotar la suma de $\sum_{k=1}^n\langle u_k,u_{k+1}\rangle$, y el subíndice $k$ $u_k$ será tomado modulo $n$, de modo que, en particular, $u_{n+1}=u_1$. Los límites anteriores pueden ser alcanzados mediante la toma de $u_k$ de la forma $$ u_k=\cos(2\pi jk/n)e_1+\sin(2\pi jk/n)e_2 $$ donde $e_1,e_2\in E$ es ortogonal par de vectores unitarios y $j$ fijo es un número entero. A continuación, $\langle u_k,u_{k+1}\rangle = \cos(2\pi j/n)$$Q(u)=n\cos(2\pi j/n)$. Además, $\sum_ku_k=0$ mientras $j$ no es un múltiplo de a $n$. Tomando $j=1$ da $Q(u)=U_n$. El límite inferior es alcanzado por $j=n/2$ incluso $n$ $j=(n-1)/2$ por extraño $n$.

Que solo queda demostrar que los límites $L_n\le Q(u)\le U_n$ hecho pulsado para cualquier elección de $u_k$ de la unidad de vectores con $\sum_{k=1}^nu_k=0$.

Límite inferior: límite inferior contiene de hecho sin la restricción de que $\sum_ku_k=0$. Incluso para $n$, esto es fácil. Como $\langle u_k,u_{k+1}\rangle\ge-1$, tenemos $$ Q(u)\ge\sum_{k=1}^n(-1)=-n=L_n. $$ Voy a considerar ahora extraño $n\ge3$. Por compacidad, podemos encontrar la unidad de vectores $u_k$ minimizar $Q(u)$. Para cualquier $\eta_k$ ortogonal a $u_k$, y la sustitución de $u_k$$(u_k+\epsilon\eta_i)/\sqrt{1+\epsilon^2\lvert\eta_k\rvert^2}$, la cantidad de $Q(u)$ varía por $\epsilon\langle\eta_k,u_{k-1}+u_{k+1}\rangle$ a primer orden en $\epsilon$. Como esta debe de desaparecer en el mínimo de$Q$, $u_k$ paralelo a $u_{k+1}+u_{k-1}$. Por eso, $u_{k-1}+u_{k+1}=\lambda_ku_k$ para escalares $\lambda_k$.Los términos en $Q(u)$ involucran $u_k$ $$ \langle u_{k-1},u_k\rangle+\langle u_k,u_{k+1}\rangle=\langle u_k,u_{k-1}+u_{k+1}\rangle=\lambda_k. $$ Si $\lambda_k=0$ cualquier $k$, entonces los términos relacionados con la $u_k$ desaparecen, por lo $Q(u)$ es una suma de $n-2$ interior de los productos, dando, $$ \begin{align} Q(u)&\ge-(n-2)\ge-n+\frac{\pi^2}{6}\ge-n+\frac{\pi^2}{2n}\\ &=-n\left(1-\frac{\pi^2}{2n^2}\right)\ge-n\cos(\pi/n)=L_n \end{align} $$ como se requiere. Sólo queda mostrar que el límite inferior se mantiene en el caso de que todos los $\lambda_k$ son cero. Como $u_{k+1}=\lambda_ku_k-u_{k-1}$, $u_{k+1}$ está en el subespacio generado por $u_{k-1},u_k$. Por inducción entonces, todas las $u_k$ mentira en el subespacio generado por $u_1,u_2$. Esto nos reduce al caso en que ${\rm dim}(E)=2$. Para los métodos de representación de la conveniencia, podemos tomar $E$ a ser el plano complejo con producto interior $\langle u,v\rangle=\Re[\bar uv]$. Para cualquier $k$, si fijamos $\omega_k=u_k/u_{k-1}$,$\omega_{k+1}\omega_k+1=\lambda_k\omega_k$. En particular, $\omega_{k+1}+\bar\omega_k=\lambda_k$ es real y distinto de cero, dando a $\omega_{k+1}=\omega_k$. Por lo tanto, $\omega_k=\omega_1$ todos los $k$ y tenemos $u_k=\omega^ku_0$ fija por unidad de vectores $u_0,\omega$. Cumplimiento $u_{n+1}=u_1$ da $\omega^n=1$, a partir de la cual vemos que el mínimo de $Q$ se obtiene en $u_k=u_0\exp(2\pi ikm/n)$ fijo entero $m$. Esto le da $$ Q(u)=\sum_{k=1}^n\Re[\bar u_k u_{k+1}]=\sum_{k=1}^n\cos(2\pi m/n)=n\cos(2\pi m/n). $$ Para $n$ raro, esta tenga un mínimo de $-n\cos(\pi/n)=L_n$$m=(n-1)/2$.

Límite superior:

Esto es donde las cosas se ponen difíciles. Los valores pequeños de a $n$ requieren de un tratamiento especial, y los valores grandes requieren algunos no trivial de la geometría de la esfera.

Caso I ($n\le6$): voy a hacer uso de la astucia método utilizado por el cartel de JLT aquí que, para $n=5,6$, gira en torno a los límites inferiores de arriba para obtener los límites superiores en la $Q(u)$. Solo para unificar el enfoque, que incluyen casos $n=2,3,4$ utilizando el mismo método (aunque, en esos casos, los límites inferiores no son necesarios). El método que se describe a continuación también puede ser aplicado por $n\ge7$ a pesar de que, entonces, los límites superiores no son óptimas. Como $\sum_ku_k=0$, se puede ampliar $$ \begin{align} 0=\left\lVert\sum_ku_k\right\rVert^2=n+\sum_{j\not=k}\langle u_j,u_k\rangle.&&{\rm(1)} \end{align} $$ Para $n=2$, esto le da a $0=2+Q(u)$, por lo que el $Q(u)=-2=U_2$. Para $n=3$ da $0=3+2Q(u)$, por lo que el $Q(u)=-3/2=U_3$. Para $n=4$, da $$ 0=4+\sum_{k=1}^4\langle u_k,u_{k+2}\rangle+2Q(u)\ge2Q(u). $$ Por eso, $Q(u)\le0=U_4$. Tenga en cuenta que, alternativamente, como ha señalado Pedro Košinár en los comentarios de abajo, podemos escribir $Q(u)=-\lVert u_1+u_3\rVert^2\le0$.

Para $n=5$, (1) da $$ \begin{align} 0&=5+2Q(u)+2\sum_{k=1}^5\langle u_k,u_{k+2}\rangle\\ &=5+2Q(u)+2\sum_{k=1}^5\langle u_{2k},u_{2(k+1)}\rangle\\ &\ge5+2Q(u)+2L_5. \end{align} $$ Aquí, he conectado en los límites inferiores demostrado arriba, así que, con $L_5=-5\cos(\pi/5)$, $$ Q(u)\le5\left(\cos(\pi/5)-1/2\right)=5\cos(2\pi/5)=U_5. $$

Para $n=6$, (1) da $$ \begin{align} 0&=6+2Q(u)+\sum_{k=1}^6\langle u_k,u_{k+3}\rangle+2\sum_{k=1}^6\langle u_k,u_{k+2}\rangle\\ &\ge6+2Q(u)+(-6)+2\sum_{k=1}^3\langle u_{2k},u_{2(k+1)}\rangle+2\sum_{k=1}^3\langle u_{1+2k},u_{1+2(k+1)}\rangle\\ &\ge 2Q(u)+2L_3+2L_3. \end{align} $$ La primera desigualdad aquí usa el $\langle u_k,u_{k+3}\rangle\ge-1$ y la segunda utiliza el límite inferior demostrado anteriormente. Poniendo en $L_3=-3\cos(\pi/3)$ da $Q(u)\le U_6$.

Caso II ($n\ge7$): voy a tratar grandes valores de $n$ utilizando un enfoque completamente diferente de la utilizada anteriormente para las pequeñas $n$, y se basan en los siguientes intuitiva resultado sobre las curvas en la unidad de la esfera.

Lema 1: Vamos a $\gamma$ ser una curva cerrada en la unidad de la esfera en $E$ cuyo casco convexo que contiene el origen. A continuación, $\gamma$ tiene una longitud de, al menos,$2\pi$.

Para ${\rm dim}(E)=3$, esto se desprende de la Crofton fórmula, ya que casi todos los geodésica en la unidad 2-esfera debe intersectar $\gamma$ al menos dos veces. Alternativamente, una prueba es dada aquí por las curvas en la 2-esfera (Lema 2.14), y la prueba se generaliza directamente arbitraria de las dimensiones.

Ahora, vamos a $d(u_k,u_{k+1})$ ser la distancia entre los puntos de $u_k,u_{k+1}$ a lo largo de la unidad de la esfera (o, equivalentemente, el ángulo entre el $u_k,u_{k+1}$), por lo $\langle u_k,u_{k+1}\rangle=\cos(d(u_k,u_{k+1}))$. La condición de que $\sum_ku_k=0$ significa que el Lema 1 se aplica y tenemos $$ \sum_{k=1}^nd(u_k,u_{k+1})\ge2\pi. $$ Para $n\ge7$, esto implica que $$ Q(u)=\sum_{k=1}^n\cos(d(u_k,u_{k+1}))\le n\cos(2\pi/n)=U_n. $$ Voy a demostrar que esta desigualdad se sigue de un lexema.

Lema 2: Para $n\ge7$, vamos a $\theta_1,\ldots,\theta_n\in[0,\pi]$ ser tal que $\sum_{k=1}^n\theta_k\ge2\pi$. A continuación, $\sum_k\cos\theta_k\le n\cos(2\pi/n)$, con la desigualdad estricta a menos que todos los $\theta_k$ igual $2\pi/n$.

Prueba: Elija $\theta_k\in[0,\pi]$ a maximizar $\varphi(\theta)=\sum_k\cos\theta_k$ sujeto a la restricción $\sum_k\theta_k\ge2\pi$. Como $\cos$ es estrictamente decreciente, tenemos $\sum_k\theta_k=2\pi$. Esto implica que al menos $n-4$ de la $\theta_k$ son estrictamente menor que $\pi/2$.

Si no existe $i,j$ con distintos $\theta_i,\theta_j$ $[0,\pi/2]$ a continuación, estricta concavidad de $\cos$ en este rango de da $$ \cos\left((\theta_i+\theta_j)/2\right)+ \cos\left((\theta_i+\theta_j)/2\right) > \cos\theta_i+\cos\theta_j. $$ Así, todos los $\theta_k$ $[0,\pi/2]$ son iguales. Esto muestra que hay un $\alpha\in[0,\pi]$ tal que $\theta_k$ se encuentran en el conjunto de $\{\alpha\}\cup(\pi/2,\pi]$. Ahora, supongamos que el $\theta_k\in(\pi/2,\pi)$ algunos $k$. Elegir distintos $i,j$$\theta_i=\theta_j=\alpha$, $$ \begin{align} \cos(\theta_i+\epsilon)+\cos(\theta_j+\epsilon)+\cos(\theta_k-2\epsilon)=&\cos\theta_i+\cos\theta_j+\cos\theta_k\\ &+2(\sin\theta_k-\sin\alpha)\epsilon\\ &-(\cos\alpha+2\cos\theta_k)\epsilon^2+O(\epsilon^3)&&{\rm(2)} \end{align} $$ Como estamos en un máximo local de $\varphi(\theta)$, esto implica que $\sin\theta-\sin\alpha=0$$\cos\alpha+2\sin\theta_k\ge0$. Sin embargo, la primera igualdad de da $\theta_k=\pi-\alpha$, $\cos\alpha+2\cos\theta_k=-\cos\alpha$ es estrictamente negativo. Esto le da una contradicción, por lo que todos los $\theta_k$ encuentran en el conjunto de $\{\alpha,\pi\}$. Además, si $\alpha=0$$\theta_k=\pi$, entonces el lado derecho de (2) es $1+\epsilon^2+O(\epsilon^3)$, contradiciendo de nuevo la condición de que $\varphi(\theta)$ es un máximo local. Esto significa que no más de uno de los $\theta_k$ igual $\pi$. De lo contrario, ya que suma a $2\pi$, tendríamos que tener $\alpha=0$.

Así, los siguientes son sólo los máximos locales de $\varphi(\theta)$.

1. Ninguno de los $\theta_k$ igual $\pi$. Entonces, todos ellos igual $\alpha$. Por eso, $n\alpha=2\pi$. Por eso,$theta_1=\cdots=\theta_n=2\pi/2$$\varphi(\theta)=n\cos(2\pi/n)$.
2. Una $\theta_k$ es igual a $\pi$ y el resto igual $\alpha$. Por eso, $\alpha=\pi/(n-1)$ y, $$ \varphi(\theta)=(n-1)\cos(\pi/(n-1))-1. $$ Este está delimitado por $n-2$, que es menos de $n\cos(2\pi/n)\ge n-2\pi^2/n$$n\ge10$, y se puede comprobar directamente que está delimitada por $n\cos(2\pi/n)$$n=7,8,9$.

Answer 2

Este es incompleta física motivado respuesta. Vamos a demostrar que la suma de interior de los productos con las restricciones dadas es equivalente a la energía de un $n$ elemento de la cadena de punto de masas confinado a una superficie esférica, conectadas por muelles. Su mínimo y máximo de la física de equilibrio de configuración, donde los objetos de forma simétrica, polígono equilátero.

Definir la norma en el espacio vectorial de la forma habitual $|u|=\sqrt{\langle u, u \rangle }$. Permítanos etiqueta $$ F = \langle u_1, u_2 \rangle + \langle u_2, u_3 \rangle + \dots + \langle u_{n-1}, u_n \rangle + \langle u_n, u_1 \rangle$$ Podemos darnos cuenta de que esto está estrechamente relacionado con la energía potencial de una cadena de punto de masas colocada en una unidad de la esfera en $u_i$ conectados por springs: $$V = \frac{1}{2}k|u_1-u_2|^2 + \frac{1}{2}k|u_2 - u_3|^2 + \dots + \frac{1}{2}k|u_n - u_1 |^2 - \sum_{i=1}^{n} \lambda_i (|u_i|^2-1) - \mu \left\langle\sum_{i=1}^{n} u_i, \epsilon\right\rangle \\ =- k F + \sum_{i=1}^n \left[(k - \lambda_i) |u_i|^2 + \lambda_i \right] - \mu \left\langle\sum_{i=1}^{n} u_i,\epsilon\right\rangle,$$ El primer $n$ términos en la primera ecuación representa la energía del resorte con constante de resorte $k$. Los resortes son atractivos si $k>0$ y repulsiva si $k<0$. Cada término en los últimos dos sumas se desvanece cuando el punto de masas están confinados a una unidad de la esfera y cuando su suma es cero arbitrario $\epsilon$ vector. Estos términos se introducen en la mecánica de Lagrange para representar la restricción de fuerzas, donde $\lambda_i$ son multiplicadores de Lagrange. Encontrar el mínimo/máximo de F $|u_i|=1$ $\sum_k u_k = 0$ es equivalente a encontrar el mínimo de la energía potencial $V$ por un resorte de constante $k=-1$ o $1$, respectivamente.

En física, un sistema de objetos está en equilibrio estático, si la energía potencial en un mínimo local. La fuerza sobre el objeto $i$ es $$f_i = -\partial V / \partial u_i^* = -k(u_i - u_{i+1}) - k(u_i - u_{i-1}) + 2\lambda_i u_i + 2\mu \epsilon \\= -k(u_i - u_{i+1}) - k(u_i - u_{i-1}) + 2\lambda_i u_i -2\sum_i\lambda_i u_i.$$ (Here $^*$ denotes the dual. We identify the index $i=0$ with $n$ and $n+el 1$ with $i=1$.) In the top line, the first two terms represent the forces arising from the two springs attached to the object and the last two terms are the constraint forces which ensures that the objects stay on the unit sphere and that their sum is zero. In the second line we have substituted the value of $\epsilon$ after solving the equations by summing $\sum_i f_i = 0$, and using the constraint $\sum_k u_k =0$.

En equilibrio, la fuerza neta $f_i$ es cero para cada una de las $i$. Si la masa se desplaza, la energía del sistema aumenta.

Estoy atrapado en el mismo escenario como el OP, ya que esta suma no puede ser cero. Los siguientes argumentos son válidos sólo en el caso de que sean cero, que resulta ser el caso, incluso,$n$.

$f_i=0$ por cada $i$ implica que los tres objetos $u_{i-1}$, $u_{i}$, y $u_{i+1}$ son linealmente dependientes para cada una de las $i$. En otras palabras, $u_{i-1}$, $u_{i}$, y $u_{i+1}$ se encuentran en un plano 2D. Además, $f_i=0$ implica que el $u_i$ es paralelo a $u_{i-1}+u_{i+1}$. El sistema en equilibrio se limita a 2 dimensiones, todas las $u_i$ túmbate en el ecuador de la $n$-esfera, en donde cada una de las $u_i$ es, precisamente, a mitad de camino entre el$u_{i-1}$$u_{i+1}$. Los puntos lapso de un triángulo polígono en 2D. (Sólo consideramos el caso en que el espacio vectorial es, al menos, 2D, de lo contrario la solución es trivial.) Podemos identificar la posición de cada objeto $$u_i = (\cos\phi_i)e_1 +(\sin\phi_i) e_2 $$ where $e_1$ and $e_2$ are arbitrary orthogonal unit vectors. Thus, local equilibrium requires $$\phi_i = i \phi_1 = 2 R \pi i/n.$$ Here $R$ must be an integer to ensure $f_n=0$ and $f_1=0$. Most generally $I\in\{1,2\dots n-1\}$. Note that $R=0$ is ruled out by the constraint given in the problem that $\sum_i u_i =0$ and $R\geq n$ and $R < 0$ are equivalent to $R {\;\rm mod\;}$ n.

Estos $n$ posibles soluciones comprenden todos los extremos locales de $F$ de las restricciones dadas. La comparación de sus valores se puede ver de inmediato que el global máximo y mínimo de $F$ corresponde a $R=1$$[n/2]$, respectivamente, donde $[n/2]$ denota el número entero más cercano a $n/2$. Por lo tanto $$F_{\max}=n \cos\frac{2\pi}{n}\quad{\rm and}\quad F_{\min}=n \cos\frac{2[n/2]\pi}{n}.$$