A combinatorial problem from linear algebra

Abstract:Consider the trace of a product of matrices in linear algebra. Everyone knows that the trace satisfies the formula tr AB = tr BA. It is also easy to show that, for matrices of arbitrary dimension, this is essentially the *only* such formula that holds (i.e., if W and W' are words in the alphabet A,B,C,..., then the formula tr W = tr W' holds for all matrices A,B,C,... if and only if W is a cyclic permutation of W). Surprisingly, however, there can be other such formulas that hold in special dimensions. Here is an example found by Bob Pare: if A and B are any 2x2-matrices, then tr AABBAB = tr AABABB. It is easy to see that if some such property holds at dimension n, then it holds at all smaller dimensions as well. It is not presently known (to me) whether there are any such special trace formulas in dimension 3. It is also not known whether Pare's formula is "essentially" the only such formula in dimension 2. It is easy to see that formulas of the above nature are independent of the field (or ring) of scalars: any such formula that holds over the real numbers also holds over any ring. In fact, one can take the scalars to be variables or "colors". Therefore, what appears to be a problem in linear algebra reduces to a combinatorial problem. It appears to be quite hard, and has a similar flavor to certain problems in graph theory.