Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation:


$$\mathbf{S}\cdot\mathbf{x}=0$$


subject to the inequalities:


$$\mathbf{a}\le\mathbf{x}\le\mathbf{b}$$


where $\mathbf{a}$ and $\mathbf{b}$ are $n$-dimensional vectors.


Denote by $\Omega$ this space of solutions. The projection of $\Omega$ over the $i$'th coordinate ($0\le i\le n$) is the function:


$$f\_{k}\left(x\_{k}\right)=\int\delta\left(\mathbf{S}\cdot\mathbf{x}\right)\prod\_{i\ne k}\mathrm{d}x\_{i}$$


where the integral goes through all the values of $x\_i$ for all $i\ne k, 1\le i \le n$, and $\delta(\mathbf{y})$ is the $m$-dimensional Dirac's delta function, given by:


$$\delta\left(\mathbf{y}\right)=\prod\_{j}\delta\left(y\_{j}\right)$$


where $\delta(y\_j)$ are ordinary one-variable Dirac's delta functions.


I understand that the exact computation of $f\_{k}\left(x\_{k}\right)$ is NP-hard. But I was wondering if something can be said about its form. I have the intuition that $f\_{k}\left(x\_{k}\right)$ should be concave, or at least have zero or one maximum. Can you prove this? What other properties $f\_{k}\left(x\_{k}\right)$ satisfies in general?



What is the functional form of the projections of a subdimensional polytope?
Assuming that $S$ is full rank, let $u$ be some unit vector not orthogonal to the null space of $S$, and let $\Omega\_t =\lbrace x-t u~:~x\in\Omega,~ (x-tu)\cdot u = 0\rbrace$. then you are interested in the $(n-m-1)$-dimensional volumes
$f(t)=|\Omega\_t|$. Note that convexity of $\Omega$ implies that for $0\le\lambda\le1$, and $t$, $t'$ such that $\Omega\_t$, $\Omega\_{t'}$ are non-empty, $\lambda\Omega\_t+(1-\lambda)\Omega\_{t'}\subseteq\Omega\_{\lambda t+(1-\lambda) t'}$. By the Brunn-Minkowski theorem we then have
$$f(\lambda t+(1-\lambda) t')^{1/(n-m-1)}\ge|\lambda\Omega\_t+(1-\lambda)\Omega\_{t'}|^{1/(n-m-1)}\ge \lambda f(t)^{1/(n-m-1)}+(1-\lambda)f(t')^{1/(n-m-1)}\text.$$


EDIT: strange to see you came to check the answer one year later, but to answer your further question: yes, $f(t)$ is piecewise polynomial of degree at most $n-m-1$. Between values of $t$ corresponding to vertices, say $t\_0$ and $t\_1$, the cross section takes the form $\Omega\_t = \frac{t-t\_0}{t\_1-t\_0} \Omega\_{t\_1} + \frac{t\_1-t}{t\_1-t\_0} \Omega\_{t\_0}$. That the volume is a polynomial in $t$ follows from Steiner's formula (see <https://en.wikipedia.org/wiki/Mixed_volume>).


