Name
Abstract | ||
|---|---|---|
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 ⊂ 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 ⩽ j ⩽ 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. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0012-365X(96)00068-4 | Discrete Mathematics |
Keywords | Field | DocType |
linear equation system,binary vector,linear equations,satisfiability | Discrete mathematics,Linear equation,Combinatorics,Invariant (physics),Matrix (mathematics),Invariant (mathematics),Unimodular matrix,Mathematics,Lemma (mathematics),Binary number | Journal |
Volume | Issue | ISSN |
171 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
15 | 1.91 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| R. Aharoni | 1 | 47 | 25.92 |
| G. T. Herman | 2 | 146 | 44.07 |
| Attila Kuba | 3 | 513 | 52.84 |