Grant: Discovery Grants Program - Individual

The proposed research is mainly in matrix theory, and includes some graph theory. The problems discussed below arise in areas like quantum information theory, computer science, analysis of social networks, and are of interest independently. ***Inverse Eigenvalue Problem. Here, the objective is to describe all possible eigenvalues of a given set of symmetric matrices with a fixed zero-nonzero pattern. The zero-nonzero pattern can be viewed as a graph. This problem has been extensively studied in various directions such as numerical values of eigenvalues, multiplicities of the eigenvalues, and ranks of matrices. I study the multiplicities of eigenvalues and related problems. For a given graph on n vertices, one may ask which integer partitions of n can be achieved as a multiplicity list of the eigenvalues of the graph. The answer is known for some families of graphs such as complete graphs. However, the question remains open. To start, consider partitions of n into two integers. The question then becomes which graphs can have exactly two distinct eigenvalues. We have several results and are working to solve the whole problem. Another approach is to study the maximum multiplicity of the eigenvalues of graphs. By using the Schur complement method we have provided a simple procedure to determine the maximum multiplicity as well as the structure of the null vectors of trees and cycles. I plan to generalize this method for all graphs, when possible.***Totally Positive Matrices. The main goal is to solve the totally positive completion problem. That is, given a matrix with both specified and unspecified entries, can the unspecified entries be replaced with values so that the determinant of every submatrix of any order (minor) in the resulting matrix is positive. I have completely solved the case when the minors of order one and two are positive. The question remains open for larger minors. Since every minor is positive, each unspecified entry is restricted by a set of polynomials involving the specified entries of the matrix. Thus, a totally positive completion of a given partial matrix is equivalent to asking if these polynomial inequalities have non-empty intersection, which is challenging when the number of unspecified entries increases. It turns out that in a totally positive matrix some minors are greater than others regardless of the values of the entries. I intend to try to find all of such relationships between minors. I also intend to search for partial orders on permutations that correspond to the minors in the same way that the Bruhat order did in the completion problem when minors of order one and two are positive.***Graph homomorphisms and domination. There are two projects. One of them is to determine which results about oriented graphs and 2-edge coloured graphs can be generalized to mixed graphs. The other project is to find structural properties of, and constructions for, various types of independent domination vertex--critical graphs.********