Consider the symmetric positive definite matrix ${M}$ such that its inverse ${M}^{-1}$ has also diagonal entries 1 and non-diagonal entries, each bounded by a constant $c' < 1$. Now, can we bound the value $x\cdot{M}^{\top}{M}\cdot x$ where $x \in \{-1,1\}^n$.
Apparently, we are trying to understand the largest singular values of ${M}$ here such that $\|{M}x\|_2$ is maximized. We know that it would correspond to the eigenvector of $({M}^{\top}{M})$. Can we say that bound has the form $\|{M}x\|_2 < c\cdot n$ where $c$ is a fixed number?
Firstly, for every real symmetric matrix $M$, the normalized eigenvectors $\{v_i\}_{i=1}^n$ of $M$ span the whole space (See here for proof). Without loss of generality, we assume such vectors are jointly orthogonal as well.
This means that one can rewrite each vector $x$ as \begin{equation} x = \sum_{i=1}^n c_i v_i. \end{equation}
As a result, we have \begin{equation} Mx = \sum_{i=1}^n c_i \lambda_i v_i, \end{equation} where concludes \begin{equation} \|Mx\|_2 = \sqrt{\sum_{i=1}^n\lambda_i^2c_i^2}, \end{equation} since $\|v_i\|_2=1$, and due to orthogonality of $v_i$s, where $\lambda_i$s are eigenvalues of $M$.
Further, since $x\in \{-1, 1\}^n$, we have $\sum_{i=1}^n c_i^2= n$. As a result, we have \begin{equation} \|Mx\|_2 \leq \sqrt{n}|\lambda_{\max}|, \end{equation} where $\lambda_{\max}$ is the eigenvalue with maximum absolute value.
Finally, Greshorin's circle theorem (see here), expresses that the eigenvalues of a matrix $M$ lies one circles with $M$s diagonal elements as centers and absolute sum of non-diagonal elements as radius's. Hence, for this matrix, we have $|\lambda_{\max}|< n$.
Finally, using above discussions we have \begin{equation} \|Mx\|_2 < n\sqrt{n}. \end{equation}
My conjecture is that, the rate $O(n\sqrt{n})$ is optimal.