Extending a matrix with a certain property over a finite field

Question

Suppose we have a $m \times n$ matrix $M$ with $n > m$ with entries over a finite field, say $\mathbb{F}_q$ with $q$ considered to be large compared to $m,n$. Suppose that $M$ has the property that every $m \times m$ minor of $M$ is invertible. Is there an efficient way to adjoin a column to $M$ to obtain a $m \times (n+1)$ matrix $M'$ with the same property?

The condition that $q$ is taken to be large is necessary in the following sense. If we take $q = 2$ for example, then we must necessarily have $n = m + 1$. To see this, apply elementary row operations to transform $M$ into $(I_m | A)$, where $I_m$ is the $m \times m$ identity matrix over $\mathbb{F}_2$. Now, for any column $a$ of $A$, the entries of $a$ must be all 1 because otherwise there would exist a subset of $m-1$ columns of $I_m$ such that $a$ is in the span of these columns. Hence $A$ has exactly one column consisting of all 1's.

Answer 1

I don't know an efficient algorithm answering your question but presumably it would have to break down for large $n$ - the MDS conjecture gives the maximal $n=q+1$ for odd $q\geq m$ with minor change in the even $q$ case. See Simeon Ball's work e.g. here http://www-ma4.upc.es/~simeon/jems-mds-conj-revised.pdf proving this when $q$ is prime.