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

Takanori Maehara, So Nakashima

TL;DR

This paper extends the elegant theory of matroids to the more complex world of modular lattices (such as the set of subspaces of a vector space). The authors introduce a new rank axiom based on directional DR-submodular functions, prove a strong exchange property for these structures, and demonstrate how this framework enables greedy optimization for problems like Principal Component Analysis (PCA).

What Problem Does This Paper Address?

In discrete mathematics, matroids are the gold standard for defining "independence" (abstracting the behavior of linear independence in vector spaces). One of their most powerful features is that they can be defined by several equivalent sets of rules, or "axioms"—most notably the rank axiom, which relies on submodular functions.

Researchers have long sought to generalize matroids to lattices (ordered sets where any two elements have a unique "ceiling" and "floor"), creating what are called supermatroids. While we’ve understood supermatroids on simple "distributive" lattices for decades, the theory breaks down on modular lattices. Modular lattices are crucial because they represent algebraic structures like subspaces and normal subgroups.

The core challenge: on modular lattices, the standard rank function is not submodular. This paper fills that gap by finding the "missing" property that characterizes the rank of a modular supermatroid.

Methods

The authors employ a mix of lattice theory and functional analysis. Their key innovation is the use of directional DR-submodular functions.

Standard submodularity essentially says that "adding an element to a small set provides more value than adding it to a large set." In a modular lattice, this isn't quite enough. The authors use a "downward" version of DR-submodularity (Diminishing Returns) which accounts for the specific "directions" or paths one can take through the lattice structure.

To prove their results, they utilize:

  • Axiomatic Equivalence: They prove that the Height Axiom (the standard definition of a supermatroid) is equivalent to their new Rank Axiom and a Middle (Base) Axiom.
  • Birkhoff-type Representations: They use geometric representations of modular lattices to prove a Strong Exchange Property, which is the theoretical backbone of greedy algorithms.

Datasets

Not discussed in the paper. This is a theoretical mathematical study; results are proven via formal logic and theorems rather than empirical testing on datasets.

Key Insights and Ideas

  • Submodularity is Insufficient: The authors provide a concrete example (the "diamond lattice") showing that a perfectly valid modular supermatroid can have a rank function that fails the standard lattice-submodularity test.
  • The Power of Direction: By relaxing submodularity into "directional DR-submodularity," they capture the exact constraints needed for modular structures. This property ensures that the "greedy" choice remains optimal or near-optimal.
  • The Hierarchy of Lattices: The paper clarifies exactly where these axioms work. They 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).
  • Connection to PCA: They show that the objective function of Principal Component Analysis (with a single data point) is actually a valuated modular supermatroid, explaining why greedy approaches can be effective in subspace selection.

Key Results

  • Characterization: The authors successfully provide four equivalent characterizations (Height, Independence, Rank, and Base axioms) for supermatroids on modular lattices.
  • Strong Exchange Property: They prove that modular supermatroids satisfy a strong exchange property, which allows for the movement between "bases" (maximal independent sets) in a controlled way.
  • Optimization Guarantees: They prove that for a "strong" DR-submodular function, a simple greedy algorithm achieves a 1/2-approximation ratio under a modular supermatroid constraint.
  • Duality: The paper defines dual matroids for modular supermatroids, showing that the rank function of a dual can be calculated directly from the primal.

Limitations and Future Work

  • Broadening the Lattice Class: The authors admit that their rank axiom fails to characterize supermatroids on lower-locally modular lattices (a broader class than modular lattices). Finding a universal rank axiom for these remains an open problem.
  • Algorithmic Refinement: While they provide a 1/2-approximation for certain optimization problems, they suggest that characterizing the "curvature" of these functions could lead to even tighter approximation bounds.
  • Non-Atomic Lattices: Much of the optimization discussion focuses on "atomic" modular lattices; extending the full suite of results to non-atomic cases is a suggested path for future research.

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