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

Απρίλιος 18, 2013

Πόσοι ιδιάζοντες πίνακες;

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

Ένας γραμμικός υπόχωρος του χώρου των n\times n πραγματικών πινάκων περιέχει μόνο ιδιάζοντες (μη αντιστρέψιμους) πίνακες.

Ποια είναι η μέγιστη διάσταση που μπορεί να έχει;

Advertisements

9 Σχόλια »

  1. Ο χώρος που παράγεται από τους n^2-n το πλήθος n \times n πίνακες A_{ij} για i=1, \dots , n, j=1, \dots , n-1 που έχουν μονάδα στη θέση (i,j) και μηδέν αλλού περιέχει μόνο ιδιάζοντες πίνακες.

    Έστω n^2-n+1 γραμμικώς ανεξάρτητοι πίνακες. Τότε με τους κατάλληλους γραμμικούς μετασχηματισμούς μπορούμε να τους μετατρέψουμε σε n^2-n+1 διαφορετικούς πίνακες B_k, τέτοιους ώστε:

    α. Υπάρχουν n-1 ζέυγη θέσεων (i,j) τέτοια ώστε για κανέναν από τους πίνακες B_k να μην γνωρίζουμε τα στοιχεία στις θέσεις αυτές, και

    β. Πέραν των θέσεων αυτών, κάθε πίνακας έχει ακριβώς μία μοναδα και τα υπόλοιπα στοιχεία είναι μηδέν.

    Οι πίνακες B_k παράγουν τον ίδιο γραμμικό υπόχωρο με τους αρχικούς πίνακες.

    Τώρα μπορούμε να βρούμε μια γραμμή (αρχή περιστεροφωλιάς) τέτοια ώστε οι B_k να μην περιέχουν καμία από τις «ιδιάζουσες θέσεις» από το (α) kαι μία στήλη ώστε να υπάρχει τουλάχιστον μία τέτοια θέση. Θέτουμε C_1 να είναι ακριβώς ο πίνακας από τους B_k που έχει τη μονάδα (όπως περιγράφηκε στο (β)) στη θέση που τέμνονται η γραμμή και η στήλη.

    Στη συνέχεια, βρίσκουμε άλλη μία γραμμή και μία στήλη, τέτοιες ώστε, αν αφαιρούσαμε τη γραμμή και τη στήλη που μόλις χρησιμοποιήσαμε, η γραμμή δεν περιέχει κάποια ιδιάζουσα θέση, ενώ η στήλη έχει τουλάχιστον μία. Βρίσκουμε έτσι έναν πίνακα C_2. Αυτό γίνεται, μιας και ο πίνακας που προκύπτει αν αφαιρέσουμε τη γραμμή και τη στήλη του πρώτου βήματος είναι n-1 \times n-1 και έχει το πολύ n-2 από τις ιδιάζουσες θέσεις.

    Συνεχίζοντας, θα βρούμε πίνακες C_3, \dots C_r , με r<n, μέχρι να εξαλειφθούν οι ιδιάζουσες θέσεις. Ο πίνακας C_1+ \dots +C_r έχει διακρίνουσα 1 ή -1, άρα είναι ανριστρέψιμος.

    Άρα, η μέγιστη διάσταση είναι n^2-n.

    Μου αρέσει!

    Σχόλιο από alexgrosdos — Ιουνίου 12, 2013 @ 12:28 μμ

  2. OK, στην πρώτη γραμμή αυτό που θες να πείς ότι ο γραμμικός χώρος των πινάκων με μηδενική την τελευταία στήλη αποτελείται από ιδιάζοντες πίνακες και έχει διάσταση n^2-n, όσα και τα στοιχεία του πίνακα εκτός της τελευταίας στήλης. Αυτό φυσικά είναι σωστό.

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

    Μου αρέσει!

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

  3. Έχετε δίκιο, έχω παραλείψει να εξηγήσω πολλά πράγματα από την απόδειξη. Εξηγώ λοιπόν.

    Στο πρώτο βήμα παίρνουμε έναν χώρο που περιέχει n^2-n+1 γραμμικώς ανεξάρτητους πίνακες, αρα διάστασης τουλάχιστον n^2-n+1 . Έστω A_k οι πίνακες. Παίρνουμε μια ολική διάταξη των (i,j) , ας πούμε λεξικογραφικά, και κάνουμε την παρακάτω διαδικάσία:

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

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

    Συνεχίζουμε έτσι μέχρι το βήμα n^2-n+1+s, όπου s το πλήθος των θέσεων που συναντήσαμε μέχρι τώρα όπου όλοι οι πινακες έχουν μηδέν. Ετσι φτάνουμε στους πίνακες B_k οι οποίοι πληρούν τις συνθήκες (α) και (β). Τα n-1 ζεύγη του (α) προκύπτουν είτε από θέσεις όπου όλοι οι πίνακες έχουν 0, είτε από θέσεις που θα περισέψουν στο τέλος της διαδικασίας (αφού έχουμε λιγότερους πίνακες από ότι θέσεις). Από τη γραμμική ανεξαρτησία των πινάκων βλέπει κανείς ότι οι ιδιάζουσες θέσεις είναι n-1 το πλήθος.

    Το δεύτερο μέρος νομίζω ότι είναι πιο ξεκάθαρο. Η κεντρική ιδέα είναι ότι μπορούμε να επιλέξουμε κατάλληλα κάποιους από τους πίνακες $B_i$ και να τους αθροίσουμε, ώστε στον υπολογσμό της ορίζουσας να μην παίζουν ρόλο οι ιδιάζουσες θέσεις. Πρακτικά, παίρνουμε τον πρώτο πίνακα να έχει μονάδα μόνο σε μία θέση μιας γραμμής και σε αυτή τη θέση η στήλη έχει μια τουλάχιστον ιδιάζουσα θέση. Άρα αν αναπτύξουμε την ορίζουσα ως προς αυτή τη γραμμή, η ιδιάζουσα θέση αυτής της γραμμής δεν παίζει κανένα ρόλο, καθότι η ορίζουσα πλέον ισούται με την ορίζουσα του minor από τον οποίο λείπει αυτή η γραμμή και η στήλη. Το υπόλοιπο συνεχίζει σχεδόν επαγωγικά.

    Αυτό που παρέλειψα είναι ότι αφού πάρουμε το άθροισμα C_1+ \dots +C_r, ίσως χρειαστεί να αθροίσουμε σε αυτούς μερικούς ακόμα από τους πίνακες B_k, ώστε η ορίζουσα να βγαίνει 1 ή -1.

    Μου αρέσει!

    Σχόλιο από alexgrosdos — Ιουνίου 13, 2013 @ 2:23 πμ

  4. Ελπίζω να έγινε πιο κατανοητή η απόδειξή μου. Απλά γράφω αρκετά αργά στον υπολογιστή, γι’αυτό παρέλειψα να γράψω μερικά πράγματα.

    Μου αρέσει!

    Σχόλιο από alexgrosdos — Ιουνίου 13, 2013 @ 2:27 πμ

  5. Πολύ ωραία.

    Μια μικρή απλούστευση που αποφεύγει τις ορίζουσες: από τη στιμή που έχεις βρει τους πίνακες B_k με τις ιδιότητες που περιγράφεις τότε υπάρχει μια ολόκληρη γραμμή (όποια γραμμή δεν περιέχει καμία «ιδιάζουσα» θέση, όπως τις έχεις ονομάσει) όπου κάποιος από τους B_k μηδενίζεται, άτοπο γιατί ο B_k έχει υποτεθεί αντιστρέψιμος.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 15, 2013 @ 2:14 πμ

  6. Από πού προκύπτει ότι υπάρχει B_k που να έχει υποτεθεί αντιστρέψιμος;

    Μου αρέσει!

    Σχόλιο από alexgrosdos — Ιουνίου 15, 2013 @ 11:16 πμ

  7. Από πουθενά. Αυτά παθαίνει κανείς όταν γράφει στις 2:14 πμ. Σκεφτόμουνα αντιστρέψιμο αντί για ιδιάζοντα. Γράψτε λάθος 😦

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 15, 2013 @ 11:21 πμ

  8. Κανένα πρόβλημα.

    Εϊχατε κατά νου κάποια πιο σύντομη λύση; (Επειδή τα πιο πολλά προβλήματα που βάζετε συνήθως απαιτούν μια ή δυο καλές ιδέες και όχι μακροσκελείς κατασκευαστικές αποδείξεις)

    Μου αρέσει!

    Σχόλιο από alexgrosdos — Ιουνίου 15, 2013 @ 10:26 μμ


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: