Why is the spectrum of this matrix product invariant with respect to order of the multiplicants? I've been chewing on the following problem for some time and I just don't have any more ideas how to tackle it. I have matrices $A_1,...,A_k \in \mathbb R^{n\times n}$ and I'm observing that the spectrum of the product is the same whatever order of multiplication I choose, that is, for an arbitrary permutation $\pi$ on ${1,...,k}$, I have
$$\sigma(A_1\cdot ...\cdot A_k) = \sigma(A_{\pi(1)}\cdot ...\cdot A_{\pi(k)}).$$
Of course, the form of the matrices is important since the above equality doesn't hold in general. All are of the form:
$$ A_j = \left[
         \array{0 & 1 & 0 & \cdots & 0 \\
                0 & \ddots & \ddots & \ddots & 0 \\
                0 & \cdots & 0 & 1 & 0 \\
                0 & \cdots & \cdots & 0 & 1 \\
                a_j & \cdots & \cdots & \cdots & a_j }
         \right],$$
with possibly all different $a_j \in\mathbb{R},\ j=1,...,k$. I find this quite peculiar and I don't see the reason, although all tested examples confirm the statement... I would be very curious and grateful if someone has an idea how to solve that...
Thanks ahead for your comments! 
 A: It seems that the claim is false when $n=2$ and $k=4$, because
$${\rm Tr} (A_1A_2A_3A_4)=a_1a_3+a_2a_4+\sigma_3({\bf a})+\sigma_4({\bf a})$$
is not symmetric in ${\bf a}=(a_1,a_2,a_3,a_4)$.
Edit: just let me add a classical result. Let $C_1,\ldots,C_r$ be the companion matrices of unitary polynomials $P_1,\ldots,P_r$ of same degree $n$. Suppose that $\lambda$ is a common root to all the $P_j's$. Then $\lambda^r$ is an eigenvalue of the product $C_1\cdots C_r$.
A: As suggested in Neil Strickland's comment, the claim seems to hold indeed for $n=k$. Inspection shows that the characteristic polynomial of the product can be written simply as $$\det(x-A_1\cdot ...\cdot A_n)=x^n-\sum_{i=1}^n (x-1)^{i-1}  x^{n-i}s_i,$$ where $s_i$ is the $i$-th symmetric function of $a_1,…,a_n$. The proof of this should not be hard using some kind of induction.
E.g. for $n=4$, in expanded form it is $$x^4-(s_1+s_2+s_3+s_4)x^3+(s_2+2s_3+3s_4)x^2-(s_3+3s_4)x+s_4.$$
A: Write $diag(\lambda_1,\dots,\lambda_n)$ for the diagonal matrix with entries $\lambda_1,\dots,\lambda_n$.
The matrix in question as $J(a_j)=diag(1,\dots,1,a_j)P$ for a fixed matrix $P$.
For a given matrix $A$, each coefficient of the characteristic polynomial $\det(x-diag(1,\dots,a)A)$ is a polynomial in $a$ of degree $\le 1$.
Now each coefficient of the characteristic polynomial
$$
\det(x-J(a_1)\cdots J(a_k))
$$
is a polynomial in the $a_j$ which is invariant under cyclic permutations and is of degree $\le 1$ in each variable $a_j$.
Each such polynomial must be invariant under the whole permutation group.
