Q:

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?

A:

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

