Symmetrically adressable matrix

Question

I'm looking to create a 2d matrix of integers with symmetric addressing ( i.e. matrix[2,3] and matrix[3,2] will return the same value ) in python. The integers will have addition and subtraction done on them, and be used for logical comparisons. My initial idea was to create the integer objects up front and try to fill a list of lists with some python equivalent of pointers. I'm not sure how to do it, though. What is the best way to implement this, and should I be using lists or another data structure?

Answer 1

You only need to store the lower triangle of the matrix. Typically this is done with one n(n+1)/2 length list. You'll need to overload the __getitem__ method to interpret what the entry means.

Answer 2

Golub and Van Loan's "Matrix Computations" book outlines a feasible addressing scheme:

You pack the data in to a vector and access as follows, assuming i >= j:

a_ij = A.vec((j-1)n - j(j-1)/2 + i)

Answer 3

You're probably better off using a full square numpy matrix. Yes, it wastes half the memory storing redundant values, but rolling your own symmetric matrix in Python will waste even more memory and CPU by storing and processing the integers as Python objects.

Answer 4

A simpler and cleaner way is to just use a dictionary with sorted tuples as keys. The tuples correspond with your matrix index. Override __getitem__ and __setitem__ to access the dictionary by sorted tuples; here's an example class:

class Matrix(dict):
    def __getitem__(self, index):
        return super(Matrix, self).__getitem__(tuple(sorted(index)))
    def __setitem__(self, index, value):
        return super(Matrix, self).__setitem__(tuple(sorted(index)), value)

And then use it like this:

>>> matrix = Matrix()
>>> matrix[2,3] = 1066
>>> print matrix
{(2, 3): 1066}
>>> matrix[2,3]
1066
>>> matrix[3,2]
1066
>>> matrix[1,1]
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "z.py", line 3, in __getitem__
    return super(Matrix, self).__getitem__(tuple(sorted(index)))
KeyError: (1, 1)