# Null space of a matrix

I was referring to this lecture http://www.stanford.edu/class/ee364a/videos/video05.html (about 0:38:10) related to convex optimization and for optimization it had a certain affine function equality constraint like $$Ax=b$$

The lecturer then obtained the equivalent optimization problem removing the equality constraint and replacing $x$ with $Fz+x_0$ $$Ax=b \iff x=Fz+x_0\text{ for some }z.$$

According to the lecturer $x_0$ is a solution of the equality $Ax=b$ and $F$ is obtained from the null space of matrix $A$. I didn't get this null space thing and how this $$x = Fz+x_0$$ is derived. Can anyone please explain?

-
en.wikipedia.org/wiki/… –  Peter Sheldrick Jun 20 '12 at 21:18
The part where he talks about that part starts at 38:00 in the video. –  Peter Sheldrick Jun 20 '12 at 22:18

The null space of matrix $A$ are all those vectors $z$ with $Az=0$ where $0$ is the zero vector (same dimensions as $x$ and $b$).

These vectors build up a vector space which can be described by a base $B$. And that base $B$ can be used to form a matrix $F$ - just fill up with zero columns until you can operate on the same vectors $A$ can.

Now multiplying $F$ with any vector $z$ is just a linear combination of some null vectors and the base vectors of $A$'s null space, in short $A(Fz)=0$.

If for $x_0$ we know $Ax_0=b$ we can add a zero and are done

$Ax_0=b\Leftrightarrow0+Ax_0=b\Leftrightarrow A(Fz)+Ax_0=b\Leftrightarrow A(\underbrace{Fz+x_0}_{=:x})=b$

No matter what $z$ an $x$ defined like that is a solution.

EDIT: Example:

$$A=\left[\begin{matrix}1&0&0\\3&2&-2\\3&3&-3\end{matrix}\right]$$ Now to find the null space one has to solve $Ax=0$. For that use row reduction until the matrix is in an "easily readable" form. $$A\longrightarrow\left[\begin{matrix}1&0&0\\0&2&-2\\0&3&-3\end{matrix}\right]\longrightarrow\left[\begin{matrix}1&0&0\\0&2&-2\\0&0&0\end{matrix}\right]=:\bar A$$ Row reduction ensures $Ax=0\Leftrightarrow\bar Ax=0$ and in the latter matrix the rows "read" as follows:
1. $1x_1+0x_2+0x_3=0\quad$ aka $x_1$ the first component of $x$ must be $0$.
2. $2x_2-2x_3=0\quad$ aka $x_2=x_3$.
3. Basically: Whatever.

So the single base vector for $A$'s null space is $$B_1=\left[\begin{matrix}0\\1\\1\end{matrix}\right]$$ To get $F$ fill up with null vectors $$F=\left[\begin{matrix}0&0&0\\1&0&0\\1&0&0\end{matrix}\right]$$ For an arbirtray $z$ we get $$A(Fz)=\left[\begin{matrix}1&0&0\\3&2&-2\\3&3&-3\end{matrix}\right]\left(\left[\begin{matrix}0&0&0\\1&0&0\\1&0&0\end{matrix}\right]\left[\begin{matrix}z_1\\z_2\\z_3\end{matrix}\right]\right)=\left[\begin{matrix}1&0&0\\3&2&-2\\3&3&-3\end{matrix}\right]\left[\begin{matrix}0\\z_1\\z_1\end{matrix}\right]=\left[\begin{matrix}0\\2z_1-2z_1\\3z_1-3z_1\end{matrix}\right]=\left[\begin{matrix}0\\0\\0\end{matrix}\right]$$ Again, if for $x_0$ we know $Ax_0=b$ it follows for any $z$ that an $x:=Fz+x_0$ yields $Ax=b$.

-
Can you give me an example to help me clarify –  user31820 Jun 20 '12 at 22:16

When we have $x_b$ a solution of $Ax = b$, then all other solutions of $Ax+b$ are given by $x_b + x_0$, where $x_0$ is any solution of $Ax = 0$.

Proof: Fix $x_b$ a solution of $Ax=b$.

1. Let $x_0$ be a solution of $Ax = 0$. Then $x_0 + x_b$ is a solution of $Ax+b$, since $A(x_0+x_b)= Ax_0 + Ax_b = 0 + b = b$.
2. Now, let $y_b$ be any solution of $Ax=b$. To prove that it has the form $x_0 + x_b$ for some $x_0$ solution of $Ax = 0$, it suffices to show that $y_b - x_b$ is indeed a solution of $Ax = 0$. Since $A(y_b - x_b) = Ay_b - Ax_b = b - b = 0$, the result follows.

This is a proof of two inclusions, which together show the equality, for any $x_b$ solution of $Ax = b$: $\{ x \in \mathbb{K}^n : Ax = b \} = x_b + \{ x \in \mathbb{K}^n : Ax = 0 \} = \{ x + x_b : x \in \mathbb{K}^n, Ax = 0 \}$ (where $\mathbb{K}$ is the appropriate field and $n$ is the number of columns of $A$).

We call the set $\{ x \in \mathbb{K}^n : Ax = 0 \}$ the null space of $A$.

-