# $A, B$ sparse imply $AB$ is sparse?

Today I read the claim that if $A$ and $B$ are sparse matrices, then $AB$ is also sparse. I didn't believe it at first, but could not exhibit a counterexample. So is this claim in fact true? If so, how sparse is $AB$? Can a nice result like if $A$ is $s$-sparse and $B$ is $t$-sparse, then $AB$ is (?)-sparse?''

-
what do you mean by "s-sparse"? If $A$ ($n\times n$) contains $2n$ entries it will (or better: might) approximately double the entries in the result as compared to $B$. So when is it not sparse anymore? – example Apr 11 '12 at 9:22
By $s$-sparse, I mean that each row and each column has at most $s$ non-zero entries. – Nick Thompson Apr 11 '12 at 9:29

If each column of $B$ has at most $t$ nonzero entries, then each column of $AB$ is the linear combination of at most $t$ columns of $A$. If the columns of $A$ have at most $s$ nonzero entries, this implies that each column of $AB$ can have at most $st$ nonzero entries.

If you want the result in terms of rows, just transpose everything.

Here is an example of the product of two $2$-sparse matrices being $4$-sparse:

$$\begin{bmatrix}\bullet & \bullet & & \\ \bullet & \bullet & & \\ & & \bullet & \bullet \\ & & \bullet & \bullet\end{bmatrix} \begin{bmatrix}\bullet & & \bullet & \\ & \bullet & & \bullet \\ \bullet & & \bullet & \\ & \bullet & & \bullet\end{bmatrix} = \begin{bmatrix}\bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet\end{bmatrix}$$

-
So, $AB$ can have as many as $nst$ nonzero entries; meaning perhaps not very sparse. Thank you for your time. – Nick Thompson Apr 12 '12 at 4:27
@Nick: yes, I added an example showing that the product can be quite dense. – Rahul Apr 12 '12 at 4:45