# Kernel of a matrix and the Catalan numbers

Let $$B_n$$ denote the Boolean lattice of a set with $$n \geq 2$$ elements and $$C_n$$ the matrix with entries $$c_{i,j}=1$$ if $$i \leq j$$ and $$c_{i,j}=0$$ else, where $$i,j\in B_n$$.

Let $$M_n:=C_n+C_n^T$$ (this is also the Cartan matrix of a certain Frobenius algebra associated to $$B_n$$), which is a symmetric matrix. Thus geometric and algebraic multiplicity should coincide. Let $$I$$ denote the identity matrix.

Question: Is there a bijective proof that for $$n$$ even (odd) we have that the basis of the kernel of $$M_n - 2 I$$ ($$M_n-3 I$$) is enumerated by the Catalan numbers?

This is true for $$n \leq 15$$.

Here a bijective proof asks for a bijection of a basis of the kernel to known combinatorial objects that are enumerated by the Catalan numbers.

For example for $$n=6$$, the kernel has dimension 5 and basis vectors are given by

(0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, -1, 1, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, -1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0),

(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -1, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 1, 0, 0, 1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

I was not able to see a pattern so far for a nice basis of the kernel as the vectors are so big for larger n.

For example for $$n=2$$, $$C_2$$ is given by $$\begin{bmatrix} 1 & 1 & 1 &1 \\ 0 & 1 & 0 &1\\ 0 & 0 & 1 &1\\ 0 & 0 & 0 &1\\ \end{bmatrix}$$ and $$M_2$$ is given by $$\begin{bmatrix} 2 & 1 & 1 &1 \\ 1 & 2 & 0 &1\\ 1 & 0 & 2 &1\\ 1 & 1 & 1 &2\\ \end{bmatrix}$$.

• @SamHopkins Of course.
– Mare
Aug 2, 2021 at 18:50
• @RolandBacher With Sage. Took some weeks.
– Mare
Aug 2, 2021 at 21:07
• Observation: relations in the kernel only involve sets of cardinalities $k-1$ and $k$ for $n=2k-1$ and sets of cardinality $k$ for $n=2k$. This might be easier to prove as the first step, and might bring you close to Catalan numbers... Aug 3, 2021 at 5:07
• To seek for patterns, here are examples. For $n=5$, one basis is$$\begin{array}{l}x_{12}-x_{13}-x_{25}+x_{35}+x_{124}-x_{134}-x_{245}+x_{345}\\x_{13}-x_{15}-x_{34}+x_{45}+x_{123}-x_{125}-x_{234}+x_{245}\\x_{14}-x_{15}-x_{34}+x_{35}+x_{124}-x_{125}-x_{234}+x_{235}\\x_{23}-x_{25}-x_{34}+x_{45}+x_{123}-x_{125}-x_{134}+x_{145}\\x_{24}-x_{25}-x_{34}+x_{35}+x_{124}-x_{125}-x_{134}+x_{135}\end{array}$$ Aug 3, 2021 at 5:46
• and for $n=6$,$$\begin{array}{l}x_{123}-x_{124}-x_{136}+x_{146}-x_{235}+x_{245}+x_{356}-x_{456}\\x_{124}-x_{126}-x_{145}+x_{156}-x_{234}+x_{236}+x_{345}-x_{356}\\x_{125}-x_{126}-x_{145}+x_{146}-x_{235}+x_{236}+x_{345}-x_{346}\\x_{134}-x_{136}-x_{145}+x_{156}-x_{234}+x_{236}+x_{245}-x_{256}\\x_{135}-x_{136}-x_{145}+x_{146}-x_{235}+x_{236}+x_{245}-x_{246}\end{array}$$ Aug 3, 2021 at 5:46

Another suggestion: let $$A_{2n}=M_{2n}-2I$$ ($$I$$=identity matrix), so we are interested in $$\ker A_{2n}$$. Let $$V$$ be the vector space on which $$A_{2n}$$ acts, so we can regard $$V$$ as having a basis consisting of all subsets of $$[2n]=\{1,2,\dots,2n\}$$. Thus $$V$$ has a grading $$V_0\oplus V_1\oplus\cdots \oplus V_{2n}$$, where $$V_i$$ has a basis consisting of all $$i$$-element subsets of $$[2n]$$. The symmetric group $$\mathfrak{S}_{2n}$$ acts on $$V$$ and preserves the grading. Write $$M_\lambda$$ for the irreducible $$\mathfrak{S}_{2n}$$-module indexed by the partition $$\lambda$$ of $$2n$$. Then (as is well-known) $$V_i$$ decomposes as $$M_{(2n)}\oplus M_{(2n-1,1)} \oplus \cdots\oplus M_{(2n-i,i)}$$ for $$0\leq i\leq n$$, and $$V_i\cong V_{2n-i}$$ (as $$\mathfrak{S}_{2n}$$-modules).
Assuming that $$\dim\ker A_{2n}=C_n$$, it is natural to conjecture that as an $$\mathfrak{S}_{2n}$$-module, $$\ker A_{2n}$$ is isomorphic to the irreducible module $$M_{(n,n)}$$. The operator $$\frac{1}{(2n)!}\sum_{w\in\mathfrak{S}_{2n}}\chi^{(n,n)}(w)w$$ will then project $$V_n$$ to $$\ker A_{2n}$$. Here $$\chi^{(n,n)}$$ is the irreducible character of $$\mathfrak{S}_{2n}$$ indexed by the partition $$(n,n)$$. There is something similar for $$M_{2n+1}$$.
Only a suggestion: This smells of the Temperley-Lieb algebra. Eigenspaces of $$M_n$$ are invariant under the obvious action of the symmetric group $$S_n$$. The $$2-$$eigenspace of $$M_n$$ is thus a decomposition of irreps of $$S_n$$. The sum of squared dimensions for irreps with Young diagrams having at most $$2$$ rows of $$S_n$$ is the $$n-$$th Catalan number.
The relation is probably not completely straightforward: Since Catalan numbers grow like $$4^nn^{-3/2}$$ (up to a constant), your matrix $$M_n$$ should roughly involve the Temperley Lie algebra of $$S_{\lfloor n/2\rfloor}$$.
In any case, the determination of the involved irreps of $$S_n$$ gives probably an indication of what is going on.