Can you completely permute the elements of a matrix by applying permutation matrices? Suppose I have a $n\times n$ matrix $A$. Can I, by using only pre- and post-multiplication by permutation matrices, permute all the elements of $A$? That is, there should be no binding conditions, like $a_{11}$ will always be to the left of $a_{n1}$, etc. This seems to be intuitively obvious. What I think is that I can write the matrix as an $n^2$-dimensional vector, then I can permute all entries by multiplying by a suitable permutation matrix, and then re-form a matrix with the permuted vector.

It is not generally possible to do so.

For a concrete example, we know that there can exist no permutation matrices $P,Q$ such that $$ P\pmatrix{1&2\\\2&1}Q = \pmatrix{2&1\\\2&1} $$ If such a $P$ and $Q$ existed, then both matrices would necessarily have the same rank.