All rights reserved. This publication is intended for use solely by faculty, students, and staff of Nova Southeastern University. No part of this publication may be reproduced, distributed, or transmitted in any form or by any means, now known or later developed, including but not limited to photocopying, recording, or other electronic or mechanical methods, without the prior written permission of the author or the publisher.
Date of Award
Honors Thesis - NSU Access Only
Halmos College of Arts and Sciences and the Guy Harvey Oceanographic Research Center
Farquhar Honors College
Honors College Dean
Andrea Nevins, Ph.D.
Home College Dean
Holly Lynn Baumgartner, Ph.D.
Lei Cao, Ph.D.
A blocker of n × n permutation matrices is a set of positions in an n × n matrix that intersects each n × n permutation matrix at least once. A blocker is minimum if removing any position makes it no longer a blocker. The Hankel cyclic decomposition implies that each minimum blocker of 123-avoiding permutation matrices must have a cardinality of at least n, and minimum blockers containing exactly n positions are called minimal blockers. The well-known Frobenius-Konig theorem characterizes the minimal blockers of permutation matrices: any r × s submatrix is a minimal blocker of all permutation matrices if and only if r + s = n + 1. A permutation matrix A is 123-avoiding if it does not contain the 3 × 3 identity matrix as a submatrix. Recently, Brualdi and Cao characterized the minimal blockers of 123 avoiding permutation matrices. They showed that all minimal blockers of 123-avoiding permutation matrices must contain either the (1,n) or (n,1) position and can be obtained by shifting positions from an L-shaped blocker. We continue their study by defining flag shaped blockers, which need not contain the (1,n) nor (n,1) position and may have a cardinality greater than n. We show that all flag-shaped blockers are minimum and all minimal blockers of 123-avoiding permutation matrices are special cases of flag-shaped blocker.
Megan Bennett. 2023. Minimum Blockers of 123-Avoiding Permutation Matrices. Capstone. Nova Southeastern University. Retrieved from NSUWorks, Halmos College of Arts and Sciences and the Guy Harvey Oceanographic Research Center. (32)