Binär matris

Från Wikipedia
Hoppa till: navigering, sök

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[redigera | redigera wikitext]

De boolska operatorerna ∧ (och) och ∨ (eller) definieras för vanliga boolska variabler b1 och b2 genom:

  • b1b2 är 1 om både b1 = 1 och b2 = 1, annars 0.
  • b1b2 är 1 om minst en av b1 och b2 ä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\or B=[a_{ij}\or b_{ij}] resp A\and B=[a_{ij}\and b_{ij}].

Exempel[redigera | redigera wikitext]

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 \or B =\begin{bmatrix}
1 \or 0 & 0 \or 1 & 1 \or 0 \\
0 \or 1 & 1 \or 1 & 0 \or 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 \and B =\begin{bmatrix}
1 \and 0 & 0 \and 1 & 1 \and 0 \\
0 \and 1 & 1 \and 1 & 0 \and 0  \end{bmatrix}=
\begin{bmatrix}
0 & 0 & 0 \\
0 & 1 & 0\end{bmatrix}

Boolska produkten[redigera | redigera wikitext]

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}\and b_{1j}) \or (a_{i2}\and b_{2j}) \or \dots \or (a_{ik}\and b_{kj})

Rekonstruktion från rad- och kolonnsummor[redigera | redigera wikitext]

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]

Se även[redigera | redigera wikitext]