Maximal determinants of combinatorial matrices

DOI10.1016/J.LAA.2018.04.030MaRDI QIDQ1641998zbMATH OpenOpenAlexWikidataFDO

Authors Henning Bruhn, Dieter Rautenbach

Publication date 20 June 2018

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

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

zbMATH Keywords

sparse matricesdeterminantpath-edge incidence matrix

Mathematics Subject Classification ID

Inequalities involving eigenvalues and eigenvectors (15A42)

Abstract: We prove that $detAleq{6}^{f}racn6$ whenever $Ain{0,1}^{nimesn}$ contains at most $2n$ ones. We also prove an upper bound on the determinant of matrices with the $k$-consecutive ones property, a generalisation of the consecutive ones property, where each row is allowed to have up to $k$ blocks of ones. Finally, we prove an upper bound on the determinant of a path-edge incidence matrix in a tree and use that to bound the leaf rank of a graph in terms of its order.

Recommendations

• On the determinant of a sparse 0-1 matrix
• Maximum determinant and permanent of sparse 0-1 matrices
• Maximum permanents of matrices of zeros and ones
• Maximum determinant of (0,1) matrices with certain constant row and column sums
• Maximum determinants of complementary acyclic matrices of zeros and ones

Cites work

• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
• Error compensation in leaf power problems
• Graph theory
• Graphs and matrices
• Maximal Determinants In Combinatorial Investigations
• On graph powers for leaf-labeled trees
• Rooted directed path graphs are leaf powers
• Some remarks about leaf roots
• Structure and linear time recognition of 3-leaf powers
• The 3-Steiner Root Problem
• The Hadamard Maximum Determinant Problem
• The characteristic polynomial of a graph

Cited in

(6)

• Properties of \((0,1)\)-matrices of order \(n\) having maximal determinant
• Maximum determinants of complementary acyclic matrices of zeros and ones
• On the determinant of a sparse 0-1 matrix
• Dual Linear Programming Problem and One-Dimensional Gromov Minimal Fillings of Finite Metric Spaces
• Maximum determinant and permanent of sparse 0-1 matrices
• Computing the Degree of Determinants via Combinatorial Relaxation

This page was built for publication: Maximal determinants of combinatorial matrices

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