Transitive reduction of a rectangular Boolean matrix

DOI10.1016/0166-218X(84)90098-2MaRDI QIDQ798324zbMATH OpenOpenAlexWikidataFDO

Authors Hiroshi Hashimoto

Publication date 1984

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(84)90098-2

zbMATH Keywords

(0,1)-matricesBoolean matrix

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Matrix equations and identities (15A24) Information storage and retrieval of data (68P20)

Review text

This paper deals with simplification of rectangular Boolean matrices of zeros and ones. For x,y whose values are zero or one, the following operations are defined \(x+y=\max (x,y), x\Theta y=\max (0,x-y)\) and for \(m\times n\) Boolean matrices A,B, \(A\Theta\) B and \(A\leq B\) are defined elementwise. An \(n\times n\) Boolean matrix R such that \(R^ 2\leq R\) is said to be transitive and a Boolean matrix, all of whose diagonal elements are zero, is said to be irreflexive. The main result is as follows: Let R, S, P be transitive matrices. If P is irreflexive and \(P\leq R\), then \(S(A\Theta SAP)R=SAR.\) The author also shows some similar relationships and remarks on an application of the results to information retrieval models.

Recommendations

• Transitive reduction of a nilpotent Boolean matrix
• A reflexive matrix contracting based square algorithm for calculating the transitive closure of a Boolean matrix
• Boolean matrices and their applications to covering reductions
• On reduction of transitive fuzzy matrices and its applications
• The Boolean pivot operation, \(M\)-matrices, and reducible matrices

Cites work

• A fuzzy model of document retrieval systems
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
• scientific article; zbMATH DE number 3351227 (Why is no real title available?)
• The Transitive Reduction of a Directed Graph

Cited in

(5)

• On reduction of transitive fuzzy matrices and its applications
• Simplification of graph structure with the aid of boolean matrices
• The Boolean pivot operation, \(M\)-matrices, and reducible matrices
• A reflexive matrix contracting based square algorithm for calculating the transitive closure of a Boolean matrix
• Transitive reduction of a nilpotent Boolean matrix

This page was built for publication: Transitive reduction of a rectangular Boolean matrix

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