Πινάκας με ορίζουσα μονάδα

Στα μαθηματικά, ένας πίνακας με ορίζουσα μονάδα Μ είναι ένας τετραγωνικός ακέραιος πίνακας που έχει ορίζουσα +1 ή -1. Αντίστοιχα, είναι ένας ακέραιος πίνακας που είναι αντιστρέψιμος στους ακεραίους: υπάρχει ένας ακέραιος πίνακας N που είναι ο αντίστροφός του (αυτά είναι ισοδύναμα σύμφωνα με τον κανόνα του Κράμερ). Έτσι, κάθε εξίσωση Mx = b}, όπου ο M και ο b έχουν και οι δύο ακέραιες συνιστώσες και ο M είναι με ορίζουσα μονάδα, έχει μια ακέραια λύση. Οι n × n πίνακες με ορίζουσα μονάδα σχηματίζουν μια ομάδα που ονομάζεται n × n γενική γραμμική ομάδα πάνω στην $\mathbb {Z}$, η οποία συμβολίζεται $\operatorname {GL} _{n}(\mathbb {Z} )$.

Παραδείγματα πινάκων με ορίζουσα μονάδα

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

• Πίνακας ταυτότητας
• Ο αντιστρέψιμος ενός πίνακα με ορίζουσα μονάδα
• Το γινόμενο δύο πινάκων με ορίζουσα μονάδα

Άλλα παραδείγματα περιλαμβάνουν:

• Πίνακες Πασκάλ
• Πίνακες μεταθέσεων
• οι τρεις πίνακες μετασχηματισμού στο τριμερές δέντρο των πρωταρχικών πυθαγόρειων τριπλών
• Ορισμένοι πίνακες μετασχηματισμού για περιστροφή, διάτμηση (και οι δύο με προσδιοριστή 1) και ανάκλαση (ορίζουσα-1).

• Ο πίνακας με ορίζουσα μονάδα που χρησιμοποιείται (ενδεχομένως σιωπηρά) στην αναγωγή πλέγματος και στην κανονική μορφή Ερμίτ των πινάκων.
• Το γινόμενο Κρόνεκερ δύο πινάκων με ορίζουσα μονάδα είναι επίσης με ορίζουσα μονάδα . Αυτό προκύπτει αφού $\det(A\otimes B)=(\det A)^{q}(\det B)^{p},$ όπου p και q είναι οι διαστάσεις των A και B, αντίστοιχα.

Ολικός πίνακας με ορίζουσα μονάδα

Ολικός πίνακας με ορίζουσα μονάδα (TU πίνακας) είναι ένας πίνακας για τον οποίο κάθε τετραγωνικός μη ιδιάζων υποπίνακας είναι με ορίζουσα μονάδα. Ισοδύναμα, κάθε τετραγωνικός υποπίνακας έχει ιδιάζουσα 0, +1 ή −1. Ένας ολικός πίνακας με ορίζουσα μονάδα δεν χρειάζεται να είναι τετραγωνικός. Από τον ορισμό προκύπτει ότι κάθε υποπίνακας ενός ολικού με ορίζουσα μονάδα είναι ο ίδιος ολικός πίνακας με ορίζουσα μονάδα(TU). Επιπλέον, προκύπτει ότι κάθε TU πίνακας έχει μόνο 0, +1 or −1 καταχωρήσεις. Το αντίστροφο δεν ισχύει, δηλαδή ένας πίνακας με μόνο 0, +1 ή −1 καταχωρήσεις δεν είναι απαραίτητα με ορίζουσα μονάδα. Ένας πίνακας είναι TU αν και μόνο αν ο μεταθέτης του είναι TU.

Οι ολικοί πίνακες με ορίζουσα μονάδα είναι εξαιρετικά σημαντικοί στην πολυεδρική συνδυαστική και τη συνδυαστική βελτιστοποίηση, καθώς παρέχουν έναν γρήγορο τρόπο για να επαληθεύσουμε ότι ένα γραμμικό πρόγραμμα είναι ολοκληρωτικό (έχει ολοκληρωτικό βέλτιστο, όταν υπάρχει οποιοδήποτε βέλτιστο). Συγκεκριμένα, αν το A είναι TU και το b είναι ολοκληρωτικό, τότε γραμμικά προγράμματα μορφών όπως $\{\min c^{\top }x\mid Ax\geq b,x\geq 0\}$ ή $\{\max c^{\top }x\mid Ax\leq b\}$ έχουν ολοκληρωτικά βέλτιστα, για οποιοδήποτε c. Επομένως, αν το A είναι ολικος με ορίζουσα μονάδα και το b είναι ολοκληρωτικό, κάθε ακραίο σημείο της εφικτής περιοχής (π.χ. $\{x\mid Ax\geq b\}$) είναι ολοκληρωτικό και επομένως η εφικτή περιοχή είναι ένα ολοκληρωτικό πολύεδρο.

Κοινοί ολικοί πίνακες με ορίζουσα μονάδα

1. Ο μη προσανατολισμένος πίνακας προσπτώσεων ενός διμερούς γραφήματος, ο οποίος είναι ο πίνακας συντελεστών για διμερές ταίριασμα, είναι ολικός με ορίζουσα μονάδα (TU) (Ο μη προσανατολισμένος πίνακας προσπτώσεων ενός μη διμερούς γραφήματος δεν είναι TU.) Γενικότερα, στο παράρτημα μιας εργασίας των Χέλερ και Τόμπκινς, οι A.J. Χόφμαν και D. Γκέιλ αποδεικνύουν τα εξής. Έστω $A$ ένας πίνακας m επί n του οποίου οι γραμμές μπορούν να χωριστούν σε δύο διαχωρισμένα σύνολα $B$ και $C$. Τότε οι ακόλουθες τέσσερις συνθήκες μαζί αρκούν για να είναι ο Α ολικός με ορίζουσα μονάδα:

• Κάθε καταχώρηση στο $A$ είναι 0, +1 ή -1,
• Κάθε στήλη του $A$ περιέχει το πολύ δύο μη μηδενικές (δηλαδή +1 ή -1) καταχωρήσεις,
• Αν δύο μη μηδενικές καταχωρήσεις σε μια στήλη της $A$ έχουν το ίδιο πρόσημο, τότε η γραμμή της μίας βρίσκεται στην $B$ και η άλλη στην $C$,
• Αν δύο μη μηδενικές καταχωρήσεις σε μια στήλη του $A$ έχουν αντίθετα πρόσημα, τότε οι γραμμές και των δύο βρίσκονται στο $B$, ή και των δύο στο $C$

Αργότερα έγινε αντιληπτό ότι αυτές οι συνθήκες ορίζουν έναν πίνακα προσπτώσεων ενός ισορροπημένου προσημασμένου γραφήματος- έτσι, αυτό το παράδειγμα λέει ότι ο πίνακας προσπτώσεων ενός προσημασμένου γραφήματος είναι ολικός με ορίζουσα μονάδα αν το προσημασμένο γράφημα είναι ισορροπημένο. Το αντίστροφο ισχύει για προσημασμένα γραφήματα χωρίς μισές ακμές (αυτό γενικεύει την ιδιότητα του μη προσανατολισμένου πίνακα πρόσπτωσης ενός γραφήματος).

2. Οι περιορισμοί των προβλημάτων μέγιστης ροής και ελάχιστου κόστους ροής δίνουν έναν πίνακα συντελεστών με αυτές τις ιδιότητες (και με κενό C). Έτσι, τέτοια προβλήματα ροής δικτύου με περιορισμένες ακέραιες χωρητικότητες έχουν μια ολοκληρωμένη βέλτιστη τιμή. Ας σημειωθεί ότι αυτό δεν ισχύει για τα προβλήματα ροής πολλαπλών αγαθών, στα οποία είναι δυνατόν να έχουμε κλασματική βέλτιστη τιμή ακόμη και με περιορισμένες ακέραιες χωρητικότητες.

3. Η ιδιότητα των διαδοχικών μονάδων: αν ο Α είναι (ή μπορεί να μετατραπεί σε) ένας πίνακας 0-1 στον οποίο για κάθε γραμμή, οι μονάδες 1 εμφανίζονται διαδοχικά, τότε ο Α είναι TU. (Το ίδιο ισχύει και για τις στήλες, αφού η αντιστροφή ενός πίνακα TU είναι επίσης TU).

4. Κάθε πίνακας δικτύου είναι TU. Οι γραμμές ενός πίνακα δικτύου αντιστοιχούν σε ένα δέντρο T = (V, R), κάθε τόξο του οποίου έχει έναν αυθαίρετο προσανατολισμό (δεν είναι απαραίτητο να υπάρχει μια κορυφή ρίζα r ώστε το δέντρο να έχει "ρίζα μέσα στην r" ή "έξω από την r").Οι στήλες αντιστοιχούν σε ένα άλλο σύνολο C τόξων στο ίδιο σύνολο κορυφών V. Για να υπολογίσουμε την καταχώρηση στη γραμμή R και τη στήλη C = st}, εξετάζουμε το μονοπάτι s-to-t P στο T, τότε η καταχώρηση είναι:

• +1 εάν το τόξο R εμφανίζεται μπροστά στο P,
• -1 αν το τόξο R εμφανίζεται προς τα πίσω στο P,
• 0 εάν το τόξο R δεν εμφανίζεται στο P.

Δείτε περισσότερα στο Schrijver (2003).

5. Οι Γκουίλα-Χουρί έδειξαν ότι ένας πίνακας είναι TU αν για κάθε υποσύνολο R γραμμών, υπάρχει μια ανάθεση $s:R\to \pm 1$ των σημείων στις γραμμές έτσι ώστε το προσημασμένο άθροισμα $\sum _{r\in R}s(r)r$ (το οποίο είναι ένα διάνυσμα γραμμών του ίδιου πλάτους με τον πίνακα) έχει όλες τις καταχωρήσεις του στο $\{0,\pm 1\}$ (i. δηλ. ο υποπίνακας γραμμών έχει ασυμφωνία το πολύ μία). Αυτός και διάφοροι άλλοι χαρακτηρισμοί αν-και-μόνο-αν αποδεικνύονται στο Schrijver (1998).

6. Οι Χόφμαν και Κρούσκαλ απέδειξαν το ακόλουθο θεώρημα. Ας υποθέσουμε ότι $G$ είναι ένας κατευθυνόμενος γράφος χωρίς 2-κύκλους, $P$ είναι το σύνολο όλων των δίπατων στο $G$, και $A$ είναι ο πίνακας 0-1 επίπτωσης του$V(G)$ έναντι του $P$. Τότε ο $A$ είναι εντελώς μονοτροπικός αν και μόνο αν κάθε απλός αυθαίρετα προσανατολισμένος κύκλος στο $G$ αποτελείται από εναλλασσόμενα τόξα προς τα εμπρός και προς τα πίσω.

7. Ας υποθέσουμε ότι ένας πίνακας έχει 0-($\pm$1) καταχωρήσεις και σε κάθε στήλη, οι καταχωρήσεις είναι μη φθίνουσες από πάνω προς τα κάτω (έτσι ώστε όλα τα -1 να βρίσκονται στην κορυφή, μετά τα 0, μετά τα 1 να βρίσκονται στο κάτω μέρος). Ο Φουτζισίγκε έδειξε ότι ο πίνακας είναι TU αν κάθε υποπίνακας 2 επί 2 έχει ορίζουσα στο $0,\pm 1$.

8. Ο Πολ Σέιμουρ (μαθηματικός) (1980) απέδειξε έναν πλήρη χαρακτηρισμό όλων των πινάκων TU, τον οποίο περιγράφουμε εδώ μόνο ανεπίσημα. Το θεώρημα του Σέιμουρ είναι ότι ένας πίνακας είναι TU αν και μόνο αν είναι ένας ορισμένος φυσικός συνδυασμός ορισμένων δικτυακών πινάκων και ορισμένων αντιγράφων ενός συγκεκριμένου πίνακα TU 5 επί 5.

Συγκεκριμένα παραδείγματα

1. Ο ακόλουθος πίνακας είναι ολικός με ορίζουσα μονάδα

$A=\left[{\begin{array}{rrrrrr}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\end{array}}\right].$

Ο πίνακας αυτός προκύπτει ως ο πίνακας συντελεστών των περιορισμών στη διατύπωση του γραμμικού προγραμματισμού του προβλήματος μέγιστης ροής στο ακόλουθο δίκτυο:

2. Οποιοσδήποτε πίνακας της μορφής

$A=\left[{\begin{array}{ccccc}&\vdots &&\vdots \\\dotsb &+1&\dotsb &+1&\dotsb \\&\vdots &&\vdots \\\dotsb &+1&\dotsb &-1&\dotsb \\&\vdots &&\vdots \end{array}}\right].$

δεν είναι μη ολικός με ορίζουσα μονάδα, αφού έχει έναν τετραγωνικό υποπίνακα με προσδιοριστή -2.

Αφηρημένη γραμμική άλγεβρα

Η Αφηρημένη γραμμική άλγεβρα εξετάζει πίνακες με καταχωρήσεις από οποιονδήποτε αντιμεταθετικό δακτύλιο $R$, χωρίς να περιορίζεται στους ακέραιους αριθμούς. Σε αυτό το πλαίσιο, ένας μονοτροπικός πίνακας είναι ένας πίνακας που είναι αντιστρέψιμος πάνω στον δακτύλιο- ισοδύναμα, του οποίου ο προσδιοριστής είναι μια μονάδα. Η ομάδα αυτή συμβολίζεται ως $\operatorname {GL} _{n}(R)$.

Πάνω σε ένα σώμα, ο όρος "με ορίζουσα μονάδα" έχει την ίδια έννοια με τον όρο "μη-ιδιάζων". Ο όρος με ορίζουσα μονάδα αναφέρεται εδώ σε πίνακες με συντελεστές σε κάποιο δακτύλιο (συχνά οι ακέραιοι) που είναι αντιστρέψιμοι πάνω σε αυτόν τον δακτύλιο, ενώ με τον όρο μη ιδιάζων' εννοούμε πίνακες που είναι αντιστρέψιμοι πάνω στο σώμα.

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Εσωτερικό γινόμενο
• Αντιερμιτιανός πίνακας
• Πίνακας (μαθηματικά)
• Τριγωνικός πίνακας
• Ερμιτιανός πίνακας
• Προβολή (γραμμική άλγεβρα)
• Συζυγής ανάστροφος πίνακας
• Θεώρημα Κέιλι-Χάμιλτον.
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form
• Algorithm overview

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

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix Analysis
• Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
• Integral Matrices
• An Introduction to Computational Physics
• Theory of Linear and Integer Programming
• Combinatorial Matrix Theory
• Introduction to Matrix Methods in Optics

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

• Μαυρογιάννης, Ν. Σ. (Μαΐου 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. 
• Gray, Lawrence F.; Flanigan, Francis J.; Kazdan, Jerry L.; Frank, David H.; Fristedt, Bert (1990), Calculus two: linear and nonlinear functions, Berlin: Springer-Verlag, σελ. 375, ISBN 0-387-97388-5, https://archive.org/details/calculustwolinea00flan/page/375 
• Sylvester, J. (1884). «Sur l'equations en matrices $px=xq$». :C. R. Acad. Sci. Paris 99 (2): 67–71, 115–116. 
• Zeni, J. R.; Rodrigues, W.A. (1992). «A thoughful study of Lorentz transformations by Clifford algebras». Int. J. Mod. Phys. A (World Scientific) 7 (8): 1793 pp. doi:10.1142/S0217751X92000776. Bibcode: 1992IJMPA...7.1793Z. http://www.worldscientific.com/doi/abs/10.1142/S0217751X92000776. 
• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), Combinatorial Optimization: Algorithms and Complexity, Mineola, N.Y.: Dover Publications, σελ. 316, ISBN 978-0-486-40258-1, https://books.google.com/books?id=cDY-joeCGoIC&pg=PA316 
• Alexander Schrijver (1998), Theory of Linear and Integer Programming. John Wiley & Sons, (ISBN 0-471-98232-6) (mathematical)
• Alexander Schrijver (2003), Combinatorial Optimization: Polyhedra and Efficiency, Springer 

Παραπομπές

• Janko Bračič, Kolobar aritmetičnih funkcij (Ring of arithmetical functions), (Obzornik mat, fiz. 49 (2002) 4, pp. 97–108) (MSC (2000) 11A25)
• Iwaniec and Kowalski, Analytic number theory, AMS (2004).