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.

Suppose we have a Hadamard matrix $H$ with rows $H_1,H_2,\ldots$ and look at the following system

$$H_j \cdot \mathbf{x} \le 1 \ \forall j$$

$$\sum_i x_i=1$$

Is there a name for polytopes defined in this way?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The system defines a region that is a rotated, translated, n-1 dimensional orthant.

First of all, if you consider a symmetrized version of the first criterion, $$\forall_{j=1}^n \ \ -1 \le H_j \cdot \mathbf{x} \le 1 ,$$ then this is a rotated n-dimensional hypercube, with the Hadamard matrix giving the rotation. The original inequalities can be seen to enforce only one of every pair of opposite sides of the hypercube, yielding a rotated and translated orthant.

If your matrix has a row of all ones, as is traditionally used for the first row (since Hadamard matrices are considered equivalent up to row/column negations and reorderings), then your second criterion is a face of the first criterion, and the resulting unbounded polytope is a (rotated and translated) n-1 dimensional orthant.


If for some reason you are using a Hadamard matrix that has not been "normalized" to have a row of all ones, then you will get either an n-1 dimensional simplex (if the second criterion cuts off the tip of the orthant), or some unbounded subset of the orthant, depending on what direction your orthant points compared to the fixed plane of the second criterion. (Note that the point (1/n,1/n,...) is always inside the orthant in this case, so you always get something.)

For example, a regular tetrahedron can be obtained from the following "unnormalized" Hadamard matrix:

+ - - -     + = +1    - = -1
- + - -     Note this pattern only works for size 4.
- - + -
- - - +

When plugged into the criteria, this yields a three dimensional regular tetrahedron in four dimensional space, with vertices (1,1,1,-2), (1,1,-2,1), (1,-2,1,1), (-2,1,1,1).

share|improve this answer
    
Thanks! I got some more useful info on mathoverflow -- mathoverflow.net/questions/38724/… –  Yaroslav Bulatov Apr 19 '11 at 17:52

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.