First, a definition to make my question easier to state. Let $X$ be an $n\times n$ matrix. Then, a number $z\in\mathbb{C}$ is a permuted trace of $X$ if there exists permutations $\alpha,\beta\in S_{n}$ such that
$$z = \sum_{i=1}^{N}X_{\alpha(i)\beta(i)}.$$
In other words, $z$ is a sum of matrix elements of $X$, such that each column and each row is represented exactly once in the terms of the sum. For example, if $X$ is $3\times 3$, examples of permuted traces include $X_{11} + X_{22} + X_{33}$ (the regular trace) and $X_{23} + X_{12} + X_{31}$.
Now, my question. Let $\mathcal{O} : V \rightarrow V$ be a normal operator on a finite dimensional vector space $V$ of dimension $N$. The trace of $\mathcal{O}$ can be written as the sum of the eigenvalues:
$$\text{tr}(\mathcal{O}) = \sum_{i=1}^{N}\lambda_i.$$
Let $v_1,\ldots,v_N$, and $w_1,\ldots,w_N$ be ordered orthonormal bases for $V$, and let $\sigma\in S_N$ be a permutation. Endowing the domain $V$ with the $\{v_i\}$ basis and the codomain $V$ with the $\{w_i\}$ basis, $\mathcal{O}$ admits a matrix representation $A\in M_N(\mathbb{C})$, where $A_{ij} = \langle w_i, Av_j\rangle$, and the trace can be written as the sum of the diagonal elements:
$$\text{tr}(\mathcal{O}) = \sum_{i=1}^{N} A_{ii} = \sum_{i=1}^{N} \langle w_i, \mathcal{O}v_i\rangle.$$
However, with $\sigma$, we could instead endow the domain $V$ with the $\{v_i\}$ basis, and the codomain $V$ with the permuted orthonormal basis $\{w_{\sigma(i)}\}$. In this basis, $\mathcal{O}$ admits a different matrix decomposition $B\in M_{N}(\mathbb{C})$, and now the trace is given by
$$\text{tr}(\mathcal{O}) = \sum_{i=1}^{N} B_{ii} = \sum_{i=1}^{N} \langle w_{\sigma(i)}, \mathcal{O}v_i\rangle = \sum_{i=1}^{N} A_{\sigma(i)i}.$$
This implies that
$$\sum_{i=1}^{N} A_{ii} = \text{tr}(\mathcal{O}) = \sum_{i=1}^{N} A_{\sigma(i)i}.$$
Stretching this argument further, one can make the claim that for all $\alpha,\beta \in S_n$,
$$\sum_{i=1}^{N} A_{\alpha(i)\beta(i)} = \sum_{i=1}^{N} A_{ii},$$
or in other words, that all of the permuted traces of the normal matrix $A$ are equal, and I showed this by representing the operator in a basis in which the permuted trace becomes a regular trace, and using the invariance of the trace under basis changes. This is clearly not true; for example, if $A$ is diagonal with non-zero trace, there exists permuted traces which equal $0$. I'm struggling however to identify the flaw in my logic. Could someone help me out?
Best Answer
The usual proof of the invariance of the trace under a change of basis of an operator $V \to V$ (and the relation to the sum of eigenvalues) assumes that you're using the same basis for $V$ in the domain and the codomain to compute the matrix. In other words, when you simultaneously change the same basis that you've used for both domain and codomain at the same time, the box of numbers you get as the representation will change, but the effect is to turn a box of numbers $A$ into something of the form $S^{-1} AS$ which will still have the same trace.
If you change a basis in only the codomain and not the domain or vice versa your box of numbers changes from $A$ to $S^{-1} A T$ where $T$ is no longer necessarily $S$. There's no reason for this type of operation on boxes of numbers to leave the trace alone.
As a silly example consider e.g. the identity operator on $\mathbb{C}$ with $e_1 = 1$ regarded as the basis of $\mathbb{C}$ when it's the domain, and $\frac{1}{2} e_1$ as the basis of $\mathbb{C}$ regarded as the codomain. The box of numbers you get here is a $1 \times 1$ matrix with a $2$ in it, although the box you would get with the same basis on both domain and codomain would have trace $1$.
For slightly more along the lines of what you were thinking of, consider maybe $V = \mathbb{C}^2$, with $\{e_1 = (1,0), e_2 = (0,1)\}$ as a basis for $V$ when it's the domain and $\{\frac{1}{2} e_1, \frac{1}{2} e_2\}$ on the codomain. Or as you already seem to have noted, the example where you take $\{e_1, e_2\}$ on the domain but $\{e_2, e_1\}$ on the codomain. These new boxes of numbers transform in a way that doesn't guarantee they will have the same trace.