Γραμμική Άλγεβρα

lemonidas · #1

Μια ωραία γραμμική άλγεβρα δικής μου κατασκευής:

Έστω $A \in R^{nxn}$ για τον οποίο ισχύει A+A^T = 2I

και $\sum}_{i \not= j} |a_{ij}|<1$ (άθροισμα πάνω στα μη διαγώνια στοιχεία κάθε γραμμής) ισχύει η ανισότητα:
$1\leq det(A) < (\sqrt{2})^n$

Εdit 1: typo
Edit 2: Νέο φράγμα

#2

Lemonida, γειά χαρά!
Κάτι ίσως έχει ξεχαστεί απο εσένα στην εκφώνηση ή εγώ δεν καταλαβαίνω (το πιο πιθανό!!).
Παίρνω π.χ τον

$\displaystyle{ A = \left[ {\begin{array}{*{20}c} 1 & 2 \\ { - 2} & 1 \\ \end{array}} \right] }$

Με det(A)=5>2^2.

#3

Νομίζω ότι έχει γίνει κάποιο τυπογραφικό,

$\sum}_{i \not= j} |a_{ij}|\neq0$

Νίκος

lemonidas · #4

Συγνώμη για το τυπογραφικό. Είναι για άθροισμα απολύτων μικρότερων του 1...

Nick1990 · #5

Βαζω μια λυση για το αριστερο σκελος:

Ισοδυναμα:

$A = I + \frac{A - A^{T}}{2} \Leftrightarrow A - xI = B - (x - 1)I \Leftrightarrow X_{A}(x) = X_{B}(x-1)$ , οπου ο $B = \frac{A - A^{T}}{2}$ ειναι αντισυμμετρικος και επομενως διαγωνοποιειται με ορθομοναδιαιο και εχει μονο φανταστικες ιδιοτιμες. Αρα απο εδω εχουμε οτι για καθε ιδιοτιμη

του

ειναι

. Οποτε η οριζουσα του

ειναι $\geq 1$ διοτι ειναι ενα γινομενο απο μοναδες και απο πραγματικους αριθμους της μορφης (1 + (Im(z))^2) > 1

, οπου

ειναι τα στοιχεια του συνολου των ιδιοτιμων του

το οποιο περιεχει και τους συζιγεις των

.

Για το δεξι σκελος αρκει να δειχτει οτι οι φανταστικες ιδιοτιμες του

εχουν μετρα μικροτερα η ισα του 1. Αυτο γινεται με μια ιδεα την οποια μου ειπε ο κατασκευαστης του προβληματος την οποια βαζω σε hide:

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

#6

Να πω ότι η δεύτερη ανισότητα βγαίνει και χωρίς την υπόθεση ότι A + A^T = 2I

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

Λίγα λόγια για την απόδειξη:

To permanent ενός $n \times n$ πίνακα $A = (a_{ij})$ (δεν έχω ιδέα πως μεταφράζεται στα ελληνικά) ορίζεται το $\displaystyle{ per(A) = \sum_{\pi \in S_n} \prod_{i=1}^n a_{i \pi(i)} }$ . Η διαφορά δηλαδή με τον αντίστοιχο τύπο για την ορίζουσα είναι ότι παίρνουμε πάντα + και όχι κάποτε + και κάποτε -.

Το permanent δεν έχει την γεωμετρική ερμηνεία της ορίζουσας (όγκος παραλληλεπιπέδου) αλλά ιδίως για πίνακες με τιμές 0 και 1 έχει συνδιαστική ερμηνεία καθώς χρησιμοποιείται για να μετρήσει διάφορες ποσότητες.

Η εικασία του Minc λέει ότι αν

είναι ένας πίνακας με τιμές 0 και 1 και αν τα αθροίσματα των σειρών του

είναι $r_1,r_2,\ldots,r_n$ (δηλαδή στην σειρά

έχουμε

άσσους και n-r_i

μηδενικά), τότε $\displaystyle{per(A) \leqslant \prod_{i=1}^n (r_i!)^{1/r_i}}$

Η εικασία αποδείχθηκε από τον Bregman. Στην βιβλιογραφία το θεώρημα είναι γνωστό είτε ως εικασία του Minc, είτε ως θεώρημα του Bregman.

Υπάρχουν αρκετές περιπτώσεις ισότητας. Για παράδειγμα αν $r_1 = \cdots = r_n = r$ και r|n

τότε ισχύει η ισότητα για τον πίνακα

που κατασκευάζεται τοποθετώντας στην "διαγώνιό" του n/r

πίνακες $r \times r$ που έχουν παντού άσσους

Αυτό γενικεύτηκε από τον Soules ως εξής:

Αν

είναι ένας πίνακας όπου όλα τα στοιχεία του ανήκουν στο [0,1]

και τα αθροίσματα των σειρών του

είναι $r_1,r_2,\ldots,r_n$ τότε $\displaystyle{per(A) \leqslant \prod_{i=1}^n \Gamma(r_i + 1)^{1/r_i}}$

('Οπου $\Gamma(z)$ είναι η συνάρτηση $\Gamma$ . Για αυτήν την συνάρτηση ισχύει $\Gamma(n+1) = n!$ )

Στην περίπτωσή μας, δουλεύοντας με τον πίνακα

όπου $c_{ij} = |a_{ij}|$ έχουμε $\det(A) \leqslant per(C) < \prod_{i=1}^n \Gamma(3)^{1/2} = (\sqrt{2})^n$ .

---------------------------
Υπάρχει ακόμη ένα σημαντικό θεώρημα που χρησιμοποιείται συνήθως σε παρόμοιες περιπτώσεις: Η εικασία του Van der Waerden λέει ότι αν ένας $n \times n$ πίνακας έχει μη αρνητικές τιμές και τα αθροίσματα κάθε σειράς και κάθε στήλης ισούνται με 1, τότε $\displaystyle{per(A) \geqslant \frac{n!}{n^n}}$ .

Η εικασία αποδείχθηκε από τον Falikman και από τον Egorychev (ανεξάρτητα). Είναι γνωστό μάλιστα ότι η ισότητα ισχύει αν και μόνο αν κάθε τιμή του πίνακα ισούται με 1/n

lemonidas · #7

Γενικά εγώ σχεδόν την ίδια λύση με του νίκου είχα στο μυαλό μου για το πρώτο μέρος, ενώ το δεύτερο (το οποίο κι εγώ δεν χρειάζομαι την συνθήκη ολόκληρη αλλά τους άσσους στη διαγώνιο) προκύπτει άμεσα με χρήση ενός θεωρήματος (Gershgorin's circle theorem), το οποίο για όποιον ενδιαφέρεται βρίσκεται εδώ. Αυτά με τα per(A) του Δημήτρη μου φαίνονται λίγο overkill

, αν και κάτι μου θυμίζουν από το κεφάλαιο ανισοτήτων του Lax...

#8

Λεωνίδα, εννοείται πως η λύση μου είναι overkill. Δεν βλέπω όμως πως αποφεύγεις να χρησιμοποιήσεις ότι A = I + B

όπου

αντισυμμετρικός. Η υπόδειξη δείχνει ότι οι ιδιοτιμές του

έχουν μέτρο το πολύ 1 αν όμως δεν ξέρουμε πως είναι αντισυμμετρικός δεν βλέπω πως να το συνεχίσω.

Για πες μας και για το κεφάλαιο ανισοτήτων του Lax. Είναι από κάποιο βιβλίο;

lemonidas · #9

Εννοώ ότι και εγώ για το δεύτερο κομμάτι χρειάζομαι μόνο την υπόθεση για τα μη διαγώνια στοιχεία + το ότι υπάρχουν άσσοι στη διαγώνιο. Για Το κάτω φράγμα χρειάζομαι το Α=Β+Ι.

Όσο για το lax, είναι ένα βιβλίο του Lax (Linear Algebra and its applications νομίζω λέγεται) το οποίο έχει ένα κεφάλαιο αφιερωμένο σε ανισότητες πινάκων. Αυτή που ανέφερες κάτι μου θυμίζει από όταν το χα διαβάσει αλλά δεν είμαι σπίτι για να δω σίγουρα...

#10

Λεωνίδα ευχαριστώ για το βιβλίο. Ήξερα ότι ο Lax είναι από τους κορυφαίους μαθηματικούς. Από ότι φαίνεται είναι και εξαιρετικός συγγραφέας.

Μπορείς να βάλεις την λύση σου για την δεύτερη ανισότητα;

lemonidas · #11

Είναι όντως εξαιρετικό βιβλίο. Μου το είχε προτείνει ο κ. Λουλάκης στο Seemous στην Κύπρο.

Για την άσκηση:

Γνωρίζουμε ότι ο Α έχει στη διαγώνιο όλα τα στοιχεία του άσσους. Οπότε σπάμε τον Α σαν A=I + F όπου ο F έχει όλα τα διαγώνια στοιχεία 0. Τώρα μπορούμε να εφαρμόσουμε το θεώρημα του Gershgorin το οποίο θα μας δώσει ότι όλες οι ιδιοτιμές μας ανήκουν σε κύκλους κέντρου (1,0) και ακτίνας το πολύ 1. (λόγω της δοσμένης συνθήκης για τα μη διαγώνια στοιχεία). Όμως ο F είναι αντισυμμετρικός το οποίο μας δίνει ότι οι ιδιοτιμές του Α έχουν πραγματικο μέρος 1 και εμφανίζονται σε συζυγή ζεύγη. Η ορίζουσα του Α θα ισούται:

$det(A) = \Pi (1 \pm j \lambda_i) = | \Pi (1+j \lambda_i) |$ Όμως η μέγιστη τιμή κάθε τέτοιου μέτρου είναι $\sqrt {2}$ . (Τομή της x=1 με τον κύκλο (x-1)^2+y^2=1

). Άρα η μέγιστη τιμή της ορίζουσας είναι $\sqrt {2}^n$

Γραμμική Άλγεβρα

Γραμμική Άλγεβρα

Re: Γραμμική Άλγεβρα

Re: Γραμμική Άλγεβρα

Re: Γραμμική Άλγεβρα

Re: Γραμμική Άλγεβρα

Re: Γραμμική Άλγεβρα

Re: Γραμμική Άλγεβρα

Re: Γραμμική Άλγεβρα

Re: Γραμμική Άλγεβρα

Re: Γραμμική Άλγεβρα

Re: Γραμμική Άλγεβρα

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