Notacja
- [;\mathbf{Z} := \{ ...\ \ -\!\!2\ -\!\!1\ 0\ 1\ 2\ ...\} ;]
- [;\mathbf{Z^+} := \{ x \in \mathbf{Z} : x \ge 0 \} ;]
- [; N\!N\!(\mathbf{Z^+}, 2) := \left\{ \left[ \begin{array}{c} x \\ X \end{array} \right] \in (\mathbf{Z^+})^2 : \left[ \begin{array}{c} x \\ X \end{array} \right] \ne \left[ \begin{array}{c} 0 \\ 0 \end{array} \right] \right\} ;]
Relacja uporządkowania
Dla dowolnych wektorów [; \left[\begin{array}{c} x \\ X \end{array}\right]\ \ \left[\begin{array}{c} y \\ Y \end{array} \right] \in N\!N\!(\mathbf{Z^+}, 2) ;] definiujemy:
- [;\left[\begin{array}{c} x \\ X \end{array}\right] > \left[\begin{array}{c} y \\ Y \end{array}\right]
\ \ \Leftarrow : \Rightarrow\ \ \det\left[\begin{array}{cc} x & y \\ X & Y \end{array}\right] > 0 ;] - [;\left[\begin{array}{c} x \\ X \end{array}\right] \equiv \left[\begin{array}{c} y \\ Y \end{array}\right]
\ \ \Leftarrow : \Rightarrow\ \ \det\left[\begin{array}{cc} x & y \\ X & Y \end{array}\right] = 0 ;] - [;\left[ \begin{array}{c} x \\ X \end{array}\right] < \left[ \begin{array}{c} y \\ Y \end{array} \right] \ \ \Leftarrow : \Rightarrow\ \ \det\left[ \begin{array}{cc} x & y \\ X & Y \end{array} \right] < 0 ;]
Ponadto, dla [; \mathbf{x}\ \ \mathbf{y} \in N\!N\!(\mathbf{Z^+}, \ 2) ;] definiujemy:
- [;\mathbf{x} \ge \mathbf{y}\ \ \Leftarrow : \Rightarrow\ \ (\mathbf{x} > \mathbf{y}\ \ \vee\ \ \mathbf{x} \equiv \mathbf{y} ) ;]
- [;\mathbf{x} \le \mathbf{y}\ \ \Leftarrow : \Rightarrow\ \ \left(\mathbf{x} < \mathbf{y}\ \ \vee\ \ \left(\mathbf{x} \equiv \mathbf{y} \right) ;]
Oczywiście zachodzi dokładnie jedna z trzech możliwości:
dla dowolnych wektorów [; \mathbf{x}\ \ \mathbf{y} ;].
Ponieważ [;\det\left[ \begin{array}{cc} \mathbf{y} & \mathbf{x} \end{array} \right] = -\det\left[ \begin{array}{cc} \mathbf{x} & \mathbf{y} \end{array} \right];], i w szczególności albo oba te wyznaczniki są równe [;0;] albo żaden, to:
- [; \mathbf{x} \equiv \mathbf{x} ;]
- [; \mathbf{x} \equiv \mathbf{y}\ \ \ \ \Longleftrightarrow\ \ \ \ \mathbf{y} \equiv \mathbf{x} ;]
- [; \mathbf{x} > \mathbf{y}\ \ \ \ \Longleftrightarrow\ \ \ \ \mathbf{y} < \mathbf{x} ;]
- [; \mathbf{x} \ge \mathbf{y}\ \ \ \ \Longleftrightarrow\ \ \ \ \det\left[ \begin{array}{cc}\mathbf{x} & \mathbf{y}\end{array}\right] \ge 0 ;]
dla dowolnych wektorów [; \mathbf{x}\ \ \mathbf{y} ;]. Pora dowieść przechodniość relacji nierówności wektorów. Będziemy korzystać z następującej cyklicznej tożsamości:
[; X\cdot \det\left[\begin{array}{cc} y & z \\ Y & Z \end{array}\right] +
Y\cdot \det\left[\begin{array}{cc} z & x \\ Z & X \end{array}\right] +
Z\cdot \det\left[\begin{array}{cc} x & y \\ X & Y \end{array}\right] = 0 ;]
którą łatwo sprawdzić bezpośrednio rozpisując wyznaczniki i redukując pary składników różniące się tylko znakiem. Tożsamość ta może także być interpretowana jako zerowanie się wyznacznika macierzy 3-na-3, mającej dwa wiersze identyczne, (X Y Z). W potrzebnym nam kontekście będziemy korzystać z następującego zapisu tejże tożsamości:
[; Z\cdot \det\left[\begin{array}{cc} x & y \\ X & Y \end{array}\right] +
X\cdot \det\left[\begin{array}{cc} y & z \\ Y & Z \end{array}\right] =
Y\cdot \det\left[\begin{array}{cc} x & z \\ X & Z \end{array}\right] ;]
Równości powyższe są spełnione także po zamianie dużych liter X Y Z przez małe x y z w roli współczynników przy wyznacznikach.
TWIERDZENIE 0
[; \left(\mathbf{x} \ge \mathbf{y}\ \ \&\ \ \mathbf{y} \ge \mathbf{z}\right)\ \ \ \ \Rightarrow\ \ \ \ \mathbf{x} \ge \mathbf{z} ;]
dla dowolnych wektorów [;\mathbf{x}\ \ \mathbf{y}\ \ \mathbf{z};].
DOWÓD
Przy podanych założeniach, korzystają z tożsamości powyżej, otrzymujemy:
[; Y\cdot \det\left[\begin{array}{cc} x & z \\ X & Z \end{array}\right] =
Z\cdot \det\left[\begin{array}{cc} x & y \\ X & Y \end{array}\right] +
X\cdot \det\left[\begin{array}{cc} y & z \\ Y & Z \end{array}\right] \ge 0 ;]
Więc także
[; \det\left[\begin{array}{cc} x & z \\ X & Z \end{array}\right] \ge 0 ;]
KONIEC DOWODU
Zauważmy, że dla dowolnych wektorów:
[; \det \left[ \begin{array}{cc} \mathbf{x} & \mathbf{x} + \mathbf{y} \end{array}\right] =
\det \left[ \begin{array}{cc} \mathbf{x} & \mathbf{x} \end{array}\right] + \det \left[ \begin{array}{cc} \mathbf{x} & \mathbf{y} \end{array}\right] =
\det \left[ \begin{array}{cc} \mathbf{x} & \mathbf{y} \end{array}\right] ;]
Podobnie mamy w sytuacji symetrycznej, tak że razem dostajemy:
[; \det \left[ \begin{array}{cc} \mathbf{x} & \mathbf{x} + \mathbf{y} \end{array}\right] =
\det \left[ \begin{array}{cc} \mathbf{x} & \mathbf{y} \end{array}\right] =
\det \left[ \begin{array}{cc} \mathbf{x} + \mathbf{y} & \mathbf{y} \end{array}\right] ;]
dzięki czemu zachodzi:
TWIERDZENIE 1 Niech [; \mathbf{x}\ \ \mathbf{y} \in N\!N\!(\mathbf{Z^+}, \ 2) ;]. Wtedy
- [; \mathbf{x} > \mathbf{y}\ \ \Rightarrow\ \ \mathbf{x} > \mathbf{x} + \mathbf{y} > \mathbf{y} ;]
- [; \mathbf{x} \equiv \mathbf{y}\ \ \Rightarrow\ \ \mathbf{x} \equiv \mathbf{x} + \mathbf{y} \equiv \mathbf{y} ;]
Sąsiedzi
Wektory [; \mathbf{x}\ \ \mathbf{y} \in N\!N\!(\mathbf{Z^+}, \ 2) ;] nazywamy sąsiadami [; \Leftarrow:\Rightarrow\ \ \det\left[\begin{array}{cc} \mathbf{x} & \mathbf{y}\end{array}\right] = 1 ;] (kolejność wektorów w kontekście sąsiadów jest ważna).
Z własności wyznacznika (patrz wyżej, tuż przed Twierdzeniem 2) natychmiast wynika
TWIERDZENIE 2 Niech wektory [; \mathbf{x}\ \ \mathbf{y} ;] będą sąsiadami. Wtedy sąsiadami są także pary wektorów [; \mathbf{x}\ \ \mathbf{x} + \mathbf{y} ;] oraz [; \mathbf{x} + \mathbf{y}\ \ \mathbf{y} ;].
Udowodnimy teraz podstawowe
TWIERDZENIE 3 Niech
[; \mathbf{x} := \left[\begin{array}{c} x \\ X \end{array}\right]\ \ \ \ \ \ \ \ \mathbf{y} := \left[\begin{array}{c} y \\ Y \end{array}\right]\ \ \ \ \ \ \ \ \mathbf{z} := \left[\begin{array}{c} z \\ Z \end{array}\right] ;]
będą trzema wektorami z [; N\!N\!(\mathbf{Z^+}, 2) ;], spełniającymi dwa warunki:
- [; \mathbf{x} > \mathbf{y} > \mathbf{z} ;]
- wektory [; \mathbf{x}\ \ \mathbf{y} ;] są sąsiadami.
Wtedy [; Y \ge X+Z\ \ \ \ \&\ \ \ \ y \ge x+z ;].
UWAGA Co więcej, przy podanych założeniach:
[; Y \ge X+Z\ \ \ \ \Logleftrightarrow\ \ \ \ y \ge x+z ;].
Wynika to z defincji wyznacznika, jako różnicy dwóch diagonalnych iloczynów, oraz z definicji sąsiadów.
DOWÓD TWIERDZENIA Na mocy wyznacznikowej tożsamości powyżej, otrzymujemy:
[; Z\cdot \det\left[\begin{array}{cc} x & y \\ X & Y \end{array}\right] +
X\cdot \det\left[\begin{array}{cc} y & z \\ Y & Z \end{array}\right] =
Y ;]
Ponieważ powyższe dwa wyznaczniki są dodatnimi liczbami calkowitymi, to:
[; Y \ge X+Z ;]
KONIEC DOWODU