Given a vector $u \in \Bbb R^n$, finding the value of the largest component of $u$ needs linear time in $n$. However, what if we additionally know that $u$ lies in some linear subspace $U \subset \Bbb R^n$ with $\dim U \sim f(n)$, with e.g. $f(n)=\sqrt n$ or $f(n)=\log n$, etc?
This probably depends on how $U$ is given to us. In my case, $U$ is given as the eigenspace of a certain sparse matrix.
What can be said about the complexity of the following problem?
Input: An $n \times n$ matrix $M \in \Bbb R^{n\times n}$, one of its eigenvalues $\theta \in \Bbb R$, and a corresponding eigenvector $u \in \Bbb R^n$.
Output: The value of the largest component of $u$ (and, if possible, its index in $u$).
We have the following information:
- We can assume that $M$ is symmetric.
- $M$ is sparse in the sense that the number of non-zero entries in any row is bounded from above by some constant $c \sim f(n)$.
- We have access to an oracle, that to each $i$ can tell the positions of the non-zero entries of the $i$-th row in $M$.
- The eigenspace of $\theta$ is of dimension $\dim \mathrm{Eig}_\theta(M) \sim f(n)$.
It feels unlikely that one can do better than linear time, but is there an easy argument why? Does it matter whether $M$ is a 01-matrix?
