Given a diagonalizable matrix $A \in \mathbb{R}^{n \times n}$ with real eigenvalues, satisfying $1+c\_1 \le \rho(A) \le 1+c\_2$ $(0<c\_1 \le c\_2)$, obviously there exists a $v \in \mathbb{R}^{n}$ such that $\|Av\| \ge \|v\|$.


I am interested in the case where $v$ is drawn uniformly at random from some discrete distribution, for instance $\{\pm1\}^{n}$. Are there any known lower bounds on $\Pr[\|Av\| \ge \|v\|]$?


Thank you.



Estimating the probability that $\|Av\| \ge \|v\|$
You can have very few vectors in the discrete set satisfy the bound. For example, let $A$ be the matrix with zeros everywhere except for $1+c\_1$ in the upper left corner (let's assume $1+c\_1<\sqrt{2}$). Then there are only two vectors in $\{\pm 1\}^n$ which satisfy $\Vert Av\Vert \geq \Vert v\Vert$.


It follows that the lower bound question is roughly equivalent to asking whether there must be *any* vector in $\{\pm 1\}^n$ satisfying the bound.


