mikeage.net Logo
mikeage.net/2005/08/12/full-matrix-to-half-matrix/

mikeage.net @ ג׳ שבט תשע״ח

Full Matrix to Half Matrix

Quick Overview

How to make a directed representation of a symetric matrix into an
undirected representation.

Overview

That's a long task. Really what it means is as follows. Suppose I have a matrix, let's say, A[i,j]. Now, if A is sparse (that is, most of the elements are zero / null / any constant value), we may choose to store it in a text file like such:
i1,j1,value
i2,j2,value
i3,j3,value

etc.
Now, sometimes you have a symetric matrix, where the value is a function of i and j. For example, those distance guides you see on AAA maps are triangular, not square, because the distance between Washington and New York is the same as the distance between New York and Washington. In other words, A[i,j] = A[j,i] for all i and j.
[In case you think this is obvious, you may not understand what the matrix is for. Suppose instead of Dist[NY,Wash] = Dist[Wash,NY] we had Moving[NY,Wash] to represent the number of people moving from NY to Washington. Obviously, that number would be different from Moving[Wash,NY], which is the number of people moving from Washington to New York.]
Getting back to the task, how can we easily filter out the duplicated elements, without having to take the text file, make a giant matrix in memory, and then write out the upper (or lower) half?

Solution

We can do the following:
For each line,

  • Read
  • Write it both forwards and backwards
  • Loop
  • Then, sort, and remove duplicates (easy with the sort and uniq commands). Then, just loop through, removing all elements where i is greater than j.

    Note

    Some people may say this is obvious. Well, it is... but I didn't see it immediately. Thanks to Dr. Dick Klavans for pointing it out to me.
    Enjoy.

Leave a Reply

Quick Map
Content +
Personal +
Archives +
Site Stuff +
RBS Weather +
Search +
Recent Images

Valid XHTML 1.1!
Printer Friendly Page
 

Last Modified: September 04, 2006 @ 02:11 CST

Memory(TRUE): 2097152/2097152
Memory(FALSE): 2990896/3000880