wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Rank of Redheffer Matrix
        
(Message started by: Aryabhatta on Apr 11^th, 2007, 4:54pm)

Title: Rank of Redheffer Matrix
Post by Aryabhatta on Apr 11^th, 2007, 4:54pm

Let RH_n be the nxn RedHeffer matrix (http://mathworld.wolfram.com/RedhefferMatrix.html) defined as:

RH_n(i,j) = 1 if i divides j or j = 1
RH_n(i,j) = 0 otherwise.

For instance RH₄ is
[1 1 1 1]
[1 1 0 1]
[1 0 1 0]
[1 0 0 1]

Prove that the rank of RH_n is atleast n-1.

Title: Re: Rank of Redheffer Matrix
Post by Eigenray on Apr 11^th, 2007, 6:48pm

The [hide]lower-right (n-1)x(n-1) submatrix is upper unitriangular[/hide].

2) Show that

det(RH_n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1ⁿ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mu.gif(k).

Hence RH_n is invertible except for

n=2, 39, 40, 58, 65, 93, ....

3) Is the above set infinite?

Title: Re: Rank of Redheffer Matrix
Post by Aryabhatta on Apr 12^th, 2007, 12:39am

on 04/11/07 at 18:48:23, Eigenray wrote:

3) Is the above set infinite?

Is this known?

Title: Re: Rank of Redheffer Matrix
Post by Eigenray on Apr 12^th, 2007, 3:48pm

No idea. You'd think they would say one way or the other on [link=http://mathworld.wolfram.com/MertensFunction.html]Mathworld[/link], but [link=http://www.research.att.com/~njas/sequences/A028442]Sloane[/link] usually says when a sequence is not known to be infinite.

It seems likely though. Here's a graph of M(n)/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn. It looks roughly like a random walk.

But it's not as a random as it looks -- on the right is a graph of A(A(A(M))), where

A(F)(n) = 1/n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1ⁿ F(k)

is the averaging operator. The position of the n-th maxima fits Ce^{.45 n} pretty well.