Jacobi's identity and the König-Egerváry theorem
type: Item
instance of: scholarly article
title: Jacobi's identity and the König-Egerváry theorem
zbMATH Open document ID: 0541.05011
DOI: 10.1016/0012-365X(84)90152-3
author: Joseph P. S. Kung
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: The König-Egerváry Theorem states that the maximum size of a partial matching in a relation is equal to the minimum size of a separating set of lines (a set of rows or columns such that every nonzero entry of the associated adjacency matrix is contained in a row or column of the set). The following weaker version of Jacobi's identity is used to prove the above theorem: let \(\Pi\) be a nonsingular matrix with rows and columns indexed by the set I. If M,\(N\subset I\) and \(| M| =| N|\), then \(\Pi\) (\(M| N)\) is nonsingular iff \(adj \Pi(M^ c| N^ c)\) is nonsingular.
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 15A99
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 3859135
zbMATH Keywords: König-Egerváry Theorem
zbMATH Keywords: partial matching
zbMATH Keywords: adjacency matrix
MaRDI profile type: Publication
full work available at URL: 0012-365x(84)90152-3
OpenAlex ID: W2005791731
description: scientific article; zbMATH DE number 3859135