1
$\begingroup$

Is there any intuitive, visual explanation of the following lemma:

Lemma: Let $\{ \alpha_{ij} : i = 1, \ldots, m, j = 1,\ldots, n \}$ be an $m \times n$ matrix, $\alpha_i = (\alpha_{i1}, \ldots, \alpha_{in}), \alpha^{(j)} = (\alpha_{1j},\ldots,\alpha_{mj})$, and $z = (z_1, \ldots, z_n)$. The system of inequalities \begin{align*} \alpha_i \cdot x & \ge 0 & i = 1,\ldots, m \\ z \cdot x & < 0 \end{align*} has a solution $x = (x_1, \ldots, x_n)$ iff the system \begin{align*} y\cdot \alpha^{(j)} & = z_j, & j = 1,\ldots, n \\ y_i & \ge 0, \end{align*} has no solution $y = (y_1, \ldots, y_m)$.

I know an complicated inductive proof, relying mainly on algebraic rearrangements, but not given any visualisations.

To give an example what I mean by visual explanation, consider the system \begin{align*} \sum_{j=1}^n \alpha_{ij} x_j > 0, i = 1,\ldots, m' \\ \sum_{j=1}^n \beta_{ij} x_j = 0, i = 1,\ldots, m'' \end{align*} then this has a solution iff the polyhedron generated by the vectors $\alpha_i$ does not intersect the subspace generated by the vectors $\beta_i$. This could be visualised for example when $m'' = 2$ and $n = 3$, then the points $0, \beta_1, \beta_2$ span a plane, and a solution vector $x$ is orthogonal to that plane. If we fix some $x$, then it makes an acute angle with any other vector on the same side of the plane and with the ones on the other side it makes an obtuse angle. So $x$ solves the system iff all the $\alpha_i$ lie on one side of the plane, and this argument could be easily generalized. But for the lemma mentioned in this question I would like to have a similar visualisation, is this possible? I find it complicated to give for example the statement that $\alpha_i x\ge 0$ any meaning with respect to the column space of the matrix $\{\alpha_{ij}\}$?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.