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

Question

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

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

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

我的下一个想法是尝试 "trick" Mathematica 中的 NMinimize 求解器，方法是给它一个受约束 Ax = b 和整数约束的 "dummy" objective 函数：

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

但是遇到了同样的"recursion"错误。

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

谢谢，旦

编辑：这是我对线性代数解决方案的想法，Ax = b:

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

x 是 0 和 1 的 N^2 x 1 向量（重塑的 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 =

求解不像 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

Answer 2

另一种非常幼稚的方法是生成随机 "binary" 矩阵并在其中一个满足您的条件时停止。这是 MATLAB 代码：

n = 3;
row_sums = [2; 1; 1];
col_sums = [1, 2, 1];
solution_found = false;

while ~solution_found
    X = randi([0, 1], n);
    if isequal(sum(X, 2), row_sums) && isequal(sum(X, 1), col_sums)
        solution_found = true;
    end
end

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

Find elements of an NxN matrix given constraints on row and column sums -- Mathematica or Matlab

matlab

wolfram-mathematica

constraints

matrix

linear-algebra