Eigenspace Decompositions with Respect to Symmetrized Incidence Mappings

Helmut Krämer

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

Abstract

Let 𝕂 denote one of the fields ℚ, 𝔽_{2} and define H (t, q), t ≤ q, to be the 𝕂–incidence matrix of the t–sets vs. 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) (s ≤ n) is the 𝕂–vector space having the s–sets as a basis. The symmetrized 𝕂–incidence matrix (of H (t, q)) is defined to be the symmetric matrix H̃ (t, q) := H (t, q)^{T} · H (t, q) which is also considered as an endomorphism of _{𝕂}C_{q}(n). In case 𝕂 = ℚ we exhibit explicitely a decomposition of _{ℚ}C_{q}(n) into eigenspaces with respect to H̃ (t, q). A closer examination of the proof of this result yields a canonical decomposition of ker H (t, q) (provided \binom{n}{t} < \binom{n}{q}) extending work done by J.B. Graver and W.B. Jurkat.

In case 𝕂 = 𝔽_{2} denote H̃ (q | n) := H̃ (q − 1, q). Then H̃ (q | n) is a projection hence diagonalizable if n is odd (otherwise nilpotent). In both cases the rank of H̃ (q | n) is determined; among other results an explicit decomposition of _{𝔽_{2}}C_{q}(n) into the two eigenspaces with respect to H̃ (q | n) is obtained provided n is odd.

As a basic tool we use the graded commutative 𝕂–algebra

𝕂ℭ_{∗}(n) = 𝕂 [T_{1}, …, T_{n}]/(T_{1}^{2}, T_{2}^{2}, …, T_{n}^{2}).

Here the 𝕂–vector spaces of the elements of degree q of _{𝕂}ℭ_{∗}(n) are isomorphic to _{𝕂}C_{q}(n).

1. We denote for n ∈ ℕ

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

let in additon 𝕂 be a field. Assume 0 ≤ t ≤ q ≤ n. Then H (t, q) denotes the 𝕂–incidence matrix (ι (N, M)). Here M runs through the q–sets of \underline{\underline{n}}, N runs through the t–sets of \underline{\underline{n}} and we define

ι (N, M) = \{ \begin{matrix}1, & N ⊆ M, \\ 0, & otherwise. \end{matrix} (0, 1 ∈ 𝕂).

Let _{𝕂}C_{q}(n) be the ℚ–vector space with basis \{[M]\}_{M∈\binom{\underline{\underline{n}}}{q}}, such that H (t, q) defines a linear mapping

𝕂C_{q}(n) ⟶ _{𝕂}C_{t}(n), [M] ⟶ ∑_{{N, \atop |N|=t}} ι (N, M)[N]

which again is denoted by the same symbol H (t, q). The transposed matrix H (t, q)^{T} defines a linear mapping

𝕂C_{t}(n) ⟶ _{𝕂}C_{q}(n), [N] ⟶ ∑_{{M, \atop |M|=q}} ι (N, M)[M],

which again is denoted by the same symbol H (t, q)^{T}. Finally we define an “augmentation map”

H (−1, 0) : _{𝕂}C_{0}(n) ⟶ 0.

We are dealing here with the “symmetrized incidence mapping” H̃ (t, q). This is defined to be the mapping

H̃ (t, q) := H (t, q)^{T} ∘ H (t, q) : _{𝕂}C_{q}(n) ⟶ _{𝕂}C_{q}(n)

which is already diagonalizable in case 𝕂 = ℚ as we soon will see.

The following proposition is well known.

Proposition 1. We have

H̃ (t, q)([M]) = ∑_{{M′, \atop |M′|=q}} 1 · \binom{|M ∩ M′|}{t} · [M′].

Proof. We have

H̃ (t, q)([M]) = ∑_{{N, \atop |N|=t}} ∑_{{M′, \atop |M′|=q}} ι (N, M) ι (N, M′) · [M′],

in addition

\begin{aligned}∑_{|N|=t}^{N} ι (N, M) · ι (N, M′) & = 1 · #\{N||N| = t, N ⊆ M ∩ M′\} \\ & = 1 · \binom{|M∩M′|}{t}. \end{aligned}

Therefore all entries of the matrix H̃ (t, q) are non–negative in case 𝕂 = ℚ. If 𝔷(M) denotes the row sum of the matrix H̃ (t, q) indexed by the q–set M we have

𝔷(M) = ∑_{{M′, \atop |M′|=q}} \binom{|M ∩ M′|}{t}

and this sum is independent from M; so we denote the constant row sum by 𝔷.

• ([3], Lemma 5.1.1) Suppose A is a real n × n–matrix with non–negative entries and constant row sum k. Then (1, 1, …, 1)^{T} is an eigenvector of A with eigenvalue k. Moreover if μ is another (complex) eigenvalue of A then it holds that

|μ| ≤ k.

Suppose now n > 1. Then k is an eigenvalue of geometric multiplicity 1 if and only if A is irreducible.

The last assertion follows from the so–called Perron–Frobenius–Theory. We note another result which applies to the matrix H̃ (t, q):

•• ([3], Theorem 3.2.1) Suppose that A is a real or complex n × n–matrix. Then A is irreducible if and only if the directed graph D (A) associated to A is strongly connected.

Now if A = H̃ (t, q), t < q, 𝕂 = ℚ, the graph D (A) has \binom{\underline{\underline{n}}}{q} as set of vertices V. If L, M ∈ V then the directed arc (L, M) is in the set E of edges of D (A) if and only if \binom{|L∩M|}{t} ≠ 0, that is |L∩M| ≥ t ist. In this case (M, L) is an arc in D (A), too.

We conclude therefore that D (A) is strongly connected if and only if the corresponding undirected graph is connected. This is indeed the case as can be easily seen as follows: Fix L, M ∈ V. Then there exist q–sets L = L_{1}, L_{2}, …, L_{r} = M with the property

|L_{i} ∩ L_{i+1}| = q − 1 ≥ t, 1 ≤ i ≤ r − 1.

If one denotes the eigenspace of H̃ (t, q) with eigenvalue λ ∈ ℝ by

Eig (H̃ (t, q), λ) ⊂ _{ℝ}C_{q}(n)

then the arguments stated above yield

Eig(H̃ (t, q), 𝔷) = ℝ · ( ∑_{{M, \atop |M|=q}}[M]) .

In the following we make the convention \binom{n}{−1} = 0.

Theorem 1. We assume 𝕂 = ℚ and 0 ≤ t < q ≤ n. Then H̃ (t, q) is diagonalizable (as a mapping of ℚ–vector spaces). More exactly the following holds: In case 0 ≤ s ≤ min{q, n − q} we define

μ (q, t; s) = \binom{q − s}{q − t} · \binom{n − t − s}{q − t}.

1) Assume t ≥ min{q, n − q}. Then we have

i) μ (q, t; 0) > μ (q, t; 1) > … > μ (q, t; min{q, n − q}) > 0 and

ii) Eig (H̃ (t, q), μ (q, t; s)) = H (s, q)^{T} (ker H (s − 1, s)), iii) dim H (s, q)^{T} (ker H (s − 1, s)) = \binom{n}{s} − \binom{n}{s−1}, such that

iv) _{ℚ}C_{q}(n) = ⨁_{s=0}^{min{q,n−q}} H (s, q)^{T} (ker H (s − 1, s))

is a decomposition of _{ℚ}C_{q}(n) into eigenspaces with respect to the endomorphism H̃ (t, q).

2) Assume t < min{q, n − q}. Then we have

i) μ (q, t; 0) > μ (q, t; 1) > … > μ (q, t; t) > 0, μ (q, t; t + 1) = … = μ (q, t; min{q, n − q}) = 0.

In case 0 ≤ s ≤ t we have ii) Eig (H̃ (t, q), μ (q, t; s)) = H (s, q)^{T} (ker H (s − 1, s)), iii) dim H (s, q)^{T} (ker H (s − 1, s)) = \binom{n}{s} − \binom{n}{s−1}. Furthermore it holds that iv) Eig (H̃ (t, q), 0) = ker H (t, q),

v) dim ker H (t, q) = \binom{n}{q} − \binom{n}{t}, such that

vi) _{ℚ}C_{q}(n) = (⨁_{s=0}^{t} H (s, q)^{T} (ker H (s − 1, s))) ⊕ ker H (t, q)

is a decomposition of _{ℚ}C_{q}(n) into eigenspaces with respect to the endomorphism H̃ (t, q).

Corollary 1. We assume q + t = n. Then the following identity holds

|det H (t, q)| = ∏_{s=0}^{t−1} \binom{q − s}{q − t}^{\binom{n}{s}−\binom{n}{s−1}}.

This statement can also be derived from [7], Theorem 2.

2. For the proof of the theorem we make use of a graded 𝕂–algebra which was essentially introduced in the previous paper [6]. We denote this algebra by _{𝕂}ℭ_{∗}(n). It is defined by

𝕂ℭ_{∗}(n) = 𝕂 [T_{1}, …, T_{n}]/(T_{1}^{2}, …, T_{n}^{2}) = 𝕂 [X_{1}, …, X_{n}],

here T_{1}, …, T_{n} are algebraically independent elements and X_{j} denotes the residue–class T_{j}mod(T_{1}^{2}, …, T_{n}^{2}), j ∈ \underline{\underline{n}}. This algebra will be used in the sequel in the cases 𝕂 = ℚ and 𝕂 = ℤ/2ℤ = 𝔽_{2}. Let _{𝕂}ℭ_{∗}(n)_{p} denote the 𝕂–vector space of the elements of degree p in this algebra; then we have that

𝕂ℭ_{∗}(n)_{p} = 0, p > n,

and

𝕂ℭ_{∗}(n)_{p} ≅ _{𝕂}C_{p}(n), 0 ≤ p ≤ n.

The isomorphisms under consideration are induced by the mappings

\begin{matrix}𝕂 ∋ 1 & ⟶ & [ ∅], \\ X_{j_{1}} · X_{j_{2}} · . . . · X_{j_{p}} & ⟶ & [\{j_{1}, j_{2}, …, j_{p}\}], \end{matrix}

(1 ≤ j_{1} < j_{2} < … < j_{p} ≤ n).

In case 0 ≤ q ≤ n we will identify the spaces _{𝕂}ℭ_{∗}(n)_{q} and _{𝕂}C_{q}(n). – To the incidence mappings H (q − 1, q), 0 ≤ q ≤ n, corresponds the 𝕂–linear map Δ of _{𝕂}ℭ_{∗}(n) with degree –1 induced by

\begin{matrix}Δ|_{ℚ} = 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{matrix}

where we assume that the X_{j_{k}} are pairwise distinct and denotes the deletion operator.

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

Proposition 2. We agree upon Δ^{∘} = id, 𝕏^{∘} = 1. Then we have

i) in case 𝕂 = ℚ

\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}

ii) in case 𝕂 = 𝔽_{2}

\begin{matrix}Δ^{2} = 0, 𝕏^{2} = 0, \\ H (t, t + 1)^{T} (w) = 𝕏 · w, w ∈ C_{t}(n), 0 ≤ t ≤ n − 1. \end{matrix}

Proof. For the proof of i) we refer to [6], Proposition 1. –

In the second statement it is obvious that Δ^{2} vanishes on the vectorspace 𝔽_{2}C_{1}(n). In case 2 ≤ q ≤ n we rewrite

Δ (X_{j_{1}} · . . . · X_{j_{q}}) = ∑_{k=1}^{q}(−1)^{k}X_{j_{1}} · . . . · X̂_{j_{k}} · . . . · X_{j_{q}}

and apply a standard argument from simplicial homology. The remaining assertions are obvious.

We remark that ( _{𝔽_{2}}ℭ_{∗}(n), Δ) is isomorphic to a Koszul–complex. We will return to this topic in the last section of this paper.

Let us write w ∈ _{𝕂}ℭ_{∗}(n) as a sum of monomials (with respect to X_{1}, …, X_{n}) with coefficients from 𝕂. Then we have defined in [6] the foundation of w (in signs Fund (w)), to be the product of all X_{j} which appear in this decomposition with non–vanishing coeffients. Sometimes we will identify Fund (w) with a subset of \underline{\underline{n}}. This convention is used in the next proposition.

Proposition 3. Assume v, w ∈ _{𝕂}ℭ_{∗}(n) and Fund (v)∩ Fund (w) = ∅. Then it holds that

Δ (v · w) = wΔ (v) + vΔ (w).

For the proof we refer to [6], Prop. 2. □

Finally we define the “falling factorial”

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

Proposition 4. i) In case 𝕂 = ℚ let α, β be non–negative integers. We assume 0 ≤ s ≤ n − 1, 1 ≤ α, α + s ≤ n, 0 ≤ β ≤ α, and w ∈ _{ℚ}C_{s}(n). Then the following identity holds

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

ii) In case 𝕂 = 𝔽_{2} we assume 0 ≤ s ≤ n − 1 and w ∈ _{𝔽_{2}}C_{s}(n). Then the following identity holds

Δ (𝕏w) = 𝕏 · Δ (w) + (n · 1) · w.

Proof. For the first statement we refer to [6], Prop. 4. The second statement is obvious in case s = 0. Assume now s ≥ 1. Let w̃ ∈ _{ℚ}C_{s}(n) be a sum of monomials (with respect to X_{1}, …, X_{n}) with integer coefficients. Then as we have seen in the first part of the proof it holds that

Δ (𝕏w̃) = 𝕏 · Δ (w̃) + (n − 2s) · w̃.

Reducing this equation modulo 2 now yields the claim.

Proposition 5. ([4], Chapt. 15, Corollary 8.5). We assume 𝕂 = ℚ and s ≤ min{q, n − q}. Then the mapping

H (s, q)^{T} : _{ℚ}C_{s}(n) ⟶ _{ℚ}C_{q}(n)

is injective.

Proof. We use the relation derived in Prop. 4, i) and assume α = β = q − s ≥ 0. Let us rewrite this relation in terms of matrices. The left hand side of the relation is ((q − s)!)^{2} H (s, q) ∘ H (s, q)^{T}; the right hand side is sum of the positive semi–definite matrices

H (2s − q + k, s)^{T} ∘ H (2s − q + k, s), q − 2s ≤ k ≤ q − s,

with non–negative integer coefficients. Also the unit matrix occurs here (take k = q − s) with the coefficient

[q − s]_{q−s} · [n − 2s]_{q−s}

which doesn’t vanish since s ≤ n − q. We conclude that in case s ≤ n − q

H (s, q) ∘ H (s, q)^{T}

is an isomorphism, hence the mapping H (s, q)^{T} is injective.

3. In this section we first come to the proof of Theorem 1.

Ad 1) So assume t ≥ min\{q, n − q\}. Suppose \binom{q−s}{q−t} = 0. This yields

t < s ≤ min{q, n − q},

a contradiction. In the same straightforward manner we conclude that the second factor occuring in μ (q, t; s) doesn’t vanish. Now it is easily seen that the μ (q, t; s), k = 0, 1, …, min {q, n − q} are strictly decreasing. This establishes statement i). – Assume now w ∈ ker Δ = ker H (s − 1, s) ⊂ C_{s}(n). According to Prop. 4 we have that

Δ^{q−t}(𝕏^{q−s}w) = [q − s]_{q−t} · [n − s − t]_{q−t} · 𝕏^{t−s} · w.

We multiply this equation with 𝕏^{q−t} and obtain

(𝕏^{q−t} · Δ^{q−t}) · (𝕏^{q−s}w) = [q − s]_{q−t} · [n − s − t]_{q−t} · 𝕏^{q−s} · w.

Now we use Prop. 2. This yields

\begin{matrix}𝕏^{q−s} · w = (q − s)! H (s, q)^{T} (w), \\ 𝕏^{q−t} · Δ^{q−t}(w) = ((q − t)!)^{2}H̃ (t, q)(w). \end{matrix}

Therefore we have now H̃ (t, q)(H (s, q)^{T} · w) = μ (q, t; s) · (H (s, q)^{T} · w),

and in turn

(1) …  H (s, q)^{T} (ker H (s − 1, s)) ⊆ Eig (H̃ (t, q), μ (q, t; s)).

Since s ≤ min\{q, n − q\} the inequality s ≤ ⌊\frac{n}{2}⌋ holds. Now we use the following Lemma. Assume h, k ∈ \{0, 1, …, n\} and \binom{n}{h} ≤ \binom{n}{k}. Then the mapping H (h, k) : C_{k}(n) ⟶ C_{h}(n) is surjective.

For a proof of the Lemma we refer to [5], 2.3., 2.4. For another independent proof see [6], Theorem 1. □ According to the Lemma we have

dim ker H (s − 1, s) = \binom{n}{s} − \binom{n}{s − 1}.

We now invoke Prop. 5 and obtain

dim H (s, q)^{T} (ker H (s − 1, s)) = \binom{n}{s} − \binom{n}{s − 1}.

Since eigenspaces to different eigenvalues are independent, we conclude

∑_{s=0}^{min{q,n−q}} H (s, q)^{T} (ker H (s − 1, s)) = ⨁_{s=0}^{min{q,n−q}} H (s, q)^{T} (ker H (s − 1, s)),

and this subspace of _{ℚ}C_{q}(n) has the dimension

∑_{s=0}^{min\{q,n−q\}} (\binom{n}{s} − \binom{n}{s − 1}) = \binom{n}{q} = dim _{ℚ}C_{q}(n).

Therefore strict equality must hold in Eq (1). At the same time all other statements are proved. ad 2): The proof of assertion i) is straigthforward. Also, along the same lines as in the corresponding statement in case 1) we conclude

(2) … H (s, q)^{T} (ker H (s − 1, s)) ⊆ Eig(H̃ (t, q), μ (q, t; s)),
0 ≤ s ≤ min {1, n − q},

and

dim H (t, q)^{T} (ker H (s − 1, s)) = \binom{n}{s} − \binom{n}{s − 1}

provided 0 ≤ s ≤ min{q, n − q}. Now we assume t < min{q, n − q} and obtain t + q + 1 ≤ n. This inequality is equivalent to the condition \binom{n}{t} < \binom{n}{q}. According to the Lemma in the first part of the proof H (t, q) is surjective, in turn

dim ker H (t, q) = \binom{n}{q} − \binom{n}{t}.

Obviously it holds that

(3) …  ker H (t, q) ⊆ Eig(H̃ (t, q), 0).−

Now we apply the first half of assertion i) and obtain

∑_{s=0}^{t} H (s, q)^{T} (ker H (s − 1, s)) + ker H (t, q) =
= ⨁_{s=0}^{t} H (s, q)^{T} (ker H (s − 1, s)) ⊕ ker H (t, q).

This subspace of _{ℚ}C_{q}(n) therefore has the dimension

∑_{s=0}^{t} (\binom{n}{s} − \binom{n}{s − 1}) + \binom{n}{q} − \binom{n}{t} = \binom{n}{q} = dim _{ℚ}C_{q}(n).

We conclude that strict equality must hold in Eq (2), (3). At the same time, all other statements have been proved. □

Remarks:

a) We note the particular result

Eig(H̃ (t, q), μ (q, t; 0)) = ℚ · ( ∑_{{M, \atop |M|=q}}[M]) .

This allows us to compute the constant row–sums 𝔷 of H̃ (t, q). We obtain

𝔷 = μ (q, t; 0) = \binom{q}{t} · \binom{n − t}{q − t}.

b) From the second part of the proof we derive

ker H (t, q) = Eig(H̃ (t, q), 0) = ker(H (t, q)^{T} ∘ H (t, q)).

Of course this is also a consequence of the following well–known equality

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

(see for instance [1], Chapt. II, 2.5 Lemma).

Now we turn to the proof of the corollary. Assume first t = q. The claim is trivially true since H̃ (t, q) is the unit matrix. Now assume t < q. Of course

| det H (t, q)| = \sqrt{det H̃ (t, q)},

and det H̃ (t, q) is the product of the eigenvalues counted with the corresponding multiplicities. Since q = n − t, case 1) of the Theorem applies and yields

μ (q, t; s) = \binom{q − s}{q − t}^{2}, 0 ≤ s ≤ t = min \{q, n − q\}. □

Let us once again return to the proof of the Theorem, case 2). We consider the sum

U = ∑_{s=0}^{min{q,n−q}} H (s, q)^{T} (ker H (s − 1, s)).

Our arguments have shown that all subspaces occuring in this sum are subspaces of eigenspaces with respect to H̃ (t, q) but the eigenspaces under consideration do not necessarily have distinct eigenvalues. In fact the last min{q, n − q} − t eigenvalues are zero according to assertion i). So in general we cannot conclude by standard arguments that U is a direct sum. However, this is true as can be seen from our next result which was announced in the previous paper ([6], Theorem 3).

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

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

Proof. Assume t + 1 ≤ s ≤ min{q, n − q} and define

V_{s} := H (s, q)^{T} (ker H (s − 1, s)).

We have already remarked that the condition imposed in Theorem 2 is equivalent to t + q + 1 ≤ n. Now we use the following

Lemma. Assume 0 ≤ s ≤ min{q, n − q} and w_{s} ∈ ker H (s − 1, s). Then we have

Δ^{q−r}(𝕏^{q−s} · w_{s}) = \{ \begin{matrix}α (q, s) · w_{s}, α (q, s) ≠ 0, & if r = s, \\ 0 , & if r < s. \end{matrix}

Proof (of the lemma): From Prop. 4 we derive

\begin{matrix}Δ^{q−s}(𝕏^{q−s} · w_{s}) = α (q, s) · w_{s} \\ α (q, s) = [q − s]_{q−s} · [n − 2s]_{q−s} ≠ 0 \end{matrix}

provided s ≤ min {q, n − q}. Now assume r < s. Then we obtain

Δ^{q−r}(𝕏^{q−s} · w_{s}) = Δ^{s−r}(Δ^{q−s}(𝕏^{q−s} · w_{s})) = Δ^{s−r}(α (q, s) · w_{s}) = 0.
□

Now take r = t in the lemma and apply Prop. 2. Then we have proved anew that V_{s} are contained in ker H (t, q). – Let us show now that the sum

V := ∑_{s=t+1}^{min{q,n−q}} V_{s}

is direct.

We take v ∈ V and write

(4) …  v = ∑_{s=t+1}^{min{q,n−q}} 𝕏^{q−s}w_{s} = 0, w_{s} ∈ ker H (s − 1, s).

In case t + 1 = min{q, n − q}, nothing is to be proved. Otherwise apply Δ^{q−(t+1)} in Eq (4). According to the Lemma we obtain

Δ^{q−(t+1)}(v) = α (q, t + 1) w_{t+1} = 0,

which in turn shows w_{t+1} = 0. Suppose now that it has already be shown that in Eq (4) the following equalities hold

w_{t+1} = w_{t+2} = … = w_{p} = 0, p < min{q, n − q}.

Then we obtain again according to the Lemma

Δ^{q−(p+1)}(v) = α (q, p + 1) · w_{p+1} = 0,

and therefore w_{p+1} = 0. –

We recall from the proof of Theorem 1

dim V_{s} = \binom{n}{s} − \binom{n}{s − 1}.

This in turn implies now

dim V = ∑_{s=t+1}^{min\{q,n−q\}} (\binom{n}{s} − \binom{n}{s − 1}) = \binom{n}{q} − \binom{n}{t} = dim ker H (t, q)

which finishes the proof of the Theorem. □

We recall that the two conditions imposed in Theorem 1, viz “t ≥ min {q, n − q}” and “t < min{q, n − q}”, respectively, are equivalent to the conditions “\binom{n}{t} ≥ \binom{n}{q}” and “\binom{n}{t} < \binom{n}{q}”. In the first case H̃ (t, q) is an isomorphism according to Theorem 1. If we use only [6] in the proof of that theorem, which is possible, then we have proved anew independently from [5], 2.3, 2.4 that H (t, q) is an isomorphism provided \binom{n}{t} ≥ \binom{n}{q}. (Of course this proof is (much) more complicated.) In particular we conclude that ker H(q − 1, q) ≠ 0 if and only if q ≤ ⌊\frac{n}{2}⌋. Now we quote

• • • ([5], 4.2, [6], 4.). Assume q ≤ ⌊\frac{n}{2}⌋. Then ker H (q − 1, q) is generated by elements of the type

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

If we combine this result with Theorem 2 we obtain systems of generators of ker H (t, q); however, these systems are in general different from those exhibited in [5]. – In the same way we have explicite systems of generators of the eigenspaces with respect to H̃ (t, q).

Finally we make a remark concerning the eigenspaces of H (t, q) ∘ H (t, q)^{T}. We restrict ourselves to quote the following result:

• • • • ([4], Chapt. 10, Lemma 3.2) For any matrix A the non–zero eigenvalues of AA^{T} and A^{T} A are the same, and have the same multiplicities.

4. In this last section we take 𝕂 = 𝔽_{2}. We investigate now the mappings

H̃_{q}(q|n) =: H̃ (q − 1, q) : _{𝔽_{2}}C_{q}(n) ⟶ _{𝔽_{2}}C_{q}(n),

using the algebra _{𝔽_{2}}ℭ_{∗}(n). According to Prop. 1 we have

H̃ (q|n)([M]) = (q · 1) · [M] + ∑_{|M∩M′|=q−1}^{|M′|=q} 1 · [M′].

The reader might have wondered why we admit a field of positive characteristic. In fact, as we soon will see, H̃ (q|n) is a projection (hence diagonalizable) if n is odd (otherwise nilpotent). We have already observed in 3. that (_{𝔽_{2}}ℭ_{∗}(n), Δ) is a complex in the sense of homological algebra. Let us rewrite this complex 𝔎_{n} in the following way

0 ⟶ C_{n}(n) ⟶^{Δ_{n}} C_{n−1}(n) ⟶^{Δ_{n−1}} … ⟶^{Δ_{2}} C_{1}(n) ⟶^{Δ_{1}} C_{0}(n) ⟶ 0,

where of course we use the notation Δ_{q} = Δ|_{C_{q}(n)}.

Proposition 6. The complex 𝔎_{n} is exact.

This can be seen in different ways: First, the homology of the ball vanishes over any field. Or secondly, 𝔎_{n} is isomorphic to a Koszulkomplex. The claim now follows from standard arguments about the vanishing of the homology modules of this complex. Third, the claim follows also from the much more general considerations in [2].

However, it will be useful for our purposes to prove the exactness of 𝔎_{n} as follows: Since the statement is trivial if n = 1, we assume in the sequel always n ≥ 2.

Proposition 7.

i) Im Δ_{q} is already generated by the images of the elements X_{n} · u, where u ∈ C_{q−1}(n − 1).

ii) rank Δ_{q} = \binom{n−1}{q−1}.

Proof. The elements different from zero recorded in assertion i) are exactly those w ∈ C_{q}(n) with the property Fund (w) ∩ {X_{n}} ≠ ∅. If q = n, the claim is obvious. So assume now 1 ≤ q ≤ n − 1 and take w ∈ C_{q}(n), Fund (w) ∩ {X_{n}} = ∅. It follows that X_{n} · w ∈ C_{q+1}(n) and according to Prop. 3

Δ_{q+1}(X_{n} · w) = w + X_{n} · Δ_{q}(w).

But Δ_{q} ∘ Δ_{q+1} = 0, so we obtain

Δ_{q}(w) = Δ_{q}(X_{n} · Δ_{q}(w))

which proves the first claim.

To prove ii) it is sufficient to show that Δ_{q} restricted to the subspace X_{n} · C_{q−1}(n − 1) is injective. So assume X_{n} · u is contained in that subspace. Then again according to Prop. 3 we obtain

0 = Δ_{q}(X_{n} · u) = u + X_{n} · Δ_{q−1}(u)

and hence u = 0, since X_{n} is no factor of u. Combined with assertion i) we obtain now

rank Δ_{q} = dim C_{q−1}(n − 1) = \binom{n − 1}{q − 1}.

As announced we prove again the exactness of 𝔎_{n} as follows: Assume 1 ≤ q ≤ n − 1. Then it holds that

dim ker Δ_{q} = \binom{n}{q} − \binom{n − 1}{q − 1} = \binom{n − 1}{q} = dim Im Δ_{q+1}.

The exactness of 𝔎_{n} at the positions 0, n is obvious.

The rank–formula in Prop. 7 is also a consequence of the more general considerations in [7]. Here the rank of the integer valued incidence matrix H (t, q) reduced mod pℤ, p any prime, was determined. The rank–formula obtained there (loc. cit., Theorem 1) applied to our case yields

rank Δ_{q} = \binom{n}{q − 1} − \binom{n}{q − 2} + \binom{n}{q − 3} ∓ … + (−1)^{q+1}\binom{n}{0}.

For a proof that both expressions obtained for the rank of Δ_{q}, coincide we refer to [6], Theorem 2, Lemma.

Theorem 3. i) H̃ (q|n)^{2} = \{ \begin{matrix}H̃ (q|n), & if n is odd, \\ 0, & if n is even. \end{matrix}

ii) If n is odd then

rank H̃ (q|n) = \binom{n − 1}{q − 1}.

Assume 1 ≤ q ≤ n − 1. Then

ker H̃ (q|n) = ImH (q, q + 1).

iii) If n is even then

rank H̃ (q|n) = \binom{n − 2}{q − 1}.

Assume 1 ≤ q ≤ n − 1. Then

ker H̃ (q|n) = X_{n} · Im H̃ (q − 1|n − 1) ⊕ Im H (q, q + 1).

Proof. ad i). Suppose u ∈ C_{q−1}(n). Then according to Prop. 4, ii) we have that

Δ (𝕏u) = 𝕏 · Δ (u) + (n · 1) · u.

But 𝕏^{2} = 0, so we obtain

𝕏Δ𝕏 (u) = (n · 1)𝕏u.

Now we take u = Δw, w ∈ C_{q}(n). This yields

𝕏Δ𝕏Δ (w) = (n · 1) · 𝕏Δ (w).

We observe 𝕏Δ (w) = H̃ (q|n)(w). The claim now follows.

To prove the remaining assertions let us make some preliminaries: Denote by H̃ (q|n)_{r} the restriction of H̃ (q|n) to the subspace X_{n} · C_{q−1}(n − 1) of C_{q}(n). Then according to Prop. 7, i)

Im H̃ (q|n) = Im H̃ (q|n)_{r}.

Take now u ∈ C_{q−1}(n − 1) and denote 𝕏_{(n−1)} := ∑_{j=1}^{n−1} X_{j}. Then according to

Prop. 3

\begin{aligned}𝕏Δ (X_{n} · u) & = (𝕏_{(n−1)} + X_{n}) · (u + X_{n} · Δ_{q−1}(u)) = \\ & = X_{n} · (u + 𝕏_{(n−1)}Δ_{q−1}(u)) + 𝕏_{(n−1)} · u. \end{aligned}

We rewrite this equation as follows

(5) … H̃ (q|n)(X_{n} · u) = X_{n} · (u + H̃ (q − 1|n − 1)(u)) + 𝕏_{(n−1)} · u.

(Observe that H̃ (0|n − 1) is the zero–mapping.) Now assume in Eq (5) that X_{n} · u is contained in the kernel of H̃ (q|n). Since 𝕏_{(n−1)} · u does not contain X_{n} as a factor both terms on the right–hand side in Eq (5) must be zero, in particular

(6) …  u + H̃ (q − 1|n − 1)(u) = 0.

ad ii). We derive from the first part of the proof that now H̃ (q − 1|n − 1) is nilpotent. Therefore Eq (6) possesses only the trivial solution u = 0, so H̃ (q|n)_{r} is injective. In turn

rank H̃ (q|n) = rank H̃ (q|n)_{r} = dim C_{q−1}(n − 1) = \binom{n − 1}{q − 1}.

Now take 1 ≤ q ≤ n − 1. Since 𝔎_{n} is exact

Im Δ_{q+1} ⊆ ker H̃ (q|n).

According to Prop. 7, ii) we have

dim Im H̃ (q|n) + dim Im Δ_{q+1} = \binom{n − 1}{q − 1} + \binom{n − 1}{q} = \binom{n}{q} = dim C_{q}(n).

This proves the remaining assertions.

ad iii). Assume first q ≥ 2. Let X_{n} ·u be in the kernel of H̃ (q|n)_{r}. Then as it was stated above u must solve Eq (6). Now according to i) H̃ (q − 1|n − 1) is a projection. Therefore Eq (6) has exactly all u ∈ Im H̃ (q − 1|n − 1) as solutions. Now we apply i) and obtain

dim ker H̃ (q|n)_{r} = dim(X_{n} · Im H̃ (q − 1|n − 1)) =

= dim Im H̃ (q − 1|n − 1) = \binom{n − 2}{q − 2},

in turn

rank H̃ (q|n) = rank H̃ (q|n)_{r} = \binom{n − 1}{q − 1} − \binom{n − 2}{q − 2} = \binom{n − 2}{q − 1}.

(Observe that H̃ (n|n) = 0.) These arguments carry easily over to the case q = 1; we leave the details to the reader whom we remind of our convention \binom{m}{−1} = 0.

Assume now 1 ≤ q ≤ n − 1. Then we claim that the subspaces X_{n} · Im H̃ (q − 1|n − 1) and Im Δ_{q+1} of ker H̃ (q|n) are disjoint. In fact according to Prop. 7, i) Im Δ_{q+1} is already generated by the Δ_{q+1}(X_{n} · u), u ∈ C_{q}(n − 1). But

Δ_{q+1}(X_{n} · u) = u + X_{n} · Δ_{q}(u).

Therefore we conclude

dim ImH̃ (q|n) + dim (X_{n} · Im H̃ (n − 1|q − 1) + ImΔ_{q+1})
= \binom{n − 2}{q − 1} + \binom{n − 2}{q − 2} + \binom{n − 1}{q} = \binom{n − 1}{q − 1} + \binom{n − 1}{q}
= \binom{n}{q} = dim C_{q}(n).

This finishes the proof.

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

References

[1] Th. Beth, D. Jungnickel, H. Lenz: Design Theory. Mannheim/Wien/Zürich 1985 (B.I. Wissenschaftsverlag)

[2] Th. Bier: Eine homologische Interpretation gewisser Inzidenzmatrizen mod p. Math. Ann. 297 (1993) 289–302

[3] R. A. Brualdi, H. Ryser: Combinatorial Matrix Theory. Cambridge 1991 (Cambridge University Press)

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

[5] J.B. Graver, W.B. Jurkat: The Module Structure of Integral Designs. Journal of Comb. Theory A 15 (1973), 75–90

[6] H. Krämer: Inversion of Incidence Mappings. Séminaire Lotharingien de Combinatoire, B39f (1997), 20pp.

http://cartan.u-strasbg.fr:80/~slc/

[7] R.M. Wilson: A Diagonal Form for the Incidence Matrices of t–Subsets vs. k–Subsets. Europ. J. Combinatorics 11 (1990) 609–615.