4
$\begingroup$

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

  • 0
    By $s$-sparse, I mean that each row and each column has at most $s$ non-zero entries.2012-04-11

1 Answers 1

10

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

  • 0
    @Nick: yes, I added an example showing that the product can be quite dense.2012-04-12