SEEMOUS 2019 / 2

Συντονιστής: Demetres

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2345
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

SEEMOUS 2019 / 2

#1

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Δευ Μαρ 18, 2019 10:19 am

Δίνονται A_{i},i=1,2,...,k
n\times n πίνακες με στοιχεία πραγματικούς.

Να δειχθεί ότι υπάρχει επιλογή από
\varepsilon _{i},i=1,2,... ,k
με
\varepsilon _{i}\in \left \{ 1,-1 \right \}
ώστε
tr(\sum_{i=1}^{k}\varepsilon _{i}A_{i})^{2}\geq \sum_{i=1}^{k}trA^{2}_{i}



Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8097
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: SEEMOUS 2019 / 2

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Μαρ 19, 2019 2:18 pm

Έχουμε:

\displaystyle \mathrm{tr}\left(\sum_{i=1}^k \varepsilon_i A_i \right)^2 = \sum_{i=1}^k \sum_{j=1}^k \mathrm{tr} (\varepsilon_i\varepsilon_j A_iA_j)

Άρα:

\displaystyle \sum_{\mathbf{v}}\mathrm{tr}\left(\sum_{i=1}^k \varepsilon_i A_i \right)^2 = 2^n \sum_{i=1}^n\mathrm{tr}(A_i)^2

όπου το άθροισμα είναι υπέρ όλων των 2^n διανυσμάτων \mathbf{v} = (\varepsilon_1,\ldots,\varepsilon_n). Για κάθε i, οι συντελεστές \varepsilon_i\varepsilon_i είναι πάντα ίσοι με 1, ενώ για κάθε i \neq j οι συντελεστές \varepsilon_i\varepsilon_j στα μισά διανύσματα είναι ίσοι με 1 και στα άλλα μισά ίσοι με -1.

Επιλέγοντας το \mathbf{v} ομοιόμορφα στην τύχη έχουμε ότι \displaystyle \mathbb{E}\left[ \mathrm{tr}\left(\sum_{i=1}^k \varepsilon_i A_i \right)^2\right] = \sum_{i=1}^n\mathrm{tr}(A_i)^2 οπότε υπάρχει και επιλογή του \mathbf{v} ώστε:

\displaystyle  \mathrm{tr}\left(\sum_{i=1}^k \varepsilon_i A_i \right)^2 \geqslant \sum_{i=1}^n\mathrm{tr}(A_i)^2


ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 2345
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

Re: SEEMOUS 2019 / 2

#3

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Τρί Μαρ 19, 2019 9:14 pm

Θα γράψω μία λύση που στην ουσία είναι η ίδια με του Δημήτρη.

Χρειαζόμαστε τις συναρτήσεις του Rademacher.
https://en.wikipedia.org/wiki/Rademacher_system
https://calculus7.org/tag/rademacher-functions/

Αν τις συμβολίσουμε με \varepsilon_i (t) i=1,2,....
τότε
\displaystyle \int_{0}^{1}\varepsilon _{i}(t)\varepsilon _{j}(t)dt=\delta _{ij}
οπου
\delta _{ii}=1,\delta _{ij}=0 fori\neq j



Εχουμε για t\in [0,1]


\displaystyle \mathrm{tr}\left(\sum_{i=1}^k \varepsilon_i (t)A_i \right)^2 = \sum_{i=1}^k \sum_{j=1}^k \mathrm{tr} (\varepsilon_i(t)\varepsilon_j(t) A_iA_j)

Αρα και

\displaystyle \mathrm{tr}\left(\sum_{i=1}^k \varepsilon_i (t)A_i \right)^2 = \sum_{i=1}^k \sum_{j=1}^k(\varepsilon_i(t)\varepsilon_j(t) \mathrm{tr}  A_iA_j)

ολοκληρώνοντας πάνω στο [0,1] παίρνουμε

\displaystyle\int_{0}^{1} \mathrm{tr}\left(\sum_{i=1}^k \varepsilon_i (t)A_i \right)^2dt = \sum_{i=1}^k \mathrm{tr} A^{2}_i

Συμπέραινουμε ότι υπάρχει t_{0}\in [0,1]
ώστε

\displaystyle \mathrm{tr}\left(\sum_{i=1}^k \varepsilon_i (t_{0})A_i \right)^{2}\geq \int_{0}^{1} \mathrm{tr}\left(\sum_{i=1}^k \varepsilon_i (t)A_i \right)^2dt = \sum_{i=1}^k \mathrm{tr} A^{2}_i

που δίνει το ζητούμενο.


sot arm
Δημοσιεύσεις: 162
Εγγραφή: Τρί Μάιος 03, 2016 5:25 pm

Re: SEEMOUS 2019 / 2

#4

Μη αναγνωσμένη δημοσίευση από sot arm » Τετ Μαρ 20, 2019 10:27 am

Μία ακόμα, θα χρησιμοποιήσουμε επαγωγή, για n=2 γράφεται:

\displaystyle{2\epsilon_{1}\epsilon_{2}Tr(A_{1}A_{2})\geq 0  }

και διαλέγουμε τα 2\epsilon_{1},\epsilon_{2} ώστε το γινόμενο να έχει το ίδιο πρόσημο με το Tr(A_{1}A_{2}).

Έπεται το ζητούμενο άμεσα από την επαγωγική υπόθεση και την περίπτωση για n=2 θέτοντας:
\displaystyle{A=\sum_{i=1}^{n}\epsilon_{i}A_{i}} και B=A_{n+1}


Αρμενιάκος Σωτήρης
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8097
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: SEEMOUS 2019 / 2

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Μαρ 20, 2019 10:49 am

Πολύ ωραία Σωτήρη. Επί τη ευκαιρία, συγχαρητήρια για το αργυρό μετάλλιο στο διαγωνισμό. Συγχαρητήρια επίσης και στους simantiris j και jason.prod για τα χρυσά καθώς και στα άλλα μέλη των ελληνικών αποστολών για τα υπόλοιπα μετάλλια.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης