Show that exactly one of: \begin{cases} B^Tv = 0\\ d^Tv = 1 \end{cases} or $Bu=d$ has a solution. I tried with Farkas lemma, but I run into trouble.
Show that exactly one of the equations has a solution.
-
0The title and body contain two different questions. Do you want to show that only one equation has a solution, or exactly one? – 2012-11-21
3 Answers
Let $u = u_1 - u_2$ such that $u_1, u_2 \geq 0$. Then the second equation is equivalent to
$B \cdot (u_1-u_2) = d, u_1, u_2 \geq 0 \quad \Leftrightarrow \quad \begin{pmatrix} B & -B \end{pmatrix} \cdot \begin{pmatrix} u_1 \\ u_2 \end{pmatrix} = d, u_1,u_2 \geq 0$
Moreover the first equation is equivalent to
$B^T \cdot v \leq 0, B^T \cdot v \geq 0, d^T \cdot v<0 \Leftrightarrow \begin{pmatrix} B^T \\ -B^T \end{pmatrix} \cdot \begin{pmatrix} v \\ v \end{pmatrix} \geq 0, d^T \cdot v <0$
Now you can apply Farkas' Lemma.
-
0If there exist $v$ such that $B^T v =0$, $d^T \cdot v=1$, then $w:=-v$ solves $B^T w =0$, d^T w<0. On the other hand: If there exists a $w$ such that $B^T w = 0$, d^T w<0, then $v:= w/(d^T \cdot w) solves $B^T \cdot v=0$, $d^T \cdot v = 1$. Thus, buth formulations are equivalent. – 2012-11-22
I know very little optimization theory, but if we perform SVD to get $B=U\Sigma V^T$ and absorb the orthogonal matrices $U,V$ into $u,v,d$, the two systems can be rewritten as \begin{align} &\begin{cases} \Sigma^T \tilde{v} = 0,\\ \tilde{d}^T \tilde{v} = 1,\end{cases}\\ &\Sigma \tilde{u}=\tilde{d}. \end{align} where $\tilde{v}=U^Tv,\ \tilde{d}=U^Td$ and $\tilde{u}=V^Tu$. As $\Sigma$ is a (rectangular) diagonal matrix, the conclusion should be clear.
-
0Yes but that does just show that they dont have a common solution. – 2012-11-21
A solution which does not involve Farkas lemma.
First observe that it is not possible to have solutions $u$ and $v$ to both equations at the same time. If there were such a solutions, then $0=u^T 0 = u^T B^T v=(Bu)^T v=d^T v=1,$ hence a contradiction.
Then if the equation $Bu=d$ has no solution we can prove that the other system of equations has a solution. Indeed in this case $d$ is not contained in the span $span(B)$ of the columns of $B$ and thus $d=d_1+d_2,\quad \text{with }d_1\in span(B),\, d_2\in span(B)^\perp,\, d_2\neq 0\,.$ The vector $v=d_2/\|d_2\|^2$ is a solution of the first set of equations because $d^Tv=\frac{d_1^Td_2 +d_2^Td_2}{\|d_2\|^2}=\frac{0+\|d_2\|^2}{\|d_2\|^2}=1$ and $B^T v=\frac{1}{\|d_2\|^2} B^T d_2=0$ since $d_2\in span(B)^\perp$. Thus there is also at least one of the two sets of equations with a solution.