CODEWITHSUNDEEP
matrixrandomgenerate
Arriburi
Arriburi

Reputation: 21

How do I generate Matrix with sum of every individual row and column being zero

I need to generate a matrix where the diagonal are zeroes and every column and row has a sum of zero.

For example first row 0, 4, -2, -1, 1 = sum is 0
or the first column 0, -4, 2, 1, 1 = sum is 0

This works for every column and row of course

0, 4, -2, -1, -1
-4, 0, 3, 3, -2
2, -3, 0, -1, 2 
1, -3, 1, 0, 1 
1, 2, -2, -1, 0

The diagonal is always filled with zeroes. Im trying to create a weighted graph that is balanced for every connection it does.

EDIT: I have also forgotten that the matrix is mirrored through the diagonal with * (-1)

Upvotes: 2

Views: 705

Answers (1)

r3mainer
r3mainer

Reputation: 24557

For 1×1, 2×2 and 3×3 matrices, the only matrices that work are the following (where r is any random number):

[ 0 ]    [ 0 0 ]    [  0  r -r ]
         [ 0 0 ]    [ -r  0  r ]
                    [  r -r  0 ]

With 4×4 matrices, you can start with a zero matrix and add randomness by repeatedly performing an operation that doesn't affect the zero-sum property. Choose any four cells at the corners of a quadrilateral (as long as they aren't on the the main diagonal). Treating the corners of this quadrilateral as a 2×2 matrix, you can add any multiple of the following matrix without affecting the row and column sums:

[  1  -1 ]
[ -1   1 ]

For example, a zero 5×5 matrix can be transformed into the following in four steps:

[   0    W+X  -X    0   -W  ]
[   Y     0    0   -Y    0  ]
[ -Y+Z   -Z    0    Y    0  ]
[  -Z   -W+Z   0    0    W  ]
[   0    -X    X    0    0  ]

Here's some Python code that implements this algorithm:

def zero_sum_matrix(n):
    #
    # Generate a random matrix with a zero leading diagonal where
    # every row and every column has a sum value of zero.
    # (n = size of matrix)
    from random import randint
    #
    # Handle trivial cases
    assert n > 0
    if n == 1:
        return [[0]]
    if n == 2:
        return [[0,0],[0,0]]
    if n == 3:
        r = randint(-10,11)
        return [[0,r,-r], [-r,0,r], [r,-r,0]]
    #
    # Start with a zero matrix
    m = [[0]*n for i in range(n)]
    #
    # Add randomness without affecting the row and column sums
    for i in range(n*n):
        while True:
            # Choose two different rows
            r1, r2 = randint(0,n-1), randint(0,n-1)
            if r1 != r2:
                break
        while True:
            # Choose two columns, making sure we aren't affecting
            # any cells on the main diagonal
            c1, c2 = randint(0,n-1), randint(0,n-1)
            if c1 != c2 and c1 not in (r1, r2) and c2 not in (r1, r2):
                break
        # Add random perturbations at the intersections of these
        # rows and columns
        x = randint(-10,11)
        m[r1][c1] += x
        m[r1][c2] -= x
        m[r2][c1] -= x
        m[r2][c2] += x
    return m

def mprint(m):
    # Formatted matrix print routine
    for row in m:
        o = '  '.join([("%4d" % x) for x in row])
        print(o)

Sample output:

>>> mprint(zero_sum_matrix(8))
   0     5     2     3    17   -13   -16     2
  -5     0   -10   -11    -2    16    17    -5
  -4    -3     0    -6    -7     9    25   -14
  18     4     0     0   -22     1     6    -7
   1   -27     2    12     0    -8    16     4
 -24    28     0    -7    15     0   -36    24
  14   -11    13   -17    17   -12     0    -4
   0     4    -7    26   -18     7   -12     0

Upvotes: 2

Related Questions