Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's consider a $2\times 2$ linear system: $$ A\bf{u} = b $$ The solution will still be the same even after we interchange the rows in $A$ and $B$. I know this to be true because algebraically, we will get the same set of equations before and after the row interchange.

However, the vectors in columns of $A$ and $B$ are different. So how can the system still have the same solution as before the row interchange?

Thank you.

share|improve this question
1  
That's the reason why one keeps track of the permutations done. To get the solution of the original system, you unscramble the solution of the pivoted system. –  J. M. Nov 26 '10 at 7:00
    
J.M., were you thinking of the effect of reordering the columns? Changing the order of the rows does not permute the entries in the solutions to the system, so there's no unscrambling to be done. –  Dan Ramras Nov 27 '10 at 7:00

3 Answers 3

up vote 3 down vote accepted

Let us consider a $2 \times 2$ example. We will then extend this higher dimensions.

Let $$A = \begin{bmatrix}A_{11} & A_{12}\\A_{21} & A_{22} \end{bmatrix}$$

$$b = \begin{bmatrix}b_1 \\b_2 \end{bmatrix}$$

So you now want to solve $Ax_1 = b$.

$x_1$ is given by $A^{-1}b$.

Now you swap the two rows of $A$ and $b$. Call them $\tilde{A}$ and $\tilde{b}$ respectively.

$$\tilde{A} = \begin{bmatrix}A_{21} & A_{22}\\A_{11} & A_{12} \end{bmatrix}$$

$$\tilde{b} = \begin{bmatrix}b_2 \\b_1 \end{bmatrix}$$

Now how do we relate $\tilde{A}$ and $A$ and similarly $\tilde{b}$ and $b$.

The relation is given by a Permutation matrix $P$.

$\tilde{A} = P A$ and $\tilde{b} = P b$.

The matrix $P$ is given by:

$$\tilde{P} = \begin{bmatrix}0 & 1\\1 & 0 \end{bmatrix}$$

Check that $\tilde{A} = P A$ and $\tilde{b} = P b$.

Now we look at solving the system $\tilde{A}x_2 = \tilde{b}$.

Substitute for $\tilde{A}$ and $\tilde{b}$ in terms of $A$ and $b$ respectively to get

$PAx_2 = Pb$.

Now the important thing to note is that $P^2 = I$.

This can be verified algebraically or by a simple argument by seeing that $P^2$ swaps and swaps again which reverts back to the original giving $I$ or the other way of looking is $P^2$ is $P$ applied to $P$ which swaps the two rows of $P$ giving back the identity matrix.

So from $P^2 = I$, we get $P^{-1} = P$.

So we have $PAx_2 = Pb$ and premultiplying by $P^{-1}$ gives $Ax_2 = b$.

So we have $Ax_1 = b$ and $Ax_2 = b$.

And if we assume $A$ is invertible this gives us a unique solution and hence we get $x_1 = x_2$.

or the other way to look at is to write $x_2 = \tilde{A}^{-1} \tilde b = (PA)^{-1}Pb = A^{-1} P^{-1} P b = A^{-1} I b = A^{-1} b$.

All you need to observe in the above step is that the matrix $P$ is invertible and hence the matrix $(PA)$ is also invertible (since $A$ is assumed to be invertible and that $(PA)^{-1} = A^{-1}P^{-1}$ and matrix multiplication is associative.

The same argument with permutation matrix holds true for a $n \times n$ system as well.

share|improve this answer

Perhaps I don't fully understand your question. So suppose you have a $2\times 2$ linear system.

$$\begin{bmatrix}a & b\\c & d \end{bmatrix}\begin{bmatrix}u_1\\ u_2\end{bmatrix}=\begin{bmatrix} e\\ f\end{bmatrix}$$

This gives you the augmented matrix $$\begin{bmatrix}a & b & e\\ c & d & f\end{bmatrix}$$

This gives the set of equations $$au_1+bu_2=e\quad\text{and}\quad cu_1+du_2=f.$$

If you interchange the rows, you get the augmented matrix $$\begin{bmatrix}c & d & f\\ a & b & e\end{bmatrix}$$

which indeed has different columns. But this gives the equations

$$cu_1+du_2=f\quad\text{and}\quad au_1+bu_2=e$$

just the other way around as before. The entries of $\textbf{u}$ haven't been switched, if that was your concern.

share|improve this answer

Rearranging the rows of $A$ and $b$ corresponds to premultiplying them with a permutation matrix $P$. It's not hard to see that the new system $PAu = Pb$ has the same solution as the original system. This holds for linear systems of all sizes, not just $2\times 2$ ones.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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