Problema de optimización (en álgebra lineal, por supuesto!)

Question

Deje $a_1, a_2, \ldots, a_n$ ser números reales tales que a$a_1 + \cdots + a_n = 0$$a_1^2 + \cdots +a_n^2 = 1$. ¿Cuál es el máximo valor de $a_1a_2 + a_2a_3 + \cdots + a_{n - 1}a_n + a_na_1$?

Me gustaría hacer hincapié en que este se encuentra en un azar de álgebra lineal hoja de ejercicio así, uno podría esperar que no existe una solución inteligente basado en la manipulación de matrices...

Personalmente he intentado concebir el problema geométrica y analíticamente. En particular, $n=1$ no tiene ningún significado, $n=2$ da $-1$, $n=3$ da $-1/2$. Esto no revela mucho sobre el caso general, excepto por el hecho de que de Lagrange (sistema de derivadas parciales y all that jazz) parece implicar que CUALQUIER combinación de satisfacer las limitaciones que da el mismo valor (valor estoy tratando de maximizar) - pero esto necesita un poco más de cheques.

De vuelta al álgebra lineal I ver las trazas de las matrices, pero necesito algo simplemente expresar $A$ $B$ (ver abajo) en términos de uno a otro antes que a nada útil, que se puede hacer...

$$A = \operatorname{diag}(a_1,a_2,\ldots,a_{n-1},a_n);$$ $$B = \operatorname{diag}(a_2,a_3,\ldots,a_{n-1},a_n,a_1);$$

P. S. El problema fue originalmente tomado de este mismo foro , pero es bastante y viejos post y me parecen no ser capaces de dejar un comentario allí.

Answer 1

EDIT: Así que aquí vamos con una reescribir completamente en el lenguaje de álgebra lineal.

En $V=\mathbb C^n$ con el estándar de producto escalar $\langle e_j,e_k\rangle=\delta_{jk}$ lo considera lineal mapa $$\begin{matrix}\phi\colon &V&\longrightarrow &V\\ &(x_1,x_2,\ldots,x_{n-1},x_n)&\longmapsto&(x_2,x_3,\ldots,x_n,x_1), \end{de la matriz}$$ que es$e_1\mapsto e_n$$e_k\mapsto e_{k-1}$$1<k\le n$. El enunciado del problema nos pide para maximizar $\langle \phi a,a\rangle$ sujeto a las condiciones

$$\begin{align}\tag{c1}\langle a,v_n\rangle &= 0,\\ \tag{c2}\langle a,a\rangle&=1,&\text{and}\\ \tag{c3}a&\in \mathbb R^n.\end{align}$$

Deje $\zeta\in\mathbb C$ ser una primitiva $n$th raíz de la unidad, por ejemplo,$\zeta=e^{\frac{2\pi}n}=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n}$. Para $0\le k<n$ deje $$v_k=\sum_{\nu=1}^n \zeta^{\nu k}e_\nu=(\zeta^k,\zeta^{2k},\ldots ,\zeta^{nk}).$$ Entonces $$\langle v_k,v_k\rangle = n,\qquad\langle v_k,v_j\rangle=0\quad\text{for }j\ne k,\qquad \phi(v_k)=\zeta^kv_k,$$i.e. the $v_k$ are an orthogonal eigenvector basis of $V$. Por lo tanto si $$\tag1a=\sum_{k=1}^n c_kv_k$$ with $c_k\in\mathbb C$, then $$\langle a,a\rangle = n\sum_{k=1}^n|c_k|^2\qquad\text{and}\qquad\langle \phi a,a\rangle = n\sum_{k=1}^n \zeta^k|c_k|^2.$$

La condición (c$3$) implica que, sobre todo a $\langle \phi a,a\rangle \in\mathbb R$ y condición (c$1$) es simplemente que $c_n=0$$(1)$. De esto podemos obtener la envolvente de $$\begin{align}\langle \phi a,a\rangle& =n\sum_{k=1}^{n} \zeta^k|c_k|^2\\& =n\sum_{k=1}^{n-1} \zeta^k|c_k|^2\\&=n\Re\left(\sum_{k=1}^{n-1} \zeta^k|c_k|^2\right)\\&=n\sum_{k=1}^{n-1} \Re(\zeta^k)|c_k|^2\\\tag2&\le \max\bigl\{\Re(\xi)\mid \xi^n=1,\xi\ne1\bigr\}\cdot n\sum_{k=1}^{n-1}|c_k|^2\\&=\cos\frac{2\pi}{n}\cdot\langle a,a\rangle.\end{align}.$$ Tenga en cuenta que la especial elección $a=\frac 1{\sqrt n} (v_1+v_{n-1})=\frac 1{\sqrt n} (v_1+\overline{v_1})$ rendimientos $a\in \mathbb R^n$, $\langle a,a\rangle=1$ y la igualdad en $(2)$. Por lo tanto $$\max\bigl\{\langle \phi a,a\rangle\mid a\in\mathbb R^n,\langle a,a\rangle=1,\langle a,v_n\rangle=0\bigr\}= \cos\frac{2\pi}{n} .$$ Tenga en cuenta que para $n=2$$n=3$, podemos recuperar los resultados de la $\cos\pi=-1$$\cos\frac{2\pi}3=-\frac12$, confirmando lo que se encuentra.

Answer 2

El problema puede ser resuelto en términos de álgebra lineal.

Hay una base ortonormales $(e_0,e_1,\ldots,e_{n-1})$ $\Bbb R^n$ que diagonalizes la forma cuadrática $$f(x):=\sum_i x_i x_{i+1}\ .$$ Al $(\xi_0,\ldots,\xi_{n-1})$ son los correspondientes cordinates la forma $f$ aparece como $$\tilde f(\xi)=\sum_{i=0}^{n-1}\lambda_i \xi_i^2\ .$$ El $e_i$ son vectores propios de la circulantes de la matriz $$A:={1\over2}\left[\matriz{ 0&1&0&0&0&1 \cr 1&0&1&0&0&0 \cr 0&1&0&1&0&0 \cr 0&0&1&0&1&0 \cr 0&0&0&1&0&1 \cr 1&0&0&0&1&0 \cr}\right]\ ,$$ dibuja aquí para el caso en $n=6$, y el $\lambda_i$ son los correspondiente (real) autovalores. De curso $e_0={1\over\sqrt{n}}(1,1,\ldots,1)$. Como todos los $e_i$ $i\geq1$ son ortogonales $e_0$ $e_i$ automáticamente satisfacer la restricción lineal "$\sum_k a_k=0$". De ello se sigue que $$\max\bigl\{f(a)\ \bigm|\ {\rm ``constraints''}\bigr\}=\max\left\{\sum_{i=1}^{n-1}\lambda_i \xi_i^2\ \biggm|\ \sum_{i=1}^{n-1} \xi_i^2=1\right\}=\max_{1\leq i\leq n-1}\lambda_i\ .$$ Para calcular el $\lambda_i$ nota de que el $n$ vectores complejos $$c_j:=(1,\omega^j,\omega^{2j},\ldots,\omega^{(n-1)j})\qquad(0\leq j\leq n-1)\ ,$$ donde $\omega:=e^{2\pi i/n}$, son linealmente independiente de vectores propios de a $A$. Los valores propios son ahora inmediato; el más grande, aparte de $\lambda_0=1$$\alpha:=\cos{2\pi\over n}$. Este valor $\alpha$ es la solución a nuestro problema; el es $>0$ todos los $n\geq5$.

Answer 3

EDIT: Aquí hay una respuesta que utiliza una cantidad mínima de complejo de la aritmética.

Considere la posibilidad de $$ H := \frac{1}{2} \begin{bmatrix} 0 & 1 & & & & & 1 \\ 1 & 0 & 1 & & & & \\ & 1 & 0 & 1 & & & \\ & & \ddots & \ddots & \ddots & & \\ & & & 1 & 0 & 1 & \\ & & & & 1 & 0 & 1 \\ 1 & & & & & 1 & 0 \end{bmatrix}. $$ Entonces el problema puede ser reescrita $$ \max_v \ v^T H v \quad \text{objeto} \ e^T v = 0, \ \|v\|_2 = 1, $$ donde $e = (1, 1, \ldots, 1)$. El problema se reduce a encontrar el mayor autovalor de a $H$ y uno de sus vectores propios asociados en el subespacio $e^T v = 0$. Es fácil comprobar que cuando $n > 2$, $v_1 := \frac{1}{\sqrt{n}} (1, 1, \ldots, 1)$ siempre es un autovector de a $H$ asociado al autovalor $1$.

Pero $H$ es un circulantes de la matriz, es real y simétrica. Cuando $n=2$, $H$ es $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ cuyo mayor autovalor es $+1$. Para cualquier $n > 2$, las propiedades de las matrices circulantes implica que el mayor autovalor de a $H$ siempre $1$. Así que ahora el problema se reduce a encontrar el segundo mayor autovalor de a $H$ y un vector propio asociado.

De acuerdo con Gris los valores propios de una circulantes de la matriz son la transformada de Fourier discreta (DFT) de su primera fila. La notación estándar para la primera fila de un circulantes de la matriz es $$ \begin{bmatrix} c_0 & c_{n-1} & c_{n-2} & \cdots & c_1 \end{bmatrix}. $$ Aquí $c_1 = c_{n-1} = 1/2$ y todos los demás son cero. La DFT de esta secuencia está dada por $$ \lambda_k = \sum_{j=0}^{n-1} c_j \, e^{-i j k 2\pi / n} = \tfrac{1}{2} 2 \cos(2 k \pi / n) = \cos(2 k \pi / n), \quad k = 0, \ldots, n-1, $$ es decir, una verdadera secuencia (por suerte, porque $H$ es simétrico!) El mayor autovalor, obtenidos por $k=0$, de hecho es $1$. La segunda es $\cos(2\pi/n)$.

Answer 4

Una solución parcial, pero necesita más de matemáticas de la que cabe en un comentario :-(

A partir de una idea en Lohwater las "Desigualdades":

Tenemos, aplicando el AM-GM de la desigualdad hasta la saciedad: $$ \begin{align*} a_1^2 + a_2^2 &\ge 2 a_1 a_2 \\ a_2^2 + a_3^2 &\ge 2 a_2 a_3 \\ \vdots\\ a_{n - 1}^2 + a_n^2 &\ge 2 a_{n - 1} a_n \\ a_n^2 + a_1^2 &\ge 2 a_n a_1 \end{align*} $$ Sumando todo el lío y dividiendo por 2: $$ a_1^2 + a_2^2 + \ldots + a_n^2 \ge a_1 a_2 + a_2 a_3 + \ldots + a_n a_1 $$ Esto demuestra que la suma es 1.

Otra idea para obtener una mayor enlazado: Vamos a $n = 2 k$ donde $k \ge 2$, y tome $a_i = \frac{1}{\sqrt{n}}$ si $1 \le i \le k$, $a_i = - \frac{1}{\sqrt{n}}$ si $k < i \le k$. Entonces, las sumas: $$ \begin{align*} a_1 a_2 + \ldots + a_{k - 1} a_k &= \frac{k - 1}{n} \\ a_{k + 1} a_{k + 2} + \ldots + a_{2 k - 1} a_{2 k} &= \frac{k - 1}{n} \\ a_{2 k} a_1 = a_k a_{k + 1} &= - \frac{1}{n} \end{align*} $$ La adición de da $a_1 a_2 + \ldots a_n a_1 = \frac{n - 4}{n}$.

La misma idea funciona siempre como $n \ge 4$; considerar la posibilidad de un tramo de $k$ positivos y un tramo de $n - k$ negativos, dando dos pasos cambiando los signos de envoltura alrededor. Los tramos dar $(k - 1) + (n - k - 1) = n - 2$ pares que se multiplican a $\frac{1}{n}$ y dos productos de $- \frac{1}{n}$ para los pasos, para un total de $\frac{n - 4}{n}$.

Answer 5

Otra respuesta parcial. Creo que la clave es pensar geométricamente acerca de esto. Sus limitaciones describir la intersección de la unidad de la esfera con el vector del subespacio ortogonal a $(1, 1, \ldots, 1)$.

Para $n=2$, el problema es $$ \min \ -2xy \quad \text{objeto} \ x+y=0, \ x^2 + y^2 = 1. $$ La introducción de multiplicadores de Lagrange, el primer orden de optimalidad de condiciones puede ser escrito \begin{align*} -2y - \lambda_1 - 2 x \lambda_2 & = 0, \\ -2x - \lambda_1 - 2 y \lambda_2 & = 0, \\ x + y & = 0, \\ x^2 + y^2 & = 1. \end{align*} Agregar las dos primeras ecuaciones y el uso de $x+y=0$, nos encontramos con $\lambda_1 = 0$. Esto significa que la función objetivo de forma natural toma su valor máximo en el avión $x+y=0$, por lo que esta restricción podría ser eliminado sin cambiar la solución. Ahora vemos que $\lambda_2 = 1$$x=-y=\pm 1 / \sqrt{2}$. El objetivo óptimo valor es $-1$ (o $+1$ si volvemos al problema de maximización).

Para $n = 3$, en el mismo caso que el anterior, nos encontramos con $\lambda_1 = 0$$\lambda_2 = 1/2$. Así como usted dice, cualquier $(x,y,z)$ la satisfacción de las limitaciones que da el mismo valor objetivo. Como usted dice, este valor es $-1/2$.

Supongo que el punto de este ejercicio es mostrar que el objetivo es constante a lo largo de ciertos puntos suspensivos.

Para general $n$, las condiciones de optimalidad son \begin{align*} -a_2 - a_n - \lambda_1 - 2 a_1 \lambda_2 & = 0, \\ -a_{i+1} - a_{i-1} - \lambda_1 - 2 a_i \lambda_2 & = 0, \\ -a_{n-1} - a_1 - \lambda_1 - 2 a_n \lambda_2 & = 0, \\ \sum_{i=1}^n a_i & = 0, \\ \sum_{i=1}^n a_i^2 & = 1. \end{align*} La suma de los primeros tres conjuntos de ecuaciones, tenemos de nuevo $\lambda_1 = 0$. Después de la extracción $\lambda_1$ de los primeros tres conjuntos de ecuaciones, el cuadrado de ellos y la adición de ellos juntos, puedo llegar $$ \lambda_2 = \pm \frac{1}{\sqrt{2}} \sqrt{1 - f(un)}, $$ donde $f(a) = -\sum_{i=1}^{n-1} a_i a_{i+1} - a_n a_1$ es el objetivo a ser minimizada. Voy a ser feliz para completar mi respuesta cuando me descubra más, pero esto ya puede poner en la pista.