I think that if you just permute the basis elements you'll actually have to permute both the rows and columns. I'm not entirely sure about this though.
Next, if the above is true, you can cyclically shift the basis elements by one position, obtaining that all the diagonal entries are the same. Then certain off-diagonal sections are individually equal to some constants. The goal would be to show these constants are all the same. I can imagine that using different permutations you can see that all the off-diagonal entries are the same. This is not much more so far, but it might be a good start.