11institutetext: University of Bologna, Bologna, Italy 11email:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext: University of Modena, Modena,
Italy, 22email<EMAIL_ADDRESS>
# Geometric Deep Learning: a Temperature Based
Analysis of Graph Neural Networks

Lapenna M. 11 0000-0001-5293-9499 Faglioni F 22 0000-0002-3327-8840
Zanchetta F 11 0000-0003-4075-7641 Fioresi R 11 0000-0003-2294-2755

###### Abstract

We examine a Geometric Deep Learning model as a thermodynamic system treating
the weights as non-quantum and non-relativistic particles. We employ the
notion of temperature previously defined in [7] and study it in the various
layers for GCN and GAT models. Potential future applications of our findings
are discussed.

###### Keywords:

Geometric Deep Learning Statistical Mechanics Machine Learning.

##  1 Introduction

Machine learning and statistical mechanics share a common root; starting from
the pioneering works by Jaynes ([9]) and Hopfield ([8]), up to the visionary
theory of (deep) Boltzmann machines ([1], [14]), it is clear there is a common
ground and the understanding of statistically inspired machine learning models
can bring a new impulse to the field. The powerful language of statistical
mechanics, connecting the elusive microscopic and measurable macroscopic
physical quantities seems the perfect framework to tackle the difficult
interpretation questions that the successful deep neural networks present.
Indeed many researchers (see [4], [5] and refs. therein) have conducted a
thermodynamic study, through analogies, of various actors in the most popular
algorithms, Deep Learning above all, and yet such analogies were not able to
fully elucidate the mechanisms of generalization and representability that
still elude our understanding. Along the same vein, new mathematical modeling,
inspired by thermodynamics, brought along new interesting mathematics, see
[3], [13], and in particular [15], that seems especially suitable to model the
dissipative phenomenon we observe in the SGD experiments.

The purpose for our present paper is to initiate this thermodynamic analysis
for the Geometric Deep Learning algorithm along the same line of our previous
works [7] and [11] on more traditional Convolutional Neural Networks (CNN). We
shall treat the parameters of the model as a thermodynamic system of particles
and we exploit the sound notion of temperature we have previously given in [7]
and [11]. Then, we study the temperature of the system across layers in Graph
Convolutional Networks (GCN) [23] and Graph Attention Networks (GAT) [25].

Our paper is organized as follows. In Sec. 2 we briefly recall the
correspondence between thermodynamics concepts and neural networks ones ([7]).
In Sec. 3 we present a Geometric Deep Learning model on the MNIST Superpixels
dataset ([18]) and we study the temperature of layers comparing with the
behaviour found for the CNN architecture in [7] and [11]. In particular, we
study the dependence of temperature from the two hyperparameters learning rate
and batch size at the end of the training, when loss and accuracy have reached
their equilibrium values. We also analyse the dynamics of the weights inside a
single Graph Convolutional layer. We consider both a GCN and a GAT models and
compare the results. In Sec. 4 we draw our conclusions and we lay foundations
for future work.

##  2 Thermodynamics and Stochastic Gradient Descent

We briefly summarize the thermodynamic analysis and modelling appearing in
[4], [7], and [11].

Stochastic Gradient Descent (SGD) and its variations (e.g. Adam) are common
choices, when performing optimization in Deep Learning algorithms.

Let $\Sigma=\\{z_{i}\,|1\leq i\leq N\\}\subset\mathbb{R}^{D}$ denote a dataset
of size $N$, i.e., $|\Sigma|=N$, $L=(1/N)\sum L_{i}$ the loss function, with
$L_{i}$ the loss of the $i$-th datum $z_{i}$ and $\mathcal{B}$ the minibatch.
The update of the weights $w=(w_{k})\in\mathbb{R}^{d}$ of the chosen model
(e.g., Geometric Deep Learning model), with SGD occurs as follows:

$w(t+1)=w(t)-\eta\nabla_{\mathcal{B}}L(w),\quad\hbox{with}\quad\nabla_{\mathcal{B}}L:=\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}\nabla
L_{i}$ (1)

where $\eta$ denotes the learning rate. Equation (1) is modelled in [4] by the
stochastic ODE (Ito formalism [24]) expressed in its continuous version as:

$dw(t)=-\eta\nabla L(w)dt+\sqrt{2\zeta^{-1}D(w)}dW(t)$ (2)

where $W(t)$ is the Brownian motion term modelling the stochasticity of the
descent, while $D(w)$ is the diffusion matrix, controlling the anisotropy of
the diffusivity in the process. The quantity $\zeta=\eta/(2|\mathcal{B}|)$ in
[4], is called the temperature. It accounts for the “noise” due to SGD: small
minibatch sizes or a high learning rate will increase the noise in the
trajectories of the weights during training.

In [7], the time evolution of the parameters is written in continuous and
discrete version as:

$dw(t)=-\eta\nabla_{\mathcal{B}}L(w)dt,\qquad
w(t+1)=w(t)-\eta\nabla_{\mathcal{B}}L(w)$ (3)

The stochastic behaviour modelled by (3) is then accounted for introducing a
microscopic definition of temperature mimicking Boltzmann statistical
mechanics. We first define the instantaneous temperature $\mathcal{T}(t)$ of
the system as its kinetic energy $\mathcal{K}(t)$ divided by the number of
degrees of freedom $d$ (in our case the dimension of the weight space) and a
constant $k_{B}>0$ to obtain the desired units:

$\mathcal{T}(t)=\frac{\mathcal{K}(t)}{k_{B}\,d}=\frac{1}{k_{B}\,d}\sum_{k=1}^{d}\frac{1}{2}m_{k}\,v_{k}(t)^{2}$
(4)

where $v_{k}(t)$ is the instantaneous velocity of one parameter, computed as
the difference between the value of the $k^{\mathrm{th}}$ parameter at one
step of training and its value at the previous step (the shift in time $\Delta
t$ is unitary since we are computing the instantaneous velocity between
consecutive steps or epochs):

$v_{k}(t)=\frac{w_{k}(t)-w_{k}(t-1)}{\Delta t}$ (5)

In the formula for the kinetic energy, $m_{k}$ is the mass of parameter
$w_{k}$ and we set it to $1$. This is because we have do not know if the
different role of the parameters can be modelled through a parallelism with
the concept of mass.

The thermodynamic temperature is then the time average of $\mathcal{T}(t)$:

$T=\frac{1}{\tau}\int_{0}^{\tau}\mathcal{T}(t)\,dt=\frac{1}{\tau
k_{B}\,d}\int_{0}^{\tau}\mathcal{K}(t)=\frac{K}{k_{B}\,d}$ (6)

where $K$ is the average kinetic energy and $\tau$ is an interval of time long
enough to account for small variation in temperature. In [7] we interpret this
system as evolving at constant temperature: at each step the temperature is
reset (analogy with system in contact with heat reservoir). Hence we do not
have a constant energy dynamics, as it is commonly referred to in atomic
simulations, but we are faced with a dissipative effect occurring at each
step.

The thermodynamic analysis performed in [7] and summarized here implies that
with SGD we have a residual velocity for each particle even after equilibrium
is reached. Our system does not evolve according to Newton dynamics and in
particular the mechanical energy is not constant. The fact we maintain a
residual temperature at equilibrium with a constant temperature evolution
means that we achieve a minimum of free energy, not of the potential energy
i.e. our loss function. This fact is stated in [4] and is well known among the
machine learning and information geometry community (see also [3]).

Let us summarize the key points of the system dynamics. We have:

– No costant mechanical energy $K+V$, where
$K=\sum_{k=1}^{d}(1/2)m_{k}v_{k}^{2}$ is the kinetic energy and $V=L$ ($L$ the
loss function) is the potential energy;

– No maximization of entropy,

All of this is due to the stochasticity of SGD which is enhanced by small
sizes of minibatch and high learning rate, as we shall elucidate more in our
experimental section together with an analysis of the temperature in the
layers.

##  3 Experiments

In this section we perform experiments with Geometric Deep Learning models on
MNIST Superpixels PyTorch dataset ([18]), in order to test the dependence of
the thermodynamic temperature from the hyperparameters learning rate and batch
size. We examine the temperature of different layers and we look at the mean
squared velocities of the weights of a single layer.We also analyze some key
differences with the findings in [7] and in [11], where we proposed pruning
techniques based on the notion of temperature.

We choose to investigate the behaviour of two separate and important Graph
Neural Network (GNN) architectures. First, we implement a model using Graph
Convolutional Network (GCN) layers from [23]. Then, we make a comparison with
a Graph Attention Network (GAT) model employing attention mechanism during the
convolution [25]. We stress that, in the literature, GAT models have
outperformed GCN’s in classification problems on superpixel images. We
consider both models in order to compare the weights’ dynamics and reason on
the thermodynamic modelling we propose.

###  3.1 GCN Architecture.

The architecture we use consists of four GCNConv layers followed by a
concatenation of a mean and a max pooling layers and at the end a dense layer
(Fig. 1). We use $\tanh$ as activation function.

Figure 1: Architecture of our GCN model in PyTorch framework. In the
parenthesis next to each layer, the first and second number indicate the
embedding dimension of the input and output respectively. The final linear
layer takes as input an embedding which is twice the size of the output from
the previous layer, due to concatenation of the two pooling operations.

We do not apply batch normalization ([17]) to the convolutional layers, since
normalizing the weights could bias our experiments (compare with [7]). We
optimize the network with SGD with a Cross Entropy loss and Adam optimizer,
without any form ofweight regularization.

We train this model on the MNIST Superpixels dataset obtained in [18], where
the $70.000$ images from the original MNIST dataset were transformed into
graphs with $75$ nodes, each node corresponding to a superpixel. We train the
model for 600 epochs, starting with a learning rate of $10^{-3}$ and decaying
it of a $1/10$ factor every 200 epochs. After training, the model reaches an
accuracy of $64\%$, which is worse than the performance obtained on the same
dataset in [18]. We think this is due to the fact that our architecture is
much simpler than MoNET ([19]) used in [18]. Once equilibrium of accuracy and
loss is reached, we further train the model for 100 epochs and we focus our
thermodynamic analysis on these last epochs at equilibrium. In particular, to
investigate the dependence of temperature from learning rate and batch size,
we further train the same equilibrium model by changing either the learning
rate or the batch size.

In Fig. 2 and 3, we show the behaviour of the temperature $T$, as defined in
our previous section, depending on the learning rate $\eta$ and the inverse of
the batch size $1/\beta$. We try values of learning rate in the range from
$7\cdot 10^{-4}$ to $3\cdot 10^{-3}$ (batch size fixed to 32) and values of
batch size in the range from 8 to 128 (learning rate fixed). We stress that,
for each layer of the architecture, the temperature was computed as the mean
kinetic energy of the weights averaged over the 100 equilibrium epochs.

Figure 2: Temperature dependence from the learning rate for selected layers of
the GCN architecture (the other behaving similarly). The equation resulting
from the fit is shown in the top left.

Figure 3: Temperature dependence from the inverse of the batch size for
selected layers of the GCN architecture.

Despite in the literature ([4] and refs therein) the temperature $\zeta$
(equation 2) is commonly believed to behave proportionally to such parameters,
we observe quite a different behaviour. As in [7], the dependence of
temperature from the learning rate is parabolic for the linear layer, whereas
it is almost parabolic for the GCNConv layers, where the exponent of $x$ in
the fit is greater than $2$ (see Fig. 2). As far as the dependence on the
batch size, we notice that all layers of the architecture exhibit a linear
dependence of temperature from $1/\beta$. This is in line with the results
obtained by [4], but differs from the ones in [7]. Indeed, in [7], the linear
dependence of the temperature from $1/\beta$ appears only for the output
linear layer, while the other layers exhibit an essential non linearity.
However, overall, as for the CNN architecture previously studied ([7], [11]),
we find that, given our thermodynamic definition of temperature, $T$ is not
proportional to $\eta/\beta$.

Furthermore, if we look at the mean squared velocities of the weights over the
epochs, without averaging on the number of weights, we discover quite an
interesting behaviour. Inside the same layer, the weights do not show all the
same mean squared velocity at equilibrium, but different rows of the weight
matrix show completely different thermal agitation (Fig. 4). This is similar
to what happens in [11], where we use the concept of temperature to
distinguish between “hot" and “cold" filters in a CNN layer and we discover
that high temperature filters can be removed from the model without affecting
the overall performance. We believe the same reasoning can be applied here for
GNN layers and it could imply that some rows of the weight matrix are
redundant to the learning. We expect to use this analysis to eliminate useless
features or to reduce the dimensions of the feature embedding and speed up the
optimization.

Figure 4: Mean squared velocity for the weights of the second GCNConv layer.
The weight matrix has dimensions $64\times 64$ and different rows of the
matrix show different temperature. The plot on the left is obtained by
flattening the matrix.

###  3.2 GAT Architecture.

The architecture we use is inspired by [20] and consists of three GATConv
layers followed by a final mean pooling layer and three dense layers (Fig. 5).
We take ReLU as activation function ([21]).

Figure 5: Architecture of our GAT model in PyTorch framework. In the
parenthesis next to each layer, the first number and second number indicate
the embedding dimension of the input and output respectively. The third
parameter indicates the number of heads. Since each GAT in the architecture
has $2$ heads, each layer following a GAT has input dimension twice the size
of the ouput from the previous GAT layer.

As for the previous GCN model, we do not apply either batch normalization
([17]) or dropout ([22]) or other forms of regularization to the weights. We
optimize the network as described for GCN and we obtain a test set accuracy of
$74\%$. To inspect the dependence of temperature on the two hyperparameters
$\eta$ and $\beta$, again we train the equilibrium model for other 100 epochs
and we restrict the analysis to these final epochs. In Fig. 6 and 7, we report
the behaviour of the temperature dependence on the learning rate $\eta$ and
the inverse of the batch size $1/\beta$ (range of values of the
hyperparameters as for the GCN model). Similarly to the model without
attention, the dependence of $T$ from $\eta$ is parabolic for the final linear
layer and almost parabolic for the other GATConv and linear layers, since for
these layers the exponent of $x$ in the fit is greater than $2$ (Fig. 6).
Furthermore, the dependence of $T$ from $1/\beta$ is again almost linear for
every layer (only the final linear layer shows a more parabolic behaviour).

Figure 6: Dependence of temperature from the learning rate for some layers of
the GAT architecture.

Figure 7: Dependence of temperature from the inverse of the batch size for
some layers of the GAT architecture.

##  4 Conclusions

We investigate the parallelism between SGD dynamics and thermodynamic systems
extending the study in [7] and [11] to Geometric Deep Learning algorithms.
Experiments show that similarly to the Deep Learning setting of CNN
architectures ([7], [11]), also for Geometric Deep Learning the temperatures
of each layer behave independently. The temperature of the linear layers in
the Geometric Deep Learning models considered behaves similarly to that of the
linear layers in the CNN models studied in [7] and does not exhibit any simple
dependence from $\eta$ and $\beta$ as originally assumed in [4]. On the
contrary, the temperature of GCN and GAT “convolutional" layers behaves
differently from the one of CNN layers considered in [7]: while the dependence
of temperature from $\eta$ is again almost parabolic, the one from $\beta$
becomes linear. Furthermore, we find that different areas of GCNConv and
GATConv layers have different temperature (see Fig. 4) as observed for the
filters of a CNN. This suggests a future technique of parameter pruning, based
on temperature, as in [11], that may help speed up the optimization and make
it more effective. More mathematical and physical modelling is needed to
further advance in this direction.

## References

  * [1] D. H Ackley, G. E Hinton, and T. J Sejnowski. A learning algorithm for Boltzmann machines. Cognitive science, 9(1):147-169, 1985.
  * [2] Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):251-276, 1998.
  * [3] Frédéric Barbaresco. Lie group statistics and Lie group machine learning based on Souriau Lie groups thermodynamics and Koszul-Souriau-Fisher metric: new entropy definition as generalized Casimir invariant function in coadjoint representation. Entropy, 22(6):642, 2020.
  * [4] Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks. 2018 Information Theory and Applications Workshop (ITA), pages 1-10.
  * [5] P. Chaudhari, A. Choromanska, S. Soatto, Y. LeCun et al. Entropy-sgd: Biasing gradient descent into wide valleys. International Conference on Learning Representations ICLR 2017, 1611.01838.
  * [6] R. Fioresi, P. Chaudhari and S. Soatto. A geometric interpretation of stochastic gradient descent using diffusion metrics. Entropy, 22(1):101, 2020.
  * [7] R. Fioresi, F. Faglioni, F. Morri and L. Squadrani. On the thermodynamic interpretation of deep learning systems. Geometric Science of Information: 5th International Conference, 2021.
  * [8] J. Hopfield J. Neurons with graded response have collective computational properties like those of two-state neurons. PNAS, 81(10):3088-3092.
  * [9] Edwin T Jaynes. Information theory and statistical mechanics. Physical review, 106(4):620, 1957.
  * [10] A. Krizhevsky, I. Sutskever and G. E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
  * [11] M. Lapenna, F. Faglioni and R. Fioresi Thermodynamics Modeling of Deep Learning Systems, preprint, Frontiers in Physics, 2023.
  * [12] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436-444, 2015.
  * [13] Charles-Michel Marle. From tools in symplectic and Poisson geometry to J. M. Souriau’s theories of statistical mechanics and thermodynamics. Entropy, 18(10):370, 2016.
  * [14] Ruslan Salakhutdinov and Geoffrey Hinton. Deep Boltzmann machines. In Artificial intelligence and statistics, pages 440-455. PMLR, 2009.
  * [15] A. Anahory Simoes, M. De Leon, M. Lainz Valcazar and D. M. De Diego. Contact geometry for simple thermodynamical systems with friction. Proceedings of the Royal Society A, 476(2241):20200244, 2020.
  * [16] Max Welling and Yee Whye Teh. Bayesian learning via stochastic gradient langevin dynamics. In International Conference on Machine Learning, 2011.
  * [17] Sergey Ioffe and Christian Szegedy. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:448-456, 2015.
  * [18] F. Monti, D. Boscaini, J. Masci, E. Rodolà et al. Geometric deep learning on graphs and manifolds using mixture model CNNs 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 10.1109/CVPR.2018.00335.
  * [19] M. Gou, F. Xiong, O. Camps and M. Sznaier. MoNet: Moments Embedding Network 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 1611.08402.
  * [20] P. H. C. Avelar, A. R. Tavares, T. L. T. da Silveira et al. Superpixel Image Classification with Graph Attention Networks. 33rd SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI), 2020, pp. 203-209, 10.1109/SIBGRAPI51738.2020.00035.
  * [21] Vinod Nair and Geoffrey E. Hinton. Rectified Linear Units Improve Restricted Boltzmann Machines. Proceedings of the 27th International Conference on Machine Learning (ICML-10), June 21-24, 2010.
  * [22] N. Srivastava, G. Hinton, A. Krizhevsky et al. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. The Journal of Machine Learning Research, Volume 15, Issue 1, pp 1929–1958.
  * [23] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks International Conference on Learning Representations ICLR 2017, url = https://openreview.net/forum?id=SJU4ayYgl.
  * [24] Hannas Risken.  The Fokker-Planck Equation, Methods of Solution and Applications, Springer, 1996.
  * [25] Veličković, Bengio, Yoshua et al. Graph Attention Networks International Conference on Learning Representations ICLR 2018, 10.40550/ARXIV.1710.10903.


#  The miracle of integer eigenvalues
Dedicated to Professor A.M.Vershik,
on the occasion of his 90-th birthday

Richard Kenyon1, Maxim Kontsevich2, Oleg Ogievetsky3,4,5 Cosmin Pohoata9, Will
Sawin6 and Senya Shlosman3,5,7,8

1 Yale University, USA, 2 IHES, France
3Aix Marseille Univ, Universite de Toulon,
CNRS, CPT, Marseille, France
4Lebedev Physical Institute, Moscow, Russia,
5Inst. of the Information Transmission Problems, Moscow, Russia,
6Princeton University, USA, 7BIMSA, Beijing, China,
8Skolkovo Institute of Science and Technology, Moscow, Russia
9Emory University, USA

###### Abstract

For partially ordered sets $X$ we consider the square matrices $M^{X}$ with
rows and columns indexed by linear extensions of the partial order on $X.$
Each entry $\left(M^{X}\right)_{PQ}$ is a formal variable defined by a
pedestal of the linear order $Q$ with respect to linear order $P.$ We show
that all the eigenvalues of any such matrix $M^{X}$ are $\mathbb{Z}$ -linear
combinations of those variables.

##  1 The statement of the main result

Let $X=\left\\{\alpha_{1},...,\alpha_{n}\right\\}$ be a partially ordered set
with the partial order $\preccurlyeq.$ A linear extension $P$ of
$\preccurlyeq$ is a bijection $P:X\rightarrow\left[1,...,n\right]$, such that
for any pair $\alpha_{i},\alpha_{j},$ satisfying
$\alpha_{i}\preccurlyeq\alpha_{j}$ we have $P\left(\alpha_{i}\right)\leq
P\left(\alpha_{j}\right).$ We denote by $\mathsf{{Tot}}_{X}$ the set of all
such linear extensions (i.e. total orders extending $\preccurlyeq$).

Let $P,Q$ be two linear extensions of $\preccurlyeq.$ We call the node
$Q^{-1}\left(k\right)\in X$ a $\left(P,Q\right)$-disagreement node iff
$P\left(Q^{-1}\left(k-1\right)\right)>P\left(Q^{-1}\left(k\right)\right).$ The
index $k$ is called the disagreement index. By definition, the node
$Q^{-1}\left(1\right)$ is a $\left(P,Q\right)$-agreement node. With every pair
$P,Q$ we associate the function
$\varepsilon_{PQ}:\left\\{1,...,n-1\right\\}\rightarrow\left\\{0,1\right\\},$
given by

$\varepsilon_{PQ}\left(k\right)=\left\\{\begin{tabular}[c]{ll}$1$&if
$Q^{-1}\left(k+1\right)$ is a $\left(P,Q\right)$-disagreement
node,\\\\[1.99997pt] $0$&otherwise.\end{tabular}\ \ \ \ \right.$ (1)

Note that for some pairs $\left(P,Q\right)\neq$
$\left(P^{\prime},Q^{\prime}\right)$ the functions $\varepsilon_{PQ},$
$\varepsilon_{P^{\prime}Q^{\prime}}$ can coincide (see the Examples section).

To formulate our main result we denote by
$\mathcal{E}=\left\\{\varepsilon:\left\\{1,...,n-1\right\\}\rightarrow\left\\{0,1\right\\}\right\\}$
the set of all $2^{n-1}$ different $\varepsilon$ functions, and we associate
with every $\varepsilon$ a corresponding formal variable $a_{\varepsilon}.$
For any poset $X$ consider the square matrix $M^{X},$ whose matrix elements
are indexed by the pairs $\left(P,Q\right),$ and are given by
$\left(M^{X}\right)_{PQ}=a_{\varepsilon_{PQ}}.$

For example, the poset $\left(X,\preccurlyeq\right)$ with three elements and
one relation: $X=\\{\\{u,v,w\\},u<v\\}$ has three linear extensions of
$\preccurlyeq$: $u<v<w,\ u<w<v,\ w<u<v.$ Let $P$ be the linear extension
$u<v<w$ and $Q$ – the linear extension $u<w<v$. We have
$\varepsilon_{PQ}=(0,1)$ since $2$ is an agreement index ($u<v$ in both $Q$
and $P$) and $3$ is a disagreement index ($w<v$ in $Q$ but not in $P$). The
matrix $M^{X}$ is

$\left(\begin{array}[c]{ccc}a_{00}&a_{01}&a_{10}\\\ a_{01}&a_{00}&a_{10}\\\
a_{01}&a_{10}&a_{00}\end{array}\right).$ (2)

The eigenvalues of this matrix are $a_{00}-a_{01}$, $a_{00}-a_{10}$ and
$a_{00}+a_{01}+a_{10}$, so they are $\mathbb{Z}$-linear combinations of the
letters entering the matrix. One of us (O.O.) conjectured that it holds (the
eigenvalues are $\mathbb{Z}$-linear combinations of the letters entering the
matrix $M^{X}$) for every poset $X$. Below we present the proof of this
conjecture:

###### Theorem 1

For every poset $X$ the eigenvalues of the matrix $M^{X}$ are linear
combinations of the variables $a_{\varepsilon}$ with integer coefficients.

The matrices $M^{X}$ were introduced in the paper [OS]. It is proven there
that the row sums $\sum_{Q}\left(M^{X}\right)_{PQ}$ do not depend on the row
$P,$ so the matrix $M^{X}$ is ‘stochastic’ (up to scale), and
$\Pi_{X}\left(\left\\{a_{\varepsilon}\right\\}\right)=\sum_{Q}\left(M^{X}\right)_{PQ}$
is its main eigenvalue. In [OS] the corresponding sums are called the
‘pedestal polynomials’. They enter into the expression for the generating
functions of the monotone functions $f:X\rightarrow\left\\{0,1,2,...\right\\}$
(e.g. the generating function of the number of plane partitions, spacial
partitions, etc.):

$\sum_{\text{monotone }f:X\rightarrow\left\\{0,1,2,...\right\\}}t^{\sum_{x\in
X}f\left(x\right)}=\Pi_{X}\left(t\right)\prod_{k=1}^{n}\frac{1}{1-t^{k}},$ (3)

where the polynomial $\Pi_{X}\left(t\right)$ is obtained from
$\Pi_{X}\left(\left\\{a_{\varepsilon}\right\\}\right)$ by the substitution

$a_{\varepsilon}\rightsquigarrow
t^{\sum_{k=1}^{n-1}k\varepsilon\left(k\right)}.$

We put into the Appendix the relevant combinatorial facts about the pedestals
and pedestal polynomials.

Our main tool is the filter semigroup of operators $M_{F}^{X},$ introduced in
the next section. They have appeared first in [BHR, BD], where their spectral
properties were studied. In fact, part of Theorem 1 can be obtained from Thm
1.2 in [BHR]. We give a shorter and more direct proof.

The next section contains some general facts about posets. It is followed by
the section containing proofs.

##  2 The filter semigroup

At the end of this section we will introduce the filter semigroup. But it is
easier to describe it geometrically, as the face semigroup of a hyperplane
arrangement, which we do first.

###  2.1 Faces

Consider the central real hyperplane arrangement $A_{n}$ consisting of
hyperplanes $\\{H_{ij}:1\leq i<j\leq n\\}$ in $\mathbb{R}^{n}$ defined by
$H_{ij}=\left\\{(x_{1},...,x_{n}):x_{i}=x_{j}\right\\}.$ Every open connected
component of the complement $\mathbb{R}^{n}\setminus\left\\{\cup
H_{ij}\right\\}$ is called a chamber. A cone is any union of closures of
chambers, which is convex. Let us introduce the (finite) set
$\mathfrak{O}\left(n\right)$ of all different cones thus obtained.

Let a poset $X$ of $n$ elements be given, with a binary relation
$\preccurlyeq$. To every pair $i,j\in X$ which is in the relation
$i\preccurlyeq j$ there corresponds a half-space $K_{ij}=\left\\{x_{i}\leq
x_{j}\right\\}\subset\mathbb{R}^{n}$ (here we assume that $X$ is identified
with $\\{1,2,\dots,n\\}$ as a plain set, ignoring the order). Consider the
cone

$A\left(X,\preccurlyeq\right)=\left\\{{\displaystyle\bigcap\limits_{i,j:i\preccurlyeq
j}}K_{ij}\right\\}\in\mathfrak{O}\left(n\right)$

where the intersection is taken over all pairs $i,j$ such that $i\preccurlyeq
j.$

The following statements are well-known (and easy to prove), see [B, D, Sa,
St].

###### Claim 2

The above defined correspondence $\left(X,\preccurlyeq\right)\rightarrow
A\left(X,\preccurlyeq\right)$ is a one-to-one correspondence between the set
of all partial orders on $\left\\{1,2,...,n\right\\}$ and the set of all cones
$\mathfrak{O}\left(n\right)$.

We present an illustration of this claim for $n=4$ on Fig.1:

Figure 1: The central real hyperplane arrangement $A_{4}$ in $\mathbb{R}^{4},$
projected to $\mathbb{R}^{3}$ along the line $x=y=z=t$ and intersected with
the sphere $\mathbb{S}^{2}\subset\mathbb{R}^{3}.$ It is a partition of
$\mathbb{S}^{2}$ into 24 equal triangles, each with the angles
$\left(\frac{\pi}{2},\frac{\pi}{3},\frac{\pi}{3}\right).$ The types of convex
unions of the triangles are: the sphere, the hemisphere, the region between
two great semicircles, an elementary triangle – or e-triangle, a pair of
e-riangles with a common side, a triangle made from three e-triangles, a
‘square’ formed by four e-triangles with a common $\frac{\pi}{2}$-vertex, a
triangle made from a ‘square’ and a fifth adjacent e-triange, a triangle
formed by six e-triangles with a common $\frac{\pi}{3}$-vertex. The number of
corresponding convex shapes are 1, 12, 60, 24, 36, 48, 6, 24, 8, with total
being 219. This is precisely the number of partial orders on the set of four
distinct elements, see the sequence A001035 in OEIS [Sl].

Let $f^{\prime},f^{\prime\prime}$ be two faces in
$A(X)=A\left(X,\preccurlyeq\right).$ (It is allowed that one or both of them
are in fact chambers, i.e. faces of highest dimension). Define the face
$f=f^{\prime\prime}\left(f^{\prime}\right)\in A\left(X\right)$ – or the face-
product $f^{\prime\prime}f^{\prime}$ – by the following procedure: choose
points $x^{\prime}\in f^{\prime},$ $x^{\prime\prime}\in f^{\prime\prime}$ in
general position and let
$s_{x^{\prime}x^{\prime\prime}}:\left[0,1\right]\rightarrow\mathbb{R}^{n}$ be
a linear segment, $s_{x^{\prime}x^{\prime\prime}}\left(0\right)=x^{\prime},$
$s_{x^{\prime}x^{\prime\prime}}\left(1\right)=x^{\prime\prime}.$ Consider the
face $f\in A\left(X\right)$ which contains all the points
$s_{x^{\prime}x^{\prime\prime}}\left(1-\varepsilon\right)$ of our segment for
$\varepsilon>0$ small enough. Such a face does exist due to the convexity of
$A(X).$ By definition, $f^{\prime\prime}\left(f^{\prime}\right)=f.$ Note that
if $f^{\prime\prime}$ is a chamber then
$f^{\prime\prime}f^{\prime}=f^{\prime\prime}.$

The face-product is associative. We mention for completeness that the
semigroups $A\left(X,\preccurlyeq\right)$ are what are called left-regular
bands, see [Sa]:

###### Claim 3

For every choice of faces $f,g,h\in A\left(X,\preccurlyeq\right)$ we have

$f\left(gh\right)=\left(fg\right)h,$ $ff=f,\ \ fgf=fg.$

We do not give here the proofs as we are not using these relations.

###  2.2 Filters

Let $F$ be a filter on $X$ of rank $k,$ i.e. a surjective map
$F:X\rightarrow\left\\{1,...,k\right\\},$ preserving the partial order, and
let

$\left\\{b_{1},...,b_{j_{1}}\right\\},\left\\{b_{j_{1}+1},...,b_{j_{2}}\right\\},...,\left\\{b_{j_{k-1}+1},...,b_{j_{k}}\right\\}\subset
X$

be its ‘floors’:

$\left\\{b_{j_{r-1}+1},...,b_{j_{r}}\right\\}=F^{-1}\left(r\right),\
r=1,...,k.$

Consider the face $f_{F}\in A\left(X,\preccurlyeq\right),$ defined by the
equations

$x_{b_{j_{r-1}+1}}=...=x_{b_{j_{r}}},\ r=1,...,k$

and inequalities

$x_{b_{j_{1}}}<x_{b_{j_{2}}}<...<x_{b_{j_{k}}}.$

(More precisely, we write an equation for every floor of $F$ which contains at
least two elements of $X.$) This is a one-to-one correspondence between faces
and filters. The filters of the highest rank $n,$ i.e. the linear extensions
of $\preccurlyeq,$ correspond to the chambers.

The corresponding filter-product looks as follows. For $F^{\prime},$
$F^{\prime\prime}$ being two filters of $X,$ the filter
$F=F^{\prime\prime}F^{\prime}$ on $X$ is uniquely defined by the following
properties:

  * •

For $u,v$ with $F^{\prime\prime}\left(u\right)<F^{\prime\prime}\left(v\right)\
$we have $F\left(u\right)<F\left(v\right).$

  * •

For $u,v$ with $F^{\prime\prime}\left(u\right)=F^{\prime\prime}\left(v\right)\
$we have $F\left(u\right)<F\left(v\right)$ iff
$F^{\prime}\left(u\right)<F^{\prime}\left(v\right).$

Indeed, let $f^{\prime},f^{\prime\prime}$ be the two faces, corresponding to
the filters $F^{\prime},F^{\prime\prime},$ and the general position points
$x^{\prime},x^{\prime\prime}$ belong to corresponding faces.

The fact that $F^{\prime\prime}\left(u\right)<F^{\prime\prime}\left(v\right)$
means that $x_{u}^{\prime\prime}<x_{v}^{\prime\prime}.$ But the point
$s_{x^{\prime}x^{\prime\prime}}\left(1-\varepsilon\right)$ is close to the
point $x^{\prime\prime},$ therefore
$\left[s_{x^{\prime}x^{\prime\prime}}\left(1-\varepsilon\right)\right]_{u}<\left[s_{x^{\prime}x^{\prime\prime}}\left(1-\varepsilon\right)\right]_{v}$
for all $\varepsilon$ small enough.

The fact that $F^{\prime\prime}\left(u\right)=F^{\prime\prime}\left(v\right)\
$while $F^{\prime}\left(u\right)<F^{\prime}\left(v\right)$ means that
$x_{u}^{\prime\prime}=x_{v}^{\prime\prime}$ while
$x_{u}^{\prime}<x_{v}^{\prime}.$ Since the map
$s_{x^{\prime}x^{\prime\prime}}:\left[0,1\right]\rightarrow\mathbb{R}^{n}$ is
linear, for any $t<1$ we have
$\left[s_{x^{\prime}x^{\prime\prime}}\left(t\right)\right]_{u}<\left[s_{x^{\prime}x^{\prime\prime}}\left(t\right)\right]_{v}.$

Let $F$ be a filter on $X$, and $P$ is some filter of rank $n$, i.e. a linear
order on $X.$ Then the filter $FP$ is again a filter of rank $n.$ Consider the
square matrix $M_{F}^{X}=\left\|\left(M_{F}^{X}\right)_{P,Q}\right\|$ where
$P,Q$ are linear orders on $X:$

$\left(M_{F}^{X}\right)_{P,Q}=\left\\{\begin{tabular}[c]{ll}$1$&if $Q=FP$\\\
$0$&if $Q\neq FP$\end{tabular}\ \ \right..$

The operators $M_{F}^{X}$ play a central role in our proof.

Examples of the operators $M_{F}^{X}$ are given in the Example section below.

##  3 Proof of the main result

The plan of the proof is the following:

  1. 1.

We will show that the matrix $M^{X}$ can be written as a linear combination of
$M_{F}^{X}$-s with integer coefficients.

  2. 2.

We will show that all $M_{F}^{X}$-s can be made upper-triangular via
conjugation with the same matrix, and the resulting upper-triangular matrices
have integer entries on the diagonal.

###  3.1 The filter decomposition

Let us rewrite $M^{X}$ as the sum over all $2^{n-1}$ functions
$\varepsilon:\left\\{1,...,n-1\right\\}\rightarrow\left\\{0,1\right\\}$:

$M^{X}=\sum_{\varepsilon}a_{\varepsilon}B_{X,\varepsilon},$ (4)

where the entries of each matrix $B_{X,\varepsilon}$ are $0$ or $1.$

For every function $\varepsilon$ we define the number
$r\left(\varepsilon\right)=1+\sum_{j=1}^{n-1}\varepsilon\left(j\right),$ and
we partition the segment $\left\\{1,...,n\right\\}$ into
$r\left(\varepsilon\right)$ consecutive segments

$\displaystyle\left\\{1,...,n\right\\}$
$\displaystyle=\left\\{1,...,c_{1}\right\\}$
$\displaystyle\cup\left\\{c_{1}+1,...,c_{1}+c_{2}\right\\}$
$\displaystyle\cup\left\\{c_{1}+c_{2}+1,...,c_{1}+c_{2}+c_{3}\right\\}\cup...$
$\displaystyle\cup\left\\{c_{1}+...+c_{r\left(\varepsilon\right)}+1,...,n\right\\},$

where the values
$c_{1}+1,c_{1}+c_{2}+1,...,c_{1}+...+c_{r\left(\varepsilon\right)}+1$ are all
the points where the function $\varepsilon$ takes value $1.$

For $c_{1},...,c_{r}$ being integers summing up to $n$ we denote by
$\mathcal{F}_{c_{1},...,c_{r}}$ the set of all filters
$F:X\rightarrow\left[1,2,...,r\right]$ such that
$\left|F^{-1}\left(i\right)\right|=c_{i}$ for all $i=1,...,r.$

###### Lemma 4

Suppose that the matrix $B_{X,\varepsilon}\neq 0,$ and the function
$\varepsilon$ has the parameters $r$ and $c_{1},...,c_{r}$. Then the following
inclusion-exclusion identity holds:

$\displaystyle B_{X,\varepsilon}$
$\displaystyle=\sum_{F\in\mathcal{F}_{c_{1},...,c_{r}}}M_{F}^{X}-\left[\sum_{\begin{subarray}{c}F\in\mathcal{F}_{c_{1}+c_{2},c_{3},...,c_{r}}\cup\\\
\cup\mathcal{F}_{c_{1},c_{2}+c_{3},...,c_{r}}\cup...\end{subarray}}M_{F}^{X}\right]$
(5)
$\displaystyle+\left[\sum_{\begin{subarray}{c}F\in\mathcal{F}_{c_{1}+c_{2}+c_{3},c_{4},...,c_{r}}\cup\\\
\cup\mathcal{F}_{c_{1}+c_{2},c_{3}+c_{4},...,c_{r}}\cup...\end{subarray}}M_{F}^{X}\right]-...$

where the sums are taken over all possible mergers of neighboring indices
$c_{i},$ and the signs are $\left(-1\right)^{\\#mergers}.$

Proof. Indeed, if we take an order $Q$ from the row $P$ which appears in the
lhs, then it agrees with $P$ over the first $c_{1}-1$ locations, then it
disagrees once, then it agrees again over next $c_{2}-1$ locations, then
disagrees once again, etc. But an order $Q$ from the row $P$ which appears in
the rhs and corresponds to the first sum in $\left(\ref{15}\right),$ agrees
with $P$ over the first $c_{1}-1$ locations, then it agrees or disagrees once,
then it agrees again over next $c_{2}-1$ locations, then agrees or disagrees
once again, etc. Therefore we have to remove all these $Q$-s which agrees with
$P$ over the first $c_{1}-1$ locations, then agrees once again, then agrees
also over next $c_{2}-1$ locations, etc.

See the Examples section for some $M_{F}^{X}$ operators.

###  3.2 Conjugation of $M_{F}^{X}$-s to upper-triangular

Our matrices $M_{F}^{X}$ are of the size
$\left|\mathsf{{Tot}}_{X}\right|\times\left|\mathsf{{Tot}}_{X}\right|$. Let us
now abolish all order relations on $X,$ getting the poset $\bar{X}$ with
$\left|\mathsf{{Tot}}_{\bar{X}}\right|=n!\ .$ Of course, $M_{F}^{X}$ is a
submatrix of $M_{F}^{\bar{X}}.$ Imagine (after reindexing) that it is an
upper-left submatrix. We claim that to the right of this submatrix all matrix
elements of $M_{F}^{\bar{X}}$ are zero, and so $M_{F}^{X}$ is a block of
$M_{F}^{\bar{X}}$. Indeed, each row of $M_{F}^{\bar{X}}$ has exactly one $1,$
and the rest are $0$-s. But each row of $M_{F}^{X}$ already has one $1.$ So it
is sufficient to know that the spectrum of $M_{F}^{\bar{X}}$ consists of
integers.

In what follows, the initial poset $X$ will not appear any more, and we will
deal only with ‘totally unordered’ poset $\bar{X}.$ The fact that the matrices
$M_{F}^{\bar{X}}$ can be conjugated simultaneously to upper-triangular ones
can be deduced from the results of the papers [BHR, BD]. We give a shorter and
more direct proof.

Let us consider an even bigger matrix, $N_{F}^{\bar{X}}$, of size
$2^{n\left(n-1\right)/2}.$ Here $F$ is a filter on $X,$ while the rows and
columns of $N_{F}^{\bar{X}}$ are indexed by tournaments between the $n$
entries of $\bar{X}$. A tournament is an assignment of an order $\preccurlyeq$
to each pair $i\neq j$ of the elements of the set $\bar{X},$ independently for
each pair. If we have a tournament $\preccurlyeq$ and a filter $F$ on
$\bar{X},$ then we define a new tournament $\preccurlyeq_{F}$ by the rule:

  1. 1.

If $F\left(i\right)=F\left(j\right)$ then $i\preccurlyeq_{F}j$ iff
$i\preccurlyeq j,$

  2. 2.

If $F\left(i\right)<F\left(j\right)$ then $i\preccurlyeq_{F}j$.

We define $N_{F}^{\bar{X}}$ by

$\left(N_{F}^{\bar{X}}\right)_{\preccurlyeq\preccurlyeq^{\prime}}=\left\\{\begin{tabular}[c]{ll}$1$&if
$\preccurlyeq^{\prime}=\ \preccurlyeq_{F}$\\\ $0$&if
$\preccurlyeq^{\prime}\not=\ \preccurlyeq_{F}$\end{tabular}\ \ \ \right.$

Any linear order defines a tournament in an obvious way, so our matrices
$M_{F}^{\bar{X}}$ are blocks of $N_{F}^{\bar{X}}$-s, and it is sufficient to
study $N_{F}^{\bar{X}}$-s.

The key observation now is the fact that $N_{F}^{\bar{X}}$ is a tensor product
of $n\left(n-1\right)/2$ two-by-two matrices, corresponding to all pairs
$\left(i,j\right),$ since the tournament orders $\preccurlyeq$ can be assigned
to the pairs independently. And since the tensor product of upper triangular
matrices is upper triangular, it is sufficient to check our claim just for the
filters and tournaments in the case $n=\left|\bar{X}\right|=2.$

The two-element no-order set $\bar{X}=\left\\{1,2\right\\}$ carries three
different filters and has two possible tournaments. The three two-by-two
matrices $N_{F}^{\bar{X}}$-s are $N_{1}:=\left(\begin{array}[c]{cc}1&0\\\
1&0\end{array}\right),N_{2}:=\left(\begin{array}[c]{cc}1&0\\\
0&1\end{array}\right),$ and $N_{3}:=\left(\begin{array}[c]{cc}0&1\\\
0&1\end{array}\right).$ Conjugating them by the discrete Fourier transform
matrix $U=\frac{1}{\sqrt{2}}\left(\begin{array}[c]{cc}1&1\\\
1&-1\end{array}\right)$ brings them to the triple of upper triangular
matrices: $UN_{1}U^{-1}=\left(\begin{array}[c]{cc}1&1\\\
0&0\end{array}\right),UN_{2}U^{-1}=\left(\begin{array}[c]{cc}1&0\\\
0&1\end{array}\right),$ and $UN_{3}U^{-1}=\left(\begin{array}[c]{cc}1&-1\\\
0&0\end{array}\right).$ Extending the conjugation through the tensor product
finishes the proof. $\blacksquare$

###### Remark 5

Recall the definition (4) of the matrices $B_{\mu}$: for a poset $X$, the set
of (0,1)-valued matrices
$\\{B_{X,\varepsilon}\\}_{\varepsilon\in\\{0,1\\}^{\\{1,\dots,n-1\\}}}$ is
defined by $M^{X}=\sum_{\varepsilon}a_{\varepsilon}B_{X,\varepsilon}$. Let
$\mathcal{L}(X)$ be the Lie algebra generated by the matrices
$\\{B_{X,\varepsilon}\\}$. The proof shows that the Lie algebra
$\mathcal{L}(X)$ is solvable.

Let us denote by $\Phi_{T}$ the algebra of functions on the set
$\mathsf{Tour}_{\bar{X}}$ of tournaments considered as the set
$\\{-1,+1\\}^{n(n-1)/2}\subset\mathbb{R}^{n(n-1)/2}$ of vertices of the cube.
This algebra carries an increasing filtration by subspaces

$0\subset\Phi_{T}^{\leq 0}\subset\Phi_{T}^{\leq
1}\subset\dots\subset\Phi_{T}^{\leq{\frac{n(n-1)}{2}}}=\Phi_{T}$

consisting of restrictions of polynomials of degree $\leq 0,\leq 1,\dots$ to
the vertices of the cube. This filtration is strictly multiplicative in the
sense that

$\Phi_{T}^{\leq k}=\underbrace{\Phi_{T}^{\leq 1}\cdot\dots\cdot\Phi_{T}^{\leq
1}}_{k\text{ times}}\,.$

Our considerations imply that all operators $N_{F}^{\bar{X}}$ preserve this
filtration, and commute with each other on the associated graded space
$\oplus_{k}\Phi_{T}^{\leq k}/\Phi_{T}^{\leq k-1}$. Indeed, $\Phi_{T}$ has
basis $\prod_{i\in S}x_{i}$ where $S$ runs through all subsets of
$\\{1,\dots,{n(n-1)\over 2}\\}$. For each coordinate $x_{i}$ we have two
commuting operators $N_{2}=\left(\begin{array}[c]{cc}1&0\\\
0&1\end{array}\right)$ and $(x_{i}\to-
x_{i})^{*}=N_{1}+N_{3}-N_{2}=\left(\begin{array}[c]{cc}0&1\\\
1&0\end{array}\right)$ acting on the $i$-th tensor factor
$\mathbb{R}^{\\{-1,+1\\}}=\mathbb{R}[x_{i}]/(x_{i}^{2}-1)$) preserving the
filtration by degree, as well as one extra operator
$(N_{3}-N_{1})=\left(\begin{array}[c]{cc}-1&1\\\ -1&1\end{array}\right)$ which
strictly decreases the filtration (it acts as $2\partial_{x_{i}}$ in the basis
$(\prod_{i\in S}x_{i})_{S\subseteq\\{1,\dots,n(n-1)/2\\}}$). We see that on
the associated graded space $\oplus_{k}\Phi_{T}^{\leq k}/\Phi_{T}^{\leq k-1}$
our operators give the ones coming from the commutative group algebra of the
abelian group $(\mathbb{Z}/2\mathbb{Z})^{n(n-1)/2}$ acting by involutions of
coordinates.

Restricting functions from $\Phi_{T}$ to the subset
$\mathsf{Tot}_{X}\subset\mathsf{Tour}_{\bar{X}}$ we obtain again a strictly
multiplicative filtration on the algebra
$\Phi_{X}:=\mathbb{R}^{\mathsf{Tot}_{X}}$ of functions on $\mathsf{Tot}_{X}$,
preserved by all operators $M_{F}^{X}$ where $F$ runs through filters on the
poset $X$.

##  4 Appendices

###  4.1 Pedestals

Let again $X$ be a finite poset with the partial order $\preccurlyeq,$ and
$P,Q$ be a pair of linear orders on $X,$ consistent with $\preccurlyeq.$ We
define the function $q_{PQ}$ on $X$ by

$q_{PQ}\left(Q^{-1}\left(k\right)\right)=\\#\left\\{l:l\leq
k,Q^{-1}\left(l\right)\text{ is a }\left(P,Q\right)\text{-disagreement
node}\right\\}.$ (6)

Clearly, the function $q_{PQ}$ is non-decreasing on $X,$ and
$q_{PQ}\left(Q^{-1}\left(1\right)\right)=0.$ It is called the pedestal of $Q$
with respect to $P.$

For example, let $X$ be a $3\times 2$ Young diagram, and

$P=\left[\begin{tabular}[c]{lll}1&2&3\\\ 4&5&6\end{tabular}\ \right],\
Q=\left[\begin{tabular}[c]{lll}1&2&5\\\ 3&4&6\end{tabular}\ \right]$

be the two standard tableaux. Then

$q_{PQ}=\left[\begin{tabular}[c]{lll}0&0&1\\\ 0&0&1\end{tabular}\ \right].$

Let $\mathcal{E}_{P}$ denotes the set of all pedestals $q_{PQ}.$ Clearly,
there is a map $\mathcal{E}_{P}\rightarrow\mathcal{E},$ which to every
pedestal $q_{PQ}$ corresponds its ‘discrete derivative’ $\varepsilon_{PQ}$.

The pedestals were introduced in [S] in the following context. Consider the
set $\mathcal{P}=\mathcal{P}_{X}$ of all non-negative integer-valued non-
decreasing functions $p$ on $X.$ Denote by $v\left(p\right)$ the ‘volume’ of
$p:$

$v\left(p\right)=\sum_{\alpha\in X}p\left(\alpha\right),$

and let $G$ be the following generating function:

$G_{X}\left(t\right)=\sum_{k\geq
0}g_{k}t^{k}=\sum_{p\in\mathcal{P}_{X}}t^{v\left(p\right)},$

i.e. $g_{k}$ is the number of non-decreasing $p$-s with $v\left(p\right)=k.$
For example, if the poset $X$ is in fact the set
$X_{n}=\left[1,2,...,n\right],$ ordered linearly, then

$G_{X_{n}}\left(t\right)=\prod_{l=1}^{n}\frac{1}{1-t^{l}}$

is the generating function of the sequence $g_{k}$ of the number of partitions
$\pi$ of the integer $k$ into at most $n$ parts:
$k=\pi\left(1\right)+\pi\left(2\right)+...+\pi\left(n\right),$ with
$\pi\left(i\right)\geq 0,$ $\pi\left(i\right)\leq\pi\left(i+1\right).$ Let
$\mathcal{Y}_{n}$ denote the set of all such partitions $\pi$ (i.e. Young
diagrams).

In order to write a formula for $G_{X}$ for an arbitrary poset $X$ one needs
pedestals. Namely, let us fix some ordering $P$ of $X,$ consider all pedestals
$q_{PQ},$ and let

$\Pi_{P}\left(t\right)=\sum_{Q}t^{v\left(q_{PQ}\right)}$ (7)

be the generating function (in fact, generating polynomial) of the sequence of
the number of pedestals with a given volume. Then we have the identity:

$G_{X}\left(t\right)=\Pi_{P}\left(t\right)G_{X_{n}}\left(t\right)\equiv\Pi_{P}\left(t\right)\prod_{l=1}^{n}\frac{1}{1-t^{l}},$
(8)

(compare with $\left(\ref{23}\right)$). In particular, it follows from
$\left(\ref{11}\right)$ that the polynomial $\Pi_{P}\left(t\right)$ does not
depend on $P,$ and thus can be denoted by $\Pi_{X}\left(t\right).$ The reason
for $\left(\ref{11}\right)$ to hold is the existence of the bijection between
the set $\mathcal{P}_{X}$ of nondecreasing functions and the direct product
$\mathcal{E}_{P}\times\mathcal{Y}_{n},$ respecting the volumes. Namely, to
each pedestal $q_{PQ}$ and each partition $\pi$ it associates the following
function $p$ on $X:$

$p\left(Q^{-1}\left(k\right)\right)=q_{PQ}\left(Q^{-1}\left(k\right)\right)+\pi\left(k\right),\
k=1,...,n.$

Clearly, the function thus defined is non-decreasing on $X.$ For the check
that this is a one-to-one correspondence, see [S].

In the case when $X$ is a (2D) Young diagram, the functions
$p\in\mathcal{P}_{X}$ are called ‘reverse plane partitions’. The generating
function $G_{X}$ for these is also given by the famous MacMahon formula,

$G_{X}\left(t\right)=\prod_{\alpha\in X}\frac{1}{1-t^{h\left(\alpha\right)}},$

where $h\left(\alpha\right)$ is the hook length of the cell $\alpha\in X.$
That means that for the case of $X$ being a Young diagram nice cancellations
happen in the rhs of $\left(\ref{11}\right).$ One can check that for some $X$
being a 3D Young diagram no cancellations happen in $\left(\ref{11}\right),$
and this is the reason why the analog of the MacMahon formula in the 3D case
does not exist.

###  4.2 Pedestal polynomials

The fact that the function $\Pi_{P}\left(t\right)$ (see
$\left(\ref{12}\right)$) does not depend on the order $P$ on $X,$ but only on
$X,$ has the following generalization. Instead of characterizing the pedestal
$q_{PQ}$ just by its volume let us associate with it the monomial
$m_{PQ}\left(x_{1},x_{2},x_{3},...\right)=x_{1}^{l_{1}-1}x_{2}^{l_{2}-l_{1}}...x_{r}^{l_{r}-l_{r-1}}x_{r+1}^{n-l_{r}+1},$
where $r$ is the number of $\left(P,Q\right)$-disagreement nodes, and
$l_{1},...,l_{r}$ are their locations, see $\left(\ref{13}\right).$ Note that
$m_{PQ}\left(1,t,t^{2},...\right)=t^{v\left(q_{PQ}\right)}.$

It was shown in [OS] that the polynomial

$\mathfrak{h}_{P}\left(x_{1},x_{2},x_{3},...\right)=\sum_{Q\in\mathsf{{Tot}}_{X}}m_{PQ}\left(x_{1},x_{2},x_{3},...\right)$

is also independent of $P,$ so it can be denoted as
$\mathfrak{h}_{X}\left(x_{1},x_{2},x_{3},...\right).$ Another way of
expressing this is to say that the matrix $\tilde{M}^{X}$ of size
$\left|\mathsf{{Tot}}_{X}\right|\times\left|\mathsf{{Tot}}_{X}\right|,$ with
entries
$\left(\tilde{M}^{X}\right)_{PQ}=m_{PQ}\left(x_{1},x_{2},x_{3},...\right)$ is
stochastic, i.e. the vector $\left(1,1,...,1\right)$ is the right eigenvector,
with the eigenvalue $\mathfrak{h}_{X}\left(x_{1},x_{2},x_{3},...\right).$

By replacing the monomials $m_{PQ}\left(x_{1},x_{2},x_{3},...\right)$ with
variables $a_{\varepsilon_{PQ}}$ one obtains from $\tilde{M}^{X}$ our matrix
$M^{X}.$

###### Remark 6

As we just said, we know from [OS] that the rows of the matrix $M^{X}$ consist
of the same matrix elements, permuted. So it is tempting to consider the set
of permutations $\pi_{PP^{\prime}}\in S_{\left|\mathsf{{Tot}}_{X}\right|},$
which permute the elements of the row $P$ to these of row $P^{\prime}.$
Unfortunately, rows of the matrix $M^{X}$ can contain repeated elements, so
the permutations $\pi_{PP^{\prime}}$ are not uniquely defined.

###  4.3 Examples

Here we present several examples in which our posets $X$ correspond to
partitions; standard Young tableaux are read row by row.

0. In all examples we considered the pedestal matrix is diagonalisable in the generic point. However for special values of variables the pedestal matrix might have non-trivial Jordan blocks. We give a minimal example - partition (3,1). It is essentially the same example as the one before the main theorem, with the pedestal matrix (2), because the box (1,1) comes first in any linear order and can be omitted.

Here it is enough to take a partial evaluation $a_{10}\mapsto-2a_{01}$. Then
the Jordan form is

$\left(\begin{array}[]{ccc}a_{00}-a_{01}&1&0\\\ 0&a_{00}-a_{01}&0\\\
0&0&a_{00}+2a_{01}\end{array}\right)\ .$

It would be interesting to understand the regimes in which the pedestal matrix
is not diagonalisible.

1. Partition (3,2). The standard tableaux are

$\\{1,3,5,2,4\\}\ ,\ \\{1,2,5,3,4\\}\ ,\ \\{1,3,4,2,5\\}\ ,\ \\{1,2,4,3,5\\}\
,\ \\{1,2,3,4,5\\}.$

The pedestal matrix $\tilde{M}^{X}$ is $x_{1}^{2}A_{(3,2)},$ where

$A_{(3,2)}=\left(\begin{array}[c]{ccccc}x_{1}^{3}&x_{2}^{3}&x_{1}^{2}x_{2}&x_{2}^{2}x_{3}&x_{1}x_{2}^{2}\\\
x_{2}^{3}&x_{1}^{3}&x_{2}^{2}x_{3}&x_{1}^{2}x_{2}&x_{1}x_{2}^{2}\\\
x_{1}^{2}x_{2}&x_{2}^{2}x_{3}&x_{1}^{3}&x_{2}^{3}&x_{1}x_{2}^{2}\\\
x_{2}^{2}x_{3}&x_{1}^{2}x_{2}&x_{2}^{3}&x_{1}^{3}&x_{1}x_{2}^{2}\\\
x_{2}^{2}x_{3}&x_{1}^{2}x_{2}&x_{2}^{3}&x_{1}x_{2}^{2}&x_{1}^{3}\end{array}\right)\
.$

After a replacement

$\phi:(x_{1}^{3},x_{1}^{2}x_{2},x_{1}x_{2}^{2},x_{2}^{3},x_{2}^{2}x_{3})\rightarrow(a_{1},a_{2},a_{3},a_{4},a_{5})\
,$ (9)

we have

$A_{(3,2)}^{\phi}=\left(\begin{array}[c]{ccccc}a_{1}&a_{4}&a_{2}&a_{5}&a_{3}\\\
a_{4}&a_{1}&a_{5}&a_{2}&a_{3}\\\ a_{2}&a_{5}&a_{1}&a_{4}&a_{3}\\\
a_{5}&a_{2}&a_{4}&a_{1}&a_{3}\\\
a_{5}&a_{2}&a_{4}&a_{3}&a_{1}\end{array}\right)\ .$

The eigenvalues of $A_{(3,2)}^{\phi}$ are

$a_{1}-a_{3}\ ,\ a_{1}+a_{2}-a_{4}-a_{5}\ ,\ a_{1}-a_{2}+a_{4}-a_{5}\ ,\
a_{1}-a_{2}-a_{4}+a_{5}\ ,\ a_{1}+a_{2}+a_{3}+a_{4}+a_{5}\ .$

2. Partition (3,1,1). The standard tableaux are

$\\{1,4,5,2,3\\}\ ,\ \\{1,3,5,2,4\\}\ ,\ \\{1,2,5,3,4\\}\ ,\ \\{1,3,4,2,5\\}\
,\ \\{1,2,4,3,5\\},\\{1,2,3,4,5\\}\ .$

The pedestal matrix is $x_{1}^{2}A_{(3,1,1)}$ where

$A_{(3,1,1)}=\left(\begin{array}[c]{cccccc}x_{1}^{3}&x_{1}x_{2}^{2}&x_{2}^{3}&x_{1}^{2}x_{2}&x_{2}^{2}x_{3}&x_{1}x_{2}^{2}\\\
x_{1}x_{2}^{2}&x_{1}^{3}&x_{2}^{3}&x_{1}^{2}x_{2}&x_{2}^{2}x_{3}&x_{1}x_{2}^{2}\\\
x_{1}x_{2}^{2}&x_{2}^{3}&x_{1}^{3}&x_{2}^{2}x_{3}&x_{1}^{2}x_{2}^{2}&x_{1}x_{2}^{2}\\\
x_{1}x_{2}^{2}&x_{1}^{2}x_{2}&x_{2}^{2}x_{3}&x_{1}^{3}&x_{2}^{3}&x_{1}x_{2}^{2}\\\
x_{1}x_{2}^{2}&x_{2}^{2}x_{3}&x_{1}^{2}x_{2}&x_{2}^{3}&x_{1}^{3}&x_{1}x_{2}^{2}\\\
x_{1}x_{2}^{2}&x_{2}^{2}x_{3}&x_{1}^{2}x_{2}&x_{2}^{3}&x_{1}x_{2}^{2}&x_{1}^{3}\end{array}\right)\
.$

After the same replacement (9) (the matrix $A_{(3,1,1)}$ contains the same
monomials as the matrix $A_{(3,2)}$) we have

$A_{(3,1,1)}^{\phi}=\left(\begin{array}[c]{cccccc}a_{1}&a_{3}&a_{4}&a_{2}&a_{5}&a_{3}\\\
a_{3}&a_{1}&a_{4}&a_{2}&a_{5}&a_{3}\\\ a_{3}&a_{4}&a_{1}&a_{5}&a_{2}&a_{3}\\\
a_{3}&a_{2}&a_{5}&a_{1}&a_{4}&a_{3}\\\ a_{3}&a_{5}&a_{2}&a_{4}&a_{1}&a_{3}\\\
a_{3}&a_{5}&a_{2}&a_{4}&a_{3}&a_{1}\end{array}\right)\ .$

The eigenvalues of $A_{(3,1,1)}^{\phi}$ are (the notation $(y)_{k}$ means that
the multiplicity of the eigenvalue $y$ is $k$)

$(a_{1}-a_{3})_{2}\ ,\ a_{1}+a_{2}-a_{4}-a_{5}\ ,\ a_{1}-a_{2}+a_{4}-a_{5}\ ,\
a_{1}-a_{2}-a_{4}+a_{5}\ ,\ a_{1}+a_{2}+2a_{3}+a_{4}+a_{5}\ .$

The example $(3,1,1)$ shows degeneration: the letter $a_{3}$ appears twice in
every row of $A_{(3,1,1)}^{\phi}$. The corresponding monomial is
$x_{1}^{3}x_{2}^{2}$ so for writing down the decomposition of the matrix
$B_{a_{3}}$ we need filters from $\mathcal{F}_{3,2}$. There are three of them
in $\mathcal{F}_{3,2}$ (the notation is like for a matrix; element $(i,j)$ is
in the intersection of row $i$ and column $j$):

  * $\bullet$

$F_{1}$: Floor 1 contains cells (1,1), (1,2) and (2,1);

  * $\bullet$

$F_{2}$: Floor 1 contains cells (1,1), (1,2) and (1,3);

  * $\bullet$

$F_{3}$: Floor 1 contains cells (1,1), (2,1) and (3,1).

The matrices of action of these filters on the linear orders are

$M_{F_{1}}=\left(\begin{array}[c]{cccccc}0&1&0&0&0&0\\\ 0&1&0&0&0&0\\\
0&0&1&0&0&0\\\ 0&0&0&1&0&0\\\ 0&0&0&0&1&0\\\
0&0&0&0&1&0\end{array}\right),M_{F_{2}}=\left(\begin{array}[c]{cccccc}0&0&0&0&0&1\\\
0&0&0&0&0&1\\\ 0&0&0&0&0&1\\\ 0&0&0&0&0&1\\\ 0&0&0&0&0&1\\\
0&0&0&0&0&1\end{array}\right),$
$M_{F_{3}}=\left(\begin{array}[c]{cccccc}1&0&0&0&0&0\\\ 1&0&0&0&0&0\\\
1&0&0&0&0&0\\\ 1&0&0&0&0&0\\\ 1&0&0&0&0&0\\\ 1&0&0&0&0&0\end{array}\right).$

The family $\mathcal{F}_{5}$ contains one filter, which acts as the identity
$I$. The matrix $B_{a_{3}}$ is thus

$B_{a_{3}}=\left(\begin{array}[c]{cccccc}0&1&0&0&0&1\\\ 1&0&0&0&0&1\\\
1&0&0&0&0&1\\\ 1&0&0&0&0&1\\\ 1&0&0&0&0&1\\\
1&0&0&0&1&0\end{array}\right)=M_{F_{1}}+M_{F_{2}}+M_{F_{3}}-I\ ,$

as dictated by the inclusion-exclusion formula.

3. Partition (3,2,1). The standard tableaux are

$\begin{array}[c]{l}\\{1,4,6,2,5,3\\}\ ,\ \\{1,3,6,2,5,4\\}\ ,\
\\{1,2,6,3,5,4\\}\ ,\ \\{1,3,6,2,4,5\\}\ ,\\\ \\{1,2,6,3,4,5\\}\ ,\
\\{1,4,5,2,6,3\\}\ ,\ \\{1,3,5,2,6,4\\}\ ,\ \\{1,2,5,3,6,4\\}\ ,\\\
\\{1,3,4,2,6,5\\}\ ,\ \\{1,2,4,3,6,5\\}\ ,\ \\{1,2,3,4,6,5\\}\ ,\
\\{1,3,5,2,4,6\\}\ ,\\\ \\{1,2,5,3,4,6\\}\ ,\ \\{1,3,4,2,5,6\\}\ ,\
\\{1,2,4,3,5,6\\}\ ,\ \\{1,2,3,4,5,6\\}\ .\end{array}$

To save the space we write down the pedestal matrix in which the replacement

$(x_{1}^{6},x_{1}^{5}x_{2},x_{1}^{4}x_{2}^{2},x_{1}^{4}x_{2}x_{3},x_{1}^{3}x_{2}^{3},x_{1}^{3}x_{2}^{2}x_{3},x_{1}^{2}x_{2}^{4},x_{1}^{2}x_{2}^{3}x_{3},x_{1}^{2}x_{2}^{2}x_{3}^{2},x_{1}^{2}x_{2}^{2}x_{3}x_{4})\rightarrow$
$(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7},a_{8},a_{9},a_{10})$

is made. This matrix $A_{(3,2,1)}^{\phi}$ is

$A_{(3,2,1)}^{\phi}=\left(\begin{array}[c]{cccccccccccccccc}\\!a_{1}\\!&\\!a_{5}\\!&\\!a_{7}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{2}\\!&\\!a_{6}\\!&\\!a_{8}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{5}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{4}\\!&\\!a_{10}\\!&\\!a_{6}\\!\\\
\\!a_{5}\\!&\\!a_{1}\\!&\\!a_{7}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{6}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{5}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{4}\\!&\\!a_{10}\\!&\\!a_{6}\\!\\\
\\!a_{5}\\!&\\!a_{7}\\!&\\!a_{1}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{6}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{5}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{10}\\!&\\!a_{4}\\!&\\!a_{6}\\!\\\
\\!a_{5}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{1}\\!&\\!a_{7}\\!&\\!a_{6}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{4}\\!&\\!a_{10}\\!&\\!a_{6}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{5}\\!\\\
\\!a_{5}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{7}\\!&\\!a_{1}\\!&\\!a_{6}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{10}\\!&\\!a_{4}\\!&\\!a_{6}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{5}\\!\\\
\\!a_{2}\\!&\\!a_{6}\\!&\\!a_{8}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{1}\\!&\\!a_{5}\\!&\\!a_{7}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{5}\\!&\\!a_{4}\\!&\\!a_{10}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{6}\\!\\\
\\!a_{6}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{5}\\!&\\!a_{1}\\!&\\!a_{7}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{5}\\!&\\!a_{4}\\!&\\!a_{10}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{6}\\!\\\
\\!a_{6}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{5}\\!&\\!a_{7}\\!&\\!a_{1}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{5}\\!&\\!a_{10}\\!&\\!a_{4}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{6}\\!\\\
\\!a_{6}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{4}\\!&\\!a_{10}\\!&\\!a_{5}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{1}\\!&\\!a_{7}\\!&\\!a_{5}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{6}\\!\\\
\\!a_{6}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{10}\\!&\\!a_{4}\\!&\\!a_{5}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{7}\\!&\\!a_{1}\\!&\\!a_{5}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{6}\\!\\\
\\!a_{6}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{10}\\!&\\!a_{4}\\!&\\!a_{5}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{7}\\!&\\!a_{5}\\!&\\!a_{1}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{8}\\!&\\!a_{6}\\!&\\!a_{2}\\!\\\
\\!a_{5}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{6}\\!&\\!a_{4}\\!&\\!a_{10}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{6}\\!&\\!a_{1}\\!&\\!a_{7}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{5}\\!\\\
\\!a_{5}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{6}\\!&\\!a_{10}\\!&\\!a_{4}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{6}\\!&\\!a_{7}\\!&\\!a_{1}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{5}\\!\\\
\\!a_{6}\\!&\\!a_{4}\\!&\\!a_{10}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{5}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{2}\\!&\\!a_{8}\\!&\\!a_{6}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{1}\\!&\\!a_{7}\\!&\\!a_{5}\\!\\\
\\!a_{6}\\!&\\!a_{10}\\!&\\!a_{4}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{5}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{9}\\!&\\!a_{2}\\!&\\!a_{6}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{7}\\!&\\!a_{1}\\!&\\!a_{5}\\!\\\
\\!a_{6}\\!&\\!a_{10}\\!&\\!a_{4}\\!&\\!a_{8}\\!&\\!a_{2}\\!&\\!a_{5}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{8}\\!&\\!a_{6}\\!&\\!a_{2}\\!&\\!a_{9}\\!&\\!a_{3}\\!&\\!a_{7}\\!&\\!a_{5}\\!&\\!a_{1}\\!\end{array}\right)\
.$

The eigenvalues of $A_{(3,2,1)}^{\phi}$ are

$(a_{1}-a_{4}-a_{7}+a_{10})_{3}\ ,\ a_{1}-a_{4}+a_{7}-a_{10}\ ,\
(a_{1}+a_{2}-a_{5}-a_{6})_{2}\ ,\ (a_{1}-a_{2}-a_{5}+a_{6})_{2}\ ,$
$(a_{1}-a_{2}-a_{3}+a_{4}+a_{7}-a_{8}-a_{9}+a_{10})_{2}\ ,\
(a_{1}-a_{2}-a_{3}+a_{4}-a_{7}+a_{8}+a_{9}-a_{10})_{2}\ ,$
$(a_{1}-a_{4}+a_{5}-a_{6}+a_{7}-a_{10})_{2}\ ,\
a_{1}+2a_{2}+2a_{3}+a_{4}-a_{7}-2a_{8}-2a_{9}-a_{10}\ ,$
$a_{1}+2a_{2}+2a_{3}+2a_{5}+2a_{6}+a_{7}+2a_{8}+2a_{9}+a_{10}\ .$

Acknowledgements. Part of this work was done in IHES during the program
dedicated to the 100-th (or rather 102-nd) anniversary of the Ising model, in
May – June of 2022. R.K., M.K. and S.S. are grateful to the organizers of the
program for the uplifting atmosphere. R.K. was supported by NSF grant
DMS-1940932 and the Simons Foundation grant 327929. The work of W.S. was
supported by the NSF grant DMS-2101491 and by the Sloan Research Fellowship.
The work of S.S. was supported by the RSF under project 23-11-00150.

## References

  * [BHR] Bidigare P., Hanlon P. and Rockmore D., A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements, Duke Math. Journal, 1999, Jul; 99(1):135-74.
  * [B] Brown K.S., Semigroups, rings, and Markov chains, Journal of Theoretical Probability, 2000, Jul; 13:871-938.
  * [BD] Brown K.S. and Diaconis P., Random walks and hyperplane arrangements, Annals of Probability, 1998, Oct; 1:1813-54.
  * [D] Dorpalen-Barry, G.A., Cones of hyperplane arrangements (Doctoral dissertation, 2021, University of Minnesota).
  * [OS] Ogievetsky O. and Shlosman S., Plane Partitions and Their Pedestal Polynomials, Mathematical Notes, 2018, May; 103(5):793-6.
  * [Sa] Saliola F.V., The face semigroup algebra of a hyperplane arrangement, Canadian Journal of Mathematics, 2009, Aug; 61(4):904-29.
  * [S] Shlosman S., The Wulff construction in statistical mechanics and combinatorics Russian Mathematical Surveys, 56(4), p.709-38, 2001.
  * [Sl] Sloane N.J.A., The on-line encyclopedia of integer sequences, http://www.oeis.org/.
  * [St] Stanley R., Enumerative Combinatorics, Cambridge University Press, New York, NY, USA, 2 edition, 2012.