On a tomographic equivalence
between (0,1) matrices
A.Frosini and M.Nivat
Dipartimento di Scienze Matematiche ed Informatiche
“Roberto Magari”
Università degli Studi di Siena
All’inizio …
All’inizio …
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
All’inizio …
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
All’inizio …
Teorema: Comunque mi muova nel piano con il tile prescelto, al suo interno
comparirà sempre una ed una sola cella marcata.
(configurazioni del piano con tale proprietà si dicono 1-omogenee)
Teorema: Se consideriamo un tile rettangolare R di dimensione m x n, tutte le
configurazioni 1-omogenee rispetto a R sono invarianti lungo una delle due
direzioni (m,0) o (0,n).
(entrambe in caso di pavimentazioni regolari)
All’inizio …
Potremmo, invece di
una sola cella, marcarne
due o più?
Cosa si può dire delle
configurazioni del piano
che sono k-omogenee?
E quale scenario aggiungendo
un peso (positivo o negativo)
alle celle marcate?
Primi risultati e …
Teorema: Supponiamo di scegliere un tile rettangolare R. Ogni configurazione
del piano che è k-omogenea rispetto a R è sovrapposizione (somma) di
configurazioni che sono 1-omogenee.
1
1 1
1
1 1
1
1 1
1
1
1 1
1
1
1
1
1 1
1 1
1 1
1
1
1 1
1
1
1 1
1
1 1
1
1 1
1 1
1
1
1
1
1
1
1
1 1
1
1
1 1
1
1
1
1
1
Primi risultati e …
Teorema: Supponiamo di scegliere un tile rettangolare R. Ogni configurazione
del piano che è k-omogenea rispetto a R è sovrapposizione (somma) di
configurazioni che sono 1-omogenee.
1
1 1
1
1 1
1
1 1
1
1
1
1
1
1 1
1 1
1 1
1
1 1
1
1
1
1
1
1
1
1 1
1
1 1
1
1
1
1
1
1
1
1 1
1
1
1 1
1
1
1
1 1
1
1
1
1
1
Primi risultati e …
Teorema: Supponiamo di scegliere un tile rettangolare R. Ogni configurazione
del piano che è k-omogenea rispetto a R è sovrapposizione (somma) di
configurazioni che sono 1-omogenee.
… primi problemi aperti
Domanda: E’ possibile trovare una decomposizione di configurazioni
k-omogenee in configurazioni 1-omogenee rispetto ad un qualsiasi tile?
…
Matrici omogenee a coefficienti interi
Associamo un peso
(intero) a ciascun
punto del piano
Consideriamo
configurazioni
k-omogenee
Matrici k-omogenee
a coefficienti interi
Ritagliamone
porzioni
rettangolari
Matrici omogenee a coefficienti interi
Teorema: Una matrice a coefficienti interi positivi è k-omogenea rispetto ad un
tile rettangolare R
se e solo se
è somma di k matrici a coefficienti in {0,1} che sono 1-omogenee rispetto a R.
Lemma: Se M è una matrice a coefficienti interi omogenea rispetto ad un tile
rettangolare R allora per ogni suo elemento (x, y) vale
M (x,y) + M (x+ m, y+ n) = M (x, y+ n) + M (x+ m, y)
per ogni coppia di interi  , .
n
m
+
+
Esempio: matrice 5-omogenea, R di dimensione 3 x 3
12111012011
00001000000
00100200201
01300201200
00001000000
00100200201
02201102101
00001000000
Esempio: matrice 5-omogenea, R di dimensione 3 x 3
12111012011
00001000000
00100200201
01300201200
00001000000
00100200201
02201102101
00001000000
Esempio: matrice 5-omogenea, R di dimensione 3 x 3
12111012011
00001000000
00100200201
01300201200
00001000000
00100200201
02201102101
00001000000
02101002001
00001000000
00100200201
01200101100
00001000000
00100200201
01200101100
00001000000
Esempio: matrice 5-omogenea, R di dimensione 3 x 3
12111012011
00001000000
00100200201
01300201200
00001000000
00100200201
02201102101
00001000000
01101001001
00000000000
00100200200
00200100100
00000000000
00100200200
00200100100
00000000000
02101002001
00001000000
00100200201
01200101100
00001000000
00100200201
01200101100
00001000000
Esempio: matrice 5-omogenea, R di dimensione 3 x 3
12111012011
00001000000
00100200201
01300201200
00001000000
00100200201
02201102101
00001000000
01101001001
00000000000
00100200200
00200100100
00000000000
00100200200
00200100100
00000000000
02101002001
00001000000
00100200201
01200101100
00001000000
00100200201
01200101100
00001000000
00100000000
00000000000
00100200200
00100000000
00000000000
00100200200
00100000000
00000000000
Esempio: matrice 5-omogenea, R di dimensione 3 x 3
12111012011
00001000000
00100200201
01300201200
00001000000
00100200201
02201102101
00001000000
01101001001
00000000000
00100200200
00200100100
00000000000
00100200200
00200100100
00000000000
02101002001
00001000000
00100200201
01200101100
00001000000
00100200201
01200101100
00001000000
00000000000
00000000000
00100100100
00000000000
00000000000
00100100100
00000000000
00000000000
00100000000
00000000000
00100200200
00100000000
00000000000
00100200200
00100000000
00000000000
Matrici omogenee a coefficienti interi
Teorema: Una matrice a coefficienti interi è k-omogenea rispetto ad un tile
rettangolare R
se e solo se
è differenza di due somme di matrici a coefficienti in {0,1} che sono 1-omogenee
rispetto a R.
Inoltre il numero di elementi in ciascuna somma è limitato da
k + { - M(x,y): M(x,y)<0}
oppure
k + { - M(x,y): M(x,y)>0}
Matrice R-nulle
Definizione: Una matrice a coefficienti interi si dice R-nulla se è 0-omogenea
rispetto al tile rettangolare R.
Lo studio delle classi di equivalenza di matrici aventi le stesse R-proiezioni
passa naturalmente dallo studio delle matrici R-nulle.
(la differenza tra due matrici della stessa classe è una matrice R-nulla)
Teorema (Ryser): E’ possibile passare da una matrice ad un’altra avente le
stesse proiezioni orizzontali e verticali tramite una serie di operazioni
elementari.
Teorema (Ryser): Ogni matrice a coefficienti in {-1,0,1} avente proiezioni
orizzontali e verticali nulle è somma di matrici aventi tutti gli elementi nulli
tranne quattro disposti come segue:
M(x0 ,y0 ) = M(x1 ,y1 ) = 1 e M(x0 ,y1 ) = M(x1 ,y0 ) = -1
Matrice R-nulle
Switch nel caso di proiezioni
orizzontali e verticali (Ryser)
Switch nel caso di proiezioni
rispetto ad un tile rettangolare
1
-1
1
Riga n-nulla
1
1
-1
-1
-1
Colonna m-nulla
Matrice R-nulle
Teorema (tipo Ryser): L’insieme delle matrici i cui unici elementi diversi da
zero sono una singola riga n-nulla o una singola colonna m-nulla generano lo
spazio delle matrici R-nulle.
Passo 1: decomponiamo una matrice R-nulla come differenza di due somme di
matrici a coefficienti in {0,1}, H1+ H2+…+ Hk-U1- U2-…- Uk.
(ovviamente il numero delle matrici in ciascuna somma è lo stesso)
Passo 2: scomponiamo ogni coppia del tipo Hi – Ui come somma di righe e
colonne n-nulle e m-nulle.
Matrice R-nulle:esempio con R di dimensione 3 x 3
0
0
0
0
1
0
0
0
0 -1 0
1 0 0
0 0 0
0 -1 0
0 0 1
0 0 0
0 -1 0
0 1 0
0 0 0
1 -1 0
0 0 0
0 0 0
0 -1 1
0 0 0
0 0 0
0 0 0
muovo gli 1 nella
prima colonna
0
1
0
0
0
0
0
0
0 0
-1 0
0 0
0 0
-1 1
0 0
0 0
0 0
0
1
0
0
0
0
0
0
=
ottenendo
+
0 0
1 -1
0 0
0 0
0 0
0 0
0 0
1 0
0 0
0 1
0 0
0 0
0 0
0 0
0 0
-1 1
0 0 0 0 0
-1 0 1 -1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 -1 1 0 1
0 0
1 -1
0 0
0 0
0 0
0 0
0 0
-1 0
0
1
0
0
1
0
0
1
0 -1 0
0 0 1
0 0 0
0 -1 0
0 0 1
0 0 0
0 -1 0
0 0 1
0 0 0
0 -1 1
0 0 0
0 0 0
0 -1 1
0 0 0
0 0 0
0 -1 1
0
0
0
0
0
0
0
0
0 0
-1 1
0 0
0 0
-1 1
0 0
0 0
-1 1
0
0
0
0
0
0
0
0
Matrice R-nulle:esempio con R di dimensione 3 x 3
0
1
0
0
1
0
0
1
0 -1 0
0 0 1
0 0 0
0 -1 0
0 0 1
0 0 0
0 -1 0
0 0 1
0 0 0
0 -1 1
0 0 0
0 0 0
0 -1 1
0 0 0
0 0 0
0 -1 1
muovo i -1 dalla
prima riga alla
seconda
0
0
0
0
0
0
0
0
0 0
-1 1
0 0
0 0
-1 1
0 0
0 0
-1 1
0
0
0
0
0
0
0
0
=
ottenendo
+
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1 0
-1 0
0 0
1 0
-1 0
0 0
1 0
-1 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0 1 0
0 -1 0
0 0 0
0 1 0
0 -1 0
0 0 0
0 1 0
0 -1 0
0
1
0
0
1
0
0
1
0 0 0 0 0 0 0 0 0 0
0 -1 1 0 -1 1 0 -1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 -1 1 0 -1 1 0 -1 1 0
0 0 0 0 0 0 0 0 0 0
0 00 0 0 0 0 0 0 0
0 -1 1 0 -1 1 0 -1 1 0
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000
000011111111111110000111110000111111110000001111100001111111111111000
000011111111111110000111110000111111110000001111100001111111111111000
000011111111111110000111110000111111111000001111100001111111111111000
000011111000000000000111110000111111111000001111100001111100000000000
000011111000000000000111110000111111111100001111100001111100000000000
000011111000000000000111110000111111111100001111100001111100000000000
000011111000000000000111110000111110111110001111100001111100000000000
000011111111111110000111110000111110111110001111100001111111111000000
00001111111111111000011111000011111001111100111110000111111111100000
000011111111111110000111110000111110011111001111100001111111111000000
000011111000000000000111110000111110001111101111100001111100000000000
000011111000000000000111110000111110001111101111100001111100000000000
000011111000000000000111110000111110000111111111100001111100000000000
000011111000000000000111110000111110000111111111100001111100000000000
000011111000000000000111110000111110000011111111100001111111111111000
000011111000000000000111110000111110000011111111100001111111111111000
000011111000000000000111110000111110000001111111100001111111111111000
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000
000000000000000000000000000000000000000000000000000000000000000 000000