# Fast multiplication with a full binary $n \times 2^n$ matrix

Let $$A$$ a $$n\times n$$ matrix, and X the full matrix of $$n\times 2^n$$ binary vectors (you can choose the order of the columns of X).

What is the fastest way to compute the product AX?

Suppose that $$A$$ were a $$1 \times n$$ matrix, let $$X_n$$ denote your matrix for a given value of $$n$$, and let $$A_{ consist of all but the last entry $$A_n$$ of $$A$$. Then up to rearrangement, $$AX_n = \begin{bmatrix} A_{ where $$+A_n$$ means adding $$A_n$$ to all entries. The running time of this procedure satisfies the recurrence $$T(n) = T(n-1) + O(2^{n-1}),$$ whose solution is $$T(n) = O(2^n)$$, which is linear in the size of the output. This should be compared to the trivial $$O(n2^n)$$ solution.
You can save a factor of $$n$$ in your case in the same way. The resulting algorithm is asymptotically optimal.
• I agree, it is optimal. But what if we get a rectangular matrix let say $m\times n$ , $m>n$, for $A$, I guess using that result we can go to $O(2^n*m*n^(-1))$ but can we do better? – TomTom Feb 10 '19 at 19:26
• I don’t follow. There are $2^nm$ outputs. Any algorithm would take at least that much time. – Yuval Filmus Feb 10 '19 at 19:27