Ορίζουσες από διαγωνισμούς

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

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

Ορίζουσες από διαγωνισμούς

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Απρ 01, 2011 5:38 pm

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

Putnam 1969/A2: Να υπολογιστεί η ορίζουσα του n \times n πίνακα A με A_{ij} = |i-j|.

\checkmark Putnam 1992/B5: Να υπολογιστεί η ορίζουσα του (n-1) \times (n-1) πίνακα A με A_{ij} = \begin{cases} 1 & i \neq j \\ i+2 & i = j\end{cases}.

\checkmark Putnam 1995/B3: Σε κάθε αριθμό m με n^2 δεκαδικά ψηφία αντιστοιχούμε τον n \times n πίνακα A_n που παράγεται από τον m γράφοντας τα ψηφία του m στα κελιά του A από αριστερά προς τα δεξιά και από πάνω προς τα κάτω. Π.χ. A_{1234} = \begin{pmatrix} 1 & 2 \\ 3 & 4\end{pmatrix}. Να υπολογιστεί το \sum_{m}|A_m| όπου το m διατρέχει όλους τους αριθμούς με ακριβώς n^2 δεκαδικά ψηφία. (Το πρώτο ψηφίο υποχρεωτικά πρέπει να είναι διάφορο του μηδενός.)

\checkmark Putnam 1999/B5: Έστω ακέραιος n \geqslant 3. Να υπολογιστεί η ορίζουσα του πίνακα I + A όπου I ο n \times n ταυτοτικός πίνακας και A ο n \times n πίνακας με A_{ij} = \cos(2\pi(i+j)/n).

\checkmark Putnam 2009/A3: Να υπολογιστεί η ορίζουσα του n \times n πίνακα A με A_{ij} = \cos((i-1)n + j).

IMC 1996/A1: Έστω a,d \in \mathbb{R}. Να υπολογιστεί η ορίζουσα του (n+1) \times (n+1) πίνακα A με A_{ij} = a + |i-j|d.

\checkmark IMC 2002/B1:. Να υπολογιστεί η ορίζουσα του n \times n πίνακα A με A_{ij} = \begin{cases} (-1)^{|i-j|} & i \neq j \\ 2 & i = j\end{cases}.

\checkmark IMC 2007/B4:. Έστω n > 1 περιττός ακέραιος. Να υπολογιστεί η ορίζουσα του n \times n πίνακα A με A_{ij} = \begin{cases} 1 & i - j  = \pm 2 \bmod n \\ 2 & i = j \\ 0 & i - j \neq 0,\pm 2 \bmod n\end{cases}.


Άβαταρ μέλους
Nick1990
Δημοσιεύσεις: 659
Εγγραφή: Παρ Ιαν 23, 2009 3:15 pm
Τοποθεσία: Peking University, Πεκίνο

Re: Ορίζουσες από διαγωνισμούς

#2

Μη αναγνωσμένη δημοσίευση από Nick1990 » Κυρ Απρ 03, 2011 1:02 pm

Demetres έγραψε: Putnam 1999/B5: Έστω ακέραιος n \geqslant 3. Να υπολογιστεί η ορίζουσα του πίνακα I + A όπου I ο n \times n ταυτοτικός πίνακας και A ο n \times n πίνακας με A_{ij} = \cos(2\pi(i+j)/n).

Putnam 2009/A3: Να υπολογιστεί η ορίζουσα του n \times n πίνακα A με A_{ij} = \cos((i-1)n + j).

Για το B5 του Putnam 1999:
Αν γράψουμε \cos(2\pi(k+j)/n) = \frac{1}{2}(e^{2\pi(k+j)/ni} + e^{-2\pi(k+j)/ni}) τότε βλέπουμε ότι
A = B + C όπου B,C είναι μιγαδικοί πίνακες με rank(B)=rank(C)=1 και με τον B να είναι ο συζηγής του C.
Άρα rank(A) = rank(B + C) \leq rank(B) + rank(C) = 1 + 1 = 2. Άρα ο A έχει το 0 ιδιοτιμή σε πολλαπλότητα τουλάχιστον n-2, και το χαρακτηρηστικό πολυώνυμο αυτού θα έχει τη μορφή X(x) = x^{n-2}(x-a)(x-b).

Έχουμε τώρα:
tr(A) = \sum_{m=1}^{n}{\cos(\frac{4\pi m}{n})} = \frac{1}{2}\sum_{m=1}^{n}{(e^{4\pi/ni})^m + (e^{-4\pi/ni})^m} = 0 διότι για n \geq 3 το e^{4\pi/ni} είναι μη τετριμένη n-ωστή ρίζα του 1.

tr(A^2) = \sum_{k,j=1}^{n}{{\cos(2\pi(k+j)/n)}^2} = \frac{1}{4}\sum_{k,j=1}^{n}{e^{4\pi(k+j)/ni} + 2 + e^{-4\pi(k+j)/ni}} = \frac{n^2}{2} + \frac{1}{4}((\sum_{m=1}^{n}{e^{4\pi m/ni}})^2 + (\sum_{m=1}^{n}{e^{-4\pi m/ni}})^2) = \frac{n^2}{2} + 0 + 0 = \frac{n^2}{2}

Άρα ο A έχει δύο αντίθετες ιδιοτιμές a,-a ώστε 2a^2 = \frac{n^2}{2} \Rightarrow a = \frac{n}{2}
Έτσι X(x) = x^{n-2}(x - \frac{n}{2})(x + \frac{n}{2}).
Η ζητούμενη ορίζουσα είναι (-1)^nX(-1) = (-1)^n(-1)^{n-2}(-1 - \frac{n}{2})(-1 + \frac{n}{2}) = (-1)^{2n - 2}(1 - \frac{n^2}{4}) = 1 - \frac{n^2}{4}



Το πρόβλημα του Putnam 2009 είναι πιο εύκολο, με τον ίδιο τρόπο δείχνουμε ότι rank(A) \leq 2 και έτσι η ορίζουσα είναι 0 για n \geq 3

Ελπίζω να μη χάνω κάτι...


Κολλιοπουλος Νικος.
Μεταδιδακτορικός ερευνητής.
Ερευνητικά ενδιαφέροντα: Στοχαστικές ΜΔΕ, ασυμπτωτική ανάλυση στοχαστικών συστημάτων, εφαρμογές αυτών στα χρηματοοικονομικά και στη διαχείριση ρίσκων.
Άβαταρ μέλους
Nick1990
Δημοσιεύσεις: 659
Εγγραφή: Παρ Ιαν 23, 2009 3:15 pm
Τοποθεσία: Peking University, Πεκίνο

Re: Ορίζουσες από διαγωνισμούς

#3

Μη αναγνωσμένη δημοσίευση από Nick1990 » Κυρ Απρ 03, 2011 7:45 pm

Βάζω κάποιες απαντήσεις που έχω στα υπόλοιπα προβλήματα:


Για το IMC2002/B1, το τρικ με τον βαθμό και το χαρακτηρηστικό πολυώνυμο δουλεύει επίσης, συγκεκριμένα:
βλέπουμε ότι ο πίνακας ισούται με I + A, όπου ο A έχει εναλλάξ -1 και 1 σε κάθε γραμμή, ενώ έχει άσσους στη διαγώνιο. Προφανώς είναι rank(A)=1 αφού κάθε γραμμή είναι μια άλλη επι 1 η -1, ενώ δεν υπάρχει μηδενική γραμμή, και ακόμα tr(A) = n, άρα X_{A}(x) = x^{n-1}(x - n) και η ζητούμενη ορίζουσα είναι (-1)^nX_{A}(-1) = (-1)^{n + n - 1}(-1 - n) = (-1)^{2n}(n+1) = n+1


Στο 2ο και στο 6ο που είναι γενίκευση του πρώτου νομίζω πως έχω λύσεις, αλλά για την ώρα δεν τις γράφω καθώς είναι μόνο γραμμοπράξεις - αναπτύγματα ως προς συγκεκριμένες γραμμές και επίλυση αναδρομικών, τα αποτελέσματα που βρήσκω είναι:
(-2d)^{n-1}a + (n-1)2^{n-2}(-1)^{n-1}d^n για το 6ο (για nxn πίνακα), \frac{n!}{2}(3n+5) για το 2ο (ξανά για nxn πίνακα)
.
Πείτε μου αν είναι σωστά και αν είναι, τότε όταν βρω χρόνο θα βάλω τις λύσεις που έχω βρει.

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


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

Re: Ορίζουσες από διαγωνισμούς

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Απρ 03, 2011 10:49 pm

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


Ilias_Zad
Δημοσιεύσεις: 418
Εγγραφή: Δευ Ιαν 26, 2009 11:44 pm

Re: Ορίζουσες από διαγωνισμούς

#5

Μη αναγνωσμένη δημοσίευση από Ilias_Zad » Σάβ Απρ 09, 2011 8:30 pm

Για αυτά που έμειναν δίνω 2 λύσεις μου:

---
Putnam 1995 B3

Για n \geq 3 κάθε πίνακας μπορεί να ζευγαρωθεί με έναν άλλον που έχει εναλλαγμένες τις 2 τελευταίες στήλες του. Τότε το άθροισμα των οριζουσών αυτών των δύο είναι μηδέν άρα και το συνολικό επίσης μηδέν.
Για n=1 , 45.
Για n=2 με παρόμοιο επιχειρημα με το πρώτο αρκεί να ασχοληθούμε με τους κάτω τριγωνικούς ( ομαδοποίηση ανά 2 δηλαδή αν η δεύτερη στήλη δεν έχει μηδενικό πάνω) που δίνουν εύκολα ότι το αποτέλεσμα είναι 10 επί 45^2.
-----
ΙΜC 2007 Β4
Έστω C_k ο πίνακας της μετάθεσης p_k, τέτοια ώστε p_k(i)=i+k (modn).
Tότε ζητάμε την det( C_{-2}+C_2+2I)=det((C_{-1}+C_1))^2=det(C_{2}+I)^2. Όμως η τελευταία έχει μη μηδενικα τα γινόμενα των a_{it(i)} για μετάθεση t είτε ταυτοτική είτε την p_2 που είναι κυκλος μήκους n επειδή n περιττός. Συνεπώς αφού και στις 2 περιπτώσεις περιπτώσεις έχουμε άρτιο πλήθος αντιστροφών , έπεται ότι det(C_{2}+I)=2 και το ζητούμενο αποτέλεσμα είναι ίσο με 4 .


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

Re: Ορίζουσες από διαγωνισμούς

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιούλ 15, 2011 12:23 am

Επαναφορά.

Έχει μείνει άλυτη η Putnam 1992/B5. (Νίκο η απάντηση στο hide είναι λανθασμένη.) Επίσης έχει δοθεί σωστή απάντηση από τον Νίκο για το IMC 1996/A1 (το οποίο γενικεύει το Putnam 1969/A2) αλλά δεν έχουμε ακόμη αποδείξεις.


dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1405
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Ορίζουσες από διαγωνισμούς

#7

Μη αναγνωσμένη δημοσίευση από dement » Παρ Ιούλ 15, 2011 3:29 pm

Για το Putnam 1992/Β5 :

Εστω d_n η ορίζουσα του αντίστοιχου (n-1) \times (n-1) πίνακα. Γράφουμε την (n-1)-οστή στήλη ως

\left( 
\begin{array}{c} 
1 \\ 
1 \\ 
... \\ 
n+1 
\end{array} \right) = \left( 
\begin{array}{c} 
0 \\ 
0 \\ 
... \\ 
n 
\end{array} \right) + \left( 
\begin{array}{c} 
1 \\ 
1 \\ 
... \\ 
1 
\end{array} \right)

και έτσι έχουμε τον αναδρομικό τύπο d_n = n d_{n-1} + (n-1)! (για το δεύτερο όρο αφαιρούμε τη (n-1)-οστή στήλη της ορίζουσας από όλες τις υπόλοιπες) με d_2 = 3.

Τώρα μπορούμε να αποδείξουμε επαγωγικά ότι d_n = n! \ H_n (όπου H_n ο n-οστός όρος της αρμονικής ακολουθίας).


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Απάντηση

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

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

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