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

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

Ιδιότητες

Κορυφές

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

Ακμές

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

(\sigma ,\omega )

έτσι ώστε

\sigma ^{-1}\omega

να είναι κύκλος.

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

Όψεις

Το πολύτοπο Μπίρκοφ βρίσκεται μέσα σε έναν (n² − 2n + 1)--διάστατο αφινικό υποχώρο του n²-διάστατου χώρου όλων των πινάκων n × n υποχώρος αυτός καθορίζεται από τους γραμμικούς περιορισμούς ισότητας ότι το άθροισμα κάθε γραμμής και κάθε στήλης πρέπει να είναι ένα. Εντός αυτού του υποχώρου, ορίζεται από n² γραμμικές ανισώσεις, μία για κάθε συντεταγμένη του πίνακα, που καθορίζουν ότι η συντεταγμένη πρέπει να είναι μη αρνητική. Επομένως, για $n\geq 3$ , έχει ακριβώς n² όψεις.^[1] Για n = 2, υπάρχουν δύο όψεις, που δίνονται από τις a₁₁ = a₂₂ = 0, και a₁₂ = a₂₁ = 0.

Συμμετρίες

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

Όγκος

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

\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\leq 15$ ο όγκος εκτιμήθηκε το 2014^[9], ενώ παρόμοιες εκτιμήσεις ακολουθούν.^[10]

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

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

Γενικεύσεις

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

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

Μαυρογιάννης, Ν. Σ. (Μαΐου 2016). «Μία εισαγωγή στους μιγαδικούς αριθμούς». Εκθέτης Φύλλα Μαθηματικής Παιδείας (16): 1-8. http://ekthetis.gr/Ekthetis016.pdf.
Bronshtein, I. N.· Semendyayev, K. A. (29 Ιουνίου 2013). Handbook of Mathematics. Springer Science & Business Media. ISBN 978-3-662-21982-9.
Belevitch V (1950). «Theory of 2n-terminal networks with applications to conference telephony». Electrical Communication 27: 231–244.
Bareiss, E. H. (1969), «Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices», Numerische Mathematik 13 (5): 404–424, doi:10.1007/BF02163269
Goldreich, O.; Tal, A. (2018), «Matrix rigidity of random Toeplitz matrices», Computational Complexity 27 (2): 305–350, doi:10.1007/s00037-016-0144-9
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.
de Boor, Carl (1990), «An empty exercise», ACM SIGNUM Newsletter 25 (2): 3–7, doi:10.1145/122272.122273, http://ftp.cs.wisc.edu/Approx/empty.pdf
Bourbaki, Nicolas (1998), Algebra I, Chapters 1-3, Springer, ISBN 9783540642435
Habgood, Ken; Arel, Itamar (2012). «A condensation-based application of Cramer's rule for solving large-scale linear systems». Journal of Discrete Algorithms 10: 98–109. doi:10.1016/j.jda.2011.06.007. https://hal.archives-ouvertes.fr/hal-01500199/file/HA.pdf.

Δείτε επίσης

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

Παραπομπές

↑ ^1,0 ^1,1 ^1,2 Ziegler, Günter M. (2007), Lectures on Polytopes, Graduate Texts in Mathematics, 152 (7th printing of 1st έκδοση), New York: Springer, σελ. 20, ISBN 978-0-387-94365-7
↑ «Garrett Birkhoff - Biography». Maths History (στα Αγγλικά). Ανακτήθηκε στις 3 Σεπτεμβρίου 2024.
↑ Birkhoff, Garrett (1946), «Tres observaciones sobre el algebra lineal [Three observations on linear algebra]», Univ. Nac. Tucumán. Revista A. 5: 147–151 .
↑ Kőnig, Dénes (1916), «Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére», Matematikai és Természettudományi Értesítő 34: 104–119 .
↑ ^5,0 ^5,1 Beck, Matthias; Pixton, Dennis (1 October 2003), «The Ehrhart Polynomial of the Birkhoff Polytope», Discrete and Computational Geometry 30 (4): 623–637, doi:10.1007/s00454-003-2850-8
↑ Pak, Igor (2000), «Four questions on Birkhoff polytope», Annals of Combinatorics 4: 83–90, doi:10.1007/PL00001277 .
↑ De Loera, Jesus A.; Liu, Fu; Yoshida, Ruriko (2007), «Formulas for the volumes of the polytope of doubly-stochastic matrices and its faces», Journal of Algebraic Combinatorics 30: 113–139, doi:10.1007/s10801-008-0155-y .
↑ Canfield, E. Rodney; McKay, Brendan D. (2007). «The asymptotic volume of the Birkhoff polytope». arXiv:0705.2422 [math.CO].
↑ Emiris, Ioannis; Fisikopoulos, Vissarion (2014), «Efficient Random-Walk Methods for Approximating Polytope Volume», Annual Symposium on Computational Geometry - SOCG'14, ACM, σελ. 318–327, doi:10.1145/2582112.2582133, ISBN 9781450325943
↑ Cousins, Ben; Vempala, Santosh (2016), «A practical volume algorithm», Mathematical Programming Computation 8 (2): 133–160, doi:10.1007/s12532-015-0097-z
↑ Emelichev, V.A.; Kovalev, M.M.; Kravtsov, M. K. (1984), Polytopes, Graphs, and Optimization, Cambridge University Press
↑ Baldoni-Silva, W.; De Loera, J. A.; Vergne, M. (2004), «Counting Integer Flows in Networks», Foundations of Computational Mathematics 4 (3): 277–314, doi:10.1007/s10208-003-0088-8

Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001.
Najnudel, Joseph; Nikeghbali, Ashkan (2013), «The Distribution of Eigenvalues of Randomized Permutation Matrices», Annales de l'Institut Fourier 63 (3): 773–838, http://www.numdam.org/item/AIF_2013__63_3_773_0/

[z-1] 1,0 ^1,1 ^1,2 Ziegler, Günter M. (2007), Lectures on Polytopes, Graduate Texts in Mathematics, 152 (7th printing of 1st έκδοση), New York: Springer, σελ. 20, ISBN 978-0-387-94365-7

[2] «Garrett Birkhoff - Biography». Maths History (στα Αγγλικά). Ανακτήθηκε στις 3 Σεπτεμβρίου 2024.

[3] Birkhoff, Garrett (1946), «Tres observaciones sobre el algebra lineal [Three observations on linear algebra]», Univ. Nac. Tucumán. Revista A. 5: 147–151 .

[4] Kőnig, Dénes (1916), «Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére», Matematikai és Természettudományi Értesítő 34: 104–119 .

[beck-pixton-5] 5,0 ^5,1 Beck, Matthias; Pixton, Dennis (1 October 2003), «The Ehrhart Polynomial of the Birkhoff Polytope», Discrete and Computational Geometry 30 (4): 623–637, doi:10.1007/s00454-003-2850-8

[6] Pak, Igor (2000), «Four questions on Birkhoff polytope», Annals of Combinatorics 4: 83–90, doi:10.1007/PL00001277 .

[7] De Loera, Jesus A.; Liu, Fu; Yoshida, Ruriko (2007), «Formulas for the volumes of the polytope of doubly-stochastic matrices and its faces», Journal of Algebraic Combinatorics 30: 113–139, doi:10.1007/s10801-008-0155-y .

[8] Canfield, E. Rodney; McKay, Brendan D. (2007). «The asymptotic volume of the Birkhoff polytope». arXiv:0705.2422 [math.CO].

[9] Emiris, Ioannis; Fisikopoulos, Vissarion (2014), «Efficient Random-Walk Methods for Approximating Polytope Volume», Annual Symposium on Computational Geometry - SOCG'14, ACM, σελ. 318–327, doi:10.1145/2582112.2582133, ISBN 9781450325943

[10] Cousins, Ben; Vempala, Santosh (2016), «A practical volume algorithm», Mathematical Programming Computation 8 (2): 133–160, doi:10.1007/s12532-015-0097-z

[11] Emelichev, V.A.; Kovalev, M.M.; Kravtsov, M. K. (1984), Polytopes, Graphs, and Optimization, Cambridge University Press

[12] Baldoni-Silva, W.; De Loera, J. A.; Vergne, M. (2004), «Counting Integer Flows in Networks», Foundations of Computational Mathematics 4 (3): 277–314, doi:10.1007/s10208-003-0088-8

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]