Rank formulas for certain products of matrices (Q1311620): Difference between revisions

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.