Kroeneker carpimi ve iliskiler

Question

$A \in \mathbb{R}^{n \times m}$ ve $B \in \mathbb{R}^{p \times q}$ matrisleri icin kroeneker carpimi

$C \in \mathbb{R}^{np \times mq}$  bir matris veriyor ve su sekilde tanimlaniyor

$C = \begin{bmatrix}    a_{11} b_{11} & a_{11} b_{12} & \cdots & a_{11} b_{1q} &                    \cdots & \cdots & a_{1n} b_{11} & a_{1n} b_{12} & \cdots & a_{1n} b_{1q} \\    a_{11} b_{21} & a_{11} b_{22} & \cdots & a_{11} b_{2q} &                    \cdots & \cdots & a_{1n} b_{21} & a_{1n} b_{22} & \cdots & a_{1n} b_{2q} \\    \vdots & \vdots & \ddots & \vdots & & & \vdots & \vdots & \ddots & \vdots \\    a_{11} b_{p1} & a_{11} b_{p2} & \cdots & a_{11} b_{pq} &                    \cdots & \cdots & a_{1n} b_{p1} & a_{1n} b_{p2} & \cdots & a_{1n} b_{pq} \\    \vdots & \vdots & & \vdots & \ddots & & \vdots & \vdots & & \vdots \\    \vdots & \vdots & & \vdots & & \ddots & \vdots & \vdots & & \vdots \\    a_{m1} b_{11} & a_{m1} b_{12} & \cdots & a_{m1} b_{1q} &                    \cdots & \cdots & a_{mn} b_{11} & a_{mn} b_{12} & \cdots & a_{mn} b_{1q} \\    a_{m1} b_{21} & a_{m1} b_{22} & \cdots & a_{m1} b_{2q} &                    \cdots & \cdots & a_{mn} b_{21} & a_{mn} b_{22} & \cdots & a_{mn} b_{2q} \\    \vdots & \vdots & \ddots & \vdots & & & \vdots & \vdots & \ddots & \vdots \\    a_{m1} b_{p1} & a_{m1} b_{p2} & \cdots & a_{m1} b_{pq} &                    \cdots & \cdots & a_{mn} b_{p1} & a_{mn} b_{p2} & \cdots & a_{mn} b_{pq} \end{bmatrix}$

 

$A$ ve $B$ matrisleri bir birer iliski temsil ediyor olsun [ $x\sim  y \iff A_{x,y} = 1$]. Eger A ve B nin temsil ettigi iliski

refleksif ve transitif ise $A \text{ kron } B$ ve $B \text{ kron } A$ nin ifade ettigi iliskiler de gecisken ve transitiftir.

Ifadesini nasil ispatlariz ?

Comments

Bir ilişkiyi (bağıntıyı) temsil eden matrisin, kare matris olması gerekir değil mi?

---

Evet hocam kare matris olmasi gerekir. Yukaridaki $A$ ve $B$ matrisleri kroeneker carpiminin genel tanimini vermek icin $\mathbb{R}^{n \times m}$ olarak tanimladim. Asagidaki ($A$ ve $B$ matrisleri bir iliski temsil ediyor olsun kismi) $A$ ve $B$ matrisleri ise $\{0,1\}^{n\times n}$ ve $\{0,1\}^{m\times m}$ elemani. Belirtmem gerekirdi sanirim

Answer 1

Sanırım şöyle oluyor:

$\beta_1,\ X$ üzerinde bir bağıntı  ve $\beta_2,\ Y$ üzerinde bir bağıntı ise,

$(x,y){\beta} (x',y')\Leftrightarrow (x{\beta_1} x') \wedge (y{\beta_2} y' ),\quad X\times Y$ üzerinde bir bağıntı olur.

Ayrıca:

$\beta_1$ ve $\beta_2$ yansımalı (refleksif) ise $\beta$ da yansımalı olur (göster)

$\beta_1$ ve $\beta_2$ geçişmeli (transitif) ise $\beta$ da geçişmeli olur (göster).

($X$ ve $Y$ sonlu ise) $\beta_1$ in matrisi $A$, $\beta_2$ in matrisi $B$ olsun.

(Bu durumda) $\beta$ nın matrisi $A\,\textbf{Kron}\,B$ olur. (Bunu tam kontrol etmedim, hissettim, bunu sen kontrol et)

Buna güvenerek:

$A\,\textbf{Kron}\,B$ nin tanımladığı bağıntı (=$\beta$) yansımalı ve geçişmeli olur

Comments

Hocam nasil hissetiniz diye sorabilir miyim ?

Arastirmalarim sonucunda dediginiz ozelligi cizgelerde saglayan (her iliskiyi bir cizge gibi gorebiliriz sanirim iliski matrisini , adjecency-matris (turkcesini bilemiyorum) gibi gorursek) ve sonuc cizgesini,  cizgelerin adjecency-matrislerinin kroenecker carpimi ile hesaplanan in bir carpma buldum.

Yansimali oldugunu gostermek kolay. cunku $\beta_i$ ler yansitmali. Sanirim transitif icin de ayni mantigi kullaniyoruz yarin bakacagim.

Soru hakkinda biraz daha bilgi vermek isterim.

 

Sonlu bir kume uzerindeki topolojileri bulan bir program yazmak istiyoruz.  Naiv bir bicimde bakarsak $n$ elemanli bir kume icin arama uzayimiz $2^{(2^n)}$ boyutunda.

Sonlu topolojiler ile preorderlar (yansimali ve gecismeli iliskiler) arasinda birebir bir iliski oldugunu ogrendik. sonra bu topolojileri yarattik.  Arama uzayimiz $(2^{n\times n})$ oldu.

Suana kadar farkettigimiz seyler :

$X,Y,Z,W \in \{0,1\}^{n\times n}$ ve $T ,\in \{0,1\}^{m\times m}$   yukaridaki sartlari saglayan birer iliski ise :

 

1. $\begin{pmatrix} X & 0 \\ 0 & T \end{pmatrix}$  (bunu gostermek de gorece rahat) [buna topoloji toplama desek ?]
2. $X \text{ kron } T$ [ buna topoloji carpma desek ?]
3. $X^T$ [kapali kumelerin olusturdugu topoloji ?]

4. $X \text{ hadamard } Y$

5. $\begin{pmatrix} X & (0 (\text{ veya } 1))_{n \times m } \\ (1 (\text{ veya } 0))_{m \times n } & T \end{pmatrix}$

iliskileri de bunlari sagliyor (en azindan numerik olarak  )

Matrisleri carparken ve toplarken matris elemanlarini $bool$ cebirinden geliyormus gibi davraniyorum [$1+1=1$](mantikli mi acaba bu ).

Iliski matrisinin diagonalinde $1$ var ise iliskiye yansimali diyorum.

Iliski matrisi $X$, butun $i,j$ler icin $(X^2)_{i,j} \leq X_{i,j}$ yi sagliyorsa $X$ e gecismeli diyorum.

 

Bu gibi bagintilari kullanarak arama uzayimizi daha da dusurmek istiyorum.

 

Bunun disinda sunu dusunuyoruz:

Iliski matrisi $X \in {0,1}^{n\times n}$  alip kume ailesi veren bir fonksyon tanimlarsak

$B(X)=\{X_i | X_i = \{ j | X_{ij}=1\} \}$ .

Soyle bir iddiamiz var :

$X=(\{1,\cdots,n\}$

$B(X)$, $X$ uzerinde bir topoloji icin bir bazdir.

 

Sitede bu konuyla ilgili bir cok soru var aslinda