login
Infinite Redheffer matrix read by upwards antidiagonals.
19

%I #66 Jan 04 2022 18:52:05

%S 1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,0,0,0,0,1,1,0,0,1,0,1,1,1,0,0,0,0,1,

%T 0,1,1,0,0,0,1,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,1,1,1,1,0,

%U 0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,0,1,0,1

%N Infinite Redheffer matrix read by upwards antidiagonals.

%C Note that Redheffer's matrix (1977) is actually given by A077049: the first row starts with a single 1. We follow the nomenclature of Wilf, Dana, Vaughan and Weisstein, which uses the transpose and sets the first column to all-1. - _R. J. Mathar_, Jul 22 2017

%C The determinant of the n X n Redheffer matrix is given by Mertens's function A002321(n) [Barrett].

%C For n > 1, replacing a(n,n) with 0 in the Redheffer matrix and taking the determinant gives Moebius(n) = A008683(n). The number of permutations with nonzero contribution to this determinant is given by A002033. For first few n, these permutations are shown in the sequences A144193 to A144201. - _Mats Granvik_, Sep 14 2008

%C The determinant that is the Moebius function was discovered by reading the blog post "The Mobius function is strongly orthogonal to nilsequences" by _Terence Tao_. - _Mats Granvik_, Jan 24 2009

%D R. C. Vaughan, On the eigenvalues of Redheffer's matrix I, in: Number Theory with an Emphasis on the Markoff Spectrum (Provo, Utah, 1991), 283-296, Lecture Notes in Pure and Appl. Math., 147, Dekker, New-York, 1993.

%H Enrique Pérez Herrero, <a href="/A143104/b143104.txt">Rows n = 1..100 of triangle, flattened</a>

%H W. B. Barret, R. W. Forcade and A. D. Pollington, <a href="http://dx.doi.org/10.1016/0024-3795(88)90241-8">On the spectral radius of a (0,1) matrix related to Mertens' Function</a>, Lin. Alg. Applic. 107 (1988) 151-159.

%H Olivier Bordellès and Benoit Cloitre, <a href="http://www.emis.de/journals/JIPAM/images/317_08_JIPAM/317_08.pdf">A matrix inequality for Möbius functions</a>, J. Inequal. Pure and Appl. Math., Volume 10 (2009), Issue 3, Article 62, 9 pp.

%H Will Dana, <a href="https://sites.math.washington.edu/~morrow/336_15/papers/will.pdf">Eigenvalues of the Redheffer Matrix and their relation to the Mertens Function</a>, (2015)

%H R. M. Redheffer, <a href="http://dx.doi.org/10.1007/978-3-0348-5936-3_13">Eine explizit lösbare Optimierungsaufgabe</a>, Internat. Schiftenreihe Numer. Math., 36 (1977), 213-216.

%H T. Tao, <a href="http://terrytao.wordpress.com/2008/07/13/the-mobius-and-nilsequences-conjecture/">The Mobius function is strongly orthogonal to nilsequences</a>

%H R. C. Vaughan, <a href="http://dx.doi.org/10.1017/S1446788700037654">On the eigenvalues of Redheffer's matrix, II</a>, J. Austral. Math. Soc. (Series A) 60 (1996), 260-273.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RedhefferMatrix.html">Redheffer Matrix</a>.

%H Herbert S. Wilf, <a href="http://arxiv.org/abs/math/0408263">The Redheffer matrix of a partially ordered set</a>, arXiv:math/0408263 [math.CO], 2004.

%H Herbert S. Wilf, <a href="https://doi.org/10.37236/1867">The Redheffer matrix of a partially ordered set</a>, The Electronic Journal of Combinatorics 11(2) (2004), #R10.

%F a(i,j) = 1 if j=1 or i|j; 0 otherwise.

%F a(A000217(n)) = a(A000217(n)+1) = 1. - _Enrique Pérez Herrero_, Apr 16 2010

%e 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

%e 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

%e 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0

%e 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1

%e 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1

%e 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0

%e 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0

%e 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0

%e 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0

%e 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1

%e 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

%e 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

%e 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

%e 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0

%e 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0

%e 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0

%e 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

%e 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

%e 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

%e 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

%p A143104 := proc(i,j)

%p if modp(j,i) =0 or j = 1 then

%p 1;

%p else

%p 0;

%p end if;

%p end proc:

%p for d from 2 to 10 do

%p for m from d-1 to 1 by -1 do

%p n := d-m ;

%p printf("%d ",A143104(n,m)) ;

%p end do:

%p end do: # _R. J. Mathar_, Jul 23 2017

%t Redheffer[i_, j_] := Boole[Divisible[i, j] || (i == 1)];

%t T[n_] := n*(n + 1)/2;

%t S[n_] := Floor[1/2 + Sqrt[2 n]];

%t j[n_] := 1 + T[S[n]] - n;

%t i[n_] := 1 + S[n] - j[n];

%t A143104[n_] := Redheffer[i[n], j[n]]; (* _Enrique Pérez Herrero_, Apr 13 2010 *)

%t a[i_, j_] := If[j == 1 || Divisible[j, i], 1, 0];

%t Table[a[i-j+1, j], {i, 1, 14}, {j, 1, i}] // Flatten (* _Jean-François Alcover_, Aug 07 2018 *)

%o (Excel) =if(mod(column();row())=0;1;if(column()=1;1;0)). Produces the Redheffer matrix.

%o (PARI) { a(i,j) = (j==1) || (j%i==0); }

%Y Cf. A008683, A051731.

%Y Cf. A002033, A144193 .. A144201, A143142. - _Mats Granvik_, Sep 14 2008

%K nonn,tabl

%O 1,1

%A _Mats Granvik_, _Roger L. Bagula_ and _Gary W. Adamson_, Jul 24 2008

%E Edited and extended by _Max Alekseyev_, Oct 28 2008