login
Triangle read by rows: T(n, k) gives the coefficients of x^k of the characteristic polynomial P(n, x) of the n X n matrix M with entries M(i, j) = 1 if i = 1 or j = 1, -1 if i = j > 1, and 0 otherwise. T(0, 0):= 0.
0

%I #40 Feb 04 2018 13:06:42

%S 0,1,-1,-2,0,1,3,3,-1,-1,-4,-8,-3,2,1,5,15,14,2,-3,-1,-6,-24,-35,-20,

%T 0,4,1,7,35,69,65,25,-3,-5,-1,-8,-48,-119,-154,-105,-28,7,6,1,9,63,

%U 188,308,294,154,28,-12,-7,-1,-10,-80,-279,-552,-672,-504,-210,-24,18,8,1

%N Triangle read by rows: T(n, k) gives the coefficients of x^k of the characteristic polynomial P(n, x) of the n X n matrix M with entries M(i, j) = 1 if i = 1 or j = 1, -1 if i = j > 1, and 0 otherwise. T(0, 0):= 0.

%C The norm of the matrix M appears to be sqrt(n), where with norm is meant the eigenvalue of the largest magnitude, negative or positive. Row sums appear to be A085750 [see below for the proof].

%C Also the coefficients of the characteristic polynomial of the matrix defined by the recurrence: A(n, k) = if n < k then if and(n > 1, k > 1) then Sum_{i=1..k-1} -A(k-i, n) else 0 else if and(n > 1, k > 1) then Sum_{i=1..n-1} -A(n-i, k) else 0.

%C By letting the upper summation indexes "k-1" and "n-1" in the recurrence above, change place with each other one gets the number theoretic matrix A191898, and it appears that the eigenvalue norm sqrt(n) of this matrix is a lower bound for the eigenvalue norm of matrix A191898 which in turn for n>10 appears to be close to A007917, the previous prime sequence. If the eigenvalue norm of matrix A191898 also can be proven to be less than n+1, then one could say that there is always a prime gap between sqrt(n) and n+1.

%C From _Wolfdieter Lang_, Feb 32 2018: (Start)

%C The characteristic polynomial P(n, x) = Det(M_n - x*1_n), with the n X n matrix M_n defined in the name and 1_n the n dimensional unit matrix, satisfies, after expanding the last row, the recurrence: P(n, x) = -z*P(n-1, x) + (-1)^(n-1)*z^(n-2), for n >= 2, and input P(1, x) = y, where y = 1-x and z = 1+x. The solution is P(n, x) = y*(-z)^(n-1) - (n-1)*(-z)^(n-2) = (-1)^n*(1 + x)^(n-2)*(x^2 - n), for n >= 1. After picking the coefficient of x^k this becomes the formula for T(n, k) given in the formula section.

%C The Determinant of M_n is P(n, 0) = T(n, 0) = (-1)^n*n = A181983(n).

%C The eigenvalues of M_n are +1 for n = 1 and for n >= 2 they are +sqrt(n), -sqrt(n), and n-2 times -1.

%C Therefore the spectral radius (absolute value of the maximal eigenvalue) is rho_n = sqrt(n), and the spectral norm of M_n (square root of the maximal eigenvalue of (M_n)^+ M_n is also sqrt(n), for n >= 1. See the conjecture in the first comment above.

%C The square of the Frobenius norm (aka Hilbert-Schmidt norm) of M_n is max_{i,j=1..n} |M_n(i,j)|^2 = 3*n - 2 = A016777(n-1), for n >= 1.

%C The row sums are P(n, 1) = (-1)^(n-1)*(n-1)*2^(n-2) = A085750(n), for n >= 1, and for n=0 the row sum is 0. The alternating row sums are P(n, -1) = 2 for n=1, -1 for n = 2, and zero otherwise.

%C The column sequence (without leading zero) for k = 1 is (-1)^(n+1)*n*(n-2), for n >= 1, which is -A131386(n). For k = 2 it is (-1)^n*(1 - n*binomial(n-2, 2)) for n >= 2 which is (-1)^n*A110427(n-1). Other columns follow from the formula for T(n, k). (End)

%F From _Wolfdieter Lang_, Feb 02 2018: (Start)

%F T(n, k) = [x*k] P(n, x), for n >= 1, with P(n, x) = Det(M_n - x*1_n), and the matrix M_n defined in the name (1_n is the n dimensional unit matrix). T(0, 0):= 0.

%F T(n, k) = (-1)^(n+1)*n for k = 0, (-1)^(n+1)*n*(n-2) for k = 1, and (-1)^n*(binomial(n-2, k-2) - n*binomial(n-2, k)) for k >= 2, with n >= 0 and 0 <= k <= n. T(n, k) = 0 for k > n. (End)

%e The matrix for these characteristic polynomials starts:

%e {

%e {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},

%e {1, -1, 0, 0, 0, 0, 0, 0, 0, 0},

%e {1, 0, -1, 0, 0, 0, 0, 0, 0, 0},

%e {1, 0, 0, -1, 0, 0, 0, 0, 0, 0},

%e {1, 0, 0, 0, -1, 0, 0, 0, 0, 0},

%e {1, 0, 0, 0, 0, -1, 0, 0, 0, 0},

%e {1, 0, 0, 0, 0, 0, -1, 0, 0, 0},

%e {1, 0, 0, 0, 0, 0, 0, -1, 0, 0},

%e {1, 0, 0, 0, 0, 0, 0, 0, -1, 0},

%e {1, 0, 0, 0, 0, 0, 0, 0, 0, -1}

%e }

%e ----------------------------------------------------------------------

%e The table T(n, k) begins:

%e n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 ..

%e 0: 0

%e 1: 1 -1

%e 2: -2 0 1

%e 3: 3 3 -1 -1

%e 4: -4 -8 -3 2 1

%e 5; 5 15 14 2 -3 -1

%e 6: -6 -24 -35 -20 0 4 1

%e 7: 7 35 69 65 25 -3 -5 -1

%e 8: -8 -48 -119 -154 -105 -28 7 6 1

%e 9: 9 63 188 308 294 154 28 -12 -7 -1

%e 10: -10 -80 -279 -552 -672 -504 -210 -24 18 8 1

%e 11: 11 99 395 915 1350 1302 798 270 15 -25 -9 -1

%e 12: -12 -120 -539 -1430 -2475 -2904 -2310 -1188 -330 0 33 10 1

%e ... reformatted by _Wolfdieter Lang_, Feb 02 2018.

%p f:= proc(n) local M,P,lambda,k;

%p M:= Matrix(n,n, proc(i,j) if i=1 or j=1 then 1 elif i=j then -1 else 0 fi end proc);

%p P:= (-1)^n*LinearAlgebra:-CharacteristicPolynomial(M,lambda);

%p seq(coeff(P,lambda,k),k=0..n)

%p end proc:

%p f(0):= 0:

%p for n from 0 to 10 do f(n) od; # _Robert Israel_, Feb 02 2018

%t Clear[A, x, t];

%t Table[t[n_, 1] = 1;

%t t[1, k_] = 1;

%t t[n_, k_] :=

%t t[n, k] =

%t If[n < k,

%t If[And[n > 1, k > 1], Sum[-t[k - i, n], {i, 1, k - 1}], 0],

%t If[And[n > 1, k > 1], Sum[-t[n - i, k], {i, 1, n - 1}], 0]];

%t A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];

%t CoefficientList[CharacteristicPolynomial[A, x], x], {nn, 1, 10}];

%t Flatten[%]

%Y Cf. A016777, A085750 (row sums), A067998, A110427 (column k=2), -A131386 (column k=1), A181983 (Det M_n), A191898.

%K tabl,sign,easy

%O 0,4

%A _Mats Granvik_, Dec 30 2017

%E Edited by _Wolfdieter Lang_, Feb 02 2018.