2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Did you consider elementary matrices? $\endgroup$ – Daniel Jul 24 '15 at 4:19
  • $\begingroup$ If A is a square invertible matrix, then wouldn't R be the identity matrix if you chose the pivots to be equal to 1. And if so wouldn't P be equal to the inverse of A? $\endgroup$ – Tucker Jul 24 '15 at 4:23
  • $\begingroup$ @Tucker, you are correct for that particular case. $\endgroup$ – wjm Jul 24 '15 at 4:25
3
$\begingroup$

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) $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Brilliant! I also see the connection between this and Solid Snake's comment regarding elementary matrices. $\endgroup$ – wjm Jul 24 '15 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.