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_{<n}$ consist of all but the last entry $A_n$ of $A$. Then up to rearrangement, $$ AX_n = \begin{bmatrix} A_{<n} X_{n-1} & A_{<n} X_{n-1} + A_n \end{bmatrix}, $$ 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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – TomTom Feb 10 '19 at 19:26
  • $\begingroup$ I don’t follow. There are $2^nm$ outputs. Any algorithm would take at least that much time. $\endgroup$ – Yuval Filmus Feb 10 '19 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.