# Multiplying sparse matrices

If I have two sparse matrices, $A$ and $B$. Let's say $A$ has $k$ non-zero entries and $B$ has $j$ non-zero entries. Let's assume all I know is the amount of non-zero entries each matrix has, I don't know where they are or what their value is. The dimensions of the matrices are known and are compatible, so it cannot be assumed that they are always square matrices (although they could be in some cases). So, let's assume A is a MxN matrix and B is an NxP matrix - making AB an MxP matrix.

If I multiply these two sparse matrices together (A*B), what is the maximum amount of non-zero values the product of the matrices could have? I have a feeling it must just be $k+j$ but I can't define it mathematically. I'm not after a completely formal proof.

• Are they square matrices? Commented Aug 12, 2016 at 9:19
• @naslundx Not always - I updated the question. Commented Aug 12, 2016 at 9:22

$A=\left( \begin{array}{ccc} 1 & 0 & \cdots & 0 \\ 1 & 0 & \cdots & 0\\ 1 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots &\ddots &\vdots\\ 0 & 0 & 0 & 0\end{array} \right),B=\left( \begin{array}{ccc} 1 & 1 & 0 &\cdots & 0 \\ 0 & 0 & 0 &\cdots & 0\\ 0 & 0 & 0 &\cdots & 0 \\ \vdots & \vdots& \vdots &\ddots &\vdots\\ 0 & 0 & 0 & 0 & 0\end{array} \right)$
$AB=\left( \begin{array}{ccc} 1 & 1 & 0 &\cdots & 0 \\ 1 & 1 & 0 &\cdots & 0\\ 1 & 1 & 0 &\cdots & 0\\ 0 & 0 & 0 &\cdots & 0 \\ \vdots & \vdots& \vdots &\ddots &\vdots\\ 0 & 0 & 0 & 0 & 0\end{array} \right)$
As it can be seen, the result gives us a matirx with six nonzero entries, which is a higher value than $k+j=5$. It gives the intuition that the maximun amount of nonzero entries will be $k*j$.