Let $A \in \mathbb{R}^{n \times n}$ be a symmetric matrix with entries $A_{ij} \sim \mathcal{N} (0,1)$, all independent except for the symmetry condition.

Consider the following minimization problem:

\begin{equation} \inf \limits_{u \in \mathbb{R}^n : \sum u_i = 0 }\{ \ \lambda_{max}( A - \text{Diag}(u))\} \end{equation}

where $\lambda_{max}(\cdot)$ denotes the largest eigenvalue and $\text{D}(v)$ is the diagonal matrix having the vector $v \in \mathbb{R}^n$ as entries.

I don't want to necessarily find the optimal value of this problem. It would suffice to find a vector $u$ that achieves a smaller value than the trivial vector $0 \in \mathbb{R}^n$, for large $n$.

**Question**: How would one find a vector $u$, with $\sum_i u_i = 0 $ (possibly random and dependent on $A$), that achives a smaller value than the zero vector asymptotically for large $n$ with high probability? For the zero vector the value is $\lambda_{max}(A)$ for which it is know that $\lambda_{max}(A) = \Theta( 2 n^{3/2}) $.

Is there existing literature on this problem? What methods might one use?

6more comments