Logická matice - Logical matrix

Logické matice , s binární matricí , vztah matice , Logická matice , nebo (0,1) matice je matice s položkami z booleovské domény B = {0, 1}. Takovou matici lze použít k reprezentaci binárního vztahu mezi dvojicí konečných množin .

Maticová reprezentace vztahu

Pokud R je binární relace mezi konečnými indexovanými množinami X a Y (tedy R ⊆ X × Y ), pak R může být reprezentována logickou maticí M, jejíž indexy řádků a sloupců indexují prvky X a Y , v takovém pořadí, že položky M jsou definovány:

${\ Displaystyle M_ {i, j} = {\ begin {cases} 1 & (x_ {i}, y_ {j}) \ in R \\ 0 & (x_ {i}, y_ {j}) \ not \ in R \ end {cases}}}$

Aby bylo možné určit počty řádků a sloupců matrice, sady X a Y jsou indexovány s kladných celých čísel: i se pohybuje v rozmezí od 1 do mohutnosti (velikost) X a j se pohybuje od 1 do mohutnost Y . Další podrobnosti najdete v záznamu o indexovaných sadách .

Příklad

Binární relace R na množině {1, 2, 3, 4} je definována tak, že aRb platí právě tehdy, pokud a dělí b rovnoměrně, beze zbytku. Například, 2 R 4 má, protože 2 dělí 4 beze zbytku, ale 3 R 4 neplatí, protože při 3 dělí 4 je zbytek 1. Následující sada je množina dvojic, pro které je poměr R drží.

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}

Odpovídající reprezentace jako logická matice je:

${\ displaystyle {\ begin {pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \ end {pmatrix}}}$ který zahrnuje úhlopříčku jedniček, protože každé číslo se rozděluje samo.

Další příklady

• Permutace matice je (0,1) -matrix, všichni jehož sloupců a řádků každý mít přesně jeden nenulový prvek.
  • Costas pole je zvláštní případ permutačního matrice
• Incidenční matice v kombinatorika a konečné geometrie má ty, které indikují výskyt mezi body (nebo vrcholy) a linie do geometrie, blocích blokovém provedení , nebo okrajů grafu (diskrétní matematiky)
• Konstrukce matrice v analýze rozptylu je (0,1) -matrix s konstantními částkami řádků.
• Logická matice může v teorii grafů představovat přilehlou matici : nesymetrické matice odpovídají směrovaným grafům , symetrické matice běžným grafům a 1 na diagonále odpovídá smyčce v odpovídajícím vrcholu.
• Biadjacency matrice z jednoduchého, neorientovaný bipartitní graf je (0,1) -matrix, a jakýkoli (0,1) -matrix vzniká tímto způsobem.
• Prvotní faktory seznamu m bez čtverců , n- hladkých čísel lze popsat jako matici m × π ( n ) (0,1), kde π je funkce počítání prvočísel a a _ij je 1, pokud a pouze v případě, že j. prvočíslo dělí i té číslo. Tato reprezentace je užitečná v algoritmu kvadratického faktoringu síta .
• Bitmapový obraz obsahující pixely pouze ve dvou barev může být reprezentován jako (0,1) -matrix, ve kterém 0 reprezentují pixelů jedné barvy a 1 reprezentují pixely jiné barvy.
• Ke kontrole herních pravidel ve hře Go lze použít binární matici

Některé vlastnosti

Maticová reprezentace vztahu rovnosti na konečné množině je matice identity I, tj. Matice, jejíž záznamy na diagonále jsou všechny 1, zatímco ostatní jsou všechny 0. Obecněji, pokud vztah R splňuje I ⊂ R , pak R je reflexivní vztah .

Pokud je booleovská doména chápána jako semiring , kde sčítání odpovídá logickému OR a násobení logickým AND , je maticová reprezentace složení dvou vztahů stejná jako maticový součin maticových reprezentací těchto vztahů. Tento produkt lze vypočítat v očekávaném čase O ( n ² ).

Operace s binárními maticemi jsou často definovány pomocí modulárního aritmetického režimu 2 - to znamená, že prvky jsou považovány za prvky Galoisova pole GF (2) = ℤ ₂ . Vznikají v různých zobrazeních a mají řadu omezenějších speciálních forem. Aplikují se např. V uspokojivosti XOR .

Počet odlišných m -by- n binárních matic se rovná 2 ^mn , a je tedy konečný.

Mříž

Nechť je dáno n a m a U značí množinu všech logických m × n matic. Pak má U částečné pořadí dané

${\ Displaystyle m \ subset n \ quad {\ text {when}} \ quad \ forall i, j \ quad m_ {ij} = 1 \ implikuje n_ {ij} = 1.}$

Ve skutečnosti U tvoří booleovskou algebru s operacemi a & nebo mezi dvěma maticemi aplikovanými komponentně. Doplněk logické matice se získá výměnou všech nul a jedniček za jejich opak.

Každý logický matice A = (A _ij ) má přemístit ^T = (a _dži ). Předpokládejme, že a je logická matice bez sloupců nebo řádků identicky nulová. Poté se matrice produktu, pomocí logických aritmetiku, je ^T A obsahuje m × m matice identity , a produkt aa ^T obsahuje n × n identitu.

Jako matematické struktury, logická algebra U tvoří mříž objednal zahrnutím ; navíc se jedná o multiplikativní mřížku v důsledku multiplikace matice.

Každá logická matice v U odpovídá binární relaci. Tyto uvedené operace na U a řazení odpovídají počtu vztahů , kde násobení matice představuje složení vztahů .

Logické vektory

Pokud m nebo n se rovná jedné, pak logická matice m × n (M _{i j} ) je logický vektor. Pokud m = 1, vektor je řádkový vektor a pokud n = 1 je to sloupcový vektor. V obou případech je index rovnající se jednomu vypuštěn z denotace vektoru.

Předpokládejme, že a jsou dva logické vektory. Vnější produkt z P a Q má za výsledek m x n obdélníkovým vztahu : ${\ Displaystyle (P_ {i}), \ quad i = 1,2, \ ldots, m}$${\ Displaystyle (Q_ {j}), \ quad j = 1,2, \ ldots, n}$

${\ Displaystyle M_ {ij} = P_ {i} \ land Q_ {j}.}$ Opětovné uspořádání řádků a sloupců takové matice může shromáždit všechny do obdélníkové části matice.

Nechť h je vektorem všech. Pak je -li v libovolný logický vektor, má vztah R = vh ^T konstantní řádky určené v . V počtu vztahů se takové R nazývá vektor . Konkrétním příkladem je univerzální vztah hh ^T .

Pro dané relace R , je maximální, obdélníkový relace obsažené v R , se nazývá koncept R . Vztahy lze studovat rozkladem na koncepty a následným zaznamenáním indukované koncepční mřížky .

Skupinové struktury
	Celek	Asociativita	Identita	Invertibilita	Komutativita
Semigroupoid	Nepotřebný	Požadované	Nepotřebný	Nepotřebný	Nepotřebný
Malá kategorie	Nepotřebný	Požadované	Požadované	Nepotřebný	Nepotřebný
Groupoid	Nepotřebný	Požadované	Požadované	Požadované	Nepotřebný
Magma	Požadované	Nepotřebný	Nepotřebný	Nepotřebný	Nepotřebný
Quasigroup	Požadované	Nepotřebný	Nepotřebný	Požadované	Nepotřebný
Unital Magma	Požadované	Nepotřebný	Požadované	Nepotřebný	Nepotřebný
Smyčka	Požadované	Nepotřebný	Požadované	Požadované	Nepotřebný
Semigroup	Požadované	Požadované	Nepotřebný	Nepotřebný	Nepotřebný
Inverzní semigroup	Požadované	Požadované	Nepotřebný	Požadované	Nepotřebný
Monoidní	Požadované	Požadované	Požadované	Nepotřebný	Nepotřebný
Komutativní monoid	Požadované	Požadované	Požadované	Nepotřebný	Požadované
Skupina	Požadované	Požadované	Požadované	Požadované	Nepotřebný
Abelianská skupina	Požadované	Požadované	Požadované	Požadované	Požadované
^α Uzávěr, který se používá v mnoha zdrojích, je ekvivalentní axiom k totalitě, i když je definován odlišně.

Předpokládejme tabulku skupiny struktur, kde „nadbytečný“ mohou být označeny 0, a „požadované“ jsou označeny odkazovými značkami 1, tvořící logické matice R . Pro výpočet prvků RR ^T je nutné použít logický vnitřní součin dvojic logických vektorů v řadách této matice. Pokud je tento vnitřní součin 0, pak jsou řádky ortogonální. Ve skutečnosti je semigroup ortogonální na smyčku, malá kategorie je ortogonální na quasigroup a groupoid je ortogonální na magma. V důsledku toho jsou v RR ^{T 0} a nejde o univerzální vztah .

Součty řádků a sloupců

Sčítání všech 1 do logické matice lze provést dvěma způsoby, nejprve sečtením řádků nebo nejprve sečtením sloupců. Když jsou sečteny součty řádků, je součet stejný jako při přidání součtů sloupců. V geometrii dopadů je matice interpretována jako matice dopadu s řádky odpovídajícími „bodům“ a sloupce jako „bloky“ (zobecňující čáry tvořené body). Součet řádků se nazývá jeho bodový stupeň a součet sloupců je stupeň bloku . Tvrzení 1.6 v teorii designu říká, že součet bodových stupňů se rovná součtu blokových stupňů.

Počátečním problémem v této oblasti bylo „najít nezbytné a dostatečné podmínky pro existenci struktury výskytu s danými bodovými stupni a blokovými stupni (nebo v maticovém jazyce pro existenci matice (0,1) typu v × b s danými součty řádků a sloupců. "Taková struktura je bloková konstrukce .

Viz také

• Seznam matic
• Binatorix (binární De Bruijn torus)
• Bitové pole
• Redhefferova matice

Poznámky

Reference

• Hogben, Leslie (2006), Handbook of Linear Algebra (Discrete Mathematics and its Applications) , Boca Raton: Chapman & Hall/CRC, ISBN 978-1-58488-510-8, § 31.3, Binární matice
• Kim, Ki Hang (1982), Boolean Matrix Theory and Applications , ISBN 978-0-8247-1788-9
• HJ Ryser (1957) „Kombinatorické vlastnosti matic nul a jednotek“, Canadian Journal of Mathematics 9: 371–7.
• Ryser, HJ (1960) „Stopy matic nul a jednotek“, Canadian Journal of Mathematics 12: 463–76.
• Ryser, HJ (1960) „Matice nul a onů“, Bulletin Americké matematické společnosti 66: 442–64.
• DR Fulkerson (1960) „Matice nula jedna s nulovou stopou“, Pacific Journal of Mathematics 10; 831–6
• DR Fulkerson a HJ Ryser (1961) „Šířky a výšky (0, 1) matic“, Canadian Journal of Mathematics 13: 239–55.
• LR Ford Jr. & DR Fulkerson (1962) § 2.12 „Matice složené z 0 a 1“, strany 79 až 91 v Toky v sítích , Princeton University Press MR 0159700

externí odkazy

• "Logická matice" , Encyklopedie matematiky , EMS Press , 2001 [1994]