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

Ιουλίου 8, 2010

Προσθαφαιρέσεις διανυσμάτων

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 10:21 μμ

Έχουμε κάποια διανύσματα v_1, v_2, \ldots, v_n \in {\mathbb R}^d με Ευκλείδιο μήκος |v_j| = 1. Δείξτε ότι μπορούμε να επιλέξουμε πρόσημα \epsilon_1=\pm 1, \ldots, \epsilon_n = \pm 1 τέτοια ώστε αν

u = \epsilon_1 v_1 + \cdots + \epsilon_n v_n

τότε να ισχύει |u| \le \sqrt{n}. Επίσης μπορούμε να τα επιλέξουμε ώστε να ισχύει |u| \ge \sqrt{n}.

Advertisements

16 Σχόλια »

  1. Καλησπέρα Αγαπητοί όλοι,

    Νομίζω πως έχω μια λύση σε αυτό το πρόβλημα την οποία σας την παραθέτω (αν τα καταφέρω με το latex)

    Είπαμε:

    u=\epsilon_{1}u_{1}+\cdots +\epsilon_{n}u_{n}=[\epsilon_{1},\epsilon_{2},\cdots, \epsilon_{n}]\cdot \left[ \begin{array}{ccc} u_{1,1} & \cdots & u_{1,d} \\ \vdots & & \vdots \\ u_{n,1} & \cdots & u_{n,d} \end{array}\right] \Longrightarrow

    u=\left(\epsilon_{1}u_{1,1}+\epsilon_{2}u_{2,1}+\cdots +\epsilon_{n}u_{n,1},\cdots ,\epsilon_{1}u_{1,d}+\epsilon_{2}u_{2,d}+\cdots +\epsilon_{n}u_{n,d} \right)\Longrightarrow

    \vert u\vert =\sqrt{(\epsilon_{1}u_{1,1}+\epsilon_{2}u_{2,1}+\cdots +\epsilon_{n}u_{n,1})^{2}+\cdots + (\epsilon_{1}u_{1,d}+\epsilon_{2}u_{2,d}+\cdots +\epsilon_{n}u_{n,d})^2} \Rightarrow

    \vert u\vert = \left[ (\epsilon_{1}u_{1,1})^2+(\epsilon_{2}u_{2,1})^2+\cdots +(\epsilon_{n}u_{n,1})^2+\cdots + \right.

    \ \ \ \ \ \ \left.(\epsilon_{1}u_{1,p})^2+(\epsilon_{2}u_{2,p})^2+\cdots +(\epsilon_{n}u_{n,p})^2+2 \cdot \sum\limits_{i=1}^n \epsilon_{i} \displaystyle\sum\limits_{j=1, j\neq i}^n \ \epsilon_{j}\displaystyle\sum\limits_{p=1}^d \left( a_{i}^p  a_{j}^p \right)\right]^{1/2}=

    \ \ \sqrt{\vert u_1\vert ^2+\vert u_2\vert ^2+\cdots + \vert u_n\vert ^2 + 2 \cdot \sum\limits_{i=1}^n \epsilon_{i} \displaystyle\sum\limits_{j=1, j\neq i}^n  \epsilon_{j}\displaystyle\sum\limits_{p=1}^d \left( a_{i}^p  a_{j}^p \right)}

    \leqslant \sqrt{n+2 \cdot \sum\limits_{i=1}^n \epsilon_{i}\displaystyle\sum\limits_{j=1, j\neq i}^n  \epsilon_{j}\displaystyle\sum\limits_{p=1}^d \left( a_{i}^p  a_{j}^p \right)}

    (Κουράστηκα με το Latex…είχα και καιρό να το χρησιμοποιήσω…)

    Τα a_{i}^p  a_{j}^p \forall i,j,p είναι σταθερά επειδή είναι οι συντεταγμένες των δεδομένων διανυσμάτων…Οπότε μπορούμε να επιλέξουμε τα έψιλον για να ισχύει ή η πρώτη ανισότητα της εκφώνησης ή η δεύτερη….

    Μου αρέσει!

    Σχόλιο από Μανούσος Κλάδος — Ιουλίου 10, 2010 @ 5:20 μμ

  2. Δεν ξέρω πως μπορώ να επεξεργαστώ το σχόλιο μου αλλά έχει γίνει ένα τυπογραφικό λάθος (ελπίζω να μην έχει άλλα :Ρ )… στην τελευταία ρίζα οι τελίτσες καιτο + πρέπει να φύγουν

    Μου αρέσει!

    Σχόλιο από Μανούσος Κλάδος — Ιουλίου 10, 2010 @ 5:22 μμ

  3. Μανούσο,

    Επεξεργάστηκα λίγο το latex ώστε να χωράει …

    Κατ’ αρχήν τα a^p_i που έχεις είναι τα ίδια με τα u_{p,i}, σωστά;

    Αλλά δεν κατάλαβα πώς ακριβώς θα γίνει η επιλογή των \epsilon_j. Δε μου είναι φανερό πώς θα κάνεις το δεύτερο προσθετέο στο τελευταίο υπόριζο να είναι αρνητικός ή θετικός.

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 10, 2010 @ 10:47 μμ

  4. Έκανα μια διόρθωση στο πρόβλημα αυτό: η συνθήκη |v_j| \le 1 μετατράπηκε σε |v_j|=1. Το πρώτο ερώτημα (|u| \le \sqrt{n}) δεν είχε πρόβλημα αλλά το δεύτερο (|u| \ge \sqrt{n}) είχε βέβαια αφού τίποτα δεν εμπόδιζε τα v_j να είναι πολύ μικρά (π.χ. 0).

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 11, 2010 @ 1:54 πμ

  5. Καλησπέρα Μιχάλη,

    Νόμιζα πως την λύση την έχεις ήδη και ξεπατώθηκα να αποδείξω κάτι το οποίο δεν μπορεί να ισχύει 🙂

    Με αυτό την νέα συνθήκη που εισήγαγες το μικρότερο ή ίσο στην τελευταία σειρά γίνεται ίσο…Τώρα το άθροισμα των γινομένων (ΑΤΓ) (που έχεις δίκιο είναι λάθος τα a_{i}^p …πιο συγκεκριμένα ισχύει a_{i}^p=u_{i,p} Συγνώμη για το κομφούζιο άλλα χάθηκα μάλλον μέσα στις σημειώσεις μου… )θα έχει κάποιο πρόσημο (η θετικό θα είναι η αρνητικό (ή και μηδέν)) Οπότε η προσέγγιση μου προτείνει το εξής:

    Αν ΑΤΓ>0 τότε αν πάρουμε όλα τα \epsilon_{i} θετικά (δηλαδή +1) έχουμε την δεύτερη συνθήκη αν τα πάρουμε αρνητικά έχουμε την πρώτη συνθήκη.
    Αντίστοιχα αν το ΑΤΓ<0….

    Στην περίπτωση που έχουμε ΑΤΓ=0 έχουμε το την ισότητα των δύο ανισοτήτων…

    Μου αρέσει!

    Σχόλιο από Μανούσος Κλάδος — Ιουλίου 11, 2010 @ 2:48 πμ

  6. Μανούσο,

    Το άθροισμα των γινομένων που λες εξαρτάται από τα i,j.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 11, 2010 @ 2:52 πμ

  7. Ναι…αλλά δεν είναι αυτό το θέμα…Το θέμα είναι ότι υπάρχει αλληλεπίδραση των \epsilon_{i} με τα \epsilon_{j}

    Θα το ξανακοιτάξω…

    Μου αρέσει!

    Σχόλιο από Μανούσος Κλάδος — Ιουλίου 11, 2010 @ 10:57 πμ

  8. Μια απλή ιδέα βασισμένη στην πιθανοθεωρητική μέθοδο που αποδεικνύει το ζητούμενο είναι η εξής: θα δείξουμε οτι το διάνυσμα x = \sum_i \epsilon_i u_i όπου τα \epsilon_i είναι τυχαίες ανεξάρτητες μεταβλητές με Pr(\epsilon_i=1)=Pr(\epsilon_i=-1)=\frac{1}{2} έχει αναμενόμενο (ευκλείδιο) μήκος \sqrt(n). Πριν δείξουμε αυτό τον ισχυρισμό, παρατηρήστε οτι αν ένα σύνολο αριθμών έχει μέσο όρο ν, τότε υπάρχει τουλάχιστον ένας όρος με τιμή μεγαλύτερη ή ίση του ν και ένας τουλάχιστον όρος με τιμή μικρότερη ίση του ν.

    Όντως, με απλή άλγεβρα προκύπτει οτι E[|x|^2] = E[ |\sum_i \epsilon_i u_i |^2 ] = E[ \sum_i \sum_j \epsilon_i \epsilon_j u_i u_j ] = \sum_i \sum_j u_i u_j E[\epsilon_i \epsilon_j]= n αφού λόγω της ανεξαρτησίας οι όροι του αθροίσματος της μορφής u_i u_j \epsilon_i \epsilon_j για i \neq j εξαφανίζονται και παίρνουμε οτι το αναμενόμενο μήκος στο τετράγωνο είναι E[|x|^2]=\sum_i u_i u_i = \sum_i |u_i|^2 = \sum_i 1 = n. Άρα υπάρχουν επιλογές των \epsilon_1, \ldots, \epsilon_n τ.ώ. |x|^2 \geq n και |x|^2 \leq n. Παίρνουμε τις ρίζες και αφού τα μήκη είναι \geq 0, η απόδειξη ολοκληρώθηκε.

    Μου αρέσει!

    Σχόλιο από Charalampos Tsourakakis — Ιουλίου 11, 2010 @ 6:03 μμ

  9. Πολύ σωστά, αυτή (η πιθανοθεωρητική) είναι η πιο απλή λύση. Δεν γνωρίζω κάποια άλλη και είμαι περίεργος για το αν μπορεί να δοθεί λύση όπως την ξεκίνησε ο Μανούσος.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 11, 2010 @ 7:27 μμ

  10. Καλησπέρα και από εμένα,

    Αυτό το θέμα με την ανεξαρτησία που έθιξε ο Μπάμπης με προβλημάτισε λίγο…Γιατί ουσιαστικά λέει πως το ΑΤΓ (αυτό που όρισα πιο πάνω) μηδενίζεται…

    Αν πάρεις την έκφραση του $lateχ u$ στην αναλυτική της μορφή το ΑΤΓ δεν μπορεί να μηδενιστεί γιατί δύο «όμοια μονώνυμα» (αν μπορώ να τα χαρακτηρίσω έτσι…) θα έχουν πάντα τον ίδιο συντελεστή (ή 1 ή -1) οπότε δεν υπάρχει περίπτωση να εξαλειφθούν…

    Μου αρέσει!

    Σχόλιο από Μανούσος Κλάδος — Ιουλίου 11, 2010 @ 8:06 μμ

  11. Μανούσο,

    Αυτό που λέει η πιθανοθεωρητική μέθοδος που χρησιμοποίησε ο Μπάμπης είναι ότι ο δεύτερος προσθετέος στο τελευταίο υπόριζο της λύσης που πρότεινες μηδενίζεται αν αθροίσουμε ως προς όλες τις δυνατές αναθέσεις τιμών σε όλα τα \epsilon_j (υπάρχουν 2^n τέτοιες).

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 11, 2010 @ 10:39 μμ

  12. Ναι πολύ σωστά… εγώ ουσιαστικά αυτό που έλεγα ήταν το εξής: για κάποια \epsilon_{i} ο δεύτερος προσθετέος του τελευταίου υπόριζου θα έχει κάποιο πρόσημο…με τους αντίθετους θα έχει το αντίθετο πρόσημο…Οπότε περιφερόμαστε ανάλογα γύρω από το \sqrt(n) και μας βγαίνουν οι ανισότητες…Στην τετριμμένη περίπτωση έχουμε το ισότητα…. 🙂

    Μου αρέσει!

    Σχόλιο από Μανούσος Κλάδος — Ιουλίου 12, 2010 @ 12:19 πμ

  13. Όμως το να αλλάξεις τα πρόσημα όλων των \epsilon_j δεν αλλάζει το πρόσημο στην ποσότητα αυτή. Για την ακρίβεια την αφήνει απολύτως ίδια.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 12, 2010 @ 12:22 πμ

  14. Ναι έχει δίκιο…Πάλι δεν το διατύπωσα καλά και μάλλον θα χρειαστεί να γράψω κατεβατά σε latex…

    Λοιπόν

    Διορθώνω λίγο το τελευταίο υπόριζο:

    = \sqrt{n+2 \cdot \sum\limits_{i=1}^{n-1} \epsilon_{i}\displaystyle\sum\limits_{j=i+1,}^n \epsilon_{j}\displaystyle\sum\limits_{p=1}^d \left( u_{i}^p u_{j}^p \right)}   Οπότε:  latex \sum\limits_{i=1}^{n-1} \epsilon_{i}\displaystyle\sum\limits_{j=i+1}^n \epsilon_{j}\displaystyle\sum\limits_{p=1}^d \left( a_{i}^p a_{j}^p \right)= \epsilon{1} \left( \displaystyle\sum\limits_{j=2}^n \epsilon_{j}\displaystyle\sum\limits_{p=1}^d \left( a_{i}^p a_{j}^p \right) \right)+\cdots +\left(\epsilon_{n-2}\left( \epsilon_{n-1}\displaystyle\sum\limits_{p=1}^d \left( a_{n-2}^p a_{n-1}^p \right)+ \epsilon_{n}\displaystyle\sum\limits_{p=1}^d \left( a_{n-1}^p a_{n}^p \right)\right)\right)+\epsilon_{n-1}\left( \epsilon_{n}\displaystyle\sum\limits_{p=1}^d \left( a_{n-1}^p a_{n}^p \right)\right)$

    Άρα βάζουμε τυχαίο \epsilon_{n} και ανάλογα προσαρμόζεται ο \epsilon_{n-1} του τελευταίου προσθετέου… όμοια ο δεύτερος παράγοντας του προτελευταίου προσθετέου έχει στάνταρ πρόσημο οπότε προσαρμόζεται ο \epsilon_{n-2} κοκ… Αυτό που θέλω να πω είναι πως κουμαντάρουμε εμείς το πρόσημο αυτού του «τέρατος»…

    Ελπίζω το latex να βγει καλά….

    Μου αρέσει!

    Σχόλιο από Μανούσος Κλάδος — Ιουλίου 12, 2010 @ 12:57 πμ

  15. \sum\limits_{i=1}^{n-1} \epsilon_{i}\displaystyle\sum\limits_{j=i+1}^n \epsilon_{j}\displaystyle\sum\limits_{p=1}^d \left( a_{i}^p a_{j}^p \right)

    = \epsilon_{1} \left( \displaystyle\sum\limits_{j=2}^n \epsilon_{j}\displaystyle\sum\limits_{p=1}^d \left( a_{i}^p a_{j}^p \right) \right)+\cdots +\left(\epsilon_{n-2}\left( \epsilon_{n-1}\displaystyle\sum\limits_{p=1}^d \left( a_{n-2}^p a_{n-1}^p \right)+ \epsilon_{n}\displaystyle\sum\limits_{p=1}^d \left( a_{n-1}^p a_{n}^p \right)\right)\right)+\epsilon_{n-1}\left( \epsilon_{n}\displaystyle\sum\limits_{p=1}^d \left( a_{n-1}^p a_{n}^p \right)\right)

    Μου αρέσει!

    Σχόλιο από Μανούσος Κλάδος — Ιουλίου 12, 2010 @ 12:57 πμ

  16. Μανούσο,

    Πολύ σωστά.

    Έχεις ουσιαστικά να κάνεις με ένα άθροισμα της μορφής S=\sum_{i=1}^n \sum_{j\neq i} A_{ij} \epsilon_i \epsilon_j το οποίο γράφεις σε «τριγωνική» μορφή ως εξής

    S = \sum_{i=1}^n \sum_{j=i+1}^n (A_{ij} + A_{ji}) \epsilon_i \epsilon_j

    και κατόπιν καθορίζεις τα πρόσημα με τον τρόπο που λες παραπάνω.

    Πολύ ωραία.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 12, 2010 @ 2:32 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Blog στο WordPress.com.

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