# 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.

-

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.

-
Thanks a lot, the if and only if explanation helps me connect these facts together now! –  mcrocker Feb 12 '12 at 4:32

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_j + ... + b_iy_i + ... b_ny_n.$$ Thus if $T(x) = 0$, $T'(x) = 0$ and vice versa. 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.

-

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

-

I think the most natural way to think about this is to note that the kernel of a matrix is also the orthogonal complement to the column-space of it's transpose. (this is the fundamental theorem of linear algebra)

So when you do row operations on a matrix, this is the same as doing linear combinations of the columns in it's transpose. This doesn't change the overall space spanned by those columns in the transpose, so it doesn't change the kernel of the original matrix.

-