SEEMOUS 2019 / 2

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #1

Δίνονται $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}$

#2

Έχουμε:

$\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)$ . Για κάθε

, οι συντελεστές $\varepsilon_i\varepsilon_i$ είναι πάντα ίσοι με

, ενώ για κάθε $i \neq j$ οι συντελεστές $\varepsilon_i\varepsilon_j$ στα μισά διανύσματα είναι ίσοι με

και στα άλλα μισά ίσοι με

.

Επιλέγοντας το $\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$

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #3

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

Χρειαζόμαστε τις συναρτήσεις του 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 · #4

Μία ακόμα, θα χρησιμοποιήσουμε επαγωγή, για 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}$

#5

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

SEEMOUS 2019 / 2

SEEMOUS 2019 / 2

Re: SEEMOUS 2019 / 2

Re: SEEMOUS 2019 / 2

Re: SEEMOUS 2019 / 2

Re: SEEMOUS 2019 / 2

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