Please use this identifier to cite or link to this item: https://hdl.handle.net/1822/895

Full metadata record
DC FieldValueLanguage
dc.contributor.authorAraújo, C. Mendes-
dc.date.accessioned2005-02-28T18:00:52Z-
dc.date.available2005-02-28T18:00:52Z-
dc.date.issued2004-
dc.identifier.urihttps://hdl.handle.net/1822/895-
dc.description.abstractNa base da chamada Teoria de Completamento, temos os conceitos de matriz parcial e de completamento. Para uma classe particular de matrizes, coloca-se a questão da existência ou não de completamentos de matrizes parciais pertencentes a essa classe de interesse. O estudo deste tipo de problemas teve o seu início em meados do século XX e, desde então, podemos encontrar uma grande variedade de trabalhos, por diversos autores, nesse contexto. Seguindo uma metodologia combinatória, abordamos, primeiramente, o problema de completamento de N–matrizes parciais. A questão base deste problema é a da existência de uma N–matriz que seja um completamento de uma dada matriz parcial. Mostramos, neste estudo, que existe um N–completamento de qualquer N–matriz parcial em PSn cujo grafo das entradas especificadas é 1–cordal ou um ciclo não dirigido. Garantimos, também, a existência do completamento desejado quando o digrafo associado é acíclico ou é um ciclo, um semiciclo ou um duplo ciclo. Analisamos, ainda, este problema de completamento impondo uma condição de simetria: procuramos determinar quais as matrizes parciais que admitem N–completamentos simétricos. Continuamos o nosso trabalho com o estudo do problema de completamento de matrizes totalmente não positivas parciais. Numa primeira abordagem, concluímos que a existência de entradas especificadas nulas condiciona fortemente a completabilidade de uma grande quantidade de grafos. O desenvolvimento deste estudo segue com base na exigência da negatividade de entradas da matriz parcial. Obtemos, então, resultados relativos a matrizes parciais cujos grafos associados são 1–cordais monotonamente etiquetados com vértice separador minimal invertível. Consideramos, ainda, os casos dos duplos triângulos, dos grafos cordais não monotonamente etiquetados e dos ciclos monotonamente etiquetados. Excluindo a existência de entradas prescritas nulas, analisamos o problema de completamento em questão para o caso não combinatorialmente simétrico, apresentando condições necessárias e suficientes para a completabilidade de caminhos totalmente especificados, ciclos dirigidos e duplos ciclos monotonamente etiquetados. O problema de completamento de P–matrizes parciais foi já abordado por vários autores e surge, de certa forma, como impulsionador de toda uma série de problemas de completamento de matrizes envolvendo propriedades de determinantes. Nesta dissertação, abordamos problemas de completamento de determinadas classes de matrizes em que menores principais positivos são um denominador comum. Nessa abordagem, mostramos que toda a Pk–matriz parcial combinatorialmente simétrica admite Pk–completamentos. Apresentamos, ainda, uma pequena nota sobre a questão de completamento de M–matrizes parciais cujo grafo associado é um caminho. Provamos, também, que todas as DN–matrizes parciais cujo grafo associado é um grafo cordal G admitem DN–completamentos se e só se G é 1–cordal. Abordamos, ainda, este problema de completamento no caso em que o grafo associado à matriz parcial é um ciclo. A classe das matrizes principalmente não singulares abrange muitas das classes de matrizes abordadas nos problemas de completamento atrás mencionados. Terminamos este trabalho abordando o problema de completamento de PN–matrizes parciais: mostramos que toda a PN–matriz parcial admite um PN–completamento. Para tal, consideramos, separadamente, o caso combinatorialmente simétrico e o caso não combinatorialmente simétrico.eng
dc.description.abstractCombinatorial 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 TNP-matrix, 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 non-combinatorially 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 DN–matrix 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.eng
dc.language.isopor-
dc.rightsopenAccesseng
dc.titleUma contribuição para o estudo de problemas de completamento de matrizeseng
dc.typedoctoralThesiseng
dc.subject.udc512.643-
Appears in Collections:BUM - Teses de Doutoramento

Files in This Item:
File Description SizeFormat 
ABSTRACT.PDF25,78 kBAdobe PDFView/Open
RESUMO.PDF31,83 kBAdobe PDFView/Open
TESE.PDF875,37 kBAdobe PDFView/Open

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID