The matrix completion problem regarding various classes of P0,1- matrices

Date
2005-01-01
Authors
Wangsness, Amy
Major Professor
Advisor
Leslie Hogben
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Mathematics
Abstract

A pattern of positions in an n x n real matrix is said to have pi-completion if every partial pi-matrix which specifies that pattern can be completed to a pi-matrix. An n x n partial matrix A (and the pattern describing the specified entries of A) is associated with a digraph G(V E) where the vertices V of G are 1, 2, 3,...,n, and an arc (i, j) [is in] E if and only if ail is specified in A. A P 0,1-matrix is a matrix in which all principal minors are non-negative and the diagonal is positive. A matrix A is sign symmetric if either aijaji > 0 or a ij = aji = 0 for all entries aij in A. A matrix A is weakly sign symmetric if aijaji > 0 for all entries aij in A. In this dissertation, all digraphs up through order 4 are classified as to whether or not every partial pi-matrix specifying the digraph can be completed to a pi-matrix for pi either of the classes weakly sign symmetric P0,1-matrices, and sign symmetric P 0,1-matrices. Also, all symmetric digraphs of size 5 and 6 are classified as to completion for the class weakly sign symmetric P 0,1-matrices, and all symmetric digraphs of order 4 are classified for the class P0,1-matrices. A number of digraphs of size up through 4 are also classified as to whether or not every partial P0,1-matrix specifying the digraphs can be completed to a P0,1-matrix. A general result is proved that allows the assumption that the non-zero entries associated with up to n - 1 arcs of a subdigraph containing no semicycle are all equal to one in a partial matrix being completed.

Comments
Description
Keywords
Citation
Source