Permute columns by pre-multiplying and rows by post-multiplying? I was looking at Gilbert Strang's lectures on Linear Algebra and noticed that in lecture 2, Elimination with Matrices, around the 40nth minute he mentions that you can use the permutation matrix, 
$$P=
\begin{bmatrix}
    0       & 1 \\
    1       & 0 
\end{bmatrix}
$$
so that $AP$ is a permutation of $A$'s columns and $PA$ is a permutation of $A$'s rows.
I was wondering if there exists a matrix $P'$ such that $P'A$ is a permutation of $A$'s columns and $AP'$ is a permutation of $A$'s rows.


*

*How to prove there is no $P'$ such that $P'A=AP$ and $AP'=PA$ for all
$n\times n$ matrices?

*For which matrices $A$ there is such a $P'$?



Tried the $2\times 2$ case
$L$ pre-multiplies $A$ and permutes its columns,
$$
\begin{bmatrix}
x_1       & x_2 \\
x_3       & x_4 
\end{bmatrix}
\begin{bmatrix}
a       & b \\
c       & d 
\end{bmatrix}=\begin{bmatrix}
b       & a \\
d       & c 
\end{bmatrix} \Rightarrow
\begin{bmatrix}
x_1       & x_2 \\
x_3       & x_4 
\end{bmatrix}=\frac{1}{ad-bc}\begin{bmatrix}
bd-ac       & a^2-b^2 \\
d^2-c^2       & ac-bd
\end{bmatrix}=L
$$
$R$ post-multiplies $A$ and permutes its rows,
$$
\begin{bmatrix}
a       & b \\
c       & d 
\end{bmatrix}
\begin{bmatrix}
x_1       & x_2 \\
x_3       & x_4 
\end{bmatrix}=
\begin{bmatrix}
c       & d \\
a       & b 
\end{bmatrix} \Rightarrow
\begin{bmatrix}
x_1       & x_2 \\
x_3       & x_4 
\end{bmatrix}=\frac{1}{ad-bc}\begin{bmatrix}
cd-ab       & d^2-b^2 \\
a^2-c^2       & ab-cd
\end{bmatrix}=R
$$


*

*$L\neq R$ in the general case

*$det(A)\neq 0$ for $R$ and $L$ to exist 

*if $det(A)\neq 0$ and $a=d=0$, then $P'=L=R$

Additional notes
I feel I have to clarify further. I was looking for a matrix $P'$ that behaves just like $P$ but from the opposite side, meaning $P'$ permutes columns when pre-multiplying $A$ and rows when post-multiplying $A$.

If there is an ($n\times n$) matrix $P’$ such that $P'A=AP$ and $AP'=PA$ then $PA^2=AP’A=A^2P$. The latter holds if $A^2$ is a linear combination of powers of $P$. Moreover, by equivalences (I) $\Leftrightarrow$ (IV) and (I) $\Leftrightarrow$(V)  of Theorem from Will Jagy’s answer, the set of matrices commuting with $P$ coincides with the set of linear combinations of powers of $P$ iff the permutation represented by $P$ is a cycle. Conversely, if $PA^2=A^2P$ and $\det A\ne 0$ we have $P'A=AP$ and $AP'=PA$ for $P’=APA^{-1}$.
