In which interval lies the minimum?

Question

Let $a_1,a_2,a_3,a_4$ be real numbers such that $a_1+a_2+a_3+a_4 =0 $ and $a_1^2+a_2^2+a_3^2+a_4^2=1$.

Then in what interval does the smallest possible value of the following expression lies?

$$(a_1-a_2)^2+(a_2-a_3)^2+(a_3-a_4)^2+(a_4-a_1)^2$$

Here lies the actual question with the options.

Answer 1

Let $a_1=0$, $a_2=\frac{1}{\sqrt2},$ $a_3=0$ and $a_4=-\frac{1}{\sqrt2}.$

Hence, we get a value $2$.

We'll prove that it's a minimal value.

Indeed, let $a_1=a$, $a_2=b$, $a_3=c$.

Thus, $a_4=-a-b-c$, $a^2+b^2+c^2+(a+b+c)^2=1$ and we need to prove that $$(a-b)^2+(b-c)^2+(a+b+2c)^2+(2a+b+c)^2\geq2$$ or $$(a-b)^2+(b-c)^2+(a+b+2c)^2+(2a+b+c)^2\geq2\left(a^2+b^2+c^2+(a+b+c)^2\right)$$ or $$(a+c)^2\geq0.$$ Done!

We'll find a maximal value for the collection.

Let $a_i=(-1)^{i-1}\frac{1}{2}.$

Hence, we get a value $4$.

We'll prove that it's a maximal value.

Indeed, let $a_1=a$, $a_2=b$, $a_3=c$.

Thus, $a_4=-a-b-c$, $a^2+b^2+c^2+(a+b+c)^2=1$ and we need to prove that $$(a-b)^2+(b-c)^2+(a+b+2c)^2+(2a+b+c)^2\leq4$$ or $$(a-b)^2+(b-c)^2+(a+b+2c)^2+(2a+b+c)^2\leq4\left(a^2+b^2+c^2+(a+b+c)^2\right)$$ or $$(a+b)^2+(b+c)^2\geq0.$$ Done!

Answer 2

We have the non-convex quadratically constrained quadratic program (QCQP) in $\mathrm x \in \mathbb R^4$

$$\begin{array}{ll} \text{minimize} & \mathrm x^\top \mathrm L \,\mathrm x\\ \text{subject to} & 1_4^\top \mathrm x = 0\\ & \mathrm x^\top \mathrm x = 1\end{array}$$

where

$$\mathrm L = \begin{bmatrix}2 & -1 & 0 & -1\\-1 & 2 & -1 & 0\\0 & -1 & 2 & -1\\-1 & 0 & -1 & 2\end{bmatrix}$$

is a (symmetric, positive semidefinite) Laplacian matrix. Since $\rm L$ is symmetric, its eigenvectors are orthogonal and its eigenvalues are real. Note that $\mathrm L 1_4 = 0_4 = 0 \cdot 1_4$, i.e., $(0, 1_4)$ is an eigenpair of matrix $\rm L$. Using the equality constraint $1_4^\top \mathrm x = 0$, we conclude that the minimum is

$$\min_{1_4^\top \mathrm x = 0\\ \| \mathrm x \|_2 = 1} \mathrm x^\top \mathrm L \,\mathrm x = \lambda_3 (\mathrm L) = 2$$

where $\lambda_3 (\mathrm L)$ is the smallest positive eigenvalue of $\rm L$.

---

Python code

Using SymPy:

>>> from sympy import *
>>> C = Matrix([[ 1,-1, 0, 0],
                [ 0, 1,-1, 0],
                [ 0, 0, 1,-1],
                [-1, 0, 0, 1]])
>>> L = C.T * C
>>> L
Matrix([
[ 2, -1,  0, -1],
[-1,  2, -1,  0],
[ 0, -1,  2, -1],
[-1,  0, -1,  2]])
>>> L.eigenvals()
{0: 1, 2: 2, 4: 1}

Note that eigenvalue $2$ has multiplicity $2$. Hence, $\lambda_2 (\mathrm L) = \lambda_3 (\mathrm L) = 2$.