The notion of fast decodability of a space-time code leads to the need for partitioned families of -linearly independent matrices satisfying the mutual orthogonality condition between members from distinct partitions (here denotes the conjugate transpose). Using both elementary matrix theory and the theory of Azumaya algebras, we obtain tight lower bounds on the cardinality of such matrix families, and hence tight lower bounds on the decoding complexity. These bounds are particularly low when the matrices arise from a division algebra.