3
$\begingroup$

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?

2 Answers 2

3

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

  • 0
    Can you give me an example to help me clarify2012-06-20
2

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