Binary vectors partially determined by linear equation systems
Binary vectors partially determined by linear equation systems
复制标题
DOI：
10.1016/s0012-365x(96)00068-4
复制
发表时间：
1997-06-20
影响因子：
0.8
通讯作者：
Kuba, A
中科院分区：
文献类型：
--
作者：
Aharoni, R;Herman, GT;Kuba, A
我们解决问题的一般形式：给定一个J维二进制（0或1值）向量，一个系统的E线性方程组的满足和域D子集的R-J，其中包含一个，当是唯一的解决方案E在D？更一般地，我们的目标是找到特定位置j的不变性的条件，1小于或等于j小于或等于J（意味着对于D中E的所有解B，B（j）= a（j））。我们研究了D的两个特殊选择：长度为J的二进制向量集（积分不变性）和R-J中分量在0和1之间的向量集（分数不变性）。对于每个位置j，产生一个不等式系统，其在适当空间中的可解性指示位置的方差。一个版本的法卡斯引理是用来指定的替代系统的不等式，产生一个向量，使用它可以告诉每个位置是否是分数不变的。证明了如果E的矩阵是全么模的，则积分不变性等价于分数不变性。我们的研究结果被应用到二维二进制图片的重建问题，从他们的投影（相当于，（0，1）-矩阵从他们的边缘），并导致一个“结构结果”的安排不变的位置在一组的所有二进制图片共享相同的行和列和其值可能规定在某些位置。我们的方法重建的高维二进制图片的问题的关系也进行了讨论。
We address problems of the general form: given a J-dimensional binary (0- or 1-valued) vector a, a system of E of linear equations which a satisfies and a domain D subset of R-J which contains a, when is a the unique solution of E in D? More generally, we aim at finding conditions for the invariance of a particular position j, 1 less than or equal to j less than or equal to J (meaning that b(j) = a(j), for all solutions b of E in D). We investigate two particular choices for D: the set of binary vectors of length J (integral invariance) and the set of vectors in R-J whose components lie between 0 and 1 (fractional invariance). For each position j, a system of inequalities is produced, whose solvability in the appropriate space indicates variance of the position. A version of Farkas' Lemma is used to specify the alternative system of inequalities, giving rise to a vector using which one can tell for each position whether or not it is fractionally invariant. We show that if the matrix of E is totally unimodular, then integral invariance is equivalent to fractional invariance. Our findings are applied to the problem of reconstruction of two-dimensional binary pictures from their projections (equivalently, (0, 1)-matrices from their marginals) and lead to a ''structure result'' on the arrangement of the invariant positions in the set of all binary pictures which share the same row and column sums and whose values are possibly prescribed at some positions. The relationship of our approach to the problem of reconstruction of higher-dimensional binary pictures is also discussed.