Minimizing the largest eigenvalue of random matrices

Question

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?

Answer 1

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$.

Answer 2

Let $v$ be the eigenvector corresponding to $\lambda_{\max}(A)$, normalized so that $\|v\|=1$. First-order perturbation results for eigenvalues are known: for a symmetric $A$, we have for each matrix $E$ $$ \lambda_{\max}(A+E) = \lambda_{\max}(A) + v^*Ev + O(\|E\|^2). $$ So you just need to choose $u$ such that $\sum u_i v_i^2>0$, and then a sufficiently small multiple of it will reduce the value of $\lambda_{\max}$.

By taking $u$ sufficiently small you can also ensure that the other eigenvalues will not be perturbed enough that they exceed $\lambda_{\max}(A+E)$. For instance, take $\max(|u_i|) < 1/2(\lambda_{\max}(A) - \lambda_2(A))$, where $\lambda_2(A)$ is the second-largest eigenvalue: then a perturbation of norm $\|E\|= \max(|u_i|)$ is small enough that $\lambda_{\max}(A+E)$ and $\lambda_2(A+E)$ won't "cross".

Note that this argument does not use anywhere that $A$ is a random matrix, if not to ensure that $\lambda_{\max}(A)$ is simple and hence $\lambda_2(A) < \lambda_{\max}(A)$. The vector $u$ is a deterministic function of $A$.