ISU Combinatorial Matrix Theory Research Group

        This is a group of faculty and students who are interested in combinatorial matrix theory.  New members can join at the beginning of the academic year, or at the beginning of the summer for the REU session  Graduate linear algebra (Math 510) is a prerequisite for graduate students; undergraduate linear algebra (Math 317 or equivalent) is a prerequisite for the summer REU undergraduates and a course in graph theory is helpful.  Graduate students in the group may register for 1 credit/semester of Math 690E during the academic year.  Faculty at nearby colleges and universities are also welcome.  At the beginning of the session we begin by discussing the necessary background, such as the use of graphs and digraphs to study matrices and the use of matrices to study (di)graphs, and review recent developments.  We then select a problem and begin active research.  This is a great opportunity for graduate and undergraduate students to become involved in research.  Past groups wrote papers on matrix completion problems and minimum rank of symmetric tree sign patterns.  For more information contact  Leslie Hogben.
 
  • About Matrix Completion Problems
  • About Minimum Rank/Maximum Multiplicity of a Graph or Sign Pattern
  • People
  • MCRG Papers
  • Leslie Hogben's Reseach Papers
  • Matrix Completion Problems Web Site
  • Linear Algebra Sites

  •  

     

    Matrix Completion Problems for Patterns using Graph Theory

          A partial matrix is a matrix in which some entries are specified and others are not ( see picture above left on this page ).  A completion of a partial matrix is a specific choice of values for the unspecified entries.  A pattern  for n x n matrices is a list of positions of an n x n matrix, that is, a subset of {1,...,n} x {1,...,n}.  A partial matrix specifies the pattern if its specified entries are exactly those listed in the pattern.  For a particular class P of matrices, the P-matrix completion problem for patterns asks which patterns of positions have the property that any partial P -matrix that specifies the pattern can be completed to a -matrix.
            In recent years graphs and directed graphs (digraphs) have been used very effectively to study matrix completion problems ( see picture above right on this page ).  For a class of symmetric matrices, since the j,i-entry is equal to the i,j-entry, the pattern must be positionally symmetric, i.e., if position (i,j) is in the pattern, then so is (j,i).  Patterns that are positionally symmetric can be studied by means of their graphs. Let A be a (fully specified) symmetric n x n matrix.  The nonzero-graph of A is the graph having as vertex set {1,...,n},  and, as its set of edges, the set of (unordered) pairs {i,j} such that both i and j are vertices with i not equal to j and aij not equal to 0.  For a positionally symmetric pattern Q, the pattern-graph of Q is the graph having {1,...,n} as its vertex set and, as its set of edges, the set of (unordered) pairs {i,j} such that position (i,j) (and therefore also (j,i)) is in Q.
         Matrix Completions Problems for Patterns Homepage
    This page provides current information about the state of knowledge for the matrix completion problem for patterns for various classes of matrices.

    Minimum Rank/Eigenvalues of Symmetric Matrices of a Graph or Sign pattern
    The graph G(A) of a real symmetric matrix A has vertices {1,...,n}, and as edges the unordered pairs {i,j} such that ai j  is nonzero (with distinct i, j).  In recent years there has been a great deal of interest in the possible eigenvalues of a real symmetric matrix whose nonzero entries are described by a given graph or by the pattern of the signs of the entries, especially a tree (i.e., a connected graph with no cycles).   An example of an application of an algorithm that produces a 0,1-matrix B wuth G(B) = T and rank B = mr(T) is shown below.
    For a sign pattern, the matrices need not be symmetric (the pattern itself need not be symmetric.  There is interest in psetrcally arbitary patterns, i.e., those that allow any spectrum.

    People

    (2007 - 2008)

    Papers

    The P0-Matrix Completion Problem (Choi, DeAlba, Hogben, Maxwell, Wangsness)
        Electronic Journal of Linear Algebra 9 (2002): 1-20
    In this paper we consider the P0-matrix completion problem. We establish that every asymmetric partial P0 -matrix has P0-completion. We also classify all 4 x 4 patterns that include all diagonal positions as either having P0-completion or not having P0-completion.  We show that any positionally symmetric pattern whose graph is an n-cycle with n > 5 has P0-completion. [ PDF ]

    The Nonnegative P0-Matrix Completion Problem
    (Choi, DeAlba, Hogben, Kivunge, Nordstrom, Shedenhelm)
        Electronic Journal of Linear Algebra 10 (2003): 46-59
    In this paper the nonnegative P 0 -matrix completion problem is considered.  It is shown that a pattern for 4 x 4 matrices that includes all diagonal positions has nonnegative P 0 -completion if and only if its digraph has the property that the induced subdigraph of any 4-cycle is a clique.It is also shown that any positionally symmetric pattern that includes all diagonal positions and whose graph is an n -cycle has nonnegative P 0 -completion if and only if n =4. [PDF ]

    The (Weakly) Sign Symmetric P-Matrix Completion Problems
    (DeAlba, Hardy, Hogben, Wangsness)
    Electronic Journal of Linear Algebra 10 (2003): 257-271
    In this paper we show that a partial sign symmetric P-matrix, whose graph of specified entries is an n-cycle with n >= 6, can be completed to a sign symmetric P-matrix. The analogous completion property is also established for a partial weakly sign symmetric P-matrix and for a partial weakly sign symmetric P0-matrix. We show that a partial (weakly) sign symmetric P-matrix, whose digraph of specified entries is an asymmetric n-cycle with n >= 4, can be completed to a (weakly) sign symmetric P-matrix. We also classify patterns of entries for 4 x 4 matrices as to whether or not a partial (weakly) sign symmetric P- or weakly sign symmetric P0-matrix specifying the pattern must have completion to the same type of matrix. We also examine the relationship between the weakly sign symmetric P- and sign symmetric P-matrix completion problems. [PDF ]

    On completion problems for various classes of P-matrices (Bowers, Evers, Hogben, Shaner, Snider, Wangsness)  Linear Algebra and Its Applications 413 (2006) 342-354.
    A pattern of positions in an n x n real matrix is said to have P-completion if every partial P-matrix which specifies that pattern can be completed to a P-matrix.  A Fischer matrix is a P-matrix that satisfies Fischer's inequality for all principal submatrices.   In this paper, all patterns of positions of size up through 4 are classified as to whether or not every partial P-matrix can  be completed to a  P-matrix for P any of the classes positive P-, nonnegative
    P-, or  Fischer matrices.   Also, all symmetric patterns up through size 5 are classified as to whether or not they have Fischer completion, and all but 2 such patterns are classified as to whether or not they have positive P- or nonnegative P-completion.  We also show that any pattern whose digraph contains a minimally chordal symmetric-Hamiltonian induced subdigraph does not have $\Pi$-completion for P any of the classes positive P-, nonnegative P-, Fischer matrices. [ PDF preprint ]

    Minimum Rank and Maximum Eigenvalue Multiplicity of Symmetric Tree Sign Patterns (DeAlba, Hardy, Hentzel, Hogben, Wangsness), Linear Algebra and Its Applications 418 (2006) 389-415 pdf preprint.
    The set of real matrices described by a sign  pattern (a square matrix  whose entries  are elements of {+, -, 0}) has been studied extensively. A simple graph has been associated with the set of symmetric matrices having a zero-nonzero pattern of off-diagonal entries described by the graph. In this
    paper, we present a unified approach to the study of the set of symmetric matrices described by a  sign pattern and the set of matrices associated with a graph allowing loops, with the presence or absence of loops describing the zero-nonzero pattern of the diagonal.  We call any family of matrices having a common graph a cohort.   For a cohort whose graph is a tree, we provide an algorithm for the calculation of the  maximum of the multiplicities of eigenvalues of any matrix in the cohort. For a symmetric tree sign pattern or tree that allows loops, this algorithm allows exact computation of maximum multiplicity and minimum rank, and can be used to obtain a symmetric integer matrix realizing minimum rank.

    Rational Realization of Maximum Eigenvalue Multiplicity of Symmetric Tree Sign Patterns (Chowdhury, Hogben, Melancon, Mikkelson),  Linear Algebra and Its Applications 418 (2006) 380-393, pdf preprint.
    A sign  pattern is a  matrix  whose entries  are elements of {+, -,0} and describes the family of real matrices whose entries have the signs in the pattern. A graph (that allows loops but not multiple edges) describes  the set of symmetric matrices  having a zero-nonzero pattern of entries determined by  the absence or presence of edges in the graph. DeAlba, Hardy, Hentzel, Hogben, Wangsness (above) gave algorithms for the computation of maximum multiplicity and minimum rank of matrices associated with a tree sign pattern or tree, and an algorithm to obtain an integer matrix realizing minimum rank.  We extend these results by giving algorithms to obtain a symmetric rational matrix realizing the maximum multiplicity of a rational eigenvalue among symmetric matrices associated with a symmetric tree sign pattern or tree.
     
    Spectrally Arbitrary Patterns: Reducibility and the 2n Conjecture
    (with DeAlba,  Hentzel, McDonald, Mikkelson, Pryporova, Shader, Vander Meulen) 
    Linear Algebra and Its Applications, 423 (2007)  262-276. [PDF preprint ]
    A sign  pattern $Z$ (a matrix  whose entries  are elements of $\{+, -, 0\}$) is spectrally arbitrary if for any self-conjugate spectrum there is a real matrix with sign pattern $Z$ having the given spectrum.  Spectrally arbitrary sign patterns were introduced in \cite{specArbPat}, where it was (incorrectly) stated that if a sign pattern $Z$ is reducible and each of its irreducible components is a spectrally arbitrary sign pattern, then $Z$ is a spectrally arbitrary sign pattern, and it was conjectured that the converse is true as well; we present counterexamples to both of these statements.  In \cite{BMO04} it was conjectured that any $n\times n$ spectrally arbitrary sign pattern must have at least $2n$ nonzero entries; we establish that this conjecture is true for $5\times 5$  sign patterns. We also establish analogous results for nonzero patterns.

    Minimum Rank of a Tree over an Arbitrary Field (with Nathan L. Chenette, Sean V. Droms, Rana Mikkelson and Olga Pryporova)   Electronic Journal of Linear Algebra 16 (2007): 183-186.
    For a field $F$ and  graph $G$ of order $n$, the minimum rank of $G$ over $F$ is defined to be the smallest possible rank over all symmetric matrices $A\in\Fnn$ whose $(i,j)$th entry (for $i\neq j$) is nonzero whenever   $\{i,j\}$ is an edge in $G$ and is zero otherwise.  We show that  the minimum rank of a tree  is independent of the field.

      Linear Algebra Sites

     
    Leslie Hogben's Homepage 30-July-07