2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\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 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 at 19:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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