Characterizations and applications of the isolated sets of permutations

Abstract

The transversals of a complex square matrix and the isolated set of transversals were used in (McDonald, J.J., Olesky, D.D. and Tastsomeros, M.J., 1997, Ray patterns of matrices and nonsigularity. Linear Algebra and its Applications, 267, 359–373) to study the ray-nonsingular matrices and the determinantal regions of square ray pattern matrices. Some necessary conditions of the isolated sets of transversals were obtained in (McDonald, J.J., Olesky, D.D. and Tastsomeros, M.J., 1997, Ray patterns of matrices and nonsigularity. Linear Algebra and its Applications, 267, 359–373). A characterization of the isolated sets of transversals in an important special case was also given in (McDonald, J.J., Olesky, D.D. and Tastsomeros, M.J., 1997, Ray patterns of matrices and nonsigularity. Linear Algebra and its Applications, 267, 359–373). The study of the isolated set of transversals is indeed equivalent to the study of the isolated set of permutations on the set {1, …, n}. In this article, we give a graph theoretical characterization of the isolated set of permutations. We also give an application of this characterization in a problem concerning the linear independence of the set of permutation matrices contained in a given square (0, 1) matrix.

Keywords:

• Permutation
• Transversal
• Isolated set
• Matrix
• Graph

Keywords:

• AMS Classifications: 15A09
• 15A48

Acknowledgement

Research supported by National Natural Science Foundation of China 10331020.