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\lor B=[a_{ij}\lor b_{ij}]$ resp $A\land B=[a_{ij}\land b_{ij}].$

Exempel

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

$A={\begin{bmatrix}1&0&1\\0&1&0\end{bmatrix}}\ \ B={\begin{bmatrix}0&1&0\\1&1&0\end{bmatrix}}$

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

$A\lor B={\begin{bmatrix}1\lor 0&0\lor 1&1\lor 0\\0\lor 1&1\lor 1&0\lor 0\end{bmatrix}}={\begin{bmatrix}1&1&1\\1&1&0\end{bmatrix}}$

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

$A\land B={\begin{bmatrix}1\land 0&0\land 1&1\land 0\\0\land 1&1\land 1&0\land 0\end{bmatrix}}={\begin{bmatrix}0&0&0\\0&1&0\end{bmatrix}}$

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}\land b_{1j})\lor (a_{i2}\land b_{2j})\lor \dots \lor (a_{ik}\land 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{matrix}n\\m\end{matrix}}\right\}(m+1)^{-k}$

och $\left\{{\begin{matrix}n\\m\end{matrix}}\right\}$ betecknar ett andra ordningens stirlingtal.[2]

Externa länkar

• Wikimedia Commons har media som rör Binär matris.
  Bilder & media