You’re spot-on on the algorithm complexity increase in general (for matrices without assumptions). I wonder whether there is or could there be a sort of “one-hot-sparse” matrix type (i.e., line/column permutations of identity matrices) with specialized operations that would bring down the complexity of matrix multiplications, since there would be logical ones and zeroes and trivial operations…