0
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Pseudonym
    Aug 13, 2021 at 7:58

1 Answer 1

1
$\begingroup$

You can't.

Consider a matrix that is nearly all zeros. Consider what happens if you have an algorithm that starts inspecting entries, keeps finding a zero in each place it looks, but halts without having looked at all entries. Consider any entry it didn't look at. The output needs to be different if the matrix is all zeros except for that entry, vs if it is all zeros. (Both matrices are in reduced row echelon form, so both are valid inputs.) However this algorithm will output the same thing for both inputs. Hence this algorithm cannot be correct.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.