Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider some arbitrary number sequence like the decimal expansion of $\pi$ = {3, 1, 4, 1, 5, 9, 2}. Prepend the sequence with the number $1$ so that you get {1, 3, 1, 4, 1, 5, 9, 2}.

Then plug it into the first column in a matrix that has the following recurrence definition:

$$\begin{align} T(n,1) &= (n-1)\text{th digit of }\pi, \\ T(n,2) &= T(n,1) - T(n-1,2), \\ \text{for } k>2, T(n,k) &= \sum\limits_{i=1}^{k-1} T(n-i,k-1)-\sum\limits_{i=1}^{k-1} T(n-i,k) \end{align} $$

That table looks like this:

$$\displaystyle \left( \begin{array}{cccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -2 & 3 & 0 & 0 & 0 & 0 & 0 \\ 4 & 6 & -2 & 3 & 0 & 0 & 0 & 0 \\ 1 & -5 & 3 & -2 & 3 & 0 & 0 & 0 \\ 5 & 10 & 0 & 3 & -2 & 3 & 0 & 0 \\ 9 & -1 & 2 & -3 & 3 & -2 & 3 & 0 \\ 2 & 3 & 7 & 7 & -3 & 3 & -2 & 3 \end{array} \right)$$

Then calculate the matrix inverse of the matrix above:

$$\displaystyle \left( \begin{array}{cccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & \frac{1}{3} & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & \frac{2}{9} & \frac{1}{3} & 0 & 0 & 0 & 0 & 0 \\ 0 & -\frac{14}{27} & \frac{2}{9} & \frac{1}{3} & 0 & 0 & 0 & 0 \\ -1 & -\frac{1}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} & 0 & 0 & 0 \\ 1 & -\frac{146}{243} & -\frac{28}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} & 0 & 0 \\ -1 & -\frac{688}{729} & -\frac{11}{243} & -\frac{1}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} & 0 \\ 0 & \frac{694}{2187} & -\frac{850}{729} & -\frac{92}{243} & -\frac{1}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} \end{array} \right)$$

Why then is there the Möbius function sequence in the first column?

I have checked this for random sequences in programs like this:

(*Mathematica*)
Clear[t, n, k, a, b];
nn = 8;
a = Flatten[{1, RealDigits[N[Pi, nn - 1]][[1]]}]
Length[a]
t[n_, 1] := t[n, 1] = a[[n]];
t[n_, k_] := 
  t[n, k] = 
   If[And[n > 1, k > 1], 
    If[k == 2, t[n, k - 1] - t[n - 1, k], 
     Sum[t[n - i, k - 1], {i, 1, k - 1}] - 
      Sum[t[n - i, k], {i, 1, k - 1}]], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A]
MatrixForm[Inverse[A]]

for up to 100 times 100 matrices and I always get the Möbius function in the first column.

I believe it has something do with the fact that the divisibility matrix equal to 1 if k divides n and 0 otherwise:

$$\displaystyle \left( \begin{array}{cccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right)$$

satisfies the recurrence, that (edit 21.7.2014) Jeffrey Shallit formulated for me:

$$\begin{align} T(n,1) &= 1, \\ \text{for } k>1, T(n,k) &= \sum\limits_{i=1}^{k-1} T(n-i,k-1)-\sum\limits_{i=1}^{k-1} T(n-i,k) \end{align}$$

and also the recurrence:

$$\begin{align} T(n,1) &=1, \\ T(n,2) &= T(n,1)-T(n-1,2),\\ \text{for } k>2, T(n,k) &= \sum\limits_{i=1}^{k-1} T(n-i,k-1) -\sum\limits_{i=1}^{k-1} T(n-i,k) \end{align}$$ which is the same as the first recurrence in the beginning of the question except that the first column here is equal to 1,1,1...


Edit 28.3.2014:

(*Mathematica Mats Granvik 28.3.2014*)
Clear[A, t, n, k, a, nn];
nn = 8;
a = Table[StringJoin[{"x", ToString[n]}], {n, 1, nn}]
Length[a]
t[n_, 1] := t[n, 1] = a[[n]];
t[n_, k_] := 
  t[n, k] = 
   If[And[n > 1, k > 1], 
    If[k == 2, t[n, k - 1] - t[n - 1, k], 
     Sum[t[n - i, k - 1], {i, 1, k - 1}] - 
      Sum[t[n - i, k], {i, 1, k - 1}]], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A]
MatrixForm[a[[1]]*Inverse[A]]

Outputs: 1,-1,-1,0,-1,1,-1,0,...


Edit 7.4.2013:

Input: {"x0", "x1", "x2", "x3", "x4", "x5", "x6", "x7", "x8", "x9", "x10"}

Mathematica program:

(*Mathematica Mats Granvik 7.4.2014*)
Clear[A, t, n, k, a, nn];
nn = 11;
a = Table[StringJoin[{"x", ToString[n - 1]}], {n, 1, nn}]
Length[a]
t[n_, 1] := t[n, 1] = If[n <= 3, 1, a[[n]]];
t[n_, k_] := 
  t[n, k] = 
   If[n >= k, 
    If[n <= 3, 1, 
     If[And[k > 1], 
      If[Or[k == 2, k == 3], 
       t[n, k - 1] - Sum[t[n - i, k], {i, 1, k - 1}], 
       If[k >= 4, 
        Sum[t[n - i, k - 1], {i, 1, k - 2}] - 
         Sum[t[n - i, k], {i, 1, k - 1}], 0], 0], 0, 0], 0], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A]
Inverse[A][[2 ;; nn, 1]]

Output; {-1, 0, -1, -1, -2, -1, -2, -2, -2, -1}

Which is the Mertens function with the first term negated.


Edit 21.7.2014:

The matrix inverse of this triangle:

$$\left( \begin{array}{cccccc} x_1 & 0 & 0 & 0 & 0 & 0 \\ x_2 & x_2 & 0 & 0 & 0 & 0 \\ x_3 & x_3-x_2 & x_2 & 0 & 0 & 0 \\ x_4 & x_2-x_3+x_4 & x_3-x_2 & x_2 & 0 & 0 \\ x_5 & -x_2+x_3-x_4+x_5 & x_4-x_3 & x_3-x_2 & x_2 & 0 \\ x_6 & x_2-x_3+x_4-x_5+x_6 & x_2-x_4+x_5 & x_4-x_3 & x_3-x_2 & x_2 \end{array} \right)$$

gives the möbius function function divided by $x_1$.


Edit 24.7.2014:

(*Program start*)
(*Mathematica Mats Granvik 24.7.2014*)
Clear[A, t, n, k, a, nn];
nn = 32;
Print["Random numbers as input:"]
a = RandomReal[7, nn]
Length[a];
t[n_, 1] := t[n, 1] = a[[n]];
t[n_, k_] := 
  t[n, k] = 
   If[And[n > 1, k > 1], 
    If[k == 2, t[n, k - 1] - t[n - 1, k], 
     Sum[t[n - i, k - 1], {i, 1, k - 1}] - 
      Sum[t[n - i, k], {i, 1, k - 1}]], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A];
B = a[[1]]*Inverse[A];
Print["Möbius function as output:"]
MatrixForm[B];
Chop[B[[All, 1]]]
(*program end*)
share|improve this question
    
Your observation is correct. –  Hagen von Eitzen Dec 31 '12 at 13:59
    
Have you tried it with a non-"random" sequence? Such as all $1$? –  Thomas Andrews Dec 31 '12 at 13:59
    
@ThomasAndrews Yes I have tried it with the all 1 sequence. That is the same as the last recurrence at the end of my writing. –  Mats Granvik Dec 31 '12 at 14:02
    
Yeah, my point is that the "random" part of the question is misleading - it has nothing to do with whether the initial sequence is "random." –  Thomas Andrews Dec 31 '12 at 14:21
    
My answer is wrong - you probably want to unselect it if you want to get a correct answer. I'm thinking about how I can fix it, but it is being stubborn. I suspect I'm on the right track, just stuck on a few points. –  Thomas Andrews Dec 31 '12 at 17:18

1 Answer 1

up vote 3 down vote accepted

(This argumen isn't working out - the "shift" issue is the problem - it doesn't quite work.)

(Actually, I'm pretty sure this answer is wrong, but something like it is almost certainly the correct approach. The problem is that the value for $(0,1,0,0,...)$ is not as simple as the shift operator I gave.

Take the vector equal to the difference of your digits, so $x=(x_i)=(1,3-1,1-4,\dots)$.

Then your matrix is a linear map of $x=(x_i)$. That is, if $A(x)$ is the matrix gotten from $x=(x_1,...,x_m)$ by starting with $T(n,1)=\sum_{i=1}^n x_i$, and computing as above, then $A(x+x')=A(x)+A(x')$ and $A(\alpha x)=\alpha A(x)$ for any constant $\alpha$.

Now, when $x=(1,0,0,...)$ you get the matrix at the bottom of your question. Let's call that matrix $B = A(1,0,...0)$.

If $x=(0,1,0,...)$ then $A(x)$ is just that same matrix with the bottom row dropped, and a top row of $0$s added. That is $MB$, where $M$ is the matrix with $1$s just below the diagonal.

(This argument is still not quite working out, but it goes somethThis all means that if $x=(x_i)$ then $A(x)=\left(\sum_{i=1}^{m} x_i M^{i-1} \right)B$

The matrix $\sum_{i=1}^m x_iM^{i-1}$ is a lower diagonal matrix, with $x_1$ in all the diagonal elements. If $x_1\neq 0$, this is invertible, and its inverse is an lower -diagonal matrix, and all the diagonals are $x_1^{-1}$.

On the other hand $B^{-1}$ is can be easily seen to have $\mu(k)$ in the left column. So $B^{-1}\left(\sum_{i=1}^m x_iM^{i-1}\right)^{-1}$ has $x_1^{-1}\mu(k)$ along the left column.

But that is precisely the inverse of your matrix, so when $x_1=1$, we are done.

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.