Linear Algebra: Preserving the null space

It means that performing an elementary row operation on a matrix does not change the null space of the matrix. That is, if $A$ is a matrix, and $E$ is an elementary matrix of the appropriate size, then the matrix $EA$ has the same null space as $A$.

To see why this is true, suppose first that $x$ is in the null space of $A$. This means that $Ax=\vec 0$. Multiplying both sides of this equation by $E$, we see that $(EA)x=E\vec 0 =\vec 0$, meaning that $x$ is also in the null space of $EA$. Now suppose that $x$ is in the null space of $EA$, so that $(EA)x=\vec 0$. As you mentioned, $E$ is invertible, so we can multiply this equation by $E^{-1}$:

$$Ax=IAx=(E^{-1}E)Ax=E^{-1}(EA)x=E^{-1}\vec 0=\vec 0\;,$$

showing that $x$ is in the null space of $A$. In other words, a vector is in the null space of $EA$ if and only if it is in the null space of $A$, and $EA$ and $A$ have the same null space.

For what it's worth, I think the following way of thinking about why row operations do not change the null space is worthwhile:

An important observation to make:

One may observe that multiplication of a matrix $A$ by a column vector $\bf x$ amounts to taking a linear combination of the columns of $A$. The coefficients of the particular linear combination are the coordinates of $\bf x$.

For example: $$\tag{1} \underbrace{\left[ \matrix{a_{11}&a_{12}&a_{13} \cr a_{21}&a_{22}&a_{23}\cr a_{31}&a_{32}&a_{33} }\right]}_{A} \left[\matrix{x\cr y\cr z}\right] =\left[\matrix{x a_{11} +ya_{12}+ z a_{13} \cr x a_{21} +ya_{22}+ z a_{23} \cr x a_{31} +ya_{32}+ z a_{33}} \right] = x\underbrace{\left[\matrix{\color{maroon}{a_{11}}\cr\color{darkgreen}{ a_{21}}\cr \color{darkblue}{a_{31}}}\right]}_{\bf a_1} +y\underbrace{\left[\matrix{\color{maroon}{a_{12}}\cr\color{darkgreen}{ a_{22}}\cr \color{darkblue}{a_{32}}}\right]}_{\bf a_2} +z\underbrace{\left[\matrix{\color{maroon}{a_{13}}\cr\color{darkgreen}{ a_{23}}\cr\color{darkblue}{ a_{33}}}\right]}_{\bf a_3} $$

A second important observation to make:

$\bf x$ is in the null space of $A$ if and only if $A{\bf x}=\bf0$. This means that the linear combination of the columns of $A$ whose coefficients are the coordinates of ${\bf x}=\Bigl[{\textstyle{x\atop y}\atop\scriptstyle z }\Bigr]$ is the zero vector:

$$\tag{2} x\underbrace{\left[\matrix{\color{maroon}{a_{11}}\cr\color{darkgreen}{ a_{21}}\cr \color{darkblue}{a_{31}}}\right]}_{\bf a_1} +y\underbrace{\left[\matrix{\color{maroon}{a_{12}}\cr\color{darkgreen}{ a_{22}}\cr \color{darkblue}{a_{32}}}\right]}_{\bf a_2} +z\underbrace{\left[\matrix{\color{maroon}{a_{13}}\cr\color{darkgreen}{ a_{23}}\cr\color{darkblue}{ a_{33}}}\right]}_{\bf a_3} =\bf0 $$

Now on to row operations:

Here, we make our third and final observation:

If one performs a row operation on $A$, then the corresponding right hand side of $(1)$ is obtained by performing the same row operation to each of ${\bf a_1}$, ${\bf a_2}$, and ${\bf a_3}$.

It follows from all of this that multiplying a row of $A$ by a non-zero number does not affect the null space. For example if row 1 of $A$ were multiplied by 2 then the right hand side of (1) would be: $$ x\underbrace{\left[\matrix{\color{maroon}{2a_{11}}\cr\color{darkgreen}{ a_{21}}\cr \color{darkblue}{a_{31}}}\right]}_{\bf a_1} +y\underbrace{\left[\matrix{\color{maroon}{2a_{12}}\cr\color{darkgreen}{ a_{22}}\cr \color{darkblue}{a_{32}}}\right]}_{\bf a_2} +z\underbrace{\left[\matrix{\color{maroon}{2a_{13}}\cr\color{darkgreen}{ a_{23}}\cr\color{darkblue}{ a_{33}}}\right]}_{\bf a_3} =\bf z $$ If (2) holds, it is easily seen that ${\bf z}=\bf0$.

It should be fairly obvious that interchanging two rows of $A$ does not affect the null space. For example if rows 1 and 3 of $A$ were interchanged, the right hand side of (1) would become $$ x\left[\matrix{\color{darkblue}{ a_{31}}\cr \color{darkgreen}{ a_{21}}\cr \color{maroon}{ a_{11}}}\right] +y\left[\matrix{\color{darkblue}{ a_{32}}\cr \color{darkgreen}{ a_{22}}\cr \color{maroon}{ a_{12}}}\right] +z\left[\matrix{\color{darkblue}{ a_{33}}\cr\color{darkgreen}{ a_{23}}\cr\color{maroon}{ a_{13}}}\right] =\bf z $$ If (2) holds, then $\bf z$ would be $\bf 0$.

Finally, if a multiple of a row of $A$ were added to another row of $A$, the null space would be unchanged. For example if twice row 1 of $A$ were added to to row 2, then the right hand side of $(1)$ would become:

$$\tag{3} x\left[\matrix{\color{maroon}{ a_{11}}\cr \color{darkgreen}{ a_{21}}+2\color{maroon}{ a_{11}}\cr\color{darkblue} a_{31}}\right] +y\left[\matrix{\color{maroon}{ a_{12}}\cr\color{darkgreen}{ a_{22}}+2 \color{maroon}{a_{12}}\cr\color{darkblue} a_{32}}\right] +z\left[\matrix{\color{maroon}{ a_{13}}\cr\color{darkgreen}{ a_{23}}+2 \color{maroon}{a_{13}}\cr\color{darkblue} a_{33}}\right] =\bf z $$

If $(2)$ holds, then $\bf z=0$. In particular, looking at the second component of the left hand side of $(3)$: $$\eqalign{ x(\color{darkgreen}{a_{21}}+2\color{maroon}{a_{11}})+ y(\color{darkgreen}{a_{22}}+2\color{maroon}{a_{12}})+ z(\color{darkgreen}{a_{23}}+2\color{maroon}{a_{13}}) &= (x \color{darkgreen}{a_{21}}+ y \color{darkgreen}{a_{22}}+ z \color{darkgreen}{a_{23}} )\cr &\ \ \ \ \ \ \ +2( x\color{maroon}{a_{11}} + y\color{maroon}{a_{12}}+ z\color{maroon}{a_{13}} )\cr&=0+2\cdot0\cr&=0}. $$

Say we have $V, W$ vector spaces and a linear transformation $T : V \to W$. The null space of $T$ is defined $N(T) = \{x \in V : T(x) = 0\}$.

When talking about row operations, we are talking about the matrix representation of the linear transformation. So if $\alpha = \{ x_1, ..., x_n \}$ is a basis of $V$ and $\beta = \{ y_1, ..., y_n \}$ is a basis of $W$ we have a matrix, say $A$, such that $A = [T]_\alpha^\beta$.

Say $T(x_i) = a_{i1}y_1 + ... + a_{in}y_n$. Then the matrix A will be the following $$ A = \left[\begin{array}{ccc} a_{11} & ... & a_{1n} \\ ... & ... & ... \\ a_{n1} & ... & a_{nn} \end{array}\right]. $$

Row operations are as follows
(i) Swap two rows.
(ii) Multiply row by non zero constant.
(iii) Add multiple of one row to a different row.

Say we swap the $i$th and $j$th row and call the new matrix $A'$. This new matrix defines a new linear transformation $T':V \to W$ such that $T'(x) = A'x$. We want to show that $N(T) = N(T')$. For any $x \in V$, say $$T(x) = b_1y_1 + ... + b_iy_i + ... + b_jy_j + ... + b_ny_n.$$ Then since $T'$ is just rows swapped $$T'(x) = b_1y_1 + ... +b_jy_i + ... + b_iy_j + ... b_ny_n.$$ Thus if $T(x) = 0$, $T'(x) = 0$, as $b_i = 0$ for all $i$. So $N(T) = N(T')$.

For (ii), think about if we multiply the $i$th row by $\beta$, then if the $i$th scalar for $T(x)$ is $c_i$, then the $i$th scalar for $T'(i)$ is $\beta c_i$. So if $T(x) = 0$, then $c_i = 0$, so $\beta c_i = 0$. All other scalars stay the same, thus $T'(x) = 0$. And if $T'(x) = 0$, $\beta^{-1}c_i = 0$, so $T(x) = 0$. Once again $N(T) = N(T')$.

I leave (iii) to you.