Integer sets without singular matrices

Let’s say that a set A\subset \mathbb N contains an n\times n singular matrix if there exists an n\times n matrix with determinant zero whose entries are distinct elements of A. For example, the set of prime numbers does not contain any 2\times 2 singular matrices; however, for every n\ge 3 it contains infinitely many n\times n singular matrices.

I don’t know of an elementary proof of the latter fact. By a 1939 theorem of van der Corput, the set of primes contains infinitely many progressions of length 3. (Much more recently, Green and Tao replaced 3 with an arbitrary k.) If every row of a matrix begins with a 3-term arithmetic progression, the matrix is singular.

In the opposite direction, one may want to see an example of an infinite set A\subset \mathbb N that contains no singular matrices of any size. Here is one:

Let \displaystyle A=\lbrace 2^{2^k}\colon k=0,1,2,3,\dots\rbrace: these numbers are 1 less than Fermat’s should-have-been-primes. Suppose that an n\times n matrix is filled with distinct elements of A. Then
\displaystyle \det A = \sum_{\sigma\in S_n} \mathrm{sign}\,(\sigma) \prod_{i=1}^n a_{i,\sigma(i)} where each product over i is a power of 2. Moreover, these powers of 2 are distinct by the uniqueness of binary representation of integers. It follows that the sum over \sigma is nonzero — again, by the uniqueness of binary representation.

This set is very sparse, because the sequence 2^{2^k} grows super-exponentially. Is there such an example with exponential growth? or even with polynomial growth?

Disclaimer: This being a weekend blog post (and not a research proposal), I did not study the literature.

Credit: Once again, to Colin Carroll for “Prime Matrices I,II”.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s