Reconstructing matrices from minors

Charles R. Johnson; Joshua J. Mollner; Ashlyn M. Winkler

doi:10.1016/j.laa.2010.09.018

Reconstructing matrices from minors

Charles R. Johnson, Joshua J. Mollner, Ashlyn M. Winkler

Managerial Economics, Decision Sciences and Operations

Research output: Contribution to journal › Article › peer-review

Abstract

Which collections of mn minors of an m-by-n matrix uniquely determine the matrix, given some regularity conditions? For m=n=3, the 585 such collections, that are distinct up to symmetry, are determined. For general m, n, a necessary and a sufficient condition for reconstruction are given in terms of matchings in a bipartite graph. Among other particular results, those collections of entries for which there are minors that permit reconstruction one entry at a time are characterized.

Original language	English (US)
Pages (from-to)	1733-1744
Number of pages	12
Journal	Linear Algebra and Its Applications
Volume	434
Issue number	7
DOIs	https://doi.org/10.1016/j.laa.2010.09.018
State	Published - Apr 1 2011

Keywords

Arrangement bipartite graph
Configuration bipartite graph
Entry-wise sequential reconstruction
Reconstruction of matrices from minors
Unique reconstruction set

ASJC Scopus subject areas

Algebra and Number Theory
Numerical Analysis
Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.laa.2010.09.018

Cite this

@article{73e90e8ab9074cb0b1edd1d9bf28591f,

title = "Reconstructing matrices from minors",

abstract = "Which collections of mn minors of an m-by-n matrix uniquely determine the matrix, given some regularity conditions? For m=n=3, the 585 such collections, that are distinct up to symmetry, are determined. For general m, n, a necessary and a sufficient condition for reconstruction are given in terms of matchings in a bipartite graph. Among other particular results, those collections of entries for which there are minors that permit reconstruction one entry at a time are characterized.",

keywords = "Arrangement bipartite graph, Configuration bipartite graph, Entry-wise sequential reconstruction, Reconstruction of matrices from minors, Unique reconstruction set",

author = "Johnson, {Charles R.} and Mollner, {Joshua J.} and Winkler, {Ashlyn M.}",

note = "Funding Information: The research described in this paper was supported by NSF Grant # DMS-0751964. ∗ Corresponding author.",

year = "2011",

month = apr,

day = "1",

doi = "10.1016/j.laa.2010.09.018",

language = "English (US)",

volume = "434",

pages = "1733--1744",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

number = "7",

}

TY - JOUR

T1 - Reconstructing matrices from minors

AU - Johnson, Charles R.

AU - Mollner, Joshua J.

AU - Winkler, Ashlyn M.

N1 - Funding Information: The research described in this paper was supported by NSF Grant # DMS-0751964. ∗ Corresponding author.

PY - 2011/4/1

Y1 - 2011/4/1

N2 - Which collections of mn minors of an m-by-n matrix uniquely determine the matrix, given some regularity conditions? For m=n=3, the 585 such collections, that are distinct up to symmetry, are determined. For general m, n, a necessary and a sufficient condition for reconstruction are given in terms of matchings in a bipartite graph. Among other particular results, those collections of entries for which there are minors that permit reconstruction one entry at a time are characterized.

AB - Which collections of mn minors of an m-by-n matrix uniquely determine the matrix, given some regularity conditions? For m=n=3, the 585 such collections, that are distinct up to symmetry, are determined. For general m, n, a necessary and a sufficient condition for reconstruction are given in terms of matchings in a bipartite graph. Among other particular results, those collections of entries for which there are minors that permit reconstruction one entry at a time are characterized.

KW - Arrangement bipartite graph

KW - Configuration bipartite graph

KW - Entry-wise sequential reconstruction

KW - Reconstruction of matrices from minors

KW - Unique reconstruction set

UR - http://www.scopus.com/inward/record.url?scp=79951677255&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79951677255&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2010.09.018

DO - 10.1016/j.laa.2010.09.018

M3 - Article

AN - SCOPUS:79951677255

SN - 0024-3795

VL - 434

SP - 1733

EP - 1744

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 7

ER -

Reconstructing matrices from minors

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this