Elementary Row Operations - Interchange a Matrix's rows 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.
 A: 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.
A: 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.
A: 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.
