A259363 Number of distinct elements in the Gram matrix of the first M rows of the Kronecker product (Sylvester) Hadamard matrix.

0, 1, 2, 3, 2, 4, 4, 3, 2, 4, 5, 6, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9, 10, 7, 8, 7, 6, 4, 5, 6, 7, 6, 9, 8, 7, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9, 10, 7, 8, 7, 6, 5, 8, 9, 10, 9, 12, 11, 10, 7, 8, 9, 10, 7, 8, 7, 6, 4, 5, 6, 7, 6, 9, 8, 7, 6, 9, 10, 11, 8, 9, 8, 7, 4, 5, 6, 7, 6, 9, 8, 7, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9

Offset

0,3

Comments

Let H(2) = [1, 1; 1, -1]; let H(2^(n+1)) be the Kronecker product of H(2^n) and H(2). For M less than or equal to 2^n, let A(2^n,M) be the submatrix of H(2^n) consisting of its first M rows, and let G(2^n,M)=(A(2^n,M))'A(2^n,M). Then a(M) is the number of distinct elements of G(2^n,M), which depends only on M.

Links

Table of n, a(n) for n=0..138.

Math Stackexchange, Relation between number of unique values in Gramian Matrix (G) and the matrices that created it

Formula

Recurrence for M>0: let b be the base-2 representation of M. Map b to a word w on the alphabet {1,I,O} by splitting b into runs of 0's and 1's and letting O represent a string of one or more 0's, I a string of two or more 1's, and 1 an isolated 1. Then a(0)=0, a(n)=s(w), where s(1)=1, s(1O1)=4, s(uO)=s(u)+1, s(vI)=s(v1)+2, s(vIO1)=s(v1)+4, s(v1O1)=s(v1)+4, where u is a nonempty word and v is an arbitrary word.

Closed form: s(1)=1, s(1O)=2, s(w)=4[(|w|+1)/2]+a(w)+b(w)+c(w), where |w| is the length of w, [x] is the greatest integer function, and a, b, c are defined by a(w)=0 if w ends in O, -1 if w ends in 1 or I; b(w)=1 if first letter of w is I, 0 if first letter of w is 1; c(w)=-1 if last non-O letter of w is I, -3 if last non-O letter of w is 1.

Equivalently, for n > 1, a(n) = 4*A069010(n) - A000035(n) + A079944(n-2) + 4 - A099545(n-1) + A036987(n-1).

Example

H(4)=[1,1,1,1;1,-1,1,-1;1,1,-1,-1;1,-1,-1,1], A(4,3)=[1,1,1,1;1,-1,1,-1;1,1,-1,-1], G(4,3)=[3,1,1,-1;1,3,-1,1;1,-1,3,1;-1,1,1,3]. Since G(4,3) has 3 distinct elements, a(3)=3.

Mathematica

mToWord[m_] := Module[{binary, sbin, lst, j},
  binary = IntegerDigits[m, 2];
  sbin = Split[binary];
  lst = {};
  For[j = 1, j <= Length[sbin], j++,
   If[sbin[[j, 1]] == 1 && Length[sbin[[j]]] > 1, AppendTo[lst, 11]];
   If[sbin[[j]] == {1}, AppendTo[lst, 1]];
   If[sbin[[j, 1]] == 0, AppendTo[lst, 0]]
   ];
  lst
  ]
s[{1}]=1
s[{1, 0}]=2
s[w_] := Module[{b, newW, a, c},
  If[w[[1]] == 11,
   b = 1,
   b = 0
   ];
  If[w[[-1]] != 0,
   newW = Append[w, 0];
   a = -1,
   newW = w;
   a = 0
   ];
  If[newW[[-2]] == 1,
   c = -3,
   If[newW[[-2]] == 11,
    c = -1
    ]
   ];
  a + b + c + 2 Length[newW]
  ]
numberDistinctGramValues[m_]:=If[m==0, 0, s[mToWord[m]]]

Crossrefs

Cf. A000975, A240908, A240909, A240910.

Sequence in context: A274228 A321476 A214567 * A087437 A304739 A304735

Adjacent sequences: A259360 A259361 A259362 * A259364 A259365 A259366

Keyword

nonn,easy

Author

William P. Orrick, Jun 24 2015

Status

approved