1
$\begingroup$

I'm going through Farka's Lemma. I can understand what $Ax = b$ from a linear algebra perspective. But, I'm unable to understand what $Ax\geq b$?

$\endgroup$
  • 4
    $\begingroup$ Two possible definitions include $|Ax| >= |b|$ and element-by-element $>=$ comparisons. Is there nothing in the prior sections to give context to this relation? $\endgroup$ – abiessu Aug 29 '13 at 20:07
  • $\begingroup$ In the context of linear coding I've seen it used as a coordinate-wise relation, but I don't think I've seen that anywhere else. The norm inequality @abiessu suggested seems the most likely given no prior context. $\endgroup$ – Jonathan Y. Aug 29 '13 at 20:28
  • $\begingroup$ If never seen it to mean $|Ax| \geq |b|$ so the coordinate-wise inequality seems the most likely. $\endgroup$ – WimC Aug 29 '13 at 20:33
  • 1
    $\begingroup$ Farkas' Lemma will definitely use a coordinate-wise relation, it's for linear programming. $\endgroup$ – Evan Aug 29 '13 at 20:51
  • $\begingroup$ Rudra: In light of your responses to answers below, you should clarify what exactly you're looking for in an answer. $\endgroup$ – Cam McLeman Aug 31 '13 at 0:15
1
$\begingroup$

The meaning of that notation depends on context, but the Wikipedia linked article makes it clear:

"Here, the notation $x \ge 0$ means that all components of the vector x are nonnegative."

so, we can guess that $A x \ge b $ is to be understood component wise, or equivalently $A x - b \ge 0 $ with the above interpretation.

$\endgroup$
  • $\begingroup$ I understand that x>=0 means, that each component of vector x must be greater than or equal to zero. But can we say something from the perspective of linear maps like how is b related to the column space of A? $\endgroup$ – Rudra Murthy Aug 29 '13 at 21:35
0
$\begingroup$

For Farkas Lemma, $Ax \geq b$ means you multiply $Ax$ to get a vector $v$, and then $v_i \geq b_i$ for each index $i$ for the vectors. Similarly using the same interpretation, in linear programming problems, people often use $Ax \leq b$ where $x$ is the vector of variables for the linear programming problem and $A,b$ are numeric, to define the constraints for the linear programming problem.

$\endgroup$
  • $\begingroup$ I understand that x>=0 means, that each component of vector x must be greater than or equal to zero. But can we say something from the perspective of linear maps like how is b related to the column space of A? $\endgroup$ – Rudra Murthy Aug 29 '13 at 21:36
0
$\begingroup$

Oh I understand your question now. Here is something:
Consider the one-row case, $a^T x \geq b$. This is geometrically saying that $x$ lies on one side of the hyperplane $a^T x=b$ (pictures available for the two dimensional case, you should draw). The hyperplane is perpendicular to $a$.

Taking all rows together, each row gives a hyperplane cut, and tells you that $x$ is one one of side of the cut. Then these define some convex region for $x$ (not necessarily bounded though)

In terms of the column space, I can't think of anything... but I don't think it leads anywhere that will lend you intuition for understanding Farkas' lemma.

$\endgroup$
0
$\begingroup$

This is a short hand notation used in linear programming. For $A \in \mathbb{K}^{m \times n}$, $x \in \mathbb{K}^n$, $b \in \mathbb{K}^m$ it means $$ A x \le b \iff \forall i \in \{1,\ldots, m\}: a_i^\top x \le b_i $$ where $a_i$ is the $i$-th row vector of $A$.

This can be interpreted as $m$ linear inequality constraints of the type $\le$ on the $n$ unknowns $x_j$. $$ \sum_{j=1}^n a_{ij} x_j \le b_i $$ Agreeing with leonbloy, it can be interpreted component-wise like this $$ (Ax)_i \le b_i $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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