Original title:
Möbiova funkce maticových uspořádání
Translated title:
Möbius function of matrix posets
Authors:
Medek, Michal ; Jelínek, Vít (advisor) ; Kantor, Ida (referee) Document type: Bachelor's theses
Year:
2023
Language:
eng Abstract:
In this work, we focus on the M¨obius function µ(X, Y ) of four variants of containment posets of sparse matrices, for which the M¨obius function has not been studied before. A sparse matrix is a binary matrix containing at most one 1-cell in each row and column. We focus mainly on the dominated scattered containment, where X ≤ Y if X can be created from Y by removing some rows and columns and by changing some 1-cells to 0-cells. We consider this poset to be a generalization of the permutation poset, as for permutations σ and π, if σ ≤ π, then the permutation matrices Mσ and Mπ satisfy Mσ ≤ Mπ. For the dominated scattered containment, we study the values of the M¨obius function on intervals of the form [1, Y ], where 1 is the 1 × 1 matrix consisting of a single 1-cell. We show that the situation when Y contains a zero row or column can be reduced to a situation when Y has no such zero line, that is, Y is a permutation matrix. For a permutation matrix Y , we derived a theorem expressing µ(1, Y ) in terms of the blocks of the sum decomposition of Y .
Keywords:
Sparse matrix|Submatrix|Möbius function; Řídká matice|Podmatice|Möbiova funkce
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/183053