Rank formulas for certain products of matrices

DOI10.1007/BF01200149MaRDI QIDQ1311620zbMATH OpenFDO

Authors Ning Cai, Rudolf Ahlswede

Publication date 21 January 1994

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01200149

zbMATH Keywords

communication complexityexponential rankHamming distancelog rankmatrix operationsmissing dimensionquasi-direct sumquasi-outer productsum-type functions

Mathematics Subject Classification ID

Communication theory (94A05)

Review text

For two matrix operations, called quasi-direct sum and quasi-outer product, we determine their deviations from multiplicative behaviour of the rank. The second operation arises in the determination of the function table for so-called sum-type functions such as the Hamming distance. A consequence of the corresponding rank formula is, that the frequently used log rank can be a very poor bound for two-way communication complexity. Instead, as was shown by the authors in ``Two- way communication complexity of sum-type functions for one processor to be informed (Preprint 91-053 SFB 343 ``Diskrete Strukturen in der Mathematik, to appear in Probl. Peredachi Informatsii), a certain exponential rank gives often excellent or even optimal bounds.

Recommendations

• Still another rank determination of set intersection matrices with an application in communication complexity
• A comparison of two lower-bound methods for communication complexity
• Two-way communication complexity of sum-type functions for one processor to be informed
• On the ``log rank-conjecture in communication complexity
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions

Cites work

• A general 4-words inequality with consequences for 2-way communication complexity
• Communication complexity of sum-type functions invariant under translation
• Orphan structure of the first-order Reed--Muller codes

Cited in

(8)

• Rank formulae from the perspective of orthogonal projectors
• Numerical Rank Deficiency in Matrix Products
• scientific article; zbMATH DE number 833769 (Why is no real title available?)
• scientific article; zbMATH DE number 2209674 (Why is no real title available?)
• Products of matrices with prescribed spectra and ranks
• On Blocky Ranks Of Matrices
• Ning Cai: a tribute to a pioneering scholar in information theory
• Ning Cai's work on communication complexity

This page was built for publication: Rank formulas for certain products of matrices

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