Linear Algebra: Preserving the null space

What does it mean when a book says that row operations preserve the null space? And why should that be true? I have read that row operations are equivalent to multiplying a vector on the left by an invertible elementary matrix. And I think I understand that the nullspace is the set of all vectors from $u \in U$ which get mapped to the zero vector in $V$ if $T:U\rightarrow V$ is linear. But I'm still not sure what this means.

Solution 1:

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.

Solution 2:

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}. $$