A Simple Complexity Lower Bound for Solving $Ax=b$

In this note, we provide a short and direct proof that approximately solving $Ax=b$ to relative error $\epsilon$, where $A$ has condition number $\kappa$ and unrestricted dimension, requires $\mathrm{\Omega }(\kappa \log (1\mathrm{/}\epsilon ))$ matrix-vector multiplications in the worst case, even for randomized algorithms. This essentially recovers the lower bound of Dereziński, Epperly and Meyer [2026] for this setting, whose elegant and more general approach inspired us to seek a short direct proof. A straightforward reduction implies the classical $\mathrm{\Omega }(\sqrt{\kappa }\log (1\mathrm{/}\epsilon ))$ lower bound for optimizing strongly convex quadratic functions, applicable to randomized algorithms.