$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?''

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} $$