Maximal determinants of combinatorial matrices

DOI10.1016/J.LAA.2018.04.030zbMATH Open1393.15025arXiv1711.09935OpenAlexW2963803598WikidataQ57653754 ScholiaQ57653754MaRDI QIDQ1641998FDOQ1641998

Authors: Henning Bruhn, Dieter Rautenbach 

Publication date: 20 June 2018

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

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.

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

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

zbMATH Keywords

sparse matricesdeterminantpath-edge incidence matrix

Mathematics Subject Classification ID

Inequalities involving eigenvalues and eigenvectors (15A42)

Cites Work

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

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)