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

• Out of curiosity, why do you want that $\sum u_i = 0$? – smapers Feb 5 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. – sigmatau Feb 5 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$. – sigmatau Feb 5 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. – Mark L. Stone Feb 5 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. – Mark L. Stone Feb 6 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? – Mark L. Stone Apr 21 at 1:46