Non-even digraphs, symplectic pairs and full sign-invertibility.

摘要

Given an {dollar}ntimes n{dollar} sign pattern H, a symplectic pair in Q(H) is a pair of matrices (A, D) such that {dollar}Ain Q(H), Din Q(H),{dollar} and {dollar}Asp{lcub}T{rcub}D=I.{dollar} (Symplectic pairs are a pattern-generalization of orthogonal matrices which arise from a special symplectic matrix found in n-body problems in celestial mechanics (1).); In Chapter Two, a family of maximal sign-nonsingular patterns (first described by Lim in (14)) derived from wheel graphs is considered. After reviewing the algorithm for constructing a sign pattern from a given wheel graph, we present an inductive proof of the patterns' sign-nonsingularity and discuss in detail the nature of the symplectic pairs allowed by this family of sign patterns.; An {dollar}ntimes n{dollar} sign pattern H is said to be sign-invertible if there exists a sign pattern {dollar}Hsp{lcub}-1{rcub}{dollar} (called the sign-inverse of H) such that, for all matrices {dollar}Ain Q(H), Asp{lcub}-1{rcub}{dollar} exists and {dollar}Asp{lcub}-1{rcub}in Q(Hsp{lcub}-1{rcub}).{dollar} If, in addition, {dollar}Hsp{lcub}-1{rcub}{dollar} is sign-invertible (implying {dollar}(Hsp{lcub}-1{rcub})sp{lcub}-1{rcub}=H), H{dollar} is said to be fully sign-invertible and {dollar}(H, Hsp{lcub}-1{rcub}){dollar} is called a sign-invertible pair.; In Chapter Three, we discuss the digraphical relationship between a sign-invertible pattern H and its sign-inverse {dollar}Hsp{lcub}-1{rcub},{dollar} and use this to cast a necessary condition for full sign-invertibility of H. We proceed to develop sufficient conditions for H's full sign-invertibility in terms of allowed paths and cycles in the digraph of H, and conclude with a complete characterization of those sign patterns that require symplectic pairs.; A digraph D is called noneven if, whenever its arcs are assigned weights of 0 or 1, D contains no cycle of even weight. A noneven digraph D corresponds to one or more sign-nonsingular sign patterns. An unweighted digraph D allows a matrix property P if at least one of the sign patterns whose digraph is D allows P.; In (2), Thomassen characterized the noneven, 2-connected symmetric digraphs (i.e., digraphs for which the existence of arc (u, v) implies the existence of arc (v, u)). In the first part of Chapter Four, we recall this characterization and use it to determine which strong symmetric digraphs allow symplectic pairs.; A digraph D is called semi-complete if, for each pair of distinct vertices (u, v), at least one of the arcs (u, v) and (v, u) exists in D. Thomassen, again in (2), presented a characterization of two classes of strong, noneven digraphs: the semi-complete digraphs and the digraphs for which each vertex has total degree which exceeds or equals the size of the digraph. In the second part of Chapter Four, we fill a gap in these two characterizations and present and prove correct versions of the main theorems involved. We then proceed to determine which digraphs from these classes allow symplectic pairs.