Query Lower Bounds for Approximating the Top Eigenvector of Asymmetric Matrices

We study the query complexity of approximating the top eigenvector of an asymmetric matrix in the matrix-vector product model. Our main result gives a gap-dependent lower bound for this problem in the adaptive query setting. Prior lower bounds for symmetric matrices already imply weaker hardness guarantees for the more general asymmetric problem, whereas our result yields a sharper dependence on the eigen-gap in the asymmetric case. In the inverse polynomial accuracy regime, this lower bound matches the benchmark upper bound of the power method up to lower-order factors. Our proof is based on an asymmetric spiked random matrix that serves as a hard instance. The key random-matrix ingredient is an analysis of the spike model, including both its asymptotic eigen-gap and the alignment between its top eigenvector and the planted spike. Building on an information-theoretic framework for query lower bounds, we then obtain the stated hardness result.