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?
Best Answer
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) $$