Nonsingular matrices with bounded coefficients

I can show that there exists $n^2$ positive integers $a_1,\ldots ,a_{n^2}$, such that each $n\times n$ matrix with coefficients $a_i$ (used once and only once) is nonsingular.

Two questions:

1. Could we find the smallest integer $M_n$ such that we can state that there exists $n^2$ positive integers $a_1,\ldots ,a_{n^2} \leqslant M_n$, such that each $n\times n$ matrix with coefficients $a_i$ (used once and only once) is nonsingular.

2. What conditions on $a,b\in \mathbb R$ are necessary and sufficient to state that there exists $n^2$ real numbers $a_1,\ldots ,a_{n^2}$ in $[a,b]$, such that each $n\times n$ matrix with coefficients $a_i$ (used once and only once) is non singular.

Also, do you know if these properties are used "somewhere"?

• When you say the coefficients are $a_i$, do you actually mean the elements? Jun 25 '16 at 23:15
• In the second question, you may consider a chain of field extensions. Jun 26 '16 at 2:13
• Difficult to formalize, but I'd bet that for the second question, all interval [a,b] with a<b satisfy (uncountable infinity of "candidates"). Jun 29 '16 at 11:09

This is only a partial answer. But maybe it will be helpful to someone.

$(1)$ I was only able to show that $M_n\leq p$, where $p$ is the first prime larger than $n^2!n$.

$(2)$ For the existence of $n^2$ numbers $a_1, \ldots, a_{n^2}\in [a,b]$ such that every matrix whose entries form a permutation of the set $\{a_1, \ldots, a_{n^2}\}$ has a nonzero determinant, it is necessary and sufficient that $a<b$ (one can even guarantee that in this case, the numbers can be chosen to be rationals).

Let's see why $(2)$ is true first, because it is related to my answer to $(1)$. We will use methods from algebraic geometry.

Clearly, $a<b$ is a necessary condition, and we only need to show that it is sufficient. Let $K$ be an infinite field. Denote by $f(X_1,\ldots, X_{n^2})$ the polynomial $\mathrm{det}(X_1,\ldots, X_{n^2})\in K[X_1,\ldots, X_{n^2}]$. Because the identity matrix has a determinant $1$, the vanishing subset $V(f):=\{(c_1,\ldots, c_{n^2})\in K^{n^2}\mid f(c_1,\ldots, c_{n^2})=0\}$ of $f$ in $K^{n^2}$ is not the whole $K^{n^2}$. By the same reasoning, for any permutation $\sigma\in S_{n^2}$ (where $S_{n^2}$ is the group of all permutations on the set $\{X_1,X_2,\ldots, X_{n^2}\}$), define $\sigma(f)$ to be the polynomial $\det(\sigma(X_1),\ldots, \sigma(X_{n^2}))$, then $V(\sigma(f))$ is also a proper subset of $K^{n^2}$. But we know that $K^{n^2}$ as an affine variety is irreducible, which means that it is not a finite union of proper closed subsets, thus $\bigcup_{\sigma \in S_{n^2}} V(\sigma(f))$ is a proper subset of $K^{n^2}$. This means that on any infinite field $K$, one can always choose $n^2$ elements $a_1, \ldots, a_{n^2}$ such that any matrix whose entries form a permutation of the $n^2$ elements has a non-zero determinant.

Now let $K=\mathbb{R}^{n^2}$. Then every proper Zariski-closed subset of $\mathbb{R}^{n^2}$ is nowhere dense, implying that the complement of a proper Zariski-closed subset is a dense open subset of $\mathbb{R}^{n^2}$ in the Euclidean sense. Thus, if $a<b$, then $[a,b]^{n^2}$ contains at least a point which is an interior point (in the Euclidean sense) of the complement of $\bigcup_{\sigma\in S_{n^2}}V(\sigma(f))$; in particular, there is a point with rational coordinates in the complement of $\bigcup_{\sigma\in S_{n^2}}V(\sigma(f))$. This shows that $(2)$ is true.

Coming back to $(1)$. To find such $n^2$ numbers $a_1,\ldots, a_{n^2}$ in $\mathbb{N}_{+}$, it is sufficient to find $n^2$ elements $b_1, \ldots, b_{n^2}$ in $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ for some prime number $p$, where some of the $b_i$ are allowed to be zero, but when lifting the zero elements back to $\mathbb{Z}$, we use $p$ instead. However, this won't give you a sharp upper bound (i.e. the existence of $a_1,\ldots, a_{n^2}$ does not guarantee the existence of $b_1, \ldots, b_{n^2}$). Let $K=\mathbb{F}_p$. Since $\mathbb{F}_p$ is a finite field, $\mathbb{F}_p^{n^2}$ is not longer irreducible, the above method does not work. But it is still true that $\bigcup_{\sigma \in S_{n^2}}V(\sigma(f))$ is not the whole $K^{n^2}$ as long as $p>n^2!n$. To see this, let's calculate the number of points in $V(f)$, to do this, we use the classical result that $$\left| \mathrm{GL}_n(\mathbb{F}_p)\right| = (p^n-1)(p^n-p)\cdot \cdots \cdot (p^n-p^{n-1}).$$ We see that $$|V(f)| = p^{n^2} - \left| \mathrm{GL}_n(\mathbb{F}_p)\right|=p^{n^2}-(p^n-1)(p^n-p)\cdot \cdots \cdot (p^n-p^{n-1}).$$ So \begin{align} \left|\bigcup_{\sigma\in S_n}V(\sigma(f))\right| &\leq n^2!\left[p^{n^2}-(p^n-1)(p^n-p)\cdot \cdots \cdot (p^n-p^{n-1})\right] \\ &<n^2!\left[p^{n^2}-(p^n-p^{n-1})^n\right] \\ &=p^{n^2}n^2!\left[1-\left(1-\frac{1}{p}\right)^n\right] \\ &=p^{n^2}n^2!\sum_{k=1}^n{n\choose k}(-1)^{k-1}\frac{1}{p^k}. \tag{A} \end{align} Notice that when $p>n^2!n$, for any $k$ such that $1\leq k< n$, we have $$p> n-k> \frac{n-k}{k+1} =\frac{\frac{n!}{(k+1)!(n-k-1)!}}{\frac{n!}{k!(n-k)!}}= \frac{n \choose k+1}{n\choose k},$$ so $${n\choose k} \frac{1}{p^k} > { n\choose k+1} \frac{1}{p^{k+1}}.$$ This means (think about the alternating series) in Inequality $(A)$ we have $$\sum_{k=1}^n {n\choose k}(-1)^{k-1}\frac{1}{p^k} \leq {n\choose 1} \frac{1}{p} =\frac{n}{p}.$$ Thus, $$\left|\bigcup_{\sigma\in S_{n^2}}V(\sigma(f))\right| < p^{n^2}\frac{n^2!n}{p}< p^{n^2}.$$

In conclusion, $(1)$ is also true.