6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Maybe further restricting the vector to have unit norm increases the chances a bit. $\endgroup$ – Manfred Weis Jul 10 at 13:31
  • $\begingroup$ @ManfredWeis That would be no problem, we can assume that $u$ has unit length, or at least, that we know the length. $\endgroup$ – M. Winter Jul 10 at 15:40
  • $\begingroup$ Largest in absolute value? $\endgroup$ – Rodrigo de Azevedo Jul 11 at 9:49
  • 1
    $\begingroup$ Imagine a matrix that is mainly 3 consecutive $1$'s in a row, the eigenvalue $3$ and the vector that has all entries $1$ but one of them is a bit larger (you'll need to adjust only 3 rows to make it a true eigenvector, etc). What are you going to do? You cannot really guess the right place to look at neither in the vector, nor in the matrix.... $\endgroup$ – fedja Jul 12 at 0:48
  • 1
    $\begingroup$ For 0-1 it goes like this (every triple is a row centered on the diagonal). The vector is ...1,1,1,2,1,1,1... and you hit it with (1,0,1), (1,1,0),(0,1,0),(0,1,1),(1,0,1) and then happily go the rest of the cycle with (1,0,1). It seems to satisfy all the requirements though I admit that this case is highly non-generic. $\endgroup$ – fedja Jul 12 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.