Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Reconstruction of matrices from submatrices
HTML articles powered by AMS MathViewer

by Géza Kós, Péter Ligeti and Péter Sziklai PDF
Math. Comp. 78 (2009), 1733-1747 Request permission

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
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
  • 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.
  • © Copyright 2009 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Math. Comp. 78 (2009), 1733-1747
  • MSC (2000): Primary 05B20; Secondary 11B83
  • DOI: https://doi.org/10.1090/S0025-5718-09-02210-8
  • MathSciNet review: 2501072