Minimizing the largest eigenvalue of random matrices 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? 
 A: For a given instantiation of $A$, the globally optimal value of $u$ can be found as the solution of a convex Linear Semidefinite Programming (SDP) problem using a standard solver such as Mosek. This optimum achieves a better objective value than $u = 0$ a.s. for $n \ge 2$.
Now assume, I believe as intended, that $u$ must be specified only with knowledge of $n$, but not with knowledge of a specific instantiation of $A$.
By convexity of $\lambda_{max}$ of a real symmetric matrix, 
$$\lambda_{max}(A) \le \frac{1}{2}\lambda_{max}(A-\text{diag}(u)) + \frac{1}{2}\lambda_{max}(A-\text{diag}(-u))$$
Taking expectation of both sides,
$$E(\lambda_{max}(A)) \le \frac{1}{2}E(\lambda_{max}(A-\text{diag}(u))) + \frac{1}{2}E(\lambda_{max}(A-\text{diag}(-u)))$$
Because $u$ was chosen without knowledge of the instantiation of $A$, and all elements of $A$ are symmetrically distributed about zero, it must be the case that 
$$E(\lambda_{max}(A-\text{diag}(-u))) =E(\lambda_{max}(A-\text{diag}(u)))$$
and therefore
$$E(\lambda_{max}(A)) \le E(\lambda_{max}(A-\text{diag}(u)))$$
So such a $u$ can do no better on average than $u = 0$.
