无界积分多面体整无界方向存在性的证明咨询
嘿,各位大佬好!最近在啃积分多面体相关的问题,碰到个卡壳的点想请教大家:
我现在有个有理多面体 $P := {\mathbf{x} \in \mathbb R^n : A\mathbf{x} = \mathbf{0}^m, \mathbf{x} \geq \mathbf{0}^n}$,其中 $A \in \mathbb Z^{n\times m}$ 是整数矩阵,而且已经确认这个多面体是其整数点的凸包——也就是它是个积分多面体。
先给不太熟悉的朋友补个基础定义:一个向量集合 $X \subseteq \mathbb R^n$ 的凸包,是包含 $X$ 的最小凸集,具体公式是:
$$
\text{conv.hull}(X) = {\lambda_1 \mathbf{x}_1 + \dots +\lambda_t \mathbf{x}_t
:
t \geq 1; \mathbf{x}_1, \dots, \mathbf{x}_t \in X;
\lambda_1, \dots, \lambda_t \geq 0;
\lambda_1 + \dots + \lambda_t = 1
}.
$$
现在我还知道,存在某个线性函数 $\mathbf{c}^T\mathbf{x}$,使得 ${\mathbf{c}^T\mathbf{x} \mid \mathbf{x} \in P}$ 是无界的——说白了就是这个线性函数在P上能取到任意大的值。
我的核心疑问是:这种情况下,是不是一定存在一个非零整数向量 $\mathbf{d} \in \mathbb Z^n$,满足这几个条件:
- $A\mathbf{d} = \mathbf{0}^m$(也就是d是P的可行方向);
- $\mathbf{d} \geq \mathbf{0}^n$;
- $\mathbf{c}^T\mathbf{d} > 0$(沿着d走,线性函数值会严格递增);
- 对任意 $\mathbf{x} \in P$ 和 $t \geq 0$,都有 $\mathbf{x} + t\mathbf{d} \in P$(也就是这条射线完全包含在P里,是无界方向)。
如果一定存在的话,能不能给个相对严谨的证明思路?要是有反例的话,也麻烦举个例子说明~
备注:内容来源于stack exchange,提问作者Polyhedrish

