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

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

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

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

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

Αυτό σημαίνει ότι το γράφημα του*B**n* είναι ένα γράφημα Κέιλεϊ της συμμετρικής ομάδας *S**n*. Αυτό συνεπάγεται επίσης ότι το γράφημα του *B**3*  είναι ένα πλήρες γράφημα *K**6*, και επομένως το *B**3* είναι ένα γειτονικό πολύτοπο.

### Όψεις
Το πολύτοπο Μπίρκοφ βρίσκεται μέσα σε έναν -διάστατο αφινικό υποχώρο του *n*2-διάστατου χώρου όλων των πινάκων  υποχώρος αυτός καθορίζεται από τους γραμμικούς περιορισμούς ισότητας ότι το άθροισμα κάθε γραμμής και κάθε στήλης πρέπει να είναι ένα. Εντός αυτού του υποχώρου, ορίζεται από *n*2 γραμμικές ανισώσεις, μία για κάθε συντεταγμένη του πίνακα, που καθορίζουν ότι η συντεταγμένη πρέπει να είναι μη αρνητική. Επομένως, για n\ge 3, έχει ακριβώς *n*2  όψεις. Για n = 2, υπάρχουν δύο όψεις, που δίνονται από τις *a**11* = *a**22* = 0, και *a**12* = *a**21* = 0.

### Συμμετρίες

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

### Όγκος

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

:\mathop{\mathrm{vol}}(B_n) \, = \, \exp\left( - (n-1)^2\ln n + n^2 - \left(n - \frac{1}{2}\right)\ln(2\pi) + \frac{1}{3} + o(1) \right) .

Για μικρές τιμές n\le 15 ο όγκος εκτιμήθηκε το 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

## Παραπομπές

* 
*

 

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