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.
