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$ ? The case $n=4$ raises already a difficulty: you can choose two "simplest" matrices, namely $$\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\qquad\hbox{or}\qquad\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}.$$ But then there is no prefered choice between the polynomials $$(X-1)^2(X^2+X+1)\qquad\hbox{or}\qquad (X-1)(X+1)(X^2+1).$$ I must acknowledge that still, these polynomials are products of cyclotomic factors.

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.