Προβλήματα Μαθηματικών

Απρίλιος 15, 2009

Ανισότητα αναδιάταξης

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 10:33 πμ

Έστω P ένας n\times n πίνακας με μη αρνητικά στοιχεία (p_{ij})_{1\le i,j\le n} τέτοια ώστε

\displaystyle \sum_{i=1}^n p_{ij}=1 για κάθε j=1,2,...,n      και      \displaystyle \qquad \sum_{j=1}^n p_{ij}=1 για κάθε i=1,2,...,n.

Αν x\in\mathbb{R}^n συμβολίζουμε με x^{*} (αντίστοιχα x_*) το διάνυσμα που προκύπτει από το x αν αναδιατάξουμε τις συντεταγμένες του με αύξουσα (αντίστοιχα φθίνουσα) σειρά. Δείξτε ότι για κάθε x,y\in\mathbb{R}^n έχουμε

\displaystyle x^*\cdot y_*\le \sum_{i,j=1}^n p_{ij}x_iy_j\le x^{*}\cdot y^{*}.

Advertisements

9 Σχόλια »

  1. Υπόδειξη:

    Προσπαθήστε πρώτα να δείξετε την ανισότητα στην περίπτωση που ο πίνακας P είναι πίνακας αναδιάταξης, έχει δηλαδή ακριβώς ένα 1 σε κάθε γραμμή και κάθε στήλη και όλα τα υπόλοιπα στοιχεία του είναι μηδέν.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Μαΐου 9, 2009 @ 1:17 μμ

  2. Ζητειται να δειξουμε x^{*} \cdot y_{*} \leq x^{T} \cdot A \cdot y \leq x^{*} \cdot y^{*} , για καθε x,y \in \mathbb{R}^n
    και A διπλά στοχαστικό πίνακα.
    Στην περιπτωση που ο A είναι πίνακας μετάθεσης, η μεσαία ποσότητα γράφεται
    \sum_{i=1}^{n} x_i y_{\sigma (i)}, όπου \sigma η μετάθεση που αντιστοιχεί στον πίνακα.
    Το τελευταίο άθροισμα μπορεί να αναδιαταχτεί (η τιμή του παραμένει η ιδια) ώστε τα x_i να
    εμφανίζονται με αύξουσα σειρά κι ετσι μπορούμε να υποθέσουμε πως x = x^{*} .
    Υποθέστε πως το y δεν είναι ίσο με το y^{*} . Τότε υπάρχει k  y_{\sigma (l)} . Οπότε
    \sum_{i=1}^{n} x_i y_{\sigma (i)} = \sum_{i\neq k,l} x_i y_{\sigma (i)} + x_k y_k + x_l y_l \leq sum_{i\neq k,l} x_i y_{\sigma (i)} + x_k y_{\sigma (l)} + x_l y_{\sigma (k)},
    κι αυτό γιατί (x_k - x_l) (y_{\sigma (k)} - y_{\sigma (l)} ) \leq 0 .
    Αυτό σημαίνει πως μπορούμε να εναλλάξουμε τη σειρά κάθε ζεύγους y_{\sigma (k)} , y_{\sigma (l)} για τα οποία ισχύει y_{\sigma (k)} > y_{\sigma (l)} .
    Επαναλαμβάνοντας αυτη τη διαδικασια παιρνουμε τη δεξιά ανισότητα.
    Η αριστερή ανισότητα, αποδεικνύεται με ακριβώς ανάλογο τρόπο υποθέτοντας ότι y \neq y_{\ast} .

    Στη γενική περίπτωση διπλά στοχαστικού πίνακα A επικαλούμαστε το Θεώρημα Birkhoff
    http://mathworld.wolfram.com/DoublyStochasticMatrix.html

    που μας λεει πως ο A γράφεται σαν κυρτός συνδυασμός πινάκων αναδιάταξης.
    Για κάθε ενα απο τους πινακες αναδιάταξης ισχύει η ανισότητα και αθροίζοντας όλες
    αυτες τις ανισότητες (πολλαπλασιασμένες με την κατάλληλη σταθερά) έχουμε το ζητουμενο.

    Μου αρέσει!

    Σχόλιο από henk&christos — Δεκέμβριος 23, 2010 @ 11:17 μμ

  3. Στην 7η γραμμή δεν εμφανίστηκε το εξής:

    ..Τότε υπάρχει k  y_{\sigma (l)} . Οπότε …

    Μου αρέσει!

    Σχόλιο από henk&christos — Δεκέμβριος 23, 2010 @ 11:24 μμ

  4. Η ιδέα είναι σε γενικές γραμμές σωστή. Όμως η διαδικασία που πρέπει να επαναλάβουμε για να πάρουμε τη δεξιά ανισότητα δεν είναι εντελώς σαφής όπως είναι γραμμένη. Θέλεις να εξηγήσεις την ιδέα σου λίγο περισσότερο?
    Ίσως βοηθήσει το ότι μπορούμε χωρίς βλάβη να υποθέσουμε ότι x=x^* και y=y^* αφού αν y_i^*=y_{\pi(i)},\ x_i^*=x_{\sigma(i)} και a_{ij}=p_{\sigma(i)\pi(j)} τότε o πίνακας A είναι διπλά στοχαστικός και \displaystyle \sum_{i,j=1}^np_{ij}x_iy_j=\sum_{i,j=1}^n a_{ij}x_i^*y_j^*.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Δεκέμβριος 26, 2010 @ 3:24 πμ

  5. Αν κανείς δεν θέλει να χρησιμοποιήσει το όμορφο αποτέλεσμα στο οποίο παραπέμπει ο henk&christos,
    υπάρχει και μια στοιχειώδης απόδειξη. Παρατηρήστε (για ζέσταμα) ότι αν ο A είναι συμμετρικός τότε

    \displaystyle \sum_{i=1}^n x_i^*y_i^*-\sum_{i,j=1}^n x_i^*y_j^*a_{ij}=\frac{1}{2}\sum_{i,j=1}^{n}a_{ij}(x_i^*-x_j^*)(y_i^*-y_j^*)\ge 0.

    Στη γενική περίπτωση και πάλι μπορούμε να γράψουμε

    \displaystyle \sum_{i=1}^n x_i^*y_i^*-\sum_{i,j=1}^n x_i^*y_j^*a_{ij}=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\sum_{k=i}^{j-1}(y_k^*-y_{k+1}^*)\big(a_{ij}(x_i^*-x_k^*)+a_{ji}(x_k^*-x_j^*)\big)\ge 0.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Δεκέμβριος 26, 2010 @ 3:36 πμ

  6. Έχοντας υποθέσει x = x^{*} και y \neq y^{*} έπεται πως υπάρχουν
    k  y_{\sigma (l)} .
    Παρατηρώντας ότι (x_k - x_l)\cdot (y_{\sigma (k)} - y_{\sigma (l)} ) \leq 0
    έπεται πως μπορούμε να αντικαταστήσουμε στο άθροισμα \sum_{i=1}^{n} x_i \cdot y_{\sigma (i)}
    το x_k \cdot y_{\sigma (k)} + x_l \cdot y_{\sigma (l)}
    από το x_k \cdot y_{\sigma (l)} + x_l \cdot y_{\sigma (k)} .
    Η διαδικασια επαναλαμβάνεται μεχρι τη στιγμή που δεν υπάρχουν k  y_{\sigma (l)} , που σημαίνει οι συντεταγμένες του y έχουν
    αναδιαταχτεί σε αύξουσα σειρα.

    Μου αρέσει!

    Σχόλιο από henk&christos — Δεκέμβριος 27, 2010 @ 1:12 μμ

  7. Επιμένει, να μην εμφαζίζει το πως βρίσκουμε τα k,l.

    Αφού y \neq y^{*}, υπάρχου k y_{σ(l)}.

    Μου αρέσει!

    Σχόλιο από henk&christos — Δεκέμβριος 27, 2010 @ 1:16 μμ

  8. Υπάρχουν k,l (k μικρότερο του l) ώστε οι
    αντίστοιχες συντεταγμένες του x να είναι η μία
    μικρότερη ή ιση της άλλης και οι αντίστοιχες
    συντεταγμένες του y να είναι η μια μεγαλύτερη της αλλής.

    Μου αρέσει!

    Σχόλιο από henk&christos — Δεκέμβριος 27, 2010 @ 1:21 μμ

  9. Σωστά. Και καλή χρονιά!

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Ιανουαρίου 1, 2011 @ 10:58 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: