Invent a polynomial algorithm to find max non-degenerate minor

Question

There is a matrix $A$ with $n$ rows and $m$ columns. The task is to invent a polynomial algorithm to find non-degenerate minor of maximum size.

If I got it right, we can reduce this to Gaussian elimination, which is of polynomial speed, am I right?

Answer 1

Yes, you're right -- though for large sizes you need to be a bit careful to avoid the entries of the partially-reduced matrix growing too large too fast.