Let G be a graph with vertices $1,2,...,n$ and $F(x)=\displaystyle{\sum\_{ij\in\rm{E(G)}}x\_ix\_j}$.


Let S be the subset of $\mathbb{R}^n$ given by $x\_i\ge 0$, $\sum x\_i=1$. We're interested in $\displaystyle{\max\_{x\in S}}$ $F(x)$.


Why is any local maximum of F in the interior of S also a global maximum?




---


I was reading this paper, <http://math.ca/cjm/v17/cjm1965v17.0533-0540.pdf>.
 In the middle of the third page, there is a remark saying:


Any local maximum of F in the interior of S is also a global maximum.


I don't see why this is true. Is this obvious? Or well-known?



Any local maximum of F in the interior of a simplex is also a global maximum?
It's because the Hessian quadratic form of $F$ restricted to the orthogonal complement of the vector of all ones is exactly the Laplacian of the graph $G$ (a good basis for the orthogonal complement is the set of vectors having $1$ in the first coordinates, and $-1$ in the $i>1$-st coordinate). The Laplacian matrix is positive semi-definite.


