\documentclass[12pt]{article} \usepackage{amsmath,amsfonts,amssymb} \usepackage{amsthm} \addtolength\textwidth{15mm} \hoffset-1cm \newcommand{\I}[1]{\mathbb{#1}} \newtheorem{prop}{Proposition} \newtheorem{theor}{Theorem} \newtheorem{cor}{Corollary} \newtheorem*{lem}{Lemma} %\renewcommand{\proofname}{Proof} \parindent0pt \begin{document} \title{Inversion of Incidence Mappings} \date{} \author{Helmut Kr\"amer\\[5pt] Mathematisches Seminar der Universit\"at Hamburg\\ Bundesstra{\ss}e 55\\ D--20146 Hamburg} \maketitle \bigskip \begin{abstract} Denote by $H(t,q),\;t\leq q$, the incidence matrix (with respect to inclusion) of the $t$--sets versus the $q$--sets of the $n$--set $\{1,2,\ldots,n\}$. This matrix is considered as a linear map of $\I Q$--vector spaces $$ C_q(n)\longrightarrow C_t(n), $$ where $C_s(n)$ is the $\I Q$--vector space having the $s$--sets as a basis $(s\leq n)$. As a basic tool, we introduce a connection of the vector spaces to a graded $\I Q$--algebra (which is at the same time an Artinian local ring). We define mappings $\triangle$ and $\I X$ of this algebra of degree $-1$ and 1, respectively. These two mappings correspond up to a scalar factor to the linear mappings $H(s-1,s)$ and $H(s-1,s)^T$, respectively. Then, a relation between the algebra maps $\triangle$ and $\I X$ is established. This relation allows to rewrite a term $\triangle^\beta \I X^\alpha$ with $\alpha,\beta$ non--negative integers (subject to some restrictions) as a sum $\sum\limits_{k=0}^\beta \binom{\beta}{k}\cdot\I X^{\alpha-k}\cdot\triangle^{\beta-k}$ (up to some scalar factors). As a main result of this relation surjectivity of the map $\triangle^{q-t}$ (related to $H(t,q)$ up to a scalar factor) is proved under the assumption $\binom{n}{t}\leq\binom{n}{q}$. Moreover, a right inverse for the matrix $H(t,q)$ is given explicitely. This result is exploited to give an inverse of the (square) incidence matrix $H(t,q)$ in the case $t=n-q$. These results extend some work done by J.B. Graver and W.B. Jurkat. \end{abstract} \bigskip {\bf 1.} For $n\in\I N$ we put $$ \underline{\underline{n}}=\{1,2,\ldots,n\}. $$ For $0\leq t\leq q\leq n$ we denote by $H\,(t,q)$ the incidence matrix (with respect to inclusion) of the $t$--sets versus the $q$--sets of the $n$--set $\underline{\underline{n}}$ and by $C_q(n)$ the $\I Q$--vector space having the basis $\big\{[M]\big\}_{M\subseteq\underline{\underline{n}}, |M|=q}$. Then $H\,(t,q)$ defines a linear mapping (``incidence mapping'') $$ C_q(n)\longrightarrow C_t(n),\;[M]\longrightarrow \sum_{N\subseteq M}^{|N|=t}[N], $$ which is denoted by the same symbol $H\,(t,q)$. -- \medskip The transpose $H\,(t,q)^T$ of $H\,(t,q)$ defines a linear mapping $$ C_t(n)\longrightarrow C_q(n),\;[N]\longrightarrow\sum_{N\subseteq M}^{|M|= q}[M], $$ which is denoted by the same symbol $H\,(t,q)^T$. Finally we define the ``augmentation mapping'' $$ H\,(-1,0):C_0(n)\longrightarrow 0. $$ Assume that $\dim_{\I Q} C_t(n)=\binom{n}{t}\leq \binom{n}{q}= \dim_{\I Q} C_q(n)$. Then it is known that the mapping $H\,(t,q)$ is surjective ([3], 2.3, 2.4), therefore in case of equality of the two dimensions under consideration an isomorphism. In this case moreover we exhibit a method to compute explicitely $H\,(t,q)^{-1}$ by defining a structure of a graded commutative algebra on the graded $\I Q$--vector space $C_\ast(n):=\bigoplus\limits_{q=0}^n C_q(n)$ such that at the same time $C_\ast(n)$ becomes an Artinian local ring. \medskip We provide an example for the computation of $H\,(n-q,q)^{-1}$: \begin{itemize} \item[$\bullet$] {\it Assume $n$ odd and $q=\lfloor\frac{n}{2}\rfloor+1$. Then one has} $$ H\,(q-1,q)^{-1} =\sum_{j=1}^q\frac{(-1)^{j+1}}{j}\cdot H\,(q-j,q)^T\circ H\,(q-j,q-1). $$ \end{itemize} There is the following generalization: \begin{itemize} \item[$\bullet\bullet$] {\it Assume $q\leq \frac{n}{2}$ if $n$ is even or $q\leq\lfloor\frac{n}{2}\rfloor+1$ if $n$ is odd. Then the mapping $$ K\,(q,q-1):C_{q-1}(n)\longrightarrow C_q(n) $$ defined by $$ K\,(q,q-1)=\sum_{j=1}^q\frac{(-1)^{j+1}}{j}\binom{n-2q+j+1}{j}^{-1}\cdot H \,(q-j,q)^T\circ H\,(q-j,q-1) $$ is a right inverse of} $H\,(q-1,q)$. \end{itemize} \bigskip {\bf 2.} One defines the structure of a commutative $\I Q$--algebra on $C_\ast (n)=\bigoplus\limits_{q=0}^n C_q(n)$ by setting for subsets $M,N$ of $\underline{\underline{n}}$ $$ [M]\cdot[N]=\left\{ \begin{array}{cl} [M\cup N], & \mbox{if } M\cap N=\emptyset,\\ 0, & \mbox{otherwise}. \end{array} \right. $$ This $\I Q$--algebra which we denote by ${\frak C}_\ast(n)$ is isomorphic to $$ {\cal A}\,(n):=\I Q\,[T_1,\ldots,T_n]/(T_1^2,T_2^2,\ldots,T_n^2) =\I Q\,[X_1,\ldots,X_n], $$ where $T_1,\ldots,T_n$ are algebraically independent elements and $X_j=T_j$ mod $(T_1^2,\ldots,T^2_n)$. The isomorphism ${\cal C}_\ast(n)\longrightarrow {\cal A}\,(n)$ is induced by $$ \begin{array}{rcl} [M]=\big[\{j_1,\ldots,j_q\}\big] & \longrightarrow & X_{j_1}X_{j_2}\cdot\ldots \cdot X_{j_q},\text{ if }|M|=q\geq 1,\\[2mm] [\emptyset] & \longrightarrow & 1\in\I Q. \end{array} $$ In the sequel we identify ${\frak C}_\ast(n)$ and ${\cal A}\,(n)$. \bigskip Let ${\frak C}_\ast(n)_p$ denote the $\I Q$--module of the elements of degree $p$ of the graded algebra ${\frak C}_\ast(n)$. Then one has $$ {\frak C}_\ast(n)_p=\left\{ \begin{array}{cl} C_p(n), & 0\leq p\leq n,\\ 0, & p>n. \end{array} \right. $$ To the mappings $H\,(q-1,q),\,0\leq q\leq n$, corresponds the map $\triangle: {\frak C}_\ast(n)\longrightarrow{\frak C}_\ast(n)$ of degree $-1$ defined by $$ \begin{array}{rcl} \triangle\Big|_{\I Q}=0,\;\triangle X_j & = & 1,\,j\in \underline{\underline{n}},\\[4mm] \triangle\,(X_{j_1}\cdot X_{j_2}\cdot\ldots\cdot X_{j_q}) & = & \sum\limits_{k=1}^q X_{j_1}\cdot\ldots\cdot\widehat X_{j_k} \cdot\ldots\cdot X_{j_q},\;2\leq q\leq n, \end{array} $$ $(1\leq j_1p. \end{array} \right.\leqno {(2)\ldots} $$ In this sum a term $X_{i_1}\cdot\ldots\cdot X_{i_{m-1}},\;(1\leq i_1<\ldots< i_{m-1}\leq p)$ occurs exactly in the terms $\triangle\,(X_{i_1} \cdot\ldots\cdot X_{i_{m-1}}\cdot X_t),\; t\in\underline{\underline{p}} \backslash\{i_1,\ldots,i_{m-1}\}$ with factor 1; therefore it occurs in $\triangle\,(\I Z^m)$ with factor $m!(p-m+1)=m\,(p-m+1)(m-1)$!. The conclusion follows now from equation (2). \end{proof} \bigskip We remark that $\triangle$ is no derivation of ${\frak C}_\ast(n)$. \medskip Let ${\frak m}:=(X_1,\ldots,X_n)$ denote the maximal ideal of ${\frak C}_\ast (n)$. Then it holds that\\ ${\frak m}^{n+1}=0$. If ${\frak p}$ is a prime ideal of ${\frak C}_\ast(n)$, then from ${\frak m}^{n+1}\subseteq{\frak p}$ one concludes ${\frak m}={\frak p}$. Therefore ${\frak C}_\ast(n)$ is an Artinian local ring. Let $\widetilde \triangle$ denote a derivation of ${\frak C}_\ast(n)$ (into itself). Then it must hold for all $j\in\underline{\underline{n}}$ that $$ 0=\widetilde\triangle\,(X_j^2)=2X_j\widetilde\triangle\,(X_j), $$ therefore $\widetilde\triangle\,(X_j)\in{\frak m}$. -- So $\widetilde \triangle$ maps ${\frak m}$ (and ${\frak C}_\ast(n)$, too) into ${\frak m}$ (compare with [4], \S 1, Exercise 4). \bigskip Now we extend Prop.2, ii): \medskip \begin{prop} Assume $0\leq s\leq n-1,\;\alpha\in\I N,\;\alpha+s\leq n$ and $w\in C_s(n)$. Then the following identity holds: $$ \triangle\,(\I X^\alpha\cdot w)=\I X^\alpha\cdot\triangle\,(w)+\alpha\, (n-\alpha-2s+1)\I X^{\alpha-1}\cdot w. $$ \end{prop} \begin{proof} In case $s=0$ the statement is true according to Prop. 2, ii). Assume now $s\geq 1$ and take $$ w=X_{j_1}\cdot\ldots\cdot X_{j_s} $$ as a basis element of $C_s(n)$. One defines $$ \I Y=\sum_{k=1}^s X_{j_k},\;\I Z=\I X-\I Y. $$ Since $w$ is a word in {\it all} $X_{j_1},\ldots,X_{j_s}$ one has $\I Y\cdot w=0$. Assume $t\geq 0$. Then the following holds $$ \I X^tw=(\I Y+\I Z)^t\cdot w=\sum_{r=0}^t\binom{t}{r}\I Z^r \I Y^{t-r}\cdot w=\I Z^tw, $$ furthermore according to the definition of $\I Y$ and $\I Z\;$ Fund $(w)\, \cap$ Fund $(\I Z^t)=\emptyset$; from Prop. 2 one concludes $$ \left\{ \begin{array}{ll} \triangle\,(\I X^\alpha\cdot w) &=\triangle\,(\I Z^\alpha\cdot w)=\I Z^\alpha \cdot\triangle\,(w)+w\cdot\triangle\,(\I Z^\alpha)\\[1mm] & = \I Z^\alpha\cdot\triangle\,(w)+\alpha\,(n-s-\alpha+1)\,\I Z^{\alpha-1}w\\[1mm] & = \I Z^\alpha\cdot\triangle\,(w)+\alpha\,(n-s-\alpha+1)\,\I X^{\alpha-1}w. \end{array} \right. \leqno {(3)\ldots} $$ Now we use $$ \I Y^t\cdot\triangle\,(w)=\left\{ \begin{array}{cl} 0, & t>1,\\ s\cdot w, &t=1. \end{array} \right. $$ Therefore $$ \begin{array}{ll} \I X^\alpha\triangle\,(w) & =\left(\sum\limits_{r=0}^\alpha\binom{\alpha}{r} \I Y^r\I Z^{\alpha-r}\right)\cdot\triangle\,(w)=(\alpha\I Y\cdot \I Z^{\alpha-1}+\I Z^\alpha)\cdot\triangle\,(w)\\[2mm] & =\alpha s\I Z^{\alpha-1}\,w+\I Z^\alpha\cdot\triangle\,(w)=\alpha\cdot s\cdot \I X^{\alpha-1}w+\I Z^\alpha\cdot\triangle\,(w). \end{array} $$ Replacing the term $\I Z^\alpha\triangle\,(w)$ in Eq. (3) yields $$ \triangle\,(\I X^\alpha w)=\I X^\alpha\cdot\triangle\,(w)+\alpha\,(n-2s-\alpha+1) \,\I X^{\alpha-1}\cdot w, $$ as claimed. -- \end{proof} \bigskip Prop. 3 is a special case of \medskip \begin{prop} The same assumptions about $s,\alpha$ are in force as in Prop. 3. Assume $r\in\I R$ and $k\in\I N$ and define $$ [r]_k=r\,(r-1)\cdot(r-2)\cdot\ldots\cdot (r-k+1),\,[r]_0=1. $$ Let $\beta$ be a non--negative integer and assume $0\leq\beta\leq\alpha$. Then the following identity holds $$ \triangle^\beta(\I X^\alpha\cdot w)=\sum_{k=0}^\beta\binom{\beta}{k} [\alpha]_k[n-\alpha-2s+\beta]_k\cdot\I X^{\alpha-k}\cdot \triangle^{\beta-k}(w). $$ \end{prop} \begin{proof} There is nothing to prove in case $\beta=0$; in case $\beta=1$ the claim boils down to Prop. 3. If $0\leq j\leq \beta$ we put $$ [\beta,j]=\I X^{\alpha-j}\cdot\triangle^{\beta-j}(w) $$ and prove first of all by induction with respect to $\beta\geq 1$, that the identity $$ \triangle^\beta(\I X^\alpha w)=\sum_{j=0}^\beta c\,(\beta,j)\cdot[\beta,j],\quad c\,(\beta,j)\in\I Q, \leqno {(4)\ldots} $$ holds; furthermore this will yield recursion formulas for the coefficients $c\,(\beta,j)$. In case $\beta=1$ one has according to Prop. 3 $$ c\,(1,0)=1,\;c\,(1,1)=\alpha\,(n-\alpha-2s+1)=:\lambda\,(\alpha,s). $$ Since $\triangle^{k-j} (w)\in C_{s-k+j}(n)$, Prop. 3 now yields $$ \begin{array}{c} \triangle\,\bigl([k,j]\bigr)=\triangle\bigl(\I X^{\alpha-j}\cdot \triangle^{k-j}(w)\bigr)=\\[2mm] =\I X^{\alpha-j}\cdot\triangle^{k-j+1}(w)+(\alpha-j)\cdot\bigl(n-(\alpha-j)- 2(s-k+j)+1\bigr)\cdot\I X^{\alpha-j-1}\cdot\triangle^{k-j}(w)=\\[2mm] =\I X^{\alpha-j}\cdot\triangle^{k-j+1}(w)+\lambda\,(\alpha-j,s-k+j)\cdot \I X^{\alpha-j-1}\cdot\triangle^{k-j}(w), \end{array}$$ that is $$ \triangle\,\bigl([k,j]\bigr)=[k+1,j]+\lambda(\alpha-j,s-k+j)[k+1,j+1]. $$ According to the induction hypothesis we obtain $$ \begin{array}{rl} \triangle^{\beta+1}(\I X^\alpha w) & =\triangle\,\bigl(\triangle^\beta(\I X^\alpha \cdot w)\bigr)=\\[3mm] c\,(\beta,0)[\beta+1,0] & +\sum\limits_{j=1}^\beta \bigl\{c\,(\beta,j)+c\, (\beta,j-1)\cdot\lambda\,(\alpha-j+1,s-\beta+j-1)\bigr\}\cdot[\beta+1,j]\\[5mm] & +\lambda\,(\alpha-\beta,s)\cdot c\,(\beta,\beta)[\beta+1,\beta+1], \end{array} $$ which proves Eq. (4); at the same time we have proved the following recursion formulas $$ c\,(\beta+1,0)=c\,(\beta,0),\;c\,(\beta+1,\beta+1)=\lambda \,(\alpha-\beta,s)\,c\,(\beta,\beta),\leqno{(5.1)\;\ldots} $$ $$ c\,(\beta+1,j)=c\,(\beta,j)+\lambda\,(\alpha-j+1,s-\beta+ j-1)\cdot c\,(\beta,j-1),(1\leq j\leq \beta). \leqno{(5.2)\;\ldots} $$ \bigskip Eq. (5.1) yields immediately $$ \left\{ \begin{array}{lll} c\,(\beta,0)=1 & &\\ & & (0\leq \beta\leq \alpha).\\ c\,(\beta,\beta)=[\alpha]_\beta[n-\alpha-2s+\beta]_\beta & & \end{array} \right. \leqno {(6)\ldots} $$ Now we claim that the following holds in case $\beta\geq j$ $$ c\,(\beta,j)=\binom{\beta}{j}[\alpha]_j[n-\alpha-2s+\beta]_j\leqno{ (7)\ldots} $$ which we prove by induction with respect to the pairs $(\beta,j),\;\beta\geq j$. The claim is true for pairs $(\beta,0)$ according to Eq. (6). Assume that it has already been proved that in case $j\geq 1$ the claim is true for all pairs $(\gamma,j-1),\;\gamma\geq j-1$. We rewrite a term in the recursion formula (5.2) $$ \lambda\,(\alpha-j+1,s-\beta+j-1)=(\alpha-j+1)(n-\alpha-2s+2\beta-j+2). $$ Now we proceed by induction with respect to $\beta,\beta\geq j$. In case $\beta=j$ the statement is true according to Eq. (6). Assume that the statement has already be proved for some $\beta\geq j$. Then we have according to Eq. (5.2) $$ \begin{array}{ll} c\,(\beta+1,j)= &\binom{\beta}{j}[\alpha]_j[n-\alpha-2s+j]_j\;+\\[2mm] & +(n-\alpha-2s+2\beta-j+2)\cdot\binom{\beta}{j-1}[\alpha]_j [n-\alpha-2s+\beta]_{j-1}. \end{array} $$ Using the identities $\binom{\beta}{j}=\binom{\beta}{j-1}\cdot \displaystyle{\frac{\beta-j+1}{j}}$ and $\binom{\beta}{j}+\binom{\beta}{j-1} =\binom{\beta+1}{j}$ we conclude $$ \begin{array}{rcl} c\,(\beta+1,j) & = & [\alpha]_j[n-\alpha+2s+\beta]_{j-1}\cdot\left\{ \binom{\beta+1}{j}(n-\alpha-2s)\right.+\binom{\beta}{j}(\beta-j+1)+\\[4mm] & & \left. +\binom{\beta}{j-1}(2\beta-j+2)\right\}\\[4mm] & = & [\alpha]_j[n-\alpha-2s+\beta]_{j-1}\cdot\binom{\beta+1}{j} (n-\alpha-2s +\beta+1)\\[4mm] & = &\binom{\beta+1}{j}[\alpha]_j[n-\alpha-2s+(\beta+1)]_j \end{array} $$ This proves Eq. (7). -- \end{proof} \bigskip {\bf 3.} Assume now $0\leq t\leq q\leq n$ and $\binom{n}{t}\leq\binom{n}{q}$. We denote $\nabla:=\triangle^{q-t}:$\\ $C_q(n)\longrightarrow C_t(n)$ and fix some $w\in C_t(n)$. Our aim is to construct explicitely a primage $u\in C_q(n)$ of $w$ with respect to $\nabla$. Therefore we make the following ansatz (we will see later that this method will work): If $0\leq j\leq t$ we denote $$ U_j:=\I X^{q-t+j}\cdot\triangle^j(w) $$ and put $$ u=\sum_{j=0}^t x_j U_j $$ where the $x_j\in\I Q$ have to be determined. To compute $\nabla U_j$ apply Prop. 4 (replace here $w$ by $\triangle^j(w)\in C_{t-j}(n)$) and obtain with the convention $$ c\,(k,j) :=\binom{q-t}{k}[q-t+j]_k\cdot[n-2t+j]_k, \quad (0\leq j\leq t,\;0\leq k\leq q-t) \leqno {(8)\ldots} $$ $$\nabla U_j=\sum_{k=0}^{q-t}c\,(k,j)\cdot\I X^{q-t+j-k}\cdot \triangle^{q-t+j-k}(w)\in C_t(n), $$ therefore $$ \nabla u=\sum_{k=0}^{q-t}\sum_{j=0}^t x_j c\,(k,j)\cdot\I X^{q-t+j-k}\cdot \triangle^{q-t+j-k}(w).\leqno{(9)\ldots} $$ We order the right hand side of this equation with respect to the terms $$ V_m:=\I X^m\cdot\triangle^m(w),\;0\leq m\leq t, $$ by defining $$ V_{k,j}=\I X^{q-t+j-k}\cdot\triangle^{q-t+j-k}(w).$$ Then it holds that $V_{k,j}=0$ if $q-t+j-k>t$ and $$ V_{k,j}=V_m $$ exactly if $k=(q-t)-l,\,j=m-l,\,0\leq l\leq \min\{m,q-t\}$. Therefore Eq. (9) yields now $$ \nabla u=\sum_{m=0}^t d_m V_m $$ with $$ d_m=\sum_{l=0}^{\min\{m,q-t\}} c\,\bigl((q-t)-l,\,m-l\bigr)\cdot x_{m-l}. \leqno{(10)\ldots} $$ \bigskip We observe that $V_0=w$. -- So $u$ is in fact a preimage, if the system of linear equations in the unknowns $x_0,\ldots,x_t$ $$ \begin{array}{c} d_0=1,\\[2mm] d_m=0,1\leq m\leq t, \end{array} $$ is solvable. This will be the case if all $c\,(q-t,m)$ don't vanish. In fact we have in the trivial case $q-t=0$ $$ c\,(0,m)=1,\; 0\leq m\leq t, $$ (and the system has the solution $x_0=1,\; x_1=x_2=\ldots=x_t=0$). In case $q-t>0$ it is sufficient (see Eq. (8)) to show that the $$ [n-2t+m]_{q-t} $$ don't vanish. Now the smallest factor $f_m$ in the above mentioned falling factorial is $$ f_m=n-2t+m-(q-t)+1=n-(q+t)+m+1. $$ Assume first $\binom{n}{t}=\binom{n}{q}$. Then it holds that $t+q=n$, therefore $f_m=m+1$. In the second case the condition $\binom{n}{k}< \binom{n}{q}$ is equivalent to $q+t+1\leq n$, therefore $f_m\geq m+2$. \smallskip So our ansatz has worked and we have proved \medskip \begin{theor} Assume $0\leq t\leq q\leq n$ and $\binom{n}{t}\leq\binom{n}{q}$. Then the mapping $$ \nabla:=\triangle^{q-t}:C_q(n)\longrightarrow C_t(n) $$ is surjektiv. There exist $x_0,x_1,\ldots,x_t\in\I Q$ such that the mapping $$ \nabla^{[-1]}:=\sum_{j=0}^t x_j\cdot\I X^{q-t+j}\cdot\triangle^j \Big|_{C_t(n)} $$ is a right inverse with respect to $\nabla$ (in case $\binom{n}{t}= \binom{n}{q}\quad\nabla^{[-1]}$ is the inverse of $\nabla$). \medskip If one denotes in case $0\leq k\leq q-t,\,0\leq j\leq t$, $$ c\,(k,j):=\binom{q-t}{k}\cdot[q-t+j]_k\cdot[n-2t+j]_k, $$ then one can choose the $x_0,\ldots,x_t$ as the (existing) solution of the system of linear equations $$ \begin{array}{c} c\,(q-t,0)\cdot x_0=1,\\ \sum\limits_{l=0}^{\min\{m,q-t\}}c\,\bigl((q-t)-l,m-l\bigr)\cdot x_{m-l}=0,\; 1\leq m\leq t. \end{array} $$ \end{theor} \bigskip \begin{cor} If one defines $$ y_j=(q-t)!j!(q-t+j)!\cdot x_j,\;0\leq j\leq t, $$ then the mapping $K\,(q,t): C_t(n)\longrightarrow C_q(n)$ defined by $$ K\,(q,t):=\sum_{j=0}^t y_j\cdot H\,(t-j,q)^T\circ H\,(t-j,t) $$ is a right inverse of $H\,(t,q)$. \end{cor} \bigskip {\it Proof} (of the corollary). According to Prop. 1 one has $$ \nabla=(q-t)!\cdot H\,(t,q) $$ and $$ \I X^{q-t+j}\cdot\triangle^j\Big|_{C_t(n)}=(q-t+j)!j!\cdot H\,(t-j,q)^T \circ H\,(t-j,t). $$\\[-1.2cm] \hspace*{\fill}$\square$ \bigskip Now we exploit the the theorem and the corollary. The following result is properly spoken another corollary; however, we state it as \bigskip \begin{theor} Assume $0\leq t< q\leq n$ and $t+q=n$. Then the following identity holds: $$ H\,(t,q)^{-1}=\sum_{j=0}^t(-1)^j\frac{q-t}{q-t+j}\,H\,(t-j,q)^T\circ H\, (t-j,t). $$ \end{theor} {\it Proof}. We introduce a new parameter $p=q-t$. Then we obtain $n-2t=p$ and $$ c\,(k,j)=\binom{p}{k}\cdot\bigl([p+j]_k\bigr)^2. $$ We switch now to new indeterminates $\alpha_j$ in the system of linear equations of the Theorem by defining $$ x_j=(-1)^j\frac{\alpha_j}{((p+j)!)^2},\;\alpha_j\in\I Q. $$ An elementary computation which we omit yields $$ \alpha_0=1 $$ and the following recursion formula $$ \alpha_j=\sum_{l=1}^{\min\{p,j\}} (-1)^{l+1}\binom{p}{l}\alpha_{j-l},\; 1\leq j\leq t. $$ We compute the $\alpha_j$ by elementary difference calculus; let us define therefore functions $$ f_p:\I N_0\longrightarrow \I Q $$ by the following conditions $$ \left\{ \begin{array}{c} f_p(0)=1,\\[4mm] f_p(j)=\sum\limits_{l=1}^{\min\{p,j\}}(-1)^{l+1}\displaystyle{\binom{p}{l}} f_p(j-l),\;1\leq j. \end{array} \right. \leqno{(11)\ldots} $$ Then we claim $$ f_p(j)=\binom{j+p-1}{p-1}.\leqno {(12)\ldots} $$ \bigskip In order to prove Eq. (12) we need the following \medskip \begin{lem} Assume $p\geq 1$ and $0\leq l\leq p$. Then the following identity holds $$ \binom{p}{l}-\binom{p}{l-1}+\binom{p}{l-2}\mp\ldots+(-1)^l\binom{p}{0}= \binom{p-1}{l}. $$ \end{lem} \bigskip {\it Proof} (of the lemma): Denote the left hand side of this identity by $S_l(p)$. Then we have $$ S_l(p)=\binom{p}{l}-S_{l-1}(p). $$ Now we proceed by induction with respect to $l.\hspace{\fill}\square$ \bigskip Denote by $\triangle f_p$ the first difference series of $f_p,$ that is $$ (\triangle f_p)(j)=f_p(j+1)-f_p(j),\,j\in\I N_0. $$ Then we have by placing $f_p(k)=\alpha_k$ and $h=\min\{p,j\}$, in case $j\geq 1$ $$ \begin{array}{ll} \alpha_{j+1}-\alpha_j & =\left[\binom{p}{1}-\binom{p}{0}\right]\cdot(\alpha_j -\alpha_{j-1})-\left[\binom{p}{2}-\binom{p}{1}+\binom{p}{0}\right]( \alpha_{j-1}-\alpha_{j-2})\pm\ldots\\[4mm] & +(-1)^{h+1}\left[\binom{p}{h}-\binom{p}{h-1}+\binom{p}{h-2}\mp\ldots+ (-1)^h\binom{p}{0}\right]\cdot(\alpha_{j-h+1}-\alpha_{j-h}). \end{array} $$ According to the lemma this rewrites to $$ (\triangle f_p)(j)=\sum_{l=1}^{\min\{j,p\}} (-1)^{l+1}\binom{p-1}{l} (\triangle f_p)(j-l),\; j\geq 1. $$ Furthermore we have $$ (\triangle f_p)(0)=p-1=f_{p-1}(1),\; p\geq 2.$$ This yields in case $p\geq 2$ $$ (\triangle f_p)(j)=f_{p-1}(j+1),\; j\in\I N_0,\leqno{(13)\ldots} $$ since $\triangle f_p$ satisfies the same recursion formula (see Eq. (12)) as $f_{p-1}$ does. \medskip Now Eq. (12) is certainly true if $p=1$. Assume our claim is true if $p-1\geq 1$. Then according to Eq. (13) we have $$ (\triangle f_p)(j)=\binom{j+p-1}{p-2},\;j\in\I N_0. $$ Therefore the function $F:\I N_0\to\I Q$ defined by $$ F\,(j)=\binom{j+p-1}{p-1} $$ is a discrete indefinite integral of $\triangle f_p$; that is $\triangle F= \triangle f_p$. It follows that $$ F=f_p+\mbox{ const}, $$ but $F\,(0)=f_p(0)$, so we have $F=f_p$. Therefore the claim Eq. (12) is proved. \medskip Now we use the notations introduced in the corollary of Theorem 1 and obtain $$ y_j=(-1)^j\;\frac{p!\,j!\,(p+j)!}{((p+j)!)^2}\;\binom{j+p-1}{p-1}=(-1)^j \frac{p}{p+j}=(-1)^j\frac{q-t}{q-t+j}. $$ The statement of Theorem 2 now follows from the corollary to Theorem 1. \hspace{\fill}$\square$ \bigskip To exploit Theorem 1 and the corollary in the case $\binom{n}{t}\leq \binom{n}{q}$, we restrict ourselves to the condition $q-t=1$. We then have $q\leq \frac{n}{2}$ if $n$ is even and $q\leq \lfloor\frac{n}{2}\rfloor+1$ if $n$ is odd. \smallskip Here we have under the assumption $0\leq j\leq t = q-1$ $$\begin{array}{lcl} c\,(0,j) &=& 1,\\[1mm] c\,(1,j) &=& (j+1)(n-2q+j+2). \end{array} $$ We obtain the following system of linear equations in the unknowns $x_0, \ldots,x_t$ $$ \begin{array}{rcl} c\,(1,0)\,x_0 &=& 1,\\[1mm] c\,(1,j)\,x_j+x_{j-1} &=& 0,\;1\leq j\leq t, \end{array} $$ which has the solution $$ x_j=\frac{(-1)^j}{(j+1)![n-2q+j+2]_{j+1}},\; 0\leq j\leq t. $$ \bigskip Again with the notations of the corollary to Theorem 1 we obtain $$ y_j=j!\,(j+1)!\,x_j=\frac{(-1)^j}{j+1}\cdot\binom{n-2q+j+2}{j+1}^{-1}. $$ Now we change the indices from $j+1$ to $j$ and obtain the statement of example\quad $\bullet\bullet$~. \bigskip Finally let us evaluate Theorem 2 in case $n=5,\,q=3,\,t=2$. With the notation\\ $\{j_1,j_2,j_3,j_4,j_5\}=\underline{\underline 5}$ we obtain $$ H\,(2,3)^{-1}(X_{j_1}\cdot X_{j_2})=$$ $$ \begin{array}{ll} \displaystyle{\frac{1}{6}}\Big[2X_{j_1}X_{j_2}X_{j_3}&-X_{j_2}X_{j_3}X_{j_4} +2X_{j_3}X_{j_4}X_{j_5}-X_{j_1}X_{j_4}X_{j_5}+2X_{j_1}X_{j_2}X_{j_4}-X_{j_1}X_{j_3} X_{j_5}+\\[2mm] & +2X_{j_1}X_{j_2}X_{j_5}-(X_{j_1}X_{j_3}X_{j_4} +X_{j_2}X_{j_3}X_{j_5}+X_{j_2}X_{j_4}X_{j_5})\Big], \end{array} $$ \medskip and conclude that the matrix $H\,(2,3)^{-1}$ is ``non--sparse''. \vspace*{1cm} {\bf 4.} Finally we demonstrate the usefulness (as we hope) of the algebra ${\frak C}_\ast(n)$ by giving new proofs or extending, respectively, some results in [2]. \medskip \begin{itemize} \item[$\bullet\bullet\bullet$] (l.c., 3.3) {\it Let} $v\in\mbox{Ker }\triangle, \,w\in C_t(n)$, {\it such that} Fund $(v)\,\cap$ Fund $(w)=\emptyset$. {\it Then it holds that} $\triangle^{t+1}(v\cdot w)=0$. \end{itemize} \medskip This is an immidediate consequence of the property of $\triangle$ to be a ``quasi--derivation'' (see Prop. 2). \vspace*{8mm} Secondly, we exhibit a system of generators of $\text{Ker } H\,(t,q)$ provided $\binom{n}{t}<\binom{n}{q}$. \medskip We denote $K_q(n)=\mbox{Ker }\triangle\Big|_{C_q(n)}$. Then obviosly one has $K_q(n-1)\subset K_q(n)$. To determine remaining candidates $u$ of $K_q(n)$ we make the following ansatz $$ u=vX_n+w,\,v\in C_{q-1}(n-1),\, w\in C_q(n-1). \leqno{(14)\ldots}. $$ \bigskip Since Fund $(v)\,\cap$ Fund $(X_n)=\emptyset$, Prop. 2, i) yields $$ 0=\triangle u=(\triangle v)\cdot X_n+(v+\triangle w), $$ therefore $$ \triangle v=0,\; v+\triangle w=0. \leqno{(15)\ldots} $$ Assume now that is has been proved by induction with respect to $s$ that $K_t(s)$,\\$t\leq \lfloor\frac{s}{2}\rfloor,s\leq n-1$, is generated by elements of the shape $$ (X_{j_1}-X_{j_2})(X_{j_3}-X_{j_4})\cdot\ldots\cdot(X_{j_{2t-1}}- X_{j_{2t}})$$ with pairwise distinct $X_{j_k}$. Therefore we may assume (in Eq. (14), (15)) that $$ v=(X_{j_1}-X_{j_2})\cdot\ldots\cdot\Big(X_{j_{2(q-1)-1}}-X_{j_{2(q-1)}} \Big). $$ There are two cases to be considered. In the first case assume $2\,(q-1)=n-1$; then we have $n$ odd, $q=\lfloor\frac{n}{2}\rfloor+1$. According to $\bullet \quad K_q(n)=0$ and then there is no more to prove. \medskip In the second case assume $2\,(q-1)