Thursday, January 19, 2012

Eigensequence of a triangle, & Eigentriangle

Given triangle M as an infinite lower triangular matrix, there is some sequence prefaced with a "1" such that M*(seq prefaced with a 1) shifts the sequence to the left, deleting the "1", while the rest of the sequence remains the same. That seq is the Eigensequence of a triangle (defined without the prepended 1).
.
Example: The Eigensequence of Pascal's triangle is A000110 in Sloane's Encyclopedia of Integer Sequences: (1, 2, 5, 15, 52,...) = the Bell seq; since letting the Pascal matrix = M, then M*(1, 1, 2, 5, 15, 52,...) = (1, 2, 5, 15, 52,...).
.
Getting the Eigensequence. Simple. Place a "1" at the top of the triangle M, getting: (using the initial Pascal's triangle):
1
1;
1, 1;
1, 2, 1;
1, 3, 3, 1;
1, 4, 6, 4, 1;
...
= new triangle Q. Take successive powers of Q, shifting all terms into a vector which is (1, 1, 2, 5, 15, 52,...). Delete the initial 1 getting (1, 2, 5, 15, 52,...), = the Bell sequence which is the Eigensquence of Pascal's Triangle.
...
THEOREM: Given an infinite Toeplitz triangle with sequence S(n) in every column, we obtain the Eigensequence as before; with the additional property that in such a Toeplitz triangle, the Eigensequence is the INVERT transform of S(n).
...
Example: Given S(n) = (1, 2, 3, 4,...), our Toeplitz triangle =
1;
2, 1;
3, 2, 1;
4, 3, 2, 1;
... = M
We place a "1" at top, take powers, getting our left-shifted vector (even-indexed Fibonacci numbers after deleting the 1): (1, 3, 8 21, 55,...). So (1, 3, 8, 21,...) is the Eigensequence of the triangle and the INVERT transform of (1, 2, 3, 4,....), the natural numbers.
.
To obtain an Eigentriangle R which has row sums of the Eigensequence of triangle M, we take the row terms of M, multiplying pairwise by terms in its Eigensequence (prefaced with a 1). Thus, using the above triangle M and (1, 1, 3, 8, 21,...) our products are (1), [(2,1)*(1,1) = (2,1)], then [(3,2,1)*(1,1,3) = (3,2,3)];, then [(4,3,2,1)*(1,1,3,8) = (4,3,6,8)]; so our Eigentriangle R =
1;
2, 1;
3, 2, 3;
4, 3, 6, 8;
... = R
...which as you can see has row sums of (1, 3, 8, 21,...). Thus, R is the Eigentriangle of triangle M.

Matrix generation of sequences

Observe the following infinite square production matrix:
1, 1, 0, 0, 0, 0,...
A, 0, 1, 0, 0, 0,...
B, 0, 0, 1, 0, 0,..
C, 0, 0, 0, 1, 0,...
D, 0, 0, 0, 0, 1,...
...
Say we have a finite (A,B,C) = (1, 1, 2). Then the g.f. (generating function) is:
1/(1-Ax-Bx^2-Cx^3) = 1/(1-x-x^2-2x^3) and the recursive relationship is:
a(n) = A*a(n-1) + B*a(n-2) + C *a(n-3).
The matrix generator is:
1, 1, 0
1, 0, 1
2, 0, 0
= M.
Any of these methods generates A077947: (1, 2, 5, 9, 18, 37, 73,...) as follows:
First, we plug in 1/(1-x-x^2-2x^3) into WolframAlpha, enter, and up comes the sequence.
By recursion, 18 = 1*9 + 1*5 + 2*2 = 9 + 5 = 4; or, a(n) = 1*a(n-1) + 1*a(n-2) * 2*a(n-3).
Or, let the Matrix = M, then take successive powers * the vector
[1
0
0]
...accessing top term; thus a(n) = M^n*[1,0,0], top term. Note that we extract the generating matrix M from the infinite square production matrix, such that M is an n*n matrix depending on the numbers of terms in (A,B,C...). That is, 3 in this case.