A partial matrix, is a matrix for which some entries are specified and some unspecified.
In general completion problems ask whether a given partial matrix, may be completed to
a matrix where all the entries are specified, such that this completion admits a specific
structure. The positive definite completion problem asks whether a partial Hermitian
matrix admits a completion such that the completed matrix is positive semidefinite.
The minimum solution criterion, is that every fully specified principal submatrix is nonnegative.
Then the set of partial Hermitian matrices, which admit a positive semidefinite
completion, forms a convex cone, and its dual cone can be identified as the set of positive
semidefinite Hermitian matrices with zeros in the entries that correspond to non-edges in
the graph G: Furthermore, the set of partial Hermitian matrices, with non-negative fully
specified principal minors, also forms a convex cone, and its dual cone can be identified as
the set of positive semidefinite Hermitian matrices which can be written as the sum of rank
one matrices, with underlying graph G. Consequently, the problem reduces to determining
when these cones are equal. Indeed, we find that this happens if and only if the underlying
graph is chordal. It then follows that the extreme rays of the cone of positive semidefinite
Hermitian matrices with zeros in the entries that correspond to non-edges in the graph
G is generated by rank one matrices. The question that arises, is what happens if the
underlying graph is not chordal. In particular, what can be said about the extreme rays of
the cone of positive semidefinite matrices with some non-chordal pattern. This gives rise
to the notion of the sparsity order of a graph G; that is, the maximum rank of matrices
lying on extreme rays of the cone of positive semidefinite Hermitian matrices with zeros
in the entries that correspond to non-edges in the graph G: We will see that those graphs
having sparsity order less than or equal to 2 can be fully characterized. Moreover, one can
determine in polynomial time whether a graph has sparsity order less than or equal to 2,
using a clique-sum decomposition. We also show that one can determine whether a graph
has sparsity order less than or equal to 2, by considering the characteristic polynomial of
the adjacency matrix of certain forbidden induced subgraphs and comparing it with the
characteristic polynomial of principal submatrices of appropriate size. / MSc (Mathematics), North-West University, Potchefstroom Campus, 2015
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:nwu/oai:dspace.nwu.ac.za:10394/15334 |
| Date | January 2015 |
| Creators | Klem, Estiaan Murrell |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0026 seconds