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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.