Find the maximum of the quadratic $\sum\limits_{1\le i<j\le n}\min\{(i-j)^2,(n+i-j)^2\}a_ia_j .$

Question

• Let $n$ be a given even number and $a_{1},a_{2},\ldots,a_{n}$ be non-negative real numbers such that $$ a_{1} + a_{2} + \cdots + a_{n} = 1. $$
• Find the maximum possible value of $$ \sum_{1\ \leq\ i\ <\ j\ \leq\ n} \min\left\{\left(i - j\right)^{2}, \left(n + i - j\right)^{2}\right\}a_{i}a_{j}. $$
• This problem may be a quadratic problem of linear algebra. In fact, this problem comes from a high school mathematics competition, so there may be a very simple method.

Answer 1

The maximum is $n^2/16$.

Let me rewrite the function somewhat. Consider the $n$ by $n$ matrix $M$ with entries $M_{ij}=\min((i-j)^2, (n-|i-j|)^2)$ and let $a$ the vector with components $a_1,\dots,a_n$. Then the function of the question is $f(a)=\frac12 a^TMa$ because the sum extends only to $i<j$.

We want to maximize $f(a)$ under the conditions that all $a_i$ are non-negative and $a_1+\cdots a_n=1$. We rewrite this as $a\geq0$ and $e^T\,a=1$ where $e=(1,\dots,1)^T$.

The problem is not so simple, because the matrix $M$ is not positive definite (the diagonal is zero!).

Observe that the rows of $M$ are cyclic permutations of each other and that $M$ is symmetric. This comes from the fact that $M_{ij}$ only depends upon $|i-j|$.

Now consider the vector $a_0=(1/2,0,\dots,0,1/2,0,\dots,0)^T$ with $1/2$ at positions $1$ and $\frac n2+1$. Then $f(a_0)=n^2/16$. Since the set of all vectors $a$ satisfying the conditions $a\geq0$, $e^T\,a=1$ is compact, $f$ has a maximum on this set. We denote by $z$ some vector where the maximum is attained. We want to show that $z$ equals $a_0$ except for a cyclic permutation and hence the maximum is $n^2/16$.

Claim 1: There exists $\lambda$ such that $Mz\leq2\lambda e$ and $(Mz)_i=2\lambda$ whenever $i\in S(z)$. Here $S(z)$ is the support of $z$, that is the set of indices $i$ such that $z_i\neq0$ and $(a)_i$ denotes the $i$-th component of a vector $a$.

Observe that then $f(z)=\lambda$ since $z^Te=1.$ The above conditions are the Kuhn-Tucker conditions for our optimisation problem, but they are easily derived here.

Proof: $\newcommand{\eps}{\varepsilon}$ Suppose first that $f(z)=\lambda$ and $(Mz)_i\neq2\lambda$ for some $i\in S(z)$. Then consider the vector $z+\eps e_i$, where $|\eps|$ is small and $e_i$ the $i$-th unit vector. We calculate $(z+\eps e_i)^T M (z+\eps e_i)=z^T M z +2\eps e_i ^T Mz +\eps^2e_i^TMe_i= 2\lambda+2\eps(Mz)_i$. Put $\tilde z=(1+\eps)^{-1}(z+\eps e_i)$. Then $e^T \tilde z=1$, $\tilde z\geq0$ and $\frac12\tilde z^TM\tilde z=(\lambda+\eps(Mz)_i)/(1+\eps)^2=\lambda+\eps((Mz)_i-2\lambda)+O(\eps^2)$, where $O(\eps^2)$ denotes terms that are smaller than $K|\eps|^2$ with some constant $K$. If $(Mz)_i>2\lambda$, we find that $f(\tilde z)>f(z)$ for small positive $\eps$ contrary to the assumption. If $(Mz)_i<2\lambda$, we conclude using a small negative $\eps$.

If $(Mz)_i>2\lambda$ for some $i$ for which $z_i=0$, then we obtain in the same way a contradiction for small positive $\eps$.

Claim 2: The support $S(z)$ is symmetric in the sence that $i\in S(z)$ if and only if $i+\frac n2\in S(z)$ for $i=1,\dots,\frac n2$.

Proof: This is the most tricky part! Suppose that the support is not symmetric. Using a cyclic permutation, we can assume that $z_{n/2}=0$, but $z_n>0$. Then we split $S(z)\setminus\{n\}$ into two parts: $S_+=\{i\in S(z)|i<n/2\}$ and $S_-=\{i\in S(z)|i>n/2,i\neq n\}$. Then by Claim $1$ $$(Mz)_n=\sum_{i\in S_+} i^2 z_i + \sum_{i\in S_-} (n-i)^2 z_i=2\lambda.$$ We calculate $$(Mz)_{n-1}=\sum_{i\in S_+} (i+1)^2 z_i+\sum_{i\in S_-} (n-i-1)^2 z_i+z_n.$$ Here we use that $n/2$ is not in $S_+$. Therefore $(Mz)_{n-1}-(Mz)_n=2\sum_{i\in S_+} i z_i - 2\sum_{i\in S_-} (n-i) z_i+1.$ So if $\sum_{i\in S_+} i z_i \geq\sum_{i\in S_-} (n-i) z_i$ then $(Mz)_{n-1}>2\lambda$ contradicting Claim 1. Similarly (using that $n/2$ is not in $S_-$) $$(Mz)_{1}=\sum_{i\in S_+} (i-1)^2 z_i+\sum_{i\in S_-} (n-i+1)^2 z_i+z_n$$ and $(Mz)_{1}-(Mz)_n=-2\sum_{i\in S_+} i z_i + 2\sum_{i\in S_-} (n-i) z_i+1.$ Therefore $(Mz)_{1}>2\lambda$ contradicting Claim 1 if $\sum_{i\in S_+} i z_i \leq\sum_{i\in S_-} (n-i) z_i$. Altogether the assumption $z_n>0$, $z_{n/2}=0$ leads to a contradiction.

In the sequel we actually only need that $S(z)$ contains $i$ and $i+n/2$ for some $i$.

Claim 3: $z$ equals $a_0$ except for some cyclic permutation and hence $f(z)=n^2/16$.

Proof: By Claim 2 and a cyclic permutation, we can assume that 1 and $\frac n2+1$ are in $S(z)$. Hence $S(a_0)\subseteq S(z)$. Observe that $a_0$ satisfies the conditions of Claim 1 with $\mu=\frac{n^2}{16}$ instead of $\lambda$, because $(\frac n2)^2> (\frac n2-i)^2+i^2$ for $i=1,\dots,\frac n2-1$. We calculate $a_0^TMa_0-z^TMz=(a_0-z)^TMz+a_0^TM(a_0-z)=(a_0-z)^TMz+(a_0-z)^TMa_0$ because $M$ is symmetric.

Now $Mz=2\lambda e - u$ where $u\geq0$ and $S(u)\cap S(z)=\emptyset$. Hence $(a_0-z)^TMz=2\lambda(a_0-z)^Te- (a_0-z)^Tu=0$ because $a_0^Te=1=z^Te$ and $S(a_0-z)\subseteq S(z)$.

We also have $Ma_0=2\mu e-v$, where $\mu=\frac {n^2}{16}$ and $v\geq0$, $S(v)\cap S(a_0)=\emptyset$. Above, we have seen that even $S(v)=\{1,\dots,n\}\setminus\{1,\frac n2+1\}$. Hence $(a_0-z)^TMa_0=2\mu(a_0-z)^Te-(a_0-z)^Tv=z^Tv$. Altogether we have $a_0^TMa_0-z^TMz=z^Tv\geq0$. Since the maximum is attained in $z$ by assumption, we have $z^Tv=0$, therefore $S(z)=S(a_0)$. Hence $z=a_0$ by Claim 1 because both satisfy the same $2$ by $2$ linear system with non-singular coefficient matrix. This completes the proof.