2

I have asked a question about a maximum of discrete function yesterday at a Maximum of Discrete Function.

I want to generalize the question. Let $X=\{(x_1,\ldots ,x_n)\mid x_i=\pm 1,1\leq i\leq n\}$.

Fix $\vec{a}_1,\cdots,\vec{a}_m\in X$. Consider the discrete function $$F(\vec{x})=\sum_{i=1}^{m}(\vec{x}^T\vec{a}_i)^2,~~~~~~~\vec{x}\in X$$

I want to find when the function reaches the maximum. Is it at $\vec{x}=\vec{a}_i$, for some $i$? And how to prove it? Thank you.

Community
  • 1
gaoxinge
  • 4,434

1 Answers1

2

Fix $n = m$ and let $\vec{a_i} = \vec{1} - 2\vec{e_i}$, where $\vec{e_i}$ is the standard basis vector with a $1$ in the $i$th position. Then $$\begin{eqnarray} F(\vec{1}) &=& m(n-2)^2 \\ &=& m^3 - 4m^2 + 4m, \end{eqnarray}$$ but $$\begin{eqnarray} F(\vec{a_i}) &=& n^2 + (m-1)(n-4)^2 \\ &=& m^3 - 8m^2 + 24m - 16. \end{eqnarray}$$

For $m \geq 5$, $F(\vec{1}) > F(\vec{a_i})$ for each $i$, so it is not generally true that $F$ attains its maximum at some $\vec{a_i}$.

Eric Tressler
  • 4,309
  • Is there any "beautiful form" of the maximum? – gaoxinge Jun 25 '15 at 04:24
  • @gaoxinge I don't know. If $n = m \in {2,3,4}$, then choosing an $\vec{a_i}$ (one that appears the most frequently) is the best you can do. If you would like to search the literature, you may find something about this in coding theory; there, it is common to look for sets of ${0,1}$ vectors that maximize $\min_{i \neq j} d(\vec{a_i},\vec{a_j})$, where $d(\cdot)$ is the Hamming distance. It's not the same thing, but it's similar. – Eric Tressler Jun 25 '15 at 05:01
  • Is it right when $n>m$? My mates and I confirm that it is always right when $n=4,5$ and $m=3$. – gaoxinge Jun 25 '15 at 12:07