Classification of external Zonotopal algebras
Gleb Nenashev

          equationsection

          Classification of external Zonotopal algebras]Classification of external Zonotopal algebras



G. Nenashev]Gleb Nenashev
 Department of Mathematics,
   Stockholm University,
   S-10691, Stockholm, Sweden
nenashev@math.su.se





In this paper we work with power algebras associated to hyperplane arrangements. There are three main types of these algebras, namely, external, central, and internal zonotopal algebras. We classify all external algebras up to isomorphism in terms of zonotopes. Also, we prove that unimodular external zonotopal algebras are in one to one correspondence with regular matroids. For the case of central algebras we formulate a conjecture.









[
    [
    December 30, 2023
=====================






§ INTRODUCTION



In this paper we work with power algebras, which are quotients of polynomial rings by power ideals. We consider zonotopal ideals, which are associated to zonotopes.  These ideals were independently introduced in two different ways. There are three types of algebras. We will work with the definition from F. Ardila and A. Postnikov <cit.>; it comes from algebras generated by the curvature forms of tautological Hermitian linear bundles <cit.>, see also papers <cit.>, where people work with quotients algebras by these ideals. At the same time the definition and the name was established by O. Holtz and A. Ron <cit.>; it comes from Box-Splines and from Dahmen-Micchelli space <cit.>, see also the papers <cit.>. 





Let A∈^n× m be a matrix of rank n.
Denote by y_1,…,y_m∈^n the columns and by t_1,…,t_n∈^m the rows.
For a matrix A, we define the zonotope 
    Z_A:=⊕_i∈ [m] [0,y_i]⊂^n
 as the Minkovskii sum of intervals [0,y_i], i∈[m].
By (A) we denote the set of facets of  Z_A.
For any facet H∈(A), we define m(H) as the number of non-zero coordinates of the vector η_H A∈^m, where η_H∈^n is a normal for H. 

Let _A^(k) be the quotient algebra 
    _A^(k):=[x_1,…,x_n]/^(k)_A,

where ^(k)_A is the zonotopal ideal generated by the polynomials

    p_H^(k)=(η_h· (x_1,…,x_n))^m(H)+k,  H∈(A).


  



There are 3 main cases, where k=± 1 and 0; they were considered in <cit.>.


  * k=1: _A^=_A^(1) is the external zonotopal algebra for A;

  * k=0: _A^=_A^(0) is the central zonotopal algebra for A;

  * k=-1: _A^=_A^(-1) is the internal zonotopal algebra for A.


The case k>1 is not “zonotopal", because the ideal ^(k) generated by

    p_h=(h· (x_1,…,x_n))^m(h)+k,  h∈^n

is different from ^(k). They coincide only for the case where k≤ 1.

In the case k≤ -5, Hilbert series is not a specialization of the corresponding Tutte polynomial, see <cit.>.





 For a matrix A∈^n× m, the Hilbert series of zonotopal algebras are given by


  * (_A^)=q^m-nT_A(1+q,1/q);

  * (_A^)=q^m-nT_A(1,1/q);

  * (_A^)=q^m-nT_A(0,1/q),

where T_A is the Tutte polynomial of the vector configuration of the columns of A (i.e., vectors y_1,…,y_m).




There are other definitions of external algebras from <cit.>.
Let Φ_m be the square-free commutative algebra generated by ϕ_i, i∈[m], i.e., with relations

    ϕ_i ϕ_j=ϕ_j ϕ_i, i,j∈[m]   and   ϕ_i^2=0, i∈[m].







The external algebra _A^  is isomorphic to the subalgebra of Φ_A^:=Φ_m  generated by

    X_i:=t_i· (ϕ_1,…,ϕ_m), i ∈[n].


In papers <cit.> we constructed the analogue of Theorem <ref> in the case of central and internal zonotopal algebras for totally unimodular matrices, see the definition below. 



The main interesting examples of zonotopal algebras arise for totally unimodular matrices and for graphs.
The matrix A is totally unimodular if  any its minors is equal to ± 1 or 0. In this case the total dimensions of the algebras have a nice interpretation.
 Let A∈^n× m be a totally unimodular matrix of rank n. Then the total dimension


  * dim(^_A) is equal to the number of lattice points of Z_A;

  * dim(^_A) is equal to the volume of Z_A;

  * dim(^_A) is equal to the number of interior lattice points of Z_A.

 

The main examples of totally unimodular matrices are graphs. Namely, let G be a graph on n vertices; then the incidence matrix of any orientation of G is totally unimodular. To construct the zonotopal algebra, we should forget exactly one row for each connected component of G. These algebras are independent (up to isomorphism) of the choice of orientations and rows.

These graphical algebras were considered in <cit.>. In the graphical case Theorem <ref> can be written in graph theory terminology.
 Let G be a graph. Then the total dimension


  * dim(^_G) is equal to the number of forests in G;

  * dim(^_G) is equal to the number of trees in G (in the connected case).

 

It is well-known that the number of lattice points (volume) of the corresponding zonotope and the
number of forests (trees) of a graph are the same, see for example <cit.> (Points of the zonotope correspond to score vectors).

Let G be graph on the vertex set {0,1,2} with 4 edges 
    (0,1), (0,2), (1,2), and (1,2),

see fig. <ref>, left. Let us orient all edges in the sense of increasing corresponding number. Consider the incidence matrix after forgetting of 0-th row


    A:=[ -1  0  1  1;  0 -1 -1 -1 ],

see zonotope Z_A on fig. <ref>, right. 

 



The zonotope Z_A has 6 facets. We need the set of its normals (note that parallel facets have the same normal up to a factor). There are 3 normals


  * η_1=(1,0);

  * η_2=(0,1);

  * η_3=(1,1).


It is easy to check that m(η_1)=m(η_2)=3 and m(η_3)=2. Hence,

    ^(k)_A=⟨x_1^3+k,x_2^3+k, (x_1+x_2)^2+k⟩.

Then

  * (_A^)= 1+2q+3q^2+3q^3+q^4     and    dim(_A^)=10;  

  * (_A^)= 1+2q+2q^2     and     dim(_A^)=5; 

  * (_A^)= 1+q     and     dim(_A^)=2. 

It is easy to check that 10, 5, and 2 are exactly the number of lattice points, the area, and the number of interior lattice points of Z_A, respectively. Furthermore, 10 and 5 are the number of forests and trees in G.
In this case the Tutte polynomial is given by


    T_G(x,y)=T_A(x,y)=x+y+x^2+xy+y^2,

Anyone can check the formulas for the Hilbert series.




The following important property of external graphical algebras was proved in <cit.>.
 Given two graphs G_1 and G_2. Then the following are equivalent:


  * _G_1^ and _G_2^ are isomorphic as non-graded algebras;

  * _G_1^ and _G_2^ are isomorphic as graded algebras;

  * the graphical matroids M_G_1 and M_G_2 are isomorphic.
 

The following conjecture was formulated for the central case:
  Given two connected graphs G_1 and G_2, the following are equivalent:


  * _G_1^ and _G_2^ are isomorphic as non-graded algebras;

  * _G_1^ and _G_2^ are isomorphic as graded algebras;

  * the bridge-free matroids M_G_1 and M_G_2 are isomorphic.
 
Here the bridge-free matroid of a graph is its graphical matroid after deleting all bridges.


In the paper <cit.>, the -theoretic filtration was considered, see definition there. Denote by _G^ the -theoretic filtration of _G^.

Given two graphs G_1 and G_2 without isolated vertices, the filtered algebras _G_1^ and _G_2^ are isomorphic if and only if G_1 and G_2 are isomorphic. 





The structure of this paper is as follows: in  2 we present a classification of external zonotopal algebras and a conjecture for the central case; in  3 we prove our classification.


















































































































 §.§ Acknowledgments

This material is based upon work supported by the National Science Foundation under Grant  DMS-1440140 while the author was staying at the Mathematical Sciences Research Institute in Berkeley, California, during the program “Geometric and Topological Combinatorics” in the fall 2017. He also would like to thank the participiants of the PA-seminar for their comments.





 

§ MAIN RESULTS


Two linear spaces V_1 ⊂^m_1 and V_2 ⊂^m_2 are called  z-equivalent  if m_1=m_2=m and there is an invertible diagonal matrix  D∈^m× m and a permutation π∈ S_m such that

    V_1=V_2 (π D).


The matrices A_1 ∈^n_1× m_1  of rank n_1 and A_2 ∈^n_2 × m_2 of rank n_2  are called z-equivalent  if the span of rows of A_1 is z-equivalent to the span of rows of A_2.


It is easy to see that z-equivalence is an equivalence relation.

In the case when A_1 and A_2 do not have proportional columns, we can say that the matrix A_1 is equivalent to A_2 if and only if their zonotopes are equivalent (since we can reconstruct the “matrix” from the zonotope in this case).

This equivalence is weaker than that of matroids. 

If two matrices A_1 and A_2 are z-equivalent, then the matroids M_A_1 and M_A_2 are isomorphic.  






It is easy to check that _A_1^ and _A_2^ are isomorphic if A_1 and A_2 are z-equivalent. The converse also holds.


Let A_1 ∈^n_1× m_1 and A_2 ∈^n_2× m_2 be two matrices of rank n_1 and n_2 respectively.
Then the following are equivalent:


  * _A_1^ and _A_2^ are isomorphic as non-graded algebras;

  * _A_1^ and _A_2^  are isomorphic as graded algebras;

  * A_1 and A_2 are z-equivalent.
 


Let A_1 ∈^n_1× m_1 and A_2 ∈^n_2× m_2 be two matrices of ranks n_1 and n_2 respectively, with isomorphic external algebras _A_1^≅_A_2^. Then the matroids M_A_1 and M_A_2 are isomorphic. 




The following theorems shows that unimodular external zonotopal algebras are in one to one correspondence with regular matroids. 


Let A_1 ∈^n_1× m_1 and A_2 ∈^n_2× m_2 be two unimodular matrices of rank n_1 and n_2 respectively.
Then the following are equivalent:


  * _A_1^ and _A_2^ are isomorphic as non-graded algebras;

  * _A_1^ and _A_2^ are isomorphic as graded algebras;

  * A_1 and A_2 are z-equivalent.

  * the matroids M_A_1 and M_A_2 are isomorphic.
 

Since for graphs we have a totally unimodular matrix, all graphical matroids are regular; the converse is almost true. Every regular matroid may be constructed by combining graphic matroids, co-graphic matroids, and a certain ten-element matroid R_10, see <cit.> or the book <cit.>. In the graphical case the last theorem says that the algebra remembers graph up to 2-isomorphism, see <cit.>.


For the central case, we can extend Conjecture <ref> for all matrices. For a matrix A, we say that a column is a bridge-column if after deleting it the rank decreases.



Let A_1 ∈^n_1× m_1 and A_2 ∈^n_2× m_2 be two matrices of ranks n_1 and n_2 respectively.
Then the following are equivalent:


  * _A_1^ and _A_2^ are isomorphic as non-graded algebras;

  * _A_1^ and _A_2^ are isomorphic as graded algebras;

  * A_1' and A_2' are z-equivalent, where A'_i∈^(n_i-k_i)× (n_i-k_i) is the submatrix of A_i resulting after deleting all k_i bridge-columns and those k_i rows such that rk(A_i')=n_i-k_i.
 








§ PROOFS


Let B be a finite dimension algebra over . We say that an element r=∑_i=1^k a_2ia_2i+1 is reducible if a_i∈ B, i∈ [2k] are nilpotent elements.

For a nilpotent  element a∈ B we define the length ℓ(a) as the maximal ℓ such that a^ℓ≠ 0.


 Clearly, we have
1⟸ 2 ⟸ 3, so we will prove 1⟹ 3.
Let _A^ be our algebra. We will work with the square-free definition, i.e., _A^ is a subalgebra of Φ_m, where 

    m=max(ℓ(a): a∈_A^).

 (note that we can work with Φ_m only theoretically, i.e., we do not know this embedding). 
We know which element is the unit, so we can chose basis  x_1,…, x_n of nilpotents of _A^ with the following property:

    ℓ(x+r)≥ℓ(x),
 for any reducible r∈_A^ and x∈{x_1,…,x_n}. Since we can define the algebra via some matrix A, then there is such basis.




Any element has the representation
 
    x_i=∑_k=1^m a_i,kϕ_i + r_i,

 where a_i,k∈ and r_i is reducible. Let A'={a_i,k: (i,k)∈[n]×[m]} be the corresponding matrix. Our goal is to reconstruct A' up to z-equivalece.
 
 Consider the projective space ^n-1 over . To finish the proof we should find the multiset 
    𝒜:={(a_1,k,a_2,k,… ,a_n,k)∈^n-1, k∈[m]}.
 
 
 
Define the set S of all non-zeroes s∈ such that there are i≠ j∈[n] and a non-zero t∈ for which

    ℓ(x_i-sx_j)<ℓ(x_i-tx_j).

It is easy to see that S is exactly the set 

    {a_i,k/a_j,k: i,j∈ [n], k∈[m], and a_i,k, a_j,k≠ 0}.

Then S is a finite set.
  Define a theoretical set 𝒮 of rows of X as  
  
    𝒮:={(s_1,s_2,… ,s_n)∈^n-1, s_i∈ S∪{0}}.
 

 
Any element of 𝒜 is an element of 𝒮, so it is enough to find the multiplicity of any s∈𝒮. 

Consider the following partial order on elements of ^n-1:
  
    (p_1,p_2,… ,p_n)≥ (p_1',p_2',… ,p_n')

 if there is t∈ such that
 
    ∀ i∈ [n], p'_i =  tp_i
    
     0.

Note that if, for any s, we know the summary multiplication of all s'≥ s in 𝒜, then we can calculate multiplicity of all elements.

Given s∈𝒮, then the summary multiplication of all s'≥ s is equal to 
    ℓ(∑_i∈ I b_i x_i)-ℓ(∑_i∈ I c_i x_i),

where 
 
  * I⊆ [n] is the support of s;
 
  * b_i, i∈ I are generic;
 
  * c_i, i∈ I are generic with the linear condition ∑_i∈ Ic_is_i=0.
  
  Let us check it:
 
    ℓ(∑_i∈ I b_i x_i)=
      ℓ(∑_i∈ I b_i (∑_k=1^m a_i,kϕ_k+r_k))=ℓ(∑_i∈ I b_i (∑_k=1^m a_i,kϕ_k))=
    
     = ℓ(∑_k=1^m (∑_i∈ I b_ia_i,k)ϕ_k)=#{i∈ k: ∑_i∈ I b_ia_i,k≠0},

   Similarly we have
   
    ℓ(∑_i∈ I c_i x_i)=#{i∈ k: ∑_i∈ I c_ia_i,k≠0}.

   
Since b_i, i∈ I and c_i, i∈ I are generic with one condition ∑_i∈ Ic_is_i=0, we have the following property:
 if ∑_i∈ I b_ia_i,k≠ 0 then 
∑_i∈ I c_ia_i,k=0 if and only if (a_1,k,…,a_n,k)≥ s.

Hence, we can compute the multiplicity of any s.    


We know 1⟺ 2 ⟺ 3 ⟹ 4 by Theorem <ref>, where we  also reconstructed a matrix, so we know the matroid.



 3 ⟸ 4. Let A_1 and A_2 be two totally unimodular matrices which give the same regular matroid (we assume that the order of elements are the same). 
  
Also if M is a regular matroid, then all orientations of M differ only by reorientations (see Corollary 7.9.4  <cit.>). Hence, we can multiply some columns of A_2 by -1 and get A_2' such that A_1 and A_2' have the same oriented matroid.
 
 It is well-known that if we have a totally unimodular matrix A_i, then all minimal linear dependents of its columns have coefficients ± 1. We get that matrices A_1 and A_2' have linear dependents with the same coefficients and, hence, A_1∼_z A_2'∼_z A_2.


8

AS A. A. Akopyan, A. A. Saakyan, 
A system of differential equations that is related to the polynomial class of translates of a box spline,  Mat. Zametki 44:6 (1988),  pp. 705–724

AP F. Ardila, A. Postnikov, 
Combinatorics and geometry of power ideals, Trans. of the AMS 362:8 (2010), pp 4357–4384.


Ar V. I. Arnold,
Remarks on eigenvalues and eigenvectors of Hermitian matrices, Berry phase, adiabatic connections and quantum Hall effect, Selecta Mathematica 1:1 (1995), 1–19
	
	
Berget
A. Berget, Products of linear forms and Tutte polynomials,
European J. Combin. 31 (2010), pp. 1924–1935.

BergetIn
A. Berget, Internal Zonotopal Algebras and the Monomial Reflection Groups, <https://arxiv.org/abs/1611.06446>

Be O. Bernardi, Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings, Electronic J. Combinatorics 15:1 (2008).

Oriented A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G. M. Ziegler, Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications (1999).







DM W. Dahmen, A. Micchelli, On the local linear independence of translates of a box spline,  Studia Math. 82:3 (1985), pp.243–263

BR C. De Boor, A. Ron, On polynomial ideals of finite codimension with applications to box spline theory, J. Math. Anal. Appl. 158:1 (1991), pp. 168–193

CP C. De Concini, C. Procesi, Topics in hyperplane arrangements, polytopes and
box-splines, Universitext, Springer, New York, 2011.

DR N. Dyn, A. Ron, Local approximation by certain spaces of exponential polynomials,
approximation order of exponential box splines, and related interpolation problems, Trans.
Amer. Math. Soc. 319 (1990), no. 1, 381–403.


 
HR O. Holtz, A. Ron, Zonotopal algebra, Advances in Mathematics 227 (2011), pp 847–894.

HRX O. Holtz, A. Ron, Z. Xu, Hierarchical zonotopal, spaces.Transactions of the American Mathematical Society 364.2 (2012): 745-766.

Huang B. Huang, Monomization of Power Ideals and Generalized Parking
Functions, <https://math.mit.edu/research/highschool/primes/materials/2014/Huang.pdf>

KN1 A. N. Kirillov, G. Nenashev, On Q-deformations of Postnikov-Shapiro algebras, Séminaire Lotharingien de Combinatoire, 78B.55, FPSAC (2017) 12 pp.

KN2 A. N. Kirillov, G. Nenashev, Unimodular zonotopal algebra, in preparation

KW D. J. Kleitman, K. J. Winston, Forests and score vectors, Combinatorica 1:1 (1981), pp 49–54.

LenzMat M. Lenz,  Zonotopal algebra and forward exchange matroids. Advances in Mathematics 294 (2016), 819–852. 



LenzBS M. Lenz,  Lattice Points in Polytopes, Box Splines, and Todd Operators. International Mathematics Research Notices 2015:14 (2016),  5289–5310. 

LenzH M. Lenz, Hierarchical Zonotopal Power Ideals, 
European Journal of Combinatorics 33 (2012), pp. 1120-1141.

NR L. Nan, A. Ron , External zonotopal algebra, Journal of Algebra and its Applications 13.02 (2014):1350097.

NS G. Nenashev, B. Shapiro, “K-theoretic” analog of Postnikov-Shapiro algebra distinguishes graphs, Journal of Combinatorial Theory, Series A, 148 (2017), pp. 316–332.

Ne G. Nenashev, Postnikov-Shapiro algebras, graphical matroids and their generalizations,   <https://arxiv.org/abs/1509.08736>






Oxley J. G. Oxley, Matroid theory, Oxford University Press, USA, 2006. 

Seymour P. D. Seymour, Decomposition of regular matroids, Journal of combinatorial theory, Series B, 28:3 (1980), pp.305–359.

PS A. Postnikov, B. Shapiro, Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Amer. Math. Soc. 356:8 (2004),  pp 3109–3142.

PSS A. Postnikov,  B. Shapiro, M. Shapiro, Algebras of curvature forms on homogeneous manifolds, Differential topology, infinite-dimensional Lie algebras, and applications, Amer. Math. Soc. Transl. Ser. 2, 194 (1999), pp 227–235.

SS B. Shapiro, M. Shapiro,  On the ring generated by Chern 2-forms on SL_n/B, C. R. Acad. Sci. Paris. I Math. 326:1 (1998),  pp 75–80.

Shan J. J. Shan, A special case of Postnikov-Shapiro conjecture 
<https://arxiv.org/abs/1307.5895>

SX B. Sturmfels, Z. Xu, Sagbi bases of Cox-Nagata rings, J. Eur. Math. Soc. 12 (2010), no. 2, 429–459

Whitney H. Whitney, 2-isomorphic graphs, American Journal of Mathematics 55 (1933),  pp. 245–254.




