I am given 2 unstructured (i.e. do not posses any special sparsity pattern like banded/triangular/etc.) sparse matrices $A$ and $B$ of dimension ($n$ x $n$) and density $d$ each (thus each matrix contains $n^2 d$ non zero elements).
In terms of probability, for any element $A(i,j)$,
$p (A[i,j] \neq 0) = d$ and independent of all other elements of $A$.
Similar probability distribution occurs for $B$.
I wanted to know if it is possible to calculate the expected density of $C = AB$ in terms of $n$ and $d$ i.e. the distribution $p( C[i,j] \neq 0 )$?

  • 1
    $\begingroup$ As it stands, this question does not make sense. If you have two given matrices, then you can of course determine the density of their product. But what do you mean by "analytically"? The answer will be a number, so there is no meaningful distinction between a numerical calculation and an analytic calculation. Also the word "random" in the title of your question is misleading. i came here because I expected a question about random matrices. $\endgroup$
    – Gustav
    Aug 1 '16 at 15:46

I took a go at this and hopefully I am able to write this properly to articulate the logic. In this logic, I am assuming summation of terms from $A$ and $B$ used to compute a term in $C$ can't cancel out to equal $0$ and that instead $C$ only has zero terms based on the sparseness of $A$ and $B$. Please let me know if you spot any errors.

$$ \begin{align} p\left( \left\{C(i,j) \neq 0\right\} \right) &= p\left( \bigcup_{k=1}^{n} \left\{ A(i,k)B(k,j) \neq 0 \right\} \right)\\ &= 1 - p\left( \bigcap_{k=1}^{n} \left\{ A(i,k)B(k,j) \neq 0 \right\}^c \right)\\ &= 1 - \prod_{k=1}^n p\left( \left\{ A(i,k)B(k,j) \neq 0 \right\}^c \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - p\left( \left\{ A(i,k)B(k,j) \neq 0 \right\} \right) \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - p\left( \left\{ \left\{A(i,k) \neq 0 \right\} \bigcap \left\{ B(k,j) \neq 0 \right\} \right\} \right) \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - p\left( \left\{A(i,k) \neq 0 \right\} \right) p\left(\left\{ B(k,j) \neq 0 \right\} \right) \right)\\ &= 1 - \prod_{k=1}^n \left( 1 - d^2 \right)\\ &= 1 - \left( 1 - d^2 \right)^n\\ &\approx nd^2\;\;\;\;\; \forall d^2 \ll 1 \end{align} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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