Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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