Assuming I have a symmetric matrix $A \in \mathbb{R}^{N \times N}$ with relative EVD $A=U \Lambda U^\top$, what does a permutation matrix $P \in \mathbb{R}^{N \times N}$ change when applied to the matrix $A$, in terms of $U$ and $\Lambda$? In other words, I would like to analyze $\hat{A}=PAP^\top$.
My thoughts are the following: first of all, $\hat{A}$ contains the same information of $A$, just rows and columns have been reordered. In terms of EVD, now we have
$$ PU \Lambda U^\top P^\top= \hat{U}\Lambda \hat{U}^\top$$ where $\hat{U}$ is just a permuted version of the eigenvector matrix $U$. However, the matrix of eigenvalues $\Lambda$ did not change. Is it correct that a permutation assignes to each eigenvector $u_i$ another eigenvalue $\lambda_j$ with $i \neq j$?
A last comment: how can a simple permutation of the original matrix, lead to an eigenvalue decomposition in which each rank-one matrix $u_i u_i^\top$ has now a different weight w.r.t before if the "content" of the matrix is the same?
Notice that $PP^T = I$, is orthogonal. So $\hat A = P A P^{T} = P A P^{-1}$, is a similarity transformation, as such, it is well known to preserve the eigenvalues.
Also you are right in saying that $\hat A = P U \Lambda U^T P^T$, and since both $P$ and $U$ are orthogonal, $PU$ is orthogonal, thus this is an eigen decomposition. In other words the matrix of vectors of $\hat A$ is $PU$.
But it is not correct to say that the transformation assigns different eigenvalues to the same eigenvector.
Take the eigen equation
$Av = \lambda v$
This can be written as $P^T \hat A P = \lambda v$, thus $\hat A P v = P \lambda v = \lambda P v$. What this means is that the eigenvector of $\hat A$ associated with $\lambda_i$ is $P u_i$, a vector whose entries are a permutation of the entries of the eigenvector of $A$, $u_i$, associated wihth $\lambda_i$.