# Lower bound on number of zero columns in matrix

I've been looking for an algorithm to tell the number of non-zero rows (or columns) in a row reduces matrix $$A\in \mathbb{R}^{m\times n}$$. A simple approach would be to check it, row by row, which would take $$O(m\cdot n)$$ time and I believe would be linear. It seems to be the lower bound, but I am not sure, could there be a more efficient deterministic algorithm for this?

• I don't see how you can answer the question without inspecting all $mn$ entries at least once, and your proposed method uses constant space and exactly $2mn$ memory accesses. The best you can do is reducing the constant factor below $2$. Aug 13, 2021 at 7:58