# 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:

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

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?

• Out of curiosity, why do you want that $\sum u_i = 0$? Commented Feb 5, 2020 at 15:50
• The mentioned problem can be viewed as an upper bound to the problem of maximizing $x^t A x$ over the hypercube. Commented Feb 5, 2020 at 15:59
• I would like to find a vector such that the value is smaller than the value attained by the zero vector with high probability for $n \to \infty$. Commented Feb 5, 2020 at 16:05
• I think that due to the $\Sigma u_i = 0$ constraint and the convexity of $\lambda_{max}$, Jensen's inequality is going against you. Commented Feb 5, 2020 at 16:38
• @smapers That was not clearly written out. The expectation is (sort of?) conditional on the value of A. I.e., randomly reordering elements of u for a fixed $A$. Anyhow, this is not a rigorous argument, rather, a germ of an idea, and perhaps it is wrong. That is why I did not submit it as an answer. Commented Feb 6, 2020 at 13:23

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

• Does the downvoter care to explain the downvote? Commented Apr 21, 2020 at 1:46

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