5

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.

Jay P
  • 187

1 Answers1

3

It cannot be k+j as it can be seen in the next counterexample:

We define k = 3 and j = 2 and create the next two matrices, with dimension that agree for the multiplication as you stated:

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

Which multiplying them will give us the next matrix:

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

Josu Etxezarreta Martinez
  • 1,142