Binär matris

En binär matris, eller en noll-ett matris, är en matris vars element bara består av 1:or eller 0:or.

Boolska operatorer

De boolska operatorerna ∧ (och) och ∨ (eller) definieras för vanliga boolska variabler b₁ och b₂ genom:

• b₁ ∧ b₂ är 1 om både b₁ = 1 och b₂ = 1, annars 0.
• b₁ ∨ b₂ är 1 om minst en av b₁ och b₂ är 1, annars 0.

Definition av Boolska operatorer för matriser. Låt $A=[a_{ij}]$ och $B=[b_{ij}]$ vara binära matriser med lika antal rader och kolonner. Då definieras A ∨ B och A ∧ B som $A\vee B=[a_{ij}\vee b_{ij}]$ resp $A\wedge B=[a_{ij}\wedge b_{ij}].$

Exempel

Vi har två 1-0 matriser A och B.

$A=\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\end{array}\right]B=\left[\begin{array}{ccc}0& 1& 0\\ 1& 1& 0\end{array}\right]$

Om vi väljer att förena A och B (A ∨ B)

$A\vee B=\left[\begin{array}{ccc}1\vee 0& 0\vee 1& 1\vee 0\\ 0\vee 1& 1\vee 1& 0\vee 0\end{array}\right]=\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 0\end{array}\right]$

Om vi väljer att A och B ska mötas (A ∧ B)

$A\wedge B=\left[\begin{array}{ccc}1\wedge 0& 0\wedge 1& 1\wedge 0\\ 0\wedge 1& 1\wedge 1& 0\wedge 0\end{array}\right]=\left[\begin{array}{ccc}0& 0& 0\\ 0& 1& 0\end{array}\right]$

Boolska produkten

Låt nu A vara en m×k 0-1 matris och b en k×n 0-1 matris. Då definieras den boolska produkten av A och B betecknad A ⊙ B som m×n-matrisen C med $C_{ij}=(a_{i1}\wedge b_{1j})\vee (a_{i2}\wedge b_{2j})\vee \dots \vee (a_{ik}\wedge b_{kj})$

Rekonstruktion från rad- och kolonnsummor

Om elementen i en binär matris kan återskapas från dess rad- och kolonnsummor kallas den på engelska en "lonesum"-matris. [1]

Antalet distinkta n×k-matriser med denna egenskap ges av polybernoullitalet $B_n^{(-k)}$, där

$B_n^{(k)}=\sum _{m=0}^n(-1{)}^{n+m}m!\left\{\begin{array}{c}n\\ m\end{array}\right\}(m+1{)}^{-k}$

och $\left\{\begin{array}{c}n\\ m\end{array}\right\}$ betecknar ett andra ordningens stirlingtal.[2]Mall:Död länk

Externa länkar

• Mall:Commonscat