The minimum rank problem for circulants

DOI10.1016/J.LAA.2015.10.033zbMATH Open1330.05099arXiv1511.07920OpenAlexW2177264089MaRDI QIDQ5962494FDOQ5962494

Authors: L. Deaett, Seth A. Meyer 

Publication date: 12 February 2016

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

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.

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

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

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)

Cites Work

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

Cited In (6)

• The minimum rank problem over the finite field of order 2: Minimum rank 3
• The minimum rank problem over finite fields
• Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
• Title not available (Why is that?)
• Maximum nullity and zero forcing of circulant graphs
• The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices

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)