I am trying to find an analytical method to find the number of valid elements in a matrix*matrix^T from the matrix without the need of doing the multiplication. I call valid elements all elements which multiplication is not zero. I'll give a brief example: Say we have this matrix A:

1 2 0
4 0 0
2 3 5

and its transposed T:

1 4 2
2 0 3
0 0 5

Let's call Zij = Number of elements valid of row i of A when multiply by column j of T. For instance, Z00 = N_valids(1*1+2*2+0*0) = 2 Z10 = N_valids(4*1+0*2+0*0) = 1 Following this we'll have Z:

2 1 2
1 1 1
2 1 3

I would like to know if somebody knows how to find out Z from A. The diagonal elements its clear, but not the rest...

  • $\begingroup$ I've removed algebra tag, since we don't use algebra tag anymore, see meta for details. Maybe linear-algebra would be appropriate for this question. I don't think that calculus fits this question. $\endgroup$ – Martin Sleziak Oct 27 '12 at 6:29

Take the matrix $A$ and create a new matrix $B$ by replacing all non-zero elements by $1$.

Example: For $A=\begin{pmatrix}1&2&0\\4&0&0\\2&3&5\end{pmatrix}$ you get $B=\begin{pmatrix}1&1&0\\1&0&0\\1&1&1\end{pmatrix}$.

The numbers you want are precisely the entries of the matrix $BB^T$.

Example: $BB^T=\begin{pmatrix}1&1&0\\1&0&0\\1&1&1\end{pmatrix}\begin{pmatrix}1&1&1\\1&0&1\\0&0&1\end{pmatrix}=\begin{pmatrix}2&1&2\\1&1&1\\2&1&3\end{pmatrix}$.

  • $\begingroup$ @ Martin: Awesome!! $\endgroup$ – Manolete Oct 27 '12 at 15:42

The number $Z_{i,j}$ is the number of columns for which both row $i$ and row $j$ of the matrix have a nonzero entry. So you could make a bitvector for each row indicating the nonzero positions, take bitwise-OR of those vectors two-by-two, and sum the bits of the result to give you entries $Z_{i,j}$ (which are of course symmetric, saving almost half the work).


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.