Does changing the order of rows and columns (in the same way) of a block diagonal matrix change its eigenvalues?

Question

If we speak of any block diagonal matrix, simply switching its rows, the answer is generally yes. Since I can give an example: just take $I$ the $2 \times 2$ identity matrix (eigenvalues 1 and 1) and switch its rows (eigenvalues 1 and -1).

But I'm switching rows and columns in the same way. See this matrix $Z$ which is usually formed by one-hot encoding of a categorical feature (I'm using R here):

Z <- model.matrix(~0 + rep(letters[1:3], times = 1:3))
colnames(Z) <- letters[1:3]
Z

  a b c
1 1 0 0
2 0 1 0
3 0 1 0
4 0 0 1
5 0 0 1
6 0 0 1

Its covariance matrix is block-diagonal:

Z %*% t(Z)

  1 2 3 4 5 6
1 1 0 0 0 0 0
2 0 1 1 0 0 0
3 0 1 1 0 0 0
4 0 0 0 1 1 1
5 0 0 0 1 1 1
6 0 0 0 1 1 1

Its eigenvalues (the eigenvalues of the blocks, which should be their dimensions $n_j$ and zeros - one can prove why):

round(eigen(Z %*% t(Z))$values, 2)

[1] 3 2 1 0 0 0

If I change the order of $Z$ (or equivalently both rows and columns of $ZZ'$), matrix is no longer block-diagonal:

ord <- c(3,4,6,1,5,2)

Z[ord,] %*% t(Z[ord,])

  3 4 6 1 5 2
3 1 0 0 0 0 1
4 0 1 1 0 1 0
6 0 1 1 0 1 0
1 0 0 0 1 0 0
5 0 1 1 0 1 0
2 1 0 0 0 0 1

And we do get the same eigenvalues:

round(eigen(Z[ord,] %*% t(Z[ord,]))$values, 2)

[1] 3 2 1 0 0 0

This isn't a coincidence obviously, can anyone help to prove why this should always be the case for such matrices?

---

Update: as mentioned below the key is not the block-diagonality of the matrix but its symmetry. This would also work:

A <- matrix(rnorm(6 * 3), nrow = 6)
round(eigen(A %*% t(A))$values, 2)
ord <- c(3,4,6,1,5,2)
round(eigen(A[ord,] %*% t(A[ord,]))$values, 2)

Answer 1

In general, if $A$ is a square matrix and $A'$ is the same matrix just with rows and columns permutated by the same permutation $\sigma \in S_n$, then there is an orthogonal matrix $P_{\sigma}$ such that: $$A'=P_{\sigma}AP_{\sigma}^t,$$ where $^t$ is the transpose operator. Since $P_{\sigma}$ is orthogonal $P^t_{\sigma}=P^{-1}_{\sigma}$. The characteristic polynomial of $A'$ is: $$p_{A'}(\lambda)=\det(A'-\lambda I)=\det(P_{\sigma}(A-\lambda I)P_{\sigma}^{-1})=\det(A-\lambda I)=p_A(\lambda)$$ So $A$ and $A'$ have the same eigenvalues (and the same characteristic polynomial).

I can go further into the details, if you ask.