1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\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.