# Is there a pattern for the irreducible factors and degrees of a characteristic polynomial?

Let $$Log(n) = \sum_{i=1}^r \alpha_i \cdot e_i$$, where $$n = \prod_{i=1}^r p_i^{\alpha_i}$$ and $$p_i$$ is the $$i$$-th prime, $$\alpha_i \ge 0$$, $$e_i$$ is the $$i$$-th standard basis vector. For example $$6 = 2\cdot3$$, hence: $$Log(6) = (1,1,0,0,0,\cdots)$$ $$Log(15) = (0,1,1,0,0,\cdots)$$ $$Log(7) = (0,0,0,1,0,\cdots)$$ Consider the matrix $$A_n = (Log(1)^T,Log(2)^T,\cdots,Log(n)^T)$$. Then one can think about that $$rank(A_n) = \Pi(n)$$, where $$\Pi$$ is the prime counting function. For fun, we might compute the Smith normal form of this matrix: $$D_n = U_n A_n V_n$$ I conjecture that $$V_n = 1_n$$ and that $$D_n$$ consists of $$\Pi(n)$$ ones on the diagonal. Now the mysterious part is the irreducible factors of the characteristic polynomial of $$U_n$$.

Here is a list for $$1 \le n \le 20$$ computed with SAGEMATH:

1 x - 1
2 x^2 + 1
3 (x - 1) * (x^2 + x + 1)
4 (x - 1)^2 * (x^2 + x + 1)
5 (x - 1) * (x^4 + 1)
6 (x - 1)^2 * (x^4 + 1)
7 (x - 1) * (x^2 + 1) * (x^4 + 1)
8 (x - 1)^2 * (x^2 + 1) * (x^4 + 1)
9 (x - 1)^3 * (x^2 + 1) * (x^4 + 1)
10 (x - 1)^4 * (x^2 + 1) * (x^4 + 1)
11 (x - 1)^5 * (x^2 + 1) * (x^4 + x^3 + x^2 + x + 1)
12 (x - 1)^6 * (x^2 + 1) * (x^4 + x^3 + x^2 + x + 1)
13 (x - 1)^5 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
14 (x - 1)^6 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
15 (x - 1)^7 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
16 (x - 1)^8 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
17 (x - 1)^9 * (x^2 + 1) * (x^2 + x + 1) * (x^4 + x^3 + x^2 + x + 1)
18 (x - 1)^10 * (x^2 + 1) * (x^2 + x + 1) * (x^4 + x^3 + x^2 + x + 1)
19 (x - 1)^9 * (x^2 + x + 1) * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
20 (x - 1)^10 * (x^2 + x + 1) * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)

It occurs that the irreducible factors are cyclotomic polynomials $$p(x)$$ with $$\deg(p(x))=\phi(m)$$ for some number $$m$$. But how does one compute the numbers $$m$$, given $$n$$? I think this would give an interesting decomposition of $$n$$ in summands and products.

For example: $$13 = 5\cdot\phi(1)+2\phi(4)+1\phi(5)$$ $$5 = 1\cdot\phi(1) + 1\cdot \phi(8)$$

I have tried to search OEIS for various related sequences but without success.

Thanks for you help.

Edit: Here is some sage code, to get the matrix $$U_5,\cdots,U_{10}$$ and the corresponding matrices.

MAXN=100

def Log(a,N=MAXN):
return vector([valuation(a,p) for p in primes(N)])

def Exp(v,N=MAXN):
P = list(primes(N))
return prod([P[i]**v[i] for i in range(len(P))])

def AA(n,N=MAXN):
return matrix([Log(n,N=N) for n in range(1,n+1)],ring=QQ)

def UU(n,N=MAXN):
D,U,V = (AA(n,N=N)).smith_form()
return U

[ 0  1  0  0  0]
[ 0  0  1  0  0]
[ 0  0  0  0  1]
[ 0 -2  0  1  0]
[-1  0  0  0  0]
[ 0  1  0  0  0  0]
[ 0  0  1  0  0  0]
[ 0  0  0  0  1  0]
[ 0 -2  0  1  0  0]
[-1  0  0  0  0  0]
[ 0 -1 -1  0  0  1]
[ 0  1  0  0  0  0  0]
[ 0  0  1  0  0  0  0]
[ 0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  1]
[-1  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0]
[ 0  2  0 -1  0  0  0]
[ 0  1  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0]
[ 0  0  0  0  0  0  1  0]
[-1  0  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0  0]
[ 0  2  0 -1  0  0  0  0]
[ 0 -3  0  0  0  0  0  1]
[ 0  1  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0]
[-1  0  0  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0  0  0]
[ 0  2  0 -1  0  0  0  0  0]
[ 0 -3  0  0  0  0  0  1  0]
[ 0  0 -2  0  0  0  0  0  1]
[ 0  1  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0]
[-1  0  0  0  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0  0  0  0]
[ 0  2  0 -1  0  0  0  0  0  0]
[ 0 -3  0  0  0  0  0  1  0  0]
[ 0  0 -2  0  0  0  0  0  1  0]
[ 0 -1  0  0 -1  0  0  0  0  1]

Update: Here are the matrices and corresponding characteristic polynomials for $$n=23,29,31$$:

[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1]
[ 0 -1  0  0 -1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2 -1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  1  1  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0 -1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0 -1  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0]
[ 0 -4  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0 -2  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  3  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0]
[ 0  0 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0 -1  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  1  0]
[ 0  0  2  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
23 (x - 1)^11 * (x^2 + x + 1) * (x^2 + 1)^3 * (x^4 + x^3 + x^2 + x + 1)
[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1]
[ 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2 -1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  1  1  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0 -1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0 -1  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -4  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  3  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0  0  2  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -3 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  0  0  0 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0]
[ 0  0 -3  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0 -2  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0]
[ 0  1  0  0  1  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
29 (x - 1)^15 * (x^2 + x + 1) * (x^2 + 1)^4 * (x^4 + x^3 + x^2 + x + 1)
[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1]
[ 0 -2 -1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  1  1  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0 -1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0 -1  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -4  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  3  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0  2  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -3 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0  0  0  0 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  0 -3  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]
[ 0 -2  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0]
[ 0  1  0  0  1  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -1  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0]
[-1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
31 (x - 1)^15 * (x^2 + x + 1) * (x^2 + 1)^5 * (x^4 - x^2 + 1)

Update to the answer given by Denis Serre: I can not see how, $$D_4 = U_1 \cdot A_4$$ or $$D_4 = U_2 \cdot A_4$$:

sage: AA(4)
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
sage: U1
[0 1 0 0]
[0 0 1 0]
[1 0 0 0]
[0 0 0 1]
sage: U2
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 0 0 0]
sage: U1*AA(4)
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
sage: U2*AA(4)
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
sage: UU(4)*AA(4)
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
• Just doing column reduction allows you to reduce A_n to a matrix of all ones, and then you use an appropriate permutation, so you should (in principle) be able to write down U_n explicitly, and maybe even represent it as a convolution. I am not surprised that the associated polynomial is a product of cyclotomics; I am surprised that 8 appears in the representation for five through ten. It might help for you to list U_5 through U_10 to show us why. Gerhard "Sometimes Having Enough Examples Helps" Paseman, 2019.03.18. – Gerhard Paseman Mar 18 at 16:15
• @GerhardPaseman: Thanks for your comment. I updated the question with examples. – orgesleka Mar 18 at 16:43
• Can you give some more entries in your list, say $n=23,29,31$? – Richard Stanley Mar 18 at 21:01
• I don't understand why $Log(15)\neq(0, 1, 1,0, \cdots)$. – Sylvain JULIEN Mar 18 at 23:21
• you are right. sorry for the stupid mistake. i will correct that – orgesleka Mar 19 at 5:14

I made hand calculations for $$n\le4$$. It turns out that even with $$V_n=1_n$$, the factor $$U_n$$ is not unique. In other words, the factorisation problem is underdetermined. This is due to the fact that the few last columns of $$A_n$$ vanish. For instance, if $$n=3$$, the general $$U_3$$ is $$\begin{pmatrix} a & 1 & 0 \\ b & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}.$$ Therefore the characteristic polynomial can be any of the polynomials $$X^3-aX^2-bX-1$$. You may prefer to select the "simplest" matrix $$U_n$$, which gives you here the polynomial $$X^3-1$$, but how will you proceed for higher values of $$n$$ ?
Edit (after miscalculation in my original answer.) The case $$n=4$$ yields even more freedom. You may choose the matrices $$U_4=\begin{pmatrix} a & 1 & 0 & 0 \\ b & 0 & 1 & 0 \\ c & -2 & 0 & 1 \\ -1 & 0 & 0 & 0 \end{pmatrix}$$ and even this list is incomplete. What is the simplest among them ? At least the second and third columns are mandatory. The corresponding characteristic polynomial $$X^4-aX^3+(2-b)X^2-(2a+c)X+1$$ can be any polynomial $$X^4+\cdots+1$$ with integer coefficients.