Calculating the maximum value of a quadratic polynomial on several variables with some restrictions

Question

Consider the following function on seven variables: $$f(x_1,\dots,x_7)=-x_1^2-2x_2^2-5x_3^2-4x_4^2-2x_5^2-71x_6^2-2x_7^2+2x_1x_2+2x_1x_3+2x_1x_4+2x_1x_6+2x_4x_5+2x_6x_7. $$

In another form, we have $$ f=3x_1^2-x_2^2-4x_3^2-2x_4^2-x_5^2-69x_6^2-x_7^2-(x_1-x_2)^2-(x_1-x_3)^2-(x_1-x_4)^2-(x_1-x_6)^2-(x_4-x_5)^2-(x_6-x_7)^2.$$

Can we find the maximum value $M$ of $f(x_1,\dots,x_n)$ with the following restrictions? The $x_i$'s are integers with $x_1,x_3,x_6$ odd and $x_2,x_4,x_5,x_7$ even.

What I know is that $(0,\dots,0)$ is the unique global maximum point of $f$ (as a function on real variables) with $f(0,\dots,0)=0$. Also $f(1,0,1,0,0,1,0)=-73$, so $0>M>-73$.

P.S. The result that I am hoping is $M<-7$.

Answer 1

$f(x)=-5$ when $x=(x_1, x_2, x_3,x_4, x_5,x_6,x_7)$ is one of the following 16 tuples,

$$\begin{array}{rrrrrrr} &(55, &28, &11, &16, &8, &1, &0) \\ &(57, &28, &11, &16, &8, &1, &0) \\ &(63, &32, &13, &18, &8, &1, &0) \\ &(63, &32, &13, &18, &10, &1, &0) \\ &(65, &32, &13, &18, &8, &1, &0) \\ &(65, &32, &13, &18, &10, &1, &0) \\ &(67, &34, &13, &20, &10, &1, &0) \\ &(69, &34, &13, &20, &10, &1, &0) \\ &(71, &36, &15, &20, &10, &1, &0) \\ &(73, &36, &15, &20, &10, &1, &0) \\ &(75, &38, &15, &22, &10, &1, &0) \\ &(75, &38, &15, &22, &12, &1, &0) \\ &(77, &38, &15, &22, &10, &1, &0) \\ &(77, &38, &15, &22, &12, &1, &0) \\ &(83, &42, &17, &24, &12, &1, &0) \\ &(85, &42, &17, &24, &12, &1, &0)\\ \end{array}$$

---

Claim: $f(x)\le-5$ when $x_1,x_3,x_6$ are odd and $x_2,x_4,x_5,x_7$ are even.

Proof: $$f(x)= -(x_1-x_2-x_3-x_4-x_6)^2 -(x_2-x_3-x_4-x_6)^2\\ -3 x_3^2 - 2 x_4^2 - 2 x_5^2 - 68 x_6^2 - (x_6-x_7)^2- x_7^2\\ + 4 x_3 x_4 + 4 x_3 x_6 + 2 x_4 x_5 + 4 x_4 x_6$$ Since $(\text{an even number})^2\equiv0$, $(\text{an odd number})^2\equiv1$, $2(\text{odd number})\equiv2$ $\pmod4$, we have $$f(x)\equiv-1-0-3-0-0-68-1-0+0+0+2+0=-71\equiv3\pmod4$$

Thanks to Will Jagy's answer, we can express $f(x)$ as a negative combination of squares.

$$\begin{aligned}f(x) = -(x_1-x_2-x_3-x_4-x_6)^2&\\ -(x_2-x_3-x_4-x_6)^2&\\ - 3(x_3-\frac23x_4-\frac23x_6)^2&\\ - \frac23(x_4-\frac32x_5-5x_6)^2&\\ - \frac12 (x_5-10x_6)^2&\\ - (x_6-x_7)^2 &\\ - x_7^2& \end{aligned}$$

Since $x_6$ is odd while $x_7$ is even, $x_6\not=x_7$. So $(x_6-x_7)^2\ge1$.

Since $f(x)\le -(x_6-x_7)^2\le-1$, all we need to prove is $f(x) \not= -1$.

Suppose $f(x)=-1$. Since $(x_6-x_7)^2\ge1$, we must have $$\begin{aligned} x_1-x_2-x_3-x_4-x_6&=0\\ x_2-x_3-x_4-x_6&=0\\ x_3-\frac23x_4-\frac23x_6&=0\\ x_4-\frac32x_5-5x_6&=0\\ x_5-10x_6&=0\\ x_6-x_7&=1\\ x_7&=0\\ \end{aligned}$$ That means, $x_7=0$, $x_6=1$, $x_5=10$, $x_4=20$, $x_3=14$. However, we require $x_3$ be odd. Hence $f(x)\not=-1$. $\quad\checkmark$

---

Hence $M=-5$.

Answer 2

... determinant 1, characteristic polynomial $ x^7 - 87x^6 + 1231x^5 - 7136x^4 + 19963x^3 - 26741x^2 + 13744x - 1 $

There is a small eigenvalue.. In the matrix identity below, we may multiply through by $216$ to get all integer matrices in $(6Q^T)(6D)(6Q) = 216 H.$ After that, write a loop in seven integer variables with your even/odd conditions, you want this to be bigger than $216 \cdot 7 = 1512.$

$$ Q^T D Q = H $$

$$\left( \begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ - 1 & - 1 & 1 & 0 & 0 & 0 & 0 \\ - 1 & - 1 & - \frac{ 2 }{ 3 } & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & - \frac{ 3 }{ 2 } & 1 & 0 & 0 \\ - 1 & - 1 & - \frac{ 2 }{ 3 } & - 5 & - 10 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & - 1 & 1 \\ \end{array} \right) \cdot \left( \begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 2 }{ 3 } & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{ 1 }{ 2 } & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) \cdot $$

$$ \left( \begin{array}{rrrrrrr} 1 & - 1 & - 1 & - 1 & 0 & - 1 & 0 \\ 0 & 1 & - 1 & - 1 & 0 & - 1 & 0 \\ 0 & 0 & 1 & - \frac{ 2 }{ 3 } & 0 & - \frac{ 2 }{ 3 } & 0 \\ 0 & 0 & 0 & 1 & - \frac{ 3 }{ 2 } & - 5 & 0 \\ 0 & 0 & 0 & 0 & 1 & - 10 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrrr} 1 & - 1 & - 1 & - 1 & 0 & - 1 & 0 \\ - 1 & 2 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 5 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 4 & - 1 & 0 & 0 \\ 0 & 0 & 0 & - 1 & 2 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 0 & 71 & - 1 \\ 0 & 0 & 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right) $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

Answer 3

Consider the following function on seven variables: $$f(x_1,\dots,x_7)=-x_1^2-2x_2^2-5x_3^2-4x_4^2-2x_5^2-71x_6^2-2x_7^2$$ $$+2x_1x_2+2x_1x_3+2x_1x_4+2x_1x_6+2x_4x_5+2x_6x_7. $$ Denote $$x_1=A,\;x_2=2B,\;x_3=C,\;x_4=2D,\;x_5=2E,\,x_6=F,\;x_7=2G,\tag1$$ then \begin{align} &f=-A^2-8B^2-5C^2-16D^2-8E^2-71F^2-8G^2+2A(2B+C+2D+F)+8DE+4FG\\ &\quad=-(A-2B-C-2D-F)^2-(2B-C-2D-F)^2-2(2D-C-E-F)^2\\ &\quad-(C-2E-4F)^2-2(E-5F)^2-(F-2G)^2-(2G)^2, \end{align}

Let us try to get solutions with $\,f>-6.$

• (7): $G\not=0\;$ means $f<-5.\;$ Assume $\;G=0,\; T_7=0.$
• (6): Since $\,F\,$ is odd, then $\,F=\pm1,\;T_6=-1.$
• (5): Maximum achieves when $\;E=5F,\;T_5=0.$
• (4): Since $\,C\,$ should be odd, then $C=2E+4F\pm1=14F\pm1,\;T_4=-1.$
• (3): $2D=C+E+F\pm1,\;T_3=-2.$
• (2): $2B=C+2D+F, T_2=0.\;$
• (1): Since $\,A\,$ is odd, $A=2B+C+2D+F\pm1,\;T_1=-1.$

The set of the possible solutions with $\;\color{blue}{\mathbf{f=-5}}\;$ is $$\begin{pmatrix} A \\ B \\ C \\ D \\ E \\ F \\ G \end{pmatrix} \in\left\{ \pm\begin{pmatrix} 63 \\ 16 \\ 13 \\ 9 \\ 5 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 65 \\ 16 \\ 13 \\ 9 \\ 5 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 67 \\ 17 \\ 13 \\ 10 \\ 5 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 69 \\ 17 \\ 13 \\ 10 \\ 5 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 71 \\ 18 \\ 15 \\ 10 \\ 5 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 73 \\ 18 \\ 15 \\ 10 \\ 5 \\ 1 \\ 0 \end{pmatrix} \pm\begin{pmatrix} 75 \\ 19 \\ 15 \\ 11 \\ 5 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 77 \\ 19 \\ 15 \\ 11 \\ 5 \\ 1 \\ 0 \end{pmatrix} \right\}.\tag2$$

Equations $\,(2), (1)\,$ define the final solution $$\color{blue}{\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{pmatrix} \in\left\{ \pm\begin{pmatrix} 63 \\ 32 \\ 13 \\ 18 \\ 10 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 65 \\ 32 \\ 13 \\ 18 \\ 10 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 67 \\ 34 \\ 13 \\ 20 \\ 10 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 69 \\ 34 \\ 13 \\ 20 \\ 10 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 69 \\ 36 \\ 15 \\ 20 \\ 10 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 71 \\ 36 \\ 15 \\ 20 \\ 10 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 73 \\ 38 \\ 15 \\ 22 \\ 10 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 75 \\ 38 \\ 15 \\ 22 \\ 10 \\ 1 \\ 0 \end{pmatrix} \right\}}.\tag3$$

$$ $$ Alternative way.

• (5): $\;E=4F(6F),\;T_5=-2.$
• (4): Since $\,C\,$ should be odd, then $C=2E+4F\pm1=12F(16F)\pm1,\;T_4=-1.$
• (3): $2D=C+E+F,\;T_3=0.$
• (2): $2B=C+2D+F,\; T_2=0.\;$
• (1): $A=2B+C+2D+F\pm1,\;T_1=1.$

$$\begin{pmatrix} A \\ B \\ C \\ D \\ E \\ F \\ G \end{pmatrix} \in\left\{ \pm\begin{pmatrix} 55 \\ 14 \\ 11 \\ 8 \\ 4 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 57 \\ 14 \\ 11 \\ 8 \\ 4 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 63 \\ 16 \\ 13 \\ 9 \\ 4 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 65 \\ 16 \\ 13 \\ 9 \\ 4 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 75 \\ 19 \\ 15 \\ 11 \\ 6 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 77 \\ 19 \\ 15 \\ 11 \\ 6 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 83 \\ 21 \\ 17 \\ 12 \\ 6 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 85 \\ 21 \\ 17 \\ 12 \\ 6 \\ 1 \\ 0 \end{pmatrix}, \right\}.\tag4$$

Equations $\,(4), (1)\,$ define the additional solutions with $\;\color{blue}{\mathbf{f=-5}}\;$ $$\color{blue}{\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{pmatrix} \in\left\{ \pm\begin{pmatrix} 55 \\ 28 \\ 11 \\ 16 \\ 8 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 57 \\ 28 \\ 11 \\ 16 \\ 8 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 63 \\ 32 \\ 13 \\ 18 \\ 8 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 65 \\ 32 \\ 13 \\ 18 \\ 8 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 75 \\ 38 \\ 15 \\ 22 \\ 12 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 77 \\ 38 \\ 15 \\ 22 \\ 12 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 83 \\ 42 \\ 17 \\ 24 \\ 12 \\ 1 \\ 0 \end{pmatrix}, \pm\begin{pmatrix} 85 \\ 42 \\ 17 \\ 24 \\ 12 \\ 1 \\ 0 \end{pmatrix} \right\}.}\tag5$$

Answer 4

Made a modification, lets me specify one elementary step at a time.

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ P^T H P = D $$

$$\left( \begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 2 & 1 & 1 & 0 & 0 & 0 \\ 4 & 2 & 1 & 1 & 1 & 0 & 0 \\ - 6 & - 3 & - 1 & - 2 & - 1 & 0 & 0 \\ 70 & 35 & 14 & 20 & 10 & 1 & 0 \\ 70 & 35 & 14 & 20 & 10 & 1 & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrrr} 1 & - 1 & - 1 & - 1 & 0 & - 1 & 0 \\ - 1 & 2 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 5 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 4 & - 1 & 0 & 0 \\ 0 & 0 & 0 & - 1 & 2 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 0 & 71 & - 1 \\ 0 & 0 & 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right) \left( \begin{array}{rrrrrrr} 1 & 1 & 4 & 4 & - 6 & 70 & 70 \\ 0 & 1 & 2 & 2 & - 3 & 35 & 35 \\ 0 & 0 & 1 & 1 & - 1 & 14 & 14 \\ 0 & 0 & 1 & 1 & - 2 & 20 & 20 \\ 0 & 0 & 0 & 1 & - 1 & 10 & 10 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ $$

$$ Q^T D Q = H $$

$$\left( \begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ - 1 & - 1 & 1 & 1 & 1 & 0 & 0 \\ - 1 & - 1 & 0 & - 1 & - 1 & 0 & 0 \\ 0 & 0 & - 1 & 1 & 0 & 0 & 0 \\ - 1 & - 1 & - 4 & - 4 & 6 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & - 1 & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrrr} 1 & - 1 & - 1 & - 1 & 0 & - 1 & 0 \\ 0 & 1 & - 1 & - 1 & 0 & - 1 & 0 \\ 0 & 0 & 1 & 0 & - 1 & - 4 & 0 \\ 0 & 0 & 1 & - 1 & 1 & - 4 & 0 \\ 0 & 0 & 1 & - 1 & 0 & 6 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrrr} 1 & - 1 & - 1 & - 1 & 0 & - 1 & 0 \\ - 1 & 2 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 5 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 4 & - 1 & 0 & 0 \\ 0 & 0 & 0 & - 1 & 2 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 0 & 71 & - 1 \\ 0 & 0 & 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right) $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$