Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am motivated by the following paper by Greg Martin and Erick B. Wong:

http://www.math.ubc.ca/~gerg/papers/downloads/AAIMHNIE.pdf

Here the authors prove that assuming that the entries of an $n \times n$ matrix are chosen randomly with respect to a uniform distribution from the set {$-k, -k + 1 \cdots, -1, 0, 1, \cdots, k-1, k$}, then the probability that the resulting matrix will be singular is $\ll k^{-2 + \epsilon}$ (lemma 1 in the above paper).

What I am interested in is a more refined case. Suppose that $H, D$ are positive integers, and suppose that $(a_h, b_h, c_h, d_h)$, $1 \leq h \leq H$, are tuples of integers. Consider the monomials $m_r(a, b, c, d) = a^u b^v c^w d^x$, where $u + v + w + x = D$, and $u,v,w,x$ are non-negative integers. Here we allow $(u,v,w,x)$ to range over all possible choices. Let $R$ be the number of such monomials, which by construction is $\displaystyle \binom{D+3}{3} = \frac{(D+3)(D+2)(D+1)}{6}$, and consider the $H \times R$ matrix where the $hr$-th entry is the monomial $m_r(a_h, b_h, c_h, d_h)$. Finally, we can assume that $R < H$ to make the problem interesting.

Now suppose that the integers $a_h, b_h, c_h, d_h$, $1 \leq h \leq H$ are chosen uniformly from the set {$-k, \cdots, -1, 0, 1, \cdots, k$} say, then what is the probability that the resulting matrix will have rank at most $R-1$?

This amounts to showing that every sub $R \times R$ matrix is singular, and so is related to the original paper cited.

share|improve this question

2 Answers 2

One can actually do better and get an asymptotic formula for the number of matrices of fixed rank. See the following paper:

Katznelson, Yonatan R. Integral matrices of fixed rank. Proc. Amer. Math. Soc. 120 (1994), no. 3, 667–675.

The main result is as follows:

Let $N(T; n, m, k)$ denote the number of integral $n \times m$ matrices of rank $k$, and norm at most $T$.

Theorem 1. For $n \geq m > k \geq 1$ and as $T \to \infty$:

(1) for $n>m$, $N(T; n, m,k) = a(n, m,k)T^{nk} + O(T^{nk-1}).$

(2) for $n=m$, $N(T;n,n,k) = p(n,k)T^{nk}\log T + O(T^{nk}).$

The methods of proof are pretty elementary (at least according to the author).

share|improve this answer

I'd guess that the probability of having even one singular $R \times R$ minor is about equal to the probability of having a tuple which is either 0 or a multiple of another one. What is the probability that a given $R \times R$ minor is non-singular? I'd suspect that the probability is similar to that from the original paper for $n=4.$ (so at least $1-\frac{C}{k^2}.$)

The article you cite mentions that the actual probability is much lower and not much higher than the probability of an all $0$ row. This does not surprise me. Suppose that you have chosen $0 \le r \lt n$ rows and that the rank so far is $r.$ What could go wrong with the next row? It might be all $0$ or plus or minus a previous row. For it to be some other non-zero rational multiple of a previous row seems pretty unlikely and to be a linear combination even less so.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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