0
$\begingroup$

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

  • 0
    I've removed [tag:algebra] tag, since we don't use algebra tag anymore, see [meta](http://meta.math.stackexchange.com/questions/473/the-use-of-the-algebra-tag/3081#3081) for details. Maybe [tag:linear-algebra] would be appropriate for this question. I don't think that [tag:calculus] fits this question.2012-10-27

2 Answers 2

1

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

  • 0
    @ Martin: Awesome!!2012-10-27
1

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