Σάββατο 25 Οκτωβρίου 2014

Tετραγωνικοί άσσοι

Έστω $A$ ένας οποιοσδήποτε πίνακας $\nu  \times  \nu $ για τον οποίον ισχύει πως κάθε του στοιχείο είναι είτε $+1$ , είτε $-1$.
Δείξτε ότι η ορίζουσα του $A$ διαιρείται με το $2^{ \nu -1}$.

11 σχόλια:

  1. Μια σκέψη, από τα λίγα που θυμάμαι, που δεν αποτελεί απόδειξη.

    Στην περίπτωση που ο πίνακας είναι full rank (D != 0), μετά το elimination, όταν πια ο πίνακας είναι σε echelon form, όλα τα στοιχεία της διαγωνίου θα είναι +-2 (εκτός από το στοιχείο [1,1] που θα είναι +-1). Και αυτό γιατί για την απαλοιφή των στοιχείων κατά το elimination πάντα θα αρκεί ο πολ/μος με +-1 μιας γραμμής και η προσθαφαίρεση από μια άλλη. Έτσι τα στοιχεία των γραμμών πλην της πρώτης θα αποτελούνται μόνο από 0 και +-2. Η ορίζουσα λοιπόν, που προκύπτει από το γινόμενο των στοιχείων της διαγωνίου, όχι μόνο θα διαιρείται με 2^(ν-1) αλλά θα ισούται και με +-2^(ν-1).


    Υ.Γ. Πώς γράφουμε LATEX εδώ; βάζοντας τους τύπους σε $ $ ;

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Latex γράφουμε απλώς με δολάριο μπροστά και στο τέλος
      Π.χ (όπου " βάλε δολάριο) στο "e^{ipi} +1=0" και θα βγει:
      $e^{ipi} +1=0$
      Aν πας κάτω δεξιά ,υπάρχει (σε κίτρινο φόντο) έτοιμη λατεξιέρα.

      Διαγραφή
  2. Όσον αφορά στο σχόλιό σου επί του θέματος είσαι ΣΧΕΔΟΝ ολόσωστος. (Το "Σχεδόν" όμως θέλει λίγη δουλειά... π.χ η τελευταία πρόταση δεν ισχύει. Π.χ στον πίνακα $2Χ2$ με όλα τα στοιχεία άσσους, η $det(A)=0$ . )

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Μα μιλάω μόνο για full rank. Αν δεν είναι θα υπάρχει μηδενικό στη διαγώνιο και θα είναι 0 η ορίζουσα.

      Διαγραφή
  3. Ηalb Wesen, για να συνεννοηθούμε ,και να μην μπλέκουμε και τους μη αγγλομαθείς ως προς την ορολογία φίλους, αν καταλαβαίνω καλά το σχόλιό σου ,αυτό που προτείνεις είναι το εξής:
    Αν προσθέσουμε την 1η σειρά του Α στις $ν-1$ υπόλοιπες σειρές,παίρνουμε έναν νέο πίνακα έστω Β. Σύμφωνα με γνωστή ιδιότητα ,ισχύει: $det(A)=det(B)$ . Eφόσον όλα τα στοιχεία του Α είναι +1 ή -1 ,o κάτω (lower submatrix) $(ν-1) Χ ν$ του Β θα περιέχει μόνο $0, 2 ,-2$ . Σωστά; Αν ναι, μέχρις εδώ όλα καλά. Διευκρίνισε αν θες πώς από αυτό το σημείο δείχνεις το ζητούμενο. Πώς δείχνεις δηλαδή ότι η $(2^{n-1)|det(B)$

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Αυτό που δεν εμφανίστηκε σωστά έγραφε:
      "Πώς δείχνεις δηλαδή ότι το $2^{n+1}$ διαιρεί την $det(B)$ ? "

      Διαγραφή
  4. Από ελληνικές ορολογίες δεν τα πάω καλά :-). Ο πίνακας σε echelon form σημαίνει, από τα όσα θυμάμαι ότι, μετά τις προσθαφαιρέσεις γραμμών και τις μεταθέσεις, έχει λάβει τη μορφή τριγωνικού άνω, με τους pivots στη διαγώνιο (οι οποίοι είναι +-1 στην πρώτη γραμμή και +-2 στις άλλες). Η ορίζουσα του τριγωνικού είναι το γινόμενο των διαγώνιων στοιχείων (pivots), δηλ +- 2^(ν-1), αν ο πίνακας είναι full rank, και 0 αν όχι (γιατί τότε κάποιος pivot θα είναι 0). Άρα σύμφωνα με αυτό το σκεπτικό η ορίζουσα διαιρείται με 2^(ν-1), αφού μπορεί μόνο να ισούται είτε με +- 2^(ν-1), είτε με 0. Όλα αυτά με την επιφύλαξη φυσικά να σφάλλω κάπου, μιας και δεν τα θυμάμαι πια πολύ καλά. Θα περιμένω με ενδιαφέρον να δω τη λύση.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. halb Wesen, όλα είναι εντάξει και σωστά όπως τα λες.
      Ωραία διαισθητική εξήγηση της Γκαουσιανής απαλοιφής (Gaussian elimination) αλλά ας δώσω (καμιά διαφορά ουσίας με τα δικά σου βέβαια) και μια πιο φορμαλιστική:
      Υπολογίζοντας λοιπόν -με ανάπτυγμα ως προς την 1η σειρά- την ορίζουσα του υποπίνακα Β, έχουμε:
      $det(B)= \sum_{j=1}^{n}{( -1)^{1+j} } B_{1j} . det( C_{1j})$
      όπου C(1j) είναι ο (ν-1) Χ (ν-1) υποπίνακας αφαιρουμένων της 1ης σειράς και της j στήλης.
      Αφού όλα τα στοιχεία του C είναι είτε +2 είτε -2 ,είτε 0 ,η ορίζουσα του C1j μπορεί να έχει μόνο τις τιμές :
      2^(ν-1) , -2^(ν-1) ή 0. Οπότε σύμφωνα με την παραπάνω σχέση για την ορίζουσα του Β, ισχύει το ζητούμενο.

      Διαγραφή
    2. Δεν τα είπα και τόσο σωστά. To λάθος που έχω κάνει είναι ότι δεν είναι απαραίτητο η ορίζουσα να ισούται είτε με +- 2^(ν-1) γιατί μπορεί να μην αρκεί μια μόνο προσθαφαίρεση γραμμής για τη δημιουργία pivot. Κάθε παραπανήσια όμως θα καταλήγει σε pivot πολ/σιο του 2.

      Κύριε Ριζόπουλε, δεν κατάλαβα μόνο το γιατί λέτε ότι όλα τα στοιχεία του C είναι είτε +2 είτε -2. Ο υποπίνακας δεν είναι το μέρος του αρχικού μετά την αφαίρεση μιας γραμμής και μιας στήλης;

      Διαγραφή
    3. Όχι. Όλα τα στοιχεία του C είναι {2, -2, ή 0}
      Ο C προκύπτει από διαγραφή της 1ης γραμμής του Β (που έχει +- άσσους) και της j στήλης . Ο Β όμως έχει προκύψει από πρόσθεση της 1ης γραμμής στις υπόλοιπες, άρα όλα τα στοιχεία του C είναι δυάρια (+ ή -) ή 0. Αν τα pivots (όπως σωστά έγραψες) είναι 2άρια η ορίζουσα είναι +- 2^(ν-1). Αν έχουμε 0 στη διαγώνιο η ορίζουσα είναι 0.

      Διαγραφή