Πολύτοπο Μπίρκοφ

Το πολυτόπιο Μπίρκοφ Bn (που ονομάζεται επίσης πολύτοπο ανάθεσης, πολύτοπο των διπλά στοχαστικών πινάκων ή πολυτόπιο τέλειας αντιστοίχισης του πλήρους διμερούς γραφήματος  $K_{n,n}$) είναι το κυρτό πολύτοπο στο R^N (όπου N = n²) του οποίου τα σημεία είναι οι διπλά στοχαστικοί πίνακες, δηλ, οι Πρότυπο:Nowrap πίνακες των οποίων οι εγγραφές είναι μη αρνητικοί πραγματικοί αριθμοί και των οποίων οι γραμμές και οι στήλες αθροίζουν το 1. Πήρε το όνομά του από τον Γκάρετ Μπίρκοφ.

Ιδιότητες

Κορυφές

Το πολύτοπο Μπίρκοφ έχει n! κορυφές, μία για κάθε μετάθεση σε n στοιχεία. Αυτό προκύπτει από το θεώρημα Μπίρκοφ-βον Νόιμαν, το οποίο δηλώνει ότι τα ακραία σημεία του πολυτόπου Μπίρκοφ είναι οι πίνακες μεταθέσεων, και επομένως ότι κάθε διπλά στοχαστικός πίνακας μπορεί να αναπαρασταθεί ως κυρτός συνδυασμός πινάκων μεταθέσεων, αυτό διατυπώθηκε σε μια εργασία του 1946 από τον Γκάρετ Μπίρκοφ, αλλά ισοδύναμα αποτελέσματα στις γλώσσες των προβολικών διαμορφώσεων και των κανονικών αντιστοιχίσεων διμερών γραφημάτων, αντίστοιχα, παρουσιάστηκαν πολύ νωρίτερα το 1894 στη διατριβή του Έρνστ Στάινιτζ και το 1916 από τον Ντένες Κνούνιγκ. Επειδή όλες οι συντεταγμένες των κορυφών είναι μηδέν ή ένα, το πολύτοπο Μπίρκοφ είναι ένα ολοκληρωτικό πολύτοπο.

Ακμές

Οι ακμές του πολυτόπου Μπίρκοφ αντιστοιχούν σε ζεύγη μεταθέσεων που διαφέρουν κατά έναν κύκλο:

$(\sigma ,\omega )$ έτσι ώστε ${\sigma }^{-1}\omega$ να είναι κύκλος.

Αυτό σημαίνει ότι το γράφημα τουB_n είναι ένα γράφημα Κέιλεϊ της συμμετρικής ομάδας S_n. Αυτό συνεπάγεται επίσης ότι το γράφημα του B₃ είναι ένα πλήρες γράφημα K₆, και επομένως το B₃ είναι ένα γειτονικό πολύτοπο.

Όψεις

Το πολύτοπο Μπίρκοφ βρίσκεται μέσα σε έναν Πρότυπο:Nowrap-διάστατο αφινικό υποχώρο του n²-διάστατου χώρου όλων των πινάκων Πρότυπο:Nowrap υποχώρος αυτός καθορίζεται από τους γραμμικούς περιορισμούς ισότητας ότι το άθροισμα κάθε γραμμής και κάθε στήλης πρέπει να είναι ένα. Εντός αυτού του υποχώρου, ορίζεται από n² γραμμικές ανισώσεις, μία για κάθε συντεταγμένη του πίνακα, που καθορίζουν ότι η συντεταγμένη πρέπει να είναι μη αρνητική. Επομένως, για $n\ge 3$, έχει ακριβώς n² όψεις. Για n = 2, υπάρχουν δύο όψεις, που δίνονται από τις a₁₁ = a₂₂ = 0, και a₁₂ = a₂₁ = 0.

Συμμετρίες

Το πολυτόπιο Μπίρκοφ B_n είναι τόσο μεταβατικό ως προς τις κορυφές όσο και ως προς τις όψεις (δηλ. το δυϊκό πολύτοπο είναι μεταβατικό ως προς τις κορυφές). Δεν είναι κανονικό για n>2.

Όγκος

Ένα εκκρεμές πρόβλημα είναι η εύρεση του όγκου των πολυτόπων Μπίρκοφ. Αυτό έχει επιτευχθεί για n ≤ 10. Είναι γνωστό ότι ισούται με τον όγκο ενός πολυτόπου που σχετίζεται με τα τυπικά πίνακες Γιανγκ. Ένας συνδυαστικός τύπος για όλα τα n δόθηκε το 2007. Ο ακόλουθος ασυμπτωτικός τύπος βρέθηκε από τους Ρόντνεϊ Κάνφιλντ και Μπρένταν ΜακΚέι:.

$\mathrm{v}\mathrm{o}\mathrm{l}(B_n)=\exp (-(n-1{)}^2\ln n+n^2-(n-\frac{1}{2})\ln (2\pi )+\frac{1}{3}+o(1)).$

Για μικρές τιμές $n\le 15$ ο όγκος εκτιμήθηκε το 2014, ενώ παρόμοιες εκτιμήσεις ακολουθούν.

Πολυώνυμο Ερχάρτ

Ο προσδιορισμός του πολυωνύμου Έρχαρτ ενός πολυτόπου είναι δυσκολότερος από τον προσδιορισμό του όγκου του, δεδομένου ότι ο όγκος μπορεί εύκολα να υπολογιστεί από τον πρώτο συντελεστή του πολυωνύμου Έρχαρτ. Το πολυώνυμο Έρχαρτ που σχετίζεται με το πολύτοπο Μπίρκοφ είναι γνωστό μόνο για μικρές τιμές. Εικάζεται ότι όλοι οι συντελεστές των πολυωνύμων Έρχαρτ είναι μη αρνητικοί.

Γενικεύσεις

• Το πολύτοπο Μπίρκοφ είναι μια ειδική περίπτωση του πολυτόπου μεταφοράς, ενός πολυτόπου μη αρνητικών ορθογώνιων πινάκων με δεδομένα αθροίσματα γραμμών και στηλών. Τα ακέραια σημεία σε αυτά τα πολύτοπα ονομάζονται πίνακες ενδεχομένων- παίζουν σημαντικό ρόλο στη Μπεϋζιανή στατιστική.
• Το πολύτοπο Μπίρκοφ είναι μια ειδική περίπτωση του πολυτόπου ταιριάσματος, που ορίζεται ως ένα κυρτό περίβλημα των τέλειων ταιριάξεων σε ένα πεπερασμένο γράφημα. Η περιγραφή των όψεων σε αυτή τη γενικότητα δόθηκε από τον Τζακ Έντμοντς (1965) και σχετίζεται με τον αλγόριθμο ταιριάσματος του Έντμοντς.
• Το πολυτόπιο Μπίρκοφ είναι μια ειδική περίπτωση του πολυτόπου ροής των μη αρνητικών ροών μέσω ενός δικτύου. Σχετίζεται με τον αλγόριθμο Φορντ-Φούλκερσον που υπολογίζει τη μέγιστη ροή σε ένα δίκτυο ροής.

Δημοσιεύσεις

• Πρότυπο:Cite journal
• Πρότυπο:Cite book
• Πρότυπο:Cite journal
• Πρότυπο:Citation
• Πρότυπο:Citation
• Diodorus Siculus, Bibliotheca Historica. Vol. 1–2. Immanel Bekker. Ludwig Dindorf. Friedrich Vogel. in aedibus B. G. Teubneri. Leipzig. 1888–1890. Greek text available at the Perseus Digital Library.
• Πρότυπο:Citation
• Πρότυπο:Citation
• Πρότυπο:Cite journal

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Πραγματικός αριθμός
• Αντιερμιτιανός πίνακας
• Μέγιστος κοινός διαιρέτης
• Υπολογιστική βιολογία
• Ελάσσων (γραμμική άλγεβρα)
• Προβολή (γραμμική άλγεβρα)
• Συμμετρικός πίνακας
• Παραμετρικές εξισώσεις
• Πολλαπλασιασμός πινάκων
• Επαναλαμβανόμενη συνάρτηση
• Ανάλυση πίνακα σε ιδιάζουσες τιμές
• Μπεϋζιανή στατιστική
• Κυρτό πολύτοπο
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form

Εξωτερικοί σύνδεσμοι

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix calculator
• Matrix Analysis
• Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
• Exercises of Matrices and Linear Algebra
• Fourier Transforms: Approach to Scientific Principles
• Euclidean Distance Matrices and Their Applications in Rigidity Theory.
• Physics and Combinatorics 2000: Proceedings of the Nagoya 2000 International ...
• Grobner Bases and Convex Polytopes..
• Discrete Geometry and Algebraic Combinatorics...
• Pedigree Polytopes: New Insights on Computational Complexity of ...
• Lectures on the Combinatorics of Free Probability, Τόμος 13

Παραπομπές

• Πρότυπο:Cite book
• Πρότυπο:Citation