# Number of valid elements Matrix*Matrix transpose

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

• 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. – 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}$.
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).