Mantıksal matris - Logical matrix

Bir mantıksal matris , ikili matris , ilişki matrisi , Boole matris ya da (0,1) matris a, matris gelen girişlerle Boole alan B = {0, 1}. Böyle bir matris, bir çift sonlu küme arasındaki ikili ilişkiyi temsil etmek için kullanılabilir .

Bir ilişkinin matris gösterimi

Eğer R , sonlu indeksli X ve Y kümeleri arasında bir ikili ilişki ise (yani R ⊆ X × Y ), o zaman R mantıksal matris M ile temsil edilebilir ve satır ve sütun indeksleri sırasıyla X ve Y öğelerini indeksler . M girişleri şu şekilde tanımlanır:

${\displaystyle M_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R\\0&(x_{i},y_{j})\değil \R \end{durumlar}}}$

Matrisin satır ve sütun numaralarını belirtmek için, X ve Y kümeleri pozitif tamsayılarla indekslenir: i , 1'den X'in kardinalitesine (boyutu) ve j , 1'den Y'nin kardinalitesine kadar değişir . Daha fazla ayrıntı için dizine alınmış kümelerle ilgili girişe bakın .

Örnek

{1, 2, 3, 4} kümesindeki R ikili ilişkisi , aRb'nin ancak ve ancak a , b'yi kalansız eşit olarak bölerse geçerli olacağı şekilde tanımlanır . Örneğin, 2 R 4 tutar çünkü 2, 4'ü bir kalan bırakmadan böler, ancak 3 R 4 tutmaz çünkü 3, 4'ü böldüğünde 1 kalan olur. Aşağıdaki küme, R bağıntısının geçerli olduğu çiftler kümesidir .

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

Mantıksal matris olarak karşılık gelen gösterim:

${\displaystyle {\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}}}$ ki bu, her sayı kendini böldüğü için birlerin köşegenini içerir.

Diğer örnekler

• Bir permütasyon matrisi , tüm sütun ve satırlarının her biri tam olarak bir sıfır olmayan öğeye sahip bir (0,1) matrisidir .
  • Bir Kostas dizisi bir permütasyon matrisinin özel bir durumdur
• Kombinatorik ve sonlu geometrideki bir insidans matrisi , bir geometrinin noktaları (veya köşeleri) ve çizgileri, bir blok tasarımının blokları veya bir grafiğin kenarları (ayrık matematik) arasındaki insidansı belirtmek için olanlara sahiptir.
• Varyans analizindeki bir tasarım matrisi , sabit satır toplamları olan bir (0,1) matrisidir .
• Mantıksal bir matris , grafik teorisinde bir bitişik matrisi temsil edebilir : simetrik olmayan matrisler yönlendirilmiş grafiklere karşılık gelir , simetrik matrisler sıradan grafiklere ve diyagonal üzerindeki 1 , karşılık gelen tepe noktasındaki bir döngüye karşılık gelir.
• Biadjacency matrisi basit bir bölgesinin yönsüz bipartit grafik bir (0,1) -Matriks ve herhangi bir (0,1) -Matris bu şekilde ortaya çıkar.
• Bir listesini ana faktörler m kare içermeyen , n Pürüzsüz sayı bir şekilde tanımlanabilir m x π ( n ) π olduğu (0,1) -Matris, ana sayma fonksiyonu ve bir _ij 1 ise, ve yalnızca j asal böler inci i inci sayı. Bu gösterim, ikinci dereceden elek çarpanlarına ayırma algoritmasında kullanışlıdır .
• Yalnızca iki renkte piksel içeren bir bitmap görüntüsü , 0'ların bir rengin piksellerini ve 1'lerin diğer rengin piksellerini temsil ettiği bir (0,1) matrisi olarak temsil edilebilir.
• Go oyununda oyun kurallarını kontrol etmek için ikili bir matris kullanılabilir.

Bazı özellikler

Matris temsili eşitliği ilişkisi sonlu dizisi üzerinde özdeşlik matrisi diğerleri, hepsi 0 Daha genel bir ilişki halinde iken, I, Girişleri diyagonal tüm 1 olan matris R tatmin I ⊂ R , daha sonra R bir yansımalı bağıntıdır .

Boolean alan bir olarak görülürse semiring için ek karşılık, mantıksal VEYA ve çarpma mantıksal ve , matris temsili bileşimin iki ilişkilerin eşittir matris ürününün bu ilişkilerin matris temsilleri. Bu çarpım, O( n ² ) beklenen zamanda hesaplanabilir .

İkili matrisler üzerindeki işlemler sıklıkla modüler aritmetik mod 2 cinsinden tanımlanır —yani, elemanlar Galois alanının GF (2) = ℤ ₂ elemanları olarak ele alınır . Çeşitli temsillerde ortaya çıkarlar ve bir dizi daha sınırlı özel biçime sahiptirler. Örneğin, XOR-tatmin edilebilirliğinde uygulanırlar .

Tat sayısı m -by- n ikili matrisler 2 eşittir ^mn ve bu nedenle sınırlı olup.

kafes

Let , n ve m, verilecek ve izin U tüm mantıksal kümesini belirtir m x n matrisler. Daha sonra U , bir yer alır kısmi sipariş verdiği

${\displaystyle m\subset n\quad {\text{ne zaman}}\quad \forall i,j\quad m_{ij}=1\n_{ij}=1.} anlamına gelir$

Aslında U , bileşen bazında uygulanan iki matris arasındaki ve & veya işlemleriyle bir Boole cebiri oluşturur . Mantıksal bir matrisin tümleyeni, tüm sıfırları ve birleri karşıtlarıyla değiştirerek elde edilir.

Her mantıksal matris a = ( a _ij ) bir devrik a ^T = ( a _ji ) sahiptir. Varsayalım bir sütun veya satır aynı sıfır mantıksal bir matristir. Daha sonra matris ürün, Boole aritmetiği kullanılarak, bir ^T içeriyorsa m x m kimlik matrisi ve ürün aa ^T içeren n x n kimlik.

Matematiksel bir yapı olarak, Boole cebri U , dahil edilerek sıralanmış bir kafes oluşturur ; ayrıca matris çarpımından dolayı çarpımsal bir kafestir .

Her mantıksal matris U bir ikili ilişkiye karşılık gelmektedir. U üzerinde listelenen bu işlemler ve sıralama, matris çarpımının ilişkilerin bileşimini temsil ettiği bir ilişkiler hesabına karşılık gelir .

mantıksal vektörler

Eğer m ya da n, daha sonra bir eşittir m x n mantıksal matriks (M _{i j} ) mantıksal vektördür. Eğer m = 1 vektör, bir satır vektörüdür ve eğer n = 1, bir sütun vektörüdür. Her iki durumda da bire eşit olan indeks, vektörün ifadesinden çıkarılır.

Diyelim ki ve iki mantıksal vektör. Dış ürün ve P ve Q, bir in sonuçları m x n dikdörtgen ilişkisi : ${\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}.}$ Böyle bir matrisin satırlarının ve sütunlarının yeniden sıralanması, hepsini matrisin dikdörtgen bir parçasında toplayabilir.

h tüm birlerin vektörü olsun . O zaman v keyfi bir mantıksal vektörse, R = vh ^T ilişkisi v tarafından belirlenen sabit satırlara sahiptir . Gelen ilişkilerin hesabı böyle bir R ' , bir adlandırılır vektör . Özel bir örnek, evrensel bağıntıdır hh ^T .

Verilen bir R bağıntısı için, R'de bulunan bir maksimal, dikdörtgen ilişki, R'de bir kavram olarak adlandırılır . İlişkiler, kavramlara ayrıştırılarak ve daha sonra indüklenen kavram kafesine dikkat edilerek incelenebilir .

Grup benzeri yapılar
	bütünlük	ilişkilendirme	Kimlik	ters çevrilebilirlik	değişebilirlik
yarıgrupoid	Gereksiz	Gerekli	Gereksiz	Gereksiz	Gereksiz
Küçük Kategori	Gereksiz	Gerekli	Gerekli	Gereksiz	Gereksiz
grupoid	Gereksiz	Gerekli	Gerekli	Gerekli	Gereksiz
magma	Gerekli	Gereksiz	Gereksiz	Gereksiz	Gereksiz
yarıgrup	Gerekli	Gereksiz	Gereksiz	Gerekli	Gereksiz
birim magma	Gerekli	Gereksiz	Gerekli	Gereksiz	Gereksiz
Döngü	Gerekli	Gereksiz	Gerekli	Gerekli	Gereksiz
yarı grup	Gerekli	Gerekli	Gereksiz	Gereksiz	Gereksiz
Ters Yarıgrup	Gerekli	Gerekli	Gereksiz	Gerekli	Gereksiz
monoid	Gerekli	Gerekli	Gerekli	Gereksiz	Gereksiz
değişmeli monoid	Gerekli	Gerekli	Gerekli	Gereksiz	Gerekli
Grup	Gerekli	Gerekli	Gerekli	Gerekli	Gereksiz
değişmeli grup	Gerekli	Gerekli	Gerekli	Gerekli	Gerekli
^α Birçok kaynakta kullanılanKapanış, farklı şekilde tanımlansa da bütünlüğe eşdeğer bir aksiyomdur.

Mantıksal bir R matrisi oluşturan "gereksiz"in 0 ve "gerekli"nin 1 ile gösterilebildiği grup benzeri yapılar tablosunu düşünün . RR ^T öğelerini hesaplamak için bu matrisin satırlarındaki mantıksal vektör çiftlerinin mantıksal iç çarpımını kullanmak gerekir. Bu iç çarpım 0 ise, sıralar diktir. Aslında, yarıgrup döngüye ortogonaldir, küçük kategori kuasigruba ortogonaldir ve grupoid magmaya ortogonaldir. Sonuç olarak, RR ^T'de 0'lar vardır ve evrensel bir bağıntı olamaz .

Satır ve sütun toplamları

Mantıksal bir matristeki tüm 1'leri toplamak, önce satırları toplamak veya önce sütunları toplamak olmak üzere iki şekilde gerçekleştirilebilir. Satır toplamları eklendiğinde, toplam sütun toplamları eklendiğindekiyle aynıdır. İn geometrisi , matris bir şekilde yorumlanır sıklığı matris sıraları "blok" (noktaları yapılan genellemede hat) olarak "puan" ve sütunlara tekabül eden. Bir satır toplamına nokta derecesi denir ve bir sütun toplamı blok derecesidir . Tasarım Teorisindeki Önerme 1.6 , nokta derecelerinin toplamının blok derecelerinin toplamına eşit olduğunu söyler.

Alandaki erken bir sorun, " verilen nokta dereceleri ve blok dereceleriyle (veya matris dilinde, v × tipinde bir (0,1) matrisinin varlığı için) bir geliş yapısının varlığı için gerekli ve yeterli koşulları bulmaktı. b verilen satır ve sütun toplamları ile." Böyle bir yapı bir blok tasarımıdır .

Ayrıca bakınız

• matris listesi
• Binatorix (bir ikili De Bruijn simit)
• Bit dizisi
• Redheffer matrisi

Notlar

Referanslar

• Hogben, Leslie (2006), Lineer Cebir El Kitabı (Ayrık Matematik ve Uygulamaları) , Boca Raton: Chapman & Hall/CRC, ISBN 978-1-58488-510-8, § 31.3, İkili Matrisler
• Kim, Ki Hang (1982), Boolean Matris Teorisi ve Uygulamaları , ISBN 978-0-8247-1788-9
• HJ Ryser (1957) " Sıfır ve birlerden oluşan matrislerin kombinatoryal özellikleri", Canadian Journal of Mathematics 9: 371–7.
• Ryser, HJ (1960) " Sıfır ve bir matrislerinin izleri", Canadian Journal of Mathematics 12: 463–76.
• Ryser, HJ (1960) "Sıfırların ve Birlerin Matrisleri", Amerikan Matematik Derneği Bülteni 66: 442-64.
• DR Fulkerson (1960) "Sıfır izli sıfır-bir matrisler", Pacific Journal of Mathematics 10; 831–6
• DR Fulkerson & HJ Ryser (1961) "(0, 1)-matrislerin genişlikleri ve yükseklikleri", Canadian Journal of Mathematics 13: 239–55.
• LR Ford Jr. & DR Fulkerson (1962) § 2.12 " 0'lar ve 1'lerden oluşan matrisler", sayfa 79 ila 91, Ağlarda Akışlar , Princeton University Press MR 0159700

Dış bağlantılar

• "Mantıksal matris" , Matematik Ansiklopedisi , EMS Press , 2001 [1994]