On the t-term rank of a matrix

DOI10.1016/J.LAA.2011.06.001MaRDI QIDQ765173zbMATH OpenOpenAlexFDO

Authors Richard A. Brualdi, Kathleen P Kiernan, Seth A. Meyer, Michael W. Schroeder

Publication date 19 March 2012

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

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

zbMATH Keywords

\(t\)-term rankcolumn sum vectorinterchangematrix classrow sum vector

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Transversal (matching) theory (05D15)

Abstract: For t a positive integer, the t-term rank of a (0,1)-matrix A is defined to be the largest number of 1s in A with at most one 1 in each column and at most t 1s in each row. Thus the 1-term rank is the ordinary term rank. We generalize some basic results for the term rank to the t-term rank, including a formula for the maximum term rank over a nonempty class of (0,1)-matrices with the the same row sum and column sum vectors. We also show the surprising result that in such a class there exists a matrix which realizes all of the maximum terms ranks between 1 and t.

Review text

Let \(t\) a positive integer. Then the \textit{\(t\)-term rank} of a \((0,1)\)-matrix \(A\) equals the maximum number of \(1\)s in \(A\) with at most one \(1\) in each column and at most \(t\) \(1\)s in each row. Thus the \(1\)-term rank is the ordinary term rank. The authors determine several basic properties of the \(t\)-term rank. In particular, they exhibit the \(t\)-term rank of matrices in a class \({\mathcal A}(R,S)\), i.e., the class of \((0,1)\)-matrices with a fixed row sum vector \(R\) and a fixed column sum vector \(S\). Given any nonempty class \({\mathcal A}(R,S)\) the following results are established: First, a formula for the maximum \(t\)-term rank over the class \({\mathcal A}(R,S)\) is given. This generalises a formula of Ryser. In addition, it is shown that there exists a matrix in \({\mathcal A}(R,S)\) which attains the maximum \(t'\)-term rank for all \(t'\) with \(1\leq t'\leq t\).

Recommendations

• On the term rank partition
• Matrices in \(\mathcal{A}(R, S)\) with minimum \(t\)-term ranks
• A generalization of Ryser's theorem on term rank
• On the properties of interchange operations in classes of \((0,1)\)- matrices
• The structure matrix and a generalization of Ryser's maximum term rank formula

Cites work

• Batch codes and their applications
• Combinatorial batch codes
• Combinatorial batch codes and transversal matroids
• Combinatorial matrix theory
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• On Fundamental Transversal Matroids

Cited in

(9)

• A generalization of Ryser's theorem on term rank
• Minimal matrices in the Bruhat order for symmetric (0,1)-matrices
• On the term rank partition
• Matrices in \(\mathcal{A}(R, S)\) with minimum \(t\)-term ranks
• The structure matrix and a generalization of Ryser's maximum term rank formula
• scientific article; zbMATH DE number 6123192 (Why is no real title available?)
• A minimal completion of (0,1)-matrices without total support
• Possible numbers of nonzero entries in a matrix with a given term rank
• On the term rank partitions of matrices in

This page was built for publication: On the \(t\)-term rank of a matrix

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