Binär matris

Från Rilpedia

Hoppa till: navigering, sök

Texten från svenska Wikipedia

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

Innehåll

1 Boolska operatorer
- 1.1 Exempel
2 Boolska produkten
3 Rekonstruktion från rad- och kolonnsummor
4 Se även

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 i j]$ och $B = [b i j]$ 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

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

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})$