Honors Theses

Copyright Statement

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

2023

Document Type

Honors Thesis - NSU Access Only

Department

Halmos College of Arts and Sciences and the Guy Harvey Oceanographic Research Center

Honors College

Farquhar Honors College Thesis

Honors College Dean

Andrea Nevins, Ph.D.

Home College Dean

Holly Lynn Baumgartner, Ph.D.

Faculty Advisor

Lei Cao, Ph.D.

Abstract

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.

Download
To access this thesis/dissertation you must have a valid nova.edu OR mynsu.nova.edu email address and create an account for NSUWorks.

Free My Thesis

If you are the author of this work and would like to grant permission to make it openly accessible to all, please click the Free My Thesis button.

Share

COinS