Linear and matrix generalizations of some combinatorial min-max theorems

Nik Weaver · 2026

Read Linear and matrix generalizations of some combinatorial min-max theorems by Nik Weaver (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30048.txt.

Introduction

Nik Weaver reviews linear and matrix extensions of four classic min-max theorems. Hall's marriage theorem and König's theorem on bipartite matchings anchor the survey. Dilworth's theorem on chains and antichains in ordered sets and Menger's theorem on disjoint paths in directed graphs complete the set. The paper relates the linear and matrix versions, showing how matching, ordering and path ideas extend beyond their first settings. It maps generalizations carrying min-max principles into linear algebra and matrix theory.

Catalog record

CREATORNik Weaver
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE87077
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30048

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Linear and matrix generalizations of some combinatorial min-max theorems Nik Weaver Abstract . We review known linear and matrix generalizations of Hall’s classic “marriage theorem” and Kőnig’s theorem on partial matchings in bipartite graphs, and relate them to linear and matrix generalizations of Dilworth’s theorem about chains and antichains in posets and Menger’s theorem about disjoint paths in directed graphs. 1991 Mathematics Subject Classification primary 15A03, 05C50; secondary 15A30, 05D15, 05C40 1. The linear setting 1.1. Hall’s theorem Hall’s marriage theorem [ 6 ] , in its most memorable (albeit informal, and perhaps outdated) formulation [ 7 ] , says that given n boys and m girls, if for every 1\leq k\leq n every set of k boys collectively know at least k girls, then the boys can be married off in such a way that each boy marries a girl he knows. This theorem can be generalized to the linear setting. Let the scalar field be \mathbb{F}=\mathbb{R} or \mathbb{C} . Given a relation R\subseteq\mathbb{F}^{n}\times\mathbb{F}^{m} with n\leq m , define the neighborhood of a nonzero vector u\in\mathbb{F}^{n} relative to R to be the set N(u)=\{w\in\mathbb{F}^{m}:\mbox{ there exists }v\in\mathbb{F}^{n}\mbox{ with }(v,w)\in R\mbox{ and }u\not\perp v\}, and let the neighborhood of any set S\subseteq\mathbb{F}^{n} be N(S)=\bigcup_{u\in S}N(u)\subseteq\mathbb{F}^{m}. We define a saturated matching in R to be a set of pairs (v_{1},w_{1}),\ldots,(v_{n},w_{n})\in R such that the v_{i} ’s constitute a basis of \mathbb{F}^{n} and the w_{i} ’s are linearly independent in \mathbb{F}^{m} . Theorem 1.1 . (Linear marriage theorem) Let m\geq n\geq 1 and let R\subset\mathbb{F}^{n}\times\mathbb{F}^{m} be finite. Then there is a saturated matching in R if and only if {\rm dim}\,{\rm span}(N(S))\geq{\rm dim}\,{\rm span}(S) for every finite subset S of \mathbb{F}^{n} . For the forward direction, suppose (v_{1},w_{1}),\ldots,(v_{n},w_{n}) is a saturated matching in R . For any finite S\subset\mathbb{F}^{n} , if {\rm dim}\,{\rm span}(S)=k then the orthocomplement of {\rm span}(S) has dimension n-k and hence can contain at most n-k of the v_{i} ’s. This means that at least k of the v ’s contribute to N(S) , i.e., N(S) contains at least k of the w_{i} ’s and hence its span has dimension at least k . Thus {\rm dim}\,{\rm span}(N(S))\geq{\rm dim}\,{\rm span}(S) for every S . The converse is easily deduced from Edmond’s matroid intersection theorem [ 4 , Theorem (69)] (cf. [ 11 , Theorem 1*] ), but it is amusing to note that one can also give an elementary proof that follows the pattern of Halmos and Vaughan’s inductive proof of the classical marriage theorem [ 7 ] : assume the theorem is true for all smaller values of n and, for the given value of n , for all smaller |R| (= the cardinality of R ), then separate into the two cases where (1) for every 1\leq k<n , every linearly independent set S\subset\mathbb{F}^{n} of cardinality k satisfies {\rm dim}\,{\rm span}(N(S))\geq k+1 and (2) for some 1\leq k<n there is a linearly independent set S\subset\mathbb{F}^{n} of cardinality k with {\rm dim}\,{\rm span}(N(S))=k exactly. We can then invoke the induction hypothesis, in the first case for smaller |R| and in the second case for smaller n . The interested reader is invited to fill in the missing details. In the special case where n=m , we get a perfect matching in R , where the v_{i} ’s and the w_{i} ’s both form bases of \mathbb{F}^{n} and the map v_{i}\mapsto w_{i} extends to a linear isomorphism of \mathbb{F}^{n} with itself, rather than merely a linear injection from \mathbb{F}^{n} into \mathbb{F}^{m} . We can draw several consequences from Theorem 1.1 . First, the classical marriage theorem follows easily from it. Given a relation r\subseteq\{1,\ldots,n\}\times\{1,\ldots,m\} , let the neighborhood of a set s\subseteq\{1,\ldots,n\} relative to r be the set n(s)=\{j\in\{1,\ldots,m\} : there exists i\in s with (i,j)\in r\} . Let a saturated matching in r be a set of pairs (i_{1},j_{1}),\ldots,(i_{n},j_{n})\in r such that \{i_{1},\ldots,i_{n}\}=\{1,\ldots,n\} and the j ’s are distinct. Corollary 1.2 . (Hall’s theorem) Let m\geq n\geq 1 and let r\subseteq\{1,\ldots,n\}\times\{1,\ldots,m\} . Then there is a saturated matching in r if and only if |n(s)|\geq|s| for all s\subseteq\{1,\ldots,n\} . Proof. The forward implication is trivial. For the reverse implication, assume |n(s)|\geq|s| for all s\subseteq\{1,\ldots,n\} and let R\subset\mathbb{F}^{n}\times\mathbb{F}^{m} be the set of pairs (e_{i},e_{j}) with (i,j)\in r , where (e_{i}) are the standard basis vectors. For any finite subset S of \mathbb{F}^{n} , let s=\{i\in\{1,\ldots,n\}:e_{i}\not\perp S\} . Then S\subseteq{\rm span}\{e_{i}:i\in s\} , so {\rm dim}\,{\rm span}(S)\leq|s| , and N(S)=\{e_{j}:j\in n(s)\} , so {\rm dim}\,{\rm span}(N(S))=|n(s)| . Thus the cardinality condition on s assumed here entails the dimension condition on S from Theorem 1.1 , and we conclude from that result that there is a saturated matching in R in the sense used there. This immediately implies that there is a saturated matching in r . ∎ Theorem 1.1 is essentially due to Lovász, cf. [ 11 , Theorem 1*] . His formulation was couched in terms of the maximum rank of matrices in linear subspaces of M_{m,n}=M_{m,n}(\mathbb{F}) . The connection to Theorem 1.1 comes from the fact that every pair (v,w)\in\mathbb{F}^{n}\times\mathbb{F}^{m} induces a rank one linear transformation wv^{*}:u\mapsto\langle u,v\rangle w from \mathbb{F}^{n} to \mathbb{F}^{m} . For any linear subspace \mathcal{V} of M_{m,n} and any linear subspace E of \mathbb{F}^{n} , write \mathcal{V}[E]={\rm span}\{Av:A\in\mathcal{V}\,\,{\rm and}\,\,v\in E\}\subseteq\mathbb{F}^{m}. Observe that if \mathcal{V}_{R} is the span of \{wv^{*}:(v,w)\in R\} , then for any subset S of \mathbb{F}^{n} we have {\rm span}(N(S))=\mathcal{V}_{R}[{\rm span}(S)]. We can infer Lovász’s version of Theorem 1.1 using the following fact. Proposition 1.3 . Let A_{1},\ldots,A_{d} be rank one matrices in M_{m,n} with A_{i}=w_{i}v_{i}^{*} ( 1\leq i\leq d ). Then A_{1}+\cdots+A_{d} has rank d if and only if v_{1} , \ldots , v_{d} are linearly independent in \mathbb{F}^{n} and w_{1} , \ldots , w_{d} are linearly independent in \mathbb{F}^{m} . Proof. If v_{1} , \ldots , v_{d} are linearly dependent then their span has dimension at most d-1 and the orthocomplement, {\rm span}(v_{1},\ldots,v_{d})^{\perp} , has dimension at least n-(d-1) . This orthocomplement is contained in the kernel of each A_{i} and hence is also contained in the kernel of A_{1}+\cdots+A_{d} , showing that the rank of the sum is at most d-1 . Similarly, the image of A_{1}+\cdots+A_{d} is contained in the span of w_{1} , \ldots , w_{d} , so if those vectors are linearly dependent then the image of the sum can have dimension at most d-1 , again showing that its rank is at most d-1 . Conversely, suppose v_{1} , \ldots , v_{d} and w_{1} , \ldots , w_{d} are both linearly independent. Let u be any vector in the kernel of A_{1}+\cdots+A_{d} . Then \langle u,v_{1}\rangle w_{1}+\cdots+\langle u,v_{d}\rangle w_{d}=0, so linear independence of the w_{i} ’s entails that \langle u,v_{1}\rangle=\cdots=\langle u,v_{d}\rangle=0, and hence u\in{\rm span}(v_{1},\ldots,v_{d})^{\perp} . We conclude that {\rm ker}(A_{1}+\cdots+A_{d})={\rm span}(v_{1},\ldots,v_{d})^{\perp} (as the reverse containment is trivial). Since the v_{i} ’s are linearly independent the dimension of their span is d , so this shows that the kernel of A_{1}+\cdots+A_{d} has dimension exactly n-d , which implies that A_{1}+\cdots+A_{d} has rank d . ∎ Corollary 1.4 . (Lovász’s theorem) Let m\geq n\geq 1 and let \mathcal{V} be a linear subspace of M_{m,n} . Suppose \mathcal{V} is generated by rank one matrices. Then \mathcal{V}

Read the complete text