Two years ago, Boris Alexeev emailed me a problem:
Let . Suppose you have distinct numbers in some field. Is it necessarily possible to arrange the numbers into an matrix of full rank?
Boris’s problem was originally inspired by a linear algebra exam problem at Princeton: Is it possible arrange four distinct prime numbers in a rank-deficient matrix? (The answer depends on whether you consider to be prime.) Recently, Boris reminded me of his email, and I finally bothered to solve it. His hint: Apply the combinatorial nullstellensatz. The solve was rather satisfying, and if you’re reading this, I highly recommend that you stop reading here and enjoy the solve yourself.
Theorem. Pick any field , fix , and let be any subset of size . Then there exists a full rank matrix such that every member of appears as an entry of .
Proof: Consider the homogeneous polynomial defined by
where means that either or but . Notice that precisely when is invertible with all distinct entries. We will identify a term of such that and so that the result follows immediately from the combinatorial nullstellensatz.
First, we observe that is a Vandermonde polynomial, and so the Leibniz formula of the corresponding determinant gives
Next, consider the term of corresponding to the identity permutation and the term of corresponding to any permutation satisfying for every . The product of these terms has exponent , where denotes the matrix representation of (namely, the identity matrix).
We claim that with and only if and , meaning there exists such that is a term of . To see this, first note that is uniquely minimized at , thereby forcing . Next, the remainder of is uniquely minimized at , thereby forcing . Continuing in this way, we obtain for every . Since for every , this forces , meaning , and so , i.e., .
Finally, since , and so we are done.