Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

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 Free Access

Abstract | References | Similar Articles | Additional Information

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

Following the ideas of Krasikov and Roditty in the reconstruction of sequences from subsequences, we replace the multiset by the sum of submatrices. For $ k>cn^{2/3}$ we prove that the matrix $ A$ is determined by the sum of the $ k\times k$ submatrices, both in the symmetric and in the nonsymmetric cases.


References [Enhancements On Off] (What's this?)


Similar Articles

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.