# Is the product of a sparse and a dense matrix also sparse in general?

My goal is to efficiently compute a particular matrix-vector product, say, $\bf{Ax}$, where $\bf{A}$ is a matrix and $\bf{x}$ is a vector. I don't know whether or not $\bf{A}$ is sparse, but I want to find that out, given the information below.

As it turns out, I know that $\bf{A} = \bf{DB}$, where the matrix $\bf{D}$ is sparse, but the matrix $\bf{B}$ is not. $\bf{D}$ and $\bf{B}$ are of the same size, and are both known.

I know that if the required matrix-vector product had been $\bf{Dx}$, my life would have been easier, because $\bf{D}$ is sparse, and I can compute $\bf{Dx}$ efficiently.

But, I'm worried that multiplying $\bf{D}$ with $\bf{B}$ will ruin its sparsity, and thus the efficiency of the matrix-vector product. Are there any conditions under which $\bf{A}$ will also be sparse? Or is it the case that nothing general can be said without further information?

Thanks!

• The unit matrix is sparse. If you multiply it with a dense matrix then you obviously get a dense matrix. Commented Sep 23, 2017 at 20:03
• Another example is letting $\mathbf X$ be a $2n \times 2n$ matrix with $1$ in every position and $\mathbf Y$ also be a $2n \times 2n$ matrix having $1$ in all positions in $n$ rows and $-1$ in all positions in the other half of the rows. Then $\mathbf X$ and $\mathbf Y$ are both dense, but $\mathbf X \mathbf Y = \mathbf 0$ is sparse. Commented Sep 23, 2017 at 20:09
• Thus, nothing can be said. Commented Sep 23, 2017 at 20:09
• For starters, even the product of two sparse matrices is not sparse in general. Commented Sep 23, 2017 at 20:09
• Good points; thank you. Commented Sep 23, 2017 at 20:23