Prove Legality of Row Operations I've been working on a formal proof of the legality of row operations to solve a system of linear equations. Let us consider an arbitrary system of linear equations $A\vec{x} = \vec{b}$ where $A$ is $m \times n$ and $\vec{b}$ has $m$ coordinates. I want to prove that I will get the same set of solution vectors if I reduce $A$ to $A'$ using row operations. I can see how this works in a very straightforward way for scalar multiplication:
$$A\vec{x} = \vec{b} \implies \sum_{i=1,...,n} a_{j,i}x_i = b_i$$
for $j = 1,...,m.$ If we multiplied the row  $r \in [m]$ by scalar $k$ we see that
$$\sum_{i=1,...,n} ma_{r,i} x_i = mb_r.$$
If $A'$ is constructed in this manner, we set row vector $\vec{a'}_r^T = m\vec{a}_{r}^T$ and $\vec{b'}_r = mb_r.$ However, I am having issues with figuring out what to do with the other rows of $A'$. Can I simply set them to the rows $j \in \{1, ... , m\}, j \neq r$? Also, is my argument accurate for all scalars? Plus, I am looking for some hints on how to prove this for row addition.
 A: Geometric interpretation
Each row of the system
$$
A x = b \quad (*)
$$ 
is the equation of an affine hyperplane $H_i$:
$$
H_i = \{ x \mid \alpha_i^T x = b_i \} \quad (i \in \{ 1, \ldots, m \} )
$$
where $\alpha_i$, the $i$-th row vector of $A$, is a normal vector of that hyperplane and $b_i$ is proportional to the distance $d = \lvert b_i \rvert / \lVert\alpha_i\rVert$ between hyperplane and origin.
$$
0 =
\alpha_i^T (x - x_d)
= 
\alpha_i^T \left(x- 
(b_i/\lVert\alpha_i\rVert) (\alpha_i/\lVert\alpha_i\rVert)\right) 
= \alpha_i^T x - b_i
$$
A solution $x$ of $(*)$ has to be element of all $H_i$, thus be element of the intersection of all $H_i$.
Multiplying a row with a scalar:
As you write, the elementary row operation of replacing a row with a scalar multiple gives
$$
\alpha_i' = s \alpha_i \quad b_i' = s b_i
$$
and the new hyperplane equation
$$
\alpha_i'^T x = b_i' \iff \\
s \alpha_i^T x = s b_i \iff \\
\alpha_i^T x = b_i \wedge s \ne 0
$$
so if the scalar $s$ is chosen different from zero, the hyperplane stays the same $H_i' = H_i$ and thus the intersection and contained solutions stay the same.
Adding the scalar multiple of another row to a row:
We pick anther row $j$ and a scalar $s$ and add the scalar multiple of it to the $i$-th row:
$$
\alpha_i' = \alpha_i + s \alpha_j \quad b_i' = b_i + s b_j
$$
this leads to the new hyperplane equation
$$
\alpha_i'^T x = b_i' \iff \\
(\alpha_i + s \alpha_j)^T x = b_i + s b_j \quad (**)
$$
Spoiler 1:
If $s \ne 0$ and $\alpha_j \ne 0$ this changes the normal vector.
If $s \ne 0$ and $b_j \ne 0$ this changes the distance of the hyperplane to the origin.
Either case will result in a new different hyperplane $H_i' \ne H_i$.
Spoiler 2:
The change of the hyperplane $H_i$ into $H_i'$, while keeping the other hyperplanes $H_k' = H_k$ for $k \ne i$, is not that bad as it might seem first. Important is only that this change will not change the intersection.
Spoiler 3:
We now take $x \in H_i' \cap H_j'$ Because $x \in H_i'$ equation
$(**)$ holds. Because $x \in H_j' = H_j$ and $s \ne 0$ equation
$(***)$ holds: $$ \alpha_j^T x = b_j \iff s \alpha_j^T x = s b_j \quad
(***) $$ So we can subtract $(***)$ from $(**)$ and have that $$
\alpha_i^T x = b_i \quad (\#) $$ is still valid: $x \in H_i$. This
works both ways. For $x \in H_i \cap H_j$ we add $(***)$ to $(\#)$ and
see that $(**)$ holds, so $x \in H_i' \cap H_j'$. In other words $H_i
\cap H_j = H_i' \cap H_j'$ and so the whole intersection has not
changed $$ S = \bigcap_i H_i = \bigcap_i H_i' = S' $$ the solutions $x
\in S$ for $(*)$ stay the same.
