Séminaire Lotharingien de Combinatoire 45 (2001), Article B45d

Binary Moore-Penrose Inverses of Set Inclusion Incidence Matrices

Helmut Krämer

Fachbereich Mathematik der Universität Hamburg Bundesstraße 55 20146 Hamburg – Germany

Abstract

This note is a supplement to some recent work of R.B. Bapat on Moore-Penrose inverses of set inclusion matrices. Among other things Bapat constructs these inverses (in case of existence) for H(s, k) mod p, p an arbitrary prime, 0 ≤ s ≤ k ≤ v − s. Here we restrict ourselves to p = 2. We give conditions for s, k which are easy to state and which ensure that the Moore-Penrose inverse of H(s, k) mod 2 equals its transpose. E.g., H(s, v − s) mod 2 has this property. Furthermore Ker H(s, v − s) mod 2 is nonzero if 0 < 2s < v ≤ 3s and then there is a decomposition

Ker H(s, v − s) ≡ _{∑_{0≤j≤s−1} ; 2 | \binom{v−s−j}{v−2s}}Im H(v − s, v − j) mod 2.

Also, refinements of this decomposition are given.

1. Let 𝔽 be a field. If A is a m × n-matrix with entries in 𝔽, then a n × mmatrix G (with entries in 𝔽) is called a generalized inverse (g-inverse) of A if

AGA = A.

A Moore-Penrose inverse of A, denoted by A^{+}, is a n×m-matrix G satisfying the equations

AGA = A, GAG = G,
(AG)^{T} = AG, (GA)^{T} = GA.

Note that if A is square and invertible, G = A^{−1} is a Moore-Penrose inverse of A. Thus A^{+} (if it exists) can be thought of as a substitute for the inverse of A, even if A is non-square.

• Any real or complex matrix admits a unique Moore-Penrose inverse.

In general, the following theorem gives a necessary and sufficient condition for a matrix to admit a Moore-Penrose inverse over an arbitrary field.

Theorem (R.B. Bapat, K.P.S. Bhaskara, K. Manjunatha, [2]) A m × n-matrix of rank r over an arbitrary field admits a Moore-Penrose inverse if and only if the sum of the squares of the r × r minors of A is nonzero.

Moore-Penrose inverses were introduced by Penrose for complex matrices with a slight modification replacing in the above four defining equations the transpose of a matrix by its complex-conjugate transpose.

However, the proof that Moore-Penrose inverses are uniquely determined (if they exist) carries over to the definiton given above. For the convenience of the reader we reproduce the proof. So let X, Y two Moore-Penrose inverses of A. Then

X = XAX = X(AX)^{T} = XX^{T} A^{T} = XX^{T} (A^{T} Y^{T} A^{T})
= X(AX)^{T} (AY)^{T} = X(AXA)Y = XAY =
= (XA)^{T} (Y AY) = (XA)^{T} (Y A)^{T} Y = (A^{T} X^{T} A^{T})Y^{T} Y =
= A^{T} Y^{T} Y = (Y A)^{T} Y = Y.

Note that all four defining equations have been used in the proof.

Now we recall the definition of set-inclusion incidence matrices. In fact there are two families of incidence matrices. Let s, k, v be in ℕ_{0} and s, k ≤ v. Let H_{v}(s, k) = H(s, k) denote the integer (0, 1)-matrix with rows and columns indexed respectively by the s-subsets and k-subsets of a fixed v-set with ijentry equal to one if and only if the i-th s-subset is contained in the j-th k-subset.

By \overline{H_{v}}(s, k) = \overline{H}(s, k) we denote the integer (0, 1)-matrix with rows and columns indexed respectively be the s-subsets and k-subsets of a fixed v-set, with ij-entry equal to one if and only if the i-th s-subset is contained in the complement of the j-th subset.

Here we are mainly concerned with the first family of matrices.

Both H(s, k) and \overline{H}(s, k) may be zero matrices but e.g. both H(0, k) and \overline{H}(0, k) are the 1 × \binom{v}{k} vector of all ones.

There are many relations between H(s, k) and \overline{H}(s, k) (see for example [5], Chapt 15, 8.2) from which we quote only one

• \overline{H}(s, k) = ∑_{i}(−1)^{i}H(i, s)^{T} H(i, k).

If p is any prime number we denote by H(s, k)_{p}, \overline{H}(s, k)_{p} the matrices obtained by reducing all entries of H(s, k) or \overline{H}(s, k) respectively modulo p ℤ.

Binomial coefficients \binom{n}{m} are also defined if m is negative. We adopt the convention that \binom{n}{m} = 0 if m < 0 or n < m.

2. The problem to give necessary and sufficient conditions which imply the existence of a Moore-Penrose inverse of H(s, k)_{p}, p an arbitrary prime, has been solved very recently:

Theorem (R.B. Bapat [1]) Let 0 ≤ s ≤ k ≤ v − s, let p be a prime and let

N = \{i : 0 ≤ i ≤ s, p ∤ \binom{k − i}{s − i}\} .

Then H(s, k)_{p} has a Moore-Penrose inverse if and only if p ∤ \binom{v−i−s}{k−s} for all i ∈ N. Furthermore, the Moore-Penrose inverse, if it exists, is given by

H(s, k)_{p}^{+} = ∑_{i,j∈N}(−1)^{i} \begin{matrix}( & {v−i−j \atop s−i} & ) \\ ( & {v−i−s \atop k−s} & ) \end{matrix}\overline{H}(i, k)_{p}^{T} \overline{H}(j, i)_{p}^{T} H(j, s)_{p}.

Corollary H(s, v − s)_{p} admits a Moore-Penrose inverse for all primes p.

Now Bapat provides an example of an incidence matrix where the Moore-Penrose inverse is just one matrix; take H_{6}(2, 4)_{3}. Here the set N = {2} has minimum cardinality. After making a suitable arrangement of the 2-sets and the 4-sets of the 6-set it is shown that H_{6}(2, 4)_{3}^{+} = H_{6}(2, 4)_{3}.

We give now another example of an incidence matrix where the set N has maximum cardinality and the Moore-Penrose inverse equals the transpose of the given matrix. Let for a moment p be an arbitrary prime and recall

Wilson’s Rank Formula ([8]) Let 0 ≤ s ≤ k ≤ v − s, let p be a prime and let

N = \{i : 0 ≤ i ≤ s, p ∤ \binom{k − i}{s − i}\} .

Then

rank H(s, k)_{p} = ∑_{i∈N} \{\binom{v}{i} − \binom{v}{i − 1}\} .

Now we take k = v − s. Let s, v be so chosen, that v > 2s and N = {0, 1, …, s}. Then the rank-formula yields

rank H(s, v − s)_{p} = ∑_{i=0}^{s} \{\binom{v}{i} − \binom{v}{i − 1}\} = \binom{v}{s},

so H(s, v − s)_{p} is nonsingular and therefore

H(s, v − s)_{p}^{+} = H(s, v − s)_{p}^{−1}.

Now we take p = 2 and claim H(s, v − s)_{2}^{−1} = H(s, v − s)_{2}^{T}.

Now H(s, v − s)^{T} H(s, v − s) = (α (L, M)) with

α (L, M) = \binom{|L ∩ M|}{s}, L, M (v − s)-sets.

Now look at Pascal’s triangle (more precisely at a part of it).

._{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  _{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.} ^{.} ^{.} ^{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.}_{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.}_{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.} _{.}  _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  _{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}_{.} ■ ⨂ ⨂  ⨂ ⨂ ⨂ ⨂ ⨂ ■ ⨂  ⨂ ⨂ ⨂ ⨂ ■  ⨂ ⨂ ⨂ ⨂ ⨂ ■ ⨂ ⨂ ■ ⨂ ■^{\binom{v−2s}{0}}  ^{\binom{v−2s}{s}}_{\binom{v−s−1}{s−1}}  _{\binom{v−s−1}{s}}_{\binom{v−s}{s}}

■ = entry is odd, ⨂ = entry is even. By moving in the triangle from left to right we obtain

2 | \binom{v − s − i}{s}, 1 ≤ i ≤ s,

in particular v > 3s. Therefore

H(s, v − s)_{2}^{T} H(s, v − s)_{2} = (α (L, M)mod 2) = I

and the claim is proved; furthermore

H(s, v − s)_{2}^{+} = H(s, v − s)_{2}^{T} .

Note that we can skip the use of Wilson’s rank-formula in proving that the Moore-Penrose inverse of H(s, v − s)_{2} equals its transpose.

3. In the sequel we focus on binary Moore-Penrose inverses of incidence matrices H(s, k)_{2}. Our main source of interest is • Construction of linear binary codes C of the form C = Ker H(s, k)_{2} for

appropriate s, k.

Definition Let 0 ≤ s ≤ k ≤ v. We say that H(s, k)_{2} admits a special Moore-Penrose inverse, if it admits a Moore-Penrose inverse and this equals H(s, k)_{2}^{T}.

We need some elementary number theory. Let p for a moment be an arbitrary prime and let n ∈ ℕ. If p^{α}, α ≥ 1 occurs as a factor in the primary decomposition of n, call α to be the order (= ord_{p} (n)) of p with respect to n. If p ∤ n, define ord_{p} (n) = 0.

• (Gauß) ord_{p}(n!) = ∑_{i=1}^{∞} ⌊\frac{n}{p^{i}} ⌋.

• ord_{p}(n!) = \frac{n − Q(n)}{p − 1}. Here Q(n) denotes the sum of the digits in the p-adic expansion of n. (See e.g. [6], Chapter I, Exercise 13. This can also easily be proved with help of Gauß’ result).

Therefore

• ord_{p} (\binom{n}{m}) = \frac{Q(m) + Q(n − m) − Q(n)}{p − 1}, 0 ≤ m ≤ n.

In particular

(1)… ord_{2} (\binom{n}{m}) = Q(m) + Q(n − m) − Q(n), 0 ≤ m ≤ n.

This yields also an “indirect proof” that all “p-adic” functions Q : ℕ_{0} → ℕ_{0} are “subadditive”, that is that

Q(l + m) ≤ Q(l) + Q(m); m, l ∈ ℕ_{0},

since

0 ≤ ord_{p} (\binom{l + m}{m}) = \frac{Q(m) + Q(l) − Q(m + l)}{p − 1}.

Theorem 1 Let 0 ≤ s < k ≤ v − s and r ∈ ℕ_{0} be such that

2^{r} ≤ k − s < 2^{r+1}.

Assume

v ≡ s + k mod 2^{r+1}.

Then H(s, k)_{2} admits a special Moore-Penrose inverse. Corollary H(s, v − s)_{2} admits a special Moore-Penrose inverse. Proof: We use the following Lemma 1 ([5], Chapter 15, 8.4) Let 0 ≤ s ≤ k, 0 ≤ t ≤ k. Then

H(s, k) H(t, k)^{T} = ∑_{i} \binom{v − s − t}{v − k − i}H(i, s)^{T} H(i, t).

The proof of the lemma uses Vandermonde’s identity for binomial coefficients.

Now put in the lemma s = t, multiply the identity from the right with H(s, k), use the well-known identity

(2)… H(i, s) H(s, l) = \binom{l − i}{s − i}H(i, l), 0 ≤ i ≤ s ≤ l,

(see e.g. [5], Chapter 15, 8.1) and obtain

(3)… H(s, k) H(s, k)^{T} H(s, k) = ∑_{i} \binom{v − 2s}{v − k − i}\binom{k − i}{s − i}H(i, s)^{T} H(i, k).

Now consider the product

\binom{v − 2s}{v − k − i}\binom{k − i}{s − i}.

Denote q := k − s. The first factor in the above product is \binom{v−2s}{q−s+i}. So we can restrict the above sum (3) to those i ≥ 0 with i ≥ s − q. We define a new running index j by

i = s − q + j, j ≥ q − s.

Then the above product equals \binom{v−2s}{j}\binom{2q−j}{q} which is zero if j < 0 or j > q. Therefore

(4)…  \{ \begin{matrix}H(s, k) H(s, k)^{T} H(s, k) = \\ ∑_{j=max\{0,q−s\}}^{q} \binom{v − 2s}{j}\binom{2q − j}{q} · H(s − q + j, k)^{T} · H(s − q + j, s). \end{matrix}

Similarly, by multiplying the identity of the lemma from the left with H(s, k)^{T} we obtain

(4’)…  \{ \begin{matrix}H(s, k)^{T} H(s, k) H(s, k)^{T} = \\ ∑_{j=max\{0,q−s\}}^{q} \binom{v − 2s}{j}\binom{2q − j}{q} · H(s − q + j, k)^{T} · H(s − q + j, s). \end{matrix}

Claim: \binom{v − 2s}{j}\binom{2q − j}{q} is \{ \begin{matrix}odd, & if j = q, \\ even, & if 0 ≤ j < q. \end{matrix}

Suppose that the claim has already been proved. Then we reduce equations (4), (4’) modulo 2, observe that H(s, s) = I and obtain

\begin{aligned}H(s, k)_{2} H(s, k)_{2}^{T} H(s, k)_{2} & = & H(s, k)_{2}, \\ H(s, k)_{2}^{T} H(s, k)_{2} H(s, k)_{2}^{T} & = & H(s, k)_{2}^{T} . \end{aligned}

This already proves that H(s, k)_{2} admits H(s, k)_{2}^{T} as a (special) Moore-Penrose inverse, since the remaining two assertions (which define Moore-Penrose inverses) are trivially satisfied.

Now we prove the claim, first statement. By assumption

n : v − s ≥ k − s = q ≥ 1,
n ≡ q mod 2^{r+1}.

Let n = λ · 2^{r+1} + q, λ ∈ ℕ_{0}, q < 2^{r+1}. Therefore

Q(n) = Q(λ · 2^{r+1}) + Q(q)

and

\begin{aligned}ord_{2} (\binom{v − 2s}{q}) & = & ord_{2} (\binom{n}{q}) = Q(q) + Q(n − q) − Q(n) = \\ & = & Q(q) + Q(λ · 2^{r+1}) − (Q(λ · 2^{r+1}) + Q(q)) = 0 \end{aligned}

To prove the second statement of the claim it is sufficient to show:

If for some j, 0 ≤ j < q, \binom{2q − j}{q} is odd, then \binom{n}{j} is even.

By assumption

(5)… 0 = ord_{2} (\binom{2q − j}{q}) = Q(q) + Q(q − j) − Q(2q − j).

Since n − j = λ · 2^{r+1} + (q − j), 1 ≤ q − j < 2^{r+1}, an easy calculation shows

ord_{2} (\binom{n}{j}) = Q(j) + Q(q − j) − Q(q).

Combine this with Eq (5) and obtain

ord_{2} (\binom{n}{j}) = Q(j) + 2Q(q − j) − Q(2q − j).

Now we use the subadditivity of Q and Q(2l) = Q(l), l ∈ ℕ_{0} and obtain

ord_{2} (\binom{n}{j}) = Q(j) + (Q(2q − 2j) + Q(q − j)) − Q(2q − j)
= (Q(j) + Q(2q − 2j)) + Q(q − j) − Q(2q − j)
≥ Q(2q − j) + Q(q − j) − Q(2q − j) = Q(q − j) > 0.

This proves the claim. □

Remark In the theorem the condition 0 ≤ s < k ≤ v − s can in some cases (with more work) be weakened. For example take k = s + 1. Then according to the theorem H(s, s+1)_{2} admits a special Moore-Penrose inverse provided

v odd , s ≤ \frac{v − 1}{2}.

However, this is true for v odd and all s, 0 ≤ s ≤ v − 1.

4. In this section we come to an application. Let 𝔽 be any field. We associate to the integer matrix H(s, k) a linear map H(s, k)_{𝔽} of 𝔽-vectorspaces as follows. Let C_{i}, 0 ≤ i ≤ v the 𝔽-vectorspace with base \{\underline{T} \}, where T runs through all i-subsets of the v-set and let the linear map

H(s, k)_{𝔽} : C_{k} → C_{s}

induced by

H(s, k)_{𝔽} (\underline{T}) = ∑_{S⊂T}^{|S|=s} \underline{S}, |T | = k.

In case 𝔽 = 𝔽_{p} we write again H(s, k)_{𝔽} = H(s, k)_{p}.

Theorem (A. Bjerhammar [4], R. Penrose [7]) Let 𝔽 be a field and A, G be m × n resp. n × m matrices with entries in 𝔽 such that AGA = A. Then the system of linear equations Ax = b has a solution if and only if

AGb = b

in which case the most general solution is

x = Gb + (I − GA)y, y arbitrary.

In particular Ker A = Im (I − GA).

Let p be an arbitrary prime and suppose that H(s, k)_{p} admits a Moore-Penrose inverse. Then

(6)… Ker H(s, k)_{p} = Im (I − H(s, k)_{p}^{+} H(s, k)_{p}).

On the other side it is straightforward to exhibit a subspace of Ker H(s, k)_{p} (regardless whether H(s, k)_{p} admits a Moore-Penrose inverse or not). According to eq. (2)

(7)… U_{s,k}^{p} := _{∑_{0≤j≤v−(k+1)} ; p | \binom{v−s−j}{k−s}} Im H(k, v − j)_{p}

is a subspace of Ker H(s, k)_{p} (of course, the above sum may be empty). We make the following

Conjecture Let 0 < s < k < v, and let p be a prime. Then

Ker H(s, k)_{p} = U_{s,k}^{p}.

We give an example where the conjecture is true and take k = s + 1, p = 2. Then H(s+1, v−j)_{2} is a subspace of U_{s,s+1}^{2} iff v−j −s is even. But according to eq. (2) then

H(s + 1, s + 2)_{2} · H(s + 2, v − j)_{2} = (v − j − s − 1) · 1 · H(s + 1, v − j)_{2} = H(s + 1, v − j), 1 ∈ 𝔽_{2}, s + 2 ≤ v − j.

Therefore

U_{s,s+1}^{2} ⊇ Im H(s + 1, s + 2)_{2} ⊇ Im H(s + 2, v − j)_{2}

and U_{s,s+1}^{2} = Im H(s + 1, s + 2)_{2}. It has been remarked in [7], Prop. 7, that Ker H(s, s + 1)_{2} = Im H(s + 1, s + 2)_{2} (= U_{s,s+1}^{2}). –

This example also shows that the sum in eq. (7) might be “redundant”.

We give a second example which at least gives some evidence that the conjecture might be true.

Let 0 < s < k = v − s and p a prime. Then

det H(s, v − s) = ∏_{j=0}^{s−1} \binom{v − s − j}{v − 2s}^{\binom{v}{j}−\binom{v}{j−1}}

(see [9], Theorem 2 or [7], Corollary 1 to Theorem 1). Then obviously

Ker H(s, v − s)_{p} ≠ (0) iff p | det H(s, v − s) iff U_{s,v−s}^{p} ≠ (0).−

In the sequel we stick to this example in the binary case. First we derive a criterion that ensures that Ker H(s, v − s)_{2} is nonzero, making no use of the formula for det H(s, v − s) just given.

According to the Corollary to Theorem 1 and eq. (6) we have

(8)… Ker H(s, v − s)_{2} = Im (I + H(s, v − s)_{2}^{T} H(s, v − s)_{2}).

Proposition Let 0 < 2s < v and assume that

H(s, v − s)_{2} : C_{v−s} → C_{s}

is an isomorphism. Then 3s < v. In particular, if 0 < 2s < v ≤ 3s then Ker H(s, v − s)_{2} is nonzero.

Proof: By assumption Ker H(s, v − s)_{2} = (0). Then eq. (8) yields

I = H(s, v − s)_{2}^{T} H(s, v − s)_{2} = (\binom{|L ∩ M|}{s} mod 2) .

Now if L, M vary through all (v − s)-sets, \binom{|L∩M|}{s} takes all values \binom{v−s−j}{s} =: α_{j}, 0 ≤ j ≤ s. Now we have α_{0} > 1 (and α_{0} odd) and α_{j} even if 0 < j. This implies v − 2s > s. □

At the same time we have proved the

Corollary Assume that 0 < 2s ≤ v and that H(s, v−s)_{2} is nonsingular. Then H(s, v − s)_{2}^{−1} = H(s, v − s)_{2}^{T}.

From now on we assume 0 < 2s < v ≤ 3s. To prove the conjecture for H(s, v − s)_{2} it is sufficient to show that

(9)… Im (I + H(s, v − s)_{2}^{T} H(s, v − s)_{2}) ⊆ U_{s,v−s}^{2} =: U_{s}.

We first describe briefly the lines of the proof. Now Ker H(s, v − s)_{2} is generated by the elements

σ_{M} := \underline{M} + ∑^{|L|=v−s} \binom{|M ∩ L|}{s} · 1 · \underline{L}, |M| = v − s, 1 ∈ 𝔽_{2}.

Now we put v − 2s =: q, 1 ≤ q ≤ s. Furthermore |L ∩ M| = v − s − j iff |L ∪ M| = v − s + j. We define

S_{v−l}^{M} = _{∑_{|L|=v−s} ; |L∪M|=v−l}\underline{L}, 0 ≤ l ≤ s.

(Observe that S_{v−s}^{M} = \underline{M}). Then we rewrite the generators σ_{M} of Ker H(s, v − s)_{2}:

(10)… σ_{M} = (\binom{s + q}{s} · 1 + 1) · \underline{M} + ∑_{l=0}^{s−1} \binom{l + q}{s} · 1 · S_{v−l}^{M}, 1 ∈ 𝔽_{2}.

Observe that all σ_{M} are nonzero.

If X is a subset of the v-set denote by ∁X the complement of X.

Lemma 2 Let M be a (v − s)-subset of the v-set. Then for 0 ≤ t ≤ s one has

τ_{t}^{M} := ∑_{|T |=t,T ⊂∁M}^{T} H(v − s, v − t)_{2} (∁T) = ∑_{l=0}^{s} \binom{l}{t} · 1 · S_{v−l}^{M}.

Furthermore if \binom{v−s−t}{s−t} is even then all τ_{t}^{M} are contained in Ker H(s, v − s)_{2}.

Proof: Let L be a (v−s)-set and |L∪M| = v−l, 0 ≤ l ≤ s and R := ∁(M ∪L). Then

L ⊂ ∁T iff ∁R = M ∪ L ⊂ ∁T iff R ⊃ T.

In particular l ≥ t. So if l < t (this condition is vacuous if t = 0) \underline{L} appears with coefficient 0 in all \binom{s}{t} summands of the L.S. of the formula. If l ≥ t then \underline{L} appears with coefficient 1 in exactly \binom{l}{t} summands in the L.S. of the formula (we remind the reader of our convention on binomial coefficients).

The last assertion follows from eq. (2). □

Now we will show that all generators σ_{M} of Ker H(s, v − s)_{2} are sums of elements τ_{t}^{M} for appropriate t all of which are contained in Ker H(s, v − s)_{2}, thereby proving eq. (9). At the same time, we obtain more precise assertions on “generating” subspaces of U_{s}.–

To state the next result we define on ℕ_{0} a partial order “≺” as follows. If j, q ∈ ℕ_{0} and

j = ∑_{i≥0} a_{i}2^{i}, q = ∑_{i≥0} b_{i}2^{i}

are the 2-adic expansions of j resp. q, we define

j ≺ q if a_{i} ≤ b_{i} for all i ≥ 0.

Then put M(q) = {j : j ∈ ℕ_{0}, j ≺ q} and M(q)^{∗} = M(q) \ {0}. So, for example for t ≥ 1

\begin{aligned}M(2^{t} − 1) & = & \{0, 1, 2, …, 2^{t} − 1\}, \\ M(2^{t}) & = & \{0, 2^{t}\}, \\ M(2^{t} + 1) & = & \{0, 1, 2^{t}, 2^{t} + 1\}. \end{aligned}

Theorem 2 Assume 0 < 2s < v ≤ 3s. Then Ker H(s, v −s)_{2} is nonzero and

Ker H(s, v − s)_{2} = _{∑_{0≤i≤s−1} ; 2 | \binom{v−s−i}{v−2s}}Im H(v − s, v − i)_{2}.

Moreover it already holds that

Ker H(s, v − s)_{2} = ∑_{j∈M(v−2s)^{∗}} Im H(v − s, v − s + j)_{2}.

So the theorem states for example that in case v − 2s = 2^{t} − 1, t ≥ 1,

Ker H(s, v − s)_{2} = ∑_{j=1}^{2^{t}−1} Im H(v − s, v − s + j)_{2},

in case v − 2s = 2^{t}, t ≥ 0,

Ker H(s, v − s)_{2} = Im H(v − s, v − s + 2^{t})_{2},

in case v − 2s = 2^{t} + 1, t ≥ 1,

Ker H(s, v − s)_{2} =

Im H(v −s, v −s+1)_{2} +Im H(v −s, v −s+2^{t})_{2} +Im H(v −s, v −s+2^{t} +1)_{2}.– Proof of the theorem: We use the notations introduced above.

We apply on the binomial coefficient \binom{l+q}{s}, q = v−2s, 0 ≤ l ≤ s, q-times the relation \binom{n}{m} = \binom{n−1}{m} + \binom{n−1}{m−1}, n ∈ ℕ, m ∈ ℤ. Note that we use the relation even in the trivial cases m < 0 or n ≤ m. At each time we cancel binomial coefficients which appear with factor 2. So for example if q = 2,

\binom{l + 2}{s} = \binom{l + 1}{s} + \binom{l + 1}{s − 1}
= (\binom{l}{s} + \binom{l}{s − 1}) + (\binom{l}{s − 1} + \binom{l}{s − 2})
= \binom{l}{s} + 2\binom{l}{s − 1} + \binom{l}{s − 2} ≡ \binom{l}{s} + \binom{l}{s − 2} mod 2.

So we reach a congruence

(11)… \binom{l + q}{s} ≡ ∑_{i∈\overline{M}(q)} \binom{l}{s − i} mod 2,

with a certain subset \overline{M}(q) of \{0, 1, 2, …, q\} which contains 0 and q. To determine this subset we consider the 𝔽_{2}-vectorspace

V = 𝔽_{2}^{(ℤ)} = {f : f : ℤ → 𝔽_{2}, almost all f(m) = 0, m ∈ ℤ}.

Let Supp f = {m : f(m) ≠ 0}. Define the basis {e_{m} : m ∈ ℤ} of V by

e_{m}(r) = \{ \begin{matrix}1, & r = m, \\ 0, & otherwise. \end{matrix}

Finally we define the linear map φ : V → V to be induced by

φ(e_{m}) = e_{m} + e_{m−1}, m ∈ ℤ.

Now we rewrite eq. (11) as follows:

(12)… \binom{l + q}{s} ≡ ∑_{r∈Supp φ^{q}(e_{s})} \binom{l}{r} mod 2.

Lemma 3 If m ∈ ℤ and q ∈ ℕ, then

Supp φ^{q}(e_{m}) = {m − j : j ∈ M(q)}.

Proof: First we prove that the assertion is true if q = 2^{t}, t ≥ 0, by induction on t. If t = 0, then

Supp φ(e_{m}) = Supp (e_{m} + e_{m−1}) = {m − j : j ∈ M(1)}.

Suppose the claim is true for q = 2^{t}. Then

φ^{2^{t+1}}(e_{m}) = φ^{2^{t}}(φ^{2^{t}}(e_{m}) = φ^{2^{t}}(e_{m} + e_{m−2^{t}})
= (e_{m} + e_{m−2^{t}}) + (e_{m−2^{t}} + e_{m−(2^{t}+2^{t})} = e_{m} + e_{m−2^{t+1}},

so the claim is true for q = 2^{t+1}.

Now we suppose that the assertion is true for all q ∈ ℕ and q ≤ 2^{t}. Then we show now that the assertion is true for all q ∈ ℕ and q ≤ 2^{t+1} (this will finish the proof). We may now assume 2^{t} < q < 2^{t+1}, so q = 2^{t} + u, 1 ≤ u < 2^{t}. Then by hypothesis

φ^{q}(e_{m}) = φ^{u}(φ^{2^{t}}(e_{m})) = φ^{u}(e_{m} + e_{m−2^{t}}) = ∑_{i∈M(u)} e_{m−i} + ∑_{i∈M(u)} e_{m−2^{t}−i}.

Since M(q) = M(2^{t} + u) = M(u) ∪ {2^{t} + i : i ∈ M(u)} we obtain

φ^{q}(e_{m}) = ∑_{j∈M(q)}e_{m−j} as claimed. □

We conclude from eq. (12) and the lemma

(13)… \binom{l + q}{s} ≡ ∑_{j∈M(q)} \binom{l}{s − j} mod 2. –

Now we show that all τ_{s−j}^{M}, j ∈ M(q)^{∗} are contained in Ker H(s, v − s)_{2}. According to Lemma 2 it is sufficient to show that

\binom{v − s − (s − j)}{j} = \binom{q + j}{j}, j ∈ M(q)^{∗}

are even. But since j ≺ q, 1 ≤ j, we have

Q(q + j) < Q(q) + Q(j),

whence ord_{2}(\binom{q+j}{j}) > 0 as claimed.– Finally we claim that

(14)… σ_{M} = ∑_{j∈M(q)^{∗}} τ_{s−j}^{M} = ∑_{j∈M(q)^{∗}} ∑_{l=0}^{s} \binom{l}{s − j} · 1 · S_{v−l}^{M}.

In fact the coefficient of S_{v−s}^{M} = \underline{M} with respect to σ_{m} is \binom{s+q}{s} · 1 + 1 and with respect to the R.S. of eq. (14) is ∑_{j∈M(q)^{∗}} \binom{s}{s−j} · 1. Both coefficients agree

by eq. (13). Furthermore the coefficient of S_{v−l}^{M}, 0 ≤ l < s with respect to σ_{M} is \binom{l+q}{s} · 1 (according to eq. (10)) and with respect to the R.S. of eq. (14) is ∑_{j∈M(q)^{∗}} \binom{l}{s−j}·

1 which is ∑_{j∈M(q)} \binom{l}{s−j} · 1 since l < s and \binom{l}{s} = 0. Again both coefficients

coincide according to eq. (13). This proves eq. (14). Now we have the following chain of inclusions

U_{s} ⊆ Ker H(s, v − s)_{2} ⊆ ∑_{j∈M(q)^{∗}} Im H(v − s, v − s + j)_{2} ⊆ U_{s}.

Therefore throughout equality must hold. This proves the theorem. □

Remark We look at eq. (2) the other way round, that is we keep H(s, l) fixed and let H(i, s) vary, obtaining an inclusion of 𝔽_{p}-vectorspaces.

Im H(s, l)_{p} ⊆ _{⋂_{i<s} ; p|\binom{l−i}{s−i}}Ker H(i, s)_{p}, p prime.

Here equality holds. This result (which is of course much more general than ours) has been proved in [3] using Wilson’s techniques [9]. That we could dismiss these techniques here is due to the fact that the distribution of even and odd entries in Pascal’s triangle is well known. If one is willing to follow the lines used here to prove (parts of) the Conjecture for an arbitrary prime p, an analysis of the distribution of the residue-classes mod p in Pascal’s triangle should be made first. We shall return to this topic in a subsequent paper.

References

[1] R.B. Bapat: Moore-Penrose inverses of set inclusion matrices. Lin. Alg. and Appl., 318 (2000), 35-44.

[2] R.B. Bapat, K.P.S. Bhaskara, and K. Manjunatha Prasad: Generalized inverses over integral domains. Lin. Alg. and Appl., 140 (1990), 181-196.

[3] Th. Bier: Eine homologische Interpretation gewisser Inzidenzmatrizen mod p. Math. Annalen 297 (1993), 289-302.

[4] A. Bjerhammar: A generalized matrix algebra. Kungl. Tekn. Högsk. Handl. No. 124 (1968), 32 pp.

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

[6] N. Koblitz: p-adic Numbers, p-adic Analysis, and Zeta-Functions. New York-Heidelberg-Berlin, 1977 (Springer).

[7] H. Krämer: Eigenspace decompositions with respect to symmetrized incidence mappings. Seminaire Lotharingien de Combinatoire, Art. B41c (1998), 20 pp. http://www.mat.univie.ac.at/∼slc/

[8] R. Penrose: A generalized inverse for matrices. Proc. Cambridge Philos. Soc. 51 (1955), 406-413.

[9] R.M. Wilson: A diagonal form for the incidence matrices of t-sets vs. k-subsets. Europ. J. Combinatorics 11 (1990), 609-615.