Skip to main content

Optimization of quadratic form with band matrices

Let $A_1$ be the $N \times N$-matrix for which $a_{i,j} = 1$ for $i=j$ and 0 otherwise. Let $A_2$ be the matrix for which $a_{i,j}=1$ for $|i-j| \leq 1$ and 0 otherwise. Similarly define $A_3$ (which has ones whenever $|i-j| \leq 2$), $A_4$, etc.

Set $$ s_m = (x_1, \dots, x_N) A_m (x_1, \dots, x_N)^T. $$ Note that $$ s_1=\sum_{k=1}^N x_k^2, $$ that $$ s_2 = \sum_{k=1}^N x_k^2 + 2 x_k x_{k+1}, $$ that $$ s_3 = \sum_{k=1}^N x_k^2 + 2 x_k x_{k+1} + 2 x_k x_{k+2}, $$ etc. (actually one has to restrict the summation ranges for the mixed terms a bit, but this is a minor point).

I am interested in the minimal possible value of $$ \max \Big( s_1, \frac{s_2}{2},\frac{s_3}{3},\frac{s_4}{4}, \dots, \frac{s_M}{M} \Big), $$ for some fixed $M$ (assume that $N \to \infty$), under the assumption that $\sum_{k=1}^N x_n = N$ and that all $x_k$'s are non-negative.

A trivial lower bound is N, since $s_1 = \sum x_k^2 \geq \sum x_k = N$. But my impression is that as $M \to \infty$ the value of this maximum should approach 2N.

Furthermore, is it true that as $M \to \infty$ the numbers $x_1, \dots, x_N$ arrange in such a way that they are all roughly of the same size, in order to minimize the maximum? (Note that this is not true for a single fixed $m$; for example, for $m=3$ the $x_k$'s would not arrange as $(1, \dots, 1)$ in order to minimize $s_3$, but rather as $(3,0,0,3,0,0,3,0,0,3,\dots)$.)