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$

	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…

Share this:

Like this:

Related

Leave a Reply Cancel reply