Reconstruction of matrices from submatrices

Authors:
Géza Kós, Péter Ligeti and Péter Sziklai

Journal:
Math. Comp. **78** (2009), 1733-1747

MSC (2000):
Primary 05B20; Secondary 11B83

DOI:
https://doi.org/10.1090/S0025-5718-09-02210-8

Published electronically:
January 23, 2009

MathSciNet review:
2501072

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For an arbitrary matrix of symbols, consider its submatrices of size , obtained by deleting rows and columns. Optionally, the deleted rows and columns can be selected symmetrically or independently. We consider the problem of whether these multisets determine matrix .

Following the ideas of Krasikov and Roditty in the reconstruction of sequences from subsequences, we replace the multiset by the sum of submatrices. For we prove that the matrix is determined by the sum of the submatrices, both in the symmetric and in the nonsymmetric cases.

**1.**P. Borwein, T. Erdélyi, G. Kós,*Littlewood-type problems on .*Proc. London Math. Soc.**79**, No. 1 (1999), 22-46. MR**1687555 (2000c:11111)****2.**M. Dudik, L. J. Schulman,*Reconstruction from subsequences.*J. Combin. Theory Ser. A**103**, No. 2 (2003), 337-348. MR**1996071 (2005a:05005)****3.**W. H. Foster, I. Krasikov,*Inequalities for real-root polynomials and entire functions.*Adv. Appl. Math.**29**, No. 1 (2002), 102-114. MR**1921546 (2004a:39055)****4.**L. O. Kalashnik,*The reconstruction of a word from fragments.*Numer. Math. and Comp. Tech., Akad. Nauk. Ukrain. SSR Inst. Mat. IV (1973), 56-57. MR**0485573 (58:5399)****5.**P. J. Kelly,*On isometric transformations.*Ph.D. Thesis, University of Wisconsin (1942).**6.**I. Krasikov, Y. Roditty,*On a reconstruction problem for sequences.*J. Combin. Theory Ser. A**77**No. 2 (1997), 344-348. MR**1429086 (97m:05186)****7.**B. Manvel, P. K. Stockmeyer,*On reconstruction of matrices.*Mathematics Magazine**44**, No. 4 (1971), 218-221. MR**0295937 (45:4998)****8.**A. Marcus, G. Tardos,*Excluded permutation matrices and the Stanley-Wilf conjecture.*J. Combin. Theory Ser. A**107**, No. 1 (2004), 153-160. MR**2063960 (2005b:05009)****9.**J. Pach, G. Tardos,*Forbidden patterns and unit distances.*SCG '05: Proc. 21st Annual Symposium on Computational Geometry, Pisa, Italy (2005), 1-9.**10.**G. Tardos,*On 0-1 matrices and small excluded submatrices.*J. Combin. Theory Ser. A**111**, No. 2 (2005), 266-288. MR**2156213 (2006e:05176)****11.**S. M. Ulam,*A collection of mathematical problems.*Interscience Tracts in Pure and Applied Mathematics**8**(1960). MR**0120127 (22:10884)**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
05B20,
11B83

Retrieve articles in all journals with MSC (2000): 05B20, 11B83

Additional Information

**Géza Kós**

Affiliation:
Mathematical Institute, Loránd Eötvös University, Pázmány P. s. 1/c, Budapest, Hungary H-1117; Computer and Automation Research Institute, Kende u. 13–17, Budapest, Hungary H-1111

Email:
kosgeza@cs.elte.hu

**Péter Ligeti**

Affiliation:
Department of Computer Algebra and Department of Computer Science, Loránd Eötvös University, Pázmány P. s. 1/c, Budapest, Hungary H-1117; Alfréd Rényi Institute of Mathematics, Reáltanoda u. 13-15, Budapest, Hungary H-1053

Email:
turul@cs.elte.hu

**Péter Sziklai**

Affiliation:
Mathematical Institute, Loránd Eötvös University, Pázmány P. s. 1/c, Budapest, Hungary H-1117

Email:
sziklai@cs.elte.hu

DOI:
https://doi.org/10.1090/S0025-5718-09-02210-8

Received by editor(s):
February 15, 2008

Received by editor(s) in revised form:
August 8, 2008

Published electronically:
January 23, 2009

Additional Notes:
The first and the third authors were supported in part by the Bolyai Grant of the Hungarian Academy of Sciences.

The third author was partially supported by the OTKA T-67867 grant.

Article copyright:
© Copyright 2009
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.