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"?

  • 2
    $\begingroup$ When you say the coefficients are $a_i$, do you actually mean the elements? $\endgroup$
    – Mårten W
    Jun 25 '16 at 23:15
  • $\begingroup$ In the second question, you may consider a chain of field extensions. $\endgroup$
    – user1551
    Jun 26 '16 at 2:13
  • $\begingroup$ Difficult to formalize, but I'd bet that for the second question, all interval [a,b] with a<b satisfy (uncountable infinity of "candidates"). $\endgroup$
    – Piquito
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.