A neat application of the polynomial method

Two years ago, Boris Alexeev emailed me a problem:

Let $n \geq 2$.  Suppose you have $n^2$ distinct numbers in some field.  Is it necessarily possible to arrange the numbers into an $n\times n$ 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 $2\times 2$ matrix? (The answer depends on whether you consider $-2$ 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 $F$, fix $n>1$, and let $S\subseteq F$ be any subset of size $n^2$. Then there exists a full rank $n\times n$ matrix $A$ such that every member of $S$ appears as an entry of $A$.

Proof: Consider the homogeneous polynomial $p\in F[x_{ij}:i,j\in\{1,\ldots,n\}]$ defined by

$\displaystyle p(x)=\mathrm{det}(x_{ij})_{i,j=1}^n\cdot q(x), \qquad q(x):=\prod_{(1,1)\preceq(i,j)\prec(i',j')\preceq(n,n)}\big(x_{i'j'}-x_{ij}\big),$

where $(i,j)\prec(i',j')$ means that either $i or $i=i'$ but $j. Notice that $p(A)\neq0$ precisely when $A$ is invertible with all distinct entries. We will identify a term $cx^\alpha$ of $p$ such that $c\neq0$ and $\max\alpha so that the result follows immediately from the combinatorial nullstellensatz.

First, we observe that $q$ is a Vandermonde polynomial, and so the Leibniz formula of the corresponding determinant gives

$\displaystyle q(x)=\sum_{\sigma\in S_{n^2}}\mathrm{sign}(\sigma)\cdot x^{\sigma(\beta)}, \qquad \beta= \left(\begin{array}{cccc} 0&1&\cdots&n-1\\ n&n+1&\cdots&2n-1\\ \vdots&\vdots&&\vdots\\ n^2-n&n^2-n+1&\cdots&n^2-1 \end{array}\right).$

Next, consider the term of $\mathrm{det}(x_{ij})_{i,j=1}^n$ corresponding to the identity permutation $\mathrm{id}\colon i\mapsto i$ and the term of $q$ corresponding to any permutation $\delta\in S_{n^2}$ satisfying $\delta(\beta)_{ii}=i-1$ for every $i\in\{1,\ldots,n\}$. The product of these terms has exponent $\alpha=\delta(\beta)+[\mathrm{id}]$, where $[\mathrm{id}]$ denotes the matrix representation of $\mathrm{id}$ (namely, the identity matrix).

We claim that $\alpha=\sigma(\beta)+[\pi]$ with $\sigma\in S_{n^2}$ and $\pi\in S_n$ only if $\sigma=\delta$ and $\pi=\mathrm{id}$, meaning there exists $c\neq0$ such that $cx^\alpha$ is a term of $p$. To see this, first note that $\alpha$ is uniquely minimized at $\alpha_{11}=1$, thereby forcing $\sigma(\beta)_{11}=0$. Next, the remainder of $\alpha$ is uniquely minimized at $\alpha_{22}=2$, thereby forcing $\sigma(\beta)_{22}=1$. Continuing in this way, we obtain $\sigma(\beta)_{ii}=i-1$ for every $i\in\{1,\ldots,n-1\}$. Since $[\pi]_{ii}=1$ for every $i\in\{1,\ldots,n-1\}$, this forces $[\pi]_{nn}=1$, meaning $\pi=\mathrm{id}$, and so $\sigma(\beta)=\alpha-[\mathrm{id}]=\delta(\beta)$, i.e., $\sigma=\delta$.

Finally, $\max\alpha=n^2-1 since $n>1$, and so we are done. $\Box$