Completely strong superadditivity of generalized matrix functions

Minghua Lin, Suvrit SraarXiv 2014 · DOI · arXiv

Abstract

We prove that generalized matrix functions satisfy a block-matrix strong superadditivity inequality over the cone of positive semidefinite matrices. Our result extends a recent result of Paksoy-Turkmen-Zhang (2014). As an application, we obtain a short proof of a classical inequality of Thompson (1961) on block matrix determinants.

Introduction

In the study of linear algebra and matrix analysis, inequalities provide the foundation for understanding how matrix functions behave under operations like addition and partitioning. A central concept in this field is superadditivity. A function $f$ is considered superadditive if $f(A+B) \ge f(A) + f(B)$. A more robust property is strong superadditivity, which suggests that the marginal "gain" of adding a matrix $A$ to a base $C$ increases as the base itself grows (e.g., to $B+C$). Formally, for positive semidefinite (PSD) matrices, this is expressed as:

$$f(A + B + C) + f(C) \ge f(A + C) + f(B + C)$$

While this property is well-established for the determinant, recent research has sought to extend these findings to generalized matrix functions (GMFs), such as the permanent. This paper advances that effort by introducing and proving Completely Strong Superadditivity (CSS)—a block-matrix version of this inequality.

The Problem: From Scalars to Blocks

The primary challenge addressed in this research is whether the strong superadditivity observed in scalar-valued matrix functions holds when those functions are applied block-wise to larger matrices. In operator theory, the prefix "completely" often refers to properties that remain invariant when a map is applied to matrices of arbitrary block size.

The authors investigate whether, for a block matrix $\mathbf{A}$ where each block is a PSD matrix, applying a GMF to each block preserves the strong superadditivity inequality. This "block-wise" behavior is critical for understanding the structural properties of large-scale matrices used in quantum information theory and multivariate statistics.

Methodology: Multilinear Algebra and Tensors

The proof relies on the sophisticated machinery of multilinear algebra, specifically the theory of symmetry classes of tensors. The authors utilize three primary technical pillars:

  1. Induced Operators: Generalized matrix functions are represented as "induced operators" $K(T)$ acting on tensor spaces. This transformation allows the authors to shift the problem from the entries of a matrix to the properties of linear operators on higher-dimensional spaces.
  2. Compressions (Lemma 2.4): A pivotal technical insight involves proving that a block matrix formed by applying a GMF to each block of a larger PSD matrix is a "compression" (a specific type of projection) of a larger induced operator. This links the block structure directly to the tensor representation.
  3. Tensor Product Inequalities: By leveraging the known property that $k$-fold tensor products are strongly superadditive, the authors use the compression lemma to "pull" the inequality from the abstract tensor level down to the concrete block-matrix level.

Key Results and Insights

Theorem 1.3: The CSS Property

The central contribution of the paper is the formal proof of Theorem 1.3, which establishes that generalized matrix functions $d_\chi^G$ are CSS over the cone of PSD matrices. For block matrices $\mathbf{A, B, C}$, the following block-wise inequality holds:

$$\Phi(\mathbf{A} + \mathbf{B} + \mathbf{C}) + \Phi(\mathbf{C}) \ge \Phi(\mathbf{A} + \mathbf{C}) + \Phi(\mathbf{B} + \mathbf{C})$$

where $\Phi$ denotes the block-wise application of the GMF. This result confirms that these functions behave predictably and robustly even when nested within complex block structures.

Simplifying Thompson’s Inequality

A significant application of this theory is found in Section 3. The authors provide a new, remarkably short inductive proof of a classical result by Thompson (1961). Thompson’s original proof regarding block matrix determinants was notoriously complex; however, by applying the CSS framework, the result—$\det \mathbf{A} \le \det(\det_m(\mathbf{A}))$—emerges as a natural corollary. This demonstrates the power of the CSS property in simplifying long-standing problems in matrix theory.

Generalizability

The findings are not limited to the determinant. Because the results apply to any GMF defined by a character of degree 1, they encompass the permanent and other functions defined by group characters, suggesting that CSS is a fundamental characteristic of this class of functions.

Limitations and Future Directions

While the paper provides a significant theoretical advancement, several avenues for future research remain:

  • PSD Constraint: The proofs are currently restricted to the cone of positive semidefinite matrices. The behavior of GMFs on general Hermitian or non-Hermitian matrices remains an open, more complex problem.
  • Character Degree: The current proof assumes the character $\chi$ has a degree of 1. Whether these properties hold for higher-degree characters is yet to be determined.
  • Computational Applications: The paper focuses on theoretical elegance and proof simplification. Future work could explore whether these block-matrix inequalities can be leveraged to optimize algorithms for matrix approximation or to improve bounds in numerical linear algebra.

Summary updated

Abstract

We prove that generalized matrix functions satisfy a block-matrix strong superadditivity inequality over the cone of positive semidefinite matrices. Our result extends a recent result of Paksoy-Turkmen-Zhang (V. Paksoy, R. Turkmen, F. Zhang, Inequalities of generalized matrix functions via tensor products, Electron. J. Linear Algebra 27 (2014) 332-341.). As an application, we obtain a short proof of a classical inequality of Thompson (1961) on block matrix determinants.
BibTeX
@misc{lin2014completely,
  author = {Minghua Lin and Suvrit Sra},
  title = {{Completely strong superadditivity of generalized matrix functions}},
  year = {2014},
  eprint = {1410.1958},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.1958},
}
Figure