# Questions on trace invariance of product of square matrices under cyclic permutations

I'm thinking about why the trace of a product of square matrices is unchanged after permuting those matrices in specific ways. I have four questions:

# 1.) What is a cyclic permutation?

I hear that one such way of permuting these matrices that leaves the trace unchanged is to perform a cyclic permutation. What is the definition of a cyclic permutation in this context? I find many different definitions across different sites (Proof Wiki, Wikipedia, and this site, for instance / at least as far as I can tell they're different). For now, I'm going to quote Wikipedia, since I found that to be the most understandable definition:

A permutation is called a cyclic permutation if and only if it consists of a single nontrivial cycle (a cycle of length > 1).

Example:

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 2 & 7 & 6 & 5 & 8 & 1 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 4 & 6 & 8 & 3 & 7 & 2 & 5 \\ 4 & 6 & 8 & 3 & 7 & 1 & 2 & 5 \end{pmatrix} = (146837)(2)(5)$

Some authors restrict the definition to only those permutations which have precisely one cycle (that is, no fixed points allowed).

Example:

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 5 & 7 & 6 & 8 & 2 & 1 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 4 & 6 & 2 & 5 & 8 & 3 & 7 \\ 4 & 6 & 2 & 5 & 8 & 3 & 7 & 1 \end{pmatrix} = (14625837)$

However, back on the trace page, Wikipedia says:

Note that arbitrary permutations are not allowed: in general,

$\text{tr}(ABC) \neq \text{tr}(ACB)$

Since this is in fact the cyclic permutation (BC)(A), I take it that the restricted definition is the one we are going to use. Is this the correct definition?

(Note: For the rest of the post, I'm going to denote all permutations by the notation \begin{pmatrix} A & B & C & ... \\ X & Y & Z & ... \end{pmatrix}, where $A \to X$, $B \to Y$, $C \to Z$, etc.)

# 2.) How do you prove the trace is invariant to cyclic permutations?

I tried to prove a very simple case to myself: $\text{tr}(ABC) = \text{tr}(CAB)$, using Einstein Summation Notation:

$\text{tr} \left ( ABC \right ) = \text{tr} \left ( CAB \right ) \\ \text{tr} \left ( A_{ij} B_{jk} C_{kl} \right ) = \text{tr} \left ( C_{ij} A_{jk} B_{kl} \right ) \\ A_{ij} B_{jk} C_{ki} = C_{ij} A_{jk} B_{ki} \\ A_{ij} B_{jk} C_{ki} = A_{jk} B_{ki} C_{ij}$

Where these two expressions are obviously identical if we replace the dummy indices $(i, j, k)$ with $(j, k, i)$, respectively. I can see how we would show that $\text{tr} \left ( A^{0} A^{1} .. A^{n - 1} A^{n} \right ) = \text{tr} \left ( A^{1} ... A^{n - 1} A^{n} A^{0} \right ) = \text{tr} \left ( A^{n} A^{0} A^{1} ... A^{n - 1} \right )$, where the $A^{i}$ are arbitrary matrices (square and of the same size, of course) with this summation notation method. However, this is not a fully general cyclic permutation (at least not under the definition I'm assuming above). How do we show this in the general case?

# 3.) What is the broadest class of permutations that have this property of trace invariance?

Under the above definition of a cyclic permutation, it is easy to come up with an example of, for instance, composing two cyclic permutations such that the net permutation is not cyclic. For instance, the cyclic permutation:

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 1 & 2 \end{pmatrix}$

which is more explicitly cyclic when arranged as:

$\begin{pmatrix} 1 & 3 & 5 & 2 & 4 \\ 3 & 5 & 2 & 4 & 1 \end{pmatrix}$

combined with the cyclic permutation:

$\begin{pmatrix} 3 & 4 & 5 & 1 & 2 \\ 2 & 1 & 3 & 5 & 4 \end{pmatrix}$

which is more explicitly cyclic when arranged as:

$\begin{pmatrix} 3 & 2 & 4 & 1 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{pmatrix}$

gives the non-cyclic permutation:

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 3 & 5 & 4 \end{pmatrix}$

which is explicitly non-cyclic when arranged as (12)(3)(45). However, if the trace of the product does not change either in the first permutation or in the second, the trace will be invariant under this net permutation, too. (I'll call this a multicyclic permutation. I don't know if that's standard terminology, but that's what I'm going to use). So, trace is invariant under multicyclic permutations as well as the subset of cyclic ones. Is there some larger category of permutations for which the trace is invariant? What's the largest category?

# 4.) Are there other functions of a matrix that are invariant to cyclic permutations?

I know the determinant is one other (well, it's invariant to permutations of the matrices full stop, so of course it will be invariant to cyclic permutations, which is a subset). I was specifically thinking: what about the symmetric sums of the eigenvalues? I know Trace is the sum of eigenvalues while determinant is the product of eigenvalues. What about, say, $\sum_{i = 1}^{N} \left [ \sum_{j = i + 1}^{N} \left [ \lambda_{i} \lambda_{j} \right ] \right ]$? If the, say, symmetric sums of eigenvalues are invariant under cyclic permutations, how would you prove it?

1) http://mathworld.wolfram.com/CyclicPermutation.html has a different definition of cyclic permutation, which is more approproate for the trace of matrices.

2) with summation convention and the substitutions $k\to i'$, $i\to j'$, $j \to k'$ (cyclic permutation of letters!) $$tr(ABC) = a_{ij}b_{jk}c_{ki} = c_{ki} a_{ij}b_{jk} = c_{i'j'} a_{j'k'}b_{k'i'} = tr(CAB)$$

3) Only permutations that map $i$ to $i+j$ (respectively $i+j-n$ if $i+j>n$) leave the trace invariant.

4) A linear mapping $f$ from $K^{n,n}$ to $K$ that satisfies $f(AB)=f(BA)$ is a multiple of the trace, see https://en.wikipedia.org/wiki/Trace_(linear_algebra)#Other_properties

$\newcommand{\brk}{\left(#1\right)}$ $\newcommand{\tr}{\operatorname{tr}}$

Actually, the cyclic invriance of the trace follows directly from it's "switching invariance":

$\tr(AB)=\tr(BA) \Rightarrow$

$\tr(XYZ) = \tr\brk{\brk{XY}Z}= \tr\brk{Z\brk{XY}}=\tr\brk{ZXY}$ and clearly the same method works for any finite number of matrices.