Given $B>0$ and $n\in\Bbb N$ what is the probability that a given $n\times n$ integer matrix with all entries bound by absolute value $<B$ is non-singular? I am looking for precise scaling.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ I was perplexed by your use of nonsingular for integer matrices. Do you mean having an inverse with integer entries (in GL($n,{\bf Z}$), or do you mean having an inverse with rational entries (having nonzero determinant)? $\endgroup$– David HandelmanCommented Mar 4, 2017 at 19:49
-
$\begingroup$ @DavidHandelman just non-zero det. $\endgroup$– TurboCommented Mar 4, 2017 at 19:51
-
$\begingroup$ @DavidHandelman Not related to this query. In your paper citeseerx.ist.psu.edu/viewdoc/… representing polynomials by positive linear combination of product of linear forms which represent a polytope - (1) Does the converse result hold? (2) can we extend this to rational functions (not just polynomials)? (3) Does the size of the linear combination differ much of we allow general (not just positive) linear combination? Any references? $\endgroup$– TurboCommented Mar 4, 2017 at 23:17
-
$\begingroup$ That article (which invariably is quoted for a routine result, rather than the much more interesting characterization of polytopes affinely equivalent to a product of simplices) has a number of results. So, the converse to which? $\endgroup$– David HandelmanCommented Mar 5, 2017 at 1:58
-
$\begingroup$ @DavidHandelman So if you have a polytope defined by linear forms you get a polynomial (is it unique in any sense?). So converse being given a polynomial when can one get a polytope up to some equivalence? $\endgroup$– TurboCommented Mar 5, 2017 at 10:35
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
If I understand the question correctly, this is a known hard problem if $B$ is fixed, but $n$ is growing. See, for example, this paper, written by some fairly smart people:
On the singularity probability of discrete random matrices Jean Bourgain, Van Vu, P. M. Wood (sorry, insert citation is failing), JFA 2010.
However, if $n$ is fixed, but $B$ is growing, this is well-understood, see the paper by Yonatan Katznelson (DMJ, 1994, "Singular matrices and a uniform bound for congruence subgroups of $SL(n, \mathbb{Z})$"), his main result is that the probability is of order $\log B/B^n,$ with explicit constants.
answered Mar 4, 2017 at 17:38
-
$\begingroup$ See also my paper with Erick B. Wong for references to work on this problem. $\endgroup$ Commented Mar 4, 2017 at 23:31
-
1$\begingroup$ @GregMartin Thanks, that is a nice paper, and I did not know about it, but also in my 2008 Duke paper (and in much greater detail in Gorodnik/Nevo MRL 2011) it is shown that a stronger statement is true: the probability of having reducible characteristic polynomial (or, better yet, characteristic polynomial with Galois group smaller than $S_n$) goes to zero. The methods are far from elementary (certainly nothing like your Monthly paper!), but one can use the much simpler Wolfgang Schmidt technology to get results. $\endgroup$ Commented Mar 5, 2017 at 1:37
$\begingroup$
$\endgroup$
3
In the simplest case $n=2$ is is possible to prove that this probability is equals to $$1-\frac{3\log B}{\pi^2B^2}+O\left(\frac{1}{B^2}\right)$$ for large $B$.
To do this let us observe that every singular matrix is born from integer vector $v=(a,b)$ with coprime $a,b<B$ and with positive maximum component, and consists of vectors $iv,jv$ with integers $i,j$ such that $|i|,|j|<\frac{B}{\max(a,b)}$. Because of zero matrix repeats in counting in $O(B^2)$ cases the quantity of singular matrices equals to $$\sum_v 4 \phi(\max(a,b))\left[\frac{B}{\max(a,b)} \right ]^2 +O(B^2)= 8\sum_{b=2}^B \phi(b) \left[\frac{B}{b} \right ]^2 + O(B^2).$$ Sum after coefficient is also equal to: $$S=\sum_{l=0}^B (2l+1) \sum_{k=2}^{[B/l]} \phi(k).$$
Let us remember the summation formala and let us write $\sum_{k \leq n} \phi(k)=3n^2/\pi^2+c(n)n\log n$ with $c(n)<C$ all $n\leq B$. After some manipulations wuth integer part we can also write: $$ \sum_{k=2}^{[B/l]} \phi(k) = \frac{3B^2}{\pi^2l^2}+c\left (\frac{B}{l} \right ) \frac{B}{l} \log \frac{B}{l}.$$ So $S=S_1+S_2$, where $$ S_1 = \sum_{l=0}^B (2l+1) \frac{3B^2}{\pi^2l^2}=\frac{6}{\pi^2}B^2 \log B+O(B^2),$$ and $$S_2 = \sum_{l=0}^B (2l+1) c\left (\frac{B}{l} \right ) \frac{B}{l} \log \frac{B}{l} \leq CB\sum_{l\leq B} (\log B - \log l) = O(B^2).$$ Finally, we have that number of nonsingular matrices equals to $(2B-1)^4-8S+O(B^2)$, so the corresponding probability is equal to $$1-\frac{8S}{(2B-1)^4}+O\left(\frac{1}{B^2}\right)=1-\frac{3\log B}{\pi^2B^2}+O\left(\frac{1}{B^2}\right).$$
answered Mar 4, 2017 at 12:24
-
2$\begingroup$ Indeed, this is a special case of Theorem 1 of my paper with Erick B. Wong. $\endgroup$ Commented Mar 4, 2017 at 23:31
-
1$\begingroup$ Greg, thanks for your link! Of course I realised that such a classical problem should be already solved even in common case but considered it as some exercise. $\endgroup$ Commented Mar 5, 2017 at 9:19
-
1$\begingroup$ No problem, helpful instincts are always good instincts! $\endgroup$ Commented Mar 5, 2017 at 9:25