We know that if $A$ is a matrix with rows $A_1, ..., A_n$, then $\sigma(A)$ is a matrix with rows $A_{\sigma(1)}, ..., A_{\sigma(n)}$.
Actually, one can show that $\sigma(A) = \sigma(I)A$, where $I$ is the identity matrix. So, it seems that the answer to my question is negative, but I do not know why I feel that the answer should be yes.
We know that $A$ and $B$ are similar when there is an invertible matrix $P$ such that $A = PBP^{-1}$.
Any hint?
Let $A=I$, and let $\sigma$ be any permutation other than the identity matrix.
Then $\sigma(A)=\sigma(I)\ne I$, hence $\sigma(A)$ is not similar to $A$ (since the only matrix similar to $I$ is $I$ itself).