Abstract:
Combinatorial matrix analysis is based on the use of combinatorial methodology or thought to better understand matrix structure or a certain matrix theoretical problem. In the last few years one can find a large growing amount of work in the literature that may be classified as combinatorial matrix analysis, including work developed on matrix completion problems. The central object for matrix completion problems is that of a partial matrix. The basic type of question is whether there exists a completion of a given partial matrix lying in a certain class of interest.
Firstly, we consider the N-matrix completion problem: we are interested in determining which partial N-matrices admit an N-matrix completion. The existence of such a completion is guaranteed for combinatorially symmetric partial N-matrices in PSn whose associated graphs are 1-chordal graphs or undirected cycles and for non-combinatorially symmetric partial N-matrices whose associated digraphs are acyclic or cycles, semicycles and double cycles. Finally, we focus on the N-matrix completion problem under symmetry assumptions.
Concerning the totally nonpositive matrix completion problem, a first approach leads us to the conclusion that completability of a great amount of graphs is strongly conditioned by the existence of specified zero entries.
Therefore, we study this matrix completion problem under the assumption of negativity of some entries of the partial matrix. We prove that a partial TNPmatrix, whose associated graph is a monotonically labeled 1-chordal graph, has a TNP-matrix completion when the minimal vertex separator is regular. The cases of double triangles, non-monotonically labeled chordal graphs and monotonically labeled cycles are also addressed. In the case of noncombinatorially symmetric partial matrices, we describe necessary and sufficient conditions for the completability of specified paths, directed cycles and monotonically labeled double cycles.
The P-matrix completion problem has been considered by several authors in the last 8 years and this problem may be pointed out as the basis of a series of matrix completion problems concerning determinately properties. In this thesis we study some matrix completion problems for classes of matrices with positive principal minors as a common denominator. We begin by showing that all combinatorially symmetric partial Pk-matrices admit a Pk- matrix completion. Then, we present a small note on the question of completability of partial M-matrices whose associated graphs are paths. Related to the positive symmetric P-matrix completion problem, we have the doubly negative matrix completion problem. In this context, we prove that all partial DN-matrices whose associated graph is a chordal graph G admit DNmatrix completions if and only if G is a 1-chordal graph.
The case where the associated graph is a cycle is also addressed. The class of principally nonsingular matrices encloses many of the classes of matrices mentioned above. The completion problem for PN-matrices is solved here: we show that all partial PN-matrices admit a PN-matrix completion. In order to prove this result, we consider, separately, the combinatorially symmetric and the non-combinatorially symmetric cases. 
 
Uma Contribuição para o Estudo de Problemas de Completamento de Matrizes (pdf) »»