Rank axiom of modular supermatroids: A connection with directional DR submodular functions

Takanori Maehara, So Nakashima

Abstract

Matroids are fundamental combinatorial structures that abstract the concept of linear independence. While well-understood on distributive lattices, their generalization to supermatroids on modular lattices has historically lacked a complete axiomatic characterization. This paper bridges this gap by introducing a rank axiom based on directional DR-submodular functions. We establish the equivalence of several axioms for modular supermatroids, prove a strong exchange property, and demonstrate applications in optimization, specifically for problems like Principal Component Analysis (PCA).

Introduction: From Matroids to Supermatroids

In discrete mathematics, matroids provide a robust framework for defining independence, abstracting properties from vector spaces and graph theory. A key strength of matroid theory is the equivalence of various axiomatic definitions, such as those based on independent sets, bases, or rank functions.

Supermatroids extend this concept to lattices—ordered sets where any two elements have a unique join (ceiling) and meet (floor). While supermatroids on distributive lattices have been characterized for decades, modular lattices present a significant challenge. Modular lattices are essential for representing algebraic structures like subspaces of a vector space or normal subgroups, yet the standard rank function on these lattices often fails to satisfy traditional submodularity.

The Hierarchy of Lattices

The applicability of supermatroid axioms depends heavily on the underlying lattice geometry. While the Independence Axiom is broadly applicable, the Rank and Base axioms are sensitive to the specific class of lattice.

Hierarchy of lattice classes and their relationships.

As shown in the hierarchy above, modular lattices sit between distributive lattices and the broader class of lower semimodular lattices. This study specifically targets modular lattices, providing the "missing" rank property that characterizes their supermatroids. The authors show that while the Independence Axiom works for almost any lattice, the Rank and Base axioms are much more sensitive to the underlying lattice geometry (Modular vs. Lower Locally Modular).

Methods: Directional DR-Submodularity

The authors identify that standard submodularity—the idea of "diminishing returns" where adding an element to a smaller set is more valuable than adding it to a larger one—is insufficient for modular lattices. They introduce directional DR-submodular functions, a refinement that accounts for the specific paths or "directions" available within the lattice structure.

Lattice elements illustrating directional relationships.

By employing this new functional class, the authors prove the equivalence of four primary characterizations:

  • Height Axiom: The traditional definition of a supermatroid.
  • Independence Axiom: Defining the structure via maximal independent sets.
  • Rank Axiom: Utilizing the new directional DR-submodular rank function.
  • Base Axiom: Characterizing the structure through its bases.

Key Insights and Optimization

A critical finding is the Strong Exchange Property. This property ensures that one can move between different bases (maximal independent sets) in a controlled manner, which is the theoretical foundation for the success of greedy algorithms.

The paper also reveals a surprising connection to Principal Component Analysis (PCA). The authors show that the objective function for PCA (with a single data point) can be modeled as a valuated modular supermatroid. This explains why greedy approaches are effective for certain subspace selection problems. For "strong" DR-submodular functions, the authors prove that a simple greedy algorithm achieves a 1/2-approximation ratio under modular supermatroid constraints.

Conclusion and Future Work

This work provides a complete axiomatic framework for supermatroids on modular lattices, a significant step forward from the distributive case. However, challenges remain. The current rank axiom does not yet extend to lower-locally modular lattices, a broader class that includes modular lattices. Future research may focus on finding a universal rank axiom for these structures and refining approximation bounds by analyzing the "curvature" of the associated submodular functions.

Summary updated

Abstract

A matroid has been one of the most important combinatorial structures since it was introduced by Whitney as an abstraction of linear independence. As an important property of a matroid, it can be characterized by several different (but equivalent) axioms, such as the augmentation, the base exchange, or the rank axiom. A supermatroid is a generalization of a matroid defined on lattices. Here, the central question is whether a supermatroid can be characterized by several equivalent axioms similar to a matroid. Barnabei, Nicoletti, and Pezzoli characterized supermatroids on distributive lattices, and Fujishige, Koshevoy, and Sano generalized the results for cg-matroids (supermatroids on lower locally distributive lattices). In this study, we focus on modular lattices, which are an important superclass of distributive lattices, and provide equivalent characterizations of supermatroids on modular lattices. We characterize supermatroids on modular lattices using the rank axiom in which the rank function is a directional DR-submodular function, which is a generalization of a submodular function introduced by the authors. Using a characterization based on rank functions, we further prove the strong exchange property of a supermatroid, which has application in optimization. We also reveal the relation between the axioms of a supermatroid on lower semimodular lattices, which is a common superclass of a lower locally distributive lattice and a modular lattice.
BibTeX
@article{maehara2022rank,
  author = {Takanori Maehara and So Nakashima},
  title = {{Rank axiom of modular supermatroids: A connection with directional DR submodular functions}},
  journal = {Adv. Appl. Math.},
  year = {2022},
  doi = {10.1016/j.aam.2021.102304},
}
Figure