Noob question: Why does substituting new equation work in Gaussian elimination? Suppose I have a matrix 
$$
\left[
\begin {matrix}
1 & -2 & \;\;\;1 & \;\;\;0 \\
0  & \;\;\;1 &-4 & \;\;\;4 \\
0 &-3 &\;13 &-9 \\
\end {matrix}
\right]
$$
I can multiply the second equation by 3, which results in 
$3x_2 + -12 x_3 = 4$ . 
Then, I can add the second equation to the third, resulting in this:
$3x_2 + -12 x_3 + -3x_2 + 13x_3 = 12 + -9$, 
simplifying to $x_3 = 3$ .
According to the algorithm for solving systems of equations, I can then substitute the new equation $x_3 = 3$ as the third equation, resulting in
$$
\left[
\begin {matrix}
1 & -2 & \;\;\;1 & \;\;\;0 \\
0  & \;\;\;1 &-4 & \;\;\;4 \\
0 &0 &\;1 &\;\;\;3 \\
\end {matrix}
\right]
$$
I don't understand this why it's appropriate to substitute the new equation as the third equation. How is the new equation the same as the original third equation? I mean, adding the two equations surely results in a different equation from the original, right? Please excuse me for this question, I haven't done basic algebra in a long time.
 A: You originally have a matrix equation to solve:
$$\begin{align}
A\mathbb x=&\mathbb b\\
\left[\begin{array}{rrr}
1&-2&1\\
0&1&-4\\
0&-3&13
\end{array}\right]\mathbb x =& \left[\begin{array}{r}
0\\
4\\
-9
\end{array}\right]
\end{align}$$
Your first row operation is actually left multiplying a matrix to both sides of the equation:
$$\left[\begin{array}{rrr}
1&0&0\\
0&3&0\\
0&0&1
\end{array}\right]\left[\begin{array}{rrr}
1&-2&1\\
0&1&-4\\
0&-3&13
\end{array}\right]\mathbb x = \left[\begin{array}{rrr}
1&0&0\\
0&3&0\\
0&0&1
\end{array}\right]\left[\begin{array}{r}
0\\
4\\
-9
\end{array}\right]$$
And then, you did $R_3\rightarrow R_3+R_2$, which is equivalent to:
$$\left[\begin{array}{rrr}
1&0&0\\
0&1&0\\
0&1&1
\end{array}\right]\left[\begin{array}{rrr}
1&0&0\\
0&3&0\\
0&0&1
\end{array}\right]\left[\begin{array}{rrr}
1&-2&1\\
0&1&-4\\
0&-3&13
\end{array}\right]\mathbb x = \left[\begin{array}{rrr}
1&0&0\\
0&1&0\\
0&1&1
\end{array}\right]\left[\begin{array}{rrr}
1&0&0\\
0&3&0\\
0&0&1
\end{array}\right]\left[\begin{array}{r}
0\\
4\\
-9
\end{array}\right]$$
If you continue to formally write the back-substitution of $x_3$ in matrix form, the left hand side chain of matrix multiplication would become the identity matrix $I$ (given it is possible). Then, all those matrices you left-multiplied actually give $A^{-1}$. Then you can actually see you have converted your original equation to
$$\begin{align}
A^{-1}A\mathbb x=&A^{-1}\mathbb b\\
I\mathbb x=&A^{-1}\mathbb b\\
\mathbb x=&A^{-1}\mathbb b
\end{align}$$
thus solving the equation.
Edit
More generally, even if $A$ is not invertible or $A$ is not even a square matrix, applying Gaussian elimination converts the left hand side matrix product $\cdots P_2 P_1 A$ to reduced row echelon form, and the right hand side to $\cdots P_2P_1\mathbb b$. The matrix equation can be checked for consistency, and, if consistent, the general solution to $\mathbb x$ can be found by setting up free variables.
A: (very late answer, but I felt something more was needed here)
You have these equations:
$$x-4y=4 \qquad(1)$$
and 
$$-3x+13y=-9\qquad(2)$$
As you mentioned, combining $(1)$ and $(2)$ gives you 
$$y=3\qquad(3)$$
So now you have 3 equations. In general, it would mean that there are less solutions (each equation can be seen as a constraint, so adding a constraint only reduce the solution space). 
What then? Well, here (3) is not any random equation, it's a linear combination of (1) and (2). 
Now there are two nice properties to remember:


*

*you can ditch any equation which is a linear combination of others that you keep: such an equation does not reduce the solution space

*since (3) is a linear combination of (1) and (2) with non-null coefficients, then any of (1), (2) and (3) is a linear combination of the other two


So you created (3) as "$3\times(1) +  (2) $", then you know that (1) is a linear combination of (2) and (3), and so you can remove (1) from your system, without modifying the solution space.
Overall, the operation of "replacing an equation with a linear combination of it and any other" is valid.
A: Gaussian elimination is, at it's core, the left- or right-multiplication by some other matrices on both sides of the equation $Ax = b$. The way it's taught is just a shortcut. What you're really doing is saying
$$\begin{align*}
Ax &= b \\
P_1Ax &= P_1b \\
P_2P_1Ax &= P_2P_1b\\
&\vdots
\end{align*}
$$
