Cyclic permutations and trace

The trace of a square matrix is the sum of the elements on its main diagonal.

The order in which you multiply matrices matters: in general, matrix multiplication is not commutative. But the trace of a product of matrices may or may not depend on the order of multiplication.

Specifically, trace doesn't change if you take the last matrix and move it to the front. You can apply this repeatedly the get all cyclic permutations.

If you just have two matrices, A and B, then order doesn't matter because there is only one permutation of two things, and it's a cyclic permutation. That is trace(AB) = trace(BA).

But in general only cyclic permutations leave the trace unchanged. The following Python code illustrates this.

 import numpy as np np.random.seed(1776) N = 4 A = np.random.rand(N, N) B = np.random.rand(N, N) C = np.random.rand(N, N) print( (A@B@C).trace() ) print( (B@C@A).trace() ) print( (C@A@B).trace() ) print( (C@B@A).trace() ) print( (B@A@C).trace() ) print( (A@C@B).trace() )

This shows that ABC, BCA, and CAB all have the same trace (5.793 in this example) and CBA, BAC, and ACB all have the same trace (4.851).

In this case there were only two trace values: one for the forward sequence and its rotations, and one for the reversed sequence and its rotations. With more matrices there are more possibilities.

 D = np.random.rand(N, N) print( (A@B@C@D).trace() ) print( (C@D@A@B).trace() ) print( (C@D@B@A).trace() ) print( (D@C@B@A).trace() )

Now we see that ABCD and CDBA have the same trace (12.632), because they are rotations of each other, but the other two permutations have difference traces (13.843 and 12.564).

If we're working with symmetric matrices, then reversing the order doesn't change the trace. Here's a quick proof for the product of three symmetric matrices:

trace(ABC) = trace((ABC)^T) = trace(C^T B^T A^T) = trace(CBA)

So for three symmetric matrices, the trace is the same for all permutations.

The following code shows that the order of multiplication can change the trace, even for symmetric matrices, if you have four matrices.

 A += A.T B += B.T C += C.T D += D.T print( (C@D@A@B).trace() ) print( (C@D@B@A).trace() )

The first statement prints 202.085 and the second 222.211.

Related posts

• Gershgorn disks
• Kronecker sum
• Convex function of diagonals and eigenvalues

The post Cyclic permutations and trace first appeared on John D. Cook.