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

DOI10.1016/J.LAA.2007.05.036MaRDI QIDQ996311zbMATHOpenAlexFDO

Authors Shaun M. Fallat, Leslie Hogben

Publication date 14 September 2007

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

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

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)

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.

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

Cites work

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

Cited in

(only showing first 100 items - show all)

• Zero forcing for sign patterns
• Minimum rank and zero forcing number for butterfly networks
• Uniform forcing and immune sets in graphs and hypergraphs
• Tree covers of graphs and their linear preservers
• Improved Computational Approaches and Heuristics for Zero Forcing
• Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
• Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• Grundy domination and zero forcing in Kneser graphs
• Minimum rank of powers of trees
• Vector representations of graphs and distinguishing quantum product states with one-way LOCC
• Zero forcing and maximum nullity for hypergraphs
• On orthogonal matrices with zero diagonal
• Sparks of symmetric matrices and their graphs
• Failed zero forcing numbers of Kneser graphs, Johnson graphs, and hypercubes
• Well-forced graphs
• The nullity of bicyclic signed graphs
• The strong spectral property for graphs
• Connected zero forcing sets and connected propagation time of graphs
• On the minimum number of distinct eigenvalues of a threshold graph
• Corrigendum to: ``Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• Minimum-rank and maximum-nullity of graphs and their linear preservers
• A note on the nullity of unicyclic signed graphs
• Conformally covariant operators and conformal invariants on weighted graphs
• On the rank of a matrix associated with a graph.
• A note on universally optimal matrices and field independence of the minimum rank of a graph
• A zero forcing technique for bounding sums of eigenvalue multiplicities
• Zero forcing number of a graph in terms of the number of pendant vertices
• Using Markov chains to determine expected propagation time for probabilistic zero forcing
• Spectral aspects of symmetric matrix signings
• Relation between the rank of a signed graph and the rank of its underlying graph
• Reconfiguration graphs of zero forcing sets
• On the rank spread of graphs
• Critical exponents of graphs
• The minimum rank of a sign pattern matrix with a 1-separation
• Maximum nullity, zero forcing number and propagation time of \(\ell\)-path graphs
• A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
• The average cut-rank of graphs
• The inverse eigenvalue problem of a graph: multiplicities and minors
• Chordal graphs and distinguishability of quantum product states
• Uniformly sparse graphs and matrices
• An integer program for positive semidefinite zero forcing in graphs
• The maximum multiplicity of the largest \(k\)-th eigenvalue in a matrix whose graph is acyclic or unicyclic
• Immune sets in monotone infection rules. Characterization and complexity
• Line graphs: their maximum nullities and zero forcing numbers.
• Maximum generic nullity of a graph
• Speeding up finite-time consensus via minimal polynomial of a weighted graph -- a numerical approach
• On leaky forcing and resilience
• The critical exponent: a novel graph invariant
• An ensemble of high rank matrices arising from tournaments
• The minimum rank problem for circulants
• The strong spectral property of graphs: graph operations and barbell partitions
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
• Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
• Approximating the minimum rank of a graph via alternating projection
• Frame graph
• Almost full rank matrices arising from transitive tournaments
• Minimum rank of graphs with loops
• On symmetric matrices with indeterminate leading diagonals
• The inertia set of a signed graph
• Maximum nullity and zero forcing number of graphs with rank at most 4
• Infection in hypergraphs
• Expected values of parameters associated with the minimum rank of a graph
• Zero forcing number, constrained matchings and strong structural controllability
• A new graph parameter related to bounded rank positive semidefinite matrix completions
• Minimum-rank matrices with prescribed graph
• Lower bounds in minimum rank problems
• Complexity and computation of connected zero forcing
• Minimum rank of edge subdivisions of graphs
• On the graph complement conjecture for minimum semidefinite rank
• An upper bound for the minimum rank of a graph
• On the nullity of graphs with pendant trees
• The inverse eigenvalue and inertia problems for minimum rank two graphs
• A new lower bound for the positive semidefinite minimum rank of a graph
• Spectral aspects of symmetric matrix signings
• 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
• On the tree cover number of a graph
• Minimum rank of skew-symmetric matrices described by a graph
• 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
• A characterization of signed planar graphs with rank at most 4
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs
• A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• A technique for computing the zero forcing number of a graph with a cut-vertex
• Determinants of grids, tori, cylinders and Möbius ladders
• Minimum rank problems
• On the minimum rank of the join of graphs and decomposable graphs
• The inverse inertia problem for the complements of partial \(k\)-trees
• Minimum rank of graphs powers family
• On acyclic and unicyclic graphs whose minimum rank equals the diameter
• Zero forcing and power domination for graph products
• On zero forcing number of graphs and their complements
• On the determinant of bipartite graphs
• Bounds for minimum semidefinite rank from superpositions and cutsets

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)