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.

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.
