Estimating spectral radius with a Gaussian vector Suppose I'm trying to estimate the spectral radius of a square $n \times n$ matrix $A$,
and let $N$ be a distribution over Gaussian i.i.d. vectors of length $n$.
Is the following lemma true:
If the spectral radius of $A$ is larger than $\epsilon$ then with probability at least 
$1/poly(n)$, a vector $v$ sampled according to $N$ will have $\frac{|v^T A v|}{\left\|v\right\|^2}>\epsilon$.
 A: No: given $\eta > \epsilon > 0$, there are $n \times n$ symmetric matrices $A_n$
with spectral radius $> \eta$, such that $Pr\left[|v^TA_nv|/\|v\|^2 > \epsilon\right] < e^{-cn}$ for some $c > 0$.
I assume a standard Gaussian distribution, with mean $0$ and covariance matrix $I$.
Consider an $n \times n$ diagonal matrix $A$ with one diagonal element $\alpha$ and 
the other diagonal elements $-\epsilon$, where $\alpha > \eta > \epsilon > 0$.  Then 
$v^T A v = \alpha v_1^2 - \epsilon \sum_{j=2}^{n} v_j^2$, and it is impossible to have 
$v^T A v < -\eta \|v\|^2$, while
$$\eqalign{Pr\left[v^T A v > \eta \|v\|^2 \right] &= 
Pr\left[ (\alpha - \eta) v_1^2 - \sum_{j=2}^n (\epsilon + \eta) v_j^2 > 0 \right]\cr
&\le Pr \left[ (\alpha - \eta) v_1^2 > k (n-1)\right] + 
Pr\left[ S_n < k (n-1)\right]\cr}$$
for any $0 < k < \epsilon + \eta$, where $S_n = \sum_{j=2}^n (\epsilon + \eta) v_j^2$. 
Now $Pr[(\alpha - \eta) v_1^2 > k (n-1)]$  goes to 0 exponentially as $n \to \infty$.
 On the other hand,
 $S_n$  has mean $(n-1)(\epsilon+\eta)$, and for any 
$k < \epsilon + \eta$, $Pr[S_n < k (n-1)]$ goes to $0$ exponentially by the theory of large deviations. 
