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

Το πολυτόπιο Μπίρκοφ Bn (που ονομάζεται επίσης πολύτοπο ανάθεσης, πολύτοπο των διπλά στοχαστικών πινάκων ή πολυτόπιο τέλειας αντιστοίχισης του πλήρους διμερούς γραφήματος  )  είναι το κυρτό πολύτοπο στο RN (όπου N = n2) του οποίου τα σημεία είναι οι διπλά στοχαστικοί πίνακες, δηλ, οι  πίνακες των οποίων οι εγγραφές είναι μη αρνητικοί πραγματικοί αριθμοί και των οποίων οι γραμμές και οι στήλες αθροίζουν το 1. Πήρε το όνομά του από τον Γκάρετ Μπίρκοφ.

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

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

  έτσι ώστε  να είναι κύκλος.  

Αυτό σημαίνει ότι το γράφημα τουBn είναι ένα γράφημα Κέιλεϊ της συμμετρικής ομάδας Sn. Αυτό συνεπάγεται επίσης ότι το γράφημα του B3  είναι ένα πλήρες γράφημα K6, και επομένως το B3 είναι ένα γειτονικό πολύτοπο.

 Όψεις
Το πολύτοπο Μπίρκοφ βρίσκεται μέσα σε έναν -διάστατο αφινικό υποχώρο του n2-διάστατου χώρου όλων των πινάκων  υποχώρος αυτός καθορίζεται από τους γραμμικούς περιορισμούς ισότητας ότι το άθροισμα κάθε γραμμής και κάθε στήλης πρέπει να είναι ένα. Εντός αυτού του υποχώρου, ορίζεται από n2 γραμμικές ανισώσεις, μία για κάθε συντεταγμένη του πίνακα, που καθορίζουν ότι η συντεταγμένη πρέπει να είναι μη αρνητική. Επομένως, για , έχει ακριβώς n2  όψεις. Για n = 2, υπάρχουν δύο όψεις, που δίνονται από τις a11 = a22 = 0, και a12 = a21 = 0.

Συμμετρίες

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

 Όγκος 

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

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

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

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

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

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





 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.




Δείτε επίσης

 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

Παραπομπές





Κατηγορία:Αριθμητική γραμμική άλγεβρα
Κατηγορία:Γραμμική άλγεβρα
Κατηγορία:Θεωρήματα της γραμμικής άλγεβρας
Κατηγορία:Πίνακες (μαθηματικά)
Κατηγορία:Συνδυαστική
Κατηγορία:Διακριτή γεωμετρία