Test TeX

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:

[; \mathbf{x} > \mathbf{y}\ \ \ \ \vee\ \ \ \ \mathbf{x} \equiv \mathbf{y}\ \ \ \ \vee\ \ \ \ \mathbf{x} < \mathbf{y} ;]

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