I'm wondering if the following problem is NP-Complete or has any hardness result. References on related problem are also welcome.

Input: integers $n\geq1,k\geq0$ and an invertible matrix $M\in\mathbb F_2^{n\times n}$.

Accept iff: with at most $k$ row elimination, $M$ can be reduced to identity.

Here, one row elimination is simply adding one row to another (just like Gaussian elimination algorithm).

By Method of Four Russians, we know for any $n$, it suffices to have $k=O\left(\frac{n^2}{\log n}\right)$. But I'm curious about the minimum number of row eliminations required.



Your Answer

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