Multilinear Formula Lower Bounds for Sparse Determinants

Link to the article

Authors

Pruthvi Boyapati, Suryajith Chillara, and Pratyush Vempati

Publisher Information

• Preprint

Abstract

Raz (2009) proved that multilinear formulas computing the determinant of a generic n \times n matrix require size n^{\Omega(\log n)}. A fundamental question in understanding this lower bound is identifying which structural properties of the determinant drive this hardness. Is it the quadratic number of variables? The dense connectivity? Specific algebraic symmetries?

We establish that density is not essential. We prove the existence of n \times n symbolic matrices with only \Theta(n \log^6 n) nonzero entries - reducing the variable count by a factor of n/{\log^6 n} - such that any multilinear formula computing their determinants still requires size n^{\Omega(\log n)}. Our construction uses rectangle sampling from the complete bipartite graph to generate sparse matrices that simultaneously maintain perfect matchings (ensuring nonzero determinant) while exhibiting diagonal imbalance under random vertex permutations - a geometric property we identify as the key driver of factor imbalance in Raz’s framework.

This demonstrates that Raz’s partial derivatives method is remarkably robust to sparsification, and suggests that the fundamental source of multilinear hardness for determinant lies in expansion-like combinatorial structure rather than density. Our techniques combine concentration inequalities for dependent random variables with insights from random graph theory.