RANK FORMULAS FOR CERTAIN PRODUCTS OF MATRICES

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 in [9], a certain exponential rank gives often excellent or even optimal bounds.