matlab - 在给定行和列总和约束的情况下查找 NxN 矩阵的元素——Mathematica 或 Matlab

Question

我试图找到 NxN 矩阵的元素，以便满足给定的行和列总和。唯一的其他限制是矩阵的元素限制为整数 0 和 1。

这可能是 Matlab 或 Mathematica 中的几行简单代码(我在这里四处寻找并在 R 中发现了一些相关问题)，但我的相关编码经验仅在约束优化方面——我迷失在这里没有要最小化的目标函数。

我的第一个想法是设置一个线性代数问题，Ax = b，但这行不通，因为 A'A 是单数。 (我会在下面的评论中提供详细信息，以防万一。)

我的下一个想法是尝试“欺骗”Mathematica 中的 NMinimize 求解器，方法是给它一个受约束 Ax = b 和整数约束约束的“虚拟”目标函数:

    x = Map[Subscript[x, #] &, Range[1, Ngrid^2]];
    x = Map[Subscript[x, #] &, Range[1, Ngrid^2]];
    NMinimize[{x.x\[Transpose], A.x == b && Apply[And,Thread[GreaterEqual[x, 0]]] && 
    Apply[And, Thread[LessEqual[x, 1]]] && Element[x,Integers]}, x, 
    Method -> "DifferentialEvolution", MaxIterations -> 2000];

但它遇到了同样的“递归”错误。

我觉得这不是解决问题的方法。是否有一些命令允许我根据约束填充矩阵的元素？如果它没有生成唯一的解决方案，是否有办法查看解决方案集？

谢谢，丹

编辑:这是我对线性代数解 Ax = b 的想法:

A 是由 0 和 1 组成的 2N x N^2 矩形矩阵。每列对应于解向量 x 中的 N^2 个元素之一(我们所追求的 reshape 的 NxN 矩阵)。 (编辑:前 N 行对应于 x 中受每个行约束影响的元素，后 N 行对应于 x 中受每个列约束影响的元素。)

x 是由 0 和 1 组成的 N^2 x 1 向量( reshape 的 NxN 解矩阵)。

b 是行和列总和(约束)的 2N x 1 向量。

例子:

如果 N=3 并且我们想要找到 x(预计到达时间:下面的“x”是我们所追求的解决方案；我们无法提前知道它):

    1   0   0
    1   0   1
    0   1   0

我们可以写成 A =

    1   1   1   0   0   0   0   0   0
    0   0   0   1   1   1   0   0   0
    0   0   0   0   0   0   1   1   1
    1   0   0   1   0   0   1   0   0
    0   1   0   0   1   0   0   1   0
    0   0   1   0   0   1   0   0   1

和 z =

    1
    2
    1
    2
    1
    1

求解不像 x = inv(A'A)*A'z 那样简单，因为 A'A 没有逆。

在此先感谢您提供的任何帮助!

Answer 1

这是一种天真的方法。这取决于您需要如何扩大规模:

n = 3;
sumsrows = {2, 1, 1};
sumscols = {1, 2, 1};
X = Array[x, {n, n}];

fi = FindInstance[
   And @@ Thread[(Tr /@ X) == sumsrows] && 
   And @@ Thread[(Tr /@ Transpose@X) == sumscols] && 
   And @@ Thread[0 <= Flatten@X <= 1], Flatten@X, Integers]

Partition[fi[[1, All, 2]], n] // MatrixForm