Open Access. Powered by Scholars. Published by Universities.®

Algebra Commons

Open Access. Powered by Scholars. Published by Universities.®

880 Full-Text Articles 930 Authors 144,019 Downloads 105 Institutions

All Articles in Algebra

Faceted Search

880 full-text articles. Page 7 of 32.

The Minimum Rank Of Symmetric Matrices Described By A Graph: A Survey, Shaun M. Fallat, Leslie Hogben 2017 University of Regina

The Minimum Rank Of Symmetric Matrices Described By A Graph: A Survey, Shaun M. Fallat, Leslie Hogben

Leslie Hogben

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. This paper surveys the current state of knowledge on the problem of determining the minimum rank of a graph and related issues.


Recursive Robust Pca Or Recursive Sparse Recovery In Large But Structured Noise, Chenlu Qiu, Namrata Vaswani, Brian Lois, Leslie Hogben 2017 Iowa State University

Recursive Robust Pca Or Recursive Sparse Recovery In Large But Structured Noise, Chenlu Qiu, Namrata Vaswani, Brian Lois, Leslie Hogben

Leslie Hogben

This paper studies the recursive robust principal components analysis problem. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, St, in the presence of large but structured noise, Lt. The structure that we assume on Lt is that Lt is dense and lies in a low-dimensional subspace that is either fixed or changes slowly enough. A key application where this problem occurs is in video surveillance where the goal is to separate a slowly changing background (Lt) from moving foreground objects (St) on-the-fly. To solve the above ...


On Completion Problems For Various Classes Of P-Matrices, John Bowers, Job Evers, Leslie Hogben, Steve Shaner, Karyn Snider, Amy Wangsness 2017 Grinnell College

On Completion Problems For Various Classes Of P-Matrices, John Bowers, Job Evers, Leslie Hogben, Steve Shaner, Karyn Snider, Amy Wangsness

Leslie Hogben

A P-matrix is a real square matrix having every principal minor positive, and a Fischer matrix is a P-matrix that satisfies Fischer’s inequality for all principal submatrices. In this paper, all patterns of positions for n × n matrices, n ⩽ 4, are classified as to whether or not every partial Π-matrix can be completed to a Π-matrix for Π any of the classes positive P-, nonnegative P-, or Fischer matrices. Also, all symmetric patterns for 5 × 5 matrices are classified as to completion of partial Fischer matrices, and all but two such patterns are classified as to positive P- or ...


Minimum Rank And Maximum Eigenvalue Multiplicity Of Symmetric Tree Sign Patterns, Luz M. DeAlba, Timothy L. Hardy, Irvin R. Hentzel, Leslie Hogben, Amy Wangsness 2017 Drake University

Minimum Rank And Maximum Eigenvalue Multiplicity Of Symmetric Tree Sign Patterns, Luz M. Dealba, Timothy L. Hardy, Irvin R. Hentzel, Leslie Hogben, Amy Wangsness

Leslie Hogben

The set of real matrices described by a sign pattern (a matrix whose entries are elements of {+, −, 0}) has been studied extensively but only loose bounds were available for the minimum rank of a tree sign pattern. 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, and the minimum rank/maximum eigenvalue multiplicity among matrices in this set is readily computable for a tree. In this paper, we extend techniques for trees to tree sign patterns and trees allowing loops (with the presence or absence ...


Rational Realization Of Maximum Eigenvalue Multiplicity Of Symmetric Tree Sign Patterns, Atoshi Chowdhury, Leslie Hogben, Jude Melancon, Rana Mikkelson 2017 Princeton University

Rational Realization Of Maximum Eigenvalue Multiplicity Of Symmetric Tree Sign Patterns, Atoshi Chowdhury, Leslie Hogben, Jude Melancon, Rana Mikkelson

Leslie Hogben

A sign pattern is a matrix whose entries are elements of {+, −, 0}; it describes the set 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 et al. [L.M. DeAlba, T.L. Hardy, I.R. Hentzel, L. Hogben, A. Wangsness, Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl., in press, doi:10.1016/j.laa.2006.02.018.] gave ...


Minimum Rank Of Matrices Described By A Graph Or Pattern Over The Rational, Real And Complex Numbers, Avi Berman, Shmuel Friedland, Leslie Hogben, Uriel G. Rothblum, Bryan Shader 2017 Technion-Israel Institute of Technology

Minimum Rank Of Matrices Described By A Graph Or Pattern Over The Rational, Real And Complex Numbers, Avi Berman, Shmuel Friedland, Leslie Hogben, Uriel G. Rothblum, Bryan Shader

Leslie Hogben

We use a technique based on matroids to construct two nonzero patterns Z1 and Z2 such that the minimum rank of matrices described by Z1 is less over the complex numbers than over the real numbers, and the minimum rank of matrices described by Z2 is less over the real numbers than over the rational numbers. The latter example provides a counterexample to a conjecture in [AHKLR] about rational realization of minimum rank of sign patterns. Using Z1 and Z2, we construct symmetric patterns, equivalent to graphs G1 and G2, with the analogous minimum rank properties. We also discuss issues ...


Path Cover Number, Maximum Nullity, And Zero Forcing Number Of Oriented Graphs And Other Simple Digraphs, Adam Berliner, Cora Brown, Joshua Carlson, Nathanael Cox, Leslie Hogben, Jason Hu, Katrina Jacobs, Kathryn Manternach, Travis Peters, Nathan Warnberg, Michael Young 2017 Saint Olaf College

Path Cover Number, Maximum Nullity, And Zero Forcing Number Of Oriented Graphs And Other Simple Digraphs, Adam Berliner, Cora Brown, Joshua Carlson, Nathanael Cox, Leslie Hogben, Jason Hu, Katrina Jacobs, Kathryn Manternach, Travis Peters, Nathan Warnberg, Michael Young

Leslie Hogben

An oriented graph is a simple digraph obtained from a simple graph by choosing exactly one of the two arcs (u,v)(u,v) or (v,u)(v,u) to replace each edge {u,v}{u,v}. A simple digraph describes the zero-nonzero pattern of off-diagonal entries of a family of (not necessarily symmetric) matrices. The minimum rank of a simple digraph is the minimum rank of this family of matrices; maximum nullity is defined analogously. The simple digraph zero forcing number and path cover number are related parameters. We establish bounds on the range of possible values of all ...


Orthogonal Representations, Minimum Rank, And Graph Complements, Leslie Hogben 2017 Iowa State University

Orthogonal Representations, Minimum Rank, And Graph Complements, Leslie Hogben

Leslie Hogben

Orthogonal representations are used to show that complements of certain sparse graphs have (positive semidefinite) minimum rank at most 4. This bound applies to the complement of a 2-tree and to the complement of a unicyclic graph. Hence for such graphs, the sum of the minimum rank of the graph and the minimum rank of its complement is at most two more than the order of the graph. The minimum rank of the complement of a 2-tree is determined exactly.


Maximum Generic Nullity Of A Graph, Leslie Hogben, Bryan Shader 2017 Iowa State University

Maximum Generic Nullity Of A Graph, Leslie Hogben, Bryan Shader

Leslie Hogben

For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that ...


Minimum Rank Problems, Leslie Hogben 2017 Iowa State University

Minimum Rank Problems, Leslie Hogben

Leslie Hogben

A graph describes the zero–nonzero pattern of a family of matrices, with the type of graph (undirected or directed, simple or allowing loops) determining what type of matrices (symmetric or not necessarily symmetric, diagonal entries free or constrained) are described by the graph. The minimum rank problem of the graph is to determine the minimum among the ranks of the matrices in this family; the determination of maximum nullity is equivalent. This problem has been solved for simple trees [P.M. Nylen, Minimum-rank matrices with prescribed graph, Linear Algebra Appl. 248 (1996) 303–316, C.R. Johnson, A. Leal ...


On The Difference Between The Maximum Multiplicity And Path Cover Number For Tree-Like Graphs, Francesco Barioli, Shaun Fallat, Leslie Hogben 2017 Carleton University

On The Difference Between The Maximum Multiplicity And Path Cover Number For Tree-Like Graphs, Francesco Barioli, Shaun Fallat, Leslie Hogben

Leslie Hogben

For a given undirected graph G, the maximum multiplicity of G is defined to be the largest multiplicity of an eigenvalue over all real symmetric matrices A whose (i, j)th entry is non-zero whenever i ≠ j and {i, j} is an edge in G. The path cover number of G is the minimum number of vertex-disjoint paths occurring as induced subgraphs of G that cover all the vertices of G. We derive a formula for the path cover number of a vertex-sum of graphs, and use it to prove that the vertex-sum of so-called non-deficient graphs is non-deficient. For ...


Constructions Of Potentially Eventually Positive Sign Patterns With Reducible Positive Part, Marie Archer, Minerva Catral, Craig Erickson, Rana Haber, Leslie Hogben, Xavier Martinez-Rivera, Antonio Ochoa 2017 Iowa State University

Constructions Of Potentially Eventually Positive Sign Patterns With Reducible Positive Part, Marie Archer, Minerva Catral, Craig Erickson, Rana Haber, Leslie Hogben, Xavier Martinez-Rivera, Antonio Ochoa

Leslie Hogben

Potentially eventually positive (PEP) sign patterns were introduced by Berman et al. (Electron. J. Linear Algebra 19 (2010), 108–120), where it was noted that a matrix is PEP if its positive part is primitive, and an example was given of a 3×3 PEP sign pattern with reducible positive part. We extend these results by constructing n×n PEP sign patterns with reducible positive part, for every n≥3.


Completions Of P-Matrix Patterns, Luz M. DeAlba, Leslie Hogben 2017 Drake University

Completions Of P-Matrix Patterns, Luz M. Dealba, Leslie Hogben

Leslie Hogben

A list of positions in an n×n real matrix (a pattern) is said to have P-completion if every partial P-matrix that specifies exactly these positions can be completed to a P-matrix. We extend the work of C.R. Johnson, B.K. Kroschel [Electron. J. Linear Algebra Appl. 241–243 (1996) 655–657] by proving that a larger class of patterns has P-completion, including any 4×4 pattern with eight or fewer off-diagonal positions. We also show that any pattern whose digraph contains a minimally chordal symmetric-Hamiltonian induced subdigraph does not have P-completion.


Graph Theoretic Methods For Matrix Completion Problems, Leslie Hogben 2017 Iowa State University

Graph Theoretic Methods For Matrix Completion Problems, Leslie Hogben

Leslie Hogben

A pattern is a list of positions in an n×n real matrix. A matrix completion problem for the class of Π-matrices asks whether every partial Π-matrix whose specified entries are exactly the positions of the pattern can be completed to a Π-matrix. We survey the current state of research on Π-matrix completion problems for many subclasses Π of P0-matrices, including positive definite matrices, M-matrices, inverse M-matrices, P-matrices, and matrices defined by various sign symmetry and positivity conditions on P0- and P-matrices. Graph theoretic techniques used to study completion problems are discussed. Several new results are also presented, including the ...


Computation Of Minimal Rank And Path Cover Number For Certain Graphs, Francesco Barioli, Shaun Fallat, Leslie Hogben 2017 University of Regina

Computation Of Minimal Rank And Path Cover Number For Certain Graphs, Francesco Barioli, Shaun Fallat, Leslie Hogben

Leslie Hogben

For a given undirected graph G, the minimum rank of G is defined to be the smallest possible rank over all real symmetric matrices A whose (i, j)th entry is non-zero whenever i ≠ j and {i, j} is an edge in G. The path cover number of G is the minimum number of vertex-disjoint paths occurring as induced subgraphs of G that cover all the vertices of G. For trees, the relationship between minimum rank and path cover number is completely understood. However, for non-trees only sporadic results are known. We derive formulae for the minimum rank and path ...


Matrix Completion Problems For Pairs Of Related Classes Of Matrices, Leslie Hogben 2017 Iowa State University

Matrix Completion Problems For Pairs Of Related Classes Of Matrices, Leslie Hogben

Leslie Hogben

For a class X of real matrices, a list of positions in an n×n matrix (a pattern) is said to have X-completion if every partial X-matrix that specifies exactly these positions can be completed to an X-matrix. If X and X0 are classes that satisfy the conditions any partial X-matrix is a partial X0-matrix, for any X0-matrix A and ε>0, A+εI is a X-matrix, and for any partial X-matrix A, there exists δ>0 such that A−δĨ is a partial X-matrix (where Ĩ is the partial identity matrix specifying the same pattern as A) then any ...


Parameters Related To Tree-Width, Zero Forcing, And Maximum Nullity Of A Graph, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, Leslie Hogben, Bryan Shader, P. van den Driessche, Hein van der Holst 2017 University of Tennessee, Chattanooga

Parameters Related To Tree-Width, Zero Forcing, And Maximum Nullity Of A Graph, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, Leslie Hogben, Bryan Shader, P. Van Den Driessche, Hein Van Der Holst

Leslie Hogben

Tree-width, and variants that restrict the allowable tree decompositions, play an important role in the study of graph algorithms and have application to computer science. The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by a graph. We establish relationships between these parameters, including several Colin de Verdière type parameters, and introduce numerous variations, including the minor monotone floors and ceilings of some of these parameters. This leads to new graph parameters and to new characterizations of existing graph parameters. In particular, tree-width, largeur d'arborescence, path-width, and proper ...


Techniques For Determining The Minimum Rank Of A Small Graph, Laura DeLoss, Jason Grout, Leslie Hogben, Tracy McKay, Jason Smith, Geoff Tims 2017 Iowa State University

Techniques For Determining The Minimum Rank Of A Small Graph, Laura Deloss, Jason Grout, Leslie Hogben, Tracy Mckay, Jason Smith, Geoff Tims

Leslie Hogben

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Minimum rank is a difficult parameter to compute. However, there are now a number of known reduction techniques and bounds that can be programmed on a computer; we have developed a program using the open-source mathematics software Sage to implement several techniques. We have also established several additional strategies for computation of minimum rank. These techniques have been used ...


Zero Forcing Parameters And Minimum Rank Problems, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Bryan Shader, P. van den Driessche, Hein van der Holst 2017 University of Tennessee, Chattanooga

Zero Forcing Parameters And Minimum Rank Problems, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Bryan Shader, P. Van Den Driessche, Hein Van Der Holst

Leslie Hogben

The zero forcing number Z(G), which is the minimum number of vertices in a zero forcing set of a graph G, is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by G. It is shown that for a connected graph of order at least two, no vertex is in every zero forcing set. The positive semidefinite zero forcing number Z+(G) is introduced, and shown to be equal to |G|-OS(G), where OS(G) is the recently defined ordered set number that is a lower bound for minimum positive semidefinite rank ...


Propagation Time For Zero Forcing On A Graph, Leslie Hogben, My Huynh, Nicole Kingsley, Sarah Meyer, Shanise Walker, Michael Young 2017 Iowa State University

Propagation Time For Zero Forcing On A Graph, Leslie Hogben, My Huynh, Nicole Kingsley, Sarah Meyer, Shanise Walker, Michael Young

Leslie Hogben

Zero forcing (also called graph infection) on a simple, undirected graph G is based on the color-change rule: if each vertex of G is colored either white or black, and vertex v is a black vertex with only one white neighbor w, then change the color of w to black. A minimum zero forcing set is a set of black vertices of minimum cardinality that can color the entire graph black using the color change rule. The propagation time of a zero forcing set B of graph G is the minimum number of steps that it takes to force all ...


Digital Commons powered by bepress