4
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.