A363099 Triangle T(n,k) in which the n-th row encodes the inverse of a 3n+1 X 3n+1 Jacobi matrix, with 1's on the lower, main, and upper diagonals in GF(2), where the encoding consists of the decimal representations for the binary rows (n >= 1, 1 <= k <= 3n+1).

11, 3, 12, 13, 91, 27, 96, 107, 3, 108, 109, 731, 219, 768, 859, 27, 864, 875, 3, 876, 877, 5851, 1755, 6144, 6875, 219, 6912, 7003, 27, 7008, 7019, 3, 7020, 7021, 46811, 14043, 49152, 55003, 1755, 55296, 56027, 219, 56064, 56155, 27, 56160, 56171, 3, 56172, 56173, 374491, 112347, 393216, 440027, 14043, 442368

Offset: 1

Author

Nei Y. Soma, May 20 2023

Keywords

• nonn
• base
• tabf

Comments

Each term in the sequence encodes a line of the inverse of a Jacobi matrix that has 1s on its lower, main, and upper diagonals in GF(2). The associated inverse matrix column values come from the binary representation of that base-10 number, being a bit per column. These matrices start with a 4 X 4 matrix and the consecutive terms came by adding ascending and consecutive multiples of 3. If the binary number has fewer bits than the number of columns, it must be zero-padded to the left. To obtain the inverse matrices in real numbers instead of GF(2), alternate between + and - between the 1s in a row. If a row is a multiple of 3, alternate between - and +. The determinants of these 3m+1 X 3m+1 Jacobi matrices are 1 in GF(2), and alternate between -1 and 1 in R if m is odd or even. These properties were proven by Sutner (1989) and Melo (1997), respectively.

Examples

			For m = 1, the Jacobi 4 X 4 matrix has as rows
     1, 1, 0, 0
     1, 1, 1, 0
     0, 1, 1, 1
     0, 0, 1, 1
Its inverse has the rows
     1, 0, 1, 1
     0, 0, 1, 1
     1, 1, 0, 0
     1, 1, 0, 1
Representing these rows as binary numbers in base 10 the first three terms of the sequence are: 11, 3, 12, 13.
The next numbers in the sequence occur for m = 2, given a sequence of six numbers. The Jacobi 7 X 7 matrix has as its rows:
     1, 1, 0, 0, 0, 0, 0
     1, 1, 1, 0, 0, 0, 0
     0, 1, 1, 1, 0, 0, 0
     0, 0, 1, 1, 1, 0, 0
     0, 0, 0, 1, 1, 1, 0
     0, 0, 0, 0, 1, 1, 1
     0, 0, 0, 0, 0, 1, 1
Its inverse has as rows:
     1, 0, 1, 1, 0, 1, 1
     0, 0, 1, 1, 0, 1, 1
     1, 1, 0, 0, 0, 0, 0
     1, 1, 0, 1, 0, 1, 1
     0, 0, 0, 0, 0, 1, 1
     1, 1, 0, 1, 1, 0, 0
     1, 1, 0, 1, 1, 0, 1
These 7 latter rows from binary to base 10 give the next 7 terms of the sequence: 91, 27, 96, 107, 3, 108, 109.
Triangle T(n,k) begins:
    11,    3,   12,   13;
    91,   27,   96,  107,   3,  108,  109;
   731,  219,  768,  859,  27,  864,  875,  3,  876,  877;
  5851, 1755, 6144, 6875, 219, 6912, 7003, 27, 7008, 7019, 3, 7020, 7021;
  ...
		

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Boston, 2nd Ed., 12th printing, 2002, pp. 24-25.
• P. Lancaster and M. Tismenetsky, The Theory of Matrices, Academic Press, Boston, 1985, p. 35.
• J. P. Melo, Reversibility of John von Neumann cellular automata, M.Sc. Thesis, Division of Computer Science, Instituto Tecnológico de Aeronáutica, 1997 (in Portuguese), p. 18.

Links

• Nei Y. Soma, Rows n = 1..30, flattened
• K. Sutner, Linear Cellular Automata and the Garden-of-Eden, The Mathematical Intelligencer, 11(2), 1989, pp. 49-53; see p. 52

Crossrefs

Column k=1 gives A245599(n+1).

Column k=2 gives A083713.

Column k=3 gives A204623.

T(n,3n-1) gives A010701.

Cf. A038184 One-dimensional cellular automaton (Rule 150) in a tape with 3m cells has as adjacency matrix the Jacobi matrices, 3m X 3m, with 1s on the lower, main and upper diagonals and the operations on it are in GF(2). And A363146 for the inverse of Jacobi matrices 3m X 3m, with 1s on the lower, main, and upper diagonals in GF(2).

Programs

Maple

T:= n-> (M-> seq(add(abs(M[j, n*3+1-i])*2^i, i=0..n*3), j=1..n*3+1))
               (Matrix(n*3+1, (i, j)-> `if`(abs(i-j)<2, 1, 0))^(-1)):
seq(T(n), n=1..6);  # Alois P. Heinz, May 20 2023

Mathematica

sequence = {};
For[k = 1, k <= 50, k++, {
  n = 3*k + 1;
  J = ConstantArray[0, {n, n}];
  For[i = 1, i < n, i++,
   J[[i, i]] = J[[i + 1, i]] = J[[i, i + 1]] = 1];
  J[[1, 1]] = J[[n, n]] = 1;
  InvJ = Mod[Inverse[J], 2];
  For[i = 1, i <= n, i++, AppendTo[sequence, FromDigits[InvJ[[i]], 2]]]
  }
 ]
sequence

PARI

row(n)=my(m=3*n+1, A=lift(matrix(m, m, i, j, Mod(abs(i-j)<=1, 2))^(-1))); vector(m, i, fromdigits(A[i,], 2)) \\ Andrew Howroyd, May 20 2023

Formula

The recurrence has as its base:

r(1, 1) = 11;

r(2, 1) = 3;

r(3, 1) = 12;

r(4, 1) = 13.

For 2 <= k <= m, and i = 1, 2, 3, ..., 3k - 2:

r(i, k) = 8*r(i, k-1) + r(2, 1) (i != 0 (mod 3)).

And r(3k-1, k) = r(2, 1);

r(3k, k) = 8*r(3(k-1), k-1) + r(3,1);

r(3k+1, k) = 8*r(3(k-1), k-1) + r(4,1).