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 costant $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?