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

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

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

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

$m_{i,j}=\{\begin{array}{cc}1& (x_i,y_j)\in R,\\ 0& (x_i,y_j)\in ̸R.\end{array}$

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

Παράδειγμα

Η δυαδική σχέση R στο σύνολο Πρότυπο:Math} ορίζεται έτσι ώστε να ισχύει 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)}.

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

$\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 0& 1\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right),$

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

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

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

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

Πολλαπλασιασμός δύο δυαδικών πινάκων με χρήση της άλγεβρας του Μπουλ

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

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

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

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

Πλέγμα

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

$\mathrm{\forall }A,B\in U,A\le B\text{when}\mathrm{\forall }i,j{A}_{ij}=1⟹B_{ij}=1.$

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

Κάθε δυαδικός πίνακας Πρότυπο:Math έχει έναν ανάστροφο Πρότυπο:Math Ας υποθέσουμε ότι ο Α είναι ένας δυαδικός πίνακας χωρίς στήλες ή γραμμές πανομοιότυπα μηδενικές. Τότε το γινόμενο του πίνακα, χρησιμοποιώντας την αριθμητική Μπουλ, $A^{\mathrm{T}}A$ περιέχει τον ταυτοτικό πίνακα m × m το γινόμενο $A{A}^{\mathrm{T}}$ περιέχει την ταυτότητα n × n.

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

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

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

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

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

$m_{ij}=P_i\wedge Q_j.$

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

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

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

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

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

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

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

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

• Πρότυπο:Cite encyclopedia
• Πρότυπο:Cite encyclopedia
• Πρότυπο:Citation
• Πρότυπο:Citation
• Πρότυπο:Cite journal
• Πρότυπο:Cite journal
• Πρότυπο:Cite journal
• Πρότυπο:Cite journal
• Πρότυπο:Cite journal
• Πρότυπο:Cite book

Δείτε επίσης

• 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 ...
• Foundation Mathematics for Computer Science: A Visual Approach
• Multidimensional Statistical Analysis and Theory of Random Matrices ...
• Quantum Probability and Spectral Analysis of Graphs.
• Symplectic Methods in Harmonic Analysis and in Mathematical Physics...
• Lie Groups: An Introduction Through Linear Groups
• Matrix Algebra: Theory, Computations, and Applications in Statistics ..
• Theory of Logical Calculi: Basic Theory of Consequence Operations
• Matrix Logic: Theory and Applications..

Παραπομπές

• David Poole: Linear Algebra. A Modern Introduction. Cengage Learning 2005, Πρότυπο:ISBN, pp. 265–267 (Πρότυπο:Google books)
• Harvey E. Rose: Linear Algebra. A Pure Mathematical Approach. Springer 2002, Πρότυπο:ISBN, pp. 57–60 (Πρότυπο:Google books)
• Πρότυπο:Citation