# Estimating column sums of $A_1,\ A_1 A_2,\ A_1A_2A_3,\ \ldots$

Given $$n\times n$$ dense real valued matrices $$A_1,\ldots, A_L$$ let $$P_i=A_1\ldots A_i$$

For each $$P_i$$ I'm interested in obtaining the sum of all rows, and the sum of all columns.

Naive approach:

• takes $$O(L n^2)$$ time to get $$L$$ rows sums
• takes $$O(L^2 n^2)$$ time to get $$L$$ column sums

Is there a way to estimate $$L$$ column sums faster than $$O(L^2 n^2)$$?

We know that $$n>L$$.

More precisely, row sum $$r_i$$ and column sum $$c_i$$ are defined as follows \begin{align} r_i&=(1,\ldots,1) P_i\\ c_i&=P_i \left(\begin{matrix}1\\ \cdots\\1\end{matrix}\right) \end{align}

• Why should the computation of the row sums take $O(Ln^2)$ but for the column sums $O(L^2n^2)$? They should take the same time? The $O(Ln^2)$ algorithm should also work for the column sums just by indexing differently? Jul 14, 2022 at 14:30
• See the hand-drawn diagram with naive approach, row sums reuse work so computing L of them has same cost as computing the last one Jul 14, 2022 at 15:08
• Ahh now I get it. Jul 14, 2022 at 16:34
• @YaroslavBulatov do you have a lower bound on $L$? For example can we assume that $L \ge n^{2/5}$? Jul 14, 2022 at 18:25
• In my application $L$ is generally much smaller than $n$. Question basically comes down to asking if there's some smart way to summarize intermediate work so as to not require $O(L^2)$ passes Jul 14, 2022 at 19:19