0

I'm reading linear programming and I bumped into the following:

enter image description here

I'm having trouble getting grasp on the proof of proposition 2. Could someone perhaps explain it to me in other terms? For some reason the proof is unclear for me :S So how did we conclude that $H$ is an $(n-1)$-dimensional hyperplane in simple english? ;)

Thank you for any help!

jjepsuomi
  • 8,619
  • 1
    "This" refers to $M$, and $H$ is a hyperplane, which is only a subspace if it includes the origin. – AnonSubmitter85 Aug 19 '13 at 08:06
  • 1
    Do you understand what a linear variety is? What exactly is confusing you? Most people (I think) refer to these as affine sets, which just means that if you take any two points in the set and draw a line between them (with the line extending out indefinitely), that all other points on this line are also in the set. – AnonSubmitter85 Aug 19 '13 at 08:23
  • +1 Hi @AnonSubmitter85 :) What is confusing me is: how did we conclude in the proof that H is $(n-1)$-dimensional hyperplane? – jjepsuomi Aug 19 '13 at 08:46

2 Answers2

1

Let $\mathbf{x}_1,\mathbf{x}_2 \in H$, then by definition $\mathbf{a}^{\mathrm{T}} \mathbf{x}_1 = c$ and $\mathbf{a}^{\mathrm{T}} \mathbf{x}_2 = c$. Now,

$$ \mathbf{a}^{\mathrm{T}}\left( \lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2 \right) = \lambda \mathbf{a}^{\mathrm{T}} \mathbf{x}_1 + (1-\lambda) \mathbf{a}^{\mathrm{T}} \mathbf{x}_2 = \lambda c + (1-\lambda)c = c $$

Therefore, $( \lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2 ) \in H$, which means that $H$ is a linear variety.

All that is left is to show that its dimension is $n-1$.

AnonSubmitter85
  • 3,455
1

What proposition 2 is saying, is this.

What is being said is this.

If $a \cdot x = c$, then the point defined by $x$ falls on a plane $H$.

The proof goes along the line that suppose there is a known X, where $a \cdot X = c$. Then the product $a \cdot (x - X) = c - c = 0$ means that the vector $x-X$ is at right angles to $a$, and thus makes a (hyper)plane, that passes through the point $0$. This is plane $M = H-x_1$

The addition of $X$ to any point on the hyperplane, makes a plane equidistant (at equal distance) from the hyperplane through $0$, and therefore is itself a hyperplane. This means that the set of vectors orthogonal to $a$ lie in a space one dimension less than the space that $a$ is in.

So if you find several vectors or points $x_1, x_2, \dots$, that $a \cdot x_1 = a \cdot x_2 \dots$ then these points $x_i$ lie on a common hyperplane perpendicular to the vector $a$.

In more direct terms, suppose $a = z$, the unit vector on the $z$ axis, then the dot product of $a \cdot x$ is simply the $z$ coordinate, $c$. This gives $H$.

Now, you have a vector $x_1$, which $z \cdot x_1 = c$. You get plane $M = H-x_1$ will give a set of vectors which the dot product with $z$ is $0$, so it defines a subspace where $z = 0$ always. Since this is identical to a space of one fewer axis (with $z$ removed), then it is a flat or linear subspace.

Adding back $x_1$ in it, means that $H$ is equal distance from $M$, and is thus a plane itself.

wendy.krieger
  • 6,856