Inversion of Incidence Mappings

Helmut Krämer

Mathematisches Seminar der Universität Hamburg Bundesstraße 55 D–20146 Hamburg

Abstract

Denote by H(t, q), t ≤ q, the incidence matrix (with respect to inclusion) of the t–sets versus the q–sets of the n–set {1, 2, …, n}. This matrix is considered as a linear map of ℚ–vector spaces

C_{q}(n) ⟶ C_{t}(n),

where C_{s}(n) is the ℚ–vector space having the s–sets as a basis (s ≤ n).

As a basic tool, we introduce a connection of the vector spaces to a graded ℚ–algebra (which is at the same time an Artinian local ring). We define mappings △ and 𝕏 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 △ and 𝕏 is established. This relation allows to rewrite a term △^{β}𝕏^{α} with α, β non–negative integers (subject

to some restrictions) as a sum ∑_{k=0}^{β} \binom{β}{k} · 𝕏^{α−k} · △^{β−k} (up to some scalar factors).

As a main result of this relation surjectivity of the map △^{q−t} (related to H(t, q) up to a scalar factor) is proved under the assumption \binom{n}{t} ≤ \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.

1. For n ∈ ℕ we put

\underline{\underline{n}} = \{1, 2, …, n\}.

For 0 ≤ t ≤ q ≤ 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 ℚ–vector space having the basis \{[M]\}_{M⊆\underline{\underline{n}},|M|=q}. Then H (t, q) defines a linear mapping (“incidence mapping”)

C_{q}(n) ⟶ C_{t}(n), [M] ⟶ ∑_{N⊆M}^{|N|=t}[N],

which is denoted by the same symbol H (t, q). –

The transpose H (t, q)^{T} of H (t, q) defines a linear mapping

C_{t}(n) ⟶ C_{q}(n), [N] ⟶ ∑_{N⊆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) ⟶ 0.

Assume that dim_{ℚ} C_{t}(n) = \binom{n}{t} ≤ \binom{n}{q} = dim_{ℚ} 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 com-

mutative algebra on the graded ℚ–vector space C_{∗}(n) := ⨁_{q=0}^{n} C_{q}(n) such that at the

same time C_{∗}(n) becomes an Artinian local ring.

We provide an example for the computation of H (n − q, q)^{−1}:

• Assume n odd and q = ⌊\frac{n}{2}⌋ + 1. Then one has

H (q − 1, q)^{−1} = ∑_{j=1}^{q} \frac{(−1)^{j+1}}{j} · H (q − j, q)^{T} ∘ H (q − j, q − 1).

There is the following generalization:

•• Assume q ≤ \frac{n}{2} if n is even or q ≤ ⌊\frac{n}{2}⌋ + 1 if n is odd. Then the mapping

K (q, q − 1) : C_{q−1}(n) ⟶ C_{q}(n)

defined by

K (q, q − 1) = ∑_{j=1}^{q} \frac{(−1)^{j+1}}{j} \binom{n − 2q + j + 1}{j}^{−1} · H (q − j, q)^{T} ∘ H (q − j, q − 1)

is a right inverse of H (q − 1, q).

2. One defines the structure of a commutative ℚ–algebra on C_{∗}(n) = ⨁_{q=0}^{n} C_{q}(n) by

setting for subsets M, N of \underline{\underline{n}}

[M] · [N] = \{ \begin{matrix}[M ∪ N], & if M ∩ N = ∅, \\ 0, & otherwise. \end{matrix}

This ℚ–algebra which we denote by ℭ_{∗}(n) is isomorphic to

A (n) := ℚ [T_{1}, …, T_{n}]/(T_{1}^{2}, T_{2}^{2}, …, T_{n}^{2}) = ℚ [X_{1}, …, X_{n}],

where T_{1}, …, T_{n} are algebraically independent elements and X_{j} = T_{j} mod (T_{1}^{2}, …, T_{n}^{2}). The isomorphism C_{∗}(n) ⟶ A (n) is induced by

\begin{matrix}[M] = [\{j_{1}, …, j_{q}\}] & ⟶ & X_{j_{1}}X_{j_{2}} · . . . · X_{j_{q}}, if |M| = q ≥ 1, \\ [∅] & ⟶ & 1 ∈ ℚ. \end{matrix}

In the sequel we identify ℭ_{∗}(n) and A (n).

Let ℭ_{∗}(n)_{p} denote the ℚ–module of the elements of degree p of the graded algebra ℭ_{∗}(n). Then one has

ℭ_{∗}(n)_{p} = \{ \begin{matrix}C_{p}(n), & 0 ≤ p ≤ n, \\ 0, & p > n. \end{matrix}

To the mappings H (q − 1, q), 0 ≤ q ≤ n, corresponds the map △ : ℭ_{∗}(n) ⟶ ℭ_{∗}(n) of degree −1 defined by

\begin{aligned}△|_{ℚ} = 0, △X_{j} & = & 1, j ∈ \underline{\underline{n}}, \\ △ (X_{j_{1}} · X_{j_{2}} · . . . · X_{j_{q}}) & = & ∑_{k=1}^{q} X_{j_{1}} · . . . · X̂_{j_{k}} · . . . · X_{j_{q}}, 2 ≤ q ≤ n, \end{aligned}

(1 ≤ j_{1} < j_{2} < … < j_{q} ≤ n, denotes the deleting operator).

Finally we define 𝕏 = ∑_{j=1}^{q} X_{j}.

Proposition 1. Assume 0 ≤ t ≤ q ≤ n. Then with the agreement △^{∘} = id, 𝕏^{∘} = 1 the following identities hold

\begin{aligned}(q − t)! · H (t, q) & = & △^{q−t}|_{C_{q}(n)}, \\ (q − t)! H (t, q)^{T} (w) & = & 𝕏^{q−t} · w, w ∈ C_{t}(n). \end{aligned}

Proof. To prove the first statement we show by induction with respect to m, 0 ≤ m ≤ q, that the identity

(1) …  △^{m}|_{C_{q}(n)} = m! H (q − m, q)

holds. Of course, this is true for m = 0, 1. Assume this identity has been proved already in case m − 1 ≥ 1. The following relation is well known in case 0 ≤ s ≤ t ≤ q

(1) …  H (s, t) ∘ H (t, q) = \binom{q − s}{t − s} H (s, q)

(see for example [2], Chapt 15, Lemma 8.1). Therefore one has

△^{m}|_{C_{q}(n)} = △|_{C_{q−m+1}(n)} ∘ △^{m−1}|_{C_{q}(n)}
= H (q − m, q − m + 1) · (m − 1)!H (q − m + 1, q)
= m · (m − 1)! · H (q − m, q) = m! H (q − m, q). −

To prove the second statement we show by induction with respect to m ≥ 0, t + m ≤ n, that for w ∈ C_{t}(n) the following relation holds

𝕏^{m} · w = m! H (t, t + m)^{T} (w).

It is sufficient for our purpose to take w as an element X_{j_{1}} ·. . .·X_{j_{t}} of the “canonical” basis of C_{t}(n). The claim is evident in case m = 0; moreover one has

𝕏w = ∑_{k≠j_{1},j_{2},... ,j_{t}}^{k} X_{j_{1}}X_{j_{2}} · . . . · X_{j_{t}} · X_{k} = H (t, t + 1)^{T} (w).

Assume that the statement has already been proved in case m−1 ≥ 0. By transposing one gets from Eq (1)

H (t, t + m)^{T} = m · H (t + 1, t + m)^{T} ∘ H (t, t + 1)^{T} ,

Therefore according to the induction hypothesis (applied to 𝕏w ∈ C_{t+1}(n))

\begin{aligned}𝕏^{m}w = 𝕏^{m−1} · 𝕏w & = (m − 1)! H (t + 1, t + m)^{T} ∘ H (t, t + 1)^{T} (w) \\ & = m! H (t, t + m)^{T} (w). \end{aligned}

Suppose w ∈ ℭ_{∗}(n). Then we define the “foundation” of w (in signs Fund (w)) to be the product of all X_{j} which appear in the basis decomposition of w with a coefficient unequal to zero. For example one has with pairwise distinct X_{j_{1}}, X_{j_{2}}, …, X_{j_{2t}}

Fund ((X_{j_{1}} − X_{j_{2}})(X_{j_{3}} − X_{j_{4}}) · . . . · (X_{j_{2t−1}} − X_{j_{2t}})) = ∏_{k=1}^{2t} X_{j_{k}}.

In a self–explaining manner we can treat the foundation also as a subset of \underline{\underline{n}}.

Proposition 2. i) Assume v, w ∈ ℭ_{∗}(n) and Fund (v) ∩ Fund (w) = ∅.

Then we have that

△ (vw) = v△ (w) + w△ (v).

ii) Denote ℤ = ∑_{k=1}^{p} X_{j_{k}}, the X_{j_{k}} pairwise distinct. Assume 1 ≤ m ≤ p (and put

ℤ^{0} = 1). Then we have that

△ (ℤ^{m}) = m (p − m + 1)ℤ^{m−1}.

Proof. Ad i) Assume in the first instance v = X_{i_{1}} · . . . · X_{i_{s}}, w = X_{j_{1}} · . . . · X_{j_{t}} are elements from a basis of ℭ_{∗}(n). According to hypothesis one has

|{i_{1}, …, i_{s}, j_{1}, …, j_{t}}| = s + t.

Therefore

△ (vw) = ∑_{k=1}^{s} X_{i_{1}} · . . . · X̂_{i_{k}} · . . . · X_{i_{s}} · X_{j_{1}} · . . . · X_{j_{t}}

+ ∑_{l=1}^{t} X_{i_{1}} · . . . · X_{i_{s}} · X_{j_{1}} · . . . · X̂_{j_{l}} · . . . · X_{j_{t}}

= w△ (v) + v△ (w).

The general case follows now from the law of distributivity.

Ad ii) Without loss of generality assume ℤ = ∑_{j=1}^{p} X_{j}. Then we have

(2) …  ℤ^{k} = \{ \begin{matrix}k! ∑_{1≤j_{1}<...<j_{k}≤p} X_{j_{1}} · . . . · X_{j_{k}}, & 1 ≤ k ≤ p, \\ 0, & k > p. \end{matrix}

In this sum a term X_{i_{1}} · . . . · X_{i_{m−1}}, (1 ≤ i_{1} < … < i_{m−1} ≤ p) occurs exactly in the terms △ (X_{i_{1}} · . . . · X_{i_{m−1}} · X_{t}), t ∈ \underline{\underline{p}}\\{i_{1}, …, i_{m−1}\} with factor 1; therefore it occurs in △ (ℤ^{m}) with factor m!(p − m + 1) = m (p − m + 1)(m − 1)!. The conclusion follows now from equation (2).

We remark that △ is no derivation of ℭ_{∗}(n).

Let 𝔪 := (X_{1}, …, X_{n}) denote the maximal ideal of ℭ_{∗}(n). Then it holds that 𝔪^{n+1} = 0. If 𝔭 is a prime ideal of ℭ_{∗}(n), then from 𝔪^{n+1} ⊆ 𝔭 one concludes 𝔪 = 𝔭. Therefore ℭ_{∗}(n) is an Artinian local ring. Let ˜△ denote a derivation of ℭ_{∗}(n) (into itself). Then it must hold for all j ∈ \underline{\underline{n}} that

0 = ˜△ (X_{j}^{2}) = 2X_{j} ˜△ (X_{j}),

therefore ˜△ (X_{j}) ∈ 𝔪. – So ˜△ maps 𝔪 (and ℭ_{∗}(n), too) into 𝔪 (compare with [4], §1, Exercise 4).

Now we extend Prop.2, ii):

Proposition 3. Assume 0 ≤ s ≤ n − 1, α ∈ ℕ, α + s ≤ n and w ∈ C_{s}(n). Then the following identity holds:

△ (𝕏^{α} · w) = 𝕏^{α} · △ (w) + α (n − α − 2s + 1)𝕏^{α−1} · w.

Proof. In case s = 0 the statement is true according to Prop. 2, ii). Assume now s ≥ 1 and take

w = X_{j_{1}} · . . . · X_{j_{s}}

as a basis element of C_{s}(n). One defines

𝕐 = ∑_{k=1}^{s} X_{j_{k}}, ℤ = 𝕏 − 𝕐.

Since w is a word in all X_{j_{1}}, …, X_{j_{s}} one has 𝕐 · w = 0. Assume t ≥ 0. Then the following holds

𝕏^{t}w = (𝕐 + ℤ)^{t} · w = ∑_{r=0}^{t} \binom{t}{r}ℤ^{r}𝕐^{t−r} · w = ℤ^{t}w,

furthermore according to the definition of 𝕐 and ℤ Fund (w) ∩ Fund (ℤ^{t}) = ∅; from Prop. 2 one concludes

(3) …  \{ \begin{matrix}△ (𝕏^{α} · w) & = △ (ℤ^{α} · w) = ℤ^{α} · △ (w) + w · △ (ℤ^{α}) \\ & = ℤ^{α} · △ (w) + α (n − s − α + 1) ℤ^{α−1}w \\ & = ℤ^{α} · △ (w) + α (n − s − α + 1) 𝕏^{α−1}w. \end{matrix}

Now we use

𝕐^{t} · △ (w) = \{ \begin{matrix}0, & t > 1, \\ s · w, & t = 1. \end{matrix}

Therefore

\begin{aligned}𝕏^{α}△ (w) & = (∑_{r=0}^{α} \binom{α}{r}𝕐^{r}ℤ^{α−r}) · △ (w) = (α𝕐 · ℤ^{α−1} + ℤ^{α}) · △ (w) \\ & = αsℤ^{α−1} w + ℤ^{α} · △ (w) = α · s · 𝕏^{α−1}w + ℤ^{α} · △ (w). \end{aligned}

Replacing the term ℤ^{α}△ (w) in Eq. (3) yields

△ (𝕏^{α}w) = 𝕏^{α} · △ (w) + α (n − 2s − α + 1) 𝕏^{α−1} · w,

as claimed. –

Prop. 3 is a special case of Proposition 4. The same assumptions about s, α are in force as in Prop. 3. Assume r ∈ ℝ and k ∈ ℕ and define

[r]_{k} = r (r − 1) · (r − 2) · . . . · (r − k + 1), [r]_{0} = 1.

Let β be a non–negative integer and assume 0 ≤ β ≤ α. Then the following identity holds

△^{β}(𝕏^{α} · w) = ∑_{k=0}^{β} \binom{β}{k}[α]_{k}[n − α − 2s + β]_{k} · 𝕏^{α−k} · △^{β−k}(w).

Proof. There is nothing to prove in case β = 0; in case β = 1 the claim boils down to Prop. 3. If 0 ≤ j ≤ β we put

[β, j] = 𝕏^{α−j} · △^{β−j}(w)

and prove first of all by induction with respect to β ≥ 1, that the identity

(4) …  △^{β}(𝕏^{α}w) = ∑_{j=0}^{β} c (β, j) · [β, j], c (β, j) ∈ ℚ,

holds; furthermore this will yield recursion formulas for the coefficients c (β, j). In case β = 1 one has according to Prop. 3

c (1, 0) = 1, c (1, 1) = α (n − α − 2s + 1) =: λ (α, s).

Since △^{k−j}(w) ∈ C_{s−k+j}(n), Prop. 3 now yields

△ ([k, j]) = △(𝕏^{α−j} · △^{k−j}(w)) =

= 𝕏^{α−j} · △^{k−j+1}(w) + (α − j) · (n − (α − j) − 2(s − k + j) + 1) · 𝕏^{α−j−1} · △^{k−j}(w) =

= 𝕏^{α−j} · △^{k−j+1}(w) + λ (α − j, s − k + j) · 𝕏^{α−j−1} · △^{k−j}(w),

that is

△ ([k, j]) = [k + 1, j] + λ(α − j, s − k + j)[k + 1, j + 1].

According to the induction hypothesis we obtain

△^{β+1}(𝕏^{α}w) = △ (△^{β}(𝕏^{α} · w)) =
c (β, 0)[β + 1, 0] + ∑_{j=1}^{β}{c (β, j) + c (β, j − 1) · λ (α − j + 1, s − β + j − 1)} · [β + 1, j]
+λ (α − β, s) · c (β, β)[β + 1, β + 1],

which proves Eq. (4); at the same time we have proved the following recursion formulas

(5.1) …  c (β + 1, 0) = c (β, 0), c (β + 1, β + 1) = λ (α − β, s) c (β, β),

(5.2) … c (β + 1, j) = c (β, j) + λ (α − j + 1, s − β + j − 1) · c (β, j − 1), (1 ≤ j ≤ β).

Eq. (5.1) yields immediately

(6) …  \{ \begin{matrix}c (β, 0) = 1 \\ & (0 ≤ β ≤ α). \\ c (β, β) = [α]_{β}[n − α − 2s + β]_{β} \end{matrix}

Now we claim that the following holds in case β ≥ j

(7) …  c (β, j) = \binom{β}{j}[α]_{j}[n − α − 2s + β]_{j}

which we prove by induction with respect to the pairs (β, j), β ≥ j. The claim is true for pairs (β, 0) according to Eq. (6). Assume that it has already been proved that in case j ≥ 1 the claim is true for all pairs (γ, j − 1), γ ≥ j − 1. We rewrite a term in the recursion formula (5.2)

λ (α − j + 1, s − β + j − 1) = (α − j + 1)(n − α − 2s + 2β − j + 2).

Now we proceed by induction with respect to β, β ≥ j. In case β = j the statement is true according to Eq. (6). Assume that the statement has already be proved for some β ≥ j. Then we have according to Eq. (5.2)

\begin{aligned}c (β + 1, j) = & \binom{β}{j}[α]_{j}[n − α − 2s + j]_{j} + \\ & +(n − α − 2s + 2β − j + 2) · \binom{β}{j−1}[α]_{j}[n − α − 2s + β]_{j−1}. \end{aligned}

Using the identities \binom{β}{j} = \binom{β}{j−1} · \frac{β − j + 1}{j} and \binom{β}{j} + \binom{β}{j−1} = \binom{β+1}{j} we conclude

c (β + 1, j) = [α]_{j}[n − α + 2s + β]_{j−1} · \{\binom{β+1}{j}(n − α − 2s) + \binom{β}{j}(β − j + 1)+
+\binom{β}{j−1}(2β − j + 2)\}
= [α]_{j}[n − α − 2s + β]_{j−1} · \binom{β+1}{j}(n − α − 2s + β + 1)
= \binom{β+1}{j}[α]_{j}[n − α − 2s + (β + 1)]_{j}

This proves Eq. (7). – 3. Assume now 0 ≤ t ≤ q ≤ n and \binom{n}{t} ≤ \binom{n}{q}. We denote ∇ := △^{q−t} : C_{q}(n) ⟶ C_{t}(n) and fix some w ∈ C_{t}(n). Our aim is to construct explicitely a primage u ∈ C_{q}(n) of w with respect to ∇. Therefore we make the following ansatz (we will see later that this method will work): If 0 ≤ j ≤ t we denote

U_{j} := 𝕏^{q−t+j} · △^{j}(w)

and put

u = ∑_{j=0}^{t} x_{j}U_{j}

where the x_{j} ∈ ℚ have to be determined. To compute ∇U_{j} apply Prop. 4 (replace here w by △^{j}(w) ∈ C_{t−j}(n)) and obtain with the convention

(8) … c (k, j) := \binom{q − t}{k}[q − t + j]_{k} · [n − 2t + j]_{k}, (0 ≤ j ≤ t, 0 ≤ k ≤ q − t)

∇U_{j} = ∑_{k=0}^{q−t} c (k, j) · 𝕏^{q−t+j−k} · △^{q−t+j−k}(w) ∈ C_{t}(n),

therefore

(9) …  ∇u = ∑_{k=0}^{q−t} ∑_{j=0}^{t} x_{j}c (k, j) · 𝕏^{q−t+j−k} · △^{q−t+j−k}(w).

We order the right hand side of this equation with respect to the terms

V_{m} := 𝕏^{m} · △^{m}(w), 0 ≤ m ≤ t,

by defining

V_{k,j} = 𝕏^{q−t+j−k} · △^{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 ≤ l ≤ min{m, q − t}. Therefore Eq. (9) yields now

∇u = ∑_{m=0}^{t} d_{m}V_{m}

with

(10) …  d_{m} = ∑_{l=0}^{min{m,q−t}} c ((q − t) − l, m − l) · x_{m−l}.

We observe that V_{0} = w. – So u is in fact a preimage, if the system of linear equations in the unknowns x_{0}, …, x_{t}

\begin{matrix}d_{0} = 1, \\ d_{m} = 0, 1 ≤ m ≤ t, \end{matrix}

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 ≤ m ≤ t,

(and the system has the solution x_{0} = 1, x_{1} = x_{2} = … = 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 ≤ n, therefore f_{m} ≥ m + 2. So our ansatz has worked and we have proved

Theorem 1. Assume 0 ≤ t ≤ q ≤ n and \binom{n}{t} ≤ \binom{n}{q}. Then the mapping

∇ := △^{q−t} : C_{q}(n) ⟶ C_{t}(n)

is surjektiv. There exist x_{0}, x_{1}, …, x_{t} ∈ ℚ such that the mapping

∇^{[−1]} := ∑_{j=0}^{t} x_{j} · 𝕏^{q−t+j} · △^{j}|_{C_{t}(n)}

is a right inverse with respect to ∇ (in case \binom{n}{t} = \binom{n}{q} ∇^{[−1]} is the inverse of ∇).

If one denotes in case 0 ≤ k ≤ q − t, 0 ≤ j ≤ t,

c (k, j) := \binom{q − t}{k} · [q − t + j]_{k} · [n − 2t + j]_{k},

then one can choose the x_{0}, …, x_{t} as the (existing) solution of the system of linear equations

\begin{matrix}c (q − t, 0) · x_{0} = 1, \\ ∑_{l=0}^{min\{m,q−t\}} c ((q − t) − l, m − l) · x_{m−l} = 0, 1 ≤ m ≤ t. \end{matrix}

Corollary 1. If one defines

y_{j} = (q − t)!j!(q − t + j)! · x_{j}, 0 ≤ j ≤ t,

then the mapping K (q, t) : C_{t}(n) ⟶ C_{q}(n) defined by

K (q, t) := ∑_{j=0}^{t} y_{j} · H (t − j, q)^{T} ∘ H (t − j, t)

is a right inverse of H (t, q).

Proof (of the corollary). According to Prop. 1 one has

∇ = (q − t)! · H (t, q)

and

𝕏^{q−t+j} · △^{j}|_{C_{t}(n)} = (q − t + j)!j! · H (t − j, q)^{T} ∘ H (t − j, t). □

Now we exploit the the theorem and the corollary. The following result is properly spoken another corollary; however, we state it as

Theorem 2. Assume 0 ≤ t < q ≤ n and t + q = n. Then the following identity holds:

H (t, q)^{−1} = ∑_{j=0}^{t}(−1)^{j} \frac{q − t}{q − t + j} H (t − j, q)^{T} ∘ H (t − j, t).

Proof. We introduce a new parameter p = q − t. Then we obtain n − 2t = p and

c (k, j) = \binom{p}{k} · ([p + j]_{k})^{2}.

We switch now to new indeterminates α_{j} in the system of linear equations of the Theorem by defining

x_{j} = (−1)^{j} \frac{α_{j}}{((p + j)!)^{2}} , α_{j} ∈ ℚ.

An elementary computation which we omit yields

α_{0} = 1

and the following recursion formula

α_{j} = ∑_{l=1}^{min\{p,j\}}(−1)^{l+1}\binom{p}{l}α_{j−l}, 1 ≤ j ≤ t.

We compute the α_{j} by elementary difference calculus; let us define therefore functions

f_{p} : ℕ_{0} ⟶ ℚ

by the following conditions

(11) …  \{ \begin{matrix}f_{p}(0) = 1, \\ f_{p}(j) = ∑_{l=1}^{min\{p,j\}}(−1)^{l+1}\binom{p}{l}f_{p}(j − l), 1 ≤ j. \end{matrix}

Then we claim

(12) …  f_{p}(j) = \binom{j + p − 1}{p − 1}.

In order to prove Eq. (12) we need the following

Lemma. Assume p ≥ 1 and 0 ≤ l ≤ p. Then the following identity holds

\binom{p}{l} − \binom{p}{l − 1} + \binom{p}{l − 2} ∓ … + (−1)^{l}\binom{p}{0} = \binom{p − 1}{l}.

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. □

Denote by △f_{p} the first difference series of f_{p}, that is

(△f_{p})(j) = f_{p}(j + 1) − f_{p}(j), j ∈ ℕ_{0}.

Then we have by placing f_{p}(k) = α_{k} and h = min{p, j}, in case j ≥ 1

\begin{aligned}α_{j+1} − α_{j} & = [\binom{p}{1} − \binom{p}{0}] · (α_{j} − α_{j−1}) − [\binom{p}{2} − \binom{p}{1} + \binom{p}{0}] (α_{j−1} − α_{j−2}) ± … \\ & +(−1)^{h+1} [\binom{p}{h} − \binom{p}{h−1} + \binom{p}{h−2} ∓ … + (−1)^{h}\binom{p}{0}] · (α_{j−h+1} − α_{j−h}). \end{aligned}

According to the lemma this rewrites to

(△f_{p})(j) = ∑_{l=1}^{min\{j,p\}}(−1)^{l+1}\binom{p − 1}{l}(△f_{p})(j − l), j ≥ 1.

Furthermore we have

(△f_{p})(0) = p − 1 = f_{p−1}(1), p ≥ 2.

This yields in case p ≥ 2

(13) …  (△f_{p})(j) = f_{p−1}(j + 1), j ∈ ℕ_{0},

since △f_{p} satisfies the same recursion formula (see Eq. (12)) as f_{p−1} does.

Now Eq. (12) is certainly true if p = 1. Assume our claim is true if p − 1 ≥ 1. Then according to Eq. (13) we have

(△f_{p})(j) = \binom{j + p − 1}{p − 2}, j ∈ ℕ_{0}.

Therefore the function F : ℕ_{0} → ℚ defined by

F (j) = \binom{j + p − 1}{p − 1}

is a discrete indefinite integral of △f_{p}; that is △F = △f_{p}. It follows that

F = f_{p} + const,

but F (0) = f_{p}(0), so we have F = f_{p}. Therefore the claim Eq. (12) is proved. 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. □ To exploit Theorem 1 and the corollary in the case \binom{n}{t} ≤ \binom{n}{q}, we restrict ourselves to the condition q − t = 1. We then have q ≤ \frac{n}{2} if n is even and q ≤ ⌊\frac{n}{2}⌋ + 1 if n is odd. Here we have under the assumption 0 ≤ j ≤ t = q − 1

\begin{aligned}c (0, j) & = & 1, \\ c (1, j) & = & (j + 1)(n − 2q + j + 2). \end{aligned}

We obtain the following system of linear equations in the unknowns x_{0}, …, x_{t}

\begin{aligned}c (1, 0) x_{0} & = & 1, \\ c (1, j) x_{j} + x_{j−1} & = & 0, 1 ≤ j ≤ t, \end{aligned}

which has the solution

x_{j} = \frac{(−1)^{j}}{(j + 1)![n − 2q + j + 2]_{j+1}} , 0 ≤ j ≤ t.

Again with the notations of the corollary to Theorem 1 we obtain

y_{j} = j! (j + 1)! x_{j} = \frac{(−1)^{j}}{j + 1} · \binom{n − 2q + j + 2}{j + 1}^{−1}.

Now we change the indices from j +1 to j and obtain the statement of example •• . 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}} · X_{j_{2}}) =

\begin{aligned}\frac{1}{6}[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}}+ \\ & +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}})], \end{aligned}

and conclude that the matrix H (2, 3)^{−1} is “non–sparse”.

4. Finally we demonstrate the usefulness (as we hope) of the algebra ℭ_{∗}(n) by giving new proofs or extending, respectively, some results in [2].

• • • (l.c., 3.3) Let v ∈ Ker △, w ∈ C_{t}(n), such that Fund (v) ∩ Fund (w) = ∅. Then it holds that △^{t+1}(v · w) = 0.

This is an immidediate consequence of the property of △ to be a “quasi–derivation” (see Prop. 2).

Secondly, we exhibit a system of generators of Ker H (t, q) provided \binom{n}{t} < \binom{n}{q}.

We denote K_{q}(n) = Ker △|_{C_{q}(n)}. Then obviosly one has K_{q}(n − 1) ⊂ K_{q}(n). To

determine remaining candidates u of K_{q}(n) we make the following ansatz

(14) . . ..  u = vX_{n} + w, v ∈ C_{q−1}(n − 1), w ∈ C_{q}(n − 1).

Since Fund (v) ∩ Fund (X_{n}) = ∅, Prop. 2, i) yields

0 = △u = (△v) · X_{n} + (v + △w),

therefore

(15) …  △v = 0, v + △w = 0.

Assume now that is has been proved by induction with respect to s that K_{t}(s), t ≤ ⌊\frac{s}{2}⌋, s ≤ n − 1, is generated by elements of the shape

(X_{j_{1}} − X_{j_{2}})(X_{j_{3}} − X_{j_{4}}) · . . . · (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}}) · . . . · (X_{j_{2(q−1)−1}} − X_{j_{2(q−1)}}).

There are two cases to be considered. In the first case assume 2 (q − 1) = n − 1; then we have n odd, q = ⌊\frac{n}{2}⌋ + 1. According to • K_{q}(n) = 0 and then there is no more to prove.

In the second case assume 2 (q − 1) < n − 1. Then there exists X_{j}, j ≤ n − 1 such that Fund (v) ∩ {X_{j}} = ∅. We conclude that

w := −v · X_{j}

solves the second equation in Eq. (15); furthermore one has u = v (X_{n} − X_{j}).

This proves

••• • (contained in l.c., 4.2) Assume q ≤ ⌊\frac{n}{2}⌋. Then it holds that Ker H (q−1, q) ≠ 0 and this kernel is generated by elements of the shape

(X_{j_{1}} − X_{j_{2}})(X_{j_{3}} − X_{j_{4}}) · . . . · (X_{j_{2q−1}} − X_{j_{2q}}).

In as subsequent paper (in which we use the algebra ℭ_{∗}(n) to exhibit explicitely eigenspace decompositions of the matrix H (t, q)^{T} ∘ H (t, q)) we will show

Theorem 3. Assume \binom{n}{t} < \binom{n}{q}. Then it holds that

Ker H (t, q) = ⨁_{s=t+1}^{min{q,n−q}} H (s, t)^{T} (Ker H (s − 1, s)).

This result provides together with • • • • systems of generators of Ker H (t, q) which are in general distinct from those which are exhibited in [2].

With the aid of Theorem 3 (and Prop. 4) one easily proves

• • • • • (l.c., 4.3) Assume 0 ≤ t < q < n − t. Then H (t + 1, q) maps the kernel of H (t, q) onto the kernel of H (t, t + 1).

Finally we exhibit in a special case a system of generators of Ker H (q − 1, q) which is different from the ”canonical” one constructed above as follows:

Assume n = 7, q = 3. Any enumeration σ of the points of the projective plane ℙ consisting of 7 points and 7 lines yields the family 𝔊_{σ} ⊂ \binom{\underline{\underline{7}}}{3} consisting of the lines of ℙ. We claim that the elements

u_{σ} := 4 · ∑_{M∈𝔊_{σ}}[M] − ∑_{M∉𝔊_{σ}}^{|M|=3}[M]

also generate Ker H (2, 3).

First, we sketch a proof that the u_{σ} indeed are contained in the kernel of H (2, 3) as follows: Define for q ∈ \underline{\underline{n}}

H_{q} := H (q − 1, q)^{T} ∘ H (q − 1, q) : C_{q} (n) ⟶ C_{q} (n).

Then it holds, if [M] is an element of the canonical basis of C_{q}(n),

(16) …  H_{q}([M]) = q · [M] + ∑_{|M∩M′|=q−1}^{|M′|=q}[M′].

Now it can be seen easily that

w_{q} := ∑_{|M|=q}^{M}[M]

is an eigenvector of H_{q} with eigenvalue q (n − q + 1). In addition we need the well known result (see for instance [1], Chapt. II, 2.5 Lemma), that

rang H (t, q) = rang H (t, q)^{T} ∘ H (t, q) (= rang H (t, q) ∘ H (t, q)^{T} ),

which yields

Ker H (t, q) = Ker (H (t, q)^{T} ∘ H (t, q)).

After this digression suppose now again n = 7, q = 3, t = 2. Since two different projective lines intersect in one point we have |M_{1} ∩ M_{2}| = 1 provided M_{1}, M_{2} ∈ 𝔊_{σ} and M_{1} ≠ M_{2}. This in turn yields according to Eq. (16):

H_{3} ( ∑_{M∈𝔊_{σ}}[M]) = 3 · ∑_{M∈𝔊_{σ}}[M] + ∑_{M′∉𝔊_{σ}}^{|M′|=3} λ_{M′}[M′].

The coefficients λ_{M′} ∈ ℚ are determined as follows: Any M′ ∉ 𝔊_{σ} consists of three non–collinear points; therefore for given M′ there are exactly three M ∈ 𝔊_{σ} such that |M′ ∩ M| = 2. We conclude λ_{M′} = 3, in turn

H_{3} ( ∑_{M∈𝔊_{σ}}[M]) = 3 · w_{3} = H_{3} (\frac{1}{5}w_{3}) ,

that is

∑_{M∈𝔊_{σ}}[M] − \frac{1}{5}w_{3} ∈ Ker (H (2, 3)^{T} ∘ H (2, 3)) = Ker H (2, 3).−

Secondly, assume that v is an element of the ”canonical” system of generators of Ker H (2, 3), say

v = (X_{1} − X_{2})(X_{3} − X_{4})(X_{5} − X_{6}).

Suppose the enumerations τ, τ′ of the points of ℙ are given by

[figure: 5; 7; 6; 4; 3; 1; 2; τ; 3; 4; 7; 5; 1; 6; 2; τ′]

Then a lengthy but elementary computation which we omit yields

v = \frac{1}{5} (u_{τ} − u_{τ′}).

We conclude that the u_{σ} generate Ker H (2, 3), too.

Acknowledgement The author is indebted to the referee for helpful comments.

References

[1] Th. Beth, D. Jungnickel und H. Lenz: Design Theory.

Mannheim / Wien / Zürich 1985 (BI–Wissenschaftsverlag)

[2] C.D. Godsil: Algebraic Combinatorics. New York / London 1993 (Chapman & Hall)

[3] J.B. Graver und W.B. Jurkat: The module structure of integral designs. Journal of Combinatorial Theory, A 15 (1973), 75–90.

[4] E. Kunz: Kähler Differentials. Braunschweig 1986 (Vieweg)