betaFeedback

WorksComputer Science

Determinant boundaries and gaps in determinantal complexity

Abstract

Landsberg, Manivel, and Ressayre constructed determinant-boundary components whose defining forms, for odd n >= 3, are limits of n x n determinants but cannot themselves be represented by determinants of that size. Their border determinantal complexity (DC) is therefore smaller than their exact DC. We prove that the difference can grow linearly with n. For every n >= 10, we construct an explicit homogeneous form of degree n, concise in n^2 variables, whose orbit closure is a boundary component, whose border DC is n, and whose exact DC is at least 2n - 1. Thus n rows suffice when limits are allowed, whereas every exact representation requires at least 2n - 1 rows. The same bound holds for the unpadded odd-skew forms at every odd n >= 3. We also prove that every concise degree-n boundary form in n^2 variables has exact DC at least n + 2. We construct three families of pairwise distinct boundary components. Together with the traceless determinant, they give at least floor((n-1)/2) + floor(n/3) components for every n >= 3, with an additional term counted explicitly in the paper. The main lower bound follows from a general degree lemma. If an affine matrix represents an irreducible homogeneous polynomial f of degree d and has globally free rank-one cokernel over the coordinate ring of f = 0, its size is at least 2d - 1. The adjugate factors into two nonzero kernel vectors, each requiring a coordinate of degree at least d - 1. Comparing their product with the degree of a cofactor proves the bound. The lemma is sharp for individual representations, as witnessed by algebraic branching programs. Whether the exact-versus-border gap can grow superlinearly remains open.

Introduction

The permanent of an n×nn \times n matrix YY is the polynomial

per⁡n(Y)=∑σ∈Sn∏i=1nYi,σ(i),\operatorname{per}_n(Y) = \sum_{\sigma\in S_n} \prod_{i=1}^{n} Y_{i,\sigma(i)},

where SnS_n is the set of permutations of {1,…,n}\{1, \ldots, n\}. The determinant is given by the same sum with the sign of σ\sigma attached to each term. The determinant can be computed by a polynomial number of arithmetic operations. The arithmetic complexity of the permanent is a central open problem in algebraic complexity theory.

Valiant [22] formulated this problem in terms of determinantal representations. A determinantal representation of a polynomial FF is a square matrix whose determinant is FF and whose entries are affine-linear forms in the variables of FF, that is, polynomials of degree at most one. The determinantal complexity (DC) of FF, denoted by dc⁡(F)\operatorname{dc}(F), is the smallest size of such a matrix. Valiant showed that a polynomial computed by an arithmetic formula of size ss has a determinantal representation of size linear in ss. He also proved that the permanent is complete for VNP, an algebraic analogue of NP, in characteristic different from two. Valiant’s determinantal complexity conjecture asks whether dc⁡(per⁡n)\operatorname{dc}(\operatorname{per}_{n}) grows faster than every polynomial in nn.

The border determinantal complexity dc⁡‾(F)\underline{\operatorname{dc}}(F) permits limits. It is the least mm such that FF is a coefficientwise limit of determinants of m×mm \times m matrices with affine-linear entries. The size mm remains fixed during the limit. Every exact representation is also such a limit, and neither a size-mm determinant nor a limit of size-mm determinants can have degree above mm. Consequently, for every nonzero polynomial FF,

deg⁡F≤dc⁡‾(F)≤dc⁡(F).(1)\deg F \le\underline{\operatorname{dc}}(F) \le\operatorname{dc}(F). \tag*{(1)}

In particular, a lower bound on border DC also gives the same lower bound on exact DC. Throughout the paper the ground field is C\mathbb{C}, and a form means a homogeneous polynomial: all of its monomials have the same total degree.

Mignon and Ressayre [17] proved the quadratic lower bound dc⁡(per⁡n)≥n2/2\operatorname{dc}(\operatorname{per}_{n}) \ge n^{2}/2 in characteristic zero. Landsberg, Manivel, and Ressayre [14] proved that the same bound holds for border DC. More recently, OpenAI’s September 2026 preprint [19] reports a cubic lower bound, dc⁡‾(per⁡n)=Ω(n3)\underline{\operatorname{dc}}(\operatorname{per}_{n}) = \Omega(n^{3}) over C\mathbb{C}. Related lower bounds from smooth restrictions and polar counts appear in the author’s earlier work [20, 21]. In addition to their lower bound for the permanent, Landsberg, Manivel, and Ressayre exhibit forms for which the second inequality in (1) is strict. The present paper concerns this distinction between exact and border complexity.

Geometric complexity theory (GCT), introduced by Mulmuley and Sohoni [18], studies orbit closures associated with polynomials such as the determinant. Let

On=GLn2⋅det⁡n\mathcal{O}_{n} = \mathrm{GL}_{n^{2}} \cdot\det_{n}

be the orbit of the determinant under invertible linear changes of its n2n^{2} variables. Its closure On‾\overline{\mathcal{O}_{n}} also contains their limits, and the determinant boundary is

∂On‾=On‾∖On.\partial\overline{\mathcal{O}_{n}} = \overline{\mathcal{O}_{n}} \setminus\mathcal{O}_{n}.

Closures are taken in the Zariski topology; over C\mathbb{C} the orbit closure also agrees with the closure in the usual complex topology. A polynomial is concise in its ambient variables if no invertible linear change of coordinates reduces their number. Equivalently, its first partial derivatives are linearly independent.

Every nonzero degree-nn form in On‾\overline{\mathcal{O}_{n}} has border DC nn. If it is concise and lies on the boundary, its exact DC is larger than nn. Indeed, a size-nn affine representation would have homogeneous degree-nn part det⁡L\det L, where LL is its linear part. Conciseness in n2n^{2} variables would force this linear substitution to be invertible, placing the form in On\mathcal{O}_{n} itself. Thus the orbit-closure formulation distinguishes border complexity from the size required by an exact representation.

Landsberg, Manivel, and Ressayre [14 Proposition 3.5.1] constructed such a concise boundary component for every odd n≥3n \ge3. Their construction starts with odd skew-symmetric matrices. Chen [6 Theorem 5.5.3] proved that adding one row and column gives another component. Hüt­tenhain [10] treats the traceless-determinant component and a further concise component at size four. The leading determinant coefficient of a singular matrix space gives a more general source of boundary points [12 Section 6.7.1]. The bounded-rank spaces of Huang and Landsberg [9] and the exterior-multiplication spaces studied by Landsberg and Manivel [13] provide further starting spaces for this construction.

These examples lead to two questions. How large can the difference between exact and border DC be on an explicit boundary component? How many distinct components can be obtained by varying the starting matrix space and adding rows and columns? We prove a linear lower bound for the first question and a uniform component count for the second.

Our contributions

Our main result is the following.

Theorem 1.1. For every n≥10n \ge10, there is an explicit homogeneous form fnf_n of degree nn, concise in n2n^2 variables, whose orbit closure is a determinant-boundary component and which satisfies

dc⁡(fn)=n,dc⁡(fn)≥2n−1.\operatorname{dc}(f_n)=n,\qquad\operatorname{dc}(f_n)\ge2n-1.

One may take fn=K2,n−10f_n=K_{2,n-10}, defined in § 3.5. For every odd n≥3n\ge3, the unpadded odd-skew form Qn,0Q_{n,0} also has these properties.

The defining determinant limits give dc⁡(fn)≤n\operatorname{dc}(f_n)\le n, and the degree gives the reverse inequality. The exact lower bound comes from a property of the whole hypersurface fn=0f_n=0: every polynomial matrix with determinant fnf_n has a free rank-one cokernel over its coordinate ring. For the unpadded odd-skew forms, this follows from unique factorization in that ring. For the Koszul forms, it follows from a calculation of the divisor class group and the depth of the two possible nonfree cokernels.

The passage from freeness to a size bound is a general degree argument. Suppose an affine matrix MM represents an irreducible homogeneous polynomial of degree dd and has a free rank-one cokernel on its zero set. Its adjugate factors there as uvTuv^T, where uu and vv are nonzero right- and left-kernel vectors. Each vector has a coordinate of degree at least d−1d-1. Since a cofactor of a size-mm affine matrix has degree at most m−1m-1, it follows that m≥2d−1m\ge2d-1. This is Theorem 4.1. The hypothesis is proved for every exact representation of the forms in Theorem 1.1; the resulting bound therefore applies to unrestricted affine determinantal representations.

In particular, the exact-minus-border gap is at least n−1n-1 and

dc⁡(fn)dc⁡(fn)≥2−1n.\frac{\operatorname{dc}(f_n)}{\operatorname{dc}(f_n)}\ge2-\frac{1}{n}.

For example, the degree-ten construction has border DC ten and exact DC at least nineteen. These are lower bounds on the exact complexity; the theorem does not determine its value.

We next construct three families of boundary components. They arise from odd skew-symmetric matrices, the block spaces of Huang and Landsberg, and middle Koszul maps. Each starting space can be padded by any number of rows and columns.

Theorem 1.2. Every form in the three families defined in § 3 is concise in n2n^2 variables, and its orbit closure is a determinant-boundary component. For fixed nn, the components obtained from different listed parameters are pairwise distinct. Including the traceless-determinant component, the boundary has at least

⌊n−12⌋+⌊n3⌋+κ(n),κ(n)=#{p≥2:(2p+1p)≤n},(2)\left\lfloor\frac{n-1}{2}\right\rfloor+\left\lfloor\frac{n}{3}\right\rfloor+\kappa(n),\qquad \kappa(n)=\#\left\{p\ge2:\binom{2p+1}{p}\le n\right\}, \tag*{(2)}

irreducible components for every $n\ge 3.

The odd-skew family includes every odd starting size rr from three to nn, with n−rn-r added rows and columns. It therefore unifies the unpadded construction of [14], Chen’s one-row extension, and arbitrary padding of the smallest skew block. The block family has starting sizes 6, 9, 12, …\ldots, and the Koszul family has starting sizes 10, 35, 126, …\ldots. The count in (2) is a lower bound; it does not classify the entire boundary. The proofs identify singular or higher-multiplicity loci determined by each polynomial and then compute its stabilizer, the group of linear changes of variables preserving that polynomial. The same loci distinguish the components. We also obtain general criteria for componenthood and for preservation of componenthood under padding.

Our final general lower bound excludes exact complexity n+1n+1 for every concise boundary point.

Theorem 1.3. Let n≥3n \ge3, and let ff be a concise degree-nn form on the determinant boundary in n2n^2 variables. Then

dc⁡(f)=n,dc⁡(f)≥n+2.\operatorname{dc}(f)=n,\qquad\operatorname{dc}(f)\ge n+2.

Theorem 7.1 proves the stronger statement that a homogeneous degree-nn form with at least n2−n+2n^2-n+2 essential variables cannot have exact DC equal to n+1n+1. For the padded odd-skew forms with starting size three, an explicit upper bound gives

n+2≤dc⁡(Q3,n−3)≤n+4.n+2\le\operatorname{dc}(Q_{3,n-3})\le n+4.

Thus the bound 2n−12n-1 in Theorem 1.1 applies to the unpadded odd-skew forms and all padded Koszul forms, rather than to every padded odd-skew form.

Organization of the paper

Section 2 gives a proof overview using the smallest odd-skew example. Section 3 defines the three families, and Section 4 proves the general degree bound. Sections 5 and 6 establish the cokernel property needed for Theorem 1.1. Section 7 treats general concise boundary points. The component proofs occupy Sections 8, 9, and 10, followed by the component count and general padding criteria. The remaining sections develop bounds from affine level sets, a reduction to regular representations of the determinant, and a criterion for rational matrix realizations. They also explain the limitations of these methods for obtaining a superlinear gap. Section 20 records the open questions.

Proof overview

The smallest odd-skew form illustrates both the determinant limit and the degree argument for exact complexity. Let x=(x1,x2,x3)Tx=(x_1,x_2,x_3)^{T}, let SS be a symmetric 3×33\times3 matrix with six independent entries, and put

A(x)=(0−x3x2x30−x1−x2x10).A(x)=\begin{pmatrix} 0 & -x_3 & x_2\\ x_3 & 0 & -x_1\\ -x_2 & x_1 & 0 \end{pmatrix}.

Then A(x)x=0A(x)x=0 and adj⁡A(x)=xxT\operatorname{adj} A(x)=xx^{T}. Expanding the determinant gives

det⁡(A(x)+tS)=t xTSx+t3det⁡S.(3)\det(A(x)+tS)=t\,x^{T}Sx+t^{3}\det S. \tag*{(3)}

For nonzero tt, the entries of A(x)+tSA(x)+tS are an invertible linear function of the nine variables, since a matrix decomposes uniquely into its skew-symmetric and symmetric parts. Multiplying one row by t−1t^{-1} therefore gives a polynomial in the determinant orbit O3\mathcal{O}_3, and

f=xTSx=lim⁡t→0t−1det⁡(A(x)+tS).f=x^{T}Sx=\lim_{t\to0}t^{-1}\det(A(x)+tS).

Thus dc⁡(f)=3\operatorname{dc}(f)=3: the limit proves the upper bound, and the degree proves the lower bound.

We next outline why every exact representation of ff has size at least five. Let MM be an m×mm \times m affine matrix with det⁡M=f\det M=f, and put R=C[x,S]/(f)R=\mathbb{C}[x,S]/(f). The matrix MM is singular over RR. The main algebraic input is that

coker⁡RM=Rm/MRm≃R.\operatorname{coker}_{R} M = R^{m}/MR^{m} \simeq R.

This means that the cokernel has one global generator, with no nonzero relation over RR. It implies that every row annihilating MM is a multiple of one row vTv^{T}. Since the rows of the adjugate annihilate MM modulo ff, we obtain

adj⁡M=uvTover R,Mu=0,vTM=0,\operatorname{adj} M = uv^{T}\quad\text{over }R,\qquad Mu=0,\qquad v^{T}M=0,

with u,vu,v nonzero.

Suppose all coordinates of uu had degree at most one. Lift them to polynomials of degree at most one before taking the quotient by ff. The entries of MuMu then have degree at most two and are divisible by the cubic ff. Hence they vanish identically. This is impossible, since a matrix with nonzero determinant has no nonzero kernel over the field of rational functions. Therefore uu has a coordinate of degree at least two. The same holds for vv.

Degrees add in the graded domain RR. Consequently some entry of uvTuv^{T}, and hence of adj⁡M\operatorname{adj} M, has degree at least four. A cofactor of an affine matrix of size mm has degree at most m−1m-1, so m≥5m\geq5. For an irreducible homogeneous polynomial of degree dd, the same argument gives a coordinate of degree at least d−1d-1 in each vector and yields m≥2d−1m\geq2d-1. § 4 proves this statement in full.

It remains to justify the cokernel hypothesis for every exact representation. The polynomial xTSxx^{T}Sx is linear in the entries of SS, and its coefficient polynomials are the products xixjx_i x_j. They vanish simultaneously only at x=0x=0, a set of codimension three. § 5 proves that, more generally, a polynomial linear in one group of variables defines a factorial coordinate ring when its coefficients have a common zero set of codimension at least three. Every determinant cokernel on such a hypersurface is free. This proves the hypothesis for xTSxx^{T}Sx and for all unpadded odd-skew forms.

The Koszul forms require a different freeness argument. Away from the zero value of their starting variables, they become ordinary determinants in the coefficient variables. A classification for the generic determinant leaves three possible rank-one cokernels. One is free. The other two extend to modules whose depths are too small on the omitted set, so neither can be the cokernel of a determinant representation. § 6 proves this assertion and establishes the lower bound at every n≥10n\geq10.

Finally, the component statements require an independent geometric argument. The defining limits give points of the determinant orbit closure. To show that their orbit closures are entire boundary components, we compute their stabilizer dimensions. We distinguish the components using singular and multiplicity loci that are preserved under every invertible linear change of variables.

Three families of boundary forms

We define the forms in Theorems 1.1 and 1.2. Each family is obtained from a singular matrix space by taking a leading determinant coefficient. The construction of this coefficient is standard [12 Section 6.7.1]. The component and distinctness statements are proved in § 8, § 10, and § 11.

Leading coefficients and padding

Let L⊂Mat⁡rL \subset\operatorname{Mat}_r be a linear space whose generic rank is r−cr-c, where c≥1c \ge1. Choose a complementary space SLS_L, so Mat⁡r=L⊕SL\operatorname{Mat}_r = L \oplus S_L, and let AA and SS be the generic matrices of these two spaces. We call LL the starting space, or seed space. For k≥0k \ge0, put n=r+kn = r+k and introduce independent matrices

U∈Mat⁡r,k,V∈Mat⁡k,r,Z∈Mat⁡kU \in\operatorname{Mat}_{r,k}, \qquad V \in\operatorname{Mat}_{k,r}, \qquad Z \in\operatorname{Mat}_k.

Define

Mt=(A+tSUtVZ),FL,k=[tc]det⁡Mt.(4)M_t = \begin{pmatrix} A+tS & U \\ tV & Z \end{pmatrix}, \qquad F_{L,k} = [t^c]\det M_t. \tag*{(4)}

References

  1. [2]M. D. Atkinson. Spaces of matrices with several zero eigenvalues. Bulletin of the London Mathematical Society 12(2) (1980), 89–95. https://doi.org/10.1112/blms/12.2.89.
  2. [3]W. Bruns and J. Herzog. Cohen–Macaulay Rings, revised edition. Cambridge Studies in Advanced Mathematics 39, Cambridge University Press, 1998.
  3. [4]R.-O. Buchweitz and G. J. Leuschke. Factoring the Adjoint and Maximal Cohen–Macaulay Modules over the Generic Determinant, American Journal of Mathematics 129(4) (2007), 943–981, especially Section 4.4. https://doi.org/10.1353/ajm.2007.0022. arXiv:math/0505315.
  4. [6]Sitan Chen. Geometry in Algorithms and Complexity: Holographic Algorithms and Valiant’s Conjecture. Harvard undergraduate thesis, 2016, Section 5.5. https://people.csail.mit.edu/sitanc/docs/gct.pdf.
  5. [7]Clément de Seguins Pazzis. Large spaces of bounded rank matrices revisited. Linear Algebra and its Applications 504 (2016), 124–189; arXiv:1507.05375, Theorem 1.7. https://arxiv.org/pdf/1507.05375.
  6. [8]Murray Gerstenhaber. On nilalgebras and linear varieties of nilpotent matrices, I. American Journal of Mathematics 80 (1958), 614–622. https://doi.org/10.2307/2372773.
  7. [9]Hang Huang and J. M. Landsberg. On Linear spaces of matrices of bounded rank. Selecta Mathematica 32, article 30 (2026); first posted 26 June 2023, arXiv:2306.14428. Theorem 3.1 and Section 9. https://doi.org/10.1007/s00029-026-01137-x.
  8. [10]Jesko Hüttenhain. Geometric Complexity Theory and Orbit Closures of Homogeneous Forms. Doctoral dissertation, TU Berlin, 2017. https://huettenhain.net/written/phd.pdf.DOI
  9. [11]C. Ikenmeyer and J. M. Landsberg. On the complexity of the permanent in various computational models. Journal of Pure and Applied Algebra 221 (2017), 2911–2927. arXiv:1610.00159.arxiv.org/abs/1610.00159
  10. [12]J. M. Landsberg. Geometry and Complexity Theory. Cambridge University Press, 2017. Author-hosted prepublication draft, Section 6.7.1. https://people.tamu.edu/~jml/simonsclass.pdf.DOI
  11. [13]J. M. Landsberg and Laurent Manivel. Equivariant spaces of matrices of constant rank. Pure and Applied Mathematics Quarterly 21(3) (2025), 1209–1244; arXiv:2212.04228 (2022), Section 3.1 and Proposition 3. https://arxiv.org/pdf/2212.04228.
  12. [14]J. M. Landsberg, L. Manivel, and N. Ressayre. Hypersurfaces with degenerate duals and the geometric complexity theory program. Commentarii Mathematici Helvetici 88 (2013), 469–484. https://ems.press/content/serial-article-files/43321.
  13. [15]Raphael Loewy and Nizar Radwan. On spaces of matrices with a bounded number of eigenvalues. Electronic Journal of Linear Algebra 3 (1998), 142–152, Theorem 2.7. https://doi.org/10.13001/1081-3810.1020.
  14. [16]Roy Meshulam. On two extremal matrix problems. Linear Algebra and its Applications 114/115 (1989), 261–271, Theorem 2 and Section 3. https://meshulam.net.technion.ac.il/files/2021/06/4.pdf.DOI
  15. [17]T. Mignon and N. Ressayre. A quadratic bound for the determinant and permanent problem. International Mathematics Research Notices 2004, no. 79, 4241–4253. https://doi.org/10.1155/S1073792804142566.
  16. [18]K. D. Mulmuley and M. Sohoni. Geometric complexity theory I: An approach to the P vs. NP and related problems. SIAM Journal on Computing 31(2) (2001), 496–526. https://doi.org/10.1137/S009753970038715X.
  17. [19]OpenAI. A cubic lower bound for border determinantal complexity of the permanent. Preprint, 24 September 2026. Author’s preprint.hub.valency.io/works/W_jy7u9k7r
  18. [20]K. Sheshadri. Conormal lower bounds for determinantal complexity: Fermat slices, tight bounds, and a ceiling. arXiv:2606.15970v2 (2026). https://arxiv.org/abs/2606.15970.
  19. [21]K. Sheshadri. Smooth slices and the limits of determinantal lower bounds. ECCC TR26-275 (2026). https://eccc.weizmann.ac.il/report/2026/275/.
  20. [22]L. G. Valiant. Completeness classes in algebra. Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC), 1979, 249–261. https://doi.org/10.1145/800135.804419.

Paper details

vlnc:W_h5vquzf4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT (multiple versions)

View statement
Looking for related papers…
Contents