In this thesis we deal with the problem to find particular forms for incidence matrices of incidence structures between t-subsets vs k-subsets (L_t,L_k; \subseteq). Denote by X a set of finite size n, say X={1,2,…,n} and by L the power set of X. We partition it into the sets L_i, for i=0,…,n; where L_i is the set of subsets of X of size i; i.e. the elements of L_i are the i-subsets of X. (L_t,L_k; \subseteq) is the incidence structure so defined: for x in L_t and y in L_k, x and y are incident if and only if x \subseteq y. Its incidence matrix is denoted by W_{tk}. R.M.Wilson finds a diagonal form for W_{tk} with purely combinatorics methods. For shortness we will refer to this result as ``Wilson's Theorem''. Many other authors have dealt with the same problem. The heart of the thesis is Chapter 4 where we give a new proof of Wilson's Theorem via linear maps. We construct a new algebraic structure: let G \subseteq Sym(n) be a permutation group on X. The action of G on X induces a natural action on L. So G acts on any L_i. This action partitions each L_i into orbits. For 0≤ t≤ k≤ n, we consider the tactical decomposition of the incidence structure (L_t,L_k; \subseteq). Then we can define two matrices X^+_{tk} and X^-_{tk} called the incidence matrices of the tactical decomposition. If G={1} then the orbits of G correspond to the subsets and X^+_{tk}=W^T_{tk} is the transpose matrix of the incidence structure (L_t,L_k; \subseteq). In Chapter 5 we will give some new results related to the invariant factors of X^+_{tk}. In Chapter 4 we introduce an algebra related to the boolean poset L, in order to give our new proof of Wilson's Theorem. Let R be one of Q, R or C, we construct the vector space RL of formal sums of elements of L with coefficients in R We want to extend the \subseteq relation from L into RL. To do this we define incidence maps: ɛ and δ such that the matrices associated to ɛ and δ, with respect to the bases L_t and L_k, are W^T_{tk} and W_{tk}, respectively. The results of Chapter 4 are achieved considering a particular basis for RL_i. Given 0≤ t≤ n-1 and k=t+1, we construct the symmetric maps δɛ, and we decompose RL_t into direct sum of eigenspaces of δɛ, denoted by E_{t,i}, with i=0,…,t’, where t’=min{t,n-t}. We prove that the eigenspaces E_{t,i} are irreducible Sym(n)-invariant and that ɛ (E_{t,i})=E_{k,i}. We observe that from these decompositions it is immediate to find two bases in RL_t and RL_k, respectively, such that the associated matrix to ɛ: R L_t -> R L_k is the diagonal form of W_{tk} found by R.M. Wilson. If we consider W_{tk} as incidence matrix of incidence structure (L_t,L_k, \subseteq), we can see W^T_{tk} as matrix associated to ɛ restricted to the Z-module ZL_t. This suggested us to address the problem via linear algebra. Unluckly the result for the Z- modules is not immediate. We give a generating set S_i of eigenvectors for the vector space RL_i, with i=0, …, n, called polytopes. For our approach an important role is played by the Z-module ZL_i with basis L_i together with the submodule ZS_i generated by polytopes. It is easy to prove that the following restrictions hold: ɛ: ZL_t -> ZL_k , ɛ:ZS_t -> ZS_k We determine the invariant factors of the matrix W^T_{tk} finding the Smith group of ɛ: ZL_t -> ZL_k. The result is obtained constructing a standard basis of polytopes and deducing opportune bases of ZL_t and ZL_k. In Chapter 5 we introduce the submodule of ZS_i which consists of elements fixed by G, that is (ZS_i)^G, and we find the Smith group of ɛ:(ZS_t)^G -> (ZS_k)^G. We restrict our attention to the case t+k=n and we prove that the groups (ZL_k)^G/ ɛ (ZL_t)^G) and (ZS_k)^G/ ɛ (ZS_t)^G) have the same order. Actually we conjecture that, for t+k=n, the two groups are isomorphic.

Nella tesi mi occupo del problema di trovare particolari forme diagonali per le matrici di strutture di incidenza tra t-sottoinsiemi e k-sottoinsiemi (L_t,L_k; \subseteq). Denotato con X un insieme finito di n elementi e con L l’insieme delle parti di X, consideriamo i sottoinsiemi L_i di L, for i=0,…,n; dove L_i è l’insieme di tutti i sottoinsiemi di X di cardinalità i; i.e. gli elementi di L_i sono i-sottoinsiemi di X. (L_t,L_k; \subseteq) è la struttura d’incidenza così definita: per x in L_t e y in L_k, x e y sono incidenti se e solo se x è contenuto in y. La sua matrice d’incidenza è denotata con W_{tk}. R.M.Wilson trova una forma diagonale per W_{tk} con metodi puramente combinatorici. Per semplicità noi chiamiamo questo teorema ``Wilson's Theorem''. Il cuore della tesi è il capitolo 4 dove diamo una nuova dimostrazione di Wilson's Theorem via algebra lineare. Costruiamo una nuova struttura algebrica: sia G contenuto in Sym(n) un gruppo di permutazioni su X. L’azione di G su X induce un’azione naturale su L. Così G agisce su ogni L_i. Questa azione partiziona ogni L_i in orbite. Per 0≤ t≤ k≤ n, consideriamo la tactical decomposition della struttura d’incidenza (L_t,L_k; \subseteq) e definiamo due matrici X^+_{tk} and X^-_{tk} chiamate le matrici d’incidenza della tactical decomposition. Se G={1} allora le orbite di G corrispondono ai sottoinsiemi e X^+_{tk}=W^T_{tk} è la matrice trasposta della struttura d’incidenza (L_t,L_k; \subseteq). Nel capitolo 5 diamo alcuni nuovi risultati in merito alla matrice X^+_{tk}. Nel capitolo 4 introduciamo un’algebra collegata all’insieme delle parti L, allo scopo di dare la nostra nuova dimostrazione di Wilson's Theorem. Sia R uno fra Q, R or C, costruiamo lo spazio vettoriale RL delle somme formali di elementi di L a coefficienti in R Estendiamo la relazione di inclusione da L a RL. Per fare questo definiamo le due mappe di incidenza ɛ and δ tali che le matrici ad esse associate rispetto alle basi L_t e L_k siano W^T_{tk} e W_{tk}, rispettivamente. I risultati del capitolo 4 sono raggiunti considerando una particolare base per RL_i. Dati 0≤ t≤ n-1 e k=t+1, costruiamo la mappa simmetrica δɛ, e decomponiamo RL_t in somma diretta di autospazi di δɛ, denotati con E_{t,i}, per i=0,…,t’, dove t’=min{t,n-t}. Proviamo che gli autospazi E_{t,i} sono Sym(n)-invarianti e irriducibili e che ɛ (E_{t,i})=E_{k,i}. Osserviamo che da queste decomposizioni è immediato trovare due basi in RL_t e RL_k, rispettivamente, tali che la matrice associata a ɛ: R L_t -> R L_k è la forma diagonale di W_{tk} trovata da R.M. Wilson. Se noi consideriamo W_{tk} matrice d’incidenza della struttura d’incidenza (L_t,L_k, \subseteq), noi possiamo anche vedere W^T_{tk} come matrice associata a ɛ ristretta allo Z-modulo ZL_t. Questo ci suggerisce di affrontare il problema via algebra lineare. Sfortunatamente il risultato per gli Z- moduli non è immediato. Noi troviamo un insieme di generatori S_i di autovettori per lo spazio vettoriale RL_i, con i=0, …, n, chiamati polytopes. Per il nostro approccio un importante ruolo è giocato dallo Z-modulo ZL_i con base L_i insieme con i sottomoduli ZS_i generati dai polytopes. E’ facile provare che valgono le seguenti restrizioni: ɛ: ZL_t -> ZL_k , ɛ:ZS_t -> ZS_k Determiniamo i fattori invarianti della matrice W^T_{tk} trovando lo Smith group di ɛ: ZL_t -> ZL_k. Il risultato è raggiunto costruendo una base standard di polytopes e deducendo opportune basi di ZL_t e ZL_k. Nel capitolo 5 introduciamo il sottomodulo di ZS_i che consiste degli elementi fissati da G, cioè (ZS_i)^G, e troviamo lo Smith group di ɛ:(ZS_t)^G -> (ZS_k)^G. Restringiamo poi la nostra attenzione al caso t+k=n e proviamo che i gruppi (ZL_k)^G/ ɛ (ZL_t)^G) e (ZS_k)^G/ ɛ (ZS_t)^G) hanno lo stesso ordine. In realtà noi congetturiamo che per t+k=n i due gruppi sono isomorfi.

(2019). Algebra of sets, permutation groups and invariant factors. (Tesi di dottorato, Università degli Studi di Milano-Bicocca, 2019).

Algebra of sets, permutation groups and invariant factors

PRANDELLI, MARIATERESA
2019

Abstract

In this thesis we deal with the problem to find particular forms for incidence matrices of incidence structures between t-subsets vs k-subsets (L_t,L_k; \subseteq). Denote by X a set of finite size n, say X={1,2,…,n} and by L the power set of X. We partition it into the sets L_i, for i=0,…,n; where L_i is the set of subsets of X of size i; i.e. the elements of L_i are the i-subsets of X. (L_t,L_k; \subseteq) is the incidence structure so defined: for x in L_t and y in L_k, x and y are incident if and only if x \subseteq y. Its incidence matrix is denoted by W_{tk}. R.M.Wilson finds a diagonal form for W_{tk} with purely combinatorics methods. For shortness we will refer to this result as ``Wilson's Theorem''. Many other authors have dealt with the same problem. The heart of the thesis is Chapter 4 where we give a new proof of Wilson's Theorem via linear maps. We construct a new algebraic structure: let G \subseteq Sym(n) be a permutation group on X. The action of G on X induces a natural action on L. So G acts on any L_i. This action partitions each L_i into orbits. For 0≤ t≤ k≤ n, we consider the tactical decomposition of the incidence structure (L_t,L_k; \subseteq). Then we can define two matrices X^+_{tk} and X^-_{tk} called the incidence matrices of the tactical decomposition. If G={1} then the orbits of G correspond to the subsets and X^+_{tk}=W^T_{tk} is the transpose matrix of the incidence structure (L_t,L_k; \subseteq). In Chapter 5 we will give some new results related to the invariant factors of X^+_{tk}. In Chapter 4 we introduce an algebra related to the boolean poset L, in order to give our new proof of Wilson's Theorem. Let R be one of Q, R or C, we construct the vector space RL of formal sums of elements of L with coefficients in R We want to extend the \subseteq relation from L into RL. To do this we define incidence maps: ɛ and δ such that the matrices associated to ɛ and δ, with respect to the bases L_t and L_k, are W^T_{tk} and W_{tk}, respectively. The results of Chapter 4 are achieved considering a particular basis for RL_i. Given 0≤ t≤ n-1 and k=t+1, we construct the symmetric maps δɛ, and we decompose RL_t into direct sum of eigenspaces of δɛ, denoted by E_{t,i}, with i=0,…,t’, where t’=min{t,n-t}. We prove that the eigenspaces E_{t,i} are irreducible Sym(n)-invariant and that ɛ (E_{t,i})=E_{k,i}. We observe that from these decompositions it is immediate to find two bases in RL_t and RL_k, respectively, such that the associated matrix to ɛ: R L_t -> R L_k is the diagonal form of W_{tk} found by R.M. Wilson. If we consider W_{tk} as incidence matrix of incidence structure (L_t,L_k, \subseteq), we can see W^T_{tk} as matrix associated to ɛ restricted to the Z-module ZL_t. This suggested us to address the problem via linear algebra. Unluckly the result for the Z- modules is not immediate. We give a generating set S_i of eigenvectors for the vector space RL_i, with i=0, …, n, called polytopes. For our approach an important role is played by the Z-module ZL_i with basis L_i together with the submodule ZS_i generated by polytopes. It is easy to prove that the following restrictions hold: ɛ: ZL_t -> ZL_k , ɛ:ZS_t -> ZS_k We determine the invariant factors of the matrix W^T_{tk} finding the Smith group of ɛ: ZL_t -> ZL_k. The result is obtained constructing a standard basis of polytopes and deducing opportune bases of ZL_t and ZL_k. In Chapter 5 we introduce the submodule of ZS_i which consists of elements fixed by G, that is (ZS_i)^G, and we find the Smith group of ɛ:(ZS_t)^G -> (ZS_k)^G. We restrict our attention to the case t+k=n and we prove that the groups (ZL_k)^G/ ɛ (ZL_t)^G) and (ZS_k)^G/ ɛ (ZS_t)^G) have the same order. Actually we conjecture that, for t+k=n, the two groups are isomorphic.
DALLA VOLTA, FRANCESCA
Smith; invarianti; permutazioni; gruppi; orbite
Smith; invariant; permutations; groups; orbite
MAT/02 - ALGEBRA
English
22-gen-2019
MATEMATICA PURA E APPLICATA - 89R
30
2016/2017
open
(2019). Algebra of sets, permutation groups and invariant factors. (Tesi di dottorato, Università degli Studi di Milano-Bicocca, 2019).
File in questo prodotto:
File Dimensione Formato  
phd_unimib_798743.pdf

accesso aperto

Descrizione: tesi di dottorato
Dimensione 727.9 kB
Formato Adobe PDF
727.9 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/241257
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
Social impact