<s>[INST] Matrix Equation: Reduced Row Echelon Form Given a matrix $A$ and its reduced row echelon form $R$, how can one find an invertible matrix $P$ such that $PA=R$?
I was given a $4\times4$ matrix $A$, I found $R$, and I tried to find $P$ by inspection. Since it was too difficult, I tried finding $P^{-1}$ by inspection because $A=P^{-1}R$ and succeeded (the greater number of zeros helps tremendously).
However, is there a more reliable method?
 [/INST] A matrix can be reduced with some sequence of three elementary row operations: swapping rows, multiplying a row by a constant, and adding one row to another. Luckily for us, each of these operations is linear, so each can be represented as a matrix multiplication. Then we just have to chain all of those matrix multiplications together.
Here's an example. Say we want to reduce the following matrix:
$$
A=
\left(\begin{array}{ccc}
0 & 1 & 5 \\
1 & 0 & 3 \\
3 & 0 & 9 \\
\end{array}\right)
$$
There are many ways we could get to the reduced row echelon form, but let's start by dividing the third row by three.
$$
P_1A =
\left( \begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & \frac{1}{3}
\end{array} \right)
\left(\begin{array}{ccc}
0 & 1 & 5 \\
1 & 0 & 3 \\
3 & 0 & 9
\end{array}\right)
=
\left(\begin{array}{ccc}
0 & 1 & 5 \\
1 & 0 & 3 \\
1 & 0 & 3
\end{array}\right)
$$
Then let's subtract the second row from the third.
$$
P_2(P_1A)=
\left( \begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1 & 1
\end{array} \right)
\left(\begin{array}{ccc}
0 & 1 & 5 \\
1 & 0 & 3 \\
1 & 0 & 3
\end{array}\right)
=
\left(\begin{array}{ccc}
0 & 1 & 5 \\
1 & 0 & 3 \\
0 & 0 & 0
\end{array}\right)
$$
Finally, let's swap the first two rows.
$$
P_3(P_2P_1A)=
\left( \begin{array}{ccc}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{array} \right)
\left(\begin{array}{ccc}
0 & 1 & 5 \\
1 & 0 & 3 \\
0 & 0 & 0
\end{array}\right)
=
\left(\begin{array}{ccc}
1 & 0 & 3 \\
0 & 1 & 5 \\
0 & 0 & 0
\end{array}\right)
$$
Great, we got to the row echelon form using three elementary operations. Notice that now we can find our permutation matrix by composing these operation matrices.
$$
P=P_3P_2P_1=
\left( \begin{array}{ccc}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{array} \right)
\left( \begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1 & 1
\end{array} \right)
\left( \begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & \frac{1}{3}
\end{array} \right)
=
\left( \begin{array}{ccc}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & -1 & \frac{1}{3}
\end{array} \right)
$$
</s>