\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