Wielościany i półprzestrzenie

Definicja 7.4   Niech $a_1,...,a_n$ będą liczbami rzeczywistymi nie równymi równocześnie zero (inaczej: $a_1^2+...+a_n^2>0$). Zbiór wektorów $x\in {\bf R}^n$ o współrzędnych $x_1,...,x_n$ spełniających $a_1x_1+...+a_nx_n \geq c$ (gdzie $c$ jest pewną liczbą rzeczywistą nazywamy półprzestrzenią. Wielościanem w ${\bf R}^n$ nazywamy przecięcie skończonej liczby półprzestrzeni.

Czytelnik zechce samodzielnie sprawdzić, że każdy wielościan (w sensie powyższej definicji) jest zbiorem wypukłym (por ćwiczenie ).
Celem niniejszego podrozdziału jest pokazanie jak z twierdzenia wynika podane niżej twierdzenie o rozdzielaniu wielomianów.

Twierdzenie 7.6 (O rozdzielaniu wielościanów)   Dla dowolnych wielościanów $W_1$ i $W_2$ rozłącznych i niepustych, istnieją rozłączne półprzestrzenie $P_1$ i $P_2$ takie, że $W_1 \subset P_1$ i $W_2 \subset P_2$.

Dowód. Przypuśćmy, że wielościany $W_1$ i $W_2$ dane są w następujący sposób:

$$W_1 = \{ {\bf x}\in {\bf R}^n: {\bf A}_1{\bf x}\leq {\bf b}_1\}$$

$$W_2 = \{ {\bf x}\in {\bf R}^n: {\bf A}_2{\bf x} \leq {\bf b}_2\}$$

Skoro $W_1 \cap W_2 = \emptyset$, to układ nierówności:

$$\left\{\begin{array}{c} {\bf A}_1{\bf x} \leq {\bf b}_1\\ {\bf A}_2{\bf x} \leq{\bf b}_2 \end{array}\right.$$

jest sprzeczny, a więc, na mocy twierdzenia istnieją wektory
${\bf y}_1\in {\bf R}^{m_1}, {\bf y}_2 \in {\bf R}^m_2$ (gdzie $m_i$ jest liczbą wierszy macierzy ${\bf A}_i$, $i=1,2$) takie, że

$${\bf y}_1{\bf A}_1 + {\bf y}_2 {\bf A}_2 = 0$$ (7.17)

$${\bf y}_1{\bf b}_1 + {\bf y}_2 {\bf b}_2 < 0$$ (7.18)

Z drugiego z powyższych związków wynika, że ${\bf y}_1 {\bf b}_1 < 0$ lub ${\bf y}_2 {\bf b}_2 < 0$. Bez straty ogólności możemy założyć, że ${\bf y}_1 {\bf b}_1 < 0$. Stąd zaś wynika, że ${\bf y}_1{\bf A}_1 \neq {\bf0}$, w przeciwnym bowiem przypadku układ ${\bf A}_1{\bf x} \leq {\bf b}_1$ byłby niezgodny, czyli wielościan $P_1$ pusty, a to jest sprzeczne z założeniami. Zbiory $\{ {\bf x}:{\bf y}_1{\bf A}_1{\bf x}\leq c \}$ oraz $\{ {\bf x}:{\bf y}_1{\bf A}_1{\bf x}\geq c\}$ są więc niepuste i różne od całej przestrzeni dla dowolnego $c \in {\bf R}$, czyli są półprzestrzeniami. W szczególności półprzestrzeniami są

$$H_1=\{ {\bf x}: {\bf y}_1{\bf A}_1{\bf x} \leq {\bf y}_1{\bf b}_1\}$$

i

$$H_2=\{ {\bf x}: {\bf y}_1{\bf A}_1{\bf x} \geq - {\bf y}_2{\bf b}_2\}$$

Z () wynika, że $H_1 \cap H_2 = \emptyset$.
Ponieważ () implikuje z kolei

$${\bf y}_1{\bf A}_1 = -{\bf y}_2{\bf A}_2$$

każdy ${\bf x}$ należący do $W_2$, czyli taki, że ${\bf A}_2{\bf x} \leq {\bf b}_2$ spełnia ${\bf y}_1{\bf A}_1{\bf x}= -{\bf y}_2{\bf A}_2{\bf x}\leq -{\bf y}_2{\bf b}_2$ (${\bf y}_2$ ma współrzędne nieujemne). A więc $W_2 \subset H_2$, co kończy dowód twierdzenia.