I need to prove that in general case (for every possible combination of square matrices) trace of the product of said matrices stays the same after some permutation iff that permutation is cyclic.
I can prove it one way: $\text{tr}(A_1A_2 \ldots A_{n-1}A_n) = \text{tr}(A_nA_1A_2 \ldots A_{n-1})$, but I'm having problems with proving the other part: "if the trace didn't change, then the permutation was cyclic".
If someone could at least point me in the right direction, I would be very grateful.
It looks like you're seeking to show that, for every non-cyclic permutation $\pi$ that there exists $A_1,A_2,\ldots,A_n$ so that $$\operatorname{tr}(A_1A_2\ldots A_n)\neq \operatorname{tr}(A_{\pi(1)}A_{\pi(2)}\ldots A_{\pi(n)}).$$ Now, consider that a permutation is cyclic if and only if $\pi(x+1)=\pi(x)+1$ (taken mod $n$, of course). In particular, we may assume there is some $x$ such that $\pi^{-1}(x+1)\neq \pi^{-1}(x)+1$. Let $y=\pi(\pi^{-1}(x)+1)$. If we cycle the left-hand expression to put $A_x$ at the start, we get the equivalent (where we consider $A_{n+1}$ to refer to $A_1$ and so on) $$\operatorname{tr}(A_xA_{x+1}\ldots A_y \ldots A_{x+n})$$ then, setting $A_x = M_1$ and $A_{x+1}=M_2$ and $A_{y}=M_3$ and the rest to the identity yields $$\operatorname{tr}(M_1M_2M_3)$$ on the left. On the right hand side, we can cycle until $A_{x}$ is the first entry again $$\operatorname{tr}(A_xA_{y}\ldots A_{x+1}\ldots A_{\pi(\pi^{-1}(x)+n)})$$ which, with the extraneous entries set to the identity as before yields $$\operatorname{tr}(M_1M_3M_2)$$ meaning all you need to do is supply an example where $$\operatorname{tr}(M_1M_2M_3)\neq \operatorname{tr}(M_1M_3M_2)$$ to prove the claim. Put intuitively, the trick here is to, for any non-cyclic permutation, find three elements that are put out of order by the permutation.