3
$\begingroup$

In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is $$ Rk_{2}(N)=v-(d_{p}+1), $$ where $d_{p}$ is the projective dimension of $S$.

I would like to know if there are known generalizations of this result in one (or better both!) of the following ways:

  1. Replacing $S(2,3,v)$ with a more general design $S_{\lambda}(t,k,v)$.

  2. Replacing the incidence matrix $N$ with a higher incidence matrix $N_{s}$.

$N_{s}$ has $\binom{v}{s}$ rows indexed by all $s$-subsets of $\{1,2,\ldots,v\}$ and its columns are indexed by the blocks of $S$, with $N_{s}(A,B)=1$ if $A \subseteq B$ and $0$ otherwise. The usual incidence matrix $N$ is equal to $N_{1}$.

$\endgroup$

1 Answer 1

3
$\begingroup$

For the generalization in the first direction, the $p$-rank of the incidence matrix $N$ of an $S(2,k,v)$ is lower bounded by the dimension of the Steinberg module:

$$\operatorname{rank}_2(N)(\operatorname{rank}_2(N)-1) \geq \frac{(v-1)(v-k)}{k} \quad \text{if} \frac{v-k}{k-1} \text{is even}$$ and if further $k$ is odd, $$\operatorname{rank}_2(N) \geq 1+\sqrt{\frac{(v-1)(v-k)}{k}}.$$ If $\frac{v-k}{k-1}$ is odd, a simple argument shows that $$\operatorname{rank}_2(N) \geq v-1$$ with equality if and only if $k$ is even.

A more general bound can be proved by applying the result given in the following paper and other known facts:

G. Hillebrandt, The $p$-rank of $(0,1)$-matrices, J. Combin. Theory, Ser A, 60 (1992), 131-139.

This and some other facts about the rank of an $S_{\lambda}(2,k,v)$ are explained in the language of design theory in Section 2.4 of Designs and Their Codes by E. F. Assmus Jr. and J. D. Key.

As in the case of $S(2,3,v)$s, the lowest rank has been studied in relation to geometric designs. The rank of the incidence matrix of the $2$-design formed by the points and subspaces of projective/affine geometry can be computed by well-known Hamada's formula for many cases, although it is a little cumbersome. A more general result in this direction is available here:

D. B. Chandler, P. Sin, Q. Xiang, The invariant factors of the incidence matrices of points and subspaces in $ \operatorname{PG}(n,q)$ and $ \operatorname{AG}(n,q)$, Trans. Amer. Math. Soc., 358 (2006), 4935-4957.

They determined the Smith normals form of the incidence matrices of points and projective $(r-1)$-dimensional subspaces of $\operatorname{PG}(n,q)$ and of the incidence matrices of points and $r$-dimensional affine subspaces of $\operatorname{AG}(n,q)$ for all $n$, $r$, and arbitrary prime power $q$. If you want a quick summary of their results and other related known results in the language of design theory, a survey by the third author is available:

Q. Xian, Recent results on $p$-ranks and Smith normal forms of some $2$−$(v,k,\lambda)$ designs, Contemp. Math., 381 (2005) 53-67.

I don't know much about the rank of the incidence matrix of an $S(t,k,v)$ over $\mathbb{F}_2$ when $t \geq 3$. But this paper studies the problem for $S(t,t+1,v)$s, and this one seems to give some results for $S(t,t+2,v)$s.

As for the generalization in the second direction, it's always full rank. For example, $N_2$ is ${{v}\choose{2}}$ binary row vectors of weight $1$ stacked together in which the column weights are uniformly $1$. And $N_3$ is the $\frac{v(v-1)}{6} \times \frac{v(v-1)}{6}$ identity matrix plus a bunch of row zero vectors underneath.

About the combination of the two types of generalizations, allowing $k > 3$ doesn't really change the situation; you always get a matrix of full rank. But increasing $t$ and/or $\lambda$ may lead to a nontrivial situation. For example, the classic rank formula for the $s$-subset vs. $t$-subset inclusion matrix by Wilson can be seen as an example of the generalization of this kind for the trivial $S(t,t,v)$ design:

R. M. Wilson, A diagonal form for the incidence matrices of $t$-subsets vs. $k$-subsets, European J. Combin., 11 (1990), 609-615

But other than this, I haven't thought or heard about generalizations you asked.

A similar problem has been considered in the following papers on an application of modular representation theory:

A. Frumkin, A. Yakir, Rank of inclusion matrices and modular representation theory, Israel J. Math. 71 (1990), 309-320.

A. Yakir, Inclusion matrix of $k$ vs. $l$ affine subspaces and a permutation module of the general affine group, J. Combin. Theory, Ser. A, 63 (1993), 301–317.

Basically, they consider the rank of the "$s$-dimensional subspaces vs. $t$-dimensional subspaces" incidence matrices of projective/affine geometry over $\mathbb{F}_q$. So, for example, when $s = 1$, the problem reduces to the case of the standard incidence matrix $N$ of the corresponding $2$-designs. And the case when $s >1$ is the $s$-dimensional version of the problem you described.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .