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<i' or i=i' but j<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<n^2 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<n^2 since n>1, and so we are done. \Box


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s