时间戳

首页 > 解决方案 > 如何生成每个单独的行和列的总和为零的矩阵

matrix - 如何生成每个单独的行和列的总和为零的矩阵

问题描述

我需要生成一个矩阵，其中对角线为零，每列和每行的总和为零。

例如第一行 0, 4, -2, -1, 1 = sum 为 0
或第一列 0, -4, 2, 1, 1 = sum 为 0

这当然适用于每一列和每一行

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

对角线总是用零填充。我试图创建一个加权图，它对它所做的每个连接都是平衡的。

编辑：我也忘记了矩阵是通过对角线镜像的 * (-1)

标签： matrixrandomgenerate

解决方案

对于 1×1、2×2 和 3×3 矩阵，唯一有效的矩阵如下（其中 r 是任意随机数）：

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

对于 4×4 矩阵，您可以从零矩阵开始，并通过重复执行不影响零和属性的操作来添加随机性。选择四边形角上的任意四个单元格（只要它们不在主对角线上）。将此四边形的角视为 2×2 矩阵，您可以添加以下矩阵的任意倍数，而不会影响行和列的总和：

[  1  -1 ]
[ -1   1 ]

例如，一个零 5×5 矩阵可以通过四个步骤转换为以下内容：

[   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  ]

下面是一些实现此算法的 Python 代码：

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)

样本输出：

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

推荐阅读