Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
@ Martin: Awesome!! –  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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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