Given an $n \times n$ symmetric matrix filled with realizations of a uniform random variable taking values in $[-1, 1]$, determine the maximum expected eigenvalue using analytic methods.
Running multiple MATLAB scripts of a large $n$ matrix gave me a the following plot:
Observe, the elliptic nature of the $100 \times 100$ plot. Intuitively, I suspect the maximum value of the eigenvalues must be $\sqrt{n}$, but I don't know how to determine this value analytically (or even if $\sqrt{n} $ is indeed true).
I've attempted reading Pastur et Al.'s "Eigenvalue distribution for Large Random matrices" But can't make sense of their work.
In short What is the relationship between $n$, dimension of the matrix and the maximum expected eigenvalue?
Answer
The Correct solution is $n$ opposed to my original intuition of $\sqrt{n}$
For the positive case only
Proof
Observe that
$$ tr(A) = \sum_{i = 1}^{n} a_{ii} = \sum_{i = 1}^{n} \lambda_i $$
Meaning that the sum of the diagonals is simultaneously equal to the sum of the possible eigenvalues in any square matrix.
Now, let $m$ be the largest entry into A (ie. For our case $m = 1$ as all $a_{ij}$ normally randomly chosen $ \in [-1, 1]$
Let $$\lambda _{max} \leq \sum_{i = 1}^{k} \lambda _k = tr(A)$$
$$\implies \lambda _{max} \leq tr(A)$$
$$a_{ii} \leq m$$
Every $a_{ij}$ entry is less than the maximum
$$\implies \sum_{i = 1}^{n} a_{ii} \leq \sum_{i = 1}^{n} m$$
$$\implies tr(A) \leq mn$$
$$\lambda _{max} \leq tr(A) \leq mn$$
$$\lambda _{max} \leq mn$$
$$\tag*{$\blacksquare$}$$
Special thanks to Rahul (in comments) & Raghav Srinivasan of the University of Toronto.
Alternately, observe that intuitively I thought that $\sqrt{n}$ was the correct solution because in a Wigner distribution, the scaling as $n \to \infty$ is $\sqrt{n}$ This can be proven here
No comments:
Post a Comment