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?