Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.