The minimum rank of symmetric matrices described by a graph: a survey

DOI10.1016/J.LAA.2007.05.036zbMATH Open1122.05057arXiv1102.5142OpenAlexW2056415888MaRDI QIDQ996311FDOQ996311

Authors: Shaun M. Fallat, Leslie Hogben 

Publication date: 14 September 2007

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: The minimum rank problem for a (simple) graph $G$ is to determine the smallest possible rank over all real symmetric matrices whose $ij$th entry (for $ieqj$) is nonzero whenever $i,j$ is an edge in $G$ and is zero otherwise. This paper surveys the many developments on the (standard) minimum rank problem and its variants since the survey paper cite{FH}. In particular, positive semidefinite minimum rank, zero forcing parameters, and minimum rank problems for patterns are discussed.

Full work available at URL: https://arxiv.org/abs/1102.5142

Recommendations

• Minimum rank of skew-symmetric matrices described by a graph
• Minimum rank problems
• Zero forcing sets and the minimum rank of graphs
• Minimum-rank and maximum-nullity of graphs and their linear preservers
• Minimum rank of powers of trees

zbMATH Keywords

graphrankmatrixinverse eigenvalue problemsymmetric matrixminimum rank

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Vector spaces, linear dependence, rank, lineability (15A03)

Cites Work

• On the Shannon capacity of a graph
• On the minimum number of distinct eigenvalues for a symmetric matrix whose graph is a given tree
• On the Addressing Problem for Loop Switching
• Title not available (Why is that?)
• The Parter--Wiener Theorem: Refinement and Generalization
• Spectral graph theory and the inverse eigenvalue problem of a graph
• Title not available (Why is that?)
• Spektren endlicher Grafen
• Computation of minimal rank and path cover number for certain graphs
• Multiplicities of eigenvalues and tree-width of graphs
• The graphs for which the maximum multiplicity of an eigenvalue is two
• Title not available (Why is that?)
• A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs
• Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns
• Forbidden minors for the class of graphs \(G\) with \(\xi (G) \leqslant 2\)
• Graphs whose positive semi-definite matrices have nullity at most two
• On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
• Inverse eigenvalue problems and lists of multiplicities of eigenvalues for matrices whose graph is a tree: The case of generalized stars and double generalized stars.
• On the possible multiplicities of the eigenvalues of a Hermitian matrix whose graph is a tree
• The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
• On two conjectures regarding an inverse eigenvalue problem for acyclic symmetric matrices
• Graphs whose minimal rank is two
• On the Eigenvalues and Eigenvectors of a Class of Matrices
• Spectral multiplicity and splitting results for a class of qualitative matrices
• Smith normal form and acyclic matrices
• A characterization of tridiagonal matrices
• Minimum-rank matrices with prescribed graph
• On the minimum semidefinite rank of a simple graph
• Title not available (Why is that?)
• Hermitian Matrices, Eigenvalue Multiplicities, and Eigenvector Components
• Title not available (Why is that?)
• On the eigenvalues of generalized and double generalized stars
• Linearly independent vertices and minimum semidefinite rank
• On the difference between the maximum multiplicity and path cover number for tree-like graphs
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• On the minimum rank of the join of graphs and decomposable graphs
• Eigenvalues and partitionings of the edges of a graph
• Unitary matrix digraphs and minimum semidefinite rank
• Biclique decompositions and Hermitian rank
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• On Fiedler's characterization of tridiagonal matrices over arbitrary fields
• On minimal rank over finite fields
• Graphs whose minimal rank is two: The finite fields case
• Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of a matrix
• On the rank of a matrix associated with a graph.
• A typical vertex of a tree
• On a characterization of tridiagonal matrices by M. Fiedler
• Minimum rank of a graph over an arbitrary field

Cited In (only showing first 100 items - show all)

• On symmetric matrices with indeterminate leading diagonals
• Linearly independent vertices and minimum semidefinite rank
• Graphs that allow all the eigenvalue multiplicities to be even
• Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint
• On acyclic and unicyclic graphs whose minimum rank equals the diameter
• Strong structural controllability of networks: comparison of bounds using distances and zero forcing
• The minimum rank problem over the finite field of order 2: Minimum rank 3
• Lower bounds in minimum rank problems
• A characterization of signed planar graphs with rank at most 4
• Maximum nullity and zero forcing number of graphs with rank at most 4
• Computing inertia sets using atoms
• Minimum rank of outerplanar graphs
• Linear algebraic methods in communication complexity
• On the graph complement conjecture for minimum rank
• On the minimum rank of the third power of a starlike tree
• Determinants of grids, tori, cylinders and Möbius ladders
• Maximum generic nullity of a graph
• On the graph complement conjecture for minimum semidefinite rank
• The minimum semidefinite rank of a triangle-free graph
• The minimum semidefinite rank of the complement of partial \(k\)-trees
• The inverse inertia problem for the complements of partial \(k\)-trees
• On the minimum rank of the join of graphs and decomposable graphs
• Orthogonal representations, minimum rank, and graph complements
• Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph
• On the relationship between the skew-rank of an oriented graph and the rank of its underlying graph
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• The minimum rank of universal adjacency matrices
• A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs
• On the tree cover number of a graph
• On zero forcing number of graphs and their complements
• Proof of a conjecture on the zero forcing number of a graph
• Failed skew zero forcing on a graph
• Minimum-rank matrices with prescribed graph
• A technique for computing the zero forcing number of a graph with a cut-vertex
• Zero forcing number, constrained matchings and strong structural controllability
• A new lower bound for the positive semidefinite minimum rank of a graph
• Minimum rank problems
• Title not available (Why is that?)
• On minimum rank and zero forcing sets of a graph
• Techniques for determining the minimum rank of a small graph
• Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers
• Zero forcing sets and the minimum rank of graphs
• Zero forcing parameters and minimum rank problems
• On the minimum semidefinite rank of a simple graph
• Subgraph complementation and minimum rank
• Zero forcing sets and bipartite circulants
• The inverse eigenvalue and inertia problems for minimum rank two graphs
• The maximum of the minimal multiplicity of eigenvalues of symmetric matrices whose pattern is constrained by a graph
• An upper bound for the minimum rank of a graph
• Minimum rank of skew-symmetric matrices described by a graph
• Title not available (Why is that?)
• On the nullity of graphs with pendant trees
• The inertia set of the join of graphs
• The inertia sets of graphs with a 2-separation
• Complexity and computation of connected zero forcing
• Complex \(D\) convergence and diagonal convergence of matrices
• Spectral aspects of symmetric matrix signings
• Lower bounds for minimum semidefinite rank from orthogonal removal and chordal supergraphs
• On extremal graphs for zero forcing number
• Minimum rank of edge subdivisions of graphs
• Improved rank bounds for design matrices and a new proof of Kelly's theorem
• Infection in hypergraphs
• The inertia set of a signed graph
• A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
• Classes of graphs with minimum skew rank 4
• A new graph parameter related to bounded rank positive semidefinite matrix completions
• On the determinant of bipartite graphs
• Bounds for minimum semidefinite rank from superpositions and cutsets
• Expected values of parameters associated with the minimum rank of a graph
• Vector representations of graphs and distinguishing quantum product states with one-way LOCC
• Zero forcing and maximum nullity for hypergraphs
• On the rank spread of graphs
• On the rank of a matrix associated with a graph.
• The inverse eigenvalue problem of a graph: multiplicities and minors
• An ensemble of high rank matrices arising from tournaments
• Frame graph
• Grundy domination and zero forcing in Kneser graphs
• Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• The average cut-rank of graphs
• A note on universally optimal matrices and field independence of the minimum rank of a graph
• Improved Computational Approaches and Heuristics for Zero Forcing
• Failed zero forcing numbers of Kneser graphs, Johnson graphs, and hypercubes
• Spectral aspects of symmetric matrix signings
• The critical exponent: a novel graph invariant
• The strong spectral property of graphs: graph operations and barbell partitions
• Uniform forcing and immune sets in graphs and hypergraphs
• Using Markov chains to determine expected propagation time for probabilistic zero forcing
• On leaky forcing and resilience
• The minimum rank problem for circulants
• Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
• On the minimum number of distinct eigenvalues of a threshold graph
• The strong spectral property for graphs
• Conformally covariant operators and conformal invariants on weighted graphs
• The nullity of bicyclic signed graphs
• Minimum rank and zero forcing number for butterfly networks
• Zero forcing for sign patterns
• Tree covers of graphs and their linear preservers
• Line graphs: Their maximum nullities and zero forcing numbers
• Critical exponents of graphs
• Sparks of symmetric matrices and their graphs

This page was built for publication: The minimum rank of symmetric matrices described by a graph: a survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q996311)