The minimum rank problem for circulants

DOI10.1016/J.LAA.2015.10.033MaRDI QIDQ5962494zbMATH OpenOpenAlexFDO

Authors L. Deaett, Seth A. Meyer

Publication date 12 February 2016

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

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

zbMATH Keywords

circulant matricescirculant graphsminimum semidefinite rankminimum rank problem

Mathematics Subject Classification ID

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

Abstract: The minimum rank problem is to determine for a graph $G$ the smallest rank of a Hermitian (or real symmetric) matrix whose off-diagonal zero-nonzero pattern is that of the adjacency matrix of $G$. Here $G$ is taken to be a circulant graph, and only circulant matrices are considered. The resulting graph parameter is termed the minimum circulant rank of the graph. This value is determined for every circulant graph in which a vertex neighborhood forms a consecutive set, and in this case is shown to coincide with the usual minimum rank. Under the additional restriction to positive semidefinite matrices, the resulting parameter is shown to be equal to the smallest number of dimensions in which the graph has an orthogonal representation with a certain symmetry property, and also to the smallest number of terms appearing among a certain family of polynomials determined by the graph. This value is then determined when the number of vertices is prime. The analogous parameter over the reals is also investigated.

Recommendations

• The minimum rank of symmetric matrices described by a graph: a survey
• Zero forcing sets and the minimum rank of graphs
• Minimum rank problems
• An upper bound for the minimum rank of a graph
• The inverse eigenvalue and inertia problems for minimum rank two graphs

Cites work

• scientific article; zbMATH DE number 3650737 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• A correction: Orthogonal representations and connectivity of graphs
• Connectivity of circulant digraphs
• Graphs whose minimal rank is two
• Graphs whose positive semi-definite matrices have nullity at most two
• Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers
• On circulant matrices
• On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
• On the Shannon capacity of a graph
• On the minimum semidefinite rank of a simple graph
• Orthogonal representations and connectivity of graphs
• Polynomials with Nonnegative Coefficients
• Rank-deficient submatrices of Fourier matrices
• The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
• The minimum rank of symmetric matrices described by a graph: a survey
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs

Cited in

(6)

• Maximum nullity and zero forcing of circulant graphs
• The minimum rank problem over finite fields
• scientific article; zbMATH DE number 6402478 (Why is no real title available?)
• The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices
• Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
• The minimum rank problem over the finite field of order 2: Minimum rank 3

This page was built for publication: The minimum rank problem for circulants

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