Δυαδικός πίνακας

Ένας δυαδικός πίνακας, πίνακας Μπουλ ή πίνακας (0, 1) είναι ένας πίνακας με καταχωρήσεις από την περιοχή Μπουλ^[1] $B = {0, 1}.$ Ένας τέτοιος πίνακας μπορεί να χρησιμοποιηθεί για την αναπαράσταση μιας δυαδικής σχέσης μεταξύ ενός ζεύγους πεπερασμένων συνόλων. Αποτελεί σημαντικό εργαλείο στη Συνδυαστική και τη Θεωρητική Πληροφορική.

Πίνακας αναπαράστασης μιας σχέσης

Αν η R είναι μια δυαδική σχέση μεταξύ των πεπερασμένων με δείκτη συνόλων X και Y (άρα $R \subseteq X \times Y$ ), τότε η R μπορεί να αναπαρασταθεί από τον δυαδικό πίνακα M του οποίου οι δείκτες γραμμής και στήλης δεικτοδοτούν τα στοιχεία των X και Y, αντίστοιχα, έτσι ώστε οι εγγραφές του M να ορίζονται ως εξής

m_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R,\\0&(x_{i},y_{j})\not \in R.\end{cases}}

Προκειμένου να προσδιοριστούν οι αριθμοί γραμμών και στηλών του πίνακα, τα σύνολα X και Y έχουν δείκτες με θετικούς ακέραιους αριθμούς: το i κυμαίνεται από το 1 έως την πληθικότητα (μέγεθος) του X, και το j κυμαίνεται από το 1 έως την πληθικότητα του Y. Δείτε το άρθρο για τα σύνολα με δείκτες για περισσότερες λεπτομέρειες.

Παράδειγμα

Η δυαδική σχέση R στο σύνολο ${1, 2, 3, 4$ } ορίζεται έτσι ώστε να ισχύει aRb αν και μόνο αν το a διαιρεί το b ομοιόμορφα, χωρίς υπόλοιπο. Παραδείγματος χάριν, το 2R4 ισχύει επειδή το 2 διαιρεί το 4 χωρίς να αφήνει υπόλοιπο, αλλά το 3R4 δεν ισχύει επειδή όταν το 3 διαιρεί το 4, υπάρχει υπόλοιπο 1. Το ακόλουθο σύνολο είναι το σύνολο των ζευγών για τα οποία ισχύει η σχέση R.

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

Η αντίστοιχη αναπαράσταση ως δυαδικός πίνακας είναι

{\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}},

η οποία περιλαμβάνει μια διαγώνιο μονάδων, αφού κάθε αριθμός διαιρεί τον εαυτό του.

Άλλα παραδείγματα

Ένας πίνακας μεταθέσεων είναι ένας (0, 1)-πίνακας, όλες οι στήλες και οι γραμμές του οποίου έχουν ακριβώς ένα μη μηδενικό στοιχείο.
- Ένας πίνακας Κωστάς είναι μια ειδική περίπτωση ενός πίνακα μεταθέσεων.
Ένας πίνακας προσπτώσεων στη συνδυαστική και την πεπερασμένη γεωμετρία έχει έναν για να υποδεικνύει προσπτώσεις μεταξύ σημείων (ή κορυφών) και γραμμών μιας γεωμετρίας, μπλοκ ενός σχεδίου μπλοκ ή ακμές ενός γραφήματος.
Ένας πίνακας σχεδιασμού στην ανάλυση διακύμανσης είναι ένας (0, 1)-πίνακας με σταθερά αθροίσματα γραμμών.
Ένας δυαδικός πίνακας μπορεί να αντιπροσωπεύει έναν πίνακα γειτνίασης στη θεωρία γραφημάτων: οι μησυμμετρικός πίνακες αντιστοιχούν σε κατευθυνόμενοι γράφοι, οι συμμετρικοί πίνακες σε συνηθισμένα γραφήματα, και ένα 1 στη διαγώνιο αντιστοιχεί σε έναν βρόγχο στην αντίστοιχη κορυφή.
Οι πρώτοι παράγοντες μιας λίστας m αριθμών χωρίς τετράγωνα, n ομαλών αριθμών μπορούν να περιγραφούν ως ένας m × π(n) (0, 1)-πίνακας, όπου π είναι η συνάρτηση καταμέτρησης πρώτων παραγόντων, και a_ij είναι 1 αν και μόνο αν ο j πρώτος διαιρεί τον i αριθμό. Αυτή η αναπαράσταση είναι χρήσιμη στον αλγόριθμο παραγοντοποίησης τετραγωνικού κόσκινου.
Μια εικόνα bitmap που περιέχει εικονοστοιχεία σε δύο μόνο χρώματα μπορεί να αναπαρασταθεί ως ένας (0, 1)-πίνακας στον οποίο τα μηδενικά αντιπροσωπεύουν εικονοστοιχεία του ενός χρώματος και οι μονάδες αντιπροσωπεύουν εικονοστοιχεία του άλλου χρώματος.
Ένας δυαδικός πίνακας μπορεί να χρησιμοποιηθεί για τον έλεγχο των κανόνων του παιχνιδιού Go.^[2]
Η λογική τεσσάρων τιμών των δύο δυφίων, μετασχηματισμένη με δυαδικούς πίνακες 2x2, σχηματίζει ένα σύστημα μετάβασης.
Το διάγραμμα αναδρομής και οι παραλλαγές του είναι πίνακες που δείχνουν ποια ζεύγη σημείων βρίσκονται πιο κοντά από ένα ορισμένο κατώφλι εγγύτητας σε ένα χώρο φάσεων.

Μερικές ιδιότητες

Η αναπαράσταση του πίνακα της σχέσης ισότητας σε ένα πεπερασμένο σύνολο είναι ο ταυτοτικός πίνακας I, δηλαδή ο πίνακας του οποίου οι εγγραφές στη διαγώνιο είναι όλες 1, ενώ οι υπόλοιπες είναι όλες 0. Γενικότερα, αν η σχέση R ικανοποιεί $I \subseteq R,$ τότε η R είναι μια ανακλαστική σχέση.

Εάν η περιοχή Μπουλ θεωρηθεί ως ένα ημί-δακττύλιος, όπου η πρόσθεση αντιστοιχεί στην λογική διάζευξη OR και ο πολλαπλασιασμός στην λογική σύζευξη AND η αναπαράσταση του πίνακα της σύνθεσης δύο σχέσεων είναι ίση με το γινόμενο του πίνακα των αναπαραστάσεων των πινάκων αυτών των σχέσεων. Αυτό το γινόμενο μπορεί να υπολογιστεί σε αναμενόμενο χρόνο O(n²).^[3]

Συχνά, οι πράξεις σε δυαδικούς πίνακες ορίζονται με όρους αριθμητικής υπολοίπων mod 2, δηλαδή, τα στοιχεία αντιμετωπίζονται ως στοιχεία του σώματος Γκαλουά ${\mathbf {GF}}(2)=\mathbb {Z} _{2}$ . Εμφανίζονται σε μια ποικιλία παραστάσεων και έχουν μια σειρά από πιο περιορισμένες ειδικές μορφές. Εφαρμόζονται π.χ. στην ικανοποίηση XOR^[4].

Ο αριθμός των διακριτών δυαδικών πινάκων m-προς-n είναι ίσος με 2^mn, και συνεπώς είναι πεπερασμένος.

Πλέγμα

Έστω n και m και ας συμβολίσουμε με U το σύνολο όλων των δυαδικών πινάκων m × n. Τότε το U έχει μια μερική τάξη που δίνεται από τη σχέση

\forall A,B\in U,\quad A\leq B\quad {\text{when}}\quad \forall i,j\quad A_{ij}=1\implies B_{ij}=1.

Στην πραγματικότητα, η U αποτελεί μια άλγεβρα Μπουλ με τις πράξεις AND & OR μεταξύ δύο πινάκων που εφαρμόζονται κατά συνιστώσες. Το συμπλήρωμα ενός δυαδικού πίνακα προκύπτει με την ανταλλαγή όλων των μηδενικών και των μονάδων με τα αντίθετά τους.

Κάθε δυαδικός πίνακας $A = (A ij)$ έχει έναν ανάστροφο $A T = (A ji).$ Ας υποθέσουμε ότι ο Α είναι ένας δυαδικός πίνακας χωρίς στήλες ή γραμμές πανομοιότυπα μηδενικές. Τότε το γινόμενο του πίνακα, χρησιμοποιώντας την αριθμητική Μπουλ, $A^{\operatorname {T} }A$ περιέχει τον ταυτοτικό πίνακα m × m το γινόμενο $AA^{\operatorname {T} }$ περιέχει την ταυτότητα n × n.

Ως μαθηματική δομή, η Άλγεβρα Μπουλ U σχηματίζει ένα πλέγμα διατεταγμένο με συμπερίληψη- επιπλέον είναι ένα πολλαπλασιαστικό πλέγμα λόγω του πολλαπλασιασμού πινάκων.

Κάθε δυαδικός πίνακας στο U αντιστοιχεί σε μια δυαδική σχέση. Αυτές οι απαριθμούμενες πράξεις στο U, και η διάταξη, αντιστοιχούν σε έναν λογισμό σχέσεων, όπου ο πολλαπλασιασμός πινάκων αντιπροσωπεύει τη σύνθεση σχέσεων.^[5]

Δυαδικά διανύσματα

Εάν m ή n ισούται με ένα, τότε ο δυαδικός πίνακας m × n (m_ij) είναι ένα δυαδικό διάνυσμα ή πίνακας μπιτ. Αν m = 1, το διάνυσμα είναι διάνυσμα γραμμής, και αν n = 1, είναι διάνυσμα στήλης. Σε κάθε περίπτωση, ο δείκτης που ισούται με 1 εγκαταλείπεται από την ονομασία του διανύσματος.

Ας υποθέσουμε ότι $(P_{i}),\,i=1,2,\ldots ,m$ και $(Q_{j}),\,j=1,2,\ldots ,n$ είναι δύο δυαδικά διανύσματα. Το εξωτερικό γινόμενο των P και Q οδηγεί σε μια m × n ορθογώνια σχέση

m_{ij}=P_{i}\land Q_{j}.

Μια αναδιάταξη των γραμμών και των στηλών ενός τέτοιου πίνακα μπορεί να συγκεντρώσει όλες τις μονάδες σε ένα ορθογώνιο τμήμα του πίνακα.^[6]

Έστω h το διάνυσμα όλων των μονάδων. Τότε αν v είναι ένα αυθαίρετο δυαδικό διάνυσμα, η σχέση R = v h^T έχει σταθερές γραμμές που καθορίζονται από το v. Στον λογισμό των σχέσεων ένα τέτοιο R ονομάζεται διάνυσμα.^[6] Μια συγκεκριμένη περίπτωση είναι η καθολική σχέση $hh^{\operatorname {T} }$ .

Για μια δεδομένη σχέση R, μια μέγιστη ορθογώνια σχέση που περιέχεται στην R ονομάζεται έννοια στην R. Οι σχέσεις μπορούν να μελετηθούν με την αποσύνθεση σε έννοιες και στη συνέχεια με την παρατήρηση του επαγόμενου πλέγματος εννοιών.

Ας θεωρήσουμε τον πίνακα των ομαδοποιημένων δομών, όπου το «μη απαραίτητο» μπορεί να συμβολίζεται με 0 και το «απαιτούμενο» με 1, σχηματίζοντας έναν δυαδικό πίνακα $R.$ Για τον υπολογισμό των στοιχείων του $RR^{\operatorname {T} }$ , είναι απαραίτητο να χρησιμοποιήσουμε το δυαδικό εσωτερικό γινόμενο των ζευγών δυαδικών διανυσμάτων στις γραμμές αυτού του πίνακα. Εάν αυτό το εσωτερικό γινόμενο είναι 0, τότε οι γραμμές είναι ορθογώνιες. Πράγματι, η μικρή κατηγορία είναι ορθογώνια προς την οιονεί ομάδα, και το ομαδοειδές είναι ορθογώνιο προς το "Μάγμα"^[7]. Συνεπώς, υπάρχουν μηδενικά στην $RR^{\operatorname {T} }$ , και αποτυγχάνει να είναι μια καθολική σχέση.

Αθροίσματα γραμμών και στηλών

Η πρόσθεση όλων των μονάδων ενός δυαδικού πίνακα μπορεί να γίνει με δύο τρόπους: αθροίζοντας πρώτα τις γραμμές ή αθροίζοντας πρώτα τις στήλες. Όταν προστίθενται τα αθροίσματα των γραμμών, το άθροισμα είναι το ίδιο με αυτό που προκύπτει όταν προστίθενται τα αθροίσματα των στηλών. Στη γεωμετρία της πρόσπτωσης, ο πίνακας ερμηνεύεται ως πίνακας προσπτώσεων με τις γραμμές να αντιστοιχούν σε «σημεία» και τις στήλες σε «τετράγωνα» (γενικεύοντας τις γραμμές που αποτελούνται από σημεία). Ένα άθροισμα γραμμής ονομάζεται βαθμός σημείου, και ένα άθροισμα στήλης είναι ο βαθμός μπλοκ. Το άθροισμα των βαθμών σημείου ισούται με το άθροισμα των βαθμών μπλοκ.^[8]

Ένα πρώιμο πρόβλημα στον τομέα αυτό ήταν «η εύρεση αναγκαίων και επαρκών συνθηκών για την ύπαρξη μιας δομής πρόσπτωσης με δεδομένους βαθμούς σημείου και βαθμούς μπλοκ- ή, σε γλώσσα πινάκων, για την ύπαρξη ενός (0, 1)-πίνακά τύπου v × b με δεδομένα αθροίσματα γραμμών και στηλών».^[8] Το πρόβλημα αυτό επιλύεται με το θεώρημα Γκέιλ-Ράιζερ.

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

Brualdi, Richard A. (2006). «Combinatorial Matrix Classes». Encyclopedia of Mathematics and its Applications. 108. Cambridge University Press. doi:10.1017/CBO9780511721182. ISBN 978-0-521-86565-4.
Brualdi, Richard A.; Ryser, Herbert J. (1991). «Combinatorial Matrix Theory». Encyclopedia of Mathematics and its Applications. 39. Cambridge University Press. doi:10.1017/CBO9781107325708. ISBN 0-521-32265-0.
Botha, J.D. (2013), «31. Matrices over Finite Fields §31.3 Binary Matrices», Handbook of Linear Algebra (Discrete Mathematics and Its Applications) (2nd έκδοση), Chapman & Hall/CRC, doi:10.1201/b16113, ISBN 978-0-429-18553-3
Kim, Ki Hang (1982), Boolean Matrix Theory and Applications, ISBN 978-0-8247-1788-9
Ryser, H.J. (1957). «Combinatorial properties of matrices of zeroes and ones». Canadian Journal of Mathematics 9: 371–7.
Ryser, H.J. (1960). «Traces of matrices of zeroes and ones». Canadian Journal of Mathematics 12: 463–476. doi:10.4153/CJM-1960-040-0.
Ryser, H.J. (1960). «Matrices of Zeros and Ones». Bulletin of the American Mathematical Society 66: 442–464. https://www.ams.org/journals/bull/1960-66-06/S0002-9904-1960-10494-6/S0002-9904-1960-10494-6.pdf.
Fulkerson, D.R. (1960). «Zero-one matrices with zero trace». Pacific Journal of Mathematics 10: 831–6. https://projecteuclid.org/journals/pacific-journal-of-mathematics/volume-10/issue-3/Zero-one-matrices-with-zero-trace/pjm/1103038231.pdf.
Fulkerson, D.R.; Ryser, H.J. (1961). «Widths and heights of (0, 1)-matrices». Canadian Journal of Mathematics 13: 239–255. doi:10.4153/CJM-1961-020-3.
Ford Jr., L.R.· Fulkerson, D.R. (2016) [1962]. «II. Feasibility Theorems and Combinatorial Applications §2.12 Matrices composed of 0's and 1's». Flows in Networks. Princeton University Press. σελίδες 79–91. doi:10.1515/9781400875184-004. ISBN 9781400875184. MR 0159700.

Δείτε επίσης

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

Παραπομπές

↑ Steinbach, Bernd (23 Απριλίου 2014). Recent Progress in the Boolean Domain. Cambridge Scholars Publishing. ISBN 978-1-4438-5967-7.
↑ Petersen, Kjeld (8 Φεβρουαρίου 2013). «Binmatrix». Ανακτήθηκε στις 11 Αυγούστου 2017.
↑ O'Neil, Patrick E.; O'Neil, Elizabeth J. (1973). «A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure». Information and Control 22 (2): 132–8. doi:10.1016/s0019-9958(73)90228-3. — The algorithm relies on addition being idempotent, cf. p.134 (bottom).
↑ «XOR-SAT (Boolean Satisfiability) - Algorithm Wiki». algorithm-wiki.csail.mit.edu. Ανακτήθηκε στις 15 Σεπτεμβρίου 2024.
↑ Copilowish, Irving (December 1948). «Matrix development of the calculus of relations». Journal of Symbolic Logic 13 (4): 193–203.
↑ ^6,0 ^6,1 Schmidt, Gunther (2013). «6: Relations and Vectors». Relational Mathematics. Cambridge University Press. σελ. 91. doi:10.1017/CBO9780511778810. ISBN 978-0-511-77881-0.
↑ «Magma - Encyclopedia of Mathematics». encyclopediaofmath.org. Ανακτήθηκε στις 16 Σεπτεμβρίου 2024.
↑ ^8,0 ^8,1 E.g., see Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1999). «Design Theory». Encyclopedia of Mathematics and its Applications. 69 (2nd έκδοση). Cambridge University Press, σελ. 18. doi:10.1017/CBO9780511549533.001. ISBN 978-0-521-44432-3.

David Poole: Linear Algebra. A Modern Introduction. Cengage Learning 2005, (ISBN 0-534-99845-3), pp. 265–267 (restricted online copy, σ. 265, στα Google Books)
Harvey E. Rose: Linear Algebra. A Pure Mathematical Approach. Springer 2002, (ISBN 3-7643-6905-1), pp. 57–60 (restricted online copy, σ. 57, στα Google Books)
Bareiss, Erwin (1968), «Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination», Mathematics of Computation 22 (102): 565–578, doi:10.2307/2004533, https://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf

[1] Steinbach, Bernd (23 Απριλίου 2014). Recent Progress in the Boolean Domain. Cambridge Scholars Publishing. ISBN 978-1-4438-5967-7.

[2] Petersen, Kjeld (8 Φεβρουαρίου 2013). «Binmatrix». Ανακτήθηκε στις 11 Αυγούστου 2017.

[3] O'Neil, Patrick E.; O'Neil, Elizabeth J. (1973). «A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure». Information and Control 22 (2): 132–8. doi:10.1016/s0019-9958(73)90228-3. — The algorithm relies on addition being idempotent, cf. p.134 (bottom).

[4] «XOR-SAT (Boolean Satisfiability) - Algorithm Wiki». algorithm-wiki.csail.mit.edu. Ανακτήθηκε στις 15 Σεπτεμβρίου 2024.

[5] Copilowish, Irving (December 1948). «Matrix development of the calculus of relations». Journal of Symbolic Logic 13 (4): 193–203.

[GS-6] 6,0 ^6,1 Schmidt, Gunther (2013). «6: Relations and Vectors». Relational Mathematics. Cambridge University Press. σελ. 91. doi:10.1017/CBO9780511778810. ISBN 978-0-511-77881-0.

[7] «Magma - Encyclopedia of Mathematics». encyclopediaofmath.org. Ανακτήθηκε στις 16 Σεπτεμβρίου 2024.

[BJL-8] 8,0 ^8,1 E.g., see Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1999). «Design Theory». Encyclopedia of Mathematics and its Applications. 69 (2nd έκδοση). Cambridge University Press, σελ. 18. doi:10.1017/CBO9780511549533.001. ISBN 978-0-521-44432-3.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]