\documentclass[12pt, fleqn]{article}
\usepackage{german}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{enumerate}
\usepackage{latexsym}
\parindent0pt

\selectlanguage{english}

\input prepictex
\input pictex.sty
\input postpictex

\bibliographystyle{plain}

\newcommand*{\I}[1]{{\mathbb #1}}
%\renewcommand{\qed}{}
%\swapnumbers
%\newtheorem{thm}{Theorem}[section]
%\newtheorem{lem}[thm]{Lemma}
%\newtheorem{cor}[thm]{Corollary}
%\newtheorem{satz}[thm]{}
%\newtheorem{defi}[thm]{Definition}
%\theoremstyle{definition}
%\newtheorem*{rem}{Remarks}
%\newtheorem*{con}{Conventions}
%\pagestyle{headings}
\setlength{\mathindent}{0mm}
\renewcommand{\baselinestretch}{1,1}

%\addtolength{\textwidth}{2cm}
%\addtolength{\textheight}{5cm}

%\voffset-2cm
%\hoffset-1cm

\begin{document}
\title{Binary Moore-Penrose Inverses of\\
Set Inclusion Incidence Matrices} 

\author{Helmut Kr"amer\\
Fachbereich Mathematik der Universit"at Hamburg\\
Bundesstra"se 55\\
20146 Hamburg -- Germany}

\date{}
\maketitle

\begin{abstract}
\noindent 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)\,{\rm mod}\,p$, $p$ an arbitrary prime, 
$0 \le s \le k \le 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)\,{\rm mod}\,2$ equals its 
transpose. 
E.g., $H(s,v-s)\, {\rm mod}\, 2$ has this property. Furthermore
${\rm Ker}\,H(s,v-s)\,{\rm mod}\,2$ is nonzero if $0 < 2s < v \le 3s$
and then there is a decomposition
$${\rm Ker}\, H(s,v-s) \equiv
\underset{2 \,\vert\, \binom{v-s-j } { v-2s}} 
{\sum \limits_{0 \le j \le s-1}} 
{\rm Im}\,H(v-s,v-j)\,{\rm mod}\,2.$$
Also, refinements of this decomposition are given.
\end{abstract}


%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 45 \rms (2001), Article~B45d\hfill}
\def\thepage{}
%
%

\bigskip

{\bf 1.} Let $\I F$ be a field. If $A$ is a $m \times n$-matrix 
with entries in $\I F$, then a $n \times m$-matrix $G$ (with entries in 
$\I F$) is called a generalized inverse (g-inverse) of $A$ if
$$AGA=A.$$
A Moore-Penrose inverse of $A$, denoted by $A^+$, is a $n \times m$-matrix 
$G$ satisfying the equations
\begin{center}
$AGA = A, \; GAG=G,$
\smallskip

$(AG)^T = AG, \; (GA)^T = GA.$
\end{center}
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.
\begin {itemize}
\item Any real or complex matrix admits a unique Moore-Penrose inverse.
\end {itemize}
In general, the following theorem gives a necessary and sufficient
condition for a matrix to admit a Moore-Penrose inverse over an
arbitrary field.
\medskip

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\small Helmut Kr\"amer}{\small Binary Moore-Penrose Inverses}
%
%


{\bf   Theorem} \qquad (R.B. Bapat, K.P.S. Bhaskara, K. Manjunatha, [2])\\
{\it
A $m \times 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 \times r$ minors of $A$ is nonzero.
}%it ende
\medskip

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.
\medskip

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
$$ \begin{array}{ccl}
X& =&  XAX = X (AX)^T = XX^TA^T = XX^T(A^TY^TA^T)\\
 & =&  X(AX)^T(AY)^T = X(AXA)Y = XAY =\\
 & =&  (XA)^T (YAY) = (XA)^T(YA)^TY = (A^TX^TA^T)Y^TY =\\
 & =&  A^T Y^TY = (YA)^T Y = Y.
\end {array}$$
Note that all four defining equations have been used in the proof.
\medskip

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 $\I N_0$ and $s, k \le 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 $ij$-entry equal 
to one if and only if the $i$-th $s$-subset is contained in the $j$-th
$k$-subset.
\medskip

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.
\medskip

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

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 \times 
{ \binom{v } { k} }$
vector of all ones.
\medskip

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

\begin {itemize}
\item $\overline{H}(s,k) = \displaystyle{ \sum \limits_i} 
(-1)^i H(i,s)^T H(i,k)$.
\end {itemize}

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 \, \I Z$.
\medskip

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$.
\bigskip

{\bf 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:
\bigskip

{ \bf Theorem} \qquad (R.B. Bapat [1])\\
{\it
Let $0 \le s \le k \le v-s$, let $p$ be a prime and let
$${\cal N} = \left\{i: 0 \le i \le s, \; 
p \nmid {\binom{k-i } { s-i}} \right\}.$$
Then $H(s,k)_p$ has a Moore-Penrose inverse if and only if 
$p \nmid {\binom{v-i-s } { k-s}}$ for all $i \in {\cal N}$. Furthermore,
the Moore-Penrose inverse, if it exists, is given by
\begin{center}
$H(s,k)_p^+ = \displaystyle{\sum
 \limits_{i,j \in {\cal N}}  } (-1)^i
 \displaystyle{\frac { \binom{v-i-j } { s-i} } {\binom{v-i-s } { k-s}} } 
\overline{H}(i,k)_p^T \, \overline {H}(j,i)_p^T \, H(j,s)_p.$
\end{center}
}%it ende
{ \bf Corollary}
{\it
$H(s,v-s)_p$ admits a Moore-Penrose inverse for all primes $p$.
}%it ende
\bigskip

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 ${\cal 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$.
\medskip

We give now another example of an incidence matrix where the set
${\cal 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
\medskip

{ \bf Wilson's Rank Formula} \; ([8])\\
{\it
Let $0 \le s \le k \le v-s$, let $p$ be a prime and let
\begin{center}
${\cal N} = \left\{i: 0 \le i \le s, \; 
p \nmid \displaystyle{\binom{k-i } { s-i}} \right\}.$
\end{center}
Then
\begin{center}
${\rm rank} \, H(s,k)_p = \displaystyle{\sum \limits_{i \in {\cal N}}  } 
\left \{ \displaystyle{ \binom{v } { i} - \binom{v } { i-1}} \right \}.$
\end{center}
}%it ende
\smallskip

Now we take $k = v-s$. Let $s,v$ be so chosen, that $v > 2s$ and
${\cal N} \linebreak[4]= \{0, 1, \ldots, s\}$. Then the rank-formula yields
\begin{center}
${\rm rank} \, H(s,v-s)_p =  \displaystyle{\sum \limits _{i = 0}^s  } \left \{
 \displaystyle{\binom{v } { i} - \binom{v } { i-1}} \right \} =  \displaystyle{\binom{v } { s}},$
\end{center}
so $H(s,v-s)_p$ is nonsingular and therefore
\begin{center}
$H(s, v-s)_p^+ = H(s,v-s)_p^{-1}.$
\end{center}

Now we take $p = 2$ and claim $H(s, v-s)_2^{-1} = H(s, v-s)_2^T$.
\medskip

Now $H(s,v-s)^T \, H(s,v-s) = (\alpha \, (L,M))$ with
\begin{center}
$\alpha \, (L, M) =  \displaystyle{\binom{|L \cap M| } { s}}, \; \; 
L, M \; (v-s)\mbox{-sets.}$
\end{center}
Now look at Pascal's triangle (more precisely at a part of it).
\vspace*{2cm}

\beginpicture

\setcoordinatesystem units <5mm, 5mm>

%Au"senlinien
\plot -11 -2  -5 4 /
\plot  16 -2  10 4 /

%durchgezogene Verbindungsslinien
%links von 0-Linie, Spitze
\plot -2 -5    0 -7 / 

\plot -2 -5      -1 -4 / %
\plot -1 -4      -0 -5 / %
\plot 0 -5     1 -6 /
\plot 0 -7        1 -6 / %
\plot -1 -6      -0 -5 /

%"rechts von 0-Linie, spitze
\plot 0 -5      1 -4 / 
\plot 1 -4      2 -5 /
\plot 2 -5      1 -6 /
 
%links oben
\plot -8 1  -6 -1 /
\plot -7 0   -6 1 /
\plot -6 1   -5 0 /
\plot -5 0   -6 -1 /
\plot -5 0   -4 1 /


%rechts oben
\plot 0 1     1 0 /
\plot 1 0    2 1 /
\plot 1 -0   2 -1 /
\plot 2 1   3 0 /
\plot 2 -1  3 0 /
\plot 3 0   4 1 /
\plot 3 0   4 -1 /
\plot 4 1   5 0 /
\plot 4 -1  5 0 /
\plot 5 0   6 1 /
\plot 5 0   6 -1 /
\plot 6 1   7 0 /
\plot 6 -1  7 0 /
\plot 7 0   8 1 /
\plot 7 0   6 -1 /

%gestrichelte Verbindungslinien
\setdots
%links oben nach rechts unten
\plot -4  1   1 -4 /
\plot -5  -0   -1 -4 /
\plot -6 -1   -2 -5 /

%rechts oben nach links unten (aussen)
\plot 6 -1     2 -5 /
\plot 4 -1     1 -4 /

%rechts oben nach links unten (innen)
\plot 2 -1     -1 -4 /
\plot 1 0      0 -1 /
\plot 0 1      -1 0 / 

%bigotimess and squares
\put {{$\blacksquare$}} at -8 1
\put {{$\bigotimes$}} at -6 1
\put {{$\bigotimes$}} at -4 1
\put {{$\bigotimes$}} at 0 1
\put {{$\bigotimes$}} at 2 1
\put {{$\bigotimes$}} at 4 1
\put {{$\bigotimes$}} at 6 1
\put {{$\bigotimes$}} at 8 1

\put {{$\blacksquare$}} at -7 0
\put {{$\bigotimes$}} at -5 0
\put {{$\bigotimes$}} at 1 0
\put {{$\bigotimes$}} at 3 0
\put {{$\bigotimes$}} at 5 0
\put {{$\bigotimes$}} at 7 0

\put {{$\blacksquare$}} at -6 -1
\put {{$\bigotimes$}} at 2 -1
\put {{$\bigotimes$}} at 4 -1
\put {{$\bigotimes$}} at 6 -1

\put {{$\bigotimes$}} at -1 -4
\put {{$\bigotimes$}} at  1 -4


\put {{$\blacksquare$}} at -2 -5
\put {{$\bigotimes$}} at 0 -5
\put {{$\bigotimes$}} at 2 -5

\put {{$\blacksquare$}} at -1 -6
\put {{$\bigotimes$}} at 1 -6

\put {{$\blacksquare$}} at 0 -7

%Beschriftungen
\put {$\binom{v-2s } { 0}$} at -9.7 1
\put {$\binom{v-2s } { s}$} at 9.7 1

\put {$\binom{v-s-1 } { s-1}$} at -2,8 -6,5
\put {$\binom{v-s-1 } { s}$} at 2,8 -6,5
\put {$\binom{v-s } { s}$} at 0 -8

\endpicture

\vspace*{1cm}
$\blacksquare = $ entry is odd, \qquad $\bigotimes = $ entry is even.
\bigskip

By moving in the triangle from left to right we obtain
\begin{center}
$2 \mid  \displaystyle{\binom{v-s-i } { s}}, \; 1 \le i \le s,$
\end{center}
in particular $v > 3s$.
\medskip

Therefore
\begin{center}
$H(s,v-s)_2^T \, H(s,v-s)_2 = (\alpha \, (L, M){\rm mod} \,2) = I$
\end{center}
and the claim is proved; furthermore
\begin{center}
$H(s,v-s)_2^+ = H(s,v-s)_2^T.$
\end{center}
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.
\bigskip

{\bf 3.} In the sequel we focus on {\it binary} Moore-Penrose
inverses of incidence matrices $H(s,k)_2$. Our main source of interest
is
\begin {itemize}
\item Construction of linear binary codes $C$ of the form 
$C= {\rm Ker} \, H(s,k)_2$ for appropriate $s,k$.
\end {itemize}
{ \bf Definition} {\it Let $0 \le s \le k \le v$. We say that $H(s,k)_2$
admits a {\it special\/} Moore-Penrose inverse, if it
admits a Moore-Penrose inverse and this equals $H(s,k)_2^T$.
}%it ende
\medskip

We need some elementary number theory. Let $p$ for a moment be an
arbitrary prime and let $n \in \I N$. If $p^{\alpha}, \; \alpha \ge 1$
occurs as a factor in the primary decomposition of $n$, call $\alpha$
to be the order ($={\rm ord}_p\,(n)$) of $p$ with respect to $n$. 
If $p \nmid n$, define ${\rm ord}_p\,(n) = 0$.

\begin {itemize}
\item ({Gau\ss})\qquad ${\rm ord}_p(n!) =  \displaystyle{\sum 
\limits_{i =1}^{\infty}   }
\left \lfloor   \displaystyle{\frac{n}{p^i} }\right \rfloor$.
\item ${\rm ord}_p (n!) =   \displaystyle{\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\ss' result).
\end {itemize}
Therefore
\begin {itemize}
\item ${\rm ord}_p  \left(\displaystyle{\binom{n } { m}}\right) = 
 \displaystyle{\frac{Q(m) + Q(n-m) - Q(n)}{p-1}}, \; 0 \le m \le n$.
\end {itemize}
In particular
\medskip

(1)$\ldots \qquad  {\rm ord}_2 
\left(  \displaystyle{\binom{n } { m}}  \right) =
Q(m) + Q(n-m) - Q(n), \; 0 \le m \le n$.
\medskip

This yields also an ``indirect proof'' that all ``$p$-adic'' functions
$Q: \I N_0 \rightarrow \I N_0$ are ``subadditive'', that is that
\begin{center}
$ Q(l+m) \le Q(l) + Q(m); \; m, l \in \I N_0, $
\end{center}
since
\begin{center}
$ 0 \le {\rm ord}_p \left(  \displaystyle{\binom{l+m } { m}}  \right) =
 \displaystyle{\frac{Q(m) + Q(l) - Q(m+l)}{p-1}}.$
\end{center}
\pagebreak

{ \bf Theorem 1} \qquad
{\it
Let $0 \le s < k \le v-s$ and $r \in \I N_0$ be such 
that
\begin{center}
$2^r \le k-s < 2^{r+1}.$
\end{center}
Assume $$v \equiv s+k \, {\rm mod} \, 2^{r+1}.$$
Then $H(s,k)_2$ admits a special Moore-Penrose inverse.
}% it ende
\bigskip

{ \bf Corollary} \qquad
{\it
$H(s,v-s)_2$ admits a special Moore-Penrose inverse.
}%it ende
\medskip

Proof: We use the following
\medskip

{ \bf Lemma 1} \qquad ([5], Chapter 15, 8.4) \\
\smallskip

{\it
Let $0 \le s \le k, \; 0 \le t \le k$. Then
\begin{center}
$H(s,k) \, H(t,k)^T =  \displaystyle{\sum \limits_i  \binom{v-s-t } { v-k-i} }
H(i,s)^T \, H(i,t).$
\end{center}
}% it ende
The proof of the lemma uses Vandermonde's identity for binomial coefficients.
\medskip

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

(2)$\ldots \qquad H(i,s)\,H(s,l) =  \displaystyle{\binom{l-i } { s-i}} H(i,l), \; \;
0\le i \le s \le l$, 
\smallskip

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

(3)$\ldots \qquad H(s,k) \, H(s,k)^T \, H(s,k) =
\displaystyle{\sum \limits_i   \binom{v-2s } { v-k-i}\binom{k-i } { s-i}} 
H(i,s)^T\, H(i,k).$
\medskip

Now consider the product
\begin{center}
$ \displaystyle{\binom{v-2s } { v-k-i}\binom{k-i } { s-i}}.$
\end{center}
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 \ge 0$ with $i \ge s-q$. We define a new running
index $j$ by
$$i = s-q+j, \; j \ge 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
\medskip

(4)$\ldots \qquad \left \{ \begin {array}{l}
\qquad H(s,k)\,H(s,k)^T\,H(s,k) =\\
\\
\displaystyle{\sum \limits _{j=max \{0, q-s \} }^q  
\binom{v-2s } { j}\binom{2q-j } { q}} \cdot H(s-q+j, k)^T \cdot H(s-q+j, s). 
\end{array}
\right. $
\medskip

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

(4')$\ldots \qquad \left \{ \begin {array}{l}
\qquad H(s,k)^T\,H(s,k)\,H(s,k)^T =\\
\\
\displaystyle{\sum \limits_{j=max\{0,q-s\}}^q 
\binom{v-2s } { j}\binom{2q-j } { q}} \cdot
H(s-q+j, k)^T \cdot H(s-q+j, s). 
\end{array}
\right .$
\bigskip

Claim: \qquad 
$ \displaystyle{\binom{v-2s } { j} \binom{2q-j } { q}}$ \; is \;  
$\left \{ 
\begin{array}{ll}
\mbox{ odd, } & \mbox{if } j=q,\\
\mbox{ even, }& \mbox{if } 0 \le j < q. 
\end{array} 
\right .$
\bigskip

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{array}{rll}
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{array}
$$ 
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.
\medskip

Now we prove the claim, first statement. By assumption
\begin{center}
$n: v-s \ge k-s = q \ge 1,$
\smallskip

$n \equiv q \, {\rm mod} \, 2^{r+1}.$
\end{center}
Let $n= \lambda \cdot 2^{r+1} + q, \; \lambda \in \I N_0, \;
q < 2^{r+1}.$ Therefore
$$ Q(n) = Q(\lambda \cdot 2	^{r+1}) + Q(q)$$
and
\smallskip

$\begin {array}{rcl}
{\rm ord}_2  
\left( \displaystyle{\binom{v-2s } { q}}  \right) & = &  
{\rm ord}_2  
\left( \displaystyle{\binom{n } { q}}  \right) =Q(q) + Q(n-q) - Q(n) = \\
\\
  & = & Q(q) + Q(\lambda \cdot 2^{r+1}) - (Q (\lambda \cdot 2^{r+1}) + Q(q))= 0
\end{array}$
\bigskip

To prove the second statement of the claim it is sufficient to show:
\begin{center}
If for some $j, \; 0 \le j < q, \;  \displaystyle{\binom{2q-j } { q}}$ is odd, then 
$ \displaystyle{\binom{n } { j}}$ is even.
\end{center}
By assumption
\medskip

(5)$\ldots \qquad 0 = {\rm ord}_2 
\left( \displaystyle{\binom{2q-j } { q}}\right) = 
Q(q) + Q(q-j) - Q(2q-j)$.
\smallskip

Since \qquad $n-j = \lambda \cdot 2^{r+1} + (q-j), \;
1 \le q-j < 2^{r+1},$
\smallskip

an easy calculation shows
\begin{center}
$ {\rm ord}_2 \left( \displaystyle{\binom{n } { j}}\right) = Q(j) + Q(q-j) - Q(q).$
\end{center}
Combine this with Eq (5) and obtain
\begin{center}
${\rm ord}_2\left( \displaystyle{\binom{n } { j}}\right) = Q(j) + 2Q(q-j) -Q(2q-j).$
\end{center}
Now we use the subadditivity of $Q$ and $Q(2l) = Q(l), \; l \in \I N_0$
and obtain
\medskip

$\begin {array}{rcl}
{\rm ord}_2\left ( \displaystyle{\binom{n } { j}}\right) & =   & Q(j) + 
(Q(2q-2j) + Q(q-j)) - Q(2q-j)\\
        & =   & (Q(j) + Q(2q-2j)) + Q(q-j) - Q(2q-j)\\[1.7mm]
       & \ge & Q(2q-j) + Q(q-j) - Q(2q-j) = Q(q-j) > 0.
\end{array}$
\bigskip

This proves the claim. \hspace*{\fill}$\square$
\medskip

{ \bf Remark} \qquad In the theorem the condition $0 \le s < k \le 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 \mbox{ odd ,} \; \, s \le \frac{v-1}{2}.$$
However, this is true for $v$ odd and all $s, \; 0 \le s \le v-1.$
\bigskip

{\bf 4.} In this section we come to an application. Let $\I F$ be any field.
We associate to the integer matrix $H(s,k)$ a linear map $H(s,k)_{\I F}$
of $\I F$-vectorspaces as follows. Let $C_i, \; 0 \le i \le v$ the
$\I F$-vectorspace with base $\{\underline{T}\}$, where $T$ runs through
all $i$-subsets of the $v$-set and let the linear map
$$H(s,k)_{\I F} : C_k \rightarrow C_s$$
induced by
$$H(s,k)_{\I F} \, (\underline{T}) = \sum \limits_{S \subset T}^{|S|=s}
\underline{S}, \; \, |T|=k.$$

In case $\I F = \I F_p$ we write again $H(s,k)_{\I F} = H(s,k)_p$.
\bigskip

{ \bf Theorem} \; (A. Bjerhammar [4], R. Penrose [7]) 
{\it
Let $\I F$
be a field and $A, G$ be $m \times n$ resp. $n \times m$ matrices with 
entries in $\I F$ 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 \mbox{ arbitrary.}$$ } %it ende

In particular \; ${\rm Ker} \, A = {\rm Im} \, (I-GA).$
\medskip

Let $p$ be an arbitrary prime and suppose that $H(s,k)_p$ admits a 
Moore-Penrose inverse. Then
\medskip

(6)$\ldots \qquad {\rm Ker} \, H(s,k)_p = {\rm Im} \,
(I-H(s,k)_p^+ \, H(s,k)_p).$
\medskip

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

(7)$\ldots \qquad  U_{s,k}^p :=  \displaystyle
\underset{p \,\vert\, \binom{v-s-j } { k-s}}{\sum
_{0 \le j \le v-(k+1)}  } \, {\rm Im} \,
H(k, v-j)_p$
\bigskip

is a subspace of ${\rm Ker} \, H(s,k)_p$ (of course, the above sum
may be empty). We make the following
\bigskip

{ \bf Conjecture} \qquad 
{\it
Let $0 < s < k < v,$ and let $p$ be a prime. Then 
$${\rm Ker} \, H(s,k)_p = U_{s,k}^p.$$}%it ende

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
\begin{center}
$H(s+1, s+2)_2 \cdot H(s+2, v-j)_2 = (v-j-s-1) \cdot 1 \cdot
H(s+1, v-j)_2 \linebreak[4]
= H(s+1, v-j), \; 1 \in \I F_2, \; s+2 \le v-j.$
\end{center}
Therefore
$$U_{s, s+1}^2 \supseteq {\rm Im} \, H(s+1,s+2)_2 \supseteq
{\rm Im} \, H(s+2, v-j)_2$$
and $U_{s, s+1}^2 = {\rm Im} \, H(s+1, s+2)_2$. It has been
remarked in [7], Prop. 7, that ${\rm Ker}\, H(s, s+1)_2 =
{\rm Im} \, H(s+1, s+2)_2 \; \, (=U_{s, s+1}^2)$. --
\medskip

This example also shows that the sum in eq. (7) might be ``redundant''. 
\medskip

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

Let $0< s < k = v-s$ and $p$ a prime. Then
$${\rm det} \, H(s,v-s) = \prod_{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
$${\rm Ker} \, H(s,v-s)_p \ne (0) \mbox{ iff } p \mid {\rm det} \,
H(s,v-s) \, \mbox{ iff } \, U_{s,v-s}^p \ne (0). -$$
\smallskip

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

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

(8)$\ldots \qquad {\rm Ker} \, H(s,v-s)_2 = {\rm Im} \, 
(I + H(s,v-s)_2^T \, H(s,v-s)_2).$
\bigskip

{ \bf Proposition} \qquad 
{\it
Let $0 < 2s < v$ and assume that
$$H(s,v-s)_2 : C_{v-s} \rightarrow C_s$$
is an isomorphism. Then \, $3s < v$. In particular, if \, $0< 2s < v \le 3s$
then ${\rm Ker} \, H(s,v-s)_2$ is nonzero.
}% it ende
\bigskip

Proof: By assumption ${\rm Ker} \, H(s,v-s)_2 = (0)$. Then eq. (8) yields
$$I = H(s,v-s)_2^T \, H(s,v-s)_2 = \left ( \binom{|L \cap M| } { s}\,
{\rm mod} \, 2 \right ).$$
Now if $L, M$ vary through all $(v-s)$-sets, ${
\binom{|L \cap M| } { s} }$ takes all values \linebreak[4]
${
\binom{v-s-j } { s}  } =: \alpha_j, \; 0 \le j \le s$. Now we have
$\alpha_0 > 1$ (and $\alpha_0$ odd) and $\alpha_j$ even if 
$0 < j$. This implies $v-2s > s$. \hspace*{\fill}$\square$
\bigskip

At the same time we have proved the 
\bigskip

{ \bf Corollary} \qquad
{\it
Assume that $ 0 < 2s \le v$ and that $H(s,v-s)_2$ is nonsingular. Then
$H(s,v-s)_2^{-1} = H(s,v-s)_2^T$.
}%it ende
\bigskip

From now on we assume $0 < 2s < v \le 3s$. To prove the conjecture
for $H(s,v-s)_2$ it is sufficient to show that 
\medskip

(9)$\ldots \qquad {\rm Im}\,(I + H(s,v-s)_2^T \, H(s,v-s)_2) \subseteq
U_{s,v-s}^2 =: U_s$.
\medskip

We first describe briefly the lines of the proof. Now ${\rm Ker}\,
H(s,v-s)_2$ is generated by the elements
$$\sigma_M := \underline{M} + \sum \limits^{|L| = v-s} \binom{|M \cap L| } { s}
\cdot 1 \cdot \underline{L}, \, \; |M| = v-s, \; 1 \in \I F_2.$$
Now we put $v-2s =: q, \; 1 \le q \le s$. Furthermore 
$|L \cap M| = v-s-j$ \, iff \, $|L \cup M| = v-s+j$. We define
$$S_{v-l}^M = \underset{|L \cup M| = v-l}{\sum _{|L| = v-s}} \underline{L},
\; \, 0 \le l \le s.$$
(Observe that $S_{v-s}^M = \underline{M}$). Then we rewrite the generators
$\sigma_M$ of \linebreak[4] ${\rm Ker}\,H(s,v-s)_2$:
\medskip

(10)$\ldots \qquad \sigma_M = \left( \displaystyle{\binom{s+q } { s}  }
\cdot 1 + 1 \right) \cdot
\underline{M} + \displaystyle{\sum \limits_{l=0} ^{s-1}  
\binom{l+q } { s}  } \cdot 1 \cdot S_{v-l}^M, \; 1 \in \I F_2.$
\medskip

Observe that all $\sigma_M$ are nonzero.
\medskip

If $X$ is a subset of the $v$-set denote by $\complement X$ the
complement of $X$.
\bigskip

{ \bf Lemma 2} \qquad 
{\it
Let $M$ be a $(v-s)$-subset of the $v$-set. Then for $0 \le t \le s$
one has
$$\tau_t^M := \sum \limits_{|T|=t, T \subset \complement M} ^T
H(v-s, v-t)_2 \; (\complement T) = \sum \limits_{l=0}^s \binom{l } { t}
\cdot 1 \cdot S_{v-l}^M.$$
Furthermore if ${ \binom{v-s-t } { s-t}  } $ is even then
all $\tau_t^M$ are contained in ${\rm Ker} \, H(s,v-s)_2$.
} %it ende
\bigskip

Proof: Let $L$ be a $(v-s)$-set and $|L \cup M| = v-l, \, 0 \le l \le s$ and $ R := \complement (M \cup L)$.
Then 
$$L \subset \complement T \, \mbox{ iff } \; \complement R =
M \cup L \subset \complement T \; \mbox{ iff } \; R \supset T.$$
In particular $l \ge 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 \ge 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).
\medskip

The last assertion follows from eq. (2). \hspace*{\fill}$\square$
\medskip

Now we will show that all generators $\sigma_M$ of ${\rm Ker} \,
H(s,v-s)_2$ are sums of elements $\tau_t^M$ for appropriate $t$ all of
which are contained in ${\rm 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$.--
\medskip

To state the next result we define on $\I N_0$ a 
partial order ``$\prec$'' as follows. 
If $j, q \in \I N_0$ and 
$$j = \sum \limits_{i \ge 0} a_i 2^i, \; 
q = \sum \limits_{i \ge 0}b_i 2^i$$
are the 2-adic expansions of $j$ resp. $q$, we define
$$j \prec q \mbox{ if } a_i \le b_i \mbox{ for all } i \ge 0.$$
Then put ${\cal M}(q) = \{j : j \in \I N_0, \; j \prec q \}$
and
${\cal M}(q)^* = {\cal M}(q) \setminus \{0\}$. 
\medskip

So, for example for $ t \ge 1$
\medskip

$\begin {array}{rcl}
\qquad \qquad \qquad {\cal M}(2^t-1) &  =&  \{0,1,2, \ldots, 2^t-1\},\\
\qquad \qquad \qquad {\cal M}(2^t)   &  =&  \{0, 2^t\},\\
\qquad \qquad \qquad {\cal M}(2^t+1) &  =&  \{0,1,2^t, 2^t+1\}.
\end{array}$
\bigskip

{ \bf Theorem 2} \qquad 
{\it
Assume $0 < 2s < v \le 3s$. Then ${\rm Ker} \, H(s,v-s)_2$ is nonzero and
$${\rm Ker} \, H(s,v-s)_2 =\underset {2 \,\vert\, \binom{v-s-i } { v-2s}} 
{\sum _{0 \le i \le s-1}}
{\rm Im} \,  H(v-s, v-i)_2.$$
Moreover it already holds that
$$ {\rm Ker} \,  H(s,v-s)_2 = \sum \limits
_{j \in {\cal M}(v-2s)^*}
{\rm Im} \,  H(v-s, v-s+j)_2.$$
}% it ende
\smallskip

So the theorem states for example that 
\smallskip

in case $v-2s = 2^t-1, \; t \ge 1,$
$${\rm Ker}  \, H(s,v-s)_2 = \sum \limits_{j=1} ^{2^t-1}
{\rm Im} \,  H(v-s, v-s+j)_2,$$
%\smallskip
in case $v-2s = 2^t, \; t \ge 0,$
$${\rm Ker}  \, H(s, v-s)_2 = {\rm Im}  \, H(v-s, v-s+2^t)_2,$$
%\smallskip
in case $v-2s = 2^t+1, \; t \ge 1,$
\begin{center}
${\rm Ker} \,  H(s,v-s)_2 = $
\smallskip

${\rm Im} \,  H(v-s,v-s+1)_2 + 
{\rm Im}  \, H(v-s,v-s+2^t)_2 + {\rm Im} \, H(v-s,v-s+2^t+1)_2. $--
\end{center}
\smallskip

Proof of the theorem: We use the notations introduced above.
\medskip

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

$\begin{array}{lcl}
\displaystyle{\binom{l+2 } { s}} & = &
\displaystyle{\binom{l+1 } { s} + \binom{l+1 } { s-1}}\\[4mm] 
  &  = & \left(\displaystyle\binom{l } { s} + \binom{l } { s-1}\right) 
+ \left(\displaystyle\binom{l } { s-1} + \binom{l } { s-2}\right)\\[4mm]
  &  = & \displaystyle{\binom{l } { s} + 2\binom{l } { s-1} + \binom{l } { s-2}}
   \equiv  \displaystyle{\binom{l } { s} + \binom{l } { s-2} }\, {\rm mod} \, 2.
\end{array}$
\bigskip

So we reach a congruence
\medskip

(11)$\ldots \qquad \displaystyle{\binom{l+q } { s} \equiv
\sum \limits _{i \in \overline{{\cal M}}(q)} \binom{l } { s-i}   }
\,{\rm mod}\, 2,$
\medskip

with a certain subset $\overline{ {\cal M}} (q)$ of $\{0,1,2,\ldots,q\}$
which contains $0$ and $q$. To determine this subset we consider the
$\I F_2$-vectorspace
$$V = \I F_2^{(\I Z)} = \{f:\; \, f: \I Z \rightarrow \I F_2, \, 
\mbox{ almost all } f(m) = 0, \, m \in \I Z \}.$$
Let ${\rm Supp}\, f = \{m : f(m) \ne 0\}$. Define the basis
$\{e_m:\, m \in \I Z \}$ of $V$ by
$$ e_m  (r) = \left \{ \begin {array}{rl}
1, & r = m,\\
0, & \text{otherwise.}
\end{array}
\right .$$

Finally we define the linear map $\varphi: V \rightarrow V$ to be 
induced by
$$\varphi(e_m) = e_m + e_{m-1}, \; m \in \I Z.$$
Now we rewrite eq. (11) as follows:
\medskip

(12)$\ldots \qquad \displaystyle{ \binom{l+q } { s} \equiv
\sum \limits 
_{r \in {\rm Supp}\, \varphi^q (e_s)}  
\binom{l } { r}    }
\, {\rm mod} \, 2$.
\bigskip

\smallskip

{ \bf Lemma 3} {\it \qquad If $m \in \I Z$ and $q \in \I N$, then
$$ {\rm Supp}\, \varphi^q (e_m) = \{m-j:j \in {\cal M}(q)\}.$$ }%it ende

Proof: First we prove that the assertion is true if 
$q=2^t, \; t \ge 0, \;$ by induction on $t$. If $t = 0$, then
$${\rm Supp} \, \varphi(e_m) = {\rm Supp}\, (e_m + e_{m-1}) 
= \{m-j:j \in {\cal M}(1)\}.$$
Suppose the claim is true for $q = 2^t$. Then
\begin{center}
$ \varphi^{2^{t+1}}(e_m) 
= \varphi^{2^t}(\varphi^{2^t}(e_m) 
= \varphi^{2^t}(e_m +e_{m-2^t})
\linebreak[4]
= (e_m + e_{m-2^t}) 
+ (e_{m-2^t} + e_{m-(2^t+2^t)}
= e_m + e_{m-2^{t+1}},$
\end{center}
so the claim is true for $q = 2^{t+1}$.
\medskip

Now we suppose that the assertion is true for all $q \in \I N$ and 
$q \le 2^t$. Then we show now that the assertion is true for all
$q \in \I N$ and $q \le 2^{t+1}$ (this will finish the proof). We 
may now assume $2^t < q < 2^{t+1}$, \, so $q = 2^t + u$, \; 
$1 \le u < 2^t$.
Then by hypothesis
$$\varphi^q (e_m)
= \varphi^u (\varphi^{2^t} (e_m)) 
= \varphi^u (e_m + e_{m-2^t})
= \sum \limits
_{i \in {\cal M}(u)} e_{m-i}
+ \sum \limits
_{i \in {\cal M}(u)} e_{m-2^t-i}.$$
Since ${\cal M}(q) = {\cal M}(2^t + u)
= {\cal M} (u) \cup \{2^t +i: i \in {\cal M}(u) \} $ we obtain
\smallskip

$\varphi^q(e_m) = \displaystyle{\sum \limits_{j \in {\cal M}(q)}  }
e_{m-j}$ as claimed. \hspace*{\fill}$\square$
\bigskip

We conclude from eq. (12) and the lemma
\medskip

(13)$\ldots \qquad \displaystyle{ \binom{l+q } { s} \equiv
\sum \limits _{j \in {\cal M}(q)} \binom{l } { s-j}   }
\, {\rm mod} \, 2.$ --
\medskip

Now we show that all $\tau_{s-j}^M, \; j \in {\cal M}(q)^*$ are
contained in ${\rm 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 \in {\cal M}(q)^*$$
are even. But since $j \prec q, \; 1 \le j$, we have
$$Q(q+j) < Q(q) + Q	(j), $$
whence ${\rm ord}_2 \big( {\binom{q+j } { j}} \big)
> 0$ as claimed.--
\medskip

Finally we claim that
\medskip

(14)$\ldots \qquad \sigma_M
= \displaystyle{ 
\sum \limits_{j \in {\cal M}(q)^*} \tau_{s-j}^M
= \sum \limits_{j \in {\cal M}(q)^*}
  \sum \limits_{l=0}^s \binom{l } { s-j}
}
\cdot 1 \cdot S_{v-l}^M$.
\medskip

In fact the coefficient of $S_{v-s}^M = \underline{M}$ with respect to
$\sigma_m$ is ${ \binom{s+q } { s} } \cdot 1 + 1$ and with
respect to the R.S. of eq. (14) is
${ \sum \limits _{j \in {\cal M}(q)^*} \binom{s } { s-j}   }
\cdot 1$. Both coefficients agree by eq. (13).
\medskip

Furthermore the coefficient of $S_{v-l}^M, \; 0 \le l < s$ with respect
to $\sigma_M$ is ${ \binom{l+q } { s}  } \cdot 1 $ 
(according to eq. (10)) and with respect to the R.S. of eq. (14) is
${ \sum \limits_{j \in {\cal M}(q)^*} \binom{l } { s-j} } 
\cdot 1$ which is ${ \sum \limits_{j \in {\cal M}(q)}
\binom{l } { s-j} } \cdot 1$ since $l<s$ and ${ \binom{l } { s}} 
= 0$. Again both coefficients coincide according to eq. (13). This
proves eq. (14).
%\smallskip

Now we have the following chain of inclusions
$$U_s \subseteq {\rm Ker} \, H(s,v-s)_2 \subseteq
\sum \limits _{j \in {\cal M}(q)^*} {\rm Im} \, H(v-s,v-s+j)_2 
\subseteq U_s.$$
Therefore throughout equality must hold.
\medskip

This proves the theorem. \hspace*{\fill}$\square$
\bigskip

{\bf Remark} \qquad 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 $\I F_p$-vectorspaces.

$${\rm Im}\, H(s,l)_p \subseteq 
\underset{p \mid \binom{l-i } { s-i}}{\bigcap _{i<s}}
{\rm Ker}\, H(i,s)_p, \; \; p \mbox{ prime.}$$
\smallskip

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.
\bigskip

\par
\fontsize{12}{13pt} \selectfont
\begin{thebibliography}{16}
\bibitem [1]{1}{\sc R.B. Bapat}: {\it Moore-Penrose inverses of set inclusion 
matrices}. Lin. Alg. and Appl., 318 (2000), 35-44.
\bibitem [2]{2}{\sc R.B. Bapat, K.P.S. Bhaskara, and K. Manjunatha Prasad}:
{\it Generalized inverses over integral domains}. Lin. Alg. and Appl., 140 
(1990), 181-196.
\bibitem [3]{3} {\sc Th. Bier}: {\it Eine homologische Interpretation gewisser 
Inzidenzmatrizen {\rm mod}\,$p$}. Math. Annalen 297 (1993), 289-302.
\bibitem [4]{4} {\sc A. Bjerhammar}: {\it A generalized matrix algebra}. 
Kungl. Tekn. H"ogsk. Handl. No. 124 (1968), 32 pp.
\bibitem [5]{5} {\sc C.D. Godsil}: Algebraic Combinatorics. New York-London
1993 (Chapman \& Hall).
\bibitem [6]{6} {\sc N. Koblitz}: $p$-adic Numbers, $p$-adic Analysis, 
and Zeta-Functions. New York-Heidelberg-Berlin, 1977 (Springer).
\bibitem [7]{7} {\sc H. Kr"amer}: {\it Eigenspace decompositions 
with respect to symmetrized incidence mappings}. Seminaire Lotharingien 
de Combinatoire, Art.~B41c (1998), 20 pp. \\
http://www.mat.univie.ac.at/$\sim$slc/
\bibitem [8]{8} {\sc R. Penrose}: {\it A generalized inverse for matrices}. Proc.
Cambridge Philos. Soc. 51 (1955), 406-413.
\bibitem [9]{9} {\sc R.M. Wilson}: {\it A diagonal form for the 
incidence matrices of $t$-sets vs. $k$-subsets}. 
Europ. J. Combinatorics 11 (1990), 609-615.

\end{thebibliography}



\end{document}